PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yiren Zhao, Guanghui Song, Tianrui Qin, Kejiang Ye, Cheng-zhong Xu, Xitong Gao

arXiv:2610.02815v1cs.AI

TL;DR

Long chain-of-thought decoding grows the KV cache, and eviction may remove historical states that later reasoning needs. iS-KV keeps recent states exact while compressing older states and synchronizing their coordinates with an evolving basis. It achieves strong accuracy at substantial compression and outperforms eviction baselines at matched memory, though the reported OjaKV runs did not yield measured accuracy.

  • Problem

    Long reasoning traces expand KV-cache storage, while eviction can remove historical tokens that later queries may need and fixed-prompt low-rank compression does not address online basis updates.

    Source: §1 · p. 1

  • Method

    iS-KV retains recent states exactly, compresses older states in low-rank K and V representations, and updates their basis and historical coefficients together during decoding.

    Source: §1 · p. 2, §5 · p. 10

  • Results

    On MATH-500, iS-KV achieves 82.6% accuracy at 4.06× persistent-KV compression on DeepSeek-R1-Distill-Llama-8B, close to the original model’s 83.6%, and outperforms R-KV and SnapKV at all six matched-memory operating points.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    Every token position remains available in exact or approximate form, but fixed-rank compression slows rather than eliminates cache growth.

    Source: §1 · p. 2, §5 · p. 10

    All 118 OjaKV generations across three settings fell into repetitive loops and reached the length limit, so the authors report observed failures rather than measured accuracy.

    Source: §4.1 · p. 7

Abstract

from arXiv · show

Long chain-of-thought reasoning substantially increases KV-cache memory during autoregressive decoding, as every generated token introduces new key and value states and causes the cache to grow linearly with decoding length. Existing KV-cache compression methods typically control this growth through token eviction, but irreversible deletion can remove historical states that later reasoning may need to revisit. SVD-based low-rank compression provides an alternative by retaining all positions with a more compact representation. However, extending it from a fixed prompt cache to online decoding is non-trivial. Through our investigation, we find that if the basis is updated for new tokens while old tokens keep their coordinates in the old basis, the stored history drifts substantially. Based on this observation, we propose iS-KV, an online low-rank KV-cache compression method for long-horizon reasoning. iS-KV keeps a recent window exact while incrementally folding older states into bounded-rank representations. As the low-rank basis evolves, it synchronizes historical coordinates with the updated basis to maintain representation consistency. On DeepSeek-R1-Distill-Llama-8B, iS-KV achieves 82.6% accuracy at 4.06-fold persistent-KV compression, close to the original model's 83.6%. On Qwen3-8B, it achieves 89.2% accuracy at 5.64-fold compression. Under matched memory budgets, iS-KV consistently outperforms token-eviction baselines.

1 INTRODUCTION

Long reasoning traces grow the KV cache, while eviction can discard tokens that later become important. iS-KV retains all positions in exact or low-rank form and synchronizes historical coordinates as its basis evolves, outperforming eviction baselines at matched memory.

1 INTRODUCTION

  • Tokens that appear unimportant can regain attention: about 30% of the 75% least-attended tokens receive strong attention again within 8K tokens on AIME, rising to about 60% by 30K.At matched memory, R-KV loses 5.4–11.0 points on DeepSeek-R1-Distill-Llama-8B and 23.0–33.6 on Qwen3-8B.Source: §1 · pp. 1–2
  • Updating the basis without old coefficients changes reconstructed historical states; at step 256, joint updates reduce drift from 1.55 to 0.023 for keys and from 1.40 to 0.051 for values.Generated KV states have low-rank structure, with faster singular-value decay for pre-RoPE keys than for values.Source: §1 · p. 2
  • iS-KV keeps recent states at original precision, compresses older K and V states separately, and updates their bases and historical coefficients together via block incremental SVD.Every token position remains available to future queries, although older states are approximate.Source: §1 · p. 2
  • 82.6% accuracy at 4.06× persistent-KV compression on DeepSeek-R1-Distill-Llama-8B is close to the original model’s 83.6%; iS-KV also beats R-KV and SnapKV at all six matched-memory MATH-500 operating points.On Qwen3-8B, it achieves 89.2% accuracy at 5.64× compression.Source: §1 · pp. 2–3

