# Tiny Recursive Message Passing

arXiv: https://arxiv.org/abs/2610.18649 · HTML: https://mlsanity.com/paper/2610.18649/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 32 of its 40 references that are in the map.
- First posted on arXiv 13 Oct 2026.

## Builds on (most cited first, 30 of 32)

- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling](https://mlsanity.com/paper/1412.3555/) (2014)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [Heterogeneous Graph Attention Network](https://mlsanity.com/paper/1903.07293/) (2019)
- [Deep Equilibrium Models](https://mlsanity.com/paper/1909.01377/) (2019)
- [Adaptive Computation Time for Recurrent Neural Networks](https://mlsanity.com/paper/1603.08983/) (2016)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Hierarchical Reasoning Model](https://mlsanity.com/paper/2506.21734/) (2025)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)
- [Multiscale Deep Equilibrium Models](https://mlsanity.com/paper/2006.08656/) (2020)
- [Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networks](https://mlsanity.com/paper/2106.04537/) (2021)
- [Implicit Graph Neural Networks](https://mlsanity.com/paper/2009.06211/) (2020)
- [Recurrent Relational Networks](https://mlsanity.com/paper/1711.08028/) (2017)
- [Approximation Ratios of Graph Neural Networks for Combinatorial Problems](https://mlsanity.com/paper/1905.10261/) (2019)
- [Neural Enhanced Belief Propagation on Factor Graphs](https://mlsanity.com/paper/2003.01998/) (2020)
- [Belief Propagation Neural Networks](https://mlsanity.com/paper/2007.00295/) (2020)
- [Goal-Aware Neural SAT Solver](https://mlsanity.com/paper/2106.07162/) (2021)
- [Probabilistic Tiny Recursive Model](https://mlsanity.com/paper/2605.19943/) (2026)
- [G4SATBench: Benchmarking and Advancing SAT Solving with Graph Neural Networks](https://mlsanity.com/paper/2309.16941/) (2023)
- [Equilibrium Reasoners: Learning Attractors Enables Scalable Reasoning](https://mlsanity.com/paper/2605.21488/) (2026)
- [Factor Graph Neural Networks](https://mlsanity.com/paper/2308.00887/) (2023)
- [Neural Learning of One-of-Many Solutions for Combinatorial Problems in Structured Output Spaces](https://mlsanity.com/paper/2008.11990/) (2020)
- [Implicit vs Unfolded Graph Neural Networks](https://mlsanity.com/paper/2111.06592/) (2021)
- [Deep Equilibrium Algorithmic Reasoning](https://mlsanity.com/paper/2410.15059/) (2024)
- [Symbol-Equivariant Recurrent Reasoning Models](https://mlsanity.com/paper/2603.02193/) (2026)
- [Lattice Deduction Transformers](https://mlsanity.com/paper/2605.08605/) (2026)

## Abstract (arXiv)

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 16k 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.