# Bounded-Path Order Router

- ID: 2453
- Canonical URL: https://synthcore.org/idea/2453/bounded-path-order-router
- API JSON: https://synthcore.org/api/idea/2453.json
- API Markdown: https://synthcore.org/api/idea/2453.md
- Verification status: unverified
- Source: [arXiv:2608.17354](https://arxiv.org/abs/2608.17354)
- Category: architecture
- Solves: speedup, stability, scalability
- ML areas: attention, transformer, graph-nn, inference-speedup, training-dynamics
- Math tags: combinatorics, graph-theory, dynamical-systems
- Ratings: usefulness 5/10; difficulty 7/10; novelty 8/10

## Idea description

Use the paper's eventual path-length bounds to constrain an order-invariant routing graph to a constant-hop communication budget. A learned sparse attention or graph-neural-network layer can explicitly route information through at most three admissible hops, while a more conservative auxiliary route permits at most five minimal-path hops, preventing increasingly long and unstable dependency chains as sequence length grows.

## Mathematical statement

For an \(\Inc\)-invariant graph chain \(\mathcal G=(G_n)\) with index \(r=\operatorname{ind}(\mathcal G)\), the paper proves that the maximal admissible-path length \(\ell(G_n)\) satisfies \(\ell(G_n)\le3\) for every \(n\ge5r\), and the maximal minimal-path length \(\ell'(G_n)\) satisfies \(\ell'(G_n)\le5\) in the same range. It further proves stabilization: \(\ell(G_n)=\ell(G_{n+1})\) and \(\ell'(G_n)=\ell'(G_{n+1})\) for \(n\ge5r+9\). Here \(n\) is sequence length, \(r\) is the finite symmetry index, and \(\ell,\ell'\) are the maximum lengths of the paper's admissible and minimal paths. The adaptation treats these bounds as hard architectural budgets: every token-to-token dependency must lie in a learned graph whose transitive routing depth is at most H=3, with H=5 used for a relaxed ablation. The theorem does not guarantee arbitrary learned graphs satisfy the hypotheses, so the implementation must monitor or enforce the path constraint.

## Key formulas

- $$\ell(G_n)\le 3\quad\text{and}\quad \ell'(G_n)\le 5\qquad(n\ge5r),$$
- $$\ell(G_n)=\ell(G_{n+1}),\qquad \ell'(G_n)=\ell'(G_{n+1})\qquad(n\ge5r+9),$$
- $$R_H=I+A+A^2+\cdots+A^H,\qquad \mathcal L_{\mathrm{route}}=\sum_{u,v}\mathbf 1[(R_H)_{uv}=0]w_{uv},$$
- $$A_{uv}=\mathbf 1\!\left[s_{uv}>\tau\right],\qquad s_{uv}=\frac{q_u^{\mathsf T}k_v}{\sqrt d}+b_{\tau(u,v)}.$$

## Implementation notes

Integrate this into a sparse-attention router or graph-neural-network block. Produce a candidate directed adjacency A from top-k attention scores s_uv, but retain only edges generated by an order-preserving motif mask of width r. Set H=3 after the sequence length exceeds 5r; during early training use H=5 or a soft penalty. Compute reachability by Boolean sparse matrix multiplication: initialize R=I and P=I; for h=1,...,H set P=P multiplied by A and R=R OR P. To avoid a dense n-by-n tensor, evaluate reachability only for sampled token pairs and for all pairs needed by the next layer's top-k candidates. Penalize unreachable candidate dependencies with L_route, where w_uv is the detached attention probability or a uniform weight. An alternative hard version repeatedly prunes the lowest-score edge whose removal reduces the number of nonzero entries in A^h, until no dependency longer than H remains. The formulas supply the constant budgets and stabilization threshold; reachability computation, threshold tau, top-k, and the soft penalty are engineering choices. Estimate r from the chosen motif width rather than fitting it initially. First experiment on TinyStories or WikiText-103 with a 4-layer, 256-dimensional Transformer, comparing dense attention, sliding-window attention, and unconstrained top-k routing at context lengths 512 and 2048. Measure perplexity, maximum gradient norm, sparse attention FLOPs, and empirical longest dependency path. The target is equal or better perplexity at fixed edges per token, no growth in longest path beyond H at long contexts, and lower activation memory or latency than dense attention.

## Disclaimer

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