Cache Hits Can Create Queues

TL;DR for operators

A multi-worker LLM service can make a request cheaper by sending it to a worker that already holds much of the required prefix in KV cache. The problem is that repeatedly favoring that worker can create a queue. Spreading traffic more evenly reduces congestion but may throw away the computational advantage of prefix reuse.

Wu and colleagues treat these as one online control problem rather than two independent optimizations.¹ Their system changes both sides of the decision: cache eviction becomes randomized to reduce pathological behavior under unfavorable request order, while routing predicts which worker should finish a request fastest after accounting for both cache hits and current queue load.

In one GSP component comparison, the Cache-Aware+LRU baseline records 26,680.55 ms P50 latency and a 23.89% cache hit rate. The combined method records 2,263.61 ms P50 latency and a 37.31% hit rate. The routing change contributes more than the eviction change by itself in this ablation, but the combined system performs best.

For operators of text-based services with substantial prefix sharing, the practical decision is therefore not “maximize cache hits” or “balance load.” It is how to price the value of a cache hit against the delay created by sending one more request to that worker.

Cache affinity and load balance can work against each other

KV reuse and load balancing are each desirable in isolation. Once multiple workers maintain different cache states, however, the two objectives become coupled.

Suppose one worker already stores most of a long shared prompt. Sending the next related request there avoids recomputing many input tokens. That lowers its service cost. But if several related requests arrive close together, the same cache advantage can repeatedly direct traffic toward one worker while others remain less loaded.

A conventional load-balancing policy can produce the opposite error. It can distribute requests more evenly while sending them to workers that lack the reusable prefix. The queues look healthier, but each request becomes more expensive to process.

The paper formalizes this interaction by making a worker’s cost depend on how many input tokens already hit its cache and then optimizing query assignments against accumulated worker load. This framing matters because eviction changes future routing economics: deleting a prefix today changes which worker becomes attractive for later requests.

Recency-based eviction has an unfavorable worst case

The eviction result addresses a separate failure mode inside the same system.

Leaf-LRU uses recency to decide which eligible leaves of a radix-tree prefix cache to evict. That is intuitive when recent use predicts future reuse. Under an unfavorable online request sequence, however, a deterministic recency rule can repeatedly discard tokens that will soon be needed again.

The relevant theoretical measure is the competitive ratio: how much worse an online eviction rule can perform than an optimal strategy that already knows the future sequence.

Under the paper’s single-query model, Leaf-LRU’s competitive ratio is bounded by

so its worst-case performance grows linearly with effective cache capacity.

The proposed Randomized Leaf Token eviction, or RLT, changes the eviction decision. Accessed tokens are marked, and when space is required, the algorithm randomly chooses among eligible unmarked leaf tokens. Under the same formal setting, its competitive ratio becomes

The paper derives an analogous logarithmic result for continuous batching and gives matching randomized lower bounds under its model.

This is a robustness claim, not a universal production speedup ratio. The theory says that randomized eviction is less exposed to adversarial ordering under the specified radix-tree cache assumptions.

Routing becomes a latency prediction problem

Changing eviction does not solve the congestion problem. The second component, Learning-Based Greedy Routing, estimates the end-to-end latency of placing each incoming request on each worker.

Its estimator has three parts:

The first term estimates service time from expected cache hits and misses. The second represents current queue load. The third is an online regression correction for latency effects not captured by those explicit quantities.

Queue load is also decayed over time instead of being treated as permanently accumulated history. An appendix ablation shows that increasing the decay interval worsens performance because the congestion estimate becomes stale. That test is best read as mechanism validation: it supports the need for a current load estimate, not as a separate headline result.

LBGR then greedily sends the request to the worker with the lowest predicted end-to-end latency.

The distinction is worth making explicit: the paper does not propose random routing. Randomization is used inside RLT’s eviction decision. Routing remains directed and greedy, based on learned latency estimates.

The ablation shows where the gains come from

The GSP comparison separates the two algorithmic changes.

RLT helps while routing is held fixed. LBGR produces a larger change while LRU is held fixed. Combining them improves the reported metrics further.

A separate single-worker worst-case GSP test isolates eviction more aggressively. There, RLT raises cache hit rate from 6.06% to 41.93%, while normalized throughput increases from 0.62 to 1.0. This is an ablation designed to expose unfavorable query ordering, not an estimate of the improvement an average production workload should expect.

Across GSP, ShareGPT, UltraChat, and Loogle on Llama-3.1-8B-Instruct, the paper reports an average 11.96× improvement in median latency and 14.06× in median TTFT over Cache-Aware+LRU. It also reports advantages across larger dense Llama models, Mixtral, different cache budgets, request rates, worker counts, prefix-sharing ratios, output lengths, and concurrency settings. Those variations function primarily as robustness tests for the main serving result.

The operational metric should be predicted completion time

For an inference-platform operator, the paper changes the unit of optimization.

Cache hit rate alone is incomplete because the worker with the best cache may have the longest queue. Queue length alone is incomplete because two workers with similar congestion can face very different computation costs for the same request.

Cognaptus therefore reads the operational implication as jointly estimating request placement cost. The affected user is an operator of a multi-worker LLM serving platform; the decision is where to route each request and what cache state to retain; the relevant condition is traffic with meaningful prefix reuse and changing congestion.

The reported control overhead is roughly 2 ms per query in the GSP ablation when routing and eviction overhead are combined. Relative to the multi-second end-to-end latencies in that experiment, this suggests that richer online control can be inexpensive enough to test in real serving stacks.

It does not establish that the same controller will dominate under every latency regime or architecture. Operators would still need to validate estimator accuracy, cache synchronization cost, and workload-specific prefix reuse in their own deployment.

The deployment boundary is narrower than the algorithmic idea

The empirical coverage is substantial within its target setting: several workloads, dense and sparse models, varying load conditions, multiple cache sizes, and up to ten workers.

Three boundaries remain material.

First, the experiments are text-only. Multimodal serving can introduce different cache structures, memory pressure, and scheduling constraints. Second, the worker fleet never exceeds ten, so the coordination behavior of substantially larger clusters remains untested. Third, the experiments use a single-domain deployment rather than geographically distributed serving, where network latency and cache replication could alter the routing trade-off.

The strongest transferable claim is consequently architectural: when cache state changes request cost, routing and eviction should be evaluated as coupled controls. The magnitude of the reported gains belongs to the tested SGLang-based environment and workloads.

Coordinate the cache with the queue

The paper’s most useful contribution is not a new reason to pursue a higher cache-hit percentage. It shows why that percentage cannot be interpreted independently of congestion.

Randomized eviction addresses sensitivity to unfavorable request order. Learned routing values the computational benefit of locality against a continuously changing estimate of worker load. The experiments indicate that each mechanism contributes and that coordinating them performs best in the evaluated system.

For prefix-sharing LLM services, that moves the serving decision from two separate heuristics toward one measurable objective: which cache and routing action is expected to get the request finished sooner.

Cognaptus: Automate the Present, Incubate the Future.