Tiny Recursive Message Passing

Tommaso Salvatori; Matteo Forasassi; Alexis Toumi; Giovanni de Felice

cs.LGOct 13, 2026

Tiny Recursive Message Passing

Authors: Tommaso Salvatori, Matteo Forasassi, Alexis Toumi, Giovanni de Felice

Organizations: Relational Intelligence, Inc · Vienna University of Technology

Abstract

Message passing neural networks have shown remarkable performance in algorithmic and constraint reasoning, due to their ability to encode the structure of the task directly in the architecture. Recent work has shown that better results can be achieved using recursive transformers trained with deep supervision and truncated recursions, which make extremely deep loops stable to train, and equipped with test-time procedures such as discrete deduction lattices. In this work, we apply the same procedures to message passing networks, and show that the two ingredients are complementary, and lead to parameter efficient models: we obtain about $99\%$ test accuracy on Sudoku-Extreme with a model of $16$ k parameters that trains in about $10$ minutes on an H100, or in $9$ hours on a CPU. We further show that the cost of truncating gradients grows with the number of rounds information needs to cross the graph, making the choice of wiring a trade-off between robustness to truncation and transfer across problem sizes. We conclude by showing that our models transfer zero-shot to larger instances than those seen during training, outperforming popular neural baselines on N-queens and Boolean satisfiability with a fraction of their parameters.

Figures & tables

Figure 1: (a) On the left, a graph with four nodes

(u,v,w,z)

, of types

(\tau_{1},\tau_{2},\tau_{2},\tau_{3})

respectively. On the right, the trajectory of a single message passing step on the corresponding model. The three types correspond to three different neural modules

f_{\tau}

, while modules of the same type are identical and share their weights. (b) Structure of the two main neural modules used in this work. The pooling module is invariant, and carries a latent state, used to compute the output when the iterative process has converged; the deep sets module is equivariant, and does not carry any latent memory.

	Peer Graph no Lattice (32k)			Lattice (<24k)		Baselines (32k)
Dataset	Single Pass	Noisy Single	best-of- $64$	Peer graph	Factor graph	LDT	Graph-LDT	RRN	SE-RRN
Sudoku-Extreme	$98.7{\scriptstyle\,\pm\,0.06}$	$98.2{\scriptstyle\,\pm\,1.2}$	$\mathbf{99.9}{\scriptstyle\,\pm\,0.1}$	$99.1{\scriptstyle\,\pm\,0.04}$	$97.6{\scriptstyle\,\pm\,0.04}$	$96.9{\scriptstyle\,\pm\,0.5}$	$98.1{\scriptstyle\,\pm\,0.4}$	$13.2{\scriptstyle\,\pm\,2.9}$	$41.1{\scriptstyle\,\pm\,6.3}$
Maze-Unique	$99.9{\scriptstyle\,\pm\,0.0}$	$99.9{\scriptstyle\,\pm\,0.1}$	$\mathbf{100}{\scriptstyle\,\pm\,0.0}$	$99.9{\scriptstyle\,\pm\,0.0}$	n.a.	$18.6{\scriptstyle\,\pm\,3.2}$	$99.4{\scriptstyle\,\pm\,0.2}$	$5.8{\scriptstyle\,\pm\,2.7}$	$11.3{\scriptstyle\,\pm\,4.2}$

Table 1: Performance on Sudoku-Extreme and Maze-Unique.

Figure 2: (a) Sudoku-extreme with the full gradient and lattice; (b) The same comparison under truncated backpropagation, $12\times 6$ ; (c) Maze-unique, 24 $\times$ 8, sweeping the truncation depth with the lattice; (d) Training curves when only $g$ rounds carry the gradients, no lattice; (e) Test-time extrapolation: board accuracy as a function of the number of inference steps $t$ for the same configurations; (f) Test accuracies using the lattice, under different numbers of cycles and rounds with gradient $g$ .

Panel of Figure 3 — Figure 3: Zero-shot size transfer on N-Queens. Left: Full board accuracy across test board sizes using a single deterministic pass. Right: Full board accuracy via multiple probabilistic passes, assuming we have access to a verifier.

		G4SATBench						RandCSPBench
		Easy		Medium		Hard		$N\leq 256$
Model	Params	SR	3-SAT	SR	3-SAT	SR	3-SAT	3-SAT	4-SAT
NeuroSAT	$430$ k	$79.79$	$80.59$	$37.25$	$41.61$	$5.19$	$11.34$	$84.48$	$47.52$
GGNN	$445$ k	$78.75$	$76.42$	$21.18$	$25.68$	–	–	–	–
QuerySAT	$363$ k	–	–	–	–	–	–	$92.38$	$66.57$
Ours, ACT ( $P=1$ )	$65$ k	$79.1_{\pm 1.5}$	$75.6_{\pm 0.7}$	$36.6_{\pm 1.1}$	$42.8_{\pm 3.4}$	$8.0_{\pm 0.4}$	$17.7_{\pm 3.3}$	$83.6_{\pm 1.1}$	$48.0_{\pm 4.7}$

