The LLM cache that reports 60% hits—and 1.6% useful reuse

A semantic cache tries to answer a new prompt with the response stored for an old, similar prompt. The appeal is obvious: one embedding lookup can replace a costly call to a large language model. But what exactly is a “hit”? If “How do I reset my password?” retrieves the answer to “How do I reset my router?”, the vector search worked and the product failed.

Kulkarni, Harkare, and Babu set out to compare cache-eviction policies across workloads, capacities, and text encoders. Their top-line systems result is deliberately boring: no tested policy improved on least-frequently used (LFU) by more than 0.041 percentage points over 18 settings. The much more consequential result arrives when a judge checks whether a cached answer could actually substitute for a fresh one. On QQP, LFU's 60.0% raw hit rate becomes just 1.6% quality-adjusted reuse.

The cache embeds each incoming query, finds its nearest resident vector, and calls the lookup a hit when squared distance is below a threshold. A quality-adjusted hit is stricter: an external judge must also say that the cached answer is valid for the new query. If H is the fraction of requests that hit and V is the fraction of those hits that are answer-substitutable, then

quality-adjusted hit rate = H × V.

This decomposition distinguishes retrieval from utility. H tests the embedding, threshold, and cache contents. V tests whether closeness preserves the facts and intent that determine the answer. A high H with low V can save almost no valid model calls—and may silently serve wrong answers if the system does not verify hits online.

def process(query, cache, hit_radius_sq):
    match, distance = nearest(cache, query.vector)
    if match is not None and distance <= hit_radius_sq:
        match.frequency += 1
        valid = match.answer_group == query.answer_group
        return True, valid
    if len(cache) == cache.capacity:
        cache.evict_lfu()
    cache.insert(query)
    return False, False

The from-scratch routine above mirrors the paper's exact lookup and insert-on-miss setup, while adding an answer-group label solely to audit validity. On a four-query hand check, two queries hit the radius, but one belongs to a different answer group: the displayed core computes 50% raw hits and 25% valid hits. Production systems do not know the answer group in advance; that is precisely why offline human or judge validation matters.

Increasing the hit radius makes the cache more willing to reuse. Raw hit rate therefore tends to rise, but valid hit rate rises only when the newly accepted neighbors share an answer. The next figure is a seed-free illustrative stream—not a reconstruction of the paper's proprietary or large public traces. It places several support intents close in a two-dimensional embedding so the accounting is visible.

A threshold is encoder-specific. The paper's most dramatic calibration warning is that a threshold tuned for MiniLM produced exactly 100% hits, zero misses, and zero evictions when applied to gte-base. Recalibrating by each encoder's distance distribution restored a meaningful comparison. The numeric threshold is not a portable unit of semantic meaning.

The paper's geometry-aware policy evicts entries with many neighbors inside a redundancy radius r. But a new entry is inserted only after no resident lies inside the hit radius h. At insertion time, its distance from every remaining resident is therefore greater than h. Whenever r ≤ h, the new entry has zero redundancy edges by construction.

That is a packing invariant, not an empirical coincidence. The admission rule continually builds a set of vectors separated by more than the hit radius, starving the semantic eviction score of local-density evidence. The policy then falls back toward frequency and recency signals that LFU or LRU already track more cheaply. This explains why “more semantic” did not imply better eviction in the tested architecture.

The limitation is specific: a cache that stores multiple candidates per neighborhood, admits hits, or maintains clusters outside the resident set could restore density signal. But then admission and lookup semantics have changed, so it is a new system rather than a fair swap of eviction policy.

Raw policy differences are single digits while the raw-to-useful collapse is tens of percentage points. SISO, the streaming semantic policy, trailed LFU by as much as 8.55 percentage points at tight capacity. In the full LMSYS runs, the graph-based semantic policy cost 5.83× to 8.24× LRU's overhead without improving hits. At 10% capacity, LRU, LFU, and the semantic policy recorded 0.7802, 0.7835, and 0.7808 hit rate respectively; at 20% and 30%, all three tied at 0.8453 and 0.8756.

Those decimals should not be read as universal rankings. The authors preserved dataset order after exact deduplication, prefilling a capacity-sized prefix and evaluating on a fixed final 70%. Random seeds changed policy sampling rather than the request trace. MOSS behaved very differently from LMSYS and QQP: it produced 97.6% raw hits and roughly 24.1–26.4% useful reuse, illustrating how workload repetition can dominate policy choice.

All main comparisons used exact nearest-neighbor search so the paper could isolate eviction. In a static HNSW check—HNSW is a graph index for approximate nearest neighbors—the loss in Recall@1 was 2.2 percentage points. That search error is vastly larger than the maximum 0.041 point advantage over LFU. A production benchmark that changes index settings between policies can easily measure retrieval approximation instead of eviction quality.

The study also used two compact English encoders, ordered public traces, CPU timing, and a response-free LLM judge from one 8-billion-parameter model family rather than human labels. Its verdict is strongest as a systems diagnosis: under this exact admission architecture, workload and router calibration swamp eviction cleverness. It is not a proof that every semantic cache should use LFU.

• Label answer substitutability on your own traffic before selecting a threshold.
• Plot raw and quality-adjusted hit rates together, with judge or human uncertainty.
• Calibrate thresholds separately for every embedding model and model version.
• Freeze the request trace and exact-search baseline when comparing eviction policies.
• Profile lookup overhead beside saved generation latency and wrong-answer cost.
• Test whether a different admission rule restores useful geometric redundancy.

The broader lesson applies anywhere a Transformer embedding becomes a routing gate: similarity is an intermediate measurement, not the business outcome. Validate the link from distance to safe action before optimizing what happens downstream.