# Residual-pivoted landmark attention

- ID: 1466
- Canonical URL: https://synthcore.org/idea/1466/residual-pivoted-landmark-attention
- API JSON: https://synthcore.org/api/idea/1466.json
- API Markdown: https://synthcore.org/api/idea/1466.md
- Verification status: unverified
- Source: [arXiv:2607.26863](https://arxiv.org/abs/2607.26863)
- Category: memory
- Solves: speedup, memory, accuracy
- ML areas: attention, inference-speedup, kv-cache
- Math tags: linear-algebra, approximation-theory, optimization
- Ratings: usefulness 6/10; difficulty 6/10; novelty 5/10

## Idea description

Replace uniform or random landmark selection in low-rank attention with approximate greedy pivoted QR selection on the attention matrix. At each step, select the key whose residual attention column has the largest norm, orthogonalize it against previously selected columns, and stop when the residual energy falls below a target tolerance. Use the selected columns as an adaptive attention basis and reconstruct the full attention output through a small coefficient matrix.

## Mathematical statement

The paper defines the pivoted-QR residual sequence $\widehat{E}^{(0)}=A$, $q_{k+1}=\widehat{E}^{(k)}_{:,j_{k+1}}/\|\widehat{E}^{(k)}_{:,j_{k+1}}\|_2$, and $\widehat{E}^{(k+1)}=(I-q_{k+1}q_{k+1}^{\top})\widehat{E}^{(k)}$. Here $A\in\mathbb{R}^{N\times N}$ is an attention or kernel matrix, $N$ is sequence length, $j_{k+1}$ is the selected column, $q_{k+1}\in\mathbb{R}^N$ is the normalized new basis vector, and $\widehat{E}^{(k)}$ is the residual after $k$ pivots. Greedy QR chooses $j_{k+1}=\arg\max_j\|\widehat{E}^{(k)}_{:,j}\|_2$; approximate greedy selection can use a quality factor $0<\eta\leq1$ satisfying $\|\widehat{E}^{(k)}_{:,j_{k+1}}\|_2\geq\eta\max_j\|\widehat{E}^{(k)}_{:,j}\|_2$. The resulting rank-$k$ approximation is $\widetilde A_k=Q_kQ_k^{\top}A=A-\widehat E^{(k)}$, with $Q_k=[q_1,\ldots,q_k]$. The paper bounds selected-submatrix volume using the leading singular values: for index sets $I,J$ of size $k$, $|\det(A_{I,J})|^{1/k}\leq(\prod_{\ell=1}^{k}\sigma_\ell(A))^{1/k}$. Thus greedy residuals should decay rapidly when the singular values $\sigma_\ell(A)$ decay algebraically or geometrically.

## Key formulas

- $$\widehat{E}^{(0)}=A,\qquad q_{k+1}=\frac{\widehat{E}^{(k)}_{:,j_{k+1}}}{\left\lVert\widehat{E}^{(k)}_{:,j_{k+1}}\right\rVert_{2}},\qquad \widehat{E}^{(k+1)}=(I-q_{k+1}q_{k+1}^{\top})\widehat{E}^{(k)}.$$
- $$j_{k+1}=\arg\max_{j\in\{1,\ldots,N\}}\left\lVert\widehat{E}^{(k)}_{:,j}\right\rVert_2\quad\text{or approximately}\quad \left\lVert\widehat{E}^{(k)}_{:,j_{k+1}}\right\rVert_2\geq\eta\max_j\left\lVert\widehat{E}^{(k)}_{:,j}\right\rVert_2.$$
- $$\widetilde A_k=Q_kQ_k^{\top}A=A-\widehat E^{(k)},\qquad Q_k=[q_1,\ldots,q_k],\qquad \operatorname{rank}(A-\widetilde A_k)\leq k.$$
- $$\left|\det(A_{I,J})\right|^{1/k}\leq\left(\prod_{\ell=1}^{k}\sigma_\ell(A)\right)^{1/k}.$$

## Implementation notes

Integrate this at the attention-kernel stage for a noncausal self-attention layer, initially on one head. Let $A=\operatorname{softmax}(QK^\top/\sqrt d)\in\mathbb{R}^{N\times N}$ and $V\in\mathbb{R}^{N\times d_v}$. Build a landmark set $J$ of at most $r$ keys. Initialize an implicit residual $R=A$ and an empty basis $Q_r$. At each step, estimate $\|R_{:,j}\|_2$ for candidate keys, choose the largest candidate, append $q=R_{:,j}/\|R_{:,j}\|_2$ to the basis, and update candidate residuals by $R_{:,j}\leftarrow R_{:,j}-q(q^\top R_{:,j})$. Stop when the largest estimated residual norm is below $\tau\|A\|_F$, or when $r=r_{\max}$. Form $C=A_{:,J}$ and compute a ridge-stabilized coefficient matrix $T=(C^\top C+\lambda I)^{-1}C^\top A$. Replace exact attention output $AV$ with $C(TV)$. The residual recursion and greedy criterion come from the paper; $\eta$, tolerance $\tau$, candidate subsampling rate, and ridge parameter $\lambda$ are empirical engineering choices. To avoid materializing all of $A$, compute selected columns and candidate residual probes on demand, or apply the procedure to a feature-based approximation of the attention kernel. First test a 2-layer Transformer encoder on WikiText-2 or a synthetic attention matrix with controlled singular-value decay, comparing adaptive pivots with uniform and random Nyström landmarks at sequence lengths 512 and 2048. Record attention-output relative error $\|AV-C(TV)\|_F/\|AV\|_F$, validation perplexity, latency, and peak memory. Success is lower error at fixed rank or at least 2x lower attention memory/FLOPs at matched perplexity.

## Disclaimer

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