Matroidal Mahalanobis Attention

(1) Integration point: replace the usual dot-product attention score, or a dense Mahalanobis distance in a metric-learning head, with the quadratic distance defined above. Let $z_i\in\mathbb{R}^d$ be the projected representation of token $i$. Fix a sparse covector matrix $A\in\mathbb{R}^{d\times m}$, and learn only the coefficient vector $\theta\in\mathbb{R}^m$ with $\ell_e=\operatorname{softplus}(\theta_e)$; use a small fixed $\varepsilon$, such as $10^{-4}$. (2) Pseudocode: compute u = einsum('dm,bnd->bnm', A, z), so u[b,n,e] = a_e^T z[b,n]; compute w = softplus(theta); for every query-key pair compute delta = u[:, :, None, :] - u[:, None, :, :], dist = (delta**2 * w).sum(-1) + eps * ((z[:, :, None, :] - z[:, None, :, :])**2).sum(-1); set logits = -dist/(2*tau) and apply the attention softmax. This is exactly $x^TMx=\sum_e\ell_e(a_e^Tx)^2+\varepsilon\|x\|^2$ applied to pairwise differences. (3) Computed from the paper: coefficient nonnegativity, the rank-one PSD decomposition, and the unimodular support. Estimated empirically: $\tau$, $\varepsilon$, the number of support columns $m$, and whether coefficient pruning is beneficial. Initially restrict $A$ to graph-incidence columns, for which total unimodularity is guaranteed; optionally prune columns with $\ell_e<\delta$ and compare the resulting sparse model. (4) First experiment: train a small 2-layer, 8-head Transformer on character-level Penn Treebank or CIFAR-10 represented as patch tokens. Compare standard dot-product attention, a dense learned Mahalanobis metric, and this matroidal metric at matched hidden dimension and approximately matched parameter count. Sweep $m\in\{d,2d,4d\}$ and measure validation loss or accuracy, gradient-norm variance, attention-logit numerical failures, parameter count, and measured attention FLOPs. The hypothesis is that the structured metric is most useful in low-data or low-parameter settings: success means equal or better validation loss with fewer metric parameters, smoother training, and no loss of stability relative to the dense baseline.