Exact-Distance Landmark Attention

Integrate this as a sparse cross-attention layer over an H by W image or spatial feature map, before or instead of dense self-attention. First choose k, usually 3 or 5, and one or several shifts t in {0,...,M-1}. Precompute a Boolean landmark mask using the exact residue formula; mark the width-k boundary strip as landmarks. For every interior non-landmark position v=(i,j), enumerate the finite offset set Delta_k = {(a,b): |a|+|b|=k}, retain offsets for which v+(a,b) is in bounds and belongs to D_t, and store one or all resulting indices q in N_k(v) intersected with D_t. The paper's lemma guarantees this list is nonempty. Compute keys and values only for landmarks. For each query token, gather its stored landmark indices and apply the sparse attention equation above, then add the result through a residual projection. Process landmark tokens with local convolution or a small global attention block. A practical variant uses different shifts t in different heads and concatenates their outputs. The residue mask, offset table, and coverage guarantee are computed exactly; no learned estimator is needed. Validate first on CIFAR-100 or ImageNet-32 with a 32 by 32 ViT. Compare dense attention, 7 by 7 local attention, and this layer at matched hidden size. For k=3, the asymptotic landmark fraction is 4/46, approximately 8.7 percent, so landmark key/value memory should be roughly 11 times smaller than dense key/value memory. Success means equal or better validation accuracy at lower attention FLOPs and peak memory.