acceptodds
Under review as a conference paper at ICLR 2027

Tiny Recursive Message Passing

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 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 test accuracy on Sudoku-Extreme with a model of k parameters, fewer than the previous best result that trains in about minutes on an H100, or in 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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Message passing neural networks, recursive reasoning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_3CJWOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper adapts recursive training and inference techniques, including deep supervision, truncated gradients, adaptive halting, and discrete deduction lattices, to message-passing networks. Experiments are mostly focused on Sudoku, while it has also some additional on mazes, N-Queens, and SAT. A central finding is that sensitivity to gradient truncation depends on the graph’s propagation distances.

Critical strengths

The paper demonstrates strong parameter efficiency and provides useful comparisons between graph structures, training procedures, and inference strategies. The analysis of gradient truncation offers insight into how graph connectivity affects learning. Experiments on multiple tasks, including transfer to larger N-Queens and SAT instances, strengthen the contribution beyond Sudoku alone.

Critical weaknesses

The abstract could state the central goal more directly and clarify how message passing supports algorithmic reasoning; the broad title could better reflect the controlled puzzle setting. Although the related work is substantial, it omits "Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error", "Causal Language Modeling Can Elicit Search and Reasoning Capabilities on Logic Puzzles", and "Learning to Solve Constraint Satisfaction Problems with Recurrent Transformer". Sudoku training uses only 1,000 base puzzles with augmentation, leaving broader generalization uncertain. The model-selection protocol also needs clarification, and minor presentation issues include an unresolved “Sec. ??” (line 296) reference and the semicolon before “None” at line 193.

Questions for authors
  • Could you evaluate online training with freshly generated Sudoku puzzles, for example using SudokuPy, as in Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error?

  • Given the use of only 1,000 base training puzzles, what evidence rules out overfitting to this dataset despite augmentation? If computationally feasible, evaluation on a broader Sudoku distribution and independent datasets with different difficulty levels would strengthen the generalization claims.

  • Could you also clarify the discrepancies in model selection and validation-set sizes, and compare methods under matched inference budgets?

  • Section 5.1 states that model configurations were selected using test accuracy, whereas Appendix S3 describes checkpoint selection using validation accuracy. Was the test set used for any configuration or model selection? Also, could you clarify why Section 5.1 reports 300 validation puzzles while Appendix S3 reports 500?

  • Finally, how do comparisons change when inference budgets, including the 64 stochastic chains, are matched?

Reviewer_UZTcOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This paper proposes to merge two approaches for reasoning models on graphs: on one hand, the use of recursive transformers, and on the other the natural ability of message passing models to encode the structure of the problem. The resulting approach obtains very small models that train quickly and reach state of the art result on several benchmarks.

Critical strengths
  • The method, which consists in merging techniques developed for transformers and message passing neural networks look promising, although the lack of clarity of the paper hinders clear and definitive identification of the novel elements.
  • The evaluation results seem are good, beating the baselines by wide margins.
Critical weaknesses

The main weakness of this paper is its lack of clarity: in several places, notions are used and not properly defined.

  • Tiny/recursive models, since they are so central to the approach, they should be described in a non ambiguous manner in the related work section.
  • the notions of HRM and TRM are used but never introduced
  • Similarly, in equation 1, while m_t is understandable, p_t is not defined at all (I assumed it was the dimension of u_v?).
  • The notion of "ports" is used but never defined
  • Figure 1. is never referenced in text
  • The input and outputs of the model are never properly defined.
  • It is also unclear what part of the presented models is the actual contribution. Section 4 presents "techniques already present in the literature". After this part, it seems that the global model is an assembly of those preexisting techniques (which qualifies as novel but better positioning would help identifying the relevance).
  • Part 5: missing reference "(Sec. ??)".
Questions for authors
  • What is meant by "accuracy" in the reported results? Is it the percentage of problems that obtained a feasible solution? Or the percentage of each solution that was correct? Or is it something else entirely?
  • What is the input of the model? What is the output? How is the loss computed? The "Adaptive computation time" paragraph seems to contain some relevant information but is not sufficient to fully understand whether a ground-truth solution is used and compared in lattice-form, or if some other mechanism is leveraged.
  • What is the contribution precisely? It should be clearly separated from the preexisting literature. A clean figure would probably help understanding.
Reviewer_cAzoOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes to port recent develpment in the are of recursive computation (adaptive computation) to graph neural networks.

The paper describes two architectures: invariant and equivariant.

The method consists of adapting previously published approaches to the message-passing architecture.

The architecture considers discrete problems.

Three classes of experiments are described: Sudoku, board games (n-queens), and SAT problems. The baseline for some problems seems weak (e.g. Recursive GNN), but the model shows good performance.

Critical strengths

The paper addresses a class of problems that are hard to solve due to their discrete nature, where standard GNN prediction does not work well.

The paper's objective is clear: "In this work, we implement, adapt, and test all of them to see which one performs better and in which case." in the domain of graph neural network architectures.

Performance results show that the proposed architecture works well on the provided experiments.

Critical weaknesses

The contribution of the paper is incremental.

It is not a new architecture.

The work focuses more on model selection and evaluation, even though the architectural methods are justified.

If the contribution is the evaluation of a set of methods on graphs, it is not enough for the conference.

Who, how, and when is the graph computed (peer or factor)?

minor:

  1. References are not in parentheses.
  2. "it to transfer across sizes (Sec. ??). In ..."
Questions for authors

The use of three loops seems arbitrary, and the role of the last loop and the additional "answer" state is not clear, apart from the advantage of the "outer loop and has been shown to be fundamental for propagating information across the different nested loops"

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.