Research map / Large language models / Reasoning and chain of thought

Randomization Boosts KV Caching, Learning Balances Query Load: A Joint Perspective

ICLR 2026 · Large language models › Reasoning and chain of thought · approach: KV cache compression

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a unified model of KV cache-aware load balancing, a randomized leaf-token eviction (RLT) with O(log n) competitive ratio versus O(n) for SGLang's leaf-LRU, and a learning-based greedy router (LBGR) with online residual regression, evaluated on SGLang with Llama-3.1 and Mixtral.

Problem

LRU-style KV cache eviction in prefix-sharing caches is fragile under dynamic online query arrivals, and KV-cache-aware routing across multiple LLM workers trades cache hit rate against load balance; existing routing relies on static heuristics.

Approach

Model KV cache-aware load balancing as a makespan minimization with service time depending on cache state; show leaf-LRU has competitive ratio O(n); replace it with randomized marking-style leaf eviction (O(log n)); route greedily by an online-learned estimate of end-to-end latency that combines service-time estimates, decayed queue load, and a residual regression.

Key results

• On Llama-3.1-8B, LBGR+RLT achieves up to 11.96x lower median latency and 14.06x lower median TTFT than Cache-Aware+LRU, averaged over benchmarks.
• RLT alone gives a 6.92x higher cache hit rate and 77.4% higher throughput than L-LRU on a single worker under round-robin query arrivals on GSP.
• On Llama-3.1-70B-Instruct, LBGR+RLT reduces median latency 5.46x and TTFT 7.19x versus the best baseline.

Surprising findings

• Leaf-LRU's competitive ratio can degrade to O(n) in the worst case, and it worsens as query lengths become more imbalanced.
• Throughput gains of the proposed methods vanish once worker count is large enough (>=6) for all methods to saturate the fixed request rate.

Limitations

• Evaluation limited to text-only KV caches; no multimodal inference.
• Experiments limited to at most 10 workers in a single-domain setup, not geo-distributed deployments.
• Theoretical analysis assumes distinct queries within each batch and a simplified makespan/cost model.

Experimental setup

Datasets: Generated Shared Prefix (GSP) ShareGPT UltraChat Loogle

Benchmarks: GSP ShareGPT UltraChat Loogle

Metrics: P50 latency P95 latency P50 TTFT P95 TTFT cache hit rate throughput

Baselines: Random+LRU Round-Robin+LRU Cache-Aware+LRU

Builds on: SGLang RadixAttention marking algorithm vLLM

Closest papers by meaning

• KVzip: Query-Agnostic KV Cache Compression with Context Reconstruction (NeurIPS 2025 · similarity 0.91)
• Taming the Fragility of KV Cache Eviction in LLM Inference (ICLR 2026 · similarity 0.91)
• Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference (NeurIPS 2025 · similarity 0.90)
• CAKE: Cascading and Adaptive KV Cache Eviction with Layer Preferences (ICLR 2025 · similarity 0.90)
• ThinK: Thinner Key Cache by Query-Driven Pruning (ICLR 2025 · similarity 0.90)
• Get More with LESS: Synthesizing Recurrence with KV Cache Compression for Efficient LLM Inference (ICML 2024 · similarity 0.90)