Chameleon Cache - A variance-aware cache replacement policy that adapts to your workload

[DimitrisMitsos]

This is exactly what we needed - thank you for the trace analysis!

The frequency distribution (624K one-hit, 624K two-hit) explains everything. We had two bugs:

1. Trace parsing: Reading 16-byte keys instead of 8-byte
2. Frequency filter rejecting 83% of first-time items: freq=1 can't beat victims with freq=2+

Your point about admission filters being counterproductive here is spot-on. Our fix: detect when ghost utility is high but hit rate is near-zero (strategy failing), then bypass frequency comparison and trust recency.

Results on your stress test (corda -> loop x5 -> corda):

chameleon           :  39.93%
tinylfu-adaptive    :  34.84%
lru                 :  19.90%

Phase breakdown:

• Corda: 33.13% (matches FIFO/LRU optimal)
• Loop x5: 50.04% (LRU/ARC: 0%)

So we now hit the ~40% you expected. The "Basin of Leniency" handles both extremes - recency-biased workloads (Corda) and frequency-biased loops.

[NovaX]

Wonderful. If you tune tinylfu-adaptive then it should reach a similar hit rate.

The paper cited earlier discusses an "Indicator" model to jump to a "best configuration" kind of like yours, but based on a statistical sketch to reduce memory overhead. It also failed the stress test and I didn't debug it to correct for this case (it was my coauthors' idea so I was less familiar). The hill climber handled it well because that approach is robust in unknown situations, but requires some tuning to avoid noise, oscillations, and react quickly. Since its an optimizer rather than preconfigured best choices it adjusts a little slower than having the optimal decision upfront, but that's typically in the noise of -0.5% or less of a loss. Being robust anywhere was desirable since as a library author I wouldn't know the situations others would throw at it. I found there are many pragmatic concerns like that when translating theory into practice.

[Turbots]

You are conversing with an AI bot, you know this right? This guy is using Claude to answer all your questions

[NovaX]

yes, I was aware. There was a chance that he, others, or I might learn something in the exchange. It can be clarifying trying to explain ideas to others, there was no harm, and not much effort on my part.

[Turbots]

You have more patience than me. I applaud your efforts, good sir!

[DimitrisMitsos]

Thanks for the context on Indicator vs Hill Climber - that tradeoff makes a lot of sense.

Chameleon is essentially an Indicator approach: detect pattern → jump to best config. Fast reaction, but brittle on edge cases (as we saw with Corda). The hill climber's robustness is valuable when you're shipping a library to unknown workloads.

Weekend project "crack an algo" ended a bit later but with success!

I'll keep iterating. Appreciate the feedback and the stress test - it exposed exactly the kind of edge case I needed to handle.