# Unique-witness two-hop attention

- ID: 1488
- Canonical URL: https://synthcore.org/idea/1488/unique-witness-two-hop-attention
- API JSON: https://synthcore.org/api/idea/1488.json
- API Markdown: https://synthcore.org/api/idea/1488.md
- Verification status: unverified
- Source: [arXiv:2607.27407](https://arxiv.org/abs/2607.27407)
- Category: architecture
- Solves: memory, speedup, accuracy
- ML areas: attention, transformer, inference-speedup
- Math tags: combinatorics, graph-theory, linear-algebra, optimization
- Ratings: usefulness 6/10; difficulty 5/10; novelty 6/10

## Idea description

Replace direct source-to-target attention connectivity by two sparse incidence relations through a set of latent witness tokens. A source token attends only to a small set of witnesses, and each witness attends only to a small set of target tokens; the composed relation is trained to contain exactly one witness for desired pairs and no witnesses for undesired pairs. This produces a controllable sparse attention pattern whose errors can be measured entrywise against a dense teacher or known mask.

## Mathematical statement

For simple graphs H and K on the same vertex set, the paper uses the identity $\bigl(A(H)A(K)\bigr)_{ij}=\sum_{\ell=1}^{n}A(H)_{i\ell}A(K)_{\ell j}=|N_H(v_i)\cap N_K(v_j)|$. Here $A(H)_{i\ell},A(K)_{\ell j}\in\{0,1\}$ are source-to-witness and witness-to-target incidences, and the product entry is the number of two-step witnesses for ordered pair $(i,j)$. Exact factorization requires $A(H)A(K)=A(G)$, so every desired ordered edge has one witness and every undesired pair, including diagonal pairs, has zero witnesses. The approximate condition allows disagreement in at most $\varepsilon n^2$ entries: $|\{(i,j):(A(H)A(K))_{ij}\neq A(G)_{ij}\}|\leq\varepsilon n^2$. We adapt this to a binary or soft attention mask $M\in\{0,1\}^{n\times n}$ using sparse incidence matrices $B\in\{0,1\}^{n\times r}$ and $C\in\{0,1\}^{r\times n}$, with witness-count matrix $W=BC$. The loss penalizes missing desired relations, false paths on undesired relations, and multiplicity $W_{ij}>1$.

## Key formulas

- $\bigl(A(H)A(K)\bigr)_{ij}=\sum_{\ell=1}^{n}A(H)_{i\ell}A(K)_{\ell j}=|N_H(v_i)\cap N_K(v_j)|$.
- $\left|\left\{(i,j):\bigl(A(H)A(K)\bigr)_{ij}\neq A(G)_{ij}\right\}\right|\leq\varepsilon n^2$.
- $B_{iw}=\sigma(\alpha_{iw}),\qquad C_{wj}=\sigma(\beta_{wj}),\qquad W_{ij}=\sum_{w=1}^{r}B_{iw}C_{wj}$.
- $\mathcal{L}_{\mathrm{witness}}=\frac{1}{n^2}\sum_{i,j}\left[M_{ij}|W_{ij}-1|+(1-M_{ij})W_{ij}\right]+\lambda\left\|\max(0,W-1)\right\|_1$.

## Implementation notes

(1) Integration point: insert the module before value aggregation in a Transformer attention block. Let X be the n token representations and let M be either a known sparse mask, a causal/local mask, or a binary teacher mask obtained by thresholding the top-q dense attention probabilities from a frozen baseline. Introduce r latent witness slots, with r much smaller than n. Compute source-to-witness logits alpha from token queries and witness keys, and witness-to-target logits beta from witness queries and token keys. (2) Pseudocode: initialize alpha[n,r] and beta[r,n]; for each batch compute B=sigmoid(alpha/tau), C=sigmoid(beta/tau), and W=B@C; add the displayed L_witness to the task loss; compute witness values z_w=sum_i B_iw V_i/(sum_i B_iw+delta); compute output y_j=sum_w C_wj z_w/(sum_w C_wj+delta), followed by the usual output projection. Use top-k or Gumbel-top-k routing for B and C with a straight-through estimator, and anneal tau from 1.0 to 0.1 before hardening the routes. At inference, retain only the k largest incidences per source and per witness, then execute the two sparse aggregations rather than forming n-by-n attention. (3) Computed directly from the paper's mathematics: W is the explicit witness-count matrix, and L_witness is the relaxed Hamming/uniqueness objective. Estimated empirically: M may come from a dense teacher's top-q edges; r, k, tau, and lambda are hyperparameters; and realized speed depends on the nonzero counts of B and C. Track coverage, false-path rate, and the proportion of pairs with zero, one, or multiple witnesses. (4) First cheap experiment: train a 4-layer, 8-head Transformer on synthetic sequence classification with block-local attention plus a few long-range dependencies. Compare dense attention, ordinary low-rank latent attention, and this unique-witness module at matched hidden size, using n=512, r=64, k=4, and a frozen dense teacher to construct M. Measure validation accuracy, peak attention memory, tokens per second, and witness statistics. A successful result preserves accuracy within one percentage point while reducing relation-storage memory by at least 4x and improving inference throughput; the strongest expected signal is lower false-path and multiple-witness rates on structured masks.

## Disclaimer

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