Table 2: Solve rate on G4SATBench ( Li et al., 2024 ) and RandCSPBench ( Skenderi et al., 2026 ) , mean

\pm

sample standard deviation over three seeds. Zero-shot transfer models are trained on medium and evaluated on hard without further tuning; RandCSPBench is scored against the benchmark’s satisfiable set. All baseline solve rates are taken from the original work. NeuroSAT implementation is the same in both RandCSPBench and G4SATBench.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Task and wiring	Budget	Widths	Parameters
Sudoku, peer graph	16k	$(10,27,55,14)$	16,485
Sudoku, peer graph	24k	$(12,34,65,16)$	23,978
Sudoku, peer graph	32k	$(15,39,76,20)$	32,763
Sudoku, peer graph, with halting head	32k	$(15,39,76,20)$	32,784
Sudoku, factor graph	16k	$(9,24,48,12)$	16,543
Sudoku, factor graph	32k	$(13,34,68,17)$	32,798

Appendix

Table 3: Widths

(n,m,n_{\mathrm{hid}},m_{a})

and exact parameter counts of the models in this appendix. Sizes are referred to by their nominal budget.

	Full gradient	Width study	Credit-horizon ablation
	factor graph	peer graph	peer graph	factor graph
Shape $C\times R$	$14\times 2$	$12\times 5$	$\{4,7,10\}\times 5$	$\{7,10\}\times 5$
Detached cycles $D$	0	11	$C-1$ , $C-2$	$C-1$ , $C-2$
Credit horizon $h$	28	5	5, 10	5, 10
Widths	$(9,24,48,12)$	6k–32k; 24k: $(12,34,65,16)$	$(10,27,55,14)$	$(9,24,48,12)$
Peak learning rate	$6.8742\times 10^{-3}$	$4.8119\times 10^{-3}$	$6.8742\times 10^{-3}$	$6.8742\times 10^{-3}$

Appendix

Table 4: Lattice recipes for Sudoku-Extreme.

h

counts rounds; a cell-to-cell exchange takes one round in the peer graph and two in the factor graph.

	6k	9k	12k	16k	24k	32k
Peer, $12\times 5$ , $D=11$ ( $h=5$ )	$53.9\pm 6.5$	$87.4\pm 2.7$	$98.5\pm 0.2$	$98.6\pm 0.3$	$\mathbf{99.1\pm 0.2}$	$98.1\pm 0.4$
FG, $12\times 5$ , $D=10$ ( $h=10$ )	–	–	$82.9\pm 2.2$	–	–	$97.6$
Peer, $4\times 6$ , $D=0$ (full)	$54.9\pm 10.8$	$89.6\pm 5.7$	$97.7\pm 0.9$	$98.8\pm 0.3$	$98.3\pm 0.6$	$99.4\pm 0.1$

Appendix

Table 5: Sudoku-Extreme, lattice model, truncated width study. Exact test accuracy (%) on 1,000 puzzles, mean

\pm

standard deviation over independent runs. The last row is the full-gradient reference.

	$h=5$ (one cycle)	$h=10$ (two cycles)
Peer graph	97.5	98.3
Factor graph	85.3	95.7

Appendix

Table 6: Sudoku-Extreme, lattice model, credit-horizon ablation at 16k parameters with

R=5

. Mean exact test accuracy (%) over all shapes and runs of each cell.

	Main recipe	Credit-horizon ladder	Truncation ladder
Shape $C\times R$	$8\times 12$	$9\times 3$	$8\times 12$ , $4\times 12$
Detached cycles $D$	6	8, 6, 3, 0	$C-2$ , $C-1$
Credit horizon $h$	24	3, 9, 18, 27	24, 12
Peak learning rate	$7.5\times 10^{-4}$	$1.5\times 10^{-3}$	$1.5\times 10^{-3}$
Training steps	275,000	150,000	180,000
Board-level halting loss	$\lambda_{\mathrm{board}}=1$	–	–

Appendix

Table 7: ACT recipes for Sudoku-Extreme, 32k peer graph,

(15,39,76,20)

$9\times 3$				$R=12$
$D$	$h$	Accuracy	Escape step	$C\times R$	$D$	$h$	Accuracy
8	3	15.8	never	$8\times 12$	7	12	34.4
6	9	25.0	never	$8\times 12$	6	24	89.6
3	18	41.4	$\sim$ 64k	$4\times 12$	3	12	31.9
0	27	87.2	$\sim$ 40k	$4\times 12$	2	24	61.2

Appendix

Table 8: Sudoku-Extreme, ACT model: validation board accuracy (%) at a fixed compute of 128 deep-supervision steps. Left: credit-horizon ladder after 150,000 steps. Right: truncation ladder after 180,000 steps.

	Lattice	ACT
Shape $C\times R$	$24\times 8$	$12\times 12$
Detached cycles $D$	20	10
Credit horizon $h$	32	24
Parameters	9k–128k; 32k: $(12,31,64,16)$	60,720; $(16,42,84,21)$
Optimiser	AdamW, $\beta=(0.9,0.95)$ , decay on matrices only
Peak learning rate	$3.4\times 10^{-4}$	$7.5\times 10^{-4}$

