# Collision-free ternary attention

- ID: 141
- Canonical URL: https://synthcore.org/idea/141/collision-free-ternary-attention
- API JSON: https://synthcore.org/api/idea/141.json
- API Markdown: https://synthcore.org/api/idea/141.md
- Verification status: unverified
- Source: [arXiv:2608.24740](https://arxiv.org/abs/2608.24740)
- Category: architecture
- Solves: memory, scalability, accuracy
- ML areas: attention, transformer, memory
- Math tags: combinatorics, graph-theory, optimization
- Ratings: usefulness 5/10; difficulty 6/10; novelty 7/10

## Idea description

Represent a sparse higher-order attention head by a 3-uniform hypergraph whose hyperedge $(v,x,y)$ allows anchor token $v$ to aggregate a pairwise interaction between tokens $x$ and $y$. During mask construction, greedily reject edges that would create a $4$-cycle in the link graph $L(v)$, so the same pair of source tokens cannot reach an anchor through multiple redundant pairings. This produces a diversity-constrained sparse attention pattern with an explicit, measurable collision bound.

## Mathematical statement

A 3-uniform hypergraph $H=(V,E)$ has a link graph $L(v)$ for each anchor $v\in V$: its vertices are tokens $u\neq v$, and $xy\in E(L(v))$ exactly when $\{v,x,y\}\in E(H)$. The paper's $K_{1,2,2}$-free condition is equivalent to every link graph $L(v)$ being $C_4$-free. For disjoint sets $A_v,B_v\subseteq V$, where $A_v$ and $B_v$ are the two source-token classes, the paper uses the exact inequality $$\sum_{y\in B_v}\binom{|A_v\cap N_{L(v)}(y)|}{2}\leq\binom{|A_v|}{2}.$$ Here $N_{L(v)}(y)$ is the neighborhood of $y$ in the link graph, and $\binom{r}{2}$ counts unordered pairs of neighbors. The inequality holds because if a pair $\{x,x'\}\subseteq A_v$ were counted for two distinct $y,y'\in B_v$, then $x,y,x',y'$ would form a $4$-cycle in $L(v)$. The adapted hard-mask constraint is $$\sum_{x<x'}\sum_{y<y'}M_{vxy}M_{vxy'}M_{vx'y}M_{vx'y'}=0,$$ where $M_{vxy}\in\{0,1\}$ indicates whether ternary interaction $(v,x,y)$ is retained. The left side counts link-graph $4$-cycles.

## Key formulas

- $$E(\mathcal{C}_k)=\big\{\{i-1,i,i+1\}:i\in\mathbb{Z}/k\mathbb{Z}\big\}.$$
- $$\sum_{y\in B_v}\binom{|A_v\cap N_{L(v)}(y)|}{2}\leq\binom{|A_v|}{2}.$$
- $$\sum_{x<x'}\sum_{y<y'}M_{vxy}M_{vxy'}M_{vx'y}M_{vx'y'}=0\qquad\text{for every anchor }v.$$
- $$\mathcal{L}_{\mathrm{C4}}(M)=\sum_v\sum_{x<x'}\sum_{y<y'}\sigma(M_{vxy})\sigma(M_{vxy'})\sigma(M_{vx'y})\sigma(M_{vx'y'}),\quad \sigma(z)=\operatorname{sigmoid}(z).$$

## Implementation notes

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.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.