Eviction Policy for a Two-Layer Cache: LRU, LFU or Length

Each rule answers a different question.

The mechanics matter for implementation cost. LRU needs a hash map plus a doubly linked list, and every read mutates the ordering structure, so reads behave like writes and read-write locks buy nothing at high throughput (Redisson's LRU guide). LFU needs a counter per entry, and a naive scan for the minimum is O(n) and unusable at real sizes. The workable structure keeps frequency buckets in a linked list and gets LRU tie-breaking among equals for free (Redisson's LRU guide).

Plain LFU has a second defect: counters only go up. An entry that was hot last month keeps that count, and a genuinely popular newcomer starting at one may never catch it. Every practical LFU decays. Caffeine halves every counter at intervals so old popularity fades geometrically while relative order survives, and Redis uses a probabilistic 8-bit counter that loses a point per configurable decay interval (Redisson's LRU guide). Redis also uses recency as the tiebreaker when frequencies are equal (Redis's LFU vs LRU comparison).

Length is the odd one out. It does not model reuse at all. It models stored size, which matters because the provider bills stored prefix tokens by size. Length eviction is really a cost lever with a hit-rate side effect.

The operational rule of thumb from the cache literature: if access patterns shift continuously, choose LRU; if they are stable and heavily skewed, choose LFU; if you do not know which you have, start with LRU and measure the hit ratio before changing anything (Redisson's LRU guide). Redis states the same split: LFU for predictable or skewed workloads such as best sellers, LRU for dynamic workloads such as user sessions and dashboards (Redis's eviction policy guide).

For a prefix cache you can do better than the rule of thumb, because you have the log. Pull every request for a week and record three fields per request: the prefix key (a hash of the exact prefix bytes), the prefix token length, and a timestamp. From that you can compute the whole comparison offline.

The key diagnostic is the reuse distribution. Sort keys by request count and ask what fraction of all requests is served by the top N keys. If the top 5 percent of keys carry most requests, you have the skew LFU is built for. If the top 5 percent carries a modest share and keys keep rotating, you have the moving window LRU is built for.

The second diagnostic is size against reuse. Sum the token length of every key and compute, for each key, its length times its request count. That product is the value of keeping it. Sort by that product and compare to sorting by length alone. If the longest prefixes are near the bottom on the value product, Length eviction is discarding exactly the wrong things.

There is direct evidence that prompt position predicts reuse. An analysis of prefix cache reuse found that different token types in a prompt, including system prompts, user queries, tool outputs, model responses and chain-of-thought reasoning, show up to 756 times variation in reuse rates, which is why recency alone is an inadequate signal (the SAECache paper). If your log shows your longest prefixes are mostly one-shot tool output, Length will look attractive and LFU will look better.

The simulation is a replay. You feed the log in time order to each policy against a local tier of a fixed token budget, and count how many bytes would have been served from the local tier and what the provider would bill.

The loop is the same for all three policies. For each request: if the key is present, record a hit, update the metadata the policy needs, and record how many provider-cached tokens you avoided. If it is absent, record a miss, then insert the key and evict until the tier fits its budget again.

def simulate(log, capacity_tokens, choose_victim):
    resident = {}          # key -> tokens
    meta = {}              # key -> policy state
    hits = misses = cached_tokens = billed_write = 0
    for t, key, ntokens in log:
        if key in resident:
            hits += 1
            cached_tokens += ntokens
            choose_victim.touch(key, meta, t)
        else:
            misses += 1
            resident[key] = ntokens
            billed_write += ntokens
            choose_victim.insert(key, meta, t, ntokens)
            while sum(resident.values()) > capacity_tokens:
                victim = choose_victim.pick(meta, resident)
                del resident[victim]; del meta[victim]
    return hits, misses, cached_tokens, billed_write

Three policy objects slot into that loop. LRU's touch stamps the current time and pick returns the smallest stamp. LFU's touch increments a count and stamps the time, and pick returns the lowest count with the oldest stamp as tiebreak. Length's pick returns the largest tokokens value, which means you want an index sorted by length, not a scan.

Run each policy at three capacities that bracket your real budget, for example half, the actual budget, and double. The curve of hit tokens against capacity tells you whether your budget is the constraint or your policy is. If hit tokens are flat as capacity grows, the policy is dropping things it should keep. If they scale with capacity, you are simply short of room.

