✗ Failed on benchmark 2026

Rank-Revealing Representative Tokens

Implementation & benchmark of arXiv:2607.13532 — Computing Strong Rank-Revealing Factorizations for Matrices with Orthonormal Rows

Usefulness7/10

Difficulty5/10

Novelty6/10

Memory Memory Speedup Accuracy Attention Kv cache Memory Transformer Linear algebra Numerical analysis Approximation theory

Source paper: Computing Strong Rank-Revealing Factorizations for Matrices with Orthonormal Rows arXiv:2607.13532 ⓘ · analyzed Aug 30, 2026

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

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.

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.$$

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.

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

Failed on benchmark

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Not reproduced ✗

Stage 2 · Practical benchmark result: Significantly worse ✗

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 8/10

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.

Agent confidence: 8/10

Baseline: At 12.5% cache: random key residual 0.0581, key sigma_min 0.0853, attention error 2.342; leverage key residual 0.0534, key sigma_min 0.0970, attention error 2.405.
Idea: RR key residual 0.0530 and key sigma_min 0.1174, but value residual 0.6487 and attention error 2.825. Core checks: exact-rank residual 6.33e-16; noise residual/epsilon approximately 3.08 for epsilon <= 1e-2; rank 8/10/12 residuals 0.448/0.591/0.665 with k=6.

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.

How to run: python3 experiment.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2607.13532) Sep 2, 2026

Significantly WORSE than the tuned baseline (+65.1%, p=0.0081, wins 0 / 8 paired seeds).

Benchmark: Sequence modeling
Model: transformer_tiny
Paired seeds: 8
Baseline mean: 0.8339
Idea mean: 1.3765
Effect (Δ): 0.5426 (+65.1%; negative = idea better)
Wins: 0 / 8 paired seeds
p-value: 0.0081 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±34.7%
Mechanism: Not confirmed ✗
Practical effect: Hurts
Baseline tuning: swept over 3 configs

Limitations:

The full requested baseline/idea hyperparameter protocol was only partially realized: the baseline swept learning rates, while the idea used three k values at lr=0.003 rather than also running the baseline-best lr and two nearby learning rates. The implementation uses a shared batch-level pivot set and straight-through reconstruction, not a production decoder KV-cache integration; no memory or throughput measurement, residual correction, language-model perplexity, or per-layer causal KV-cache experiment was performed.

How to run: python3 rr_bench.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Aug 31, 2026 latest Failed ✗

Agent confidence: 9/10

Implemented a local rank-revealing representative-token transformer on the structurally matched sequence forecast track and ran the 8-seed paired benchmark. The best reported idea configuration had test MSE 1.3765 versus baseline 0.8339, with paired delta +0.5426 and permutation p=0.0081, so the idea was significantly worse. The nominal zero-residual signature is degenerate because the selected k=32 equals the full 32-token window; compressed k=16 and k=24 were also worse, so no neural-network training win was observed.

Baseline: Best sweep lr=0.001, test MSE mean 0.83386 over 8 seeds; per-seed [0.75903, 0.76029, 0.73261, 1.00138, 0.87364, 0.83181, 0.91628, 0.79583].
Idea: Best tested idea lr=0.003, k=32, test MSE mean 1.37649 over 8 seeds; paired delta +0.54263, p=0.0081, 0/8 wins. Compressed settings: k=16 mean 1.43064 and k=24 mean 1.40122.

Benchmark result