Fractional Ellipsoidal Sparse Attention

(1) Integration point: replace or augment the score-and-softmax operation in a multi-head self-attention layer. For head h, let q_i, k_j, and v_j be the query, key, and value vectors in R^{d_h}. Compute d_ij=q_i-k_j. Give each head a learned lower-triangular matrix L_h and define B_h=L_h L_h^T+epsilon I with epsilon=1e-4. Use a_h to define s_h=0.05+0.90 sigmoid(a_h). (2) Pseudocode: for each query i and candidate key j, compute r_ij=d_ij^T B_h d_ij; compute w_ij=K_h*max(1-r_ij,0)^(1+s_h); optionally multiply w_ij by exp(q_i^T k_j/sqrt(d_h)) if content matching is retained; normalize alpha_ij=w_ij/(sum_j w_ij+delta); output o_i=sum_j alpha_ij v_j. During an initial correctness experiment, enumerate all pairs. After learning stable ellipsoids, construct candidate pairs with an approximate range-search data structure and retain only r_ij<1. (3) Computed directly from the paper’s mathematics: compact support, the SPD quadratic metric, and the exponent 1+s_h. Estimated or tuned empirically: the eigenvalues of B_h, the active-neighbor count, K_h, and the initialization radius. Initialize B_h near an isotropic matrix so every query has neighbors, and add a mild penalty if the mean active count is below a minimum. (4) First experiment: train a 4-layer, 8-head transformer on CIFAR-10 image patches and on a synthetic task where each token depends on a randomly rotated local ellipse. Compare dense softmax attention, fixed square-window attention, and the ellipsoidal kernel. Report validation accuracy, loss at equal FLOPs, active neighbors per query, and wall-clock attention time. A successful result is at least two times fewer active pairs with no more than one percentage point accuracy loss, or better accuracy than fixed windows at the same active-neighbor budget. Ablate the learned matrix, the fractional exponent, and the content-score multiplier.