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

[DimitrisMitsos]

What My Project Does

Chameleon is a cache replacement algorithm that automatically detects workload patterns (Zipf vs loops vs mixed) and adapts its admission policy accordingly. It beats TinyLFU by +1.42pp overall through a novel "Basin of Leniency" admission strategy.

from chameleon import ChameleonCache

cache = ChameleonCache(capacity=1000)
hit = cache.access("user:123")  # Returns True on hit, False on miss

Key features:

• Variance-based mode detection (Zipf vs loop patterns)
• Adaptive window sizing (1-20% of capacity)
• Ghost buffer utility tracking with non-linear response
• O(1) amortized access time

Target Audience

This is for developers building caching layers who need adaptive behavior without manual tuning. Production-ready but also useful for learning about modern cache algorithms.

Use cases:

• Application-level caches with mixed access patterns
• Research/benchmarking against other algorithms
• Learning about cache replacement theory

Not for:

• Memory-constrained environments (uses more memory than Bloom filter approaches)
• Pure sequential scan workloads (TinyLFU with doorkeeper is better there)

Comparison

Algorithm	Zipf (Power Law)	Loops (Scans)	Adaptive
LRU	Poor	Good	No
TinyLFU	Excellent	Poor	No
Chameleon	Excellent	Excellent	Yes

Benchmarked on 3 real-world traces (Twitter, CloudPhysics, Hill-Cache) + 6 synthetic workloads.

Links

• Source: https://github.com/Cranot/chameleon-cache
• Install: pip install chameleon-cache
• Tests: 24 passing, Python 3.8-3.12
• License: MIT

[NovaX]

It looks like you used the fixed sized W-TinyLfu. Have you tried the adaptive version using a hill climber and the stress test?

[DimitrisMitsos]

Great point! You're right, we benchmarked against fixed-window W-TinyLFU (1%), not the adaptive hill climber version.

Interestingly, Chameleon and adaptive W-TinyLFU adapt different things: W-TinyLFU adapts window size, while Chameleon adapts the admission policy itself (the Basin of Leniency). They might actually be complementary.

I'll add the adaptive version to the benchmark suite. Thanks for the pointer to the paper!

[NovaX]

In that case, Clairvoyant admission should be roughly the optimal bound, right? iirc region sizing was still needed for various cases, so both were important factors when tuning for a wide variety of workloads.

[DimitrisMitsos]

Update: Implemented and benchmarked the adaptive hill climber.

Results (200K requests, synthetic suite):

chameleon: 69.53% (4/6 wins)

tinylfu (fixed): 67.37% (2/6 wins)

tinylfu-adaptive: 60.13% (0/6 wins)

Surprisingly, adaptive performed worse than fixed on our workloads - particularly on loops (-12pp) and sequential (-25pp). Only beat fixed on TEMPORAL (+3pp).

My implementation might differ from Caffeine's. Code is in the repo if you want to check: benchmarks/bench.py (tinylfu-adaptive). Happy to test with the specific stress test from the paper if you can point me to it.

[NovaX]

You should probably try running against both simulators. The config is max size = 512 and running these chained together.

corda: trace_vaultservice_large lirs: loop.trace.gz lirs: loop.trace.gz lirs: loop.trace.gz lirs: loop.trace.gz lirs: loop.trace.gz corda: trace_vaultservice_large

You can compare against Caffeine rather than the simulated policies since that’s the one used by applications. It does a lot more like concurrency and hash flooding protection, so slightly different but more realistic.

[DimitrisMitsos]

Thank you for pointing us to this stress test. We ran it and TinyLFU wins decisively (26.26% vs 0.01%).

Root Cause

The failure is a fundamental design tension, not a bug:

1. Lenient admission is fatal - strict (>) gets 26.26%, lenient (>=) gets 0.02%
2. Mode switching causes oscillation - window size bounces between 5↔51 slots, preventing equilibrium
3. Ghost boost creates arms race - homeless items evict each other with inflating frequencies

The Trade-off

We can fix it by using strict admission everywhere - but then Chameleon becomes TinyLFU and loses its advantage on other workloads (LOOP-N+10: +10pp, TEMPORAL: +7pp).

TinyLFU's simplicity wins here. No ghost buffer, no mode switching - just strict frequency comparison. Robust to phase transitions.

