arXiv:2608.20633 2026 Architecture 1 ideas extracted · analyzed Sep 1, 2026
The paper provides a principled randomized low-rank factorization for positive-semidefinite matrices: sample pivots in proportion to the diagonal of the current residual, then remove the corresponding rank-one Schur-complement contribution. Its transferable asset is an adaptive sampling distribution that concentrates computation on locations poorly represented by the current low-rank approximation. A direct neural-network use is compressing PSD kernel attention by selecting data-dependent landmarks during inference, rather than using uniformly spaced or randomly selected Nyström landmarks. The near-optimal rank-versus-error result gives a concrete hypothesis: residual-diagonal pivoting should reach a target attention approximation error with fewer landmarks than uniform sampling at comparable kernel-evaluation cost.
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.