Andrew Ng dropped a number this week: 90% of Agent projects get stuck on deployment—not for technical reasons. We buy half of that, but what's really tripping teams up is often the "old-school" infrastructure details, like LRU cache.
What This Is
LRU (Least Recently Used) is an eviction policy: when capacity fills up, discard the data least recently accessed. It's powered by two cooperating data structures: a hash table handles "find the node by key," while a doubly linked list handles "arrange nodes by access order." Together, they make lookup, insertion, and eviction all O(1) (constant time—fixed cost regardless of data volume). A LeetCode #146 solution recently went viral on Juejin, explaining this clearly.
But here's what matters: this 1960s algorithm now underpins AI inference infrastructure. The LLM KV Cache (storing computed attention results for reuse, avoiding recomputation), vector database query caches, RAG (Retrieval-Augmented Generation) system retrieval caches, and Agent short-term conversation memory all run on LRU or its variants.
Industry View
Classic LRU hits two new problems in the AI era. First, "long context" pressure: models now routinely support 128K, 200K, even million-token contexts (token = the model's minimum text unit), and time-based eviction doesn't guarantee keeping the most useful content. Second, "cost structure" has changed: traditional LRU assumes all nodes are equal size, but AI cache entries vary wildly—a vector is a few KB, a conversation history is several MB. Pure count-based eviction wastes GPU memory.
So big model companies have been "reinventing the wheel" in recent years: Anthropic's Prompt Caching prices based on prefix hit rate; vLLM and DeepSeek's Paged Attention (slicing KV Cache into small OS-style pages to manage) solves memory fragmentation; Meta's StreamingLLM uses an attention-sink strategy, letting models "forget the middle, remember the start and end." None of these are LRU, but they're all extensions of—or rebellions against—LRU thinking.
A word of caution: the more complex the caching strategy, the more engineering landmines. Paged Attention still has memory leak issues in some inference frameworks; over-reliance on prefix caching makes cold-start user experience worse. This is an engineering battle with no standard answer.
Impact on Regular People
For enterprise IT: When procuring AI inference services, "cache hit rate" matters more than comparing token unit prices. For the same vendor and same model, a 10-percentage-point hit-rate gap can roughly double your bill.
For individual careers: When using AI tools, building habits of "fixed openings, fixed terminology" actively helps the system improve cache hit rates—and you'll see response times noticeably faster.
For the consumer market: The "speed" of future AI applications will increasingly depend on underlying cache strategies, not raw compute. This means the same GPU can deliver wildly different product experiences depending on the company behind it.