Research map / Large language models / Agents, code and math
When No Paths Lead to Rome: Benchmarking Systematic Neural Relational Reasoning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces NoRA, an ASP-generated benchmark for systematic relational reasoning that requires off-path reasoning, ambiguous facts, and multi-relation labels, and shows that Edge Transformers, RAT, EpiGNN, NBFNet and R-GCN struggle on its off-path and branching splits.
Problem
Existing systematic relational reasoning benchmarks (CLUTRR, GraphLog, STaR) can be solved largely by path-based composition, so models with path-based inductive biases look strong on them but may not generalize to settings requiring off-path reasoning, ambiguity, or multiple relations between the s
Approach
A family-and-everyday-relations benchmark generated with Answer Set Programming, with controlled difficulty metrics (reasoning depth, width, backtrack load, and off-path edge count) and test splits that extend each metric beyond the training range, including ambiguous facts and multi-label targets.
Key results
- Edge Transformer multi-edge reaches 0.785 exact-match on BL but only 0.037 on OPEC; single-edge ET reaches 0.060 on OPEC, with most models near zero on OPEC and BL-na.
- o3 achieves near-perfect accuracy on OPEC 0 problems but fails on OPEC 3 problems when all world rules are given in context.
- On HetioNet, EpiGNN-min achieves 0.772 exact-match on Test-OPEC, the best among the evaluated models there, while ET single-edge leads in-distribution (0.838).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use multi-edge rather than single-edge input representation (ablation) | Edge Transformer · NoRA | exact-match accuracy: 0.885 -> 0.900; 0.741 -> 0.493; 0.703 -> 0.790; 0.245 -> 0.785; 0.060 -> 0.037 | Mixed |
| use multi-edge rather than single-edge input representation (ablation) | Edge Transformer · NoRA without ambiguity | exact-match accuracy: 0.800 -> 0.800; 0.822 -> 0.494; 0.104 -> 0.056; 0.110 -> 0.077 | Mixed |
| replace margin loss with BCE loss (ablation) | EpiGNN-min · NoRA | exact-match accuracy: 0.334 -> 0.451; 0.491 -> 0.665; 0.176 -> 0.456; 0.000 -> 0.154; 0.000 -> 0.005 | Helped |
| replace margin loss with BCE loss (ablation) | NBFNet · NoRA | exact-match accuracy: 0.000 -> 0.576; 0.000 -> 0.531; 0.000 -> 0.460; 0.000 -> 0.153; 0.000 -> 0.009 | Helped |
Surprising findings
- Ambiguity did not pose a particular challenge for tested models, but this was attributed to shortcuts that let models avoid reasoning about ambiguity.
- Models performed better on BL than on BL-na, despite BL being assumed harder.
Limitations
- Metrics such as reasoning depth and backtrack load depend on how the knowledge base is encoded; the true reasoning depth can be lower than measured.
- Reasoning width only partially captures differences between ambiguities.
- Randomly sampled test problems are rarely hard, so high-difficulty regimes are hard to test (motivating NoRA v1.1).
Experimental setup
Datasets: NoRA NoRA v1.1 HetioNet-inspired world (InspiredFromHetionet)
Benchmarks: NoRA test splits (In-dist, D, W, BL, OPEC and na variants) NoRA v1.1 HetioNet-inspired test splits
Metrics: exact-match accuracy weighted F1
Baselines: Edge Transformer RAT EpiGNN NBFNet R-GCN o3 o4-mini
Builds on: CLUTRR STaR Edge Transformer EpiGNN Clingo
Closest papers by meaning
- Systematic Relational Reasoning With Epistemic Graph Neural Networks (ICLR 2025 · similarity 0.92)
- When can transformers reason with abstract symbols? (ICLR 2024 · similarity 0.89)
- Boule or Baguette? A Study on Task Topology, Length Generalization, and the Benefit of Reasoning Trace (NeurIPS 2026 · similarity 0.87)
- Emergent Symbolic Mechanisms Support Abstract Reasoning in Large Language Models (ICML 2025 · similarity 0.86)
- LongCoT: Benchmarking Long-Horizon Chain-of-Thought Reasoning (ICML 2026 · similarity 0.86)
- Relational Programming with Foundational Models (AAAI 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.