Christoffel-Balanced Sparse Attention

Integrate the construction at the attention-logit stage of a decoder or encoder Transformer. Choose a period k dividing the target context length and choose a reduced density m/k, such as m = 64 and k = 512 or m = 128 and k = 1024. Compute the Boolean vector with c[j] = floor((j+1)*m/k) - floor(j*m/k) using integer arithmetic or high-precision arithmetic, then precompute the allowed relative offsets O = {j: c[j] == 1}. For query position i, form the key indices from these offsets, retain only indices satisfying the causal condition j <= i for a decoder, and compute logits, softmax, and the value sum only on those keys. Pseudocode is: for j in 0..k-1: c[j] = floor((j+1)*m/k) - floor(j*m/k); O = where(c == 1); for each query i: J = [i + offset for offset in O if 0 <= i + offset < L and, if causal, i + offset <= i]; logits = Q[i] @ K[J].T / sqrt(d); A = softmax(logits); Y[i] = A @ V[J]. For a production implementation, avoid materializing an L by L mask and write or adapt a block-sparse kernel that gathers the m allowed offsets for each query block. For bidirectional attention, use signed offsets or combine two masks generated by slopes m/k and (k-m)/k. The mathematical quantities computed exactly are the carry word, its m selected offsets, and its prefix-balance guarantee. The engineer must estimate empirically whether this balance improves connectivity and optimization; measure graph reachability across layers because a single periodic mask may create undesirable residue classes. Begin with a 12-layer, 256-dimensional Transformer on WikiText-103 or a synthetic long-range copying task at context length 2048. Compare dense attention, a contiguous local window with the same number of edges, random m-edge attention, fixed strided attention, and the Christoffel mask. Keep parameter count and attention-edge count equal. Measure validation perplexity, loss versus training FLOPs, wall-clock throughput, peak memory, and accuracy on long-range copying or retrieval. The method succeeds if it matches or improves perplexity while reducing attention memory and compute, or if it gives faster loss descent at equal sparse-attention FLOPs. Also inspect attention-reachability, offset histograms, and gradient norms to detect disconnected or overly periodic behavior.