Hamiltonian Path Scan Layer

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.