Okada Non-Crossing Routing Attention

(1) Integrate the module into a Transformer encoder by replacing one or two dense self-attention blocks. Given hidden states $H\in\mathbb{R}^{B\times N\times d}$, define generator $e_i$ as a learned two-token mixing operation acting only on positions $i$ and $i+1$. A routing program is a word $w=(i_1,\ldots,i_T)$ of adjacent generator indices. (2) Pseudocode: initialize an empty diagram $D$; for each $i_t$, compose $D\leftarrow D\circ e_{i_t}$; repeatedly scan the word for $e_i e_i$ and replace it by $e_i$ using idempotence; commute generators with $|i-j|\ge2$ into a deterministic index order; replace every $e_{i+1}e_i e_{i+1}$ by $e_{i+1}$; then compose the retained local diagrams by tracing paths through intermediate vertices and deleting closed loops. Convert the final propagating arcs into sparse COO pairs $(a,b)$. Compute $H'_a=\sum_{b:(a,b)\in D}\alpha_{ab}W_vH_b$, with $\alpha_{ab}$ produced by a scaled dot product or a small edge MLP only on those pairs, followed by output projection and a residual connection. (3) The mathematical computation is the rewrite and diagram-composition procedure. Estimate generator scores using a router MLP on each adjacent pair $(H_i,H_{i+1})$; choose top-$k$ generators while enforcing a non-crossing pattern, or use a fixed alternating pattern initially. Estimate $\alpha_{ab}$ empirically from the surviving edges. (4) First experiment: use a 6-layer, 256-dimensional encoder on ListOps and Dyck-language prediction, with CIFAR-10 patch classification as a non-hierarchical control. Compare dense attention, local-window attention, and this method at sequence lengths 128, 512, and 2048. Record validation accuracy, peak activation memory, wall-clock time, number of surviving arcs, and loss per training FLOP. The method is promising if it achieves at least 2x lower attention memory and near-linear scaling while remaining within one percentage point of dense attention on hierarchical tasks; failure on CIFAR-10 but success on ListOps or Dyck would indicate that the non-crossing bias is useful specifically for nested dependencies.