2 RELATED WORK

Related KV-cache work reduces memory through token selection, changes to attention or quantization, or low-rank representations. iS-KV focuses on coordinating online low-rank updates so historical coordinates remain consistent as new states arrive.

2 RELATED WORK

  • Token-selection methods preserve selected positions but sacrifice historical coverage; iS-KV instead keeps every position in exact or low-rank form, trading representation precision rather than token availability.Examples include H2O, STREAMINGLLM [Xiao et al., 2024], SNAPKV [Li et al., 2024], and R-KV [Cai et al., 2026].Source: §2 · p. 3
  • Attention-efficiency methods and quantization address different costs, while iS-KV targets the number of coordinates stored per historical state without changing the pretrained attention architecture.The paper does not evaluate additional low-bit quantization or serving-system integration.Source: §2 · p. 3
  • Prior low-rank methods study factorization, reduced-space attention, retrieval, or rank choice; iS-KV instead asks how to incorporate decoded states while keeping historical coordinates consistent with an evolving basis.These studies include Palu [Chang et al., 2024], Eigen Attention [Saxena et al., 2024], and SHADOWKV [Sun et al., 2025].Source: §2 · p. 3
  • iS-KV uses Brand’s incremental SVD [Brand, 2002; 2006], a classical decomposition primitive, for coordinated updates of shared historical factors and old coordinates alongside exact recent states.Its contribution is the cache update and its evaluation on long reasoning at matched persistent-memory budgets.Source: §2 · p. 3

3 iS-KV

iS-KV preserves a compact representation of every token position while keeping selected states exact. Its decoding updates historical coordinates with the evolving low-rank basis, then reconstructs positions in token order for attention.

3 iS-KV

  • iS-KV initializes exact states and a low-rank history, then jointly updates the basis and historical coefficients as unprotected rows enter in blocks.The recent window stays exact while older states are folded into a compact low-rank history.Source: §3 · p. 3, Figure 2 · p. 4

3.1 OBJECTIVE AND PREFILL COMPRESSION

  • During prefill, iS-KV partitions positions into exact and compressed sets, stores exact rows unchanged, and approximates the remaining rows with a rank-budgeted truncated SVD.The factorization stores the shared basis and each compressed token’s coefficients in that basis.Source: §3.1 · p. 4

3.2 BLOCK-INCREMENTAL DECODING

  • Every b pending rows, block incremental SVD combines the maintained history approximation and new exact block, updates basis and coefficients together, and computes a small core SVD independent of history length.Residual directions outside the current basis can expand it; the updated coefficients represent both the prior history and incoming block in the new basis.Source: §3.2 · p. 5

3.3 RECONSTRUCTION AND STORAGE COST

  • Reconstruction aligns keys and values by original token position and applies RoPE to keys at those positions; storage grows as O(nr) with history length.At equal rank and precision, each compressed key-value pair uses 2r coefficients rather than 2d scalars, plus shared factors.Source: §3.3 · pp. 5–6

4 EXPERIMENTS

The experiments compare iS-KV with the original model and token-eviction baselines on reasoning accuracy, long-prefill retrieval, and generation efficiency. They also test key/value compression and online basis adaptation through ablations.

4.1 LONG-COT REASONING

  • The released OjaKV checkpoint reaches 62.0% accuracy at approximately 1.30× compression, while higher-compression runs looped to the length limit and were stopped without scored accuracy.By comparison, iS-KV reaches 78.2–82.6% at 4.06–5.92× compression on this model and dataset.Source: §4.1 · pp. 6–7, Table 2 · p. 7
  • 89.2% accuracy at 5.644× compression on Qwen3-8B exceeds matched-memory R-KV’s 68.8%; iS-KV outperforms both eviction baselines at all six MATH-500 model-budget settings.Table 1 matches persistent KV bytes, including protected and exact states, low-rank factors, and baseline staging storage; these ratios do not measure peak GPU-memory savings.Source: §4.1 · p. 6, Table 1 · p. 7

