# Hamiltonian Path Scan Layer

- ID: 2995
- Canonical URL: https://synthcore.org/idea/2995/hamiltonian-path-scan-layer
- API JSON: https://synthcore.org/api/idea/2995.json
- API Markdown: https://synthcore.org/api/idea/2995.md
- Verification status: unverified
- Source: [arXiv:2609.01256](https://arxiv.org/abs/2609.01256)
- Category: architecture
- Solves: speedup, scalability, memory
- ML areas: graph-nn, attention, ssm, inference-speedup
- Math tags: combinatorics, graph-theory, number-theory
- Ratings: usefulness 5/10; difficulty 6/10; novelty 7/10

## Idea description

Build a fixed sparse token-mixing layer on n=qr cyclic positions whose directed edges are all offsets 1 through r, but execute the edges through r Hamiltonian path scans plus one prescribed chain. The paths preserve exact coverage of the circulant connectivity while exposing long sequential traversals that can be fused into custom kernels, recurrent scans, or state-space updates.

## Mathematical statement

The paper defines the directed circulant C_q(r)=Cay^rightarrow(Z_(qr),[r]), where vertices are residues x in Z_(qr), [r]={1,...,r}, and every vertex has arcs x to x+s modulo qr for each s in [r]. It has qr^2 arcs, so any decomposition into directed paths needs at least ceil(qr^2/(qr-1))=r+1 paths because a simple directed path on qr vertices contains at most qr-1 arcs. A q-layer balanced Hamilton starter H is a Hamilton cycle containing exactly one arc x to x+s for each pair (j,s) in Z_q times [r], where j=x modulo q. Its translates H+tq, for t=0,...,r-1, partition all arcs. Chain compatibility supplies one selected arc from each translate, and those selected arcs form the simple path C: 0 to 2 to 4 to ... to 2r. Deleting the selected arc from each translated cycle produces r Hamilton paths P_t=(H+tq) minus the selected edge; together with C, these give an optimal r+1-path decomposition. The explicit existence regime used here is q=4, r congruent to 1 modulo 4, r at least 9.

## Key formulas

- $$\mathcal{C}_{q}(r):=\operatorname{Cay}^{\rightarrow}\bigl(\mathbb{Z}_{qr},[r]\bigr),\qquad [r]=\{1,\ldots,r\},\qquad E=\{(x,x+s):x\in\mathbb{Z}_{qr},\ s\in[r]\}.$$
- $$\#E=qr^{2},\qquad \operatorname{pn}(\mathcal{C}_q(r))\ge \left\lceil\frac{qr^{2}}{qr-1}\right\rceil=r+1.$$
- $$\forall (j,s)\in\mathbb{Z}_{q}\times[r],\quad \#\{x\to x+s\in H:x\equiv j\pmod q\}=1,\qquad E=\bigsqcup_{t=0}^{r-1}E(H+tq).$$
- $$C=(0\to2\to4\to\cdots\to2r),\qquad P_t=(H+tq)\setminus\{e_t\},\qquad E=E(C)\sqcup\bigsqcup_{t=0}^{r-1}E(P_t).$$

## Implementation notes

Integrate this at the token-mixing operation of a graph neural network or local-attention transformer. Arrange n=qr tokens on cyclic indices Z_(qr), choose q=4 and r congruent to 1 modulo 4, and start with r=9, giving n=36. Precompute one valid starter cycle H offline from the paper's explicit construction, store its ordered vertex list, and store the selected deletion edge e_t for every translated cycle H+tq. Materialize the r translated Hamilton paths P_t and the additional chain C. For token features X in R^(n times d), replace explicit offset aggregation by path scans. For each path p=(v_0,...,v_L), initialize a state z from X[v_0], then iterate over ordered edges: compute s_i=(v_(i+1)-v_i) modulo n, retrieve a shared step-specific matrix W[s_i] or a low-rank embedding of s_i, and update z using z <- phi(A[s_i]z+B X[v_(i+1])+b[s_i]); scatter the resulting message to v_(i+1). Add the outputs from all paths and C, then apply a residual projection and normalization. A simpler first version can use direct messages y[v_(i+1)] += W[s_i]X[v_i] instead of a recurrent state. In pseudocode: construct H and e_t; for t from 0 to r-1, form H_t=H+tq and remove e_t; for each ordered edge (u,v) in every P_t and C, set s=(v-u) mod n, compute message M=phi(W_s X[u]), and accumulate y[v]+=M; return LayerNorm(X+Projection(y)). The mathematical construction guarantees that every edge (u,u+s), for every u and s in [r], appears exactly once and no edge is duplicated. Empirically estimate kernel time, peak memory, achieved bandwidth, and task accuracy; no graph quantity needs to be estimated. The first cheap experiment should use a 36-token synthetic long-range copy or modular-arithmetic task and a small sequence classifier, comparing this layer against explicit all-offset message passing and local attention with exactly qr^2 edges, equal hidden width, and equal parameter count. Success means lower wall-clock time or peak memory at matched accuracy, faster loss descent at equal FLOPs, or better long-range-copy accuracy than random edge ordering. Also test whether a fused one-dimensional scan implementation outperforms the baseline gather-scatter implementation, separating the mathematical ordering benefit from merely changing the sparse operator.

## Disclaimer

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