iS-KV: Online Low-Rank KV Cache Compression via Block-Incremental SVD

Summary (Overview)

• Novel approach to KV cache compression: iS-KV retains every token position during long chain-of-thought (CoT) reasoning by storing older states in bounded-rank low-rank representations instead of evicting tokens, while keeping recent states at full precision.

• Key insight on basis drift: The authors demonstrate that when the low-rank basis is updated for new tokens but old tokens' coordinates remain in the old basis, the stored history drifts substantially (drift of 1.55 for keys and 1.40 for values at step 256). iS-KV solves this by jointly updating both the basis and historical coordinates via block-incremental SVD.

• Superior reasoning accuracy: On MATH-500, iS-KV achieves 82.6% accuracy at 4.06× compression on DeepSeek-R1-Distill-Llama-8B (close to the original's 83.6%) and 89.2% at 5.64× compression on Qwen3-8B, consistently outperforming token-eviction baselines (R-KV, SnapKV) at all six matched-memory operating points.

• Token importance is unpredictable: The paper shows that ~30% of the 75% least-attended tokens at step 1024 receive strong attention again within the next 8K tokens on AIME benchmarks, growing to ~60% by 30K tokens—motivating the need to retain all positions.

• Broad evaluation: The method is validated on reasoning benchmarks (MATH-500, AIME 2024/2025), long-input retrieval (RULER at 64K context), and efficiency measurements, with ablations confirming the critical role of online basis adaptation.

Introduction and Theoretical Foundation

Background and Motivation

Long chain-of-thought (CoT) reasoning significantly increases KV-cache memory during autoregressive decoding. Each generated token introduces new key and value states, causing the cache to grow linearly with decoding length. This creates a fundamental tension: reducing KV storage cost during decoding without losing information that later reasoning may need.

Two Key Observations

1. Old tokens can become important again: A token that receives little attention at the current step may receive strong attention thousands of tokens later. Once evicted, it cannot be recovered. The paper demonstrates this with R-KV, which reduces MATH-500 accuracy from 94.4% to 68.8% at ~5.6× compression on Qwen3-8B.

2. KV states have strong low-rank structure: Generated KV states exhibit significant low-rank structure (particularly keys before rotary positional embeddings), enabling compression without deletion.

The Basis Drift Problem

The central theoretical challenge: when the low-rank basis evolves as new tokens arrive, the coefficients of previously compressed tokens (computed in the old basis) must be updated accordingly. Otherwise, the same coefficients represent different vectors under the new basis, causing the stored history to drift from its true representation.

Theoretical Foundation

The optimization objective for compressing a set of rows $X_{\mathcal{C}_X} \in \mathbb{R}^{n_X \times d}$ with rank budget $r_X$ is:

$$\min_{\widehat{X}_{\mathcal{C}_X} \in \mathbb{R}^{n_X \times d}} \|X_{\mathcal{C}_X} - \widehat{X}_{\mathcal{C}_X}\|_F^2 \quad \text{s.t. } \operatorname{rank}(\widehat{X}_{\mathcal{C}_X}) \leq r_X$$

The truncated SVD, denoted by $(U_X, \Sigma_X, B_X) = \mathrm{SVD}_{r_X}(X_{\mathcal{C}_X})$, retains the leading $k_X = \min(r_X, n_X, d)$ singular components, where $U_X$ and $B_X$ contain orthonormal left/right singular vectors and $\Sigma_X$ is diagonal with retained singular values.

Methodology

Architecture Overview

iS-KV maintains two components for each K/V path:

• Exact recent window: The most recent $w$ tokens stored at original precision
• Low-rank history: Older tokens folded into compact representations with rank budget $r_X$

Prefill Compression

1. Key protection: For each chunk $c$ and KV head $h$, score by minimum cosine similarity: $s_{c,h} = \min_{i \in c} \cos(k_{i,h}^{\mathrm{rot}}, \bar{k}_{c,h}^{\mathrm{rot}})$. Select up to $m$ lowest-scoring chunks per head as outlier chunks; the union of their positions plus a local suffix defines protected positions $\mathcal{P}_K$.

2. Value protection: $\mathcal{P}_V$ includes all positions within $\rho$ tokens of any position in $\mathcal{P}_K$.

3. Initial factorization: Remaining rows are factorized via truncated SVD.

Block-Incremental Decoding Updates

For each regular update, given history $A = U\Sigma B^\top \in \mathbb{R}^{n \times d}$ with $k \leq r$ components and pending block $F \in \mathbb{R}^{b \times d}$, the goal is:

$$\min_{\widehat{M} \in \mathbb{R}^{(n+b) \times d}} \|M - \widehat{M}\|_F^2 \quad \text{s.t. } \operatorname{rank}(\widehat{M}) \leq r$$

where $M = [A; F]$. The update procedure:

1. Compute residual basis: $\mathbf{E} = \mathbf{F} - (\mathbf{F}\mathbf{B})\mathbf{B}^\top$, then construct residual basis $P$ via QR and SVD
2. Express history and block in augmented basis $[B \: P]$:

$$M \approx \begin{bmatrix} U & 0 \\ 0 & I_b \end{bmatrix} Z [B \: P]^\top, \qquad Z = \begin{bmatrix} \Sigma & 0 \\ FB & FP \end{bmatrix}$$

3. Compute core SVD: $(G, \Sigma^+, H) = \mathrm{SVD}_r(Z)$, giving updated factors:

$$U^+ = \begin{bmatrix} U & 0 \\ 0 & I_b \end{bmatrix} G, \qquad B^+ = [B \: P]H$$

This reduces the SVD to a $(k+b) \times (k+p)$ core, independent of history length $n$.

Reconstruction and Storage

The reconstructed cache $\widetilde{X}$ at position $i$ is:

$$\widetilde{X}[i] = \begin{cases} (U_X\Sigma_X B_X^\top)[j], & i = \mathcal{C}_X[j], \\ X_{\mathrm{exact}}[i], & i \in \mathcal{E}_X \end{cases}$$

Per-layer persistent storage cost:

$$M_{iS-\mathrm{KV}} = \beta_f \sum_{X \in \{K, V\}} k_X(n_X + d + 1) + \beta_e d \sum_{X \in \{K, V\}} e_X$$

where $\beta_f$ and $\beta_e$ are bytes per scalar for factors and exact rows, respectively.

Empirical Validation / Results

MATH-500 Reasoning Accuracy

Table 1: MATH-500 accuracy at matched persistent-KV footprints

Key findings:

• iS-KV outperforms both eviction baselines at all six reported model–budget settings
• Accuracy degrades gradually with decreasing rank (4.4 points on DeepSeek, 4.2 on Qwen3 from rank 128→64)
• Gains over R-KV range from 5.4 to 5.6 percentage points at higher compression

AIME Results

On Qwen3-8B with 32,768-token limit:

• AIME 2024: At rank 192, iS-KV answers 23/30 correctly (76.7%), matching the original model, versus 43.3% for matched-memory R-KV
• AIME 2025: Rank 192 achieves 56.7%, above R-KV's 40.0% but below original's 63.3%

Comparison with OjaKV

The released OjaKV checkpoint achieves only 62.0% at ~1.30× compression, and all 118 generations at reduced ranks fell into repetitive loops reaching the length limit without EOS.

Ablation Study

Table 3: Component ablation on fixed 80-question MATH subset

Critical finding: Keeping bases fixed reduces accuracy by 17.5 percentage points, confirming the necessity of online basis adaptation.

Efficiency Results

• Generation time: iS-KV takes 47.45s vs 38.83s (original) at 8K input, with overhead decreasing from 22.2% to 8.8% as input length grows to 32K
• Memory savings: 33.7% at 8K, 44.2% at 16K, and 56.2% at 32K

Theoretical and Practical Implications

Theoretical Contributions

1. Basis-coordinate synchronization: The paper establishes that updating the basis without updating historical coordinates causes representation drift, and provides a mathematically grounded solution via block-incremental SVD that maintains consistency.

2. Computational efficiency: The core SVD is independent of history length $n$, operating on a $(k+b) \times (k+p)$ core, making online updates tractable for long sequences.

3. Storage scaling: Storage grows as $O(nr)$ with history length rather than $O(nd)$, providing a tunable trade-off between fidelity and memory.

Practical Implications

1. Token eviction is fundamentally limited: The empirical demonstration that ~60% of low-attention tokens regain importance within 30K tokens challenges the core assumption of eviction-based methods.

2. Value compression is more challenging: Values decay more slowly in singular values and are harder to compress than keys, suggesting asymmetric rank allocations may be beneficial.

3. Long-prompt compression remains difficult: RULER results show more significant degradation on multi-value and multi-query retrieval at 64K context, indicating room for improvement in prompt-history compression.

Conclusion

iS-KV demonstrates that compressing a growing KV cache is fundamentally a problem of representing every token faithfully, not just choosing which tokens to keep. By jointly updating the low-rank basis and historical coordinates through block-incremental SVD, the method achieves near-original accuracy at 4–7× compression on long-horizon reasoning tasks, consistently outperforming token-eviction baselines at matched memory budgets.

Future directions suggested by the work include:

• Improving value compression, which remains more challenging than key compression
• Reducing the remaining accuracy gap at higher compression ratios
• Addressing long-prompt compression scenarios where the entire prompt exceeds the exact-recent window
• Potential integration with quantization and serving systems for additional memory savings