# Residual-Pivoted Kernel Attention

- ID: 2626
- Canonical URL: https://synthcore.org/idea/2626/residual-pivoted-kernel-attention
- API JSON: https://synthcore.org/api/idea/2626.json
- API Markdown: https://synthcore.org/api/idea/2626.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2608.20633](https://arxiv.org/abs/2608.20633)
- Category: architecture
- Solves: speedup, memory, accuracy
- ML areas: attention, transformer, inference-speedup, kv-cache
- Math tags: linear-algebra, probability, numerical-analysis, optimization
- Ratings: usefulness 7/10; difficulty 5/10; novelty 5/10

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

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

## Key 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}.$$

## 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

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: no_effect
- Verdict: 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.

### Mechanism check

- Verdict: 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.
- Confidence: 8/10
- 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.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.84055
- Paired wins: 4/8
- Benchmark verdict: no significant win

## Artifacts

- [bench_report.json](https://synthcore.org/code/1008/bench_report.json)
- [experiment.py](https://synthcore.org/code/1008/experiment.py)
- [report.md](https://synthcore.org/code/1008/report.md)
- [report_bench_2026-09-01T183508.md](https://synthcore.org/code/1008/report_bench_2026-09-01T183508.md)
- [results.json](https://synthcore.org/code/1008/results.json)
- [stage2_bench.py](https://synthcore.org/code/1008/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/1008)

## Disclaimer

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