Source-linked AI summary
Recurrent Relational Networks
Rasmus Berg Palm, Ulrich Paquet, Ole Winther
TL;DR
The paper addresses tasks requiring chains of interdependent relational inferences, where standard architectures and single-step relational modules are limited. It introduces a recurrent relational network that performs iterative graph-based reasoning, achieving strong results on bAbI and Sudoku while using Pretty-CLEVR to probe reasoning depth. The authors report 20/20 bAbI tasks in 13 of 15 runs and 96.6% accuracy on the hardest Sudoku puzzles.
Problem
Many-step relational reasoning remains challenging for deep learning architectures, while standard MLPs, CNNs, and single-step relational networks are limited in handling extended object interactions.
Method
The recurrent relational network performs iterative message passing and recurrent node updates on graph representations, with losses applied at every step.
Results
20/20 bAbI tasks were solved in 13 of 15 runs, and 96.6% of the hardest Sudoku puzzles were solved after 64 test-time steps.
Takeaways & Limitations
Recurrent relational networks support relational reasoning across substantially more steps than the few-step settings of prior relational benchmarks, including Sudoku tasks requiring more than ten steps.
Takeaways & Limitations
Applying loss at every step might encourage a greedy algorithm that becomes stuck in a local minimum, although the separated output function preserves capacity for non-greedy multi-step computation.
Abstract
from arXiv · showhide
This paper is concerned with learning to solve tasks that require a chain of interdependent steps of relational inference, like answering complex questions about the relationships between objects, or solving puzzles where the smaller elements of a solution mutually constrain each other. We introduce the recurrent relational network, a general purpose module that operates on a graph representation of objects. As a generalization of Santoro et al. [2017]'s relational network, it can augment any neural network model with the capacity to do many-step relational reasoning. We achieve state of the art results on the bAbI textual question-answering dataset with the recurrent relational network, consistently solving 20/20 tasks. As bAbI is not particularly challenging from a relational reasoning point of view, we introduce Pretty-CLEVR, a new diagnostic dataset for relational reasoning. In the Pretty-CLEVR set-up, we can vary the question to control for the number of relational reasoning steps that are required to obtain the answer. Using Pretty-CLEVR, we probe the limitations of multi-layer perceptrons, relational and recurrent relational networks. Finally, we show how recurrent relational networks can learn to solve Sudoku puzzles from supervised training data, a challenging task requiring upwards of 64 steps of relational reasoning. We achieve state-of-the-art results amongst comparable methods by solving 96.6% of the hardest Sudoku puzzles.
1 Introduction
The paper targets many-step relational reasoning, where objects and their interactions must be tracked across interdependent steps. It introduces a recurrent relational network to provide this capacity within end-to-end differentiable models.
- Motivation: Many-step relational reasoning requires reasoning about objects and their interactions over successive, interdependent steps.Sudoku illustrates this process: placing a digit affects other cells through shared rows, columns, and boxes.
- Motivation: MLPs and CNNs process an entire Sudoku in one forward pass, ignoring object-level interaction structure and falling short on basic relational reasoning.
- Limitations of prior work: Santoro et al.’s relational network performs a single relational operation and was evaluated on datasets requiring at most three reasoning steps.
- Contribution: The recurrent relational network is a modular, end-to-end differentiable component for many-step reasoning over object representations.It encodes assumptions that objects have properties, properties change, and objects affect one another through time-invariant interactions.
- Architecture: The relational reasoning module operates on graph nodes and directed edges, complementing a perceptual front-end that converts raw inputs into vector representations.
- Setting: Hand-crafted symbolic Sudoku solvers are efficient and exact but cannot integrate with differentiable perceptual front-ends because they do not operate on real-valued vectors.
2 Recurrent Relational Networks
The recurrent relational network performs iterative message passing on a graph, updating node states and producing outputs at each step. Supervision at every step encourages convergent multi-step reasoning while supporting graph and output variations.
- Message passing: At each iteration, nodes send learned messages to neighboring nodes, and each receiver aggregates incoming messages by summation.For Sudoku, messages communicate constraints such as removing a given digit from related cells.
- Message passing on a graph: In Sudoku, each graph node represents a cell and connects to cells in the same row, column, and box.Node features encode the initial cell content and location-related information; the graph may be supplied by a perceptual front-end.
- Recurrent updates: Recurrent node updates combine the current messages with the previous hidden state and input features, allowing information to accumulate across iterations.Retaining the previous state lets the network work toward a solution instead of restarting from the input at every step.
- Supervised training: The model maps each node’s hidden state to a probability distribution over digits and trains with summed cross-entropy across nodes.
- Convergent message passing: Losses are applied at every step, encouraging convergent message passing and helping address vanishing gradients.At test time, only the final-step output probabilities are used.
- Variations: The architecture can assume a fully connected graph when edges are unknown, incorporate edge attributes, or produce a single output for the whole graph.
3 Experiments
Experiments evaluate the recurrent relational network on bAbI, Pretty-CLEVR, and Sudoku, testing whether repeated relational updates improve performance as reasoning depth increases. The model solves all bAbI tasks, handles variable-depth Pretty-CLEVR questions, and reaches 96.6% on the hardest Sudoku puzzles after extended inference.
- 3.1 bAbI question-answering tasks: 20/20 bAbI tasks are solved in 13 of 15 runs, with dropout and question encodings identified as important for performance.The network requires only one relational step on bAbI, despite the hardest tasks requiring reasoning about three facts.
- 3.2 Pretty-CLEVR: Pretty-CLEVR varies relational difficulty by asking questions requiring different numbers of jumps among eight colored shapes.Zero-jump questions are non-relational, while the dataset includes questions requiring up to multiple relational steps.
- 3.2 Pretty-CLEVR: The MLP solves non-relational Pretty-CLEVR questions but struggles with one jump, whereas the relational network declines as jump count increases.The recurrent relational network generally performs well when its number of reasoning steps is at least the number of jumps.
- 3.3 Sudoku: 94.1% of the hardest 17-givens Sudokus are solved after 32 steps, with complete-puzzle accuracy requiring every digit to be correct.Accuracy approaches 100% as the number of givens increases, and the network produces probability distributions at each step.
- 3.3 Sudoku: 96.6% of 17-givens Sudoku puzzles are solved after 64 steps, up from the 32-step evaluation.Even 33-givens Sudokus require upwards of 10 relational steps, while harder puzzles continue improving beyond 32 steps.
- 3.3 Sudoku: Multiple relational steps are crucial for Sudoku: the one-step node-centric relational network fails to solve any puzzle, while the recurrent model outperforms compared differentiable methods.The comparison includes loopy belief propagation variants and a convolutional approach.
4 Discussion
The recurrent relational network targets substantially deeper relational reasoning than prior comparable tasks and achieves strong results on bAbI and Sudoku. Its parallel message aggregation can function as an implicit attention mechanism, while the output design preserves capacity for non-greedy multi-step computation.
- 96.6% of the hardest Sudokus with 17 givens were solved, while 20/20 bAbI tasks were solved in 13 of 15 runs.
- The model addresses Pretty-CLEVR tasks requiring up to eight reasoning steps and Sudoku tasks requiring more than ten steps.
- Separating node states and output probabilities lets the network retain a current best guess while running a non-greedy multi-step algorithm.
- Summing incoming messages can act as an implicit attention mechanism because receiving nodes influence which messages are effectively received.
5 Related work
The paper situates recurrent relational networks among graph message-passing, learned inference, symbolic-neural reasoning, and differentiable optimization approaches. It emphasizes design choices for stable multi-step reasoning and notes comparison limits for scalable Sudoku solvers.
- Single-step relational and interaction networks cannot naturally perform complex multi-step reasoning without compressing relations into a fixed-size vector.
- Including node features at every recurrent step and optimizing loss at every step are presented as important for stable multi-step reasoning.
- The model is framed as a learned message-passing algorithm related to belief propagation and inference machines.
- The paper does not introduce explicit logic, discover fuzzy logic rules, or impose logical constraints as prior knowledge.
- Direct comparison with OptNet is unavailable because OptNet has computational scaling issues on 9-by-9 Sudokus.
- CommNet differs by using the same messages across nodes at each step and by not optimizing loss at every step.
6 Supplementary Material
The supplementary material documents implementation choices for bAbI experiments, including feature construction, recurrent updates, training configuration, and ablation setup. It also identifies the reported ablation table as covering model runs and error outcomes.
- Each bAbI node feature combines fact and question encodings with a randomized, order-preserving sentence-position representation.The random offset prevents memorizing absolute fact positions while preserving relative order.
- The bAbI model uses an LSTM-based node update and runs the network for three reasoning steps.
- Training jointly covers all 20 tasks using 9,000 training samples, 1,000 validation samples, Adam, batch size 512, and 5M gradient steps.
- Ablations test sentence-question encoding choices and replace the four-layer MLP with a single linear layer in one condition.
- Table 3 reports model runs, mean error, failed tasks, and mean error at 1M updates.
6.3 Pretty-CLEVR experimental details
The Pretty-CLEVR experiments compare recurrent, single-step relational, and whole-scene MLP baselines under a compact graph-based setup. The reported configuration includes positional, color, marker, and jump information, recurrent updates, augmentation, and separate validation and test sets.
- The Pretty-CLEVR setup uses 128 hidden units, with MLPs consisting of one ReLU layer followed by a linear layer unless otherwise specified.
- Node features represent position, color, marker, the start-object attribute, and the number of jumps.
- The recurrent relational network uses an MLP message function, an MLP node function, and four recurrent reasoning steps.
- Training uses 12.8M questions, random scene scaling and rotation, validation and test sets of 128,000 questions, and 10M gradient updates.
- The RN baseline is identical to the recurrent relational network except that it performs one relational reasoning step.
- The baseline MLP receives the entire scene state and has 87% more parameters than the RN and RRN.The parameter counts are 261,136 for the MLP versus 139,536 for the RN and RRN.
6.4 Sudoku dataset
The Sudoku dataset is built from solved 17-givens puzzles, sampled into training, validation, and test sets with randomized additional digits. Each cell is represented using its digit and grid position, and the recurrent model is trained with repeated outputs.
- 49,151 unique 17-givens puzzles are split into 38,151 training, 1,000 validation, and 10,000 test puzzles.
- The network uses 96 hidden units, with three-ReLU-layer MLPs followed by linear layers.
- Each Sudoku cell is represented by its digit, row, and column position, with digits and positions mapped through learned embeddings.Each embedding is 16-dimensional, and edge features are not used.
- The output function is a linear layer producing nine logits for each cell’s digit prediction.
- The model runs for 32 steps and is trained with a loss at every step using Adam, 300,000 updates, batch size 256, and learning rate 2e-4.L2 regularization is 1e-4 on all weight matrices.
6.6 Sudoku relational network baseline details
The baseline comparison contrasts node-centric recurrent reasoning with a graph-centric relational-network-style model. The age-arithmetic task uses graph-structured facts and evaluates reasoning depth through shortest paths and recurrent test steps.
- The graph-centric baseline performs one relational-reasoning step, sums node states, and maps the result to 81 × 9 Sudoku outputs with a four-layer MLP.Its hidden states have size 256 to compensate for compressing the graph into a fixed-size vector.
- The age-arithmetic dataset contains 262,144 unique eight-node trees, split 90%/10% into training and test graphs.
- Each graph supplies seven relative age facts, one absolute age fact, and a question whose shortest path determines the minimum arithmetic computations required.
- The eight facts are provided as a fully connected graph, although the network never observes the tree used to generate them.
6.9 Full Sudoku solution
The supplied passages describe an age-arithmetic results figure and an example recurrent relational network graph, alongside a visualization of Sudoku predictions before message-passing steps.
- Figure 5 reports age-arithmetic results while varying the number of recurrent relational network steps used during testing.
- The figure uses random selection from 100 possible ages as a reference condition.
- The recurrent relational network illustration shows a fully connected graph with three nodes and recurrent connections across steps.
- The Sudoku example visualizes each cell’s digit probabilities at step 0 before any recurrent steps are taken.