△ Mechanism confirmed, baseline not beaten 2026

Residual-Pivoted Kernel Attention

Implementation & benchmark of arXiv:2608.20633 — A new analysis of the randomly pivoted Cholesky algorithm

Usefulness7/10

Difficulty5/10

Novelty5/10

Architecture Speedup Memory Accuracy Attention Transformer Inference speedup Kv cache Linear algebra Probability Numerical analysis Optimization

Source paper: A new analysis of the randomly pivoted Cholesky algorithm arXiv:2608.20633 ⓘ · analyzed Sep 1, 2026

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

Idea description

Replace full PSD self-attention with a pivoted Cholesky/Nyström approximation whose landmarks are sampled from the unexplained diagonal mass. Tokens with large residual self-similarity are more likely to become landmarks, so the rank budget is spent on difficult regions rather than uniformly selected tokens.

Formulas

$$\Pr\{s_i=t\}=\frac{A_{tt}-\widehat A^{(i-1)}_{tt}}{\operatorname{tr}(A-\widehat A^{(i-1)})}=\frac{R^{(i-1)}_{tt}}{\operatorname{tr}(R^{(i-1)})}.$$

$$u_i=\frac{R^{(i-1)}_{:,s_i}}{\sqrt{R^{(i-1)}_{s_i,s_i}}},\qquad \widehat A^{(i)}=\widehat A^{(i-1)}+u_i u_i^*,\qquad R^{(i)}=R^{(i-1)}-\frac{R^{(i-1)}_{:,s_i}R^{(i-1)}_{s_i,:}}{R^{(i-1)}_{s_i,s_i}}.$$

$$K_{ab}=\exp\!\left(\frac{q_a^Tq_b}{\tau}\right),\qquad K\approx UU^T,\qquad \operatorname{Attn}(Q,V)\approx \operatorname{diag}(U(U^T\mathbf 1))^{-1}U(U^TV).$$

$$\text{number of pivots}=O\!\left(\frac{r}{\varepsilon}+r\sqrt{\log r}\right)\quad\text{for a target }(1+\varepsilon)\text{-relative low-rank error}.$$

Mathematical statement

Let A be an N-by-N positive-semidefinite matrix, let \widehat A^{(i-1)} be the current rank-(i-1) approximation, and define the PSD residual R^{(i-1)}=A-\widehat A^{(i-1)}. The paper samples pivot s_i with probability R^{(i-1)}_{s_i s_i}/tr(R^{(i-1)}). The selected residual column is normalized as u_i=R^{(i-1)}_{:,s_i}/sqrt(R^{(i-1)}_{s_i s_i}), and the approximation is updated by \widehat A^{(i)}=\widehat A^{(i-1)}+u_i u_i^*. Equivalently, R^{(i)}=R^{(i-1)}-R^{(i-1)}_{:,s_i}R^{(i-1)}_{s_i,:}/R^{(i-1)}_{s_i s_i}. For attention, use tied query/key vectors q_a and the PSD exponential kernel K_{ab}=exp(q_a^Tq_b/tau), where tau>0 is temperature. After r pivots, K is approximated by UU^T. The normalized kernel attention output for value matrix V is approximated by diag(U(U^T 1))^{-1}U(U^T V). The paper's complexity claim is O(r/epsilon+r sqrt(log r)) steps for a (1+epsilon)-relative rank-r approximation, motivating residual sampling as an efficient landmark-selection rule.

Implementation notes

Integrate this into the self-attention forward pass for inference, initially in a single-head or small multi-head transformer. Use tied query/key projections in the first experiment so that K_ab=exp(q_a^Tq_b/tau) is a valid PSD exponential dot-product kernel. Given Q in R^{n x d} and V in R^{n x d_v}, choose a rank budget r. Initialize residual diagonal rho_j=K_jj. For i=1,...,r, sample landmark s with probability rho_s/(sum_j rho_j), compute the kernel column c=K[:,s] from Q and q_s, compute the current approximation at that column as z=U U[s,:]^T, set w=(c-z)/sqrt(max(rho_s,delta)), append w to U, and update rho=max(rho-w^2,0) elementwise, with delta=1e-8 for numerical stability. Each kernel column costs O(nd), and the algorithm need not materialize the full n-by-n matrix. After r pivots, compute numerator=U@(U.T@V) and denominator=U@(U.T@ones(n)); return numerator/(denominator+delta). For autoregressive decoding, select pivots once per prompt or refresh them per token block, and cache U instead of the full attention matrix. Compare exact softmax attention against uniform Nyström landmarks and ordinary random landmarks at matched rank and kernel evaluations. Estimate output error using ||KV-K_hat V||_F/||KV||_F on held-out sequences, and record latency, peak memory, and perplexity. Begin with a 2-layer transformer on WikiText-2 at sequence lengths 512 and 2048 and ranks 32, 64, and 128. Success is lower attention-output error or perplexity than uniform Nyström at equal rank, or equal perplexity with at least 2x lower attention memory and measurable inference speedup.

