Unverified 2026

Non-crossing d-arc sparse attention

Implementation & benchmark of arXiv:2607.19916 — Higher cluster tilting objects in locally finite triangulated categories

Usefulness5/10

Difficulty4/10

Novelty7/10

Architecture Speedup Scalability Memory Attention Transformer Inference speedup Combinatorics Graph theory Representation theory Geometry

Source paper: Higher cluster tilting objects in locally finite triangulated categories arXiv:2607.19916 ⓘ · analyzed Aug 30, 2026

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

Idea description

Represent sequence positions as vertices on a circle and use a maximal family of mutually non-crossing d-arcs to define the allowed attention interactions. Rotate the family by d positions, or use several phase-shifted families across successive layers, so each layer has only O(N) edges but repeated layers propagate information over long distances. The geometric compatibility rule replaces arbitrary local-window or hand-designed sparse masks with a structured family whose maximality gives broad coverage.

Formulas

$$D_{i,j}\rightarrow D_{i,j+d},\quad D_{i,j}\rightarrow D_{i+d,j},\quad D_{i,i+N-d}\rightarrow D_{ii}^{\pm},\quad D_{ii}^{\pm}\rightarrow D_{i+d,i+N}$$

$$i<m<j<l<m+N,\qquad t\in\{1,2,\ldots,d\},\qquad m-t-i\in d\mathbb{Z},\qquad \beta[t]=D_{m-t,l-t}$$

$$\alpha\text{ crosses }\beta\ \Longrightarrow\ \operatorname{Hom}_{\mathcal{C}_{d}}(X_{\alpha},X_{\beta}[t])\neq 0;\qquad \text{therefore use }\operatorname{cross}(\alpha,\beta)=0\text{ as the attention-compatibility rule}$$

$$\operatorname{Attn}(Q,K,V;E)=\operatorname{softmax}_{j:(i,j)\in E}\!\left(\frac{Q_iK_j^{\mathsf T}}{\sqrt{h}}+b_{ij}\right)V_j$$

Mathematical statement

The paper defines d-arcs D_{i,j} between cyclically ordered boundary vertices and describes the Auslander–Reiten graph through the local d-moves D_{i,j}\rightarrow D_{i,j+d} and D_{i,j}\rightarrow D_{i+d,j}. It proves geometrically that crossing arcs create nonzero shifted morphisms: for crossing \alpha=D_{i,j} and \beta=D_{m,l} with i<m<j<l<m+N, choose the unique t\in\{1,\ldots,d\} such that m-t-i\in d\mathbb{Z}; then \beta[t]=D_{m-t,l-t} lies in the Hom-hammock H^{+}(\alpha), hence Hom(X_{\alpha},X_{\beta}[t])
eq 0. We transfer the contrapositive compatibility rule: retain pairs of arcs with no crossing, treating them as d-orthogonal. Here N is the sequence length, indices are taken modulo N, d is the interaction stride/order, and X_{\alpha} is the attention edge associated with arc \alpha. A maximal non-crossing family is used as a sparse mask; rotating indices by d implements the paper's AR-translation-like coverage mechanism.

Implementation notes

Integrate this into the attention-logit and value-gathering operation of a transformer encoder. First choose N sequence positions on a circle, select an integer d, and generate a maximal non-crossing set of ordinary chords D_{i,j}; a simple MVP can use a fan triangulation plus chords whose endpoint differences are multiples of d. For every layer phase r, rotate the endpoints by rd modulo N and form edge set E_r. To test crossing, sort each chord so i<j and declare (i,j) and (m,l) crossing when i<m<j<l or m<i<l<j; do not include both crossing edges in the same mask. Pseudocode: E = maximal_non_crossing_arcs(N,d); for layer l: E_l = rotate(E, (l*d) mod N); logits = Q@K.T/sqrt(h); logits[not E_l] = -inf; Y = softmax(logits,rowwise)@V. The mathematical object computed exactly is the non-crossing compatibility mask and its d-step rotations. Empirically estimate coverage by computing graph diameter and the number of layers needed for every token pair to communicate; compare this with sliding-window, dilated, and BigBird-style masks at equal edge count. Start with a 6-layer, 8-head Transformer on ListOps or WikiText-2 with N=512 and hidden size 256. Measure training loss at equal FLOPs, validation perplexity, attention-memory reduction, and gradient propagation across distant token pairs. Success would be at least 2x fewer attention edges with no more than 1% perplexity degradation, or faster loss descent at matched compute. Include ablations for fixed versus d-rotated masks and for maximal versus randomly sampled non-crossing families.

Verification

This idea has not been verified yet.

Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.

Artifacts

Artifacts unavailable.