# Periodic Perfect-Matching Router

- ID: 304
- Canonical URL: https://synthcore.org/idea/304/periodic-perfect-matching-router
- API JSON: https://synthcore.org/api/idea/304.json
- API Markdown: https://synthcore.org/api/idea/304.md
- Verification status: unverified
- Source: [arXiv:2607.00238](https://arxiv.org/abs/2607.00238)
- Category: architecture
- Solves: scalability, speedup, accuracy
- ML areas: attention, graph-nn, moe-routing, inference-speedup
- Math tags: combinatorics, graph-theory, linear-algebra
- Ratings: usefulness 7/10; difficulty 4/10; novelty 6/10

## Idea description

Replace dense token-to-token mixing on a 2D grid by a learned or fixed periodic perfect-matching route. Each source coordinate is connected to exactly one destination coordinate, and the same matching pattern is translated across periods, producing sparse, parameter-shared aggregation with predictable equivariance.

## Mathematical statement

The paper uses a perfect matching W: \mathbb{Z}^{2}    o\mathbb{Z} as a sparse weight pattern and assumes periodicity W(i,j)=W(i+r,j-r). Here W(i,j) is interpreted as the edge weight between coordinate i on one axis and coordinate j on the other, with the perfect-matching constraint meaning that every active source and destination participates in exactly one edge. The periodic identity induces a shift operator v on matching elements: v:(s_{1},s_{2},i)\mapsto(s_{1}+r,s_{2}-r,i), and v^{q} shifts by q periods. We transfer these two properties into a sparse neural mixing matrix A_W: each token has O(1) routed partners, and translating the input by one period translates the route rather than changing its parameters. If W is binary, A_W is a permutation/incidence matrix; if W has learned scalar weights, use one scalar per matching orbit and share it across all q.

## Key formulas

- $$W(i,j)=W(i+r,j-r)$$
- $$(s_{1},s_{2},i)\xmapsto{\,v^{q}\,}(s_{1}+qr,s_{2}-qr,i)$$
- $$y_{s_{1},s_{2}}=\phi\!\left(Bx_{s_{1},s_{2}}+\sum_{(i,j):\,W(i,j)\neq 0}W(i,j)\,U_{i,j}x_{\pi_{W}(s_{1},s_{2};i,j)}\right)$$

## Implementation notes

Integrate this at the token-mixing operation of a small ViT, grid transformer, or 2D SSM. Let the input be X with shape [batch, height, width, d]. Choose a period r and a matching table containing one destination offset for each source residue class modulo r; enforce the matching constraint by sampling a permutation or by using Sinkhorn during initialization and then projecting to the nearest permutation. For every token (h,w), compute its routed partner using the periodic rule W(i,j)=W(i+r,j-r), gather that token, apply a shared linear map U for its orbit, and add the result to a local residual projection Bx. Pseudocode: `res = B(X); for each residue edge e=(i,j): src = periodic_index(h,w,e); res += alpha[e] * U[e](gather(X,src)); Y = phi(res)`. Use one or a few matching layers before a dense MLP; optionally stack K independently shifted matchings so the receptive field grows while each layer remains O(HW d) rather than O((HW)^2 d). Compute the mathematical route exactly from the stored permutation; estimate no spectral quantities. First experiment: CIFAR-10 or ImageNet-100 with a 4-layer ViT at equal parameter count, comparing dense attention, local-window attention, and one to four matching layers. Measure validation accuracy, wall-clock throughput, and memory. Success is at least 2x lower attention-memory cost with no more than 1 percentage-point accuracy loss, or better accuracy than local windows at equal FLOPs.

## Disclaimer

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