The worked example matters more than the code. Suppose your log has ten thousand requests over a week, the top fifty prefixes carry 60 percent of them and each is about eight thousand tokens, and the remaining nine thousand five hundred prefixes average twenty thousand tokens each and are read once. An LFU tier sized to hold the top fifty plus a little slack keeps the 60 percent resident and pays writes on it once. A Length tier evicting the longest entries first would evict those twenty-thousand-token one-shot prefixes, which is fine, but on a week where the top fifty included a long system prompt it would also evict the system prompt and pay its write premium every time it came back.

Watch billed stored tokens per successful request, not hit rate alone.

Hit rate tells you the local tier is doing its job. It does not tell you whether the provider is still charging you for prefixes that idle. A policy change can raise your local hit rate and raise your bill at the same time, for example if LFU keeps a large prefix resident locally while your application sends requests that do not reuse the provider's copy and let it expire. Infracost's glossary on cached token pricing is a useful reminder that the billed units are not the same as your application-level hits (Infracost's cached token glossary).

The arithmetic you want on the dashboard is: total provider input tokens billed, split into writes, hits and uncached input, divided by the number of requests that found their prefix in the local tier. If that number falls after a policy change while local hit rate holds or rises, the change is good. If it rises, revert.

There is a second reason to distrust hit rate as the headline. A published account of moving dynamic working memory out of the system prompt and into a user message at the end raised cache hit rate from 7 percent to 84 percent and cut overall LLM cost by 59 percent, with 9.8 billion tokens served from cache (the Digital Applied prompt caching playbook). Hit rate and cost moved together there because the workload was reordered to match the billing model. Your eviction policy should do the same thing: optimize the billed number, and let hit rate be the explanation rather than the target.

Measuring hits on keys you never sent again. A hit only counts if the request would otherwise have gone to the provider. If your simulation counts local reads that the application never actually sends to a model, you are measuring a database, not a cache.

Ignoring the provider's expiry. Anthropic's cache lifetime counts from the start of the request that writes or reads the entry, and time spent generating a response counts against the lifetime (the Claude docs). A prefix kept in your local tier but not re-read within the window is dead weight. Your simulation needs a TTL step: expire keys the provider would have expired, and record that as a write on the next request.

Assuming the provider stores everything you send. Providers keep a limited set. In serving engines, the prefix cache occupies scarce memory that can preserve only a fraction of all reusable key-value states; one published estimate is that serving a large model on four GPUs leaves room for roughly a modest number of cached prefix tokens relative to what you might send (the SAECache paper). Your local tier is the part you control, so the simulation should model the provider as lossy rather than as a perfect mirror.

Forgetting that the match is per block. Prefix caching implementations hash blocks and cache only full blocks (vLLM's prefix caching design). A prefix that ends mid-block gets less reuse than its token count suggests. Round your logged lengths down to the block boundary before you feed them to the simulation, or the numbers will be optimistic for short prefixes.

Treating Length as free. Length is cheap to compute and it does reduce stored bytes, which is why it is tempting. But it has no model of reuse, and the reuse-rate variation across token types in prompts means a length rule can systematically discard the section you rely on most (SAECache). Use it only if the log shows your longest entries are also your least reused.

Run this in order, and stop at the first rule that fires.

The last row is not a cop-out. LRU is the safe default when you cannot keep frequency counters accurate, and it adapts to change fast because a single read promotes an entry to the top (Redisson). LFU adapts slowly and needs decay to avoid fossilizing, but it has good scan resistance because a one-off scan never accumulates a meaningful count (Redisson). If your log is a weekly report generator walking every prefix once, LRU will be destroyed by that scan and LFU will shrug it off.

The deeper point from the cache literature is that the measurement is worth more than the policy (Redisson). A two-layer setup with a careful simulation and a lazy policy beats a hand-waved policy with no numbers.

If your access log spans several model families and you want to compare policy effects across them without wiring a separate SDK for each, one API key over text, image, video, audio and embedding models makes the experiment cheaper to run, and Quanta Inference is where that lives: https://quantaintelligence.ai/inference.