Verification

Mechanism confirmed, baseline not beaten

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: No measurable effect

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

Built residual-diagonal sampled pivoted-Cholesky kernel attention with normalized low-rank output, plus uniform Nyström and random-column baselines. All three mechanism predictions were confirmed: expected trace-decrease errors were 1.27%, 0.43%, and 0.17%; diagonal-selection bias increased with spread; and an exact rank-8 PSD matrix reached 2.5e-15 relative residual after 8 pivots. In the synthetic attention test, residual pivoting had lower relative output error than both baselines at every tested rank, but this is not evidence of an end-to-end speed or memory win.

Agent confidence: 8/10

Baseline: Uniform Nyström relative attention-output error: rank 8 55.7052, rank 16 19.4916, rank 32 6.7003. Random-column errors: 1.5512, 1.6235, 1.6475.
Idea: Residual-pivot relative attention-output error: rank 8 1.0895, rank 16 0.6777, rank 32 0.3256. Mechanism checks: trace identity relative discrepancies 1.27%, 0.43%, 0.17%; diagonal-bias ratios to uniform 1.000, 1.085, 1.682, 3.070; rank-8 termination residual 2.54e-15.

Limitations: Only a small synthetic N=128 attention experiment was tested. The kernel and full ground-truth matrix were materialized for evaluation; streaming kernel-column computation, GPU fallback, peak memory, wall-clock speedup, autoregressive decoding, transformer loss/perplexity, WikiText-2, and sequence lengths 512/2048 were not tested. The normalized low-rank factor can have signed entries, making denominators numerically fragile; no stabilization study beyond a small epsilon was performed.

How to run: python3 experiment.py

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

Ahead of the baseline (−1.1%) but not statistically significant (p=0.8406, wins 4 / 8 paired seeds).

Benchmark: Sequence modeling
Model: transformer_tiny
Paired seeds: 8
Baseline mean: 1.035
Idea mean: 1.0233
Effect (Δ): -0.0117 (−1.1%; negative = idea better)
Wins: 4 / 8 paired seeds
p-value: 0.8406 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±14.3%
Mechanism: Confirmed ✓
Practical effect: No effect
Baseline tuning: swept over 3 configs

Limitations:

The benchmark was reduced to 200 training samples, 100 test samples, 3 epochs, and rank 4 after the original larger run exceeded 40 minutes. Only the built-in sequence forecast track was tested; no long-context, autoregressive decoding, peak-memory, latency, perplexity, or ranks 32/64/128 measurements were run.

How to run: python3 stage2_bench.py

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

Stage 2 — Benchmark Sep 1, 2026 latest Failed ✗

Agent confidence: 9/10

Implemented Residual-Pivoted Kernel Attention as a local replacement for transformer self-attention on the structurally matched sequence forecast task. The trained-model mechanism signature confirmed the predicted trace-decrease identity with 0.07% relative error, but the idea had mean test MSE 1.023332 versus 1.034990 for the tuned exact-attention baseline; paired delta was -0.011658 with permutation p=0.84055, so there was no significant win.

Baseline: Exact transformer attention, tuned lr=0.001: mean test MSE 1.034990, std 0.096300. Sweep means: lr=0.001 1.003167, lr=0.003 2.889053, lr=0.01 10.712081.
Idea: Residual-pivoted exponential-kernel attention, rank=4, lr=0.001: mean test MSE 1.023332, std 0.090481. Sweep means: lr=0.001 1.023332, lr=0.003 4.040841, lr=0.01 6.475607. Paired delta=-0.011658, 4/8 wins, p=0.84055.

Benchmark result