When No Paths Lead to Rome: Benchmarking Systematic Neural Relational Reasoning

AI summary

Overview

Research area: neuro-symbolic and neural relational reasoning, with a focus on systematic generalization and benchmark design.

Technical level: Intermediate to Advanced (assumes familiarity with graph neural networks, transformer variants, and logic-programming concepts such as answer sets).

Scope: This paper introduces and analyzes NoRA, a new benchmark for evaluating whether neural models can perform systematic relational reasoning that goes beyond composing relations along a single path.

What This Paper Is About

Existing benchmarks for systematic relational reasoning, most notably CLUTRR and (to a lesser extent) STaR, assume that reasoning can be reduced to composing relations along a path between two entities in a knowledge graph. Several recent models hard-code this assumption into their architecture, so they score well on those benchmarks without genuinely learning to reason systematically. The authors build NoRA (Non-Path Reasoning with Ambiguous Facts), a benchmark that deliberately breaks the path-based assumption by requiring off-path reasoning, allowing multiple relationships between the same pair of entities, and injecting ambiguous facts that must be resolved through constraints.

Key Contributions

1. A new benchmark, NoRA. It uses realistic, everyday relationships (including gender-specific family roles such as "maternal aunt of" and relations such as "is schoolmates with" and "lives in the same place as"), and it is designed so that many problem instances cannot be solved by path composition alone.
2. Difficulty metrics that go beyond chain length. Four metrics are proposed: reasoning depth (number of inference steps), reasoning width (number of distinct derivations, capturing ambiguity), backtrack load or BL (ratio of inference steps to entities involved), and off-path edge count or OPEC (number of edges in a derivation that lie on no direct path between the query entities).
3. Systematic train/test splits built on those metrics. A controlled training distribution (depth ≤ 6, width ≤ 5, BL ≤ 1.5, OPEC ≤ 2) is paired with out-of-distribution test sets that each push one metric beyond the training range.
4. An empirical demonstration that state-of-the-art models struggle. Edge Transformers, RAT, EpiGNNs, NBFNet, and R-GCNs are evaluated, and all degrade sharply on the harder splits; large reasoning models o3 and o4-mini also fail on off-path problems even when given the world rules explicitly.
5. Two additional datasets. NoRA v1.1, generated by recursive subgraph expansion for guaranteed compositional generalization, and HetioNet, built on a different rule system involving diseases, genes, and drugs.

Main Findings

• Edge Transformers are the strongest of the evaluated models. The multi-edge ET reaches 0.900 exact-match accuracy in-distribution and the single-edge ET 0.885, but performance collapses on the OPEC test set (0.037 for multi-edge, 0.060 for single-edge).
• Off-path reasoning is the hardest axis for every model. All models perform poorly on OPEC, and on the ambiguity-free OPEC-na and BL-na splits. This is consistent with the authors' claim that most existing methods are aligned with path-based reasoning.
• GNNs fare poorly even in-distribution. EpiGNN-min with margin loss achieves 0.000 on BL and OPEC, and EpiGNN-min with BCE loss also scores 0.000 on both BL-na and OPEC-na. R-GCN reaches 0.032 on OPEC. NBFNet with margin loss scores 0.000 on every reported column.
• BCE loss and multiplication-based aggregation help EpiGNNs. EpiGNN-mul (BCE) reaches 0.520 in-distribution versus 0.451 for EpiGNN-min (BCE) and 0.334 for EpiGNN-min (margin), confirming that the margin-based loss is unsuitable for the multi-label setting.
• Reasoning width is surprisingly tractable. Most models perform reasonably on test-W (for example, ET multi-edge reaches 0.790), which the authors describe as surprising.
• Models perform better on BL than on BL-na. This contradicts the assumption that BL is the harder of the two, and further analysis showed models exploit shortcuts on the majority of ambiguous problems.
• The apparent robustness of Edge Transformers along difficulty axes is misleading. When reasoning depth is broken down while controlling for both BL and reasoning width, accuracy falls from above 0.8 at depth 4 to roughly 0.2–0.6 at depth 6 for the multi-edge ET. In this controlled analysis, the multi-edge variant clearly outperforms the single-edge variant.
• Hard instances are rare under random sampling. The authors note they cannot easily test reasoning depth above 12 or OPEC above 4 with the original sampling procedure, and that high-depth problems tend to have low OPEC and vice versa, which confounds difficulty analyses. NoRA v1.1 was created to address this.
• NoRA v1.1 confirms the main conclusions. Using recursive subgraph expansion, the authors include training examples with OPEC up to 3 and generate test instances that are guaranteed to be stitchable from training examples, yet models still fail on off-path reasoning.
• Large reasoning models fail at off-path reasoning even with the rules handed to them. On non-ambiguous problem instances with a single best label and two in-context demonstrations, o3 achieves near-perfect accuracy at OPEC 0, but at OPEC 3 none of the reasoning-depth-7 instances were answered correctly. Performance is slightly better at higher inference depths because of shortcut instances. o4-mini performs slightly worse than o3.

