Outlier-Spectral Landmark Attention

Integrate this into a transformer as a token-mixing residual branch, either after the value projection or as a replacement for one dense self-attention block. For token matrix X with shape [batch,n,d], first compute a symmetric bounded affinity A implicitly: use normalized tokens Z=X/(||X||_2+10^-6), compute landmark affinities C between every token and s sampled landmarks, and compute W, the s-by-s landmark affinity matrix. Sample S uniformly without replacement during training; for cheaper inference, fix S using a deterministic hash or reservoir sampling. Pseudocode: (1) choose s=ceil(c log(n)/(epsilon^4 delta) log(1/(epsilon delta))^3), clipped to [r_min,n]; (2) compute C_ij=tanh(z_i^T z_{S_j}/sqrt(d)) and W_ij=tanh(z_{S_i}^T z_{S_j}/sqrt(d)); (3) symmetrize W=(W+W^T)/2; (4) compute W=U diag(mu) U^T and set P=U diag(1/mu_k if |mu_k|>=tau_W, else 0) U^T; (5) for values V, output Y=X+alpha C P(C^T V), where alpha is a learned scalar. The paper's mathematical contribution is the sampled-column span and outlier threshold; Nyström is the concrete reconstruction used here because the extracted material does not expose Algorithm (1)'s full estimator. Estimate the approximation residual on validation batches by explicitly forming A for n<=1024 and computing ||(A-Ahat)V||_F/||AV||_F. First test on a 6-layer transformer with 512 and 1024 tokens using CIFAR-100 patch tokens or Long Range Arena, comparing full attention, standard Nyström attention, and this module. Record accuracy, wall-clock time, peak memory, rank, and spectral residual. Success means at least 1.5x lower attention memory or latency with less than one percentage point accuracy loss, while increasing s should reduce the measured residual and preserve the dominant eigenmodes.