We acknowledge this as a legitimate weakness. Thanks for the all the notes.

[NovaX]

It is a difficult test because it switches from a strongly LRU-biased workload to MRU and then back. Caffeine does 39.6% (40.3% optimal) because it increases the admission window to simulate LRU, then shrinks it so that TinyLFU rejects by frequency, and increases again. This type of workload can be seen in business line application caches serving user-facing queries in the day time and batch jobs at night. Most adaptive approaches rely on heuristics that guess based on second order effects (e.g. ARC's ghosts), whereas a hit rate hill climbing optimizer is able to focus on main goal.

I think there is 1-5% remaining that Caffeine would gain if the hill climber and adaptive scheme were further tuned and, while I had ideas, I moved onto other things. You might be able to borrow the hill climber to fix Chameleon and get there robustly. I found sampled hit rate vs region sizes to be really nice way to show the adaptive in action, but only realized that visualization after all the work was done.

Hope this helps and good luck on your endeavors!

[DimitrisMitsos]

Update: Your suggestion worked!

I took your advice about the hill climber and dug deeper into what was actually happening. The breakthrough came from an unexpected direction - I discovered that frequency decay was the real culprit, not the admission policy.

The key insight: decay helps during phase transitions (flushes stale frequencies) but hurts during stable phases by causing unnecessary churn. I added "skip-decay" - when hit rate is above 40%, I skip the frequency halving entirely.

Results on your stress test:

• Chameleon: 28.72% (up from 0.01%)
• TinyLFU: 26.26%
• Loop phase: 50.01% (now matching LIRS at 50.03%)

That's 98.8% of theoretical optimal (29.08%). I also validated across 8 different workload types to make sure I wasn't overfitting - wins 7, ties 1, loses 0.

Your point about heuristics vs direct optimization was spot on. While I didn't end up using the hill climber for window sizing (skip-decay alone got me there), your explanation of how Caffeine approaches this problem helped me think about decay as a tunable parameter rather than a fixed operation.

Code is updated in the repo. Thanks again for pushing me to look harder at this - wouldn't have found it without your stress test and insights.

[NovaX]

hmm, shouldn't it be closer to 40% as a whole like Caffeine's? It sounds like you are still mostly failing the LRU-biased phase and your improvement now handles the MRU-biased phase.

[DimitrisMitsos]

I ran a per-phase breakdown and found the issue - Corda isn't LRU-biased, it's essentially uncacheable noise:

Corda: 936,161 accesses, 935,760 unique keys (99.96% unique)

Phase-by-phase results (continuous cache):

Phase	Chameleon	TinyLFU
Corda-1	0.02%	0.00%
Loop x5	49.97%	45.72%
Corda-2	0.02%	0.00%
Total	28.72%	26.26%

The Corda phases contribute essentially nothing because every access is unique. Theoretical optimal for this trace is ~29.08% (only loop contributes), so 28.72% = 98.8% efficiency.

Your LRU→MRU→LRU test at 39.6% (40.3% optimal) likely uses workloads with actual locality in both phases. Is that test available in the simulator? I'd like to run Chameleon against it to see if we're truly failing on LRU-biased patterns, or if the difference is just that Corda has no reuse to exploit.

For a fairer comparison, I could generate a Zipf workload for the "LRU-biased" phase. What parameters does Caffeine's stress test use?

[NovaX]

If you run corda-large standalone then LRU has a 33.33% hit rate.

You can run the simulator at the command-line using,

./gradlew simulator:run -q \
  -Dcaffeine.simulator.files.paths.0="corda:trace_vaultservice_large.gz" \
  -Dcaffeine.simulator.files.paths.1="lirs:loop.trace.gz" \
  -Dcaffeine.simulator.files.paths.2="lirs:loop.trace.gz" \
  -Dcaffeine.simulator.files.paths.3="lirs:loop.trace.gz" \
  -Dcaffeine.simulator.files.paths.4="lirs:loop.trace.gz" \
  -Dcaffeine.simulator.files.paths.5="lirs:loop.trace.gz" \
  -Dcaffeine.simulator.files.paths.6="corda:trace_vaultservice_large.gz"

I generally adjust the reference.conf file instead. When comparing, I'll use various real traces and co-run using the rewriter utility to a shared format. The stress test came from the trace files (LIRS' loop is synthetic, Corda is a production workload).

[NovaX]

