# Rank-Revealing Representative Tokens

- ID: 868
- Canonical URL: https://synthcore.org/idea/868/rank-revealing-representative-tokens
- API JSON: https://synthcore.org/api/idea/868.json
- API Markdown: https://synthcore.org/api/idea/868.md
- Verification status: failed_benchmark
- Source: [arXiv:2607.13532](https://arxiv.org/abs/2607.13532)
- Category: memory
- Solves: memory, speedup, accuracy
- ML areas: attention, kv-cache, memory, transformer
- Math tags: linear-algebra, numerical-analysis, approximation-theory
- Ratings: usefulness 7/10; difficulty 5/10; novelty 6/10

## Idea description

Compress a transformer KV cache by selecting actual past tokens whose key or hidden-state columns form a stable basis for all cached tokens. Instead of retaining tokens with the largest attention scores or leverage scores independently, compute rank-revealing pivoting of the leading right-singular-vector matrix and retain its pivot columns, then evaluate attention using the representatives plus an optional low-cost residual correction.

## Mathematical statement

The paper evaluates a column subset \(\mathcal C\subseteq[n]\), with \(|\mathcal C|=k\), using both projection error \(\|A-P_{\mathcal C}A\|_{\{2,F\}}\) and conditioning of the selected basis \(\sigma_{\min}(A(:,\mathcal C))\). Here \(A\in\mathbb R^{m\times n}\) is a matrix whose columns are token representations, \(A(:,\mathcal C)\) is the submatrix formed by selected columns, \(P_{\mathcal C}=A(:,\mathcal C)A(:,\mathcal C)^+\) is the orthogonal projector onto their span, \(\|\cdot\|_2\) and \(\|\cdot\|_F\) are spectral and Frobenius norms, and \(\sigma_{\min}\) is the smallest singular value. GKS first computes the leading \(k\) right singular vectors \(V_k\in\mathbb R^{n\times k}\) of \(A\). Since \(V_k^TV_k=I_k\), the matrix \(B=V_k^T\in\mathbb R^{k\times n}\) has orthonormal rows. Stewart-style rank-revealing pivoting chooses \(k\) columns of \(B\); the same pivot indices choose columns of \(A\). The mechanism is that a well-conditioned \(B(:,\mathcal C)\) means the selected actual tokens cover the dominant rank-\(k\) subspace while avoiding redundant representatives. The implementation should monitor both \(\|A-P_{\mathcal C}A\|_F\) and \(\sigma_{\min}(A(:,\mathcal C))\), not only attention scores.

## Key formulas

- $$\|A-P_{\mathcal C}A\|_{\{2,F\}},\qquad P_{\mathcal C}=A(:,\mathcal C)A(:,\mathcal C)^+.$$
- $$\sigma_{\min}\!\left(A(:,\mathcal C)\right).$$
- $$A\approx U_k\Sigma_kV_k^T,\qquad B=V_k^T\in\mathbb R^{k\times n},\qquad BB^T=I_k,$$
- $$\mathcal C=\operatorname{pivots}_k(B),\qquad \widehat A=A(:,\mathcal C)\left(A(:,\mathcal C)^+A\right),\qquad E=A-\widehat A.$$

## Implementation notes

Integrate this at inference time in a decoder transformer immediately after each layer has produced a candidate KV cache, or first prototype it on hidden states. For a sequence of length \(n\), construct \(A\in\mathbb R^{d\times n}\) by stacking key vectors, value vectors, or projected hidden states as columns. Choose target cache size \(k\). Compute a randomized or deterministic rank-\(k\) SVD, retaining \(V_k\in\mathbb R^{n\times k}\), and set \(B=V_k^T\). Run column-pivoted QR on \(B\): initialize an empty pivot set \(\mathcal C\), repeatedly choose the unused column with the largest residual norm after projection onto the already selected columns, append its index, and update the QR factors. For a closer Stewart-style implementation, permit swaps whenever a nonselected column would increase the smallest singular value of \(B(:,\mathcal C)\) or improve the current QR diagonal; stop when no swap improves the objective by more than \(10^{-3}\). Retain the corresponding K/V entries and use them in attention. Compute from the mathematics: \(V_k\), pivot indices, projection coefficients, reconstruction residual, and \(\sigma_{\min}(A(:,\mathcal C))\). Estimate empirically: the usable rank \(k\), swap tolerance, and whether keys, values, or concatenated key-value features work best. The first cheap experiment is a 2-layer GPT-style model on WikiText-2 or C4 with sequence length 512, comparing full KV cache, attention-score top-\(k\), leverage-score top-\(k\), ordinary pivoted QR, and rank-revealing pivoting at 25%, 50%, and 75% cache sizes. Measure peak KV memory, decode tokens per second, perplexity, attention-output error, normalized projection residual \(\|A-P_{\mathcal C}A\|_F/\|A\|_F\), and selected-basis conditioning. Success is lower perplexity at equal cache size, or at least 2x lower KV memory at iso-perplexity, without very small \(\sigma_{\min}\) values that produce unstable reconstruction.

## Verification

- Status: failed_benchmark
- Mechanism evidence: yes
- Mechanism confirmed: no
- Practical verdict: harms
- Verdict: Implemented rank-revealing representative selection using leading right-singular vectors and greedy residual-norm pivoting. The mechanism manifested: exact-rank projection residual was approximately zero, residual scaled linearly with additive noise, and a clear positive-residual transition occurred when true rank exceeded the cache size. In the mini attention test, RR improved key projection residual and conditioning versus baselines but worsened single-query attention error, so no end-to-end inference win was observed.

### Mechanism check

- Verdict: Implemented rank-revealing representative selection using leading right-singular vectors and greedy residual-norm pivoting. The mechanism manifested: exact-rank projection residual was approximately zero, residual scaled linearly with additive noise, and a clear positive-residual transition occurred when true rank exceeded the cache size. In the mini attention test, RR improved key projection residual and conditioning versus baselines but worsened single-query attention error, so no end-to-end inference win was observed.
- Confidence: 8/10
- Limitations: Only synthetic matrices and a single-query attention comparison were tested. No real transformer, WikiText perplexity, decode throughput, GPU memory measurement, concatenated K/V selection, swaps beyond greedy pivoting, or optional residual correction was evaluated.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0081
- Paired wins: 0/8
- Benchmark verdict: idea worse (significant)

## Artifacts

- [REPORT.md](https://synthcore.org/code/351/REPORT.md)
- [bench_report.json](https://synthcore.org/code/351/bench_report.json)
- [experiment.py](https://synthcore.org/code/351/experiment.py)
- [report.md](https://synthcore.org/code/351/report.md)
- [report_bench_2026-08-31T021731.md](https://synthcore.org/code/351/report_bench_2026-08-31T021731.md)
- [results.json](https://synthcore.org/code/351/results.json)
- [rr_bench.py](https://synthcore.org/code/351/rr_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/351)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.