# Zero-forcing causal lattice mixer

- ID: 2774
- Canonical URL: https://synthcore.org/idea/2774/zero-forcing-causal-lattice-mixer
- API JSON: https://synthcore.org/api/idea/2774.json
- API Markdown: https://synthcore.org/api/idea/2774.md
- Verification status: unverified
- Source: [arXiv:2608.27804](https://arxiv.org/abs/2608.27804)
- Category: architecture
- Solves: memory, scalability, sample-efficiency
- ML areas: graph-nn, ssm, memory, training
- Math tags: graph-theory, combinatorics, linear-algebra, spectral-theory
- Ratings: usefulness 5/10; difficulty 6/10; novelty 6/10

## Idea description

Build a sparse recurrent graph-neural layer on a path-by-path, path-by-cycle, or cycle-by-cycle latent lattice using a skew-zero-forcing seed set and its forcing order as a causal update schedule. Only the currently forced target node is activated at each step, so a small number of anchor states can propagate through the complete lattice while retaining local connectivity and periodic-boundary structure. The exact seed-count formulas predict the minimum number of anchors required by the graph family and expose parity effects that a generic boundary mask would miss.

## Mathematical statement

For a graph G without isolated vertices, a legal open-neighborhood sequence is a sequence S=(v_1,...,v_k) of distinct vertices satisfying N_G(v_i)\setminus\bigcup_{j<i}N_G(v_j)
eq\varnothing for every i; its maximum length is the Grundy total domination number \gamma_{\mathrm{gr}}^t(G). The paper uses \gamma_{\mathrm{gr}}^t(G)=|V(G)|-Z_{-}(G), where Z_{-}(G) is the minimum size of a skew-zero-forcing set. In the skew forcing process, a vertex with exactly one white neighbor forces that neighbor blue; the forcing vertex need not itself be blue. For Cartesian products, the associated sparse matrix pattern is the Kronecker difference A\otimes I-I\otimes B, with A and B factor-graph matrices and I identity matrices of matching sizes. The exact seed budgets are Z_{-}(P_a\square P_b)=a-\mathbf{1}_{\{a    ext{ odd},b    ext{ even}\}}, Z_{-}(P_p\square C_c)=\min\{p,c\} for odd c and \min\{2p,c\} for even c, and the cycle-cycle cases listed in the formulas. The network treats every forcing relation u    o v as a directed schedule edge and computes v from u plus already activated neighbors.

## Key formulas

- $$N_G(v_i)\setminus\bigcup_{j=1}^{i-1}N_G(v_j)\neq\varnothing\qquad\text{for every }1\leq i\leq k.$$
- $$\gamma_{\mathrm{gr}}^t(G)=|V(G)|-Z_{-}(G).$$
- $$Z_{-}(P_a\square P_b)=a-\mathbf{1}_{\{a\ {\rm odd},\,b\ {\rm even}\}},\qquad 2\leq a\leq b.$$
- $$Z_{-}(P_p\square C_c)=\begin{cases}\min\{p,c\},&c\text{ is odd},\\ \min\{2p,c\},&c\text{ is even},\end{cases}\qquad Z_{-}(C_a\square C_b)=\begin{cases}2a-1,&a=b\text{ odd},\\2a,&a=b\text{ even},\\\min\{b,2a\},&a<b,\ a\text{ odd},\\a,&a<b,\ a\text{ even},\ b\text{ odd},\\2a,&a<b,\ a,b\text{ even}.\end{cases}$$

## Implementation notes

1. Integration point: replace the dense spatial mixer in a small vision or grid-state model by a recurrent sparse message-passing layer over H    imes W, H    imes C, or C_1    imes C_2 latent nodes. Each node stores h_v, and each local lattice edge has a learned message map M_{u    o v}(h_u). Choose an anchor set B with size equal to the relevant Z_- formula and construct a forcing order offline. 2. Pseudocode: initialize active=B and set h_v=x_v for v in B; while active does not contain every node, inspect every vertex u and compute the number of inactive neighbors r(u)=|N(u)\setminus active|; select a u with r(u)=1, let v be its unique inactive neighbor, and update h_v=GRU(h_v, M_{u    o v}(h_u)+\sum_{w\in N(v)\cap active}M_{w    o v}(h_w)); mark v active and record u    o v. If no legal force exists, add an emergency anchor at the inactive vertex maximizing future closure and log this violation. 3. The paper supplies the target anchor count and parity-dependent graph-family budget. Compute the actual forcing order by greedy closure or beam search over boundary candidates, and verify closure and seed count exhaustively on small lattices. The neural weights, message maps, and GRU parameters are learned; the graph mask, anchor set, and schedule are fixed. 4. First experiment: train on 16x16 masked-MNIST or Moving-MNIST reconstruction with 10%, 25%, and 50% observed anchor nodes. Compare a standard 3x3 convolutional recurrent baseline and a synchronous GNN at equal parameter count. Measure reconstruction error versus message updates, peak activation memory, and robustness to missing anchors. Success means comparable or lower error with at least 2x fewer simultaneously stored activations, plus the predicted one-anchor parity difference between odd/even rectangular grids.

## Disclaimer

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