Technical Summary: SAECache – Semantic-Aware Eviction for LLM Prefix Caches

Problem Statement

Prefix caching in Large Language Models (LLMs) aims to reduce inference latency (specifically Time-to-First-Token, or TTFT) by reusing Key-Value (KV) states from requests that share input prefixes. However, the efficacy of prefix caching is severely constrained by limited GPU memory, necessitating an eviction policy to discard less valuable blocks when capacity is reached.

Existing eviction policies, such as Least Recently Used (LRU) and Least Frequently Used (LFU), rely primarily on access time or frequency statistics. These token-agnostic approaches treat all cached blocks uniformly, ignoring two critical dimensions of LLM workloads:

1. Semantic Heterogeneity: Different token types (e.g., system prompts vs. chain-of-thought reasoning) exhibit vastly different intrinsic reuse rates.
2. Workload Variability: Reuse patterns differ significantly between single-turn templated requests (structural reuse) and multi-turn conversations (session-local temporal reuse), with inter-turn intervals following distinct distributions across different application types (e.g., chat vs. agentic workflows).

The authors observe that treating a high-value system prompt block and a low-value chain-of-thought block as equivalent when their recency matches leads to suboptimal memory allocation. Furthermore, fixed-parameter policies fail when workload compositions shift, causing performance degradation of up to 2.7× under workload mismatch.

Methodology: SAECache

To address these limitations, the authors propose SAECache (Semantic-Adaptive Eviction for prefix caches), a policy that integrates token-semantic structure with online workload adaptation. The system operates through three core mechanisms:

1. Multi-Queue Architecture with Rule-Based Routing

SAECache routes KV blocks into four distinct queues based on their dominant reuse patterns, rather than a single global queue:

• Evict-First Queue: Stores low-value blocks, including decode-phase tokens and untemplated prefill blocks with low reuse potential. These are drained first.
• Structural Queue: Stores KV blocks from single-turn sessions that rely on shared prompt structures (e.g., tool-use templates, programming instructions).
• Chat Queue: Stores multi-turn blocks from conversational sessions, modeling session-local temporal reuse.
• Agentic Queue: Stores multi-turn blocks from agent/tool-use sessions, which exhibit different token content and request interval distributions compared to standard chat.

A lightweight multi-turn session predictor (a 3-layer MLP reusing the serving model's final hidden states) resolves ambiguity for the first request of a session, routing it to the appropriate multi-turn queue if continuation is predicted, or to the structural/evict-first queues otherwise.

2. Local Priority Scoring

Within each queue, blocks are scored for eviction based on a composite metric $P(b)$:
$$P(b) = \alpha_q \cdot w_{\tau(b)} \cdot \frac{p_q(b)}{\Delta t_b}$$

• $\alpha_q$ (Queue Weight): A dynamic weight reflecting the recent hit efficiency of the specific queue.
• $w_{\tau(b)}$ (Token-Type Weight): A learned weight specific to the token type (e.g., system prompt, user query, chain-of-thought) of the block.
• $p_q(b)$ (Local Survival Probability):
  • For Chat/Agentic queues: Calculated as the survival probability $1 - F_{LN}(\Delta t_b; \mu_q, \sigma_q)$ under a log-normal distribution fitted to the inter-turn intervals of that session type.
  • For the Structural queue: Calculated as $1 - (o_b / o_{max})^\gamma$, where $o_b$ is the block offset and $\gamma$ is a learned decay power, prioritizing earlier blocks in a prompt.
• $\Delta t_b$: The elapsed time since the block's last access.

3. Fully Adaptive Online Learning

SAECache eliminates manual tuning by updating all parameters online via a unified feedback loop based on cache hit/miss statistics:

• Token-Type Weights: Updated via Exponential Moving Average (EMA) based on "miss-after-eviction" rates and overall hit rates.
• Log-Normal Parameters ($\mu, \sigma$): Estimated online using Maximum Likelihood Estimation (MLE) on observed inter-access times for chat and agentic queues.
• Position Decay Power ($\gamma$): Learned from correlations between block position and hit rates in the structural queue.
• Queue Weights ($\alpha_q$): Updated based on the ratio of hit tokens to allocated capacity for each queue, scaled by a temperature parameter.

Key Contributions

1. Empirical Characterization: A systematic study revealing that token reuse varies by up to 756× across token types (92.3% for system prompts vs. 2.2% for chain-of-thought) and that inter-turn intervals follow session-specific log-normal distributions rather than simple exponential decays.
2. SAECache Policy: A semantic-aware, multi-queue eviction policy that decouples heterogeneous reuse mechanisms (structural vs. temporal) and assigns distinct priorities to token types.
3. Online Adaptation: A learning framework that automatically tunes timing distributions, position decay, and weighting parameters without manual intervention, adapting to shifting workload compositions.
4. Comprehensive Evaluation: Extensive experiments on real-world datasets (ShareGPT, LMSys, Chatbot-Arena) demonstrating robustness across heterogeneous workloads.

Experimental Results

Evaluated on a vLLM implementation with Qwen2.5-1.5B-Instruct on an NVIDIA A40 GPU, SAECache was compared against LRU (production baseline) and Learned Prefix Caching (LPC).

• TTFT Improvement: SAECache achieved a 1.4× to 2.7× improvement in TTFT over production-style baselines across heterogeneous workloads.
• Cache Hit Ratio: SAECache consistently achieved the highest cache hit rates, improving by 4.8–5.9 percentage points over the strongest baseline (LRU or LPC) across all tested configurations.
• Workload Mismatch Resilience: Fixed-parameter alternatives suffered up to a 2.7× degradation in TTFT when the workload composition deviated from the training trace. SAECache maintained stable performance by adapting its parameters online.
• Ablation Studies:
  • Token-type-aware weighting contributed an additional 23% improvement.
  • Adaptive queue weighting contributed the largest gain at 39%.
  • Log-normal timing and position-decay learning provided additional gains of 14% and 12%, respectively.
• Overhead: The multi-turn session predictor is highly efficient, requiring only ~1M parameters (vs. 118M for LPC's embedding model) and achieving 8.8× higher inference throughput.

Significance and Claims

The paper claims that prefix cache eviction should not treat all cached blocks uniformly, even when they share similar recency or frequency statistics. The authors assert that token semantics, prompt structure, and session type are fundamental drivers of reuse that existing policies fail to capture.

The significance of SAECache lies in its ability to:

1. Bridge the gap between static heuristic policies and the dynamic, semantic reality of LLM serving.
2. Eliminate manual tuning, making the system robust to workload shifts (e.g., from chat-heavy to tool-use-heavy traffic) without retraining or parameter adjustment.
3. Demonstrate that fine-grained, semantic-aware eviction is a critical design choice for efficient LLM serving, particularly in environments with high cache pressure and heterogeneous request patterns.

The authors note that while SAECache excels in multi-turn and mixed workloads, its overhead can slightly reduce performance in single-turn-dominated regimes (e.g., Chatbot-Arena) where the benefits of higher hit rates do not fully offset the management costs, highlighting the necessity of adaptive strategies that can scale with workload characteristics.