Why LRU Is Still a Tough Baseline for AI Agent Caching

Key takeaways

• KV caches store attention keys and values computed while processing earlier tokens.
• Prefix caching reuses that data when requests share an identical beginning.
• LRU can work well when agents return to recently used context.
• Cache policies need evaluation on memory use, reused tokens, latency, and management overhead.

A coding agent reads a file, edits code, runs tests, and takes another pass. Each model call can carry much of the same context, making repeated computation an obvious place to save time. Deciding what to keep in memory brings us back to an old systems question—and an old answer: LRU, or Least Recently Used.

Reuse the context, skip some work

As a language model processes tokens, it computes keys and values used in attention. A KV cache stores those intermediate results.

Prefix caching allows that data to be reused across requests with the same beginning. If the instructions and conversation history match, the model can reuse the cached keys and values for that portion.

Suppose a request appends 1,000 new tokens to 8,000 tokens of previously processed context. If the earlier cache is still available and eligible for reuse, the model can avoid recomputing the keys and values for those 8,000 tokens.

That does not make the whole request nine times faster. The model still has to process the new input and generate its answer. New tokens still need to attend to earlier context.

The match also needs to be exact. Similar meaning does not make two prefixes interchangeable. Put a changing timestamp near the start of every request, or rearrange the documents, and reuse can break from that point onward.

Before shopping for a better eviction policy, check whether your application actually preserves the repeated prefix. An inconsistent prompt layout can undermine an otherwise useful cache.

LRU works when the agent comes back soon

Memory fills up. An eviction policy decides what leaves.

LRU removes the entry that has gone unused for the longest time. Its working assumption is straightforward: something used recently may be needed again soon. When that holds, the workload has temporal locality.

A coding agent working through one task can fit this pattern well. It reads repository context, makes a change, receives test output, and makes another change. Much of the previous request may remain at the beginning of the next one.

Keeping recently used context can therefore be an effective strategy without elaborate prediction. The agent keeps returning to the same working material.

But “agent workload” is not a guarantee of temporal locality. A tool might take a long time to finish. Meanwhile, requests from other sessions arrive and push the waiting agent’s context out of memory.

What matters is the order in which requests reach the cache. An agent returning after a quiet pause and one returning after a flood of competing requests face very different conditions.

A smarter policy has to pay for itself

A cache policy can consider more than recency. It might track access frequency, estimate the cost of recomputing an entry, or use a model to predict future reuse.

Each extra signal brings overhead. Statistics need updating. Candidates need comparing. A prediction model needs to run.

The useful gain is the computation saved after accounting for the cost of making those decisions. A policy that selects better entries can still fail to reduce response time.

LRU has weaknesses, too. A succession of long inputs used only once can displace context that will be needed again. Recency alone does not reveal how valuable an entry will be to reuse.

That value varies. Reusing a long prefix shared by many requests offers different savings from repeatedly reusing short, separate prefixes. A policy that wins on one pattern may lose on another.

Claims of improvement need that workload context. “Better than LRU” means little without knowing what arrived, what fit in memory, and what the policy cost to run.

Benchmark the workload your server actually sees

Replaying real agent traces can preserve useful details about request lengths and repetition. It does not automatically reproduce a live service.

Four checks make the comparison more informative:

• Match the memory budget. An equal number of cached requests does not imply equal memory use when their lengths differ. Include the memory needed for policy metadata.
• Preserve request interleaving and timing. Finishing one session before starting another can favor reuse. Concurrent sessions compete for space, and tool delays affect when requests return.
• Measure reused tokens alongside hit counts. Reusing a short opening and reusing most of a long context should not look equally valuable in the results.
• Measure user waiting time. Time to first token and total task completion time answer different questions. Check slow requests as well as averages.

A trace simulation that counts cache hits can help compare eviction behavior. Demonstrating a speed improvement requires measuring the policy’s overhead on an inference server as well.

LRU deserves a serious baseline because its simple rule can fit repeated agent work remarkably well. A replacement earns its place by shortening users’ waits under comparable memory and request conditions. A better prediction is only useful if it buys a shorter wait.