Collision-free ternary attention

Integrate this into a sparse ternary-attention layer rather than ordinary dense self-attention. Given token states $h_1,\ldots,h_n$, use learned projections $q_v=W_qh_v$, $k_x=W_kh_x$, and $r_y=W_rh_y$, and score each candidate hyperedge by $s_{vxy}=q_v^\top U[k_x;r_y]/\sqrt d$. For each anchor $v$, generate a candidate set of at most $K$ pairs $(x,y)$ using approximate top scoring, then sort candidates by decreasing $s_{vxy}$. Maintain the adjacency sets of the link graph $L(v)$. Accept $(v,x,y)$ unless adding link edge $(x,y)$ creates a four-cycle: reject if there exist $x'$ and $y'$ with existing edges $(x,y')$, $(x',y')$, and $(x',y)$. This check can use hash sets and pairwise common-neighbor counts. Compute messages only over accepted triples, using $m_v=\sum_{(x,y):M_{vxy}=1}a_{vxy}\phi(h_x,h_y)$ with $a_{vxy}=\operatorname{softmax}_{(x,y)}s_{vxy}$. For a differentiable variant, train logits with $\lambda\mathcal{L}_{\mathrm{C4}}(M)$, estimated by randomly sampling quadruples, and apply the greedy hard projection at inference. The mathematical guarantee is the zero-$C_4$ condition and the counting inequality; density, $K$, $\lambda$, and accuracy effects must be measured empirically. First test a 2-layer, 8-head Transformer on CIFAR-100 or WikiText-2, comparing equal-edge-count collision-free masks against random and top-score sparse attention. Measure validation accuracy or perplexity, attention FLOPs, peak memory, accepted-edge fraction, and duplicate two-hop paths. Success means at least 1.5x fewer collisions with no accuracy loss and lower memory at equal retained edges.