Sparse Prefix Caching for Hybrid and Recurrent LLM Serving

# Sparse Prefix Caching for Hybrid and Recurrent LLM Serving
Source: [https://arxiv.org/html/2605.05219](https://arxiv.org/html/2605.05219)
###### 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 exactO​\(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\.

## 1Introduction

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](https://arxiv.org/html/2605.05219#bib.bib4)\], radix\-tree sharing\[[38](https://arxiv.org/html/2605.05219#bib.bib5)\], and distributed prompt scheduling\[[29](https://arxiv.org/html/2605.05219#bib.bib6)\]to make this practical at scale\.

Recent progress in state\-space and linear recurrent models\[[11](https://arxiv.org/html/2605.05219#bib.bib1),[7](https://arxiv.org/html/2605.05219#bib.bib2),[26](https://arxiv.org/html/2605.05219#bib.bib12),[33](https://arxiv.org/html/2605.05219#bib.bib10)\]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](https://arxiv.org/html/2605.05219#bib.bib11)\]complicate this picture\. Since a recurrent layer evolves its state asht=F​\(ht−1,xt\)h\_\{t\}=F\(h\_\{t\-1\},x\_\{t\}\), continuing from tokenttrequires onlyhth\_\{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 asdhead2d\_\{\\mathrm\{head\}\}^\{2\}, whereas attention KV storage grows only linearly indheadd\_\{\\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 ofMMcheckpoint slots along a prefix of lengthNN, 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](https://arxiv.org/html/2605.05219#bib.bib8)\], 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](https://arxiv.org/html/2605.05219#bib.bib42)\], 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. 1\.We prove that balanced spacing is optimal under uniform overlap and in the worst case \(Theorem[1](https://arxiv.org/html/2605.05219#Thmtheorem1)\)\.
2. 2\.We formalize sparse prefix caching as a one\-sided weightedkk\-median problem with an exactO​\(N​M\)O\(NM\)dynamic program \(Theorem[2](https://arxiv.org/html/2605.05219#Thmtheorem2)\)\.
3. 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](https://arxiv.org/html/2605.05219#Thmlemma1)\) and therefore its suboptimality can be bounded by total variation between the empirical and true distributions \(Theorem[3](https://arxiv.org/html/2605.05219#Thmtheorem3)\)\. We also provide a similar bound for the case of drift in overlap depth distributions \(Theorem[4](https://arxiv.org/html/2605.05219#Thmtheorem4)\)\.
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](https://arxiv.org/html/2605.05219#S2)reviews prior work on prefix caching, KV\-cache compression, hybrid\-model serving, and related checkpointing and facility\-location formulations\. Section[3](https://arxiv.org/html/2605.05219#S3)introduces the sparse prefix caching problem and its distributional formulation\. Section[4](https://arxiv.org/html/2605.05219#S4)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](https://arxiv.org/html/2605.05219#S5)describes the experimental setup, datasets, baselines, and implementation constraints\. Section[6](https://arxiv.org/html/2605.05219#S6)reports token\-savings and prototype wall\-clock results\. Section[7](https://arxiv.org/html/2605.05219#S7)concludes, and the appendix contains additional proofs and supplementary figures\.

## 2Related 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](https://arxiv.org/html/2605.05219#bib.bib4)\]\. SGLang introduced RadixAttention for structured multi\-call applications, allowing for automatic prefix sharing across programs\[[38](https://arxiv.org/html/2605.05219#bib.bib5)\], while Preble studied distributed prompt scheduling that co\-optimizes sharing and load balancing\[[29](https://arxiv.org/html/2605.05219#bib.bib6)\]\. CacheBlend addressed exact reuse of non\-contiguous cached chunks as needed in retrieval\-augmented generation\[[34](https://arxiv.org/html/2605.05219#bib.bib7)\]\. ChunkAttention proposed a two\-phase partition scheme for prefix\-aware decoding that further reduces redundant attention computation\[[35](https://arxiv.org/html/2605.05219#bib.bib13)\]\. 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](https://arxiv.org/html/2605.05219#bib.bib14)\]\. H2O retains only a heavy\-hitter set of KV entries that accumulate the most attention mass\[[37](https://arxiv.org/html/2605.05219#bib.bib15)\]\. PyramidKV and PyramidInfer exploit the observation that later layers need fewer cached tokens, and allocates budgets in a layer\-adaptive pyramid shape\[[4](https://arxiv.org/html/2605.05219#bib.bib16),[31](https://arxiv.org/html/2605.05219#bib.bib17)\]\. SnapKV clusters attention features to select representative KV entries per layer\[[16](https://arxiv.org/html/2605.05219#bib.bib18)\], and DMC proposes a learnable policy that decides which tokens to merge, evict, or keep\[[22](https://arxiv.org/html/2605.05219#bib.bib19)\]\.

In contrast to these, our method targets recurrent states rather than KV cache, and keeps the outputs exact\.

#### Hybrid\-model prefix caching\.

The closest prior work has been done by Marconi et al\.\[[23](https://arxiv.org/html/2605.05219#bib.bib8)\]\. It identifies that hybrid models use in\-place recurrent updates that make partial rollback hard, pushing serving toward exact\-match entries and creating many large, low\-value cache candidates\. The authors propose improved admission and eviction policies\. Our emphasis in this work is complementary: rather than improving the management of exact recurrent cache entries, we change the unit of reuse itself by storing sparse exact checkpoints so that partial prefix overlap becomes useful\.

#### Activation checkpointing in training\.

Sparse prefix caching is structurally similar to activation checkpointing\[[5](https://arxiv.org/html/2605.05219#bib.bib42)\], where a subset of layer activations is stored during the forward pass to reduce peak memory during backpropagation\. Both problems ask where to place checkpoints along a sequential computation so as to minimize recomputation under a memory budget\. The key differences are that:\(i\)activation checkpointing optimizes a single deterministic computation graph with known topology, whereas we optimize across requests with stochastic overlap, and\(ii\)in serving, checkpoint placement interacts with cache admission and eviction, which has no counterpart in training\.

#### Facility location andkk\-median problems\.

The offline checkpoint placement problem we study is a one\-sided, one\-dimensional weightedkk\-median on a line\. Classicalkk\-median is NP\-hard in general metric spaces\[[20](https://arxiv.org/html/2605.05219#bib.bib20)\], but the one\-dimensional case admits efficient dynamic programs\[[12](https://arxiv.org/html/2605.05219#bib.bib21),[10](https://arxiv.org/html/2605.05219#bib.bib22)\]\. Our convex\-hull\-trick solver exploits the monotone structure of prefix sums to achieveO​\(N​M\)O\(NM\)time, which is similar to the SMAWK\-based optimizations used in related interval\-scheduling problems\[[1](https://arxiv.org/html/2605.05219#bib.bib23)\]\.

## 3Problem Formulation

Consider a cached prefix of lengthNNand a checkpoint set

𝒞=\{c1,c2,…,cM\},1≤c1<⋯<cM≤N\.\\mathcal\{C\}=\\\{c\_\{1\},c\_\{2\},\\dots,c\_\{M\}\\\},\\qquad 1\\leq c\_\{1\}<\\cdots<c\_\{M\}\\leq N\.If a future request overlaps the prefix up to depthtt, then the deepest reusable checkpoint is

ℓ​\(t;𝒞\)=max⁡\(\{0\}∪\{c∈𝒞:c≤t\}\),\\ell\(t;\\mathcal\{C\}\)=\\max\(\\\{0\\\}\\cup\\\{c\\in\\mathcal\{C\}:c\\leq t\\\}\),and exact resumption requires recomputing

r​\(t;𝒞\)=t−ℓ​\(t;𝒞\)r\(t;\\mathcal\{C\}\)=t\-\\ell\(t;\\mathcal\{C\}\)tokens of recurrent work\. Let

Rnc=E​\[T\]=∑t=1Npt​tR\_\{\\mathrm\{nc\}\}=E\[T\]=\\sum\_\{t=1\}^\{N\}p\_\{t\}tdenote the no\-cache recurrent\-work baseline\. We report normalized savings as

Savings​\(C\)=1−E​\[r​\(T;C\)\]Rnc\.\\mathrm\{Savings\}\(C\)=1\-\\frac\{E\[r\(T;C\)\]\}\{R\_\{\\mathrm\{nc\}\}\}\.For plots whose vertical axis is marked “×\\times”, we additionally report the recurrent\-work reduction factor

Reduction​\(C\)=RncE​\[r​\(T;C\)\]=11−Savings​\(C\)\.\\mathrm\{Reduction\}\(C\)=\\frac\{R\_\{\\mathrm\{nc\}\}\}\{E\[r\(T;C\)\]\}=\\frac\{1\}\{1\-\\mathrm\{Savings\}\(C\)\}\.
#### Distributional formulation\.

We consider a version of this problem where exact request structure is ignored for simplicity and the overlap depth of each request is an i\.i\.d\. sample from the*overlap depth distribution*T∈\{1,…,N\}T\\in\\\{1,\\dots,N\\\}with masspt=Pr⁡\[T=t\]p\_\{t\}=\\Pr\[T=t\]\. The objective is the expected recomputation cost𝔼T​\[r​\(T;𝒞\)\]=∑t=1Npt​\(t−ℓ​\(t;𝒞\)\)\\mathbb\{E\}\_\{T\}\[r\(T;\\mathcal\{C\}\)\]=\\sum\_\{t=1\}^\{N\}p\_\{t\}\\,\(t\-\\ell\(t;\\mathcal\{C\}\)\)\.

#### Conditioning on retained hits\.

The theoretical objective is conditional on a retained cache entry whose prefix overlaps the incoming request\. Admission/eviction and exact\-match miss handling are orthogonal system components; in the experiments below, we combine sparse checkpoint placement with a fixed last\-KKentry policy to study the resulting runtime behavior\.

#### Drift generalization\.

We also consider a distribution drift setup, where the overlap depth distribution changes over time\. This version is motivated by the fact that the cache hit rate changes over time for real\-world deployments, either because of changing usage scenarios\[[25](https://arxiv.org/html/2605.05219#bib.bib40)\], steadily growing context lengths\[[9](https://arxiv.org/html/2605.05219#bib.bib41)\], or cache saturation\[[23](https://arxiv.org/html/2605.05219#bib.bib8)\]\.

#### Generalizing to a trie structure\.

Real cached prefixes form a trie \(prefix tree\), and the truly optimal checkpoint placement would optimize over this trie structure\. However, common real\-world topologies are either star\-shaped \(e\.g\., a chat with one root and many leaves\) or comb\-shaped \(shared document with varying suffixes\)\. In both cases, each edge of the trie is a single long shared prefix, so the trie\-optimal solution decomposes into independent per\-edge problems, each of which is exactly the single\-prefix formulation above\. We therefore restrict our attention to the single\-prefix case without loss of generality for these topologies\.

## 4Theoretical Analysis

### 4\.1Optimal checkpoint placement

We now collect the main mathematical results about sparse checkpoint placement\. Appendix[A](https://arxiv.org/html/2605.05219#A1)contains the proofs of all statements in this section\.

Throughout this section we define gap lengths

gi=ci\+1−ci,i=0,…,M,g\_\{i\}=c\_\{i\+1\}\-c\_\{i\},\\qquad i=0,\\dots,M,wherec0=0c\_\{0\}=0andcM\+1=N\+1c\_\{M\+1\}=N\+1\. Then thegig\_\{i\}are positive integers summing toN\+1N\+1\.

#### Balanced checkpointing\.

We begin by studying the simplest strategy where checkpoints are evenly spaced\. We call a checkpoint set𝒞\\mathcal\{C\}*balanced*if∀i≠j:\|gi−gj\|≤1\\forall i\\neq j:\|g\_\{i\}\-g\_\{j\}\|\\leq~1\.

###### Theorem 1\(Balanced checkpointing is optimal under uniform overlap and in worst\-case\)\.

Assumept=1/Np\_\{t\}=1/Nfor allt=1,…,Nt=1,\\dots,N\. LetK=M\+1K=M\+1and writeN\+1=q​K\+ρN\+1=qK\+\\rhowith0≤ρ<K0\\leq\\rho<K\. Then,

1. 1\.Checkpoint set minimizes𝔼​\[r​\(T;𝒞\)\]\\mathbb\{E\}\[r\(T;\\mathcal\{C\}\)\]if and only if it is balanced\. The exact optimal expected recomputation is 𝔼​\[r​\(T;𝒞⋆\)\]=1N​\(\(K−ρ\)​q​\(q−1\)2\+ρ​q​\(q\+1\)2\)=N2​\(M\+1\)\+O​\(1\),\\mathbb\{E\}\[r\(T;\\mathcal\{C\}^\{\\star\}\)\]=\\frac\{1\}\{N\}\\left\(\(K\-\\rho\)\\frac\{q\(q\-1\)\}\{2\}\+\\rho\\frac\{q\(q\+1\)\}\{2\}\\right\)=\\frac\{N\}\{2\(M\+1\)\}\+O\(1\),where theO​\(1\)O\(1\)term is forN→∞N\\to\\inftywithMMfixed\.
2. 2\.Balanced sets also minimizemaxt⁡r​\(t;𝒞\)\\max\\limits\_\{t\}\\,r\(t;\\mathcal\{C\}\)with worst\-case recomputation of⌈N\+1M\+1⌉−1\\Big\\lceil\\frac\{N\+1\}\{M\+1\}\\Big\\rceil\-1tokens\.

One notable regime isM=O​\(N\)M=O\(\\sqrt\{N\}\), where the number of checkpoints and the expected/worst\-case recomputation both grow at rateN\\sqrt\{N\}\.

While Theorem[1](https://arxiv.org/html/2605.05219#Thmtheorem1)provides optimal checkpoint sets under uniform and worst\-case assumptions, its results are unlikely to extend to real\-world serving systems, which target average throughput rather than worst\-case latency\[[36](https://arxiv.org/html/2605.05219#bib.bib26),[14](https://arxiv.org/html/2605.05219#bib.bib4),[38](https://arxiv.org/html/2605.05219#bib.bib5)\], and where the overlap distribution is far from uniform \(Fig\.[1](https://arxiv.org/html/2605.05219#S5.F1)\)\.

#### Distribution\-aware checkpointing\.

For a given overlap distributionp1,…,pNp\_\{1\},\\dots,p\_\{N\}and budgetMM, letdp​\[m,j\]\\mathrm\{dp\}\[m,j\]denote the minimum recomputation cost of serving depths\{1,…,j\}\\\{1,\\dots,j\\\}withmmcheckpoints\. If the last checkpoint is placed at positions≤js\\leq j, the cost decomposes into:

1. \(1\)the optimal cost of serving\{1,…,s−1\}\\\{1,\\dots,s\{\-\}1\\\}withm−1m\{\-\}1checkpoints, namelydp​\[m−1,s−1\]\\mathrm\{dp\}\[m\{\-\}1,s\{\-\}1\];
2. \(2\)the cost of usingssas the deepest checkpoint for depthst∈\{s,…,j\}t\\in\\\{s,\\dots,j\\\}, namelyw​\(s,j\)=∑t=sjpt​\(t−s\)w\(s,j\)=\\sum\_\{t=s\}^\{j\}p\_\{t\}\(t\{\-\}s\)

###### Theorem 2\(Exact dynamic program\)\.

For a given overlap depth distribution, the optimal checkpoint placement satisfies the recurrence

dp​\[0,j\]=∑t=1jpt​t,dp​\[m,j\]=min1≤s≤j⁡\(dp​\[m−1,s−1\]\+w​\(s,j\)\)\.\\mathrm\{dp\}\[0,j\]=\\sum\_\{t=1\}^\{j\}p\_\{t\}\\,t,\\qquad\\mathrm\{dp\}\[m,j\]=\\min\_\{1\\leq s\\leq j\}\\bigl\(\\mathrm\{dp\}\[m\-1,s\-1\]\+w\(s,j\)\\bigr\)\.
With prefix sumsPj=∑t=1jptP\_\{j\}=\\sum\_\{t=1\}^\{j\}p\_\{t\}andTj=∑t=1jt​ptT\_\{j\}=\\sum\_\{t=1\}^\{j\}t\\,p\_\{t\}, each DP layer can be evaluated inO​\(N\)O\(N\)time using the monotone convex hull trick \(the slopes−s\-sare monotone inssand the query pointsPjP\_\{j\}are non\-decreasing injj\), givingO​\(N​M\)O\(NM\)total time\.

For a fixed estimated overlap law and budget, this schedule can be computed offline and refreshed only when the histogram estimate is updated; it adds no optimization overhead on the serving path itself\.

### 4\.2Empirical histograms

In practice, we do not have access to true overlap depth probabilities since they can only be estimated using historical data\. Lemma[1](https://arxiv.org/html/2605.05219#Thmlemma1)justifies using the empirical histogram oracle: if the observed overlap histogram converges to the true law in total variation, then the optimal sparse schedule is necessarily close in value\.

###### Lemma 1\(Stability under distribution misspecification\)\.

\|𝔼p​\[r​\(T;𝒞\)\]−𝔼q​\[r​\(T;𝒞\)\]\|≤N​‖p−q‖1\.\\left\|\\mathbb\{E\}\_\{p\}\[r\(T;\\mathcal\{C\}\)\]\-\\mathbb\{E\}\_\{q\}\[r\(T;\\mathcal\{C\}\)\]\\right\|\\leq N\\\|p\-q\\\|\_\{1\}\.

Note that the total variation in the right\-hand side can be further bounded whenqqis the empirical distribution ofpp\[[8](https://arxiv.org/html/2605.05219#bib.bib27),[19](https://arxiv.org/html/2605.05219#bib.bib28),[3](https://arxiv.org/html/2605.05219#bib.bib29)\]\. Theorem[3](https://arxiv.org/html/2605.05219#Thmtheorem3)gives a self\-contained stationary\-learning guarantee for the histogram oracle: under i\.i\.d\. overlap, empirical re\-estimation becomes near\-optimal at the familiarn−1/2n^\{\-1/2\}rate\.

###### Theorem 3\(High\-probability plug\-in guarantee for the empirical histogram oracle\)\.

LetT1,…,TnT\_\{1\},\\dots,T\_\{n\}be i\.i\.d\. overlap samples from a lawp=\(p1,…,pN\)p=\(p\_\{1\},\\dots,p\_\{N\}\), letp^\(n\)\\hat\{p\}^\{\(n\)\}be the empirical distribution, and let𝒞^n\\widehat\{\\mathcal\{C\}\}\_\{n\}be any optimal checkpoint set of sizeMMforp^\(n\)\\hat\{p\}^\{\(n\)\}\. Then for everyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\delta,

‖p^\(n\)−p‖1≤Nn\+2​log⁡\(1/δ\)n\.\\\|\\hat\{p\}^\{\(n\)\}\-p\\\|\_\{1\}\\leq\\sqrt\{\\frac\{N\}\{n\}\}\+\\sqrt\{\\frac\{2\\log\(1/\\delta\)\}\{n\}\}\.Consequently, the plug\-in schedule satisfies

0≤𝔼p​\[r​\(T;𝒞^n\)\]−VM​\(p\)≤2​N​\(Nn\+2​log⁡\(1/δ\)n\),0\\leq\\mathbb\{E\}\_\{p\}\[r\(T;\\widehat\{\\mathcal\{C\}\}\_\{n\}\)\]\-V\_\{M\}\(p\)\\leq 2N\\left\(\\sqrt\{\\frac\{N\}\{n\}\}\+\\sqrt\{\\frac\{2\\log\(1/\\delta\)\}\{n\}\}\\right\),whereVM​\(p\)V\_\{M\}\(p\)is the optimalMM\-checkpoint cost under the true law\.

We also study the scenario where the true overlap depth distribution can drift over time\. Exponential reweighting\[[2](https://arxiv.org/html/2605.05219#bib.bib37),[21](https://arxiv.org/html/2605.05219#bib.bib38),[18](https://arxiv.org/html/2605.05219#bib.bib39)\]is a classical technique to track drifting distributions, where older samples receive exponentially decaying weights proportional toγt−s\\gamma^\{t\-s\}so that the reweighted empirical estimate remains close in total variation to the current distribution\. It allows us to bound total variation and substitute these bounds into Lemma[1](https://arxiv.org/html/2605.05219#Thmlemma1)\.

###### Theorem 4\(Bias\-variance tracking bound for exponential histograms\)\.

LetT1,…,TtT\_\{1\},\\dots,T\_\{t\}be independent overlap samples with time\-varying lawsp1,…,ptp\_\{1\},\\dots,p\_\{t\}, and define the exponentially weighted empirical histogram

p^t\(γ\)=1−γ1−γt​∑s=1tγt−s​eTs,0<γ<1,\\hat\{p\}\_\{t\}^\{\(\\gamma\)\}=\\frac\{1\-\\gamma\}\{1\-\\gamma^\{t\}\}\\sum\_\{s=1\}^\{t\}\\gamma^\{t\-s\}e\_\{T\_\{s\}\},\\qquad 0<\\gamma<1,whereeTse\_\{T\_\{s\}\}is the one\-hot vector at the observed overlap depth\. Then

𝔼​\[‖p^t\(γ\)−pt‖1\]≤1−γ1−γt​∑s=1tγt−s​‖ps−pt‖1\+N​1−γ1\+γ​1\+γt1−γt\.\\mathbb\{E\}\\\!\\left\[\\\|\\hat\{p\}\_\{t\}^\{\(\\gamma\)\}\-p\_\{t\}\\\|\_\{1\}\\right\]\\leq\\frac\{1\-\\gamma\}\{1\-\\gamma^\{t\}\}\\sum\_\{s=1\}^\{t\}\\gamma^\{t\-s\}\\\|p\_\{s\}\-p\_\{t\}\\\|\_\{1\}\+\\sqrt\{N\\frac\{1\-\\gamma\}\{1\+\\gamma\}\\frac\{1\+\\gamma^\{t\}\}\{1\-\\gamma^\{t\}\}\}\.

Combined with Lemma[1](https://arxiv.org/html/2605.05219#Thmlemma1), this immediately yields a corresponding excess\-recomputation bound for schedules selected from the exponentially weighted histogram\.

For largett, the variance term behaves asN​\(1−γ\)/\(1\+γ\)\\sqrt\{N\(1\-\\gamma\)/\(1\+\\gamma\)\}\. Under bounded drift‖pu−pu−1‖1≤Δ\\\|p\_\{u\}\-p\_\{u\-1\}\\\|\_\{1\}\\leq\\Deltafor alluu, the bias term is at mostΔ​γ/\(1−γ\)\\Delta\\gamma/\(1\-\\gamma\)\. Settingγ=0\.99\\gamma=0\.99\(our experimental choice\) trades off these terms in favor of low variance while still tracking moderate drift; empirically we did not observe strong sensitivity to this choice across our datasets\.

## 5Experimental Methodology

#### Baselines and Methods\.

We compare our method against dense and deterministic sparse checkpoint placement strategies\. We additionally include a logarithmic baseline with exponentially increasing gap sizes from the beginning of the prefix; in the figures this baseline is labeledLogarithmic\. For hybrid models, we assume that all strategies store the entire KV cache for the full attention layers; they differ only in the location of recurrent layer checkpoints\. Since modern serving systems store KV cache in blocks and efficient GPU kernels operate blockwise\[[6](https://arxiv.org/html/2605.05219#bib.bib34),[32](https://arxiv.org/html/2605.05219#bib.bib35),[15](https://arxiv.org/html/2605.05219#bib.bib36),[14](https://arxiv.org/html/2605.05219#bib.bib4)\], we clip every checkpoint position to the block boundaries; the block size isB=128B=128tokens throughout\. All methods are subjected to this same implementation constraint, so the measured system curves should be read as blockwise execution results rather than as an idealized token\-level runtime\.

Table 1:Recurrent\-state checkpoint placement strategies\. All hybrid\-model runs store the full attention KV cache; the methods differ only in where recurrent\-layer checkpoints are placed;LLis the cached prefix length,BBis the block size, andMMis the recurrent\-checkpoint budget\.StrategyCheckpoint positionsTail recomputeNo cache—LLKV only—LLBalanced⌊i​\(L\+1\)/\(M\+1\)⌋,i=1,…,M\\lfloor i\(L\+1\)/\(M\+1\)\\rfloor,\\ i=1,\\dots,M⌈L\+1M\+1⌉−1\\left\\lceil\\frac\{L\+1\}\{M\+1\}\\right\\rceil\-1BlockB,2​B,…,⌊L/B⌋​BB,2B,\\ldots,\\lfloor L/B\\rfloor BLmodBL\\bmod BL\\sqrt\{L\}⌊L⌋\\lfloor\\sqrt\{L\}\\rfloor\-spacedLmod⌊L⌋L\\bmod\\lfloor\\sqrt\{L\}\\rfloorDP\-optimalsolved via Theorem[2](https://arxiv.org/html/2605.05219#Thmtheorem2)distribution\-dependent
#### Our method\.

In the main results section we report the exponentially reweighted DP\-optimal checkpoint placement withγ=0\.99\\gamma=0\.99, re\-solving and updating the histogram every 10 requests to tackle distribution shift\.

#### Datasets\.

In real\-world data, unrelated requests almost never have long common prefixes, because the number of possible token sequences grows combinatorially with length\. However, requests can share long non\-trivial prefixes if they start with a static chunk of text\. We group such datasets into two kinds:

1. \(1\)*single document with multiple questions*: QuALITY\[[24](https://arxiv.org/html/2605.05219#bib.bib30)\], NarrativeQA\[[13](https://arxiv.org/html/2605.05219#bib.bib31)\];
2. \(2\)*long shared prompt*: we take real system prompts from major LLM providers\[[30](https://arxiv.org/html/2605.05219#bib.bib33)\], and combine them with real user queries from the ShareGPT\[[28](https://arxiv.org/html/2605.05219#bib.bib32)\]dataset\.

All these datasets are structured so that requests come in groups that may have long prefix overlap, and the maximum possible speedup is bounded by its length\. We limit each dataset to 1000 requests for prototype wall\-clock runs\. For savings results, which can be calculated without performing real inference and storing the KV cache, we use 10K requests\. To simulate online cache state, we order requests according to a Poisson arrival process; under the fixed last\-KKpolicy, only the induced request order affects the results\.

#### KV cache management\.

Orthogonal to checkpoint placement efficiency, the maximum speedup from prefix caching is bounded by the cache size and cache eviction policies: even perfectly placed checkpoints do not bring any speedup if the cached checkpoints have already been evicted\. To isolate this effect, we use a simple caching strategy that keeps exactly the lastKKentries\. We do not include a direct baseline from\[[23](https://arxiv.org/html/2605.05219#bib.bib8)\]in these plots because Marconi et al\. optimize admission and eviction across entries, whereas here we fix a simple last\-KKpolicy precisely to isolate within\-entry checkpoint placement\.

#### Implementation details\.

All prototype timing experiments were run on an NVIDIA RTX 2080 Super with 8 GB VRAM, paired with an Intel Core i5\-12400F CPU and 16 GB DDR4 RAM, using the HuggingFace Transformers model implementation, CUDA 13\.0, and PyTorch 2\.10\. We use a cache capacity ofK=100K=100entries for NarrativeQA \(simulation\),K=50K=50for System Prompts, andK=35K=35for QuALITY under the fixed last\-KKpolicy; these values are chosen to fit the available CPU RAM\. We use block sizeB=64B=64, matching the block granularity of the Flash Linear Attention kernels, and an exponentially weighted overlap histogram withγ=0\.99\\gamma=0\.99refreshed every1010requests\. We use chunked prefill, because when resuming from a non\-first position HuggingFace Transformers materializes a full attention mask that does not fit the available VRAM for realistic request lengths\. Reported timing curves are obtained from a single deterministic run for each dataset and budget; pilot runs with different random seeds produced negligible variation, so we omit error bars in this prototype evaluation and defer a more thorough statistical treatment to a full\-device study on production hardware\.

#### Capturing checkpoints\.

We report inference time and capture recurrent\-state checkpoints in separate untimed runs, because the current Flash Linear Attention library does not expose a Python API for non\-last checkpoint extraction, although the underlying low\-level kernels already return recurrent states at block\-6464positions\. We view removing this off\-critical\-path separation as a straightforward engineering task and defer it, together with the full\-device evaluation, to future work\.

#### Overlap distributions\.

Figure[1](https://arxiv.org/html/2605.05219#S5.F1)shows the empirical overlap depth distributions across all three datasets\. The distributions are far from uniform: QuALITY has a sharp spike near the full document length, NarrativeQA exhibits a wide multimodal spread, and System Prompts concentrate mass at short prefix lengths\. These shapes explain why distribution\-aware placement outperforms balanced spacing, especially at low budgets\.

![Refer to caption](https://arxiv.org/html/2605.05219v1/x1.png)Figure 1:Empirical overlap depth distributions across datasets\.

## 6Results

#### Token savings\.

Figure[2](https://arxiv.org/html/2605.05219#S6.F2)shows the recurrent\-work reduction factor on NarrativeQA, where sequences are too long for the same prototype timing setup on available hardware\. The DP\-optimal schedule consistently dominates the deterministic baselines across the full budget range\. The advantage is largest at low checkpoint budgets, where the empirical overlap distribution is most non\-uniform, and narrows as the budget grows and all methods cover an increasing fraction of the prefix\.

![Refer to caption](https://arxiv.org/html/2605.05219v1/x2.png)Figure 2:Recurrent\-work reduction factor vs\. checkpoint budget on NarrativeQA\.
#### Prototype wall\-clock time\.

Figure[3](https://arxiv.org/html/2605.05219#S6.F3)shows prototype wall\-clock Pareto fronts on QuALITY and System Prompts\. Wall\-clock time was measured on a representative layer group \(1 full attention layer and 3 GatedDeltaNet layers\) of the Qwen\-3\.5\-0\.8B model\[[27](https://arxiv.org/html/2605.05219#bib.bib11)\]\. We therefore interpret these measurements as evidence that token savings translate into runtime savings under a realistic implementation constraint, rather than as full\-model serving benchmarks\.

![Refer to caption](https://arxiv.org/html/2605.05219v1/x3.png)Figure 3:Prototype layer\-group Pareto fronts: measured layer\-group time vs\. checkpoint budget on \(a\) QuALITY and \(b\) System Prompts\.
#### When does distribution\-aware placement help?

The advantage of DP\-optimal over balanced is largest at low checkpoint budgets and on workloads with concentrated overlap distributions\. On System Prompts \(Fig\.[3](https://arxiv.org/html/2605.05219#S6.F3)b\), where overlap mass concentrates at short prefix lengths \(Fig\.[1](https://arxiv.org/html/2605.05219#S5.F1)c\), the DP places checkpoints densely near the divergence peak and leaves the tail uncovered, achieving the same measured runtime as block caching but with fewer checkpoints\. On QuALITY \(Fig\.[3](https://arxiv.org/html/2605.05219#S6.F3)a\), the gap between DP\-optimal and balanced is smaller because the overlap distribution is closer to a point mass at the full document length, reducing the scope for non\-uniform placement\. In the limit of large budgets, all strategies converge because every prefix position is approximately covered\.

![Refer to caption](https://arxiv.org/html/2605.05219v1/x4.png)Figure 4:Real wall\-time vs amount of recurrent work on System Prompts dataset\. Marker size corresponds to amount of cache for CPU→\\toGPU transfer\.For NarrativeQA, recall that we report the reduction factor rather than wall\-clock time because the sequences do not fit the prototype setup\. We verify in Fig\.[4](https://arxiv.org/html/2605.05219#S6.F4)that the number of tokens to recompute is essentially proportional to wall\-clock time on the smaller datasets, so the reduction\-factor curves should translate directly to runtime savings on hardware that does fit NarrativeQA\.

#### Overhead decomposition\.

The wall\-clock cost of a cache hit consists of:\(i\)loading the stored checkpoint from CPU to GPU,\(ii\)replaying the suffix through the recurrent layers, and\(iii\)for the attention layers, loading the cached KV state\.

Figure[4](https://arxiv.org/html/2605.05219#S6.F4)shows that wall\-clock time is approximately linear in the number of tokens to recompute, with a small constant offset due to cache loading\. This offset is visible as the nonzero intercept for the hit strategies; its magnitude grows with the amount of cached state \(marker size in the figure\)\. For the checkpoint budgets used in our experiments, the loading overhead is small relative to the recomputation savings, which is why the prototype Pareto fronts show net runtime improvement\.

## 7Conclusion

Sparse prefix caching is based on a structural asymmetry in hybrid and recurrent LLMs: exact reuse does not require dense per\-token recurrent state\. By storing only a sparse set of exact checkpoints and replaying the missing suffix, we obtain a new memory/recompute trade\-off that cannot be obtained in dense KV\-centric serving\.

The main limitation is that our approach is most useful when many requests share a substantial but not identical prefix inside a retained cache entry; in some situations this is indeed the case, but append\-only chat workloads have different properties: if you include all history every time and only append to it, caching the last checkpoint is obviously sufficient\.

For future work, we first of all note engineering challenges: to implement caching in a useful way one has to implement efficient state extraction and restoration in production runtimes and combine checkpoint placement with Marconi\-style admission/eviction\. As for theory, we note that our single\-prefix theory can hopefully be further extended to general prefix trees with branching and eviction\.

## References

- \[1\]A\. Aggarwal, M\. M\. Klawe, S\. Moran, P\. Shor, and R\. Wilber\(1987\)Geometric applications of a matrix\-searching algorithm\.Algorithmica2,pp\. 195–208\.Cited by:[§2](https://arxiv.org/html/2605.05219#S2.SS0.SSS0.Px5.p1.3)\.
- \[2\]R\. D\. Barve and P\. M\. Long\(1997\)On the complexity of learning from drifting distributions\.Information and Computation138\(2\),pp\. 170–193\.Cited by:[§4\.2](https://arxiv.org/html/2605.05219#S4.SS2.p3.1)\.
- \[3\]D\. Berend and A\. Kontorovich\(2012\)On the convergence of the empirical distribution\.arXiv preprint arXiv:1205\.6711\.Cited by:[§4\.2](https://arxiv.org/html/2605.05219#S4.SS2.p2.3)\.
- \[4\]Z\. Cai, Y\. Zhang, B\. Gao, Y\. Liu, T\. Liu, K\. Lu, W\. Xiong, Y\. Dong, B\. Chang, J\. Hu, and W\. Xiao\(2024\)PyramidKV: dynamic KV cache compression based on pyramidal information funneling\.arXiv preprint arXiv:2406\.02069\.Cited by:[§2](https://arxiv.org/html/2605.05219#S2.SS0.SSS0.Px2.p1.1)\.
- \[5\]T\. Chen, B\. Xu, C\. Zhang, and C\. Guestrin\(2016\)Training deep nets with sublinear memory cost\.External Links:1604\.06174,[Link](https://arxiv.org/abs/1604.06174)Cited by:[§1](https://arxiv.org/html/2605.05219#S1.p6.1),[§2](https://arxiv.org/html/2605.05219#S2.SS0.SSS0.Px4.p1.1)\.
- \[6\]T\. Dao, D\. Y\. Fu, S\. Ermon, A\. Rudra, and C\. Ré\(2022\)FlashAttention: fast and memory\-efficient exact attention with IO\-awareness\.Advances in Neural Information Processing Systems \(NeurIPS\)35\.Cited by:[§5](https://arxiv.org/html/2605.05219#S5.SS0.SSS0.Px1.p1.1)\.
- \[7\]T\. Dao and A\. Gu\(2024\)Transformers are SSMs: generalized models and efficient algorithms through structured state space duality\.arXiv preprint arXiv:2405\.21060\.Cited by:[§1](https://arxiv.org/html/2605.05219#S1.p2.5)\.
- \[8\]L\. Devroye and G\. Lugosi\(2001\)Combinatorial methods in density estimation\.Springer\.Cited by:[§4\.2](https://arxiv.org/html/2605.05219#S4.SS2.p2.3)\.
- \[9\]Y\. Fu, P\. Bailis, I\. Stoica, and H\. Zhang\(2024\)Challenges in deploying long\-context transformers: a theoretical peak performance analysis\.arXiv preprint arXiv:2405\.08944\.Cited by:[§3](https://arxiv.org/html/2605.05219#S3.SS0.SSS0.Px3.p1.1)\.
- \[10\]L\. K\. Grover\(1996\)A new algorithm for thekk\-median problem\.Information Processing Letters57\(3\),pp\. 151–155\.Cited by:[§2](https://arxiv.org/html/2605.05219#S2.SS0.SSS0.Px5.p1.3)\.
- \[11\]A\. Gu and T\. Dao\(2023\)Mamba: linear\-time sequence modeling with selective state spaces\.arXiv preprint arXiv:2312\.00752\.Cited by:[§1](https://arxiv.org/html/2605.05219#S1.p2.5)\.
- \[12\]R\. Hassin and A\. Tamir\(1991\)Improved complexity bounds for location problems on the real line\.Operations Research Letters10\(7\),pp\. 395–402\.Cited by:[§2](https://arxiv.org/html/2605.05219#S2.SS0.SSS0.Px5.p1.3)\.
- \[13\]T\. Kočiský, J\. Schwarz, P\. Blunsom, C\. Dyer, K\. M\. Hermann, G\. Melis, and E\. Grefenstette\(2018\)The NarrativeQA reading comprehension challenge\.Transactions of the Association for Computational Linguistics6,pp\. 317–328\.Cited by:[item 1](https://arxiv.org/html/2605.05219#S5.I1.i1.p1.1)\.
- \[14\]W\. Kwon, Z\. Li, S\. Zhuang, Y\. Sheng, L\. Zheng, C\. H\. Yu, J\. E\. Gonzalez, H\. Zhang, and I\. Stoica\(2023\)Efficient memory management for large language model serving with pagedattention\.arXiv preprint arXiv:2309\.06180\.Cited by:[§1](https://arxiv.org/html/2605.05219#S1.p1.1),[§2](https://arxiv.org/html/2605.05219#S2.SS0.SSS0.Px1.p1.1),[§4\.1](https://arxiv.org/html/2605.05219#S4.SS1.SSS0.Px1.p3.1),[§5](https://arxiv.org/html/2605.05219#S5.SS0.SSS0.Px1.p1.1)\.
- \[15\]B\. Lefaudeux, F\. Massa, D\. Liskovich, W\. Xiong, V\. Caggiano, S\. Nber, T\. Xu, J\. Hu, M\. Tintore, S\. Ho, P\. Labatut, and D\. Haziza\(2022\)XFormers: a modular and hackable transformer modelling library\.Note:[https://github\.com/facebookresearch/xformers](https://github.com/facebookresearch/xformers)Cited by:[§5](https://arxiv.org/html/2605.05219#S5.SS0.SSS0.Px1.p1.1)\.
- \[16\]Y\. Li, Y\. Huang, B\. Yang, B\. Venkitesh, A\. Locatelli, H\. Ye, T\. Cai, P\. Lewis, and D\. Chen\(2024\)SnapKV: LLM knows what you are looking for before generation\.arXiv preprint arXiv:2404\.14469\.Cited by:[§2](https://arxiv.org/html/2605.05219#S2.SS0.SSS0.Px2.p1.1)\.
- \[17\]Z\. Liu, A\. Desai, F\. Liao, W\. Wang, V\. Xie, Z\. Xu, A\. Kyrillidis, and A\. Shrivastava\(2024\)Scissorhands: exploiting the persistence of importance hypothesis for LLM KV cache compression at test time\.arXiv preprint arXiv:2305\.17118\.Cited by:[§2](https://arxiv.org/html/2605.05219#S2.SS0.SSS0.Px2.p1.1)\.
- \[18\]A\. Mazzetto and E\. Upfal\(2023\)Nonparametric density estimation under distribution drift\.InInternational Conference on Machine Learning \(ICML\),pp\. 24251–24270\.Cited by:[§4\.2](https://arxiv.org/html/2605.05219#S4.SS2.p3.1)\.
- \[19\]C\. McDiarmid\(1989\)On the method of bounded differences\.InSurveys in Combinatorics,J\. Siemons \(Ed\.\),London Mathematical Society Lecture Note Series, Vol\.141,pp\. 148–188\.Cited by:[§4\.2](https://arxiv.org/html/2605.05219#S4.SS2.p2.3)\.
- \[20\]N\. Megiddo and K\. J\. Supowit\(1984\)The complexity of some common geometric location problems\.Journal of Algorithms5\(4\),pp\. 544–554\.Cited by:[§2](https://arxiv.org/html/2605.05219#S2.SS0.SSS0.Px5.p1.3)\.
- \[21\]M\. Mohri and A\. Muñoz Medina\(2012\)New analysis and algorithm for learning with drifting distributions\.InAlgorithmic Learning Theory \(ALT\),pp\. 124–138\.Cited by:[§4\.2](https://arxiv.org/html/2605.05219#S4.SS2.p3.1)\.
- \[22\]P\. Nawrot, A\. Łancucki, M\. Chochowski, D\. Tarjan, and E\. M\. Ponti\(2024\)Dynamic memory compression: retrofitting LLMs for accelerated inference\.arXiv preprint arXiv:2403\.09636\.Cited by:[§2](https://arxiv.org/html/2605.05219#S2.SS0.SSS0.Px2.p1.1)\.
- \[23\]R\. Pan, Z\. Wang, Z\. Jia, C\. Karakus, L\. Zancato, T\. Dao, Y\. Wang, and R\. Netravali\(2024\)Marconi: prefix caching for the era of hybrid LLMs\.arXiv preprint arXiv:2411\.19379\.Cited by:[§1](https://arxiv.org/html/2605.05219#S1.p4.2),[§2](https://arxiv.org/html/2605.05219#S2.SS0.SSS0.Px3.p1.1),[§3](https://arxiv.org/html/2605.05219#S3.SS0.SSS0.Px3.p1.1),[§5](https://arxiv.org/html/2605.05219#S5.SS0.SSS0.Px4.p1.2)\.
- \[24\]R\. Y\. Pang, A\. Parrish, N\. Joshi, N\. Nangia, J\. Phang, A\. Chen, V\. Padmakumar, J\. Ma, J\. Thompson, H\. He, and S\. R\. Bowman\(2022\)QuALITY: question answering with long input texts, yes\!\.Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics \(NAACL\),pp\. 5336–5358\.Cited by:[item 1](https://arxiv.org/html/2605.05219#S5.I1.i1.p1.1)\.
- \[25\]P\. Patel, E\. Choukse, C\. Zhang, A\. Shah, Í\. Goiri, S\. Maleki, and R\. Bianchini\(2024\)Splitwise: efficient generative LLM inference using phase splitting\.arXiv preprint arXiv:2311\.18677\.Cited by:[§3](https://arxiv.org/html/2605.05219#S3.SS0.SSS0.Px3.p1.1)\.
- \[26\]B\. Peng, E\. Alcaide, Q\. Anthony, A\. Albalak, S\. Arcadinho, H\. Cao, X\. Cheng, M\. Chung, M\. Grber,et al\.\(2023\)RWKV: reinventing RNNs for the transformer era\.arXiv preprint arXiv:2305\.13048\.Cited by:[§1](https://arxiv.org/html/2605.05219#S1.p2.5)\.
- \[27\]Qwen Team\(2025\)Qwen3\.5 technical report\.Note:[https://qwen\.ai/blog?id=qwen3\.5](https://qwen.ai/blog?id=qwen3.5)Cited by:[§1](https://arxiv.org/html/2605.05219#S1.p2.5),[§6](https://arxiv.org/html/2605.05219#S6.SS0.SSS0.Px2.p1.1)\.
- \[28\]ShareGPT Community\(2023\)ShareGPT\.Note:[https://sharegpt\.com](https://sharegpt.com/)Cited by:[item 2](https://arxiv.org/html/2605.05219#S5.I1.i2.p1.1)\.
- \[29\]V\. Srivatsa, Z\. He, R\. Abhyankar, D\. Li, and Y\. Zhang\(2024\)Preble: efficient distributed prompt scheduling for LLM serving\.arXiv preprint arXiv:2407\.00023\.Cited by:[§1](https://arxiv.org/html/2605.05219#S1.p1.1),[§2](https://arxiv.org/html/2605.05219#S2.SS0.SSS0.Px1.p1.1)\.
- \[30\]Á\. Thorsteinsson\(2024\)System prompts leaks\.Note:[https://github\.com/asgeirtj/system\_prompts\_leaks](https://github.com/asgeirtj/system_prompts_leaks)Cited by:[item 2](https://arxiv.org/html/2605.05219#S5.I1.i2.p1.1)\.
- \[31\]D\. Yang, X\. Han, Y\. Gao, Y\. Hu, S\. Zhang, and H\. Zhao\(2024\)PyramidInfer: pyramid KV cache compression for high\-throughput LLM inference\.arXiv preprint arXiv:2405\.12532\.Cited by:[§2](https://arxiv.org/html/2605.05219#S2.SS0.SSS0.Px2.p1.1)\.
- \[32\]S\. Yanget al\.\(2024\)Flash\-linear\-attention\.Note:[https://github\.com/fla\-org/flash\-linear\-attention](https://github.com/fla-org/flash-linear-attention)Cited by:[§5](https://arxiv.org/html/2605.05219#S5.SS0.SSS0.Px1.p1.1)\.
- \[33\]S\. Yang, B\. Wang, Y\. Shen, R\. Panda, and Y\. Kim\(2024\)Gated linear attention transformers with hardware\-efficient training\.arXiv preprint arXiv:2312\.06635\.Cited by:[§1](https://arxiv.org/html/2605.05219#S1.p2.5)\.
- \[34\]J\. Yao, H\. Li, Y\. Liu, S\. Ray, Y\. Cheng, Q\. Zhang, K\. Du, S\. Lu, and J\. Jiang\(2024\)CacheBlend: fast large language model serving for RAG with cached knowledge fusion\.arXiv preprint arXiv:2405\.16444\.Cited by:[§2](https://arxiv.org/html/2605.05219#S2.SS0.SSS0.Px1.p1.1)\.
- \[35\]L\. Ye, Z\. Liang, Y\. Guan, Z\. Jia, and L\. Li\(2024\)ChunkAttention: efficient self\-attention with prefix\-aware KV cache and two\-phase partition\.arXiv preprint arXiv:2402\.15220\.Cited by:[§2](https://arxiv.org/html/2605.05219#S2.SS0.SSS0.Px1.p1.1)\.
- \[36\]G\. Yu, J\. S\. Jeong, G\. Kim, S\. Kim, and B\. Chun\(2022\)Orca: a distributed serving system for transformer\-based generative models\.Proceedings of the 16th USENIX Symposium on Operating Systems Design and Implementation \(OSDI\),pp\. 521–538\.Cited by:[§4\.1](https://arxiv.org/html/2605.05219#S4.SS1.SSS0.Px1.p3.1)\.
- \[37\]Z\. Zhang, Y\. Sheng, T\. Zhou, T\. Chen, L\. Zheng, R\. Cai, Z\. Song, Y\. Tian, C\. Ré, C\. Barrett, Z\. Wang, and B\. Chen\(2024\)H2O: heavy\-hitter oracle for efficient generative inference of large language models\.arXiv preprint arXiv:2306\.14048\.Cited by:[§2](https://arxiv.org/html/2605.05219#S2.SS0.SSS0.Px2.p1.1)\.
- \[38\]L\. Zheng, L\. Yin, Z\. Xie, C\. Sun, J\. Huang, C\. H\. Yu, S\. Cao, C\. Kozyrakis, I\. Stoica, J\. E\. Gonzalez, C\. Barrett, and Y\. Sheng\(2023\)SGLang: efficient execution of structured language model programs\.arXiv preprint arXiv:2312\.07104\.Cited by:[§1](https://arxiv.org/html/2605.05219#S1.p1.1),[§2](https://arxiv.org/html/2605.05219#S2.SS0.SSS0.Px1.p1.1),[§4\.1](https://arxiv.org/html/2605.05219#S4.SS1.SSS0.Px1.p3.1)\.

## Appendix AProofs

All theorem and lemma statements in this appendix appear in the main text; we only restate them here to the extent needed for the proofs, and do not repeat this notice for individual results\.

### A\.1Balanced sparse checkpoints

###### Lemma 2\(Gap decomposition under uniform overlap\)\.

Ifpt=1/Np\_\{t\}=1/Nfort=1,…,Nt=1,\\dots,N, then

N​𝔼​\[r​\(T;𝒞\)\]=∑i=0M∑h=0gi−1h=∑i=0Mgi​\(gi−1\)2\.N\\,\\mathbb\{E\}\[r\(T;\\mathcal\{C\}\)\]=\\sum\_\{i=0\}^\{M\}\\sum\_\{h=0\}^\{g\_\{i\}\-1\}h=\\sum\_\{i=0\}^\{M\}\\frac\{g\_\{i\}\(g\_\{i\}\-1\)\}\{2\}\.\(1\)

###### Proof of Lemma[2](https://arxiv.org/html/2605.05219#Thmlemma2)\.

On the gap\(ci,ci\+1\)\(c\_\{i\},c\_\{i\+1\}\), the reusable depth remains fixed atcic\_\{i\}, so the recompute costs on positionst=ci,ci\+1,…,ci\+1−1t=c\_\{i\},c\_\{i\}\{\+\}1,\\dots,c\_\{i\+1\}\{\-\}1are precisely0,1,…,gi−10,1,\\dots,g\_\{i\}\{\-\}1\. Under the uniform lawpt=1/Np\_\{t\}=1/N, every depth contributes equally, hence \([1](https://arxiv.org/html/2605.05219#A1.E1)\)\. ∎

###### Proof of Theorem[1](https://arxiv.org/html/2605.05219#Thmtheorem1)\.1\.

We will show that a checkpoint set𝒞\\mathcal\{C\}minimizes𝔼​\[r​\(T;𝒞\)\]\\mathbb\{E\}\[r\(T;\\mathcal\{C\}\)\]⇔\\Leftrightarrowits induced gap lengths satisfygi∈\{q,q\+1\}g\_\{i\}\\in\\\{q,q\+1\\\}for allii, with exactlyρ\\rhogaps equal toq\+1q\+1\. In particular, any evenly spaced schedule such as

ci=⌊i​\(N\+1\)M\+1⌋,i=1,…,M,c\_\{i\}=\\left\\lfloor\\frac\{i\(N\+1\)\}\{M\+1\}\\right\\rfloor,\\qquad i=1,\\dots,M,is optimal\.

⇒\\RightarrowBy Lemma[2](https://arxiv.org/html/2605.05219#Thmlemma2), minimizing𝔼​\[r​\(T;𝒞\)\]\\mathbb\{E\}\[r\(T;\\mathcal\{C\}\)\]is equivalent to minimizing

∑i=0Mϕ​\(gi\),ϕ​\(x\)=x​\(x−1\)2,\\sum\_\{i=0\}^\{M\}\\phi\(g\_\{i\}\),\\qquad\\phi\(x\)=\\frac\{x\(x\-1\)\}\{2\},over positive integersgig\_\{i\}summing toN\+1N\{\+\}1\. The functionϕ\\phiis strictly convex\.

Suppose there exist indicesi,ji,jwithgi≥gj\+2g\_\{i\}\\geq g\_\{j\}\{\+\}2\. Replacing\(gi,gj\)\(g\_\{i\},g\_\{j\}\)by\(gi−1,gj\+1\)\(g\_\{i\}\{\-\}1,g\_\{j\}\{\+\}1\)preserves the total sum and changes the objective by

ϕ​\(gi\)\+ϕ​\(gj\)−ϕ​\(gi−1\)−ϕ​\(gj\+1\)=gi−gj−1\>0\.\\phi\(g\_\{i\}\)\+\\phi\(g\_\{j\}\)\-\\phi\(g\_\{i\}\{\-\}1\)\-\\phi\(g\_\{j\}\{\+\}1\)=g\_\{i\}\-g\_\{j\}\-1\>0\.Hence any feasible gap vector with two gaps differing by at least 2 can be strictly improved\. Therefore every optimum must have all gaps differing by at most one\.

⇐\\LeftarrowNow letK=M\+1K=M\+1and write

N\+1=q​K\+ρ,0≤ρ<K\.N\+1=qK\+\\rho,\\qquad 0\\leq\\rho<K\.The only positive integers summing toN\+1N\{\+\}1and differing pairwise by at most one are exactlyK−ρK\{\-\}\\rhocopies ofqqandρ\\rhocopies ofq\+1q\{\+\}1\. Conversely,ϕ\\phiis permutation\-invariant and every such gap multiset has the same objective value, so every such schedule is optimal\.

Finally,ci=⌊i​\(N\+1\)/\(M\+1\)⌋c\_\{i\}=\\lfloor i\(N\{\+\}1\)/\(M\{\+\}1\)\\rfloorinduces gaps differing by at most one, hence it is optimal\.

The exact optimal cost follows by substituting this gap multiset into Lemma[2](https://arxiv.org/html/2605.05219#Thmlemma2):

N​𝔼​\[r​\(T;𝒞⋆\)\]=\(K−ρ\)​q​\(q−1\)2\+ρ​\(q\+1\)​q2\.N\\,\\mathbb\{E\}\[r\(T;\\mathcal\{C\}^\{\\star\}\)\]=\(K\-\\rho\)\\frac\{q\(q\-1\)\}\{2\}\+\\rho\\frac\{\(q\+1\)q\}\{2\}\.Sinceq=⌊\(N\+1\)/\(M\+1\)⌋=N/\(M\+1\)\+O​\(1\)q=\\lfloor\(N\{\+\}1\)/\(M\{\+\}1\)\\rfloor=N/\(M\{\+\}1\)\+O\(1\), dividing byNNgives𝔼​\[r​\(T;𝒞⋆\)\]=N/\(2​\(M\+1\)\)\+O​\(1\)\\mathbb\{E\}\[r\(T;\\mathcal\{C\}^\{\\star\}\)\]=N/\(2\(M\{\+\}1\)\)\+O\(1\)asN→∞N\\to\\inftywithMMfixed\. ∎

###### Proof of Theorem[1](https://arxiv.org/html/2605.05219#Thmtheorem1)\.2\.

Let

R∞​\(𝒞\)=max1≤t≤N⁡r​\(t;𝒞\)\.R\_\{\\infty\}\(\\mathcal\{C\}\)=\\max\_\{1\\leq t\\leq N\}r\(t;\\mathcal\{C\}\)\.We will show that

min\|𝒞\|=M⁡R∞​\(𝒞\)=⌈N\+1M\+1⌉−1\.\\min\_\{\|\\mathcal\{C\}\|=M\}R\_\{\\infty\}\(\\mathcal\{C\}\)=\\left\\lceil\\frac\{N\+1\}\{M\+1\}\\right\\rceil\-1\.and balanced schedules reach the minima for everyMM\.

The maximum recomputation equals the largest gap minus one:R∞​\(𝒞\)=max0≤i≤M⁡\(gi−1\)R\_\{\\infty\}\(\\mathcal\{C\}\)=\\max\_\{0\\leq i\\leq M\}\(g\_\{i\}\-1\)\. Since theM\+1M\{\+\}1positive integersg0,…,gMg\_\{0\},\\dots,g\_\{M\}sum toN\+1N\{\+\}1, the pigeonhole principle gives

maxi⁡gi≥⌈N\+1M\+1⌉,\\max\_\{i\}g\_\{i\}\\geq\\left\\lceil\\frac\{N\+1\}\{M\+1\}\\right\\rceil,and thereforeR∞​\(𝒞\)≥⌈\(N\+1\)/\(M\+1\)⌉−1R\_\{\\infty\}\(\\mathcal\{C\}\)\\geq\\lceil\(N\{\+\}1\)/\(M\{\+\}1\)\\rceil\-1\.

For the upper bound, take any balanced schedule from Theorem[1](https://arxiv.org/html/2605.05219#Thmtheorem1)\. All gaps are eitherqqorq\+1q\{\+\}1, soR∞​\(𝒞\)=⌈\(N\+1\)/\(M\+1\)⌉−1R\_\{\\infty\}\(\\mathcal\{C\}\)=\\lceil\(N\{\+\}1\)/\(M\{\+\}1\)\\rceil\-1, and the lower bound is attained\.

∎

### A\.2Histogram\-based oracle

###### Proof of Lemma[1](https://arxiv.org/html/2605.05219#Thmlemma1)\.

For any fixed checkpoint set𝒞\\mathcal\{C\},

\|𝔼p​\[r​\(T;𝒞\)\]−𝔼q​\[r​\(T;𝒞\)\]\|=\|∑t=1N\(pt−qt\)​r​\(t;𝒞\)\|≤∑t=1N\|pt−qt\|​r​\(t;𝒞\)≤N​‖p−q‖1,\\left\|\\mathbb\{E\}\_\{p\}\[r\(T;\\mathcal\{C\}\)\]\-\\mathbb\{E\}\_\{q\}\[r\(T;\\mathcal\{C\}\)\]\\right\|=\\left\|\\sum\_\{t=1\}^\{N\}\(p\_\{t\}\-q\_\{t\}\)\\,r\(t;\\mathcal\{C\}\)\\right\|\\leq\\sum\_\{t=1\}^\{N\}\|p\_\{t\}\-q\_\{t\}\|\\,r\(t;\\mathcal\{C\}\)\\leq N\\\|p\{\-\}q\\\|\_\{1\},since0≤r​\(t;𝒞\)≤N0\\leq r\(t;\\mathcal\{C\}\)\\leq Nfor everytt\. Optimizing over𝒞\\mathcal\{C\}on both sides and using a standard swap argument \(as in the proof of Theorem[3](https://arxiv.org/html/2605.05219#Thmtheorem3)below\) extends the bound to the value functionVMV\_\{M\}\. ∎

###### Proof of Theorem[3](https://arxiv.org/html/2605.05219#Thmtheorem3)\.

Let

Fn=‖p^\(n\)−p‖1\.F\_\{n\}=\\\|\\hat\{p\}^\{\(n\)\}\-p\\\|\_\{1\}\.By the Cauchy–Schwarz inequality,

Fn≤N​‖p^\(n\)−p‖2\.F\_\{n\}\\leq\\sqrt\{N\}\\,\\\|\\hat\{p\}^\{\(n\)\}\-p\\\|\_\{2\}\.Taking expectations and applying Jensen’s inequality,

𝔼​\[Fn\]≤N​𝔼​\[‖p^\(n\)−p‖22\]\.\\mathbb\{E\}\[F\_\{n\}\]\\leq\\sqrt\{N\\,\\mathbb\{E\}\\\!\\left\[\\\|\\hat\{p\}^\{\(n\)\}\-p\\\|\_\{2\}^\{2\}\\right\]\}\.Now

𝔼​\[‖p^\(n\)−p‖22\]=∑t=1NVar​\(p^t\(n\)\)=1n​∑t=1Npt​\(1−pt\)≤1n,\\mathbb\{E\}\\\!\\left\[\\\|\\hat\{p\}^\{\(n\)\}\-p\\\|\_\{2\}^\{2\}\\right\]=\\sum\_\{t=1\}^\{N\}\\mathrm\{Var\}\(\\hat\{p\}^\{\(n\)\}\_\{t\}\)=\\frac\{1\}\{n\}\\sum\_\{t=1\}^\{N\}p\_\{t\}\(1\-p\_\{t\}\)\\leq\\frac\{1\}\{n\},so

𝔼​\[Fn\]≤Nn\.\\mathbb\{E\}\[F\_\{n\}\]\\leq\\sqrt\{\\frac\{N\}\{n\}\}\.
Next, changing one sampleTiT\_\{i\}modifies the empirical histogram by moving mass1/n1/nfrom one coordinate to another, soFnF\_\{n\}changes by at most2/n2/n\. McDiarmid’s inequality therefore gives

Pr⁡\[Fn−𝔼​\[Fn\]≥ε\]≤exp⁡\(−n​ε22\)\.\\Pr\\\!\\left\[F\_\{n\}\-\\mathbb\{E\}\[F\_\{n\}\]\\geq\\varepsilon\\right\]\\leq\\exp\\\!\\left\(\-\\frac\{n\\varepsilon^\{2\}\}\{2\}\\right\)\.Settingε=2​log⁡\(1/δ\)/n\\varepsilon=\\sqrt\{2\\log\(1/\\delta\)/n\}yields, with probability at least1−δ1\-\\delta,

Fn≤Nn\+2​log⁡\(1/δ\)n\.F\_\{n\}\\leq\\sqrt\{\\frac\{N\}\{n\}\}\+\\sqrt\{\\frac\{2\\log\(1/\\delta\)\}\{n\}\}\.
For the plug\-in bound, let𝒞^n\\widehat\{\\mathcal\{C\}\}\_\{n\}be optimal underp^\(n\)\\hat\{p\}^\{\(n\)\}\. Then

𝔼p​\[r​\(T;𝒞^n\)\]−VM​\(p\)\\displaystyle\\mathbb\{E\}\_\{p\}\[r\(T;\\widehat\{\\mathcal\{C\}\}\_\{n\}\)\]\-V\_\{M\}\(p\)≤\|𝔼p​\[r​\(T;𝒞^n\)\]−𝔼p^\(n\)​\[r​\(T;𝒞^n\)\]\|\+\|VM​\(p^\(n\)\)−VM​\(p\)\|\\displaystyle\\leq\\bigl\|\\mathbb\{E\}\_\{p\}\[r\(T;\\widehat\{\\mathcal\{C\}\}\_\{n\}\)\]\-\\mathbb\{E\}\_\{\\hat\{p\}^\{\(n\)\}\}\[r\(T;\\widehat\{\\mathcal\{C\}\}\_\{n\}\)\]\\bigr\|\+\\bigl\|V\_\{M\}\(\\hat\{p\}^\{\(n\)\}\)\-V\_\{M\}\(p\)\\bigr\|≤N​Fn\+N​Fn=2​N​Fn,\\displaystyle\\leq NF\_\{n\}\+NF\_\{n\}=2NF\_\{n\},using Lemma[1](https://arxiv.org/html/2605.05219#Thmlemma1)for both terms\. ∎

### A\.3Tracking Under Drift

###### Proof of Theorem[4](https://arxiv.org/html/2605.05219#Thmtheorem4)\.

Write

wt,s=\(1−γ\)​γt−s1−γt,p^t\(γ\)=∑s=1twt,s​eTs,p¯t\(γ\)=𝔼​\[p^t\(γ\)\]=∑s=1twt,s​ps\.w\_\{t,s\}=\\frac\{\(1\-\\gamma\)\\gamma^\{t\-s\}\}\{1\-\\gamma^\{t\}\},\\qquad\\hat\{p\}\_\{t\}^\{\(\\gamma\)\}=\\sum\_\{s=1\}^\{t\}w\_\{t,s\}e\_\{T\_\{s\}\},\\qquad\\bar\{p\}\_\{t\}^\{\(\\gamma\)\}=\\mathbb\{E\}\[\\hat\{p\}\_\{t\}^\{\(\\gamma\)\}\]=\\sum\_\{s=1\}^\{t\}w\_\{t,s\}p\_\{s\}\.Then by the triangle inequality,

𝔼​\[‖p^t\(γ\)−pt‖1\]≤‖p¯t\(γ\)−pt‖1\+𝔼​\[‖p^t\(γ\)−p¯t\(γ\)‖1\]\.\\mathbb\{E\}\\\!\\left\[\\\|\\hat\{p\}\_\{t\}^\{\(\\gamma\)\}\-p\_\{t\}\\\|\_\{1\}\\right\]\\leq\\\|\\bar\{p\}\_\{t\}^\{\(\\gamma\)\}\-p\_\{t\}\\\|\_\{1\}\+\\mathbb\{E\}\\\!\\left\[\\\|\\hat\{p\}\_\{t\}^\{\(\\gamma\)\}\-\\bar\{p\}\_\{t\}^\{\(\\gamma\)\}\\\|\_\{1\}\\right\]\.The bias term is

‖p¯t\(γ\)−pt‖1=‖∑s=1twt,s​\(ps−pt\)‖1≤∑s=1twt,s​‖ps−pt‖1\.\\\|\\bar\{p\}\_\{t\}^\{\(\\gamma\)\}\-p\_\{t\}\\\|\_\{1\}=\\left\\\|\\sum\_\{s=1\}^\{t\}w\_\{t,s\}\(p\_\{s\}\-p\_\{t\}\)\\right\\\|\_\{1\}\\leq\\sum\_\{s=1\}^\{t\}w\_\{t,s\}\\\|p\_\{s\}\-p\_\{t\}\\\|\_\{1\}\.
For the stochastic term, Jensen and Cauchy–Schwarz give

𝔼​\[‖p^t\(γ\)−p¯t\(γ\)‖1\]≤N​𝔼​\[‖p^t\(γ\)−p¯t\(γ\)‖22\]\.\\mathbb\{E\}\\\!\\left\[\\\|\\hat\{p\}\_\{t\}^\{\(\\gamma\)\}\-\\bar\{p\}\_\{t\}^\{\(\\gamma\)\}\\\|\_\{1\}\\right\]\\leq\\sqrt\{N\\,\\mathbb\{E\}\\\!\\left\[\\\|\\hat\{p\}\_\{t\}^\{\(\\gamma\)\}\-\\bar\{p\}\_\{t\}^\{\(\\gamma\)\}\\\|\_\{2\}^\{2\}\\right\]\}\.Because the samples are independent and centered cross\-terms vanish,

𝔼​\[‖p^t\(γ\)−p¯t\(γ\)‖22\]=∑s=1twt,s2​𝔼​\[‖eTs−ps‖22\]\.\\mathbb\{E\}\\\!\\left\[\\\|\\hat\{p\}\_\{t\}^\{\(\\gamma\)\}\-\\bar\{p\}\_\{t\}^\{\(\\gamma\)\}\\\|\_\{2\}^\{2\}\\right\]=\\sum\_\{s=1\}^\{t\}w\_\{t,s\}^\{2\}\\,\\mathbb\{E\}\\\!\\left\[\\\|e\_\{T\_\{s\}\}\-p\_\{s\}\\\|\_\{2\}^\{2\}\\right\]\.Now

𝔼​\[‖eTs−ps‖22\]=1−‖ps‖22≤1,\\mathbb\{E\}\\\!\\left\[\\\|e\_\{T\_\{s\}\}\-p\_\{s\}\\\|\_\{2\}^\{2\}\\right\]=1\-\\\|p\_\{s\}\\\|\_\{2\}^\{2\}\\leq 1,so

𝔼​\[‖p^t\(γ\)−p¯t\(γ\)‖22\]≤∑s=1twt,s2\.\\mathbb\{E\}\\\!\\left\[\\\|\\hat\{p\}\_\{t\}^\{\(\\gamma\)\}\-\\bar\{p\}\_\{t\}^\{\(\\gamma\)\}\\\|\_\{2\}^\{2\}\\right\]\\leq\\sum\_\{s=1\}^\{t\}w\_\{t,s\}^\{2\}\.Finally,

∑s=1twt,s2=\(1−γ\)2\(1−γt\)2​∑k=0t−1γ2​k=\(1−γ\)2\(1−γt\)2⋅1−γ2​t1−γ2=1−γ1\+γ⋅1\+γt1−γt\.\\sum\_\{s=1\}^\{t\}w\_\{t,s\}^\{2\}=\\frac\{\(1\-\\gamma\)^\{2\}\}\{\(1\-\\gamma^\{t\}\)^\{2\}\}\\sum\_\{k=0\}^\{t\-1\}\\gamma^\{2k\}=\\frac\{\(1\-\\gamma\)^\{2\}\}\{\(1\-\\gamma^\{t\}\)^\{2\}\}\\cdot\\frac\{1\-\\gamma^\{2t\}\}\{1\-\\gamma^\{2\}\}=\\frac\{1\-\\gamma\}\{1\+\\gamma\}\\cdot\\frac\{1\+\\gamma^\{t\}\}\{1\-\\gamma^\{t\}\}\.Combining the bias and variance bounds proves the claim\. ∎

### A\.4Proof of Theorem[2](https://arxiv.org/html/2605.05219#Thmtheorem2)

###### Proof\.

The recurrence follows from the cost decomposition in Section[4](https://arxiv.org/html/2605.05219#S4)\. For theO​\(N​M\)O\(NM\)complexity, writew​\(s,j\)=\(Tj−Ts−1\)−s​\(Pj−Ps−1\)w\(s,j\)=\(T\_\{j\}\-T\_\{s\-1\}\)\-s\(P\_\{j\}\-P\_\{s\-1\}\)\. Then

dp​\[m,j\]=Tj\+min1≤s≤j⁡\(dp​\[m−1,s−1\]−Ts−1\+s​Ps−1−s​Pj\)\.\\mathrm\{dp\}\[m,j\]=T\_\{j\}\+\\min\_\{1\\leq s\\leq j\}\\bigl\(\\mathrm\{dp\}\[m\{\-\}1,s\{\-\}1\]\-T\_\{s\-1\}\+sP\_\{s\-1\}\-sP\_\{j\}\\bigr\)\.For fixedmm, each candidatesscontributes a liney=\(−s\)​x\+\(dp​\[m−1,s−1\]−Ts−1\+s​Ps−1\)y=\(\-s\)x\+\(\\mathrm\{dp\}\[m\{\-\}1,s\{\-\}1\]\-T\_\{s\-1\}\+sP\_\{s\-1\}\)evaluated at query pointx=Pjx=P\_\{j\}\. The slopes−s\-sare strictly decreasing inss, and the query pointsPjP\_\{j\}are non\-decreasing injj\(sincept≥0p\_\{t\}\\geq 0\)\. A monotone convex hull trick therefore evaluates each layer inO​\(N\)O\(N\)amortized time, givingO​\(N​M\)O\(NM\)total\.

*Note:*if somept=0p\_\{t\}=0, consecutive query points may coincide, but the monotone\-pointer technique handles ties without affecting the amortized bound\. ∎

## Appendix BAdditional Figures

![Refer to caption](https://arxiv.org/html/2605.05219v1/x5.png)Figure 5:Checkpoint placements for sampled conversations \(a\) QuALITY, \(b\) System Prompts