# Sparse Prefix Caching for Hybrid and Recurrent LLM Serving

arXiv: https://arxiv.org/abs/2605.05219 · HTML: https://mlsanity.com/paper/2605.05219/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving.
- Builds on 22 of its 41 references that are in the map.
- First posted on arXiv 17 Apr 2026.

## Placed in

- Efficient LLM inference and serving / [KV cache optimization](https://mlsanity.com/inference/kv-cache-optimization/)

## Builds on (most cited first, 22 of 22)

- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality](https://mlsanity.com/paper/2405.21060/) (2024)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [SnapKV: LLM Knows What You are Looking for Before Generation](https://mlsanity.com/paper/2404.14469/) (2024)
- [Training Deep Nets with Sublinear Memory Cost](https://mlsanity.com/paper/1604.06174/) (2016)
- [RWKV: Reinventing RNNs for the Transformer Era](https://mlsanity.com/paper/2305.13048/) (2023)
- [The NarrativeQA Reading Comprehension Challenge](https://mlsanity.com/paper/1712.07040/) (2017)
- [Splitwise: Efficient generative LLM inference using phase splitting](https://mlsanity.com/paper/2311.18677/) (2023)
- [Gated Linear Attention Transformers with Hardware-Efficient Training](https://mlsanity.com/paper/2312.06635/) (2023)
- [Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Time](https://mlsanity.com/paper/2305.17118/) (2023)
- [PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling](https://mlsanity.com/paper/2406.02069/) (2024)
- [CacheBlend: Fast Large Language Model Serving for RAG with Cached Knowledge Fusion](https://mlsanity.com/paper/2405.16444/) (2024)
- [QuALITY: Question Answering with Long Input Texts, Yes!](https://mlsanity.com/paper/2112.08608/) (2021)
- [PyramidInfer: Pyramid KV Cache Compression for High-throughput LLM Inference](https://mlsanity.com/paper/2405.12532/) (2024)
- [Dynamic Memory Compression: Retrofitting LLMs for Accelerated Inference](https://mlsanity.com/paper/2403.09636/) (2024)
- [ChunkAttention: Efficient Self-Attention with Prefix-Aware KV Cache and Two-Phase Partition](https://mlsanity.com/paper/2402.15220/) (2024)
- [Preble: Efficient Distributed Prompt Scheduling for LLM Serving](https://mlsanity.com/paper/2407.00023/) (2024)
- [Challenges in Deploying Long-Context Transformers: A Theoretical Peak Performance Analysis](https://mlsanity.com/paper/2405.08944/) (2024)
- [Marconi: Prefix Caching for the Era of Hybrid LLMs](https://mlsanity.com/paper/2411.19379/) (2024)
- [Nonparametric Density Estimation under Distribution Drift](https://mlsanity.com/paper/2302.02460/) (2023)

## Built on by (most cited first, 4 of 4)

- [LinearKV: One Cached State Suffices for Position-Independent Caching in Hybrid LLMs](https://mlsanity.com/paper/2608.11231/) (2026)
- [Tail-Replay: Escaping the Curse of Linear Attention in Prefix Caching for Hybrid LLMs](https://mlsanity.com/paper/2608.30310/) (2026)
- [Validating Hybrid-State Cache Recovery for GLM-5.3-Flash with vLLM and LMCache](https://mlsanity.com/paper/2609.15030/) (2026)
- [Just Let Linear States Forget the Distant Past: Prefix Caching via Suffix Replay for Hybrid LLMs](https://mlsanity.com/paper/2609.33477/) (2026)

## Abstract (arXiv)

Prefix caching is a key latency optimization for autoregressive LLM serving, yet existing systems assume dense per-token key/value reuse. State-space models change the structure of the problem: a recurrent layer can resume from a single stored state rather than requiring the entire token history. This asymmetry opens a new design point between no reuse and dense caching: store exact recurrent states at a sparse set of checkpoint positions and, on a cache hit, resume from the deepest stored checkpoint and recompute the remaining suffix exactly. We formalize sparse prefix caching as checkpoint placement under a distribution over overlap depths, yielding an exact O(NM) dynamic program. For use cases where requests share a non-trivial prefix (e.g. asking different questions about a single long document), we show that our method consistently improves the Pareto frontier traced by standard heuristics on real-world data. Across QuALITY and System Prompts, distribution-aware placement dominates every fixed-budget baseline on the measured layer-group Pareto frontier and matches or outperforms the strongest heuristic (block caching) while typically using substantially fewer checkpoints, with the largest gains at low checkpoint budgets where the overlap distribution is most non-uniform. The method is most relevant when many requests share a substantial but not identical prefix within a retained cache entry. It preserves exact outputs, does not change the recurrent computation itself or require new recurrent update kernels, applies to recurrent/SSM layers whose hidden state can be extracted and restored exactly, and for hybrid models can be combined with existing KV-cache compression techniques.