Tiny Recursive Message Passing

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 trends have, however, 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 adaptive halting and 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 above $99\%$ test accuracy on Sudoku-Extreme with a model of $16$k parameters, $50\times$ fewer than the previous best result 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 reporting results comparable to the state-of-the-art on Maze-unique, and zero-shot transfer to larger instances on N-Queens and Boolean satisfiability.