4.4 EFFICIENCY

  • At 32K input, iS-KV uses 1.808 GiB versus the original model’s 4.125 GiB, with 56.2% savings; generation takes 74.70 s versus 68.63 s, an 8.8% overhead.Measurements are single-run results for prefill plus 1,024 decode steps; memory excludes indices, unused capacity, reconstructed caches, and workspace.Source: Figure 4 · p. 8, §4.4 · p. 9

4.1 LONG-COT REASONING

  • At rank 192 on AIME 2024, Qwen3-8B iS-KV reaches 76.7% accuracy versus matched R-KV’s 43.3%, with 23 of 30 correct, matching the original model.On AIME 2025, rank 192 reaches 56.7%, above R-KV’s 40.0% but below the original model’s 63.3%; one answer changes accuracy by 3.3 points.Source: §4.1 · p. 8, Figure 3 · p. 8

4.2 ABLATION STUDY

  • K-only compression answers 68/80 questions versus 67/80 for the original, while V-only and joint K+V compression each answer 65/80.The comparison fixes per-path rank rather than total memory, and the one-question K-only difference does not establish an improvement.Source: §4.2 · p. 8, Table 3 · p. 8
  • Freezing both bases at their prompt initialization reduces the score from 65/80 to 51/80, a 17.5-point drop under the same rank and recent-window settings.The answer-level ablation complements reconstruction-drift measurements for unsynchronized historical coordinates.Source: §4.2 · pp. 8–9

4.3 LONG PREFILL EVALUATION

  • At rank 160, iS-KV matches original-model scores of 100.0 on RULER’s S1–S3 tasks, while its mean scores are 87.8, 86.3, and 79.0 across the three evaluated models.The rank-96 and rank-160 configurations use different update and recent-window settings, so this is not a rank-only comparison; the evaluation measures retrieval from compressed 64K prompts.Source: §4.3 · p. 9, Table 4 · p. 9

5 CONCLUSION

Long reasoning grows the KV cache, while eviction can discard tokens that later reasoning may need. iS-KV retains every position, compresses older states, and updates historical coordinates with the evolving basis.

5 CONCLUSION

  • iS-KV keeps every token position, storing recent states exactly and older states compactly rather than deleting them.Memory still grows with trace length, although the cost of each stored token is lower.Source: §5 · p. 10
  • Block-incremental SVD updates the basis and old coordinates together to preserve the consistency of the stored history.Source: §5 · p. 10
  • The conclusion frames faithful representation of every token—not only choosing which tokens to keep—as the cache-compression challenge.Source: §5 · p. 10

A IMPLEMENTATION DETAILS AND REPRODUCIBILITY

The appendix collects implementation and reproducibility details across method settings, evaluation protocols, probes, block-update properties, and numerical diagnostics.

A IMPLEMENTATION DETAILS AND REPRODUCIBILITY

A.1 METHOD SETTINGS

The method settings specify exact recent windows, bounded ranks, precision and reorthogonalization choices, prompt protection, cache-update schedules, and residual-basis construction.

A.1 METHOD SETTINGS

  • The main configuration uses exact recent windows of 128 rows, block size 64, residual tolerance τ = 10^-6, and a per-update rank budget.MATH-500 uses ranks 64, 96, and 128 on both models.Source: §A.1 · p. 12
  • Persistent factors and diagonal singular values are stored in FP16, while projection, residual QR, core SVD, reorthogonalization, and reconstruction use FP32.Reorthogonalization runs after every 256 rows processed by regular block updates; optional prompt sketches, residual corrections, historical-token scoring, and integer quantization are disabled.Source: §A.1 · p. 12
  • Prompt keys are protected by selecting low-cosine-similarity chunks and a local suffix, while values near protected keys also remain exact.The latest 128 prompt values initialize the exact recent window; the 64K RULER evaluation uses the same protection rule.Source: §A.1 · p. 12
  • Decoded keys and values enter exact buffers, and the oldest eligible rows are folded into low-rank history in 64-row blocks.Before regular value updates, the first refit waits until rV unprotected rows have left the recent window and recomputes a truncated SVD with rank budget rV.Source: §A.1 · p. 12
  • Residual directions are retained only when their singular values exceed the numerical threshold, with no residual basis when the residual is small or the rank reaches d.The threshold is τeff = max(τ, ϵ max(b, d)∥F∥F), and the retained basis has p ≤ min(d − k, b) directions.Source: §A.1 · p. 12

