Motivation.

Summary

We propose Tail-Optimized LRU (T-LRU), a lightweight modification to vLLM's existing LRU prefix-cache eviction policy that reduces P95 tail Time-to-First-Token (TTFT) by up to 27.4% on real conversation workloads, with no overhead during normal (cache-hit) operation and no change to API surface.

The idea and full analysis appear in our paper:

Tail-Optimized Caching for LLM Inference Wenxin Zhang, Ciamac C. Moallemi, Tianyi Peng Columbia Business School NeurIPS 2025. arXiv: https://arxiv.org/abs/2510.15152

Motivation

vLLM's current eviction policy is LRU. LRU maximizes cache-hit rate but is conversation-length blind: it treats a block from a 5-turn, 10 000-token conversation identically to a block from a 1-turn, 100-token conversation. This creates an avoidable source of tail latency.

Key Insight

For a conversation with history H blocks and estimated next-query length Q_hat blocks, evicting more than B = max(0, H + Q_hat - xi) blocks does not further increase the next turn's TTFT beyond the SLA threshold xi. Any block beyond this cap is TEL-safe (Tail Excess Latency safe) - it can be evicted without causing an SLO violation for that conversation.

Proposed Change.

Algorithm

T-LRU is a two-queue extension of LRU. When a request completes and its blocks are freed:

1. Compute B = max(0, H + Q_hat - xi) for the request.
2. 1. The last H - B blocks (suffix/tail) are TEL-safe -> append to tel_safe_queue.
3. 1. The first B blocks (prefix/head) are TEL-unsafe -> append to the existing LRU free queue as before. When new blocks are needed:
4. Drain tel_safe_queue first.
5. 1. Fall back to the normal LRU queue for any remaining demand. xi and Q_hat are tunable parameters exposed as CLI flags:

vllm serve <model> --enable-prefix-caching --tlru-xi-tokens 4096 --tlru-qhat-tokens 200

Implementation

All changes are confined to the v1 KV cache stack. No changes to the scheduler, attention kernels, or serving API.

• vllm/v1/core/kv_cache_utils.py: Added is_tel_safe: bool = False field to KVCacheBlock
• • vllm/v1/core/block_pool.py: Added tel_safe_queue, free_blocks_tlru(), modified get_new_blocks()
• • • vllm/v1/core/single_type_kv_cache_manager.py: free() routes to free_blocks_tlru() when T-LRU is enabled
• • • • vllm/v1/core/kv_cache_coordinator.py: Forwards params to BlockPool
• • • • • tests/v1/core/test_tlru_eviction.py: 15 unit tests

Experimental Results (WildChat dataset)

T-LRU reduces P95 TTFT by up to 27.4% vs LRU and closes 25-79% of the gap to the clairvoyant offline optimum. Results on ShareGPT are consistent.

Feedback Period.

At least one week.

CC List.

No response

Any Other Things.

Design Decisions & Open Questions

1. Default for Q_hat (tlru-qhat-tokens): We default to 200 tokens.
2. 1. tel_safe_queue vs FreeKVCacheBlockQueue pointer: The current separate-deque approach is simpler.
3. 1. Interaction with prefix caching: TEL-safe blocks are evicted before LRU pool blocks, which is intentional.

How to Try It

# Branch: feature/tlru-eviction-policy on github.com/wenxinzhang0/vllm
vllm serve meta-llama/Llama-3-8B \
  --enable-prefix-caching \
  --tlru-xi-tokens 4096 \
  --tlru-qhat-tokens 200

References

• Zhang, Moallemi, Peng. Tail-Optimized Caching for LLM Inference. NeurIPS 2025. https://arxiv.org/abs/2510.15152
• • Kwon et al. Efficient Memory Management for Large Language Model Serving with PagedAttention. SOSP 2023.
• • • vLLM Prefix Caching documentation: https://docs.vllm.ai/en/stable/design/prefix_caching/

Before submitting a new issue...

• Make sure you already searched for relevant issues, and asked the chatbot living at the bottom right corner of the documentation page, which can answer lots of frequently asked questions.