Sparse Prefix Caching for Hybrid and Recurrent LLM Serving

Mikhail Shirokikh, Sergey Nikolenko · 2026

Read Sparse Prefix Caching for Hybrid and Recurrent LLM Serving by Mikhail Shirokikh, Sergey Nikolenko (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-05219.txt.

Introduction

Mikhail Shirokikh and Sergey Nikolenko redesign prefix caching, a latency saver in language model serving, for hybrid models with recurrent layers. A recurrent layer can resume from one stored state instead of a full token history, so caching every token's data is wasteful. Their sparse scheme stores exact recurrent states only at chosen checkpoint positions and recomputes the short remainder on a hit.

They formalise checkpoint placement under a distribution of overlap depths and solve it exactly with a dynamic program. On real datasets where requests share long prefixes, distribution-aware placement beat every fixed-budget baseline they measured. Gains were largest at small checkpoint budgets, where overlap patterns are most uneven.

Catalog record

CREATORMikhail Shirokikh, Sergey Nikolenko
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE36 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.05219

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sparse Prefix Caching for Hybrid and Recurrent LLM Serving Mikhail Shirokikh, Sergey Nikolenko Abstract 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 ⁡ ( N ​ M ) 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. 1 Introduction Prefix caching avoids redundant prefill computation when successive requests share a common prefix. In Transformer-centric serving systems, the reusable state consists of dense per-token key/value tensors, and modern runtimes exploit paging [ 14 ] , radix-tree sharing [ 38 ] , and distributed prompt scheduling [ 29 ] to make this practical at scale. Recent progress in state-space and linear recurrent models [ 11 , 7 , 26 , 33 ] has produced architectures whose recurrent layers maintain a fixed-size hidden state rather than per-token key/value pairs. Hybrid architectures that combine attention with recurrent or state-space layers [ 27 ] complicate this picture. Since a recurrent layer evolves its state as h_{t}=F(h_{t-1},x_{t}) , continuing from token t requires only h_{t} , not the entire history of intermediate states. Dense per-token caching of recurrent state is therefore both unnecessary and prohibitively expensive: for models such as Qwen-3.5, the recurrent (GatedDeltaNet) state per head scales as d_{\mathrm{head}}^{2} , whereas attention KV storage grows only linearly in d_{\mathrm{head}} per head. Hybrid and SSM serving do not have to choose between full dense caching and no caching at all; they can instead store the recurrent state at a sparse set of checkpoint positions and recompute the gap between the deepest stored checkpoint and the divergence point on demand. The resulting optimization problem is: given a memory budget of M checkpoint slots along a prefix of length N , where should checkpoints be placed to minimize expected recomputation under the overlap structure of future requests? This question is orthogonal to the cache-admission and eviction policies studied by Marconi [ 23 ] , which decide which entries to retain. We instead ask how to make partial prefix overlap useful for recurrent layers by selecting which tokens to checkpoint within every single entry. This is particularly beneficial when requests share long but not fully matching prefixes, e.g. when consecutive requests share a long system prompt, start with RAG-retrieved text, or ask different questions about the same document. For chat-like workloads, where each consecutive request within a conversation contains the previous one as a substring, the optimal strategy is obviously to store only the last state, so our method does not bring additional benefits (but also incurs no overhead). The problem is reminiscent of activation checkpointing in training [ 5 ] , where a subset of intermediate activations is stored during the forward pass and the rest are recomputed during backpropagation. The key difference is that activation checkpointing optimizes a single, known computation graph, whereas our setting involves stochastic overlap structure across requests, shared cache capacity, and online estimation of the overlap distribution. Our contributions. 1. We prove that balanced spacing is optimal under uniform overlap and in the worst case (Theorem 1 ). 2. We formalize sparse prefix caching as a one-sided weighted k -median problem with an exact O(NM) dynamic program (Theorem 2 ). 3. Furthermore, to enable using the empirical overlap depth distribution over previous requests instead of the true distribution over future overlaps, we show that the value function is Lipschitz in the overlap law (Lemma 1 ) and therefore its suboptimality can be bounded by total variation between the empirical and true distributions (Theorem 3 ). We also provide a similar bound for the case of drift in overlap depth distributions (Theorem 4 ). 4. We validate these results on real-world datasets (QuALITY, NarrativeQA, System Prompts) and show that our method saves more recomputations per checkpoint than every fixed-budget baseline we consider. On QuALITY and System Prompts, the DP-derived schedule yields prototype wall-clock speedups on a representative layer group, with the largest gains at low checkpoint budgets where the overlap distribution is most non-uniform. The rest of the paper is organized as follows. Section 2 reviews prior work on prefix caching, KV-cache compression, hybrid-model serving, and related checkpointing and facility-location formulations. Section 3 introduces the sparse prefix caching problem and its distributional formulation. Section 4 presents the main theoretical results, including optimal balanced placement under uniform overlap, the exact dynamic program, and plug-in guarantees under stationary and drifting overlap laws. Section 5 describes the experimental setup, datasets, baselines, and implementation constraints. Section 6 reports token-savings and prototype wall-clock results. Section 7 concludes, and the appendix contains additional proofs and supplementary figures. 2 Related Work Serving systems and dense prefix reuse. The PagedAttention mechanism in vLLM demonstrated that in practice, serving LLMs depends a lot on flexible KV-cache sharing and low-fragmentation memory management [ 14 ] . SGLang introduced RadixAttention for structured multi-call applications, allowing for automatic prefix sharing across programs [ 38 ] , while Preble studied distributed prompt scheduling that co-optimizes sharing and load balancing [ 29 ] . CacheBlend addressed exact reuse of non-contiguous cached chunks as needed in retrieval-augmented generation [ 34 ] . ChunkAttention proposed a two-phase partition scheme for prefix-aware decoding that further reduces redundant attention computation [ 35 ] . All of these systems assume dense token-indexed KV state; however; our setting is different because recurrent layers can be resumed from sparse exact checkpoints. KV cache compression and selection. A large body of work reduces the memory footprint of dense attention caches through eviction, quantization, or sparsification. Scissorhands identifies tokens that are “pivotal” for future attention and evicts the rest [ 17 ] . H 2 O retains only a heavy-hitter set of KV entries that accumulate the most attention mass [ 37 ] . PyramidKV and PyramidInfer exploit the observation that later layers need fewer cached tokens, and allocates budgets in a layer-adaptive pyramid shape [ 4 , 31 ] . SnapKV clusters attention

Read the complete text