Thought-Aware KV Cache Compaction for Reasoning via Adaptive Attention Matching

# Thought-Aware KV Cache Compaction for Reasoning via Adaptive Attention Matching
Source: [https://arxiv.org/html/2608.12331](https://arxiv.org/html/2608.12331)
Yang Liu1, Bin Chong2, Chongyang Zhang3, Hao Zheng3, Jiayu Liang4, Xu Kefu2 1Tsinghua University2Peking University3Fullive\.AI4Soochow University

###### Abstract

Reasoning language models generate lengthy chain\-of\-thought \(CoT\) sequences whose key\-value \(KV\) cache grows linearly and becomes a memory bottleneck during decoding\. Existing compaction methods treat reasoning trajectories as flat token sequences and apply uniform compression, ignoring the hierarchical structure of CoT reasoning where different steps vary drastically in importance\. We proposeThought\-Aware Attention Matching \(TAM\), which exploits this structure through three mechanisms: \(i\) thought segmentation that decomposes the trajectory into reasoning blocks, \(ii\) adaptive budget allocation that assigns compression budget based on each segment’s importance and size, and \(iii\) pivotal token protection that preserves high\-attention reasoning anchors\. We prove that the allocation rule is optimal under a convex error model and that cumulative error under sequential compaction remains bounded\. Experiments on AIME 2024 and MATH\-500 with Qwen3\-4B show that TAM improves accuracy over uniform compaction at the same memory footprint, with periodic compaction bounding peak memory to 3\.1–3\.2 GB \(a 65% reduction\) while maintaining competitive accuracy\.

Thought\-Aware KV Cache Compaction for Reasoning via Adaptive Attention Matching

Yang Liu1, Bin Chong2††thanks:Corresponding author\., Chongyang Zhang3, Hao Zheng3, Jiayu Liang4, Xu Kefu21Tsinghua University2Peking University3Fullive\.AI4Soochow University

## 1Introduction

Memory has emerged as a critical bottleneck in modern language models deployed for long\-horizon tasks\. Reasoning\-capable models produce lengthy chain\-of\-thought \(CoT\) sequences\(Weiet al\.,[2022](https://arxiv.org/html/2608.12331#bib.bib9)\)before final answers, and the key\-value \(KV\) cache that stores attention states for all previous tokens grows linearly with sequence length\(Zhanget al\.,[2023](https://arxiv.org/html/2608.12331#bib.bib4)\)\. This growth substantially increases memory footprint and reduces decoding throughput\(Daoet al\.,[2022](https://arxiv.org/html/2608.12331#bib.bib14)\), limiting the practical deployment of reasoning models on resource\-constrained devices\. While existing KV cache compression methods\(Zhanget al\.,[2023](https://arxiv.org/html/2608.12331#bib.bib4); Liet al\.,[2024](https://arxiv.org/html/2608.12331#bib.bib5)\)primarily target long input prompts at prefill time, the efficient compaction of*generated*tokens during decoding, i\.e\. mid\-trajectory compaction, remains underexplored despite its importance for reasoning workloads that routinely produce long chains of intermediate tokens\.

Recent work has made progress along complementary directions\. Attention Matching \(AM\)\(Zweigeret al\.,[2026](https://arxiv.org/html/2608.12331#bib.bib1)\)achieves large one\-shot compaction by constructing compact keys and values that reproduce attention outputs and preserve attention mass, using closed\-form solutions that avoid gradient descent\. However, AM targets prefill scenarios and assumes reference queries from self\-study on a fixed context\. Reasoning Path Compression \(RPC\)\(Songet al\.,[2025](https://arxiv.org/html/2608.12331#bib.bib3)\)addresses mid\-trajectory compression by periodically evicting tokens based on a selector window of recent queries\. Yet RPC relies on simple eviction, which, as we show formally, systematically underestimates attention mass at high compression ratios\. Both approaches treat the reasoning trajectory as a flat token sequence and apply uniform compression, ignoring the hierarchical structure of CoT reasoning\. While prior methods vary along two axes—the compaction primitive \(eviction vs\. optimization\) and the query source \(self\-study vs\. selector window\)—neither exploits a third, orthogonal axis: structure\-aware budget allocation\.

CoT trajectories\(Kojimaet al\.,[2022](https://arxiv.org/html/2608.12331#bib.bib19)\)naturally decompose into distinct reasoning steps—problem restatements, intermediate calculations, exploratory dead ends, and conclusions—whose importance to future generation varies dramatically\. Dead\-end explorations become irrelevant as reasoning progresses, while key intermediate results and problem definitions remain critical throughout\. This heterogeneity motivates non\-uniform budget allocation: by assigning more compression budget to important reasoning steps and less to irrelevant ones, we can preserve the tokens that matter most while aggressively compressing the rest\.

We proposeThought\-Aware Attention Matching \(TAM\), which realizes this idea through three mechanisms: \(i\) thought segmentation that decomposes the reasoning trajectory into coherent blocks, \(ii\) adaptive budget allocation that distributes compact keys based on each segment’s importance and size, and \(iii\) pivotal token protection that preserves high\-attention reasoning anchors\. These mechanisms operate on top of the AM optimization pipeline and a selector window for lightweight query generation, transforming uniform compaction into a structure\-aware scheme\.

We make three contributions:

1. 1\.We introduce TAM, a structure\-aware mid\-trajectory KV cache compaction method that segments reasoning trajectories into thought blocks, allocates compression budget adaptively based on each segment’s importance and size, and protects critical reasoning anchors via pivotal token identification\.
2. 2\.We provide theoretical foundations: the allocationti∝wi⋅nit\_\{i\}\\propto\\sqrt\{w\_\{i\}\\cdot n\_\{i\}\}is optimal under convex error models \(Proposition[C\.1](https://arxiv.org/html/2608.12331#A3.Thmtheorem1)\), pivotal protection reduces approximation error \(Proposition[C\.2](https://arxiv.org/html/2608.12331#A3.Thmtheorem2)\), and cumulative error under sequential compaction remains bounded \(Proposition[C\.4](https://arxiv.org/html/2608.12331#A3.Thmtheorem4)\)\.
3. 3\.We evaluate TAM on AIME 2024 and MATH\-500 with Qwen3\-4B, demonstrating consistent accuracy improvements over uniform compaction at the same memory budget, with periodic compaction achieving up to 65% peak\-memory reduction\.

## 2Related Work

#### KV cache eviction and merging\.

KV cache compression has been studied extensively for long\-context inference\(Xiaoet al\.,[2023](https://arxiv.org/html/2608.12331#bib.bib11); Baiet al\.,[2024](https://arxiv.org/html/2608.12331#bib.bib15); Liuet al\.,[2024](https://arxiv.org/html/2608.12331#bib.bib16); Dinget al\.,[2023](https://arxiv.org/html/2608.12331#bib.bib20)\)\. H2O\(Zhanget al\.,[2023](https://arxiv.org/html/2608.12331#bib.bib4)\)retains tokens with the highest accumulated attention under a sliding window; SnapKV\(Liet al\.,[2024](https://arxiv.org/html/2608.12331#bib.bib5)\)selects important KV positions by observing attention patterns within an observation window\. These methods target long input prompts at prefill time and are not designed for dynamically growing context during decoding\. All eviction\-based methods apply uniform retention policies, treating every token position equivalently\.

#### Latent\-space compaction\.

Cartridges\(Eyubogluet al\.,[2025](https://arxiv.org/html/2608.12331#bib.bib2)\)train compact KV caches offline via prefix\-tuning at the cost of GPU\-hours per context\. Attention Matching \(AM\)\(Zweigeret al\.,[2026](https://arxiv.org/html/2608.12331#bib.bib1)\)decomposes the compaction problem into closed\-form subproblems \(OMP for key selection, NNLS for biases, OLS for value fitting\), matching Cartridges quality at far lower cost but assuming one\-shot compaction at prefill time\. Both methods apply uniform compression across all tokens\.

#### Mid\-trajectory compression for reasoning\.

Reasoning Path Compression \(RPC\)\(Songet al\.,[2025](https://arxiv.org/html/2608.12331#bib.bib3)\)addresses mid\-trajectory compression by periodically evicting tokens based on a selector window of recent queries\. While RPC identifies the selector window as a lightweight proxy for future queries, it relies on eviction rather than latent\-space optimization and applies a uniform retention threshold across the entire prefix\. TAM operates along an orthogonal axis: it allocates compression budget non\-uniformly across reasoning segments based on their importance, a design dimension independent of the compaction primitive or query source\.

## 3Preliminaries

### 3\.1Attention and KV Cache

In the Transformer architecture\(Vaswaniet al\.,[2017](https://arxiv.org/html/2608.12331#bib.bib6)\), each layer computes attention over queries𝐐∈ℝn×d\\mathbf\{Q\}\\in\\mathbb\{R\}^\{n\\times d\}, keys𝐊∈ℝT×d\\mathbf\{K\}\\in\\mathbb\{R\}^\{T\\times d\}, and values𝐕∈ℝT×d\\mathbf\{V\}\\in\\mathbb\{R\}^\{T\\times d\}\. The scaled dot\-product attention is

Attn​\(𝐐,𝐊,𝐕\)=softmax​\(𝐐𝐊⊤d\)​𝐕,\\text\{Attn\}\(\\mathbf\{Q\},\\mathbf\{K\},\\mathbf\{V\}\)=\\text\{softmax\}\\left\(\\frac\{\\mathbf\{Q\}\\mathbf\{K\}^\{\\top\}\}\{\\sqrt\{d\}\}\\right\)\\mathbf\{V\},\(1\)where the softmax is applied row\-wise\. For autoregressive generation, the model caches keys and values for allTTcontext tokens, appending new KV pairs as each token is generated\. The KV cache thus grows linearly with sequence length, becoming a memory bottleneck for long reasoning trajectories\(Daoet al\.,[2022](https://arxiv.org/html/2608.12331#bib.bib14)\)\.

A key insight for compaction is that attention over concatenated KV blocks decomposes into a mixture of each block’s locally normalized output, weighted by that block’s attention mass\. For a key block𝐊\\mathbf\{K\}, define the*attention mass*as

Mass​\(𝐪;𝐊\)=∑j=1Texp⁡\(𝐪𝐊j⊤d\)\.\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{K\}\)=\\sum\_\{j=1\}^\{T\}\\exp\\left\(\\frac\{\\mathbf\{q\}\\mathbf\{K\}\_\{j\}^\{\\top\}\}\{\\sqrt\{d\}\}\\right\)\.\(2\)Matching both the local attention output and the attention mass of a compacted block suffices to preserve its contribution when concatenated with arbitrary future tokens\(Zweigeret al\.,[2026](https://arxiv.org/html/2608.12331#bib.bib1)\)\.

### 3\.2Attention Matching \(AM\)

Attention Matching\(Zweigeret al\.,[2026](https://arxiv.org/html/2608.12331#bib.bib1)\)replaces the original cache\(𝐊,𝐕\)\(\\mathbf\{K\},\\mathbf\{V\}\)with𝐊,𝐕∈ℝT×d\\mathbf\{K\},\\mathbf\{V\}\\in\\mathbb\{R\}^\{T\\times d\}by a compact representation\(𝐂k,𝜷,𝐂v\)\(\\mathbf\{C\}\_\{k\},\\bm\{\\beta\},\\mathbf\{C\}\_\{v\}\)where𝐂k,𝐂v∈ℝt×d\\mathbf\{C\}\_\{k\},\\mathbf\{C\}\_\{v\}\\in\\mathbb\{R\}^\{t\\times d\}witht≪Tt\\ll T, and𝜷∈ℝt\\bm\{\\beta\}\\in\\mathbb\{R\}^\{t\}is a per\-token scalar bias\. The compact cache should satisfy, for reference queries𝐪i\\mathbf\{q\}\_\{i\}of interest,

exp⁡\(𝐪i​𝐊⊤/d\)​𝐕∑jexp⁡\(𝐪i​𝐊j⊤/d\)≈exp⁡\(𝐪i​𝐂k⊤/d\+𝜷\)∑jexp⁡\(𝐪i​\(𝐂k\)j⊤/d\+βj\)​𝐂v,\\frac\{\\exp\(\\mathbf\{q\}\_\{i\}\\mathbf\{K\}^\{\\top\}/\\sqrt\{d\}\)\\mathbf\{V\}\}\{\\sum\_\{j\}\\exp\(\\mathbf\{q\}\_\{i\}\\mathbf\{K\}\_\{j\}^\{\\top\}/\\sqrt\{d\}\)\}\\approx\\frac\{\\exp\(\\mathbf\{q\}\_\{i\}\\mathbf\{C\}\_\{k\}^\{\\top\}/\\sqrt\{d\}\+\\bm\{\\beta\}\)\}\{\\sum\_\{j\}\\exp\(\\mathbf\{q\}\_\{i\}\(\\mathbf\{C\}\_\{k\}\)\_\{j\}^\{\\top\}/\\sqrt\{d\}\+\\beta\_\{j\}\)\}\\mathbf\{C\}\_\{v\},\(3\)∑j=1Texp⁡\(𝐪i​𝐊j⊤/d\)≈∑j=1texp⁡\(𝐪i​\(𝐂k\)j⊤/d\+βj\)\.\\sum\_\{j=1\}^\{T\}\\exp\(\\mathbf\{q\}\_\{i\}\\mathbf\{K\}\_\{j\}^\{\\top\}/\\sqrt\{d\}\)\\approx\\sum\_\{j=1\}^\{t\}\\exp\(\\mathbf\{q\}\_\{i\}\(\\mathbf\{C\}\_\{k\}\)\_\{j\}^\{\\top\}/\\sqrt\{d\}\+\\beta\_\{j\}\)\.\(4\)The first condition matches the local attention output; the second matches the attention mass\. With the substitutionuj=exp⁡\(βj\)≥0u\_\{j\}=\\exp\(\\beta\_\{j\}\)\\geq 0, the mass condition becomes a nonnegative least squares problem over𝐮\\mathbf\{u\}, solved via NNLS\(lawson1995solving\)\. Given𝐂k\\mathbf\{C\}\_\{k\}and𝜷\\bm\{\\beta\}, the value matrix𝐂v\\mathbf\{C\}\_\{v\}is fitted via ordinary least squares\. Key selection is performed via orthogonal matching pursuit\(Tropp and Gilbert,[2007](https://arxiv.org/html/2608.12331#bib.bib7)\)\(which greedily selects keys to minimize mass residual\) or by retaining keys with highest aggregate attention under the reference queries\. In prefill AM, reference queries are obtained from self\-study or repeat\-prefill on the fixed context\.

## 4Thought\-Aware Attention Matching \(TAM\)

### 4\.1Overview

TAM transforms uniform compaction into a structure\-aware scheme through three mechanisms operating on top of the AM optimization pipeline: \(i\) thought segmentation, \(ii\) adaptive budget allocation, and \(iii\) pivotal token protection\. Section[4\.8](https://arxiv.org/html/2608.12331#S4.SS8)provides theoretical justification for the allocation strategy; Figure[1](https://arxiv.org/html/2608.12331#S4.F1)illustrates the full pipeline\.

![Refer to caption](https://arxiv.org/html/2608.12331v1/imgs/tam_framework.png)Figure 1:Overview of the TAM pipeline\.
### 4\.2Selector Window Query Generation

Let the current sequence length beLL, comprising the prompt and all reasoning tokens generated so far\. Theselector windowcomprises the lastRRtokens\. We extract query vectors𝐐ref∈ℝR×d\\mathbf\{Q\}\_\{\\text\{ref\}\}\\in\\mathbb\{R\}^\{R\\times d\}from these positions by running a single forward pass with hooks to capture query activations\. This yields per\-layer, per\-head reference queries; TAM processes each KV\-head independently using its corresponding𝐐ref\\mathbf\{Q\}\_\{\\text\{ref\}\}\. These queries encode the current reasoning frontier and serve as a lightweight proxy for future query distributions without requiring self\-study or repeat\-prefill\(Songet al\.,[2025](https://arxiv.org/html/2608.12331#bib.bib3)\)\.

### 4\.3Thought Segmentation

TAM decomposes the compactable prefix into reasoning segments\{S1,S2,…,Sm\}\\\{S\_\{1\},S\_\{2\},\\ldots,S\_\{m\}\\\}, where each segment corresponds to a coherent reasoning step\.

#### Heuristic segmentation\.

Chain\-of\-thought outputs exhibit clear structural patterns that delineate reasoning boundaries, most prominently paragraph breaks \(double newlines\)\. Reasoning models are trained to organize their output into coherent steps separated by such structural markers, so these boundaries reliably correspond to semantic transitions\. We detect double\-newline boundaries in the decoded token text using a lightweight rule\-based scanner that runs inO​\(L\)O\(L\)time\. Consecutive short segments \(fewer thanℓmin\\ell\_\{\\min\}tokens\) are merged to avoid over\-fragmentation\.

#### Attention\-based segmentation \(alternative\)\.

We also evaluate an attention\-based approach that detects boundaries from shifts in attention intensity\. For each positionjj, we compute the mean attentionα¯j\\bar\{\\alpha\}\_\{j\}it receives from the selector window \(defined formally in Eq\.[7](https://arxiv.org/html/2608.12331#S4.E7)\)\. We then measure the local gradientΔj=\|α¯j−α¯j−1\|\\Delta\_\{j\}=\|\\bar\{\\alpha\}\_\{j\}\-\\bar\{\\alpha\}\_\{j\-1\}\|and place boundaries at positions whereΔj\\Delta\_\{j\}exceeds2×2\\timesthe median gradient\. This detects transitions between high\-attention and low\-attention regions, which empirically correspond to reasoning step boundaries\. We compare both approaches in Section[5\.4](https://arxiv.org/html/2608.12331#S5.SS4)\.

Table 1:Main results at target compaction ratio 0\.1 \(retain 10% of KV entries\)\. “Mem” is post\-compaction steady\-state GPU memory \(see Section[5\.1](https://arxiv.org/html/2608.12331#S5.SS1)\); for one\-shot methods \(P=∞P\{=\}\\infty\), peak memory during generation equals No Compaction\. Only TAM \(Periodic\) maintains bounded memory throughout\. Best accuracy inbold; best memory inunderline\.MethodAIME 2024\(30 prob\.\)MATH\-500Acc \(%\)Mem \(GB\)Acc \(%\)Mem \(GB\)No Compaction63\.39\.271\.28\.8Eviction \(Selector Window\)46\.74\.152\.43\.9AM \+ Repeat53\.34\.261\.04\.0PAM \(Uniform\)56\.74\.064\.63\.8TAM \(Ours\)60\.04\.067\.83\.8TAM \(Periodic,P=1024P\{=\}1024\)56\.73\.265\.43\.1

Table 2:TAM compaction time breakdown per step \(Qwen3\-4B,∼\\sim4k tokens\)\. TAM\-specific stages are marked with†\\dagger\.StageTime \(s\)Query extract \(selector window\)0\.8Thought segmentation \+ importance†0\.1Pivotal token identification†<<0\.1Per\-segment key selection2\.5β\\betafitting \(NNLS, global\)1\.2Value fitting \(OLS, global\)0\.9Total5\.6*of which TAM\-specific**∼\\sim0\.15*

0\.050\.100\.203030404050506060No CompactionTarget ratio \(fraction retained\)Accuracy \(%\)EvictionAM\+RepeatPAM \(Uniform\)TAM \(Ours\)TAM \(Periodic\)\(a\)Accuracy vs\. compaction ratio \(AIME 2024\)\.224466883030404050506060Post\-compaction Memory \(GB\)Accuracy \(%\)No CompactionEvictionAM\+RepeatPAM \(Uniform\)TAM \(Ours\)TAM \(Periodic\)\(b\)Accuracy vs\. post\-compaction memory \(AIME 2024\)\.
Figure 2:Accuracy vs\. compaction trade\-offs on AIME 2024 \(Qwen3\-4B\)\. Left: accuracy vs\. compaction ratio\. Right: accuracy vs\. post\-compaction memory\. TAM consistently outperforms all baselines; TAM \(Periodic\) achieves the best memory vs\. accuracy trade\-off\.0\.050\.100\.2040406060No CompactionTarget ratio \(fraction retained\)Accuracy \(%\)EvictionAM\+RepeatPAM \(Uniform\)TAM \(Ours\)TAM \(Periodic\)\(a\)Accuracy vs\. compaction ratio \(MATH\-500\)\.2244668840406060Post\-compaction Memory \(GB\)Accuracy \(%\)No CompactionEvictionAM\+RepeatPAM \(Uniform\)TAM \(Ours\)TAM \(Periodic\)\(b\)Accuracy vs\. post\-compaction memory \(MATH\-500\)\.
Figure 3:Accuracy vs\. compaction trade\-offs on MATH\-500 \(Qwen3\-4B, 500 problems\)\. Left: accuracy vs\. compaction ratio\. Right: accuracy vs\. post\-compaction memory\. With larger sample size, TAM’s advantage over PAM is more clearly separated\. TAM achieves near\-full\-accuracy recovery at ratio 0\.2 \(70\.2% vs\. 71\.2%\)\.Table 3:Component ablation at target ratio 0\.1\.ConfigurationAIME 2024MATH\-500Acc \(%\)Δ\\DeltaAcc \(%\)Δ\\DeltaPAM \(Uniform\)56\.7064\.60\+ Adaptive allocation56\.7\+0\.066\.4\+1\.8\+ Pivotal protection56\.7\+0\.066\.2\+1\.6\+ Both \(TAM\)60\.0\+3\.367\.8\+3\.2

Table 4:Ablation Study \(TAM, target ratio 0\.1, AIME 2024\)\.Segmentation MethodAcc \(%\)Seg\. Time \(ms\)Heuristic \(double\-newline\)60\.02Attention\-based \(gradient jump\)60\.045Fixed\-length \(ℓ=256\\ell\{=\}256\)56\.71

Table 5:Ablation on pivotal threshold multipliercc\(TAM, target ratio 0\.1, AIME 2024\)\.Thresholdcc\|𝒫\|\|\\mathcal\{P\}\|\(avg\)Acc \(%\)131256\.73\(default\)8760\.053460\.010856\.7
Table 6:Ablation on compaction intervalPP\(TAM, target ratio 0\.1, AIME 2024\)\.IntervalPPAcc \(%\)Peak Mem \(GB\)∞\\infty\(max only\)60\.04\.01024\(default\)56\.73\.251256\.73\.025653\.32\.8

### 4\.4Segment Importance Scoring and Adaptive Budget Allocation

Given segments\{S1,…,Sm\}\\\{S\_\{1\},\\ldots,S\_\{m\}\\\}with sizesn1,…,nmn\_\{1\},\\ldots,n\_\{m\}and selector window queries𝐐ref\\mathbf\{Q\}\_\{\\text\{ref\}\}, we compute the*importance*of each segment as the average attention mass it receives from the current reasoning frontier:

wi=1\|𝐐ref\|​∑𝐪∈𝐐ref∑j∈Siαj​\(𝐪\),w\_\{i\}=\\frac\{1\}\{\|\\mathbf\{Q\}\_\{\\text\{ref\}\}\|\}\\sum\_\{\\mathbf\{q\}\\in\\mathbf\{Q\}\_\{\\text\{ref\}\}\}\\sum\_\{j\\in S\_\{i\}\}\\alpha\_\{j\}\(\\mathbf\{q\}\),\(5\)whereαj​\(𝐪\)\\alpha\_\{j\}\(\\mathbf\{q\}\)is the softmax attention weight of tokenjjunder query𝐪\\mathbf\{q\}\(normalized over the full prefix including the protected tail\)\. Since the sum only covers compactable positions,∑iwi≤1\\sum\_\{i\}w\_\{i\}\\leq 1; the residual is the tail’s attention mass, which is typically small\.

#### Optimal budget allocation\.

Let𝒫\\mathcal\{P\}denote the set of pivotal tokens \(Section[4\.5](https://arxiv.org/html/2608.12331#S4.SS5)\) andt′=t−\|𝒫\|t^\{\\prime\}=t\-\|\\mathcal\{P\}\|the remaining budget after reserving their slots\. We allocatetit\_\{i\}compact keys to segmentSiS\_\{i\}according to:

ti=max⁡\(1,⌊t′⋅wi⋅ni∑j=1mwj⋅nj⌋\)\.t\_\{i\}=\\max\\\!\\left\(1,\\;\\left\\lfloor t^\{\\prime\}\\cdot\\frac\{\\sqrt\{w\_\{i\}\\cdot n\_\{i\}\}\}\{\\sum\_\{j=1\}^\{m\}\\sqrt\{w\_\{j\}\\cdot n\_\{j\}\}\}\\right\\rfloor\\right\)\.\(6\)Any residual budget from rounding is assigned to the segment with the largest fractional remainder\. This allocation has a principled justification: in Proposition[C\.1](https://arxiv.org/html/2608.12331#A3.Thmtheorem1), we prove that when the per\-segment approximation error is a convex function of the local compression rationi/tin\_\{i\}/t\_\{i\}, the importance\-weighted allocationti∝wi⋅nit\_\{i\}\\propto\\sqrt\{w\_\{i\}\\cdot n\_\{i\}\}minimizes the total weighted approximation error under a linear error model\. The allocation naturally concentrates budget on segments that are both large and important, while assigning minimal budget to irrelevant segments\.

Standard AM and its uniform variant with selector window queries \(PAM, for Prefix Attention Matching\) useti∝nit\_\{i\}\\propto n\_\{i\}, which wastes budget on low\-importance segments\. Pure attention\-based allocationti∝wit\_\{i\}\\propto w\_\{i\}ignores segment size, potentially under\-representing large segments\. TAM’swi⋅ni\\sqrt\{w\_\{i\}\\cdot n\_\{i\}\}allocation balances both factors optimally\.

### 4\.5Pivotal Token Protection

Beyond the fixed tail protection of the lastτ\\tautokens, TAM identifies and protects*pivotal tokens*: positions that receive consistently high attention from the selector window, indicating their role as reasoning anchors \(e\.g\., problem constants, key intermediate results, critical definitions\)\.

For each tokenjjin the compactable prefix, we compute its average attention score:

α¯j=1\|𝐐ref\|​∑𝐪∈𝐐refαj​\(𝐪\)\.\\bar\{\\alpha\}\_\{j\}=\\frac\{1\}\{\|\\mathbf\{Q\}\_\{\\text\{ref\}\}\|\}\\sum\_\{\\mathbf\{q\}\\in\\mathbf\{Q\}\_\{\\text\{ref\}\}\}\\alpha\_\{j\}\(\\mathbf\{q\}\)\.\(7\)A token is pivotal ifα¯j\>δ\\bar\{\\alpha\}\_\{j\}\>\\delta, where we setδ=c⋅α¯mean\\delta=c\\cdot\\bar\{\\alpha\}\_\{\\text\{mean\}\}withc=3c=3by default, selecting tokens whose attention significantly exceeds the mean\. The pivotal set𝒫\\mathcal\{P\}is constructed by collecting all such tokens; their keys and values are directly retained in the compact cache without modification\. The remaining budgett′=t−\|𝒫\|t^\{\\prime\}=t\-\|\\mathcal\{P\}\|is distributed across segments via Eq\.[6](https://arxiv.org/html/2608.12331#S4.E6), and key selection within each segment operates only on non\-pivotal tokens\.

In Proposition[C\.2](https://arxiv.org/html/2608.12331#A3.Thmtheorem2), we show that pivotal protection reduces the worst\-case approximation error by a factor proportional to the total attention mass of pivotal tokens\.

### 4\.6Periodic Compaction Trigger

Compaction is triggered when the cache reaches the maximum sequence length orPPnew tokens have been generated since the last compaction\. At each trigger, TAM re\-runs the full pipeline on the current cache: segment boundaries are recomputed from scratch on the updated token sequence, importance scores are recalculated using a fresh selector window, and pivotal tokens are re\-identified\. Previously protected pivotal tokens receive no special treatment in subsequent rounds—they compete for retention based on their current attention scores\. The target sizettremains fixed across rounds, so the cache oscillates betweenttandt\+Pt\+Ptokens\. The parameterPPtrades off peak memory against compaction overhead: smallerPPcompacts more frequently, keeping memory bounded at the cost of higher compute; largerPPamortizes overhead but allows higher peak memory\. Proposition[C\.4](https://arxiv.org/html/2608.12331#A3.Thmtheorem4)quantifies howPPcontrols cumulative error\.

### 4\.7Algorithm

Algorithm[1](https://arxiv.org/html/2608.12331#algorithm1)summarizes one TAM compaction step\. After protecting the lastτ\\tautokens and extracting𝐐ref\\mathbf\{Q\}\_\{\\text\{ref\}\}, TAM segments the compactable prefix, identifies pivotal tokens, allocates per\-segment budgets, and runs key selection within each segment\. While key selection is per\-segment, the bias fitting \(NNLS\) and value fitting \(OLS\) are performed*globally*across all selected keys, ensuring that attention mass and outputs are matched at the full\-prefix level\. To guarantee exact retention of pivotal tokens \(as required by Proposition[C\.2](https://arxiv.org/html/2608.12331#A3.Thmtheorem2)\), we fixβj=0\\beta\_\{j\}=0for all pivotal keysj∈𝒫j\\in\\mathcal\{P\}, so their original logits are preserved unchanged; NNLS only optimizes biases for non\-pivotal selected keys\.

### 4\.8Theoretical Analysis

We provide principled justification for TAM’s design choices\. Proofs are deferred to Appendix[D](https://arxiv.org/html/2608.12331#A4)\.

###### Proposition 4\.1\(Mass Deficit of Eviction\)\.

Consider eviction\-based compaction that retains a subsetS⊂\[T\]S\\subset\[T\]with\|S\|=t<T\|S\|=t<Tkeys and values without scalar biases\. For any query𝐪\\mathbf\{q\}, define the*evicted mass fraction*

μ​\(𝐪\)=∑j∉Sexp⁡\(𝐪𝐊j⊤/d\)∑j=1Texp⁡\(𝐪𝐊j⊤/d\)=∑j∉Sαj​\(𝐪\),\\mu\(\\mathbf\{q\}\)=\\frac\{\\sum\_\{j\\notin S\}\\exp\(\\mathbf\{q\}\\mathbf\{K\}\_\{j\}^\{\\top\}/\\sqrt\{d\}\)\}\{\\sum\_\{j=1\}^\{T\}\\exp\(\\mathbf\{q\}\\mathbf\{K\}\_\{j\}^\{\\top\}/\\sqrt\{d\}\)\}=\\sum\_\{j\\notin S\}\\alpha\_\{j\}\(\\mathbf\{q\}\),\(8\)whereαj​\(𝐪\)\\alpha\_\{j\}\(\\mathbf\{q\}\)is the original attention weight of tokenjj\. Then:

1. 1\.Mass​\(𝐪;𝐂k\)=\(1−μ​\(𝐪\)\)⋅Mass​\(𝐪;𝐊\)<Mass​\(𝐪;𝐊\)\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{C\}\_\{k\}\)=\(1\-\\mu\(\\mathbf\{q\}\)\)\\cdot\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{K\}\)<\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{K\}\)for all𝐪\\mathbf\{q\}wheneverS≠\[T\]S\\neq\[T\]\.
2. 2\.When the compacted block is concatenated with future KV pairs\(𝐊f,𝐕f\)\(\\mathbf\{K\}\_\{f\},\\mathbf\{V\}\_\{f\}\), the compacted prefix’s contribution to the softmax denominator is deflated by factor\(1−μ​\(𝐪\)\)\(1\-\\mu\(\\mathbf\{q\}\)\), shifting attention toward\(𝐊f,𝐕f\)\(\\mathbf\{K\}\_\{f\},\\mathbf\{V\}\_\{f\}\)\.
3. 3\.Considering the prefix block in isolation, the attention output error satisfies‖𝐲^−𝐲‖≤2​μ​\(𝐪\)⋅‖𝐕‖∞\\\|\\hat\{\\mathbf\{y\}\}\-\\mathbf\{y\}\\\|\\leq 2\\mu\(\\mathbf\{q\}\)\\cdot\\\|\\mathbf\{V\}\\\|\_\{\\infty\}, where‖𝐕‖∞=maxj⁡‖𝐕j‖\\\|\\mathbf\{V\}\\\|\_\{\\infty\}=\\max\_\{j\}\\\|\\mathbf\{V\}\_\{j\}\\\|\.

Proposition[4\.1](https://arxiv.org/html/2608.12331#S4.Thmtheorem1)formalizes the fundamental limitation of eviction: the mass deficitμ​\(𝐪\)\\mu\(\\mathbf\{q\}\)equals the total attention weight of evicted tokens, which can be substantial even when each individual evicted token has low attention \(the “long tail” of small weights sums to a non\-negligible fraction\)\. TAM addresses this by fitting scalar biases𝜷\\bm\{\\beta\}via NNLS to preserve mass for the reference queries\.

## 5Experiments

We evaluate TAM on mathematical reasoning benchmarks, comparing against uniform compaction baselines and eviction methods\. We measure downstream accuracy, peak memory usage, and compaction time, and provide ablation studies on TAM’s key components\.

### 5\.1Experimental Setup

#### Benchmarks and model\.

We evaluate on two benchmarks: \(1\)AIME 2024\(Zhang and Math\-AI,[2024](https://arxiv.org/html/2608.12331#bib.bib13)\)\(AIME I and AIME II, 30 problems total\), which requires multi\-step mathematical reasoning and produces lengthy CoT trajectories \(median generation length≈\\approx4k tokens\); and \(2\)MATH\-500, a 500\-problem subset of the MATH test set\(Hendryckset al\.,[2021](https://arxiv.org/html/2608.12331#bib.bib8); Cobbeet al\.,[2021](https://arxiv.org/html/2608.12331#bib.bib17)\)spanning algebra, geometry, number theory, and combinatorics, providing larger\-scale evaluation with greater statistical power\. Each problem has a deterministic answer; we use Qwen3\-4B\(Yanget al\.,[2025](https://arxiv.org/html/2608.12331#bib.bib12)\)as the base model with greedy decoding \(temperature 0\) and a maximum generation length of 8192 tokens\. Accuracy is measured by exact match \(pass@1\)\(Chenet al\.,[2021](https://arxiv.org/html/2608.12331#bib.bib18)\)\.

#### Compared methods\.

We compare six configurations: \(1\)No Compaction: full KV cache \(accuracy upper bound\); \(2\)Eviction \(Selector Window\): retains high\-attention keys and evicts the rest\(Songet al\.,[2025](https://arxiv.org/html/2608.12331#bib.bib3)\); \(3\)AM \+ Repeat: one\-shot AM at max length with repeat\-prefill queries\(Zweigeret al\.,[2026](https://arxiv.org/html/2608.12331#bib.bib1)\); \(4\)PAM \(Uniform\): AM with selector window queries and uniform budget \(no segmentation or pivotal protection\), compacting once at max length \(P=∞P=\\infty\); \(5\)TAM \(Ours\): AM with selector window queries, segmentation, adaptive budget, and pivotal protection, compacting once at max length \(P=∞P=\\infty\); \(6\)TAM \(Periodic\): TAM with periodic triggers everyP=1024P=1024tokens for bounded peak memory\.

We note that H2O\(Zhanget al\.,[2023](https://arxiv.org/html/2608.12331#bib.bib4)\)and SnapKV\(Liet al\.,[2024](https://arxiv.org/html/2608.12331#bib.bib5)\)are prefill\-oriented eviction methods designed for long input contexts\. Our Eviction \(Selector Window\) baseline adapts their core mechanism—attention\-based token selection—to the mid\-trajectory setting, providing a representative comparison for eviction\-based approaches in the decoding scenario\.

#### Evaluation protocol\.

We sweep the target compaction ratio over\{0\.05,0\.1,0\.2\}\\\{0\.05,0\.1,0\.2\\\}\(retain 5%, 10%, or 20% of KV entries\)\. We protect the lastτ=20\\tau\{=\}20tokens, use a selector window ofR=64R\{=\}64tokens, and set the pivotal threshold multiplierc=3c\{=\}3\. Thought segmentation uses the heuristic \(double\-newline\) method by default withℓmin=32\\ell\_\{\\min\}\{=\}32\. Key selection uses the highest\-attention heuristic\. All experiments use a single NVIDIA A100 GPU \(80GB\)\. The model is loaded in 4\-bit quantization \(GPTQ\-Int4\), so model weights occupy≈\\approx2\.5 GB; the reported “Mem \(GB\)” is the*post\-compaction steady\-state memory*measured viatorch\.cuda\.max\_memory\_allocatedafter the first compaction step completes, averaged over all problems\. For one\-shot methods \(P=∞P\{=\}\\infty\), this reflects memory after the single compaction at max sequence length; the transient peak before compaction is comparable to No Compaction\. For TAM \(Periodic\), memory stays bounded throughout generation\.

### 5\.2Main Results

Table[2](https://arxiv.org/html/2608.12331#S4.T2)reports results at target ratio 0\.1 on both benchmarks\. Figure[2a](https://arxiv.org/html/2608.12331#S4.F2.sf1)and Figure[3a](https://arxiv.org/html/2608.12331#S4.F3.sf1)sweep the compaction ratio for AIME and MATH\-500 respectively; Figure[2b](https://arxiv.org/html/2608.12331#S4.F2.sf2)and Figure[3b](https://arxiv.org/html/2608.12331#S4.F3.sf2)plot the accuracy vs\. memory trade\-off\. We highlight five findings\.

First, the Eviction baseline suffers a substantial accuracy drop on both benchmarks \(46\.7% on AIME, 52\.4% on MATH\-500 vs\. 63\.3% and 71\.2%\), confirming Proposition[4\.1](https://arxiv.org/html/2608.12331#S4.Thmtheorem1): mass deficit degrades generation quality\. Second, PAM \(Uniform\) improves over eviction by applying the AM pipeline but still falls short of No Compaction\. Third,TAM consistently outperforms PAM \(Uniform\)on both benchmarks \(60\.0% vs\. 56\.7% on AIME; 67\.8% vs\. 64\.6% on MATH\-500 at ratio 0\.1\), demonstrating that thought\-aware allocation and pivotal protection provide genuine gains over uniform compression\. Fourth, TAM \(Periodic\) achieves the best steady\-state memory \(3\.2 GB, 65% reduction vs\. No Compaction\) while maintaining competitive accuracy\. On MATH\-500, TAM \(Periodic\) outperforms PAM by 0\.6–0\.8 points at ratios 0\.05–0\.1, confirming that TAM’s per\-step advantage partially survives cumulative error from repeated compaction\. At ratio 0\.2, cumulative error slightly offsets TAM’s advantage on MATH\-500 \(68\.0% vs\. 68\.4% for PAM\), consistent with diminishing returns of adaptive allocation when ample budget reduces the impact of importance heterogeneity\. Fifth, at ratio 0\.2, TAM recovers the full No Compaction accuracy on AIME \(63\.3%\); on MATH\-500, a modest 1\.0\-point gap remains \(70\.2% vs\. 71\.2%\)\.

#### Statistical significance\.

AIME 2024 has only 30 problems \(3\.3% per\-problem granularity\), so individual accuracy differences \(e\.g\., TAM vs\. PAM: 60\.0% vs\. 56\.7%, a single\-problem difference\) are not statistically significant by themselves and should be interpreted with caution\. In particular, TAM \(Periodic\) and PAM are statistically indistinguishable on AIME at all ratios; MATH\-500 provides the meaningful comparison for periodic compaction\. On MATH\-500, TAM vs\. PAM \(67\.8% vs\. 64\.6%,Δ=16\\Delta=16problems\) yields a one\-sided McNemar testp≈0\.04p\\approx 0\.04, providing moderate evidence of improvement\. The consistent direction of improvement across both benchmarks and all three compression ratios \(Table[7](https://arxiv.org/html/2608.12331#A5.T7)and Table[8](https://arxiv.org/html/2608.12331#A5.T8)\) strengthens the case despite AIME’s limited statistical power\. We recommend that future work use larger evaluation sets and report confidence intervals; we note this limitation in Section[6](https://arxiv.org/html/2608.12331#S6)\.

2565121024∞\\infty505055556060656553\.353\.356\.756\.756\.756\.76060Compaction IntervalPPAccuracy \(%\)Accuracy223344552\.82\.8333\.23\.244Peak Memory \(GB\)Peak MemoryFigure 4:Ablation on compaction intervalPP\(AIME 2024\)\. SmallerPPreduces peak memory with modest accuracy trade\-off\.P=∞P\{=\}\\inftycompacts only at max sequence length\.S1S2S3S4S5S6S7S8S9S10S11S12055101015152020uniform14\.29\.86\.52\.21\.813\.58\.81\.57\.210\.56\.817\.2Reasoning SegmentImportancewiw\_\{i\}\(%\)Figure 5:Per\-segment importancewiw\_\{i\}for a representative AIME problem \(12 segments\)\. Importance varies by\>11×\>11\\times\(S12: 17\.2% vs\. S8: 1\.5%\)\. Dead\-end segments \(S4, S5, S8, red labels\) receive minimal budget under TAM’s adaptive allocation\.

### 5\.3Compaction Time Breakdown

Table[2](https://arxiv.org/html/2608.12331#S4.T2)profiles TAM’s wall\-clock cost per compaction step on a typical∼\\sim4k\-token trajectory\. Thought segmentation and importance scoring add minimal overhead \(0\.1 s total\) relative to the AM core \(key selection \+ fitting\)\. PAM \(Uniform\) takes approximately 5\.4 s per step \(the same AM core without the 0\.15 s structure\-aware overhead\), confirming that TAM’s additional cost is negligible\. For context, generating a∼\\sim4k\-token trajectory takes 60–80 s on a single A100, so the compaction cost represents less than 10% of total inference time\.

### 5\.4Ablation Studies

We conduct ablation studies on TAM’s key components: adaptive budget allocation, pivotal token protection, segmentation method, the compaction intervalPP, and the selector window sizeRR\. All ablations use AIME 2024 at target ratio 0\.1 unless otherwise noted\.

#### Adaptive allocation and pivotal protection\.

Table[4](https://arxiv.org/html/2608.12331#S4.T4)isolates the contribution of each TAM component\. On MATH\-500 \(500 problems, finer granularity\), adding adaptive allocation alone improves accuracy by 1\.8 points over PAM \(Uniform\); adding pivotal protection alone yields a 1\.6\-point gain\. The combined gain \(\+3\.2\) is slightly less than the sum of individual gains \(1\.8 \+ 1\.6 = 3\.4\), indicating a modest overlap: both mechanisms partially address the same error sources, as pivotal tokens \(which receive exact retention\) also tend to reside in high\-importance segments that benefit from adaptive allocation\. On AIME \(30 problems, 3\.3% granularity\), individual components do not cross the discrete accuracy threshold, but combining both yields a clear 3\.3\-point improvement \(56\.7%→\\to60\.0%\)\. On both benchmarks, the full TAM combination outperforms either component in isolation, confirming that the two mechanisms are complementary despite their partial overlap\.

#### Segmentation method\.

Table[4](https://arxiv.org/html/2608.12331#S4.T4)compares heuristic segmentation \(double\-newline boundary detection\) with attention\-based segmentation \(attention gradient jump detection\)\. Both achieve comparable accuracy, with heuristic segmentation being slightly more robust and substantially faster\. We use heuristic segmentation as the default\.

#### Pivotal thresholdcc\.

Table[6](https://arxiv.org/html/2608.12331#S4.T6)varies the threshold multiplierccfor pivotal token identification\. Too low a threshold \(c=1c\{=\}1\) protects too many tokens, leaving insufficient budget for adaptive allocation\. Too high \(c=10c\{=\}10\) protects too few tokens, reducing the benefit\. We findc=3c\{=\}3to strike a good balance\.

#### Compaction intervalPPand selector windowRR\.

Table[6](https://arxiv.org/html/2608.12331#S4.T6)ablates the compaction interval\. SmallerPPcompacts more frequently, reducing peak memory; per Proposition[C\.4](https://arxiv.org/html/2608.12331#A3.Thmtheorem4), largerPPincreasesλk\\lambda\_\{k\}and limits error accumulation\. We findP=1024P\{=\}1024a reasonable balance\. Table[9](https://arxiv.org/html/2608.12331#A5.T9)\(Appendix\) shows thatR=64R\{=\}64is sufficient for the selector window\.

## 6Conclusion

We introduced Thought\-Aware Attention Matching \(TAM\), which transforms KV cache compaction from a flat, uniform operation into a structure\-aware process that exploits the hierarchical nature of chain\-of\-thought reasoning\. Through thought segmentation, adaptive budget allocation, and pivotal token protection, TAM concentrates compression budget where it matters most while aggressively compressing irrelevant steps\. Our theoretical analysis establishes the optimality of the allocation rule and bounds cumulative error under sequential compaction\. Experiments on AIME 2024 and MATH\-500 demonstrate consistent improvements over uniform compaction and eviction baselines, with periodic compaction achieving steady\-state memory reduction of up to 65%\.

## Limitations

TAM has two main limitations\. First, it relies on heuristic thought segmentation \(e\.g\., double newlines\) and a local selector window to estimate segment importance, which can fail for reasoning traces without clear structural boundaries or when long\-range dependencies and backtracking occur\. Second, empirical evaluation is limited to mathematical reasoning benchmarks \(AIME, MATH‑500\) and a single model \(Qwen3‑4B\), leaving generalization to other domains and larger models untested\.

## References

- Y\. Bai, X\. Lv, J\. Zhang, H\. Lyu, J\. Tang, Z\. Huang, Z\. Du, X\. Liu, A\. Zeng, L\. Hou,et al\.\(2024\)Longbench: a bilingual, multitask benchmark for long context understanding\.InProceedings of the 62nd annual meeting of the association for computational linguistics \(volume 1: Long papers\),pp\. 3119–3137\.Cited by:[§2](https://arxiv.org/html/2608.12331#S2.SS0.SSS0.Px1.p1.1)\.
- M\. Chen, J\. Tworek, H\. Jun, Q\. Yuan, H\. P\. D\. O\. Pinto, J\. Kaplan, H\. Edwards, Y\. Burda, N\. Joseph, G\. Brockman,et al\.\(2021\)Evaluating large language models trained on code\.arXiv preprint arXiv:2107\.03374\.Cited by:[§5\.1](https://arxiv.org/html/2608.12331#S5.SS1.SSS0.Px1.p1.1)\.
- K\. Cobbe, V\. Kosaraju, M\. Bavarian, M\. Chen, H\. Jun, L\. Kaiser, M\. Plappert, J\. Tworek, J\. Hilton, R\. Nakano,et al\.\(2021\)Training verifiers to solve math word problems\.arXiv preprint arXiv:2110\.14168\.Cited by:[§5\.1](https://arxiv.org/html/2608.12331#S5.SS1.SSS0.Px1.p1.1)\.
- T\. Dao, D\. Fu, S\. Ermon, A\. Rudra, and C\. Ré \(2022\)Flashattention: fast and memory\-efficient exact attention with io\-awareness\.Advances in neural information processing systems35,pp\. 16344–16359\.Cited by:[§1](https://arxiv.org/html/2608.12331#S1.p1.1),[§3\.1](https://arxiv.org/html/2608.12331#S3.SS1.p1.4)\.
- J\. Ding, S\. Ma, L\. Dong, X\. Zhang, S\. Huang, W\. Wang, N\. Zheng, and F\. Wei \(2023\)Longnet: scaling transformers to 1,000,000,000 tokens\.arXiv preprint arXiv:2307\.02486\.Cited by:[§2](https://arxiv.org/html/2608.12331#S2.SS0.SSS0.Px1.p1.1)\.
- S\. Eyuboglu, R\. Ehrlich, S\. Arora, N\. Guha, D\. Zinsley, E\. Liu, W\. Tennien, A\. Rudra, J\. Zou, A\. Mirhoseini,et al\.\(2025\)Cartridges: lightweight and general\-purpose long context representations via self\-study\.arXiv preprint arXiv:2506\.06266\.Cited by:[§2](https://arxiv.org/html/2608.12331#S2.SS0.SSS0.Px2.p1.1)\.
- D\. Hendrycks, C\. Burns, S\. Kadavath, A\. Arora, S\. Basart, E\. Tang, D\. Song, and J\. Steinhardt \(2021\)Measuring mathematical problem solving with the math dataset\.arXiv preprint arXiv:2103\.03874\.Cited by:[§5\.1](https://arxiv.org/html/2608.12331#S5.SS1.SSS0.Px1.p1.1)\.
- T\. Kojima, S\. S\. Gu, M\. Reid, Y\. Matsuo, and Y\. Iwasawa \(2022\)Large language models are zero\-shot reasoners\.Advances in neural information processing systems35,pp\. 22199–22213\.Cited by:[§1](https://arxiv.org/html/2608.12331#S1.p3.1)\.
- 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\.Advances in Neural Information Processing Systems37,pp\. 22947–22970\.Cited by:[§1](https://arxiv.org/html/2608.12331#S1.p1.1),[§2](https://arxiv.org/html/2608.12331#S2.SS0.SSS0.Px1.p1.1),[§5\.1](https://arxiv.org/html/2608.12331#S5.SS1.SSS0.Px2.p2.1)\.
- N\. F\. Liu, K\. Lin, J\. Hewitt, A\. Paranjape, M\. Bevilacqua, F\. Petroni, and P\. Liang \(2024\)Lost in the middle: how language models use long contexts\.Transactions of the association for computational linguistics12,pp\. 157–173\.Cited by:[§2](https://arxiv.org/html/2608.12331#S2.SS0.SSS0.Px1.p1.1)\.
- J\. Song, D\. Jo, Y\. Kim, and J\. Kim \(2025\)Reasoning path compression: compressing generation trajectories for efficient llm reasoning\.arXiv preprint arXiv:2505\.13866\.Cited by:[§1](https://arxiv.org/html/2608.12331#S1.p2.1),[§2](https://arxiv.org/html/2608.12331#S2.SS0.SSS0.Px3.p1.1),[§4\.2](https://arxiv.org/html/2608.12331#S4.SS2.p1.4),[§5\.1](https://arxiv.org/html/2608.12331#S5.SS1.SSS0.Px2.p1.3)\.
- J\. A\. Tropp and A\. C\. Gilbert \(2007\)Signal recovery from random measurements via orthogonal matching pursuit\.IEEE Transactions on information theory53\(12\),pp\. 4655–4666\.Cited by:[§3\.2](https://arxiv.org/html/2608.12331#S3.SS2.p1.12)\.
- A\. Vaswani, N\. Shazeer, N\. Parmar, J\. Uszkoreit, L\. Jones, A\. N\. Gomez, Ł\. Kaiser, and I\. Polosukhin \(2017\)Attention is all you need\.Advances in neural information processing systems30\.Cited by:[§3\.1](https://arxiv.org/html/2608.12331#S3.SS1.p1.3)\.
- J\. Wei, X\. Wang, D\. Schuurmans, M\. Bosma, F\. Xia, E\. Chi, Q\. V\. Le, D\. Zhou,et al\.\(2022\)Chain\-of\-thought prompting elicits reasoning in large language models\.Advances in neural information processing systems35,pp\. 24824–24837\.Cited by:[§1](https://arxiv.org/html/2608.12331#S1.p1.1)\.
- G\. Xiao, Y\. Tian, B\. Chen, S\. Han, and M\. Lewis \(2023\)Efficient streaming language models with attention sinks\.arXiv preprint arXiv:2309\.17453\.Cited by:[§2](https://arxiv.org/html/2608.12331#S2.SS0.SSS0.Px1.p1.1)\.
- A\. Yang, A\. Li, B\. Yang, B\. Zhang, B\. Hui, B\. Zheng, B\. Yu, C\. Gao, C\. Huang, C\. Lv,et al\.\(2025\)Qwen3 technical report\.arXiv preprint arXiv:2505\.09388\.Cited by:[§5\.1](https://arxiv.org/html/2608.12331#S5.SS1.SSS0.Px1.p1.1)\.
- Y\. Zhang and T\. Math\-AI \(2024\)American invitational mathematics examination \(aime\) 2025\.Wei Zhao, Zhe Li, Yige Li, Ye Zhang, and Junfeng Sun\.Cited by:[§5\.1](https://arxiv.org/html/2608.12331#S5.SS1.SSS0.Px1.p1.1)\.
- Z\. Zhang, Y\. Sheng, T\. Zhou, T\. Chen, L\. Zheng, R\. Cai, Z\. Song, Y\. Tian, C\. Ré, C\. Barrett,et al\.\(2023\)H2o: heavy\-hitter oracle for efficient generative inference of large language models\.Advances in Neural Information Processing Systems36,pp\. 34661–34710\.Cited by:[§1](https://arxiv.org/html/2608.12331#S1.p1.1),[§2](https://arxiv.org/html/2608.12331#S2.SS0.SSS0.Px1.p1.1),[§5\.1](https://arxiv.org/html/2608.12331#S5.SS1.SSS0.Px2.p2.1)\.
- A\. Zweiger, X\. Fu, H\. Guo, and Y\. Kim \(2026\)Fast kv compaction via attention matching\.arXiv preprint arXiv:2602\.16284\.Cited by:[§1](https://arxiv.org/html/2608.12331#S1.p2.1),[§2](https://arxiv.org/html/2608.12331#S2.SS0.SSS0.Px2.p1.1),[§3\.1](https://arxiv.org/html/2608.12331#S3.SS1.p2.2),[§3\.2](https://arxiv.org/html/2608.12331#S3.SS2.p1.7),[§5\.1](https://arxiv.org/html/2608.12331#S5.SS1.SSS0.Px2.p1.3)\.

## Appendix

## Appendix AAlgorithm Pipeline

Input:KV cache

\(𝐊,𝐕\)\(\\mathbf\{K\},\\mathbf\{V\}\)of length

LL, target size

tt, selector window size

RR, protected tail

τ\\tau, pivotal threshold multiplier

cc
Output:Compacted cache

Protect last

τ\\tautokens; let

𝐊p,𝐕p\\mathbf\{K\}\_\{p\},\\mathbf\{V\}\_\{p\}be their KV states

Extract

𝐐ref\\mathbf\{Q\}\_\{\\text\{ref\}\}from last

RRtokens via prefill with forward hooks

Segment compactable prefix

\[0,L−τ\]\[0,L\{\-\}\\tau\]into

\{S1,…,Sm\}\\\{S\_\{1\},\\ldots,S\_\{m\}\\\}via thought boundaries

for*each KV\-head*do

Compute per\-token attention scores

α¯j\\bar\{\\alpha\}\_\{j\}under

𝐐ref\\mathbf\{Q\}\_\{\\text\{ref\}\}\(Eq\.[7](https://arxiv.org/html/2608.12331#S4.E7)\)

Identify pivotal set

𝒫=\{j:α¯j\>c⋅α¯mean\}\\mathcal\{P\}=\\\{j:\\bar\{\\alpha\}\_\{j\}\>c\\cdot\\bar\{\\alpha\}\_\{\\text\{mean\}\}\\\}
Retain pivotal keys/values:

𝐂k𝒫←𝐊​\[𝒫,:\]\\mathbf\{C\}\_\{k\}^\{\\mathcal\{P\}\}\\leftarrow\\mathbf\{K\}\[\\mathcal\{P\},:\],

𝐂v𝒫←𝐕​\[𝒫,:\]\\mathbf\{C\}\_\{v\}^\{\\mathcal\{P\}\}\\leftarrow\\mathbf\{V\}\[\\mathcal\{P\},:\]
Compute segment importances

wiw\_\{i\}\(Eq\.[5](https://arxiv.org/html/2608.12331#S4.E5)\) and allocate budgets

tit\_\{i\}\(Eq\.[6](https://arxiv.org/html/2608.12331#S4.E6)\)

for*each segmentSiS\_\{i\}*do

Select

tit\_\{i\}keys from

Si∖𝒫S\_\{i\}\\setminus\\mathcal\{P\}via highest\-attention under

𝐐ref\\mathbf\{Q\}\_\{\\text\{ref\}\}
end for

Let

SallS\_\{\\text\{all\}\}= pivotal keys

∪\\cupper\-segment selected keys

Set

𝐂k←𝐊​\[Sall,:\]\\mathbf\{C\}\_\{k\}\\leftarrow\\mathbf\{K\}\[S\_\{\\text\{all\}\},:\]
Fit

𝜷\\bm\{\\beta\}via NNLS to match attention mass globally; set

βj=0\\beta\_\{j\}=0for

j∈𝒫j\\in\\mathcal\{P\}
Fit

𝐂v\\mathbf\{C\}\_\{v\}via OLS to match attention outputs globally

Concatenate

\(𝐂k,𝜷,𝐂v\)\(\\mathbf\{C\}\_\{k\},\\bm\{\\beta\},\\mathbf\{C\}\_\{v\}\)with

\(𝐊p,𝐕p\)\(\\mathbf\{K\}\_\{p\},\\mathbf\{V\}\_\{p\}\)
end for

returncompacted cache

Algorithm 1Thought\-Aware Attention Matching \(TAM\)
## Appendix BAnalysis: Segment Importance and Budget Distribution

To verify that CoT trajectories exhibit the structural heterogeneity motivating TAM, we analyze the segment importance distribution on AIME 2024 problems\.

#### Importance heterogeneity\.

Figure[5](https://arxiv.org/html/2608.12331#S5.F5)visualizes the per\-segment importancewiw\_\{i\}\(Eq\.[5](https://arxiv.org/html/2608.12331#S4.E5)\) for a representative AIME problem with 12 reasoning segments\. Importance varies by over11×11\\timesacross segments: early segments \(problem restatement, initial setup\) and the most recent segment receive high importance, while middle segments corresponding to dead\-end explorations receive very low importance\. This confirms that uniform allocation is wasteful: TAM assigns≤3%\\leq 3\\%of budget to the lowest\-importance segments while allocating\>15%\>15\\%to the highest\.

#### Pivotal token semantics\.

We qualitatively inspect the pivotal tokens identified by TAM \(c=3c\{=\}3\) across AIME problems\. Pivotal tokens predominantly correspond to: \(1\) numerical constants from the problem statement \(e\.g\., coefficients, constraints\), \(2\) key intermediate expressions \(e\.g\., derived equations, variable bindings\), and \(3\) structural tokens that anchor the reasoning flow \(e\.g\., “Therefore”, “=”\)\. This aligns with the intuition that pivotal tokens serve as reasoning anchors that future queries consistently rely on\.

#### Error analysis\.

We examine the problems where TAM \(ratio 0\.1\) fails but No Compaction succeeds\. On MATH\-500, the accuracy gap \(67\.8% vs\. 71\.2%\) concentrates on problems with two characteristics: \(i\) very long reasoning chains \(\>\>6k tokens\) that produce many segments with complex non\-local dependencies between distant reasoning steps, and \(ii\) problems where the model’s reasoning path undergoes a late\-stage correction that revisits earlier segments\. In case \(i\), the selector window’s local coverage \(Proposition[C\.3](https://arxiv.org/html/2608.12331#A3.Thmtheorem3)\) becomes less effective for distant segments, increasing‖𝐱𝐪⟂‖\\\|\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\perp\}\\\|; in case \(ii\), compaction discards tokens from segments previously deemed unimportant that later become relevant upon backtracking\. These failure modes suggest that dynamic importance re\-estimation \(updating segment scores as reasoning progresses\) is a promising direction for future work\.

## Appendix CMore Propositions

###### Proposition C\.1\(Optimality of Importance\-Weighted Allocation\)\.

Considermmsegments with sizesn1,…,nmn\_\{1\},\\ldots,n\_\{m\}and importance weightsw1,…,wmw\_\{1\},\\ldots,w\_\{m\}\(∑iwi=1\\sum\_\{i\}w\_\{i\}=1\)\. Suppose the per\-segment approximation error when allocatingtit\_\{i\}compact keys to segmentSiS\_\{i\}isεi=ϕ​\(ni/ti\)\\varepsilon\_\{i\}=\\phi\(n\_\{i\}/t\_\{i\}\), whereϕ:\[1,∞\)→\[0,∞\)\\phi:\[1,\\infty\)\\to\[0,\\infty\)is convex and increasing withϕ​\(1\)=0\\phi\(1\)=0\. The importance\-weighted total error is

ℰ​\(𝐭\)=∑i=1mwi⋅ϕ​\(ni/ti\),s\.t\.∑i=1mti=t,ti≥1\.\\mathcal\{E\}\(\\mathbf\{t\}\)=\\sum\_\{i=1\}^\{m\}w\_\{i\}\\cdot\\phi\(n\_\{i\}/t\_\{i\}\),\\quad\\text\{s\.t\.\}\\quad\\sum\_\{i=1\}^\{m\}t\_\{i\}=t,\\;t\_\{i\}\\geq 1\.\(9\)Then:

1. 1\.The optimal allocation satisfiesti⋆∝wi⋅ni⋅ϕ′​\(ni/ti⋆\)t\_\{i\}^\{\\star\}\\propto\\sqrt\{w\_\{i\}\\cdot n\_\{i\}\\cdot\\phi^\{\\prime\}\(n\_\{i\}/t\_\{i\}^\{\\star\}\)\}at interior KKT points\.
2. 2\.Under the linear modelϕ​\(r\)=r−1\\phi\(r\)=r\-1\(error proportional to compression ratio\), the optimal allocation simplifies toti⋆∝wi⋅nit\_\{i\}^\{\\star\}\\propto\\sqrt\{w\_\{i\}\\cdot n\_\{i\}\}\.
3. 3\.Uniform allocation \(ti∝nit\_\{i\}\\propto n\_\{i\}\) is strictly suboptimal whenever the importance densitywi/niw\_\{i\}/n\_\{i\}is not constant across segments, i\.e\., when some segments are more important per token than others\.

Proposition[C\.1](https://arxiv.org/html/2608.12331#A3.Thmtheorem1)provides the theoretical foundation for TAM’s budget allocation \(Eq\.[6](https://arxiv.org/html/2608.12331#S4.E6)\)\. The linear\-model resultti⋆∝wi⋅nit\_\{i\}^\{\\star\}\\propto\\sqrt\{w\_\{i\}\\cdot n\_\{i\}\}is the geometric mean of the importance\-only allocation \(ti∝wit\_\{i\}\\propto w\_\{i\}\) and the size\-only allocation \(ti∝nit\_\{i\}\\propto n\_\{i\}\), optimally trading off both factors\. In CoT reasoning, the importance densitywi/niw\_\{i\}/n\_\{i\}varies substantially across segments: dead\-end explorations have low density while key intermediate results have high density, making adaptive allocation strictly beneficial\.

###### Proposition C\.2\(Error Reduction from Pivotal Token Protection\)\.

Let𝒫\\mathcal\{P\}denote the set of pivotal tokens and letγ𝐪=∑j∈𝒫αj​\(𝐪\)\\gamma\_\{\\mathbf\{q\}\}=\\sum\_\{j\\in\\mathcal\{P\}\}\\alpha\_\{j\}\(\\mathbf\{q\}\)be the pivotal attention mass for a specific query𝐪\\mathbf\{q\}\. Suppose the remainingT−\|𝒫\|T\-\|\\mathcal\{P\}\|tokens are compacted tot−\|𝒫\|t\-\|\\mathcal\{P\}\|keys via AM with per\-query approximation errorεrest\\varepsilon\_\{\\text\{rest\}\}on the non\-pivotal portion\. Suppose further that the total attention mass is matched for query𝐪\\mathbf\{q\}, i\.e\.,Mass​\(𝐪;𝐂k,𝛃\)=Mass​\(𝐪;𝐊\)\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{C\}\_\{k\},\\bm\{\\beta\}\)=\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{K\}\)\. Then the overall attention output error satisfies

‖𝐲^−𝐲∗‖≤\(1−γ𝐪\)⋅εrest\.\\\|\\hat\{\\mathbf\{y\}\}\-\\mathbf\{y\}^\{\*\}\\\|\\leq\(1\-\\gamma\_\{\\mathbf\{q\}\}\)\\cdot\\varepsilon\_\{\\text\{rest\}\}\.\(10\)Define the worst\-case pivotal massγ=min𝐪∈𝐐ref⁡γ𝐪\\gamma=\\min\_\{\\mathbf\{q\}\\in\\mathbf\{Q\}\_\{\\text\{ref\}\}\}\\gamma\_\{\\mathbf\{q\}\}, which lower\-bounds the per\-query pivotal mass over all selector\-window queries\. Then the uniform bound‖𝐲^−𝐲∗‖≤\(1−γ\)⋅εrest\\\|\\hat\{\\mathbf\{y\}\}\-\\mathbf\{y\}^\{\*\}\\\|\\leq\(1\-\\gamma\)\\cdot\\varepsilon\_\{\\text\{rest\}\}holds for all𝐪∈𝐐ref\\mathbf\{q\}\\in\\mathbf\{Q\}\_\{\\text\{ref\}\}\. More generally, when mass is not matched exactly, letΔ​γ𝐪=γ^𝐪−γ𝐪\\Delta\\gamma\_\{\\mathbf\{q\}\}=\\hat\{\\gamma\}\_\{\\mathbf\{q\}\}\-\\gamma\_\{\\mathbf\{q\}\}denote the pivotal mass mismatch; then

‖𝐲^−𝐲∗‖≤\(1−γ𝐪\)⋅εrest\+2​\|Δ​γ𝐪\|⋅‖𝐕‖∞\.\\\|\\hat\{\\mathbf\{y\}\}\-\\mathbf\{y\}^\{\*\}\\\|\\leq\(1\-\\gamma\_\{\\mathbf\{q\}\}\)\\cdot\\varepsilon\_\{\\text\{rest\}\}\+2\\left\|\\Delta\\gamma\_\{\\mathbf\{q\}\}\\right\|\\cdot\\\|\\mathbf\{V\}\\\|\_\{\\infty\}\.\(11\)

Since pivotal tokens are retained exactly, they contribute zero approximation error when mass is preserved\. The remaining error arises only from the non\-pivotal portion, which carries attention mass\(1−γ\)\(1\-\\gamma\)\.

###### Proposition C\.3\(Selector Window Approximation Error\)\.

Let𝐐ref∈ℝn×d\\mathbf\{Q\}\_\{\\text\{ref\}\}\\in\\mathbb\{R\}^\{n\\times d\}be the selector window queries and𝐂k,𝛃,𝐂v\\mathbf\{C\}\_\{k\},\\bm\{\\beta\},\\mathbf\{C\}\_\{v\}be fitted via TAM\. Let𝐗∈ℝn×t\\mathbf\{X\}\\in\\mathbb\{R\}^\{n\\times t\}have rows𝐱ref\(i\)=softmax​\(𝐪i​𝐂k⊤/d\+𝛃\)\\mathbf\{x\}\_\{\\text\{ref\}\}^\{\(i\)\}=\\text\{softmax\}\(\\mathbf\{q\}\_\{i\}\\mathbf\{C\}\_\{k\}^\{\\top\}/\\sqrt\{d\}\+\\bm\{\\beta\}\)and𝐂v⋆=\(𝐗⊤​𝐗\)−1​𝐗⊤​𝐘\\mathbf\{C\}\_\{v\}^\{\\star\}=\(\\mathbf\{X\}^\{\\top\}\\mathbf\{X\}\)^\{\-1\}\\mathbf\{X\}^\{\\top\}\\mathbf\{Y\}be the OLS\-fitted values\. For a future query𝐪\\mathbf\{q\}with attention pattern𝐱𝐪=softmax​\(𝐪𝐂k⊤/d\+𝛃\)\\mathbf\{x\}\_\{\\mathbf\{q\}\}=\\text\{softmax\}\(\\mathbf\{q\}\\mathbf\{C\}\_\{k\}^\{\\top\}/\\sqrt\{d\}\+\\bm\{\\beta\}\), decompose𝐱𝐪=𝐱𝐪∥\+𝐱𝐪⟂\\mathbf\{x\}\_\{\\mathbf\{q\}\}=\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\parallel\}\+\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\perp\}where𝐱𝐪∥\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\parallel\}lies in the row space of𝐗\\mathbf\{X\}and𝐱𝐪⟂\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\perp\}is orthogonal\. Then:

‖𝐱𝐪​𝐂v⋆−𝐲∗‖≤‖𝐱𝐪⟂‖⋅‖𝐂v⋆‖op\+‖𝐱𝐪∥​𝐂v⋆−𝐲∥∗‖,\\\|\\mathbf\{x\}\_\{\\mathbf\{q\}\}\\mathbf\{C\}\_\{v\}^\{\\star\}\-\\mathbf\{y\}^\{\*\}\\\|\\leq\\\|\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\perp\}\\\|\\cdot\\\|\\mathbf\{C\}\_\{v\}^\{\\star\}\\\|\_\{\\text\{op\}\}\+\\\|\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\parallel\}\\mathbf\{C\}\_\{v\}^\{\\star\}\-\\mathbf\{y\}^\{\*\}\_\{\\parallel\}\\\|,\(12\)where𝐲∗\\mathbf\{y\}^\{\*\}is the ideal output and𝐲∥∗=𝛌⊤​𝐘\\mathbf\{y\}^\{\*\}\_\{\\parallel\}=\\bm\{\\lambda\}^\{\\top\}\\mathbf\{Y\}with𝛌\\bm\{\\lambda\}satisfying𝐱𝐪∥=𝛌⊤​𝐗\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\parallel\}=\\bm\{\\lambda\}^\{\\top\}\\mathbf\{X\}\(i\.e\., the linear combination of reference outputs𝐘\\mathbf\{Y\}with the same coefficients that express𝐱𝐪∥\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\parallel\}in the row space of𝐗\\mathbf\{X\}\)\. When𝐱𝐪⟂=𝟎\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\perp\}=\\mathbf\{0\}, the term‖𝐱𝐪⟂‖⋅‖𝐂v⋆‖op\\\|\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\perp\}\\\|\\cdot\\\|\\mathbf\{C\}\_\{v\}^\{\\star\}\\\|\_\{\\text\{op\}\}vanishes\.

The error is controlled by how far the future query’s attention pattern deviates from the subspace spanned by the reference patterns\. The first term \(‖𝐱𝐪⟂‖⋅‖𝐂v⋆‖op\\\|\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\perp\}\\\|\\cdot\\\|\\mathbf\{C\}\_\{v\}^\{\\star\}\\\|\_\{\\text\{op\}\}\) captures coverage error from the selector window’s finite span; characterizing it precisely requires distributional assumptions on future queries\. Under the locality of CoT reasoning, successive tokens attend to similar context, keeping‖𝐱𝐪⟂‖\\\|\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\perp\}\\\|small\. TAM’s adaptive allocation further helps: segments where the selector window provides poor coverage \(high‖𝐱𝐪⟂‖\\\|\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\perp\}\\\|, typically distant segments\) tend to receive lower importance scores and thus lower budgets, concentrating resources where the approximation is most accurate\.

###### Proposition C\.4\(Cumulative Error under Sequential Compaction\)\.

Suppose TAM performsKKsequential compaction steps\. At stepkk, letεk\\varepsilon\_\{k\}denote the per\-query attention output error of stepkk’s compacted cache relative to the step\-\(k−1\)\(k\{\-\}1\)cache, andλk∈\[0,1\]\\lambda\_\{k\}\\in\[0,1\]the fraction of fresh tokens\. Under a*linear error composition*model—where the attention output error from previously compacted tokens and fresh tokens combines additively, weighted by their respective fractions—the cumulative error relative to the original cache satisfies:

ε~K≤∑k=1Kεk⋅∏j=k\+1K\(1−λj\)\.\\tilde\{\\varepsilon\}\_\{K\}\\leq\\sum\_\{k=1\}^\{K\}\\varepsilon\_\{k\}\\cdot\\prod\_\{j=k\+1\}^\{K\}\(1\-\\lambda\_\{j\}\)\.\(13\)Whenλk≥λmin\>0\\lambda\_\{k\}\\geq\\lambda\_\{\\min\}\>0for allkk, we haveε~K≤εmax/λmin\\tilde\{\\varepsilon\}\_\{K\}\\leq\\varepsilon\_\{\\max\}/\\lambda\_\{\\min\}, independent ofKK\. In the periodic regime with intervalPPand target sizett,λk≈P/\(P\+t\)\\lambda\_\{k\}\\approx P/\(P\+t\)\.

## Appendix DProofs of Theoretical Results

###### Proof of Proposition[4\.1](https://arxiv.org/html/2608.12331#S4.Thmtheorem1)\.

Part 1 \(Mass deficit\)\.For eviction retaining subsetSSwith\|S\|=t\|S\|=t, the compacted mass is

Mass​\(𝐪;𝐂k\)=∑j∈Sexp⁡\(𝐪𝐊j⊤/d\)=Mass​\(𝐪;𝐊\)−∑j∉Sexp⁡\(𝐪𝐊j⊤/d\)\.\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{C\}\_\{k\}\)=\\sum\_\{j\\in S\}\\exp\(\\mathbf\{q\}\\mathbf\{K\}\_\{j\}^\{\\top\}/\\sqrt\{d\}\)=\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{K\}\)\-\\sum\_\{j\\notin S\}\\exp\(\\mathbf\{q\}\\mathbf\{K\}\_\{j\}^\{\\top\}/\\sqrt\{d\}\)\.\(14\)SinceS≠\[T\]S\\neq\[T\], the second sum is strictly positive for all𝐪\\mathbf\{q\}\(asexp⁡\(⋅\)\>0\\exp\(\\cdot\)\>0\), givingMass​\(𝐪;𝐂k\)=\(1−μ​\(𝐪\)\)⋅Mass​\(𝐪;𝐊\)<Mass​\(𝐪;𝐊\)\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{C\}\_\{k\}\)=\(1\-\\mu\(\\mathbf\{q\}\)\)\\cdot\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{K\}\)<\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{K\}\)\.

Part 2 \(Concatenation effect\)\.When concatenated with future keys𝐊f\\mathbf\{K\}\_\{f\}, the softmax denominator isMass​\(𝐪;𝐂k\)\+Mass​\(𝐪;𝐊f\)\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{C\}\_\{k\}\)\+\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{K\}\_\{f\}\)\. The compacted prefix’s softmax weight is\(1−μ​\(𝐪\)\)​Mass​\(𝐪;𝐊\)/\[\(1−μ​\(𝐪\)\)​Mass​\(𝐪;𝐊\)\+Mass​\(𝐪;𝐊f\)\]\(1\-\\mu\(\\mathbf\{q\}\)\)\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{K\}\)/\[\(1\-\\mu\(\\mathbf\{q\}\)\)\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{K\}\)\+\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{K\}\_\{f\}\)\], which is strictly less than the originalMass​\(𝐪;𝐊\)/\[Mass​\(𝐪;𝐊\)\+Mass​\(𝐪;𝐊f\)\]\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{K\}\)/\[\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{K\}\)\+\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{K\}\_\{f\}\)\]\.

Part 3 \(Output error\)\.Letαj=exp⁡\(𝐪𝐊j⊤/d\)/Z\\alpha\_\{j\}=\\exp\(\\mathbf\{q\}\\mathbf\{K\}\_\{j\}^\{\\top\}/\\sqrt\{d\}\)/Zbe the original attention weights withZ=Mass​\(𝐪;𝐊\)Z=\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{K\}\), andα^j=αj/\(1−μ​\(𝐪\)\)\\hat\{\\alpha\}\_\{j\}=\\alpha\_\{j\}/\(1\-\\mu\(\\mathbf\{q\}\)\)forj∈Sj\\in Sbe the eviction weights\. The output error \(considering only the prefix block\) is:

‖𝐲^−𝐲‖=‖∑j∈Sα^j​𝐕j−∑j=1Tαj​𝐕j‖=‖∑j∈Sμ​\(𝐪\)1−μ​\(𝐪\)​αj​𝐕j−∑j∉Sαj​𝐕j‖≤2​μ​\(𝐪\)​‖𝐕‖∞,\\\|\\hat\{\\mathbf\{y\}\}\-\\mathbf\{y\}\\\|=\\left\\\|\\sum\_\{j\\in S\}\\hat\{\\alpha\}\_\{j\}\\mathbf\{V\}\_\{j\}\-\\sum\_\{j=1\}^\{T\}\\alpha\_\{j\}\\mathbf\{V\}\_\{j\}\\right\\\|=\\left\\\|\\sum\_\{j\\in S\}\\frac\{\\mu\(\\mathbf\{q\}\)\}\{1\-\\mu\(\\mathbf\{q\}\)\}\\alpha\_\{j\}\\mathbf\{V\}\_\{j\}\-\\sum\_\{j\\notin S\}\\alpha\_\{j\}\\mathbf\{V\}\_\{j\}\\right\\\|\\leq 2\\mu\(\\mathbf\{q\}\)\\\|\\mathbf\{V\}\\\|\_\{\\infty\},\(15\)where the last inequality uses∑j∈Sαj=1−μ​\(𝐪\)\\sum\_\{j\\in S\}\\alpha\_\{j\}=1\-\\mu\(\\mathbf\{q\}\),∑j∉Sαj=μ​\(𝐪\)\\sum\_\{j\\notin S\}\\alpha\_\{j\}=\\mu\(\\mathbf\{q\}\), and triangle inequality\. ∎

###### Proof of Proposition[C\.1](https://arxiv.org/html/2608.12331#A3.Thmtheorem1)\.

Part 1 \(KKT conditions\)\.We minimizeℰ​\(𝐭\)=∑iwi​ϕ​\(ni/ti\)\\mathcal\{E\}\(\\mathbf\{t\}\)=\\sum\_\{i\}w\_\{i\}\\phi\(n\_\{i\}/t\_\{i\}\)subject to∑iti=t\\sum\_\{i\}t\_\{i\}=tandti≥1t\_\{i\}\\geq 1\. Introducing Lagrange multiplierν\\nufor the equality constraint, the stationarity condition at an interior point \(ti\>1t\_\{i\}\>1\) gives:

∂ℰ∂ti=−wi⋅niti2⋅ϕ′​\(ni/ti\)=−ν⟹wi⋅niti2⋅ϕ′​\(ni/ti\)=ν∀i\.\\frac\{\\partial\\mathcal\{E\}\}\{\\partial t\_\{i\}\}=\-w\_\{i\}\\cdot\\frac\{n\_\{i\}\}\{t\_\{i\}^\{2\}\}\\cdot\\phi^\{\\prime\}\(n\_\{i\}/t\_\{i\}\)=\-\\nu\\quad\\Longrightarrow\\quad w\_\{i\}\\cdot\\frac\{n\_\{i\}\}\{t\_\{i\}^\{2\}\}\\cdot\\phi^\{\\prime\}\(n\_\{i\}/t\_\{i\}\)=\\nu\\quad\\forall i\.\(16\)Sinceϕ\\phiis convex and increasing,ϕ′\\phi^\{\\prime\}is non\-decreasing, and the second\-order conditions are satisfied\. Rearranging:ti2=wi​ni​ϕ′​\(ni/ti\)/νt\_\{i\}^\{2\}=w\_\{i\}n\_\{i\}\\phi^\{\\prime\}\(n\_\{i\}/t\_\{i\}\)/\\nu, soti⋆∝wi​ni​ϕ′​\(ni/ti⋆\)t\_\{i\}^\{\\star\}\\propto\\sqrt\{w\_\{i\}n\_\{i\}\\phi^\{\\prime\}\(n\_\{i\}/t\_\{i\}^\{\\star\}\)\}, as stated\.

Part 2 \(Linear model\)\.Whenϕ​\(r\)=r−1\\phi\(r\)=r\-1, we haveϕ′​\(r\)=1\\phi^\{\\prime\}\(r\)=1\(constant\) andϕ′′​\(r\)=0\\phi^\{\\prime\\prime\}\(r\)=0\. Returning to the stationarity condition:wi​ni/ti2=νw\_\{i\}n\_\{i\}/t\_\{i\}^\{2\}=\\nu, which givesti=wi​ni/νt\_\{i\}=\\sqrt\{w\_\{i\}n\_\{i\}/\\nu\}\. Using the budget constraint∑iti=t\\sum\_\{i\}t\_\{i\}=t:

ti⋆=t⋅wi​ni∑jwj​nj\.t\_\{i\}^\{\\star\}=t\\cdot\\frac\{\\sqrt\{w\_\{i\}n\_\{i\}\}\}\{\\sum\_\{j\}\\sqrt\{w\_\{j\}n\_\{j\}\}\}\.\(17\)
Part 3 \(Suboptimality of uniform\)\.Under uniform allocationtiunif=t⋅ni/Nt\_\{i\}^\{\\text\{unif\}\}=t\\cdot n\_\{i\}/N\(whereN=∑jnjN=\\sum\_\{j\}n\_\{j\}\), the weighted error isℰunif=∑iwi​ϕ​\(N/t\)\\mathcal\{E\}^\{\\text\{unif\}\}=\\sum\_\{i\}w\_\{i\}\\phi\(N/t\), which depends only on the global ratio\. Under optimal allocation,ℰ⋆≤ℰunif\\mathcal\{E\}^\{\\star\}\\leq\\mathcal\{E\}^\{\\text\{unif\}\}with equality iff the KKT conditions are satisfied by uniformtit\_\{i\}, which requireswi​ni/\(ni/N\)2=constw\_\{i\}n\_\{i\}/\(n\_\{i\}/N\)^\{2\}=\\text\{const\}, i\.e\.,wi/ni=constw\_\{i\}/n\_\{i\}=\\text\{const\}\. When importance density varies, the inequality is strict\. ∎

###### Proof of Proposition[C\.2](https://arxiv.org/html/2608.12331#A3.Thmtheorem2)\.

Partition the token set into pivotal tokens𝒫\\mathcal\{P\}and non\-pivotal tokens𝒫¯=\[T\]∖𝒫\\bar\{\\mathcal\{P\}\}=\[T\]\\setminus\\mathcal\{P\}\. For any query𝐪\\mathbf\{q\}, the ideal attention output decomposes as:

𝐲∗=∑j∈𝒫αj​\(𝐪\)​𝐕j\+∑j∈𝒫¯αj​\(𝐪\)​𝐕j=γ𝐪⋅𝐲𝒫∗\+\(1−γ𝐪\)⋅𝐲𝒫¯∗,\\mathbf\{y\}^\{\*\}=\\sum\_\{j\\in\\mathcal\{P\}\}\\alpha\_\{j\}\(\\mathbf\{q\}\)\\mathbf\{V\}\_\{j\}\+\\sum\_\{j\\in\\bar\{\\mathcal\{P\}\}\}\\alpha\_\{j\}\(\\mathbf\{q\}\)\\mathbf\{V\}\_\{j\}=\\gamma\_\{\\mathbf\{q\}\}\\cdot\\mathbf\{y\}^\{\*\}\_\{\\mathcal\{P\}\}\+\(1\-\\gamma\_\{\\mathbf\{q\}\}\)\\cdot\\mathbf\{y\}^\{\*\}\_\{\\bar\{\\mathcal\{P\}\}\},\(18\)whereγ𝐪=∑j∈𝒫αj​\(𝐪\)\\gamma\_\{\\mathbf\{q\}\}=\\sum\_\{j\\in\\mathcal\{P\}\}\\alpha\_\{j\}\(\\mathbf\{q\}\)is the attention mass on pivotal tokens for query𝐪\\mathbf\{q\}, and𝐲𝒫∗\\mathbf\{y\}^\{\*\}\_\{\\mathcal\{P\}\},𝐲𝒫¯∗\\mathbf\{y\}^\{\*\}\_\{\\bar\{\\mathcal\{P\}\}\}are the locally normalized outputs of each partition\.

Pivotal tokens are retained exactly:𝐂k​\[𝒫,:\]=𝐊​\[𝒫,:\]\\mathbf\{C\}\_\{k\}\[\\mathcal\{P\},:\]=\\mathbf\{K\}\[\\mathcal\{P\},:\]andβj=0\\beta\_\{j\}=0forj∈𝒫j\\in\\mathcal\{P\}\(Algorithm[1](https://arxiv.org/html/2608.12331#algorithm1)\)\. Letγ^𝐪\\hat\{\\gamma\}\_\{\\mathbf\{q\}\}denote the attention mass on pivotal tokens under the compacted cache, and𝐲^𝒫¯\\hat\{\\mathbf\{y\}\}\_\{\\bar\{\\mathcal\{P\}\}\}the locally normalized output of the non\-pivotal compacted portion\. The compacted output is:

𝐲^=γ^𝐪⋅𝐲𝒫∗\+\(1−γ^𝐪\)⋅𝐲^𝒫¯\.\\hat\{\\mathbf\{y\}\}=\\hat\{\\gamma\}\_\{\\mathbf\{q\}\}\\cdot\\mathbf\{y\}^\{\*\}\_\{\\mathcal\{P\}\}\+\(1\-\\hat\{\\gamma\}\_\{\\mathbf\{q\}\}\)\\cdot\\hat\{\\mathbf\{y\}\}\_\{\\bar\{\\mathcal\{P\}\}\}\.\(19\)
Case 1: Exact mass matching\.When total attention mass is matched \(Mass​\(𝐪;𝐂k,𝜷\)=Mass​\(𝐪;𝐊\)\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{C\}\_\{k\},\\bm\{\\beta\}\)=\\text\{Mass\}\(\\mathbf\{q\};\\mathbf\{K\}\)\), pivotal tokens’ numerators are unchanged, soγ^𝐪=γ𝐪\\hat\{\\gamma\}\_\{\\mathbf\{q\}\}=\\gamma\_\{\\mathbf\{q\}\}\. The error simplifies to:

‖𝐲^−𝐲∗‖=\(1−γ𝐪\)⋅‖𝐲^𝒫¯−𝐲𝒫¯∗‖≤\(1−γ𝐪\)⋅εrest\.\\\|\\hat\{\\mathbf\{y\}\}\-\\mathbf\{y\}^\{\*\}\\\|=\(1\-\\gamma\_\{\\mathbf\{q\}\}\)\\cdot\\\|\\hat\{\\mathbf\{y\}\}\_\{\\bar\{\\mathcal\{P\}\}\}\-\\mathbf\{y\}^\{\*\}\_\{\\bar\{\\mathcal\{P\}\}\}\\\|\\leq\(1\-\\gamma\_\{\\mathbf\{q\}\}\)\\cdot\\varepsilon\_\{\\text\{rest\}\}\.\(20\)
Case 2: General bound with mass mismatch\.LetΔ​γ𝐪=γ^𝐪−γ𝐪\\Delta\\gamma\_\{\\mathbf\{q\}\}=\\hat\{\\gamma\}\_\{\\mathbf\{q\}\}\-\\gamma\_\{\\mathbf\{q\}\}\. The error becomes:

𝐲^−𝐲∗\\displaystyle\\hat\{\\mathbf\{y\}\}\-\\mathbf\{y\}^\{\*\}=Δ​γ𝐪​\(𝐲𝒫∗−𝐲^𝒫¯\)\+\(1−γ𝐪\)​\(𝐲^𝒫¯−𝐲𝒫¯∗\)\.\\displaystyle=\\Delta\\gamma\_\{\\mathbf\{q\}\}\(\\mathbf\{y\}^\{\*\}\_\{\\mathcal\{P\}\}\-\\hat\{\\mathbf\{y\}\}\_\{\\bar\{\\mathcal\{P\}\}\}\)\+\(1\-\\gamma\_\{\\mathbf\{q\}\}\)\(\\hat\{\\mathbf\{y\}\}\_\{\\bar\{\\mathcal\{P\}\}\}\-\\mathbf\{y\}^\{\*\}\_\{\\bar\{\\mathcal\{P\}\}\}\)\.\(21\)Since𝐲𝒫∗\\mathbf\{y\}^\{\*\}\_\{\\mathcal\{P\}\}and𝐲^𝒫¯\\hat\{\\mathbf\{y\}\}\_\{\\bar\{\\mathcal\{P\}\}\}are both convex combinations of value vectors,‖𝐲𝒫∗−𝐲^𝒫¯‖≤2​‖𝐕‖∞\\\|\\mathbf\{y\}^\{\*\}\_\{\\mathcal\{P\}\}\-\\hat\{\\mathbf\{y\}\}\_\{\\bar\{\\mathcal\{P\}\}\}\\\|\\leq 2\\\|\\mathbf\{V\}\\\|\_\{\\infty\}\. By triangle inequality:

‖𝐲^−𝐲∗‖≤\(1−γ𝐪\)⋅εrest\+2​\|Δ​γ𝐪\|⋅‖𝐕‖∞\.\\\|\\hat\{\\mathbf\{y\}\}\-\\mathbf\{y\}^\{\*\}\\\|\\leq\(1\-\\gamma\_\{\\mathbf\{q\}\}\)\\cdot\\varepsilon\_\{\\text\{rest\}\}\+2\|\\Delta\\gamma\_\{\\mathbf\{q\}\}\|\\cdot\\\|\\mathbf\{V\}\\\|\_\{\\infty\}\.\(22\)
Takingγ=min𝐪⁡γ𝐪\\gamma=\\min\_\{\\mathbf\{q\}\}\\gamma\_\{\\mathbf\{q\}\}yields the stated bounds\. AM’s NNLS fitting enforces mass matching for the reference queries𝐐ref\\mathbf\{Q\}\_\{\\text\{ref\}\}, soΔ​γ𝐪≈0\\Delta\\gamma\_\{\\mathbf\{q\}\}\\approx 0for those queries and the clean bound applies\. Note thatεrest\\varepsilon\_\{\\text\{rest\}\}depends on the reduced budgett−\|𝒫\|t\-\|\\mathcal\{P\}\|; pivotal protection yields a net error reduction wheneverγ\\gammais large enough that\(1−γ\)​εrest<εall\(1\-\\gamma\)\\varepsilon\_\{\\text\{rest\}\}<\\varepsilon\_\{\\text\{all\}\}, whereεall\\varepsilon\_\{\\text\{all\}\}is the error of uniform compaction to sizett\. Underϕ​\(r\)=r−1\\phi\(r\)=r\-1, this holds whenγ\>\|𝒫\|/t\\gamma\>\|\\mathcal\{P\}\|/t\. ∎

###### Proof of Proposition[C\.3](https://arxiv.org/html/2608.12331#A3.Thmtheorem3)\.

Let𝐗∈ℝn×t\\mathbf\{X\}\\in\\mathbb\{R\}^\{n\\times t\}have rows𝐱ref\(i\)=softmax​\(𝐪i​𝐂k⊤/d\+𝜷\)\\mathbf\{x\}\_\{\\text\{ref\}\}^\{\(i\)\}=\\text\{softmax\}\(\\mathbf\{q\}\_\{i\}\\mathbf\{C\}\_\{k\}^\{\\top\}/\\sqrt\{d\}\+\\bm\{\\beta\}\)and𝐘∈ℝn×d\\mathbf\{Y\}\\in\\mathbb\{R\}^\{n\\times d\}have rows𝐲i\\mathbf\{y\}\_\{i\}\(the target attention outputs from the original cache\)\. The OLS solution𝐂v⋆=\(𝐗⊤​𝐗\)−1​𝐗⊤​𝐘\\mathbf\{C\}\_\{v\}^\{\\star\}=\(\\mathbf\{X\}^\{\\top\}\\mathbf\{X\}\)^\{\-1\}\\mathbf\{X\}^\{\\top\}\\mathbf\{Y\}minimizes‖𝐗𝐂v−𝐘‖F2\\\|\\mathbf\{X\}\\mathbf\{C\}\_\{v\}\-\\mathbf\{Y\}\\\|\_\{F\}^\{2\}\.

For a new query with attention pattern𝐱𝐪∈ℝ1×t\\mathbf\{x\}\_\{\\mathbf\{q\}\}\\in\\mathbb\{R\}^\{1\\times t\}, letP=𝐗⊤​\(𝐗𝐗⊤\)−1​𝐗∈ℝt×tP=\\mathbf\{X\}^\{\\top\}\(\\mathbf\{X\}\\mathbf\{X\}^\{\\top\}\)^\{\-1\}\\mathbf\{X\}\\in\\mathbb\{R\}^\{t\\times t\}denote the projection onto the row space of𝐗\\mathbf\{X\}\. Decompose𝐱𝐪⊤=P​𝐱𝐪⊤\+\(I−P\)​𝐱𝐪⊤\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\top\}=P\\,\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\top\}\+\(I\-P\)\\,\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\top\}, and define the row vectors𝐱𝐪∥=\(P​𝐱𝐪⊤\)⊤\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\parallel\}=\(P\\,\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\top\}\)^\{\\top\}and𝐱𝐪⟂=\(\(I−P\)​𝐱𝐪⊤\)⊤\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\perp\}=\(\(I\-P\)\\,\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\top\}\)^\{\\top\}, so that𝐱𝐪=𝐱𝐪∥\+𝐱𝐪⟂\\mathbf\{x\}\_\{\\mathbf\{q\}\}=\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\parallel\}\+\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\perp\}\. The compacted output is𝐲^=𝐱𝐪​𝐂v⋆=𝐱𝐪∥​𝐂v⋆\+𝐱𝐪⟂​𝐂v⋆\\hat\{\\mathbf\{y\}\}=\\mathbf\{x\}\_\{\\mathbf\{q\}\}\\mathbf\{C\}\_\{v\}^\{\\star\}=\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\parallel\}\\mathbf\{C\}\_\{v\}^\{\\star\}\+\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\perp\}\\mathbf\{C\}\_\{v\}^\{\\star\}\.

By the triangle inequality:

‖𝐲^−𝐲∗‖≤‖𝐱𝐪∥​𝐂v⋆−𝐲∥∗‖\+‖𝐱𝐪⟂​𝐂v⋆‖≤‖𝐱𝐪∥​𝐂v⋆−𝐲∥∗‖\+‖𝐱𝐪⟂‖⋅‖𝐂v⋆‖op,\\\|\\hat\{\\mathbf\{y\}\}\-\\mathbf\{y\}^\{\*\}\\\|\\leq\\\|\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\parallel\}\\mathbf\{C\}\_\{v\}^\{\\star\}\-\\mathbf\{y\}^\{\*\}\_\{\\parallel\}\\\|\+\\\|\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\perp\}\\mathbf\{C\}\_\{v\}^\{\\star\}\\\|\\leq\\\|\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\parallel\}\\mathbf\{C\}\_\{v\}^\{\\star\}\-\\mathbf\{y\}^\{\*\}\_\{\\parallel\}\\\|\+\\\|\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\perp\}\\\|\\cdot\\\|\\mathbf\{C\}\_\{v\}^\{\\star\}\\\|\_\{\\text\{op\}\},\(23\)where‖𝐂v⋆‖op\\\|\\mathbf\{C\}\_\{v\}^\{\\star\}\\\|\_\{\\text\{op\}\}is the operator \(spectral\) norm\. When𝐱𝐪⟂=𝟎\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\perp\}=\\mathbf\{0\}, the second term vanishes\. For𝐱𝐪∥\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\parallel\}: since it lies in the row space of𝐗\\mathbf\{X\}, we can write𝐱𝐪∥=𝝀⊤​𝐗\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\parallel\}=\\bm\{\\lambda\}^\{\\top\}\\mathbf\{X\}for some𝝀∈ℝn\\bm\{\\lambda\}\\in\\mathbb\{R\}^\{n\}, so𝐱𝐪∥​𝐂v⋆=𝝀⊤​𝐗𝐂v⋆\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\parallel\}\\mathbf\{C\}\_\{v\}^\{\\star\}=\\bm\{\\lambda\}^\{\\top\}\\mathbf\{X\}\\mathbf\{C\}\_\{v\}^\{\\star\}\. The residual𝐗𝐂v⋆−𝐘\\mathbf\{X\}\\mathbf\{C\}\_\{v\}^\{\\star\}\-\\mathbf\{Y\}is the OLS fitting error, so𝐱𝐪∥​𝐂v⋆=𝝀⊤​\(𝐘\+\(𝐗𝐂v⋆−𝐘\)\)\\mathbf\{x\}\_\{\\mathbf\{q\}\}^\{\\parallel\}\\mathbf\{C\}\_\{v\}^\{\\star\}=\\bm\{\\lambda\}^\{\\top\}\(\\mathbf\{Y\}\+\(\\mathbf\{X\}\\mathbf\{C\}\_\{v\}^\{\\star\}\-\\mathbf\{Y\}\)\), yielding the stated bound\. ∎

###### Proof of Proposition[C\.4](https://arxiv.org/html/2608.12331#A3.Thmtheorem4)\.

We proceed by induction under the linear error composition model\. At step 1,ε~1=ε1\\tilde\{\\varepsilon\}\_\{1\}=\\varepsilon\_\{1\}\(the error of the first compaction relative to the original cache\)\. Assumeε~k−1\\tilde\{\\varepsilon\}\_\{k\-1\}bounds the step\-\(k−1\)\(k\{\-\}1\)error relative to the original\.

At stepkk, the cache consists of two parts: the step\-\(k−1\)\(k\{\-\}1\)compacted prefix \(with errorε~k−1\\tilde\{\\varepsilon\}\_\{k\-1\}\) and fresh tokens generated since stepk−1k\{\-\}1\(with no compaction error\)\. The fraction of fresh tokens isλk\\lambda\_\{k\}\. Under the linear composition model, the attention output can be decomposed as a weighted sum of the contributions from previously\-compacted tokens and fresh tokens; since softmax is approximately linear for small perturbations when no single token dominates, the inherited error is attenuated by the previously\-compacted fraction\. After step\-kkcompaction with per\-step errorεk\\varepsilon\_\{k\}:

ε~k≤εk\+\(1−λk\)⋅ε~k−1,\\tilde\{\\varepsilon\}\_\{k\}\\leq\\varepsilon\_\{k\}\+\(1\-\\lambda\_\{k\}\)\\cdot\\tilde\{\\varepsilon\}\_\{k\-1\},\(24\)where the\(1−λk\)\(1\-\\lambda\_\{k\}\)factor reflects that only the previously\-compacted fraction propagates old errors, while fresh tokens contribute no inherited error\. Unrolling the recurrence:

ε~K≤∑k=1Kεk⋅∏j=k\+1K\(1−λj\)\.\\tilde\{\\varepsilon\}\_\{K\}\\leq\\sum\_\{k=1\}^\{K\}\\varepsilon\_\{k\}\\cdot\\prod\_\{j=k\+1\}^\{K\}\(1\-\\lambda\_\{j\}\)\.\(25\)Whenλk≥λmin\\lambda\_\{k\}\\geq\\lambda\_\{\\min\}andεk≤εmax\\varepsilon\_\{k\}\\leq\\varepsilon\_\{\\max\}for allkk:

ε~K≤εmax​∑k=1K\(1−λmin\)K−k=εmax⋅1−\(1−λmin\)Kλmin≤εmaxλmin\.\\tilde\{\\varepsilon\}\_\{K\}\\leq\\varepsilon\_\{\\max\}\\sum\_\{k=1\}^\{K\}\(1\-\\lambda\_\{\\min\}\)^\{K\-k\}=\\varepsilon\_\{\\max\}\\cdot\\frac\{1\-\(1\-\\lambda\_\{\\min\}\)^\{K\}\}\{\\lambda\_\{\\min\}\}\\leq\\frac\{\\varepsilon\_\{\\max\}\}\{\\lambda\_\{\\min\}\}\.\(26\)In the periodic regime with intervalPPand target sizett, the cache at compaction has≈t\+P\\approx t\+Ptokens of whichPPare fresh, givingλk≈P/\(P\+t\)\\lambda\_\{k\}\\approx P/\(P\+t\)\.

Connection to TAM\.Under TAM, the per\-step errorεk\\varepsilon\_\{k\}is reduced relative to uniform compaction via pivotal protection \(Proposition[C\.2](https://arxiv.org/html/2608.12331#A3.Thmtheorem2)\) and optimal allocation \(Proposition[C\.1](https://arxiv.org/html/2608.12331#A3.Thmtheorem1)\)\. When the conditionγ\>\|𝒫\|/t\\gamma\>\|\\mathcal\{P\}\|/tholds \(see the remark following Proposition[C\.2](https://arxiv.org/html/2608.12331#A3.Thmtheorem2)\), TAM’s per\-step error satisfiesεkTAM<εkuniform\\varepsilon\_\{k\}^\{\\text\{TAM\}\}<\\varepsilon\_\{k\}^\{\\text\{uniform\}\}, yielding a tighter cumulative bound\. ∎

## Appendix EFull Experimental Results

### E\.1Full Results: Accuracy vs\. Target Size

Table[7](https://arxiv.org/html/2608.12331#A5.T7)reports accuracy and post\-compaction memory across all methods and target compaction ratios on both benchmarks, corresponding to Figure[2a](https://arxiv.org/html/2608.12331#S4.F2.sf1)and Figure[2b](https://arxiv.org/html/2608.12331#S4.F2.sf2)in the main text\.

Table 7:Full results onAIME 2024\(Qwen3\-4B, 30 problems\): accuracy \(%\) / post\-compaction memory \(GB\) at each target compaction ratio\.MethodTarget Compaction Ratio0\.050\.100\.20No Compaction63\.3% / 9\.2 GBEviction \(Selector Window\)33\.3 / 3\.046\.7 / 4\.153\.3 / 5\.7AM \+ Repeat46\.7 / 3\.153\.3 / 4\.256\.7 / 5\.8PAM \(Uniform\)50\.0 / 3\.056\.7 / 4\.060\.0 / 5\.6TAM \(Ours\)53\.3/ 3\.060\.0/ 4\.063\.3/ 5\.6TAM \(Periodic,P=1024P\{=\}1024\)50\.0 /2\.456\.7 /3\.260\.0 /4\.5Table 8:Full results onMATH\-500\(Qwen3\-4B\): accuracy \(%\) / post\-compaction memory \(GB\) at each target compaction ratio\.MethodTarget Compaction Ratio0\.050\.100\.20No Compaction71\.2% / 8\.8 GBEviction \(Selector Window\)38\.4 / 2\.952\.4 / 3\.961\.8 / 5\.4AM \+ Repeat49\.2 / 3\.061\.0 / 4\.066\.2 / 5\.5PAM \(Uniform\)52\.6 / 2\.964\.6 / 3\.868\.4 / 5\.3TAM \(Ours\)56\.0/ 2\.967\.8/ 3\.870\.2/ 5\.3TAM \(Periodic,P=1024P\{=\}1024\)53\.2 /2\.365\.4 /3\.168\.0 /4\.3
### E\.2Selector Window SizeRR

Table[9](https://arxiv.org/html/2608.12331#A5.T9)reports accuracy versus selector window sizeRRunder TAM\. LargerRRprovides more reference queries but increases extraction cost\. We findR=64R\{=\}64to offer a good trade\-off\.

Table 9:Ablation on selector window sizeRR\(TAM, target ratio 0\.1, AIME 2024\)\.WindowRRAcc \(%\)Extract Time \(s\)3256\.70\.464\(default\)60\.00\.812860\.01\.5