Appendix

Table 9: Truncated-gradient recipes for Maze-unique.

Budget	Steps	Accuracy
128k	10,000	99.10
64k	12,000	99.63
32k	15,000	99.90
16k	20,000	98.92
12k	25,000	99.20
9k	25,000	99.15

Appendix

Table 10: Maze-unique, lattice model,

24\times 8

D=20

(

h=32

). Exact test accuracy (%) on 1,000 mazes, averaged over the runs that passed the validation threshold of val accuracy

>40\%

Shape ( $h$ )	9k	12k	16k	32k
$24\times 8$ , $D=20$ (32)	$99.7\pm 0.5$	$99.5\pm 0.5$	$99.3\pm 0.7$	$99.9\pm 0.0$
$24\times 8$ , $D=22$ (16)	$98.7\pm 0.9$	$95.5\pm 3.7$	$98.2\pm 1.5$	$98.7\pm 0.9$
$16\times 8$ , $D=12$ (32)	$99.4\pm 0.4$	$99.8\pm 0.2$	$99.3\pm 0.7$	$99.3\pm 0.3$

Appendix

Table 11: Maze-unique, lattice model, shape study. Exact test accuracy (%), mean

\pm

standard deviation over the best runs of each cell.

$N$	Solutions of the board	Train puzzles	Test puzzles	Test orbits	Coverage floor
10	724	13,442	2,372	756	0.426
11	2,680	–	703	703	0.146
12	14,200	–	736	736	0.037
13	73,712	–	777	777	0.009
14	365,596	–	782	782	0.002
15	2,279,184	–	799	799	0.0005

Appendix

Table 12: N-Queens datasets. Orbits are dihedral orbits of puzzles. The coverage floor is the mean of

1/|\mathcal{S}(x)|

over the test puzzles, i.e. the coverage of a model that always returns a single correct solution.

Neural Algorithmic Reasoning

Neural algorithmic reasoning studies how neural networks can learn, execute, and generalize algorithmic procedures.

See all 45 papers

Form Follows Function: Recursive Stem Model
Mar 3, 2026Navid HakimiRecursive Reasoning Models Neural Algorithmic Reasoning
What Limits Recursive Reasoning Models: Optimization, Architecture and Test-Time Scaling
Sep 30, 2026Yuliana Shakhvalieva, Dmitrii Kharchev, Viacheslav Bezrukov +4Recursive Reasoning Models Neural Algorithmic Reasoning
RND NLP, DAIMLD, Russian Federation
Universal Transformers Need Memory: Depth-State Trade-offs in Adaptive Recursive Reasoning
Apr 23, 2026Grigory SapunovMemory-Augmented Neural Networks Sudoku Solving
Intento

Mar 3, 2026J/K move · Enter open · S save

Form Follows Function: Recursive Stem Model

Navid Hakimi

Recursive Reasoning Models Neural Algorithmic Reasoning Algorithmic Reasoning Test-Time Scaling

Open paper AskPDF arXiv

Recursive reasoning models such as Hierarchical Reasoning Model (HRM) and Tiny Recursive Model (TRM) show that small, weight-shared networks can solve compute-heavy and NP puzzles by iteratively refining latent states, but their training typically relies on deep supervision and/or long unrolls that increase wall-clock cost and can bias the model toward greedy intermediate behavior. We introduce Recursive Stem Model (RSM), a recursive reasoning approach that keeps the TRM-style backbone while changing the training contract so the network learns a stable, depth-agnostic transition operator. RSM fully detaches the hidden-state history during training, treats early iterations as detached "warm-up" steps, and applies loss only at the final step. We further grow the outer recursion depth

H

and inner compute depth

L

independently and use a stochastic outer-transition scheme (stochastic depth over

H

) to mitigate instability when increasing depth. This yields two key capabilities: (i)

>20\times

faster training than TRM while improving accuracy (

\approx 5\times

reduction in error rate), and (ii) test-time scaling where inference can run for arbitrarily many refinement steps (

\sim 20,000 H_{\text{test}} \gg 20 H_{\text{train}}

), enabling additional "thinking" without retraining. On Sudoku-Extreme, RSM reaches 97.5% exact accuracy with test-time compute (within ~1 hour of training on a single A100), and on Maze-Hard (

30 \times 30

) it reaches ~80% exact accuracy in ~40 minutes using attention-based instantiation. Finally, because RSM implements an iterative settling process, convergence behavior provides a simple, architecture-native reliability signal: non-settling trajectories warn that the model has not reached a viable solution and can be a guard against hallucination, while stable fixed points can be paired with domain verifiers for practical correctness checks.

Abstract

Neural Algorithmic Reasoning

Explore similar work

Form Follows Function: Recursive Stem Model

What Limits Recursive Reasoning Models: Optimization, Architecture and Test-Time Scaling

Universal Transformers Need Memory: Depth-State Trade-offs in Adaptive Recursive Reasoning