A.2 EVALUATION PROTOCOLS

The evaluation protocols specify shared MATH-500 conditions, memory accounting, matched-budget comparisons, and settings for ablations and RULER. They also document scope boundaries, including factor overflow at long generation budgets.

MATH-500

  • The original model, iS-KV, and R-KV use the same MATH-500 questions, prompts, seeds, and evaluator, with one generation for each of 500 questions.Runs use BF16, temperature 0.6, top-p 0.95, top-k 50, and a 16,384-token maximum total length.Source: §A.2 · p. 12

Memory accounting

  • Persistent analytical cache bytes include factor-layout storage but exclude temporary reconstruction tensors and model weights; no throughput or peak-HBM advantage is claimed.The implementation has no fused factor-aware attention kernel.Source: §A.2 · p. 13

R-KV matching

  • On DeepSeek-R1-Distill-Llama-8B, matched R-KV budgets yield iS-KV accuracy advantages of 4.4, 5.4, and 5.6 points at 4.060×, 4.813×, and 5.920× compression.On Qwen3-8B, rank-96 iS-KV and R-KV compression is 5.6442× and 5.6410×, a relative mismatch of 0.056%.Source: §A.2 · p. 13

OjaKV evaluation

  • The released OjaKV checkpoint answers 310/500 questions correctly at approximately 77% of the original model’s persistent KV storage.Reduced-rank runs targeting higher compression were stopped after repetitive outputs reached the length limit without EOS, and were not scored.Source: §A.2 · p. 13

Component ablation

  • The key/value and frozen-basis ablations use a fixed prefix of 80 MATH-500 questions on DeepSeek-R1-Distill-Llama-8B.Compressed variants use rank 96, exact recent windows of 128 rows, block size 64, and reorthogonalization every 256 folded rows.Source: §A.2 · p. 13

RULER

  • The 64K RULER rank-96 evaluation uses exact recent windows of 128 rows, 16-row folds, and reorthogonalization every 32 folded rows; each task has ten examples.Source: §A.2 · p. 13

Factor precision

  • At a 32,768-token Qwen3-8B generation budget, FP16 factors overflow and turn logits into NaN, so all 32K experiments use BF16 factors.BF16 and FP16 use the same two bytes, but the 32K results are reported as a separate configuration and MATH-500 is not rerun in BF16.Source: §A.2 · p. 13

A.3 PROBE SETTINGS

The appendix specifies settings for the attention-recurrence, spectral-decay, and update-rule probes, plus fidelity probes of cache factors and model outputs.

A.3 PROBE SETTINGS

  • Figure 1(a) ranks tokens by mean attention over the preceding 32 steps at decode step 1024 and marks the bottom 75%.The panel uses the longest trace from each model and task; marked tokens are not removed.Source: §A.3 · pp. 13–14
  • Figure 1(b) measures normalized singular-value decay on four 8K-token AIME 2024 traces per model, taking medians over layers and traces.Panels (a) and (b) show two-model means and ranges, not confidence intervals.Source: §A.3 · p. 14
  • The update-rule probe compares stale-coordinate and synchronized Brand updates on three DeepSeek traces, while end-to-end probes measure teacher-forced logit and token-prediction changes.The update-rule probe uses layers 0, 15, and 31, rank 32, and 64-row blocks; end-to-end probes use rank-96 and rank-64 caches.Source: §A.3 · p. 14

A.4 PROPERTIES OF THE BLOCK UPDATE

The block update incorporates arriving rows through a small core SVD, with exact-arithmetic guarantees qualified by residual-basis completeness and accumulated approximation history.