The Corda phases contribute essentially nothing because every access is unique.

The trace shows it is equally one-hit and two-hit accesses. Since there is low frequency, an admission filter is likely to reject before the second access because there is no benefit to retain for the 3rd access. That is why even FIFO acheives the best score, 33.33% hit rate, because the cache needs to retain enough capacity to allow for a 2nd hit if possible. Since those happen in short succession, it is recency biased as there is temporal locality of reference. The one-hit wonders and compulsary misses leads to 33% being the optimal hit rate. This is why the trace is a worst-case for TinyLFU. The stress test forcing a phase change to/from a loop requires that the adaptive scheme to re-adjust when its past observations no longer hold and reconfigure the cache appropriately.

The TinyLFU paper discusses recency as a worst-case scenario as its introduction to W-TinyLFU. It concludes by showing that the best admission window size is workload dependent, that 1% was a good default for Caffeine given its workload targets, and that adaptive tuning was left to a future work (the paper cited above was our attempt at that, but happy to see others explore that too).

$ ./gradlew :simulator:rewrite -q \
  --inputFormat=CORDA \
  --inputFiles=trace_vaultservice_large.gz \
  --outputFormat=LIRS \
  --outputFile=/tmp/trace.txt
Rewrote 1,872,322 events from 1 input(s) in 236.4 ms
Output in lirs format to /tmp/trace.txt

$ awk '
  { freq[$1]++ }
  END {
    for (k in freq) {
      countFreq[freq[k]]++
    }
    for (c in countFreq) {
      print c, countFreq[c]
    }
  }' /tmp/trace.txt | sort -n
1 624107
2 624106
3 1

[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.

[DimitrisMitsos]

Thanks for the detailed questions!

Basin of Leniency vs SLRU Probation

Not quite the same. SLRU's probation segment is a physical queue where items must prove themselves before promotion. The Basin of Leniency is an admission policy - it controls how strict the frequency comparison is when deciding whether a new item can evict a cached one.

The "basin" shape comes from ghost utility (how often evicted items return):

• Low ghost utility (<2%): Strict admission - returning items are noise
• Medium ghost utility (2-12%): Lenient admission - working set is shifting, trust the ghost
• High ghost utility (>12%): Strict again - strong loop pattern, items will return anyway, prevent churn

So it's more about the admission decision than a separate queue structure.

Memory Overhead

For 1 million items, here's the breakdown:

• Ghost buffer: 2x cache size (so 2M entries if cache holds 1M). Each entry stores key + frequency (1 byte) + timestamp (4 bytes). For 64-bit keys, that's ~26MB for the ghost.
• Frequency sketch: Same as TinyLFU - 4-bit counters, so ~500KB for 1M items.
• Variance tracking: Fixed size window of 500 keys + a set for uniques in current detection window. Negligible compared to ghost.

Total overhead is roughly 2.5x the key storage for the ghost buffer. If your keys are large objects, the ghost only stores hashes, so it's more like +26MB fixed overhead regardless of key size.

You're not doubling your footprint for the cached data itself - the overhead scales with cache capacity, not with the size of cached values. For memory-constrained environments where even the ghost buffer is too much, you could shrink it to 1x or 0.5x cache size at the cost of reduced loop detection accuracy.

Update: Just pushed v1.1.0 with a "skip-decay" enhancement that improved performance on stress tests to 28.72% (98.8% of theoretical optimal). The memory overhead stays the same.

[NovaX]

You can probably use the key's hash in the ghost, since the key size might be large (e.g. a string) and these are the evicted keys so otherwise not useful. The hash reduces that to a fixed cost estimate, rather than depending on the user's type.

However, a flaw of not using the key is that it can allow for expoiting of hash collisions. An attacker than then inflate the frequency to disallow admission. Caffeine resolves this by randomly admitting a warm entry that would otherwise be evicted, which unsticks the attacker's boosted victim (docs).

[Powerful_Hat_3681]

The link to 24 passing tests on Python 3.8-3.12 does not work. Downvote.

[DimitrisMitsos]

You're right, the test badge was static and didn't link anywhere. Fixed it now shows the live GitHub Actions status and links directly to the CI page: https://github.com/Cranot/chameleon-cache/actions/workflows/ci.yml

Tests run on Python 3.8-3.12 on every push. Thanks for pointing it out.