Research map / Large language models / Reasoning and chain of thought
Tail-Optimized Caching for LLM Inference
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 Tail-Optimized LRU (T-LRU), an LRU variant that first evicts KV-cache blocks beyond a TEL-safe budget, and proves hindsight and stochastic-model optimality for a tail-excess-latency objective, evaluated on WildChat and ShareGPT with Vicuna-7B on vLLM.
Problem
LRU prompt-cache eviction ignores conversation heterogeneity and can be arbitrarily poor for tail TTFT latency in multi-turn LLM serving.
Approach
Trim each conversation's cache down to a TEL-safe budget (history plus expected next prompt minus a latency threshold in blocks) before applying LRU eviction, which is hindsight-optimal when combined with Belady and optimal online under a birth-death conversation model.
Key results
- T-LRU reduces P90 tail TTFT by up to 27.5% and P95 by up to 23.9% versus LRU on WildChat (C=10,000, xi_s=150 ms and 200 ms respectively).
- T-LRU reduces SLO violations (requests with TTFT > 200 ms) by up to 40.7% versus LRU and 38.9% versus Threshold-LRU on WildChat at capacity 10,000.
- On ShareGPT with synthetic timestamps, improvements are smaller: up to 10% at P90 and 7% at P95.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use T-LRU instead of LRU | Vicuna-7B prompt caching · WildChat, capacity 10000, ξs=150ms | P90 latency: 27.5% | Helped |
| Use T-LRU instead of LRU | Vicuna-7B prompt caching · WildChat, capacity 10000, ξs=200ms | P95 latency: 23.9% | Helped |
| Use T-LRU instead of Threshold-LRU | Vicuna-7B prompt caching · WildChat, capacity 10000, ξs=200ms | P95 latency: 22.8% | Helped |
| Use T-LRU instead of LRU | Vicuna-7B prompt caching · WildChat, capacity 10000, ξs=200ms SLO | requests exceeding 200ms: 40.7% | Helped |
| Use T-LRU instead of LRU | Vicuna-7B prompt caching · ShareGPT, capacity 6000, ξs=500ms | P90 latency: 10.0% | Helped |
| Use T-LRU instead of LRU | Vicuna-7B prompt caching · WildChat, capacity 10000, ξs=500ms | P90 latency: -13.3% | Hurt |
| Raise ξs to 500ms instead of calibrating it to the target tail (ablation) | T-LRU · WildChat, capacity 10000 | requests exceeding 200ms: -19.3% | Hurt |
| Set ξs to 200ms instead of 500ms (ablation) | T-LRU · WildChat, capacity 10000 | P95 latency reduction vs LRU: 23.9% vs -3.5% | Helped |
| Add knowledge of whether conversations will continue (ablation) | T-LRU · WildChat | tail latency | Helped |
| Add exact next-prompt length knowledge to End-Aware T-LRU (ablation) | End-Aware T-LRU · WildChat | tail latency | Helped |
| Trade lower median latency for tail-focused T-LRU caching | T-LRU vs LRU · WildChat | median latency: 10ms to 40ms | Hurt |
Surprising findings
- Median latency rises slightly under T-LRU (e.g., from about 10 ms to 40 ms in one setting), a deliberate tail-for-median tradeoff.
- Setting the threshold too high (xi_s=500 ms) makes T-LRU worse than LRU at P95 and P99 in several configurations.
Limitations
- Theoretical optimality holds under a stochastic birth-death conversation model with assumptions such as no cross-conversation cache reuse and exponential session lifetimes.
- Assumes TTFT is linear in uncached blocks and evaluates on a single storage tier with a single GPU and Vicuna-7B only.
- ShareGPT timestamps are synthetically generated, and gains there are smaller.
Experimental setup
Datasets: WildChat ShareGPT
Benchmarks: WildChat ShareGPT
Metrics: P90 TTFT P95 TTFT P99 TTFT median TTFT SLO violation rate (TTFT > 200 ms)
Baselines: LRU Threshold-LRU
Builds on: LRU Belady's algorithm vLLM prefix caching
Closest papers by meaning
- QUEST: Query-Aware Sparsity for Efficient Long-Context LLM Inference (ICML 2024 · similarity 0.89)
- Taming the Fragility of KV Cache Eviction in LLM Inference (ICLR 2026 · similarity 0.89)
- SCBench: A KV Cache-Centric Analysis of Long-Context Methods (ICLR 2025 · similarity 0.89)
- Randomization Boosts KV Caching, Learning Balances Query Load: A Joint Perspective (ICLR 2026 · similarity 0.89)
- ChunkKV: Semantic-Preserving KV Cache Compression for Efficient Long-Context LLM Inference (NeurIPS 2025 · similarity 0.88)
- CaM: Cache Merging for Memory-efficient LLMs Inference (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.