A.4 PROPERTIES OF THE BLOCK UPDATE

  • Without truncation, the block update exactly incorporates the arriving block when the residual basis spans the complete residual row space.The construction decomposes the block into components in the existing basis and the orthogonal residual basis.Source: §A.4 · p. 14
  • Retaining the core SVD's leading components gives the best rank-limited reconstruction locally for the maintained history and arriving block.This is not necessarily the rank-r SVD of the original uncompressed history after earlier approximations.Source: §A.4 · pp. 14–15
  • When the residual basis is incomplete, discarded core singular values alone do not characterize the full update error.The result relies on decomposing error into orthogonal components inside and outside the retained feature subspace.Source: §A.4 · pp. 14–15
  • Periodic reorthogonalization preserves the represented product in exact arithmetic, while finite-precision storage adds rounding error.The reorthogonalized factors are orthonormal up to computation roundoff before storage casting.Source: §A.4 · p. 15
  • For block size b, width d, rank r, and n factorized rows, historical-coefficient updates cost O(nr(r + b)) and persistent factor storage costs O((n + d)r).Projection and residual computation require O(bdr) work; periodic reorthogonalization adds work depending on n.Source: §A.4 · p. 15

A.5 NUMERICAL DIAGNOSTICS

The numerical diagnostics report bounded drift on a long trajectory, large errors from an invalid residual threshold, and orthogonality and spectral results that inform implementation settings.

A.5 NUMERICAL DIAGNOSTICS

  • With an invalid oversized residual threshold, value drift reaches 0.961 and 0.906, versus 0.0001 and 0.0109 for the stable update at the same points.The comparison is at step 1,024, layer 0, and step 2,048, layer 15; these probes assess update fidelity, not original-cache error or generation quality.Source: §A.5 · p. 15
  • At step 8,192, key-path excess error stays within 0.007 and value-path excess error within 0.016–0.021 on one AIME 2024 trajectory.The trajectory has 8,192 decoded rows, FP16 persistent factors, and reorthogonalization every 256 folded rows; values are more constrained than keys.Source: §A.5 · p. 15, Table 5 · p. 15
  • Reorthogonalization reduces layer-15 rank-128 basis orthogonality error from 9.5 × 10^-3 to 1.1 × 10^-3, with median represented-product change of 2.4 × 10^-4.Within 8K steps it does not reduce reconstruction error, but keeps bases orthogonal to guard against error build-up in longer generations.Source: §A.5 · p. 15
  • Beyond layer 3, r99% varies across depth, spanning 122–338, while energy retained at rank 128 has coefficient of variation ≤0.023 for keys and ≤0.055 for values.The r99% coefficient of variation is 0.19 for DeepSeek-R1-Distill-Llama-8B and 0.26 for Qwen3-8B; stable energy retention supports one rank setting across layers.Source: §A.5 · p. 16

B ALGORITHMS

The algorithms initialize an exact-and-compressed cache at prefill, then fold eligible rows into low-rank histories during decoding and reconstruct states for attention.

B ALGORITHMS

  • Prefill computes exact causal attention, selects protected key and value positions, initializes recent windows, and factorizes the remaining rows at their rank budgets.Protected values include positions within ρ tokens of protected keys; recent windows begin with the last min(w, L) prompt positions.Source: B ALGORITHMS · p. 16
  • The prefill cache stores protected and recent rows exactly, while the remaining prompt positions are represented by truncated-SVD factors with original indices retained.The output of prefill does not depend on the compressed representation.Source: B ALGORITHMS · p. 16
  • At each decoding step, new rows stay exact as windows advance, and unprotected rows leaving them enter FIFO queues for block updates.An empty history starts with truncated SVD; regular updates use synchronized block-incremental SVD, with a one-time value refit before regular value updates.Source: B ALGORITHMS · pp. 16–17
  • The decoding procedure periodically reorthogonalizes factors, moves folded positions into the compressed set, and keeps protected, recent, and queued positions exact.Queue occupancy determines update timing, and the residual threshold controls the residual basis.Source: B ALGORITHMS · pp. 16–17
  • For attention, the algorithm reconstructs keys and values in token order, restores head dimensions, applies RoPE at original positions, and computes the output.The reconstruction and attention calculations use Equations (5) and (6).Source: B ALGORITHMS · pp. 16–17
Loading 2610.02815v1…