Methodology in Plain English

The authors generate stories: sets of facts about entities that satisfy a fixed set of "world rules." These rules include definite rules, which let new facts be inferred (for example, that living in the same place is transitive, or that schoolmates are underage), and constraint rules, which declare combinations of facts impossible (for example, that underage people cannot be parents). Some facts are deliberately ambiguous, expressed in Answer Set Programming syntax to say that one of several alternatives holds. The authors use Clingo 5.7.1 to compute answer sets — the consistent ways of resolving the ambiguity — and a relationship is treated as a correct answer for a query only if it holds in every answer set.

Difficulty is then quantified with four metrics: reasoning depth, reasoning width, backtrack load, and off-path edge count. Training data is capped on all four metrics, while test sets are constructed to exceed the training range on one metric at a time, giving both ambiguity-containing and ambiguity-free out-of-distribution splits plus in-distribution controls. A separate training set with no ambiguity at all (width 1) is used to evaluate the ambiguity-free splits.

Models evaluated are Edge Transformers in single-edge and multi-edge variants, relation-aware self-attention transformers in single-edge and multi-edge variants, EpiGNNs with margin or BCE loss and minimum or multiplication aggregation, NBFNet with margin or BCE loss, and R-GCNs. Ambiguities are encoded in the graph representation using special edges. Success is measured by exact match between the predicted relation set and the ground-truth set. For the large reasoning models o3 and o4-mini, the world rules were supplied explicitly and the evaluation was restricted to non-ambiguous instances with a single best label and two in-context demonstrations.

Why This Matters

The paper argues that a benchmark used to measure systematic reasoning should not be solvable by the architectural shortcut that most current models rely on. By showing that strong models fail when that shortcut is removed, it reframes progress in the field: improvements on CLUTRR-style tasks may reflect exploitation of benchmark structure rather than genuine compositional generalization.

Real-world applications implied by the work:

• Knowledge graph completion and query answering, where relevant facts frequently lie off the connecting path between two entities.
• Text-based reasoning, where ambiguous coreference (for example, which of two people a pronoun refers to) must be resolved using constraints.
• Biomedical reasoning over entity types such as diseases, genes, and drugs, which is the setting of the HetioNet dataset introduced in the paper.
• Narrative and social reasoning about kinship and everyday relationships, where multiple relationship types can hold simultaneously between the same pair of people.

Industry relevance: any system that answers multi-hop questions over structured or semi-structured data — search, enterprise knowledge graphs, clinical decision support — depends on combining evidence from more than one chain of facts, which is precisely what this benchmark stresses.

Future Directions

• Designing architectures that are not inherently limited to path composition and can handle off-path edges and multi-path combinations, since the evaluated models all degrade on OPEC.
• Better mechanisms for reasoning under ambiguity, since the authors found that models exploit shortcuts on most ambiguous problems rather than genuinely eliminating inconsistent possibilities.
• Generating systematically hard instances, which motivated NoRA v1.1; the authors note that random sampling rarely produces instances with high reasoning depth or high OPEC.
• Closing the gap for large reasoning models, which fail at off-path reasoning even when the correct world rules are provided in context; applying the correct rules is described as a prerequisite for the learning task.
• Extending the benchmark to rule systems beyond family and everyday relations, as partially started with HetioNet.

Target Audience

Researchers working on neuro-symbolic reasoning, compositional generalization, and graph neural networks; benchmark designers who need evaluation sets that resist shortcut exploitation; and practitioners building multi-hop reasoning systems over knowledge graphs or text who want to understand where current models break down.

Authors’ abstract

Designing models that can learn to reason in a systematic way is an important and long-standing challenge. In recent years, a wide range of solutions have been proposed for the specific case of systematic relational reasoning, including Neuro-Symbolic approaches, variants of the Transformer architecture, and specialised Graph Neural Networks. However, existing benchmarks for systematic relational reasoning focus on an overly simplified setting, based on the assumption that reasoning can be reduced to composing relational paths. In fact, this assumption is hard-baked into the architecture of several recent models, leading to approaches that can perform well on existing benchmarks but are difficult to generalise to other settings. To support further progress in the field of systematic relational reasoning with neural networks, we introduce NoRA, a new benchmark which adds several levels of difficulty and requires models to go beyond path-based reasoning.