Evaluating Relational Reasoning in LLMs with REL

Lukas Fesser, Yasha Ektefaie, Ada Fang, Sham Kakade, Marinka Zitnik · 2026

Read Evaluating Relational Reasoning in LLMs with REL by Lukas Fesser, Yasha Ektefaie, Ada Fang, Sham Kakade, Marinka Zitnik (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-12176.txt.

Introduction

Fesser and four colleagues define relational complexity as the smallest number of entities that must be bound at once to apply a relation. They build REL, a benchmark spanning algebra, chemistry, and biology that varies this number within each domain. Across frontier models, performance falls steadily as complexity rises, even with entity counts held fixed. The failure persists under more test-time compute and in-context learning, pointing to a limit tied to binding arity itself.

Catalog record

CREATORLukas Fesser, Yasha Ektefaie, Ada Fang, Sham Kakade, Marinka Zitnik
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE77715
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.12176

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Evaluating Relational Reasoning in LLMs with REL Lukas Fesser, Yasha Ektefaie, Ada Fang, Sham Kakade, Marinka Zitnik Abstract Relational reasoning is the ability to infer relations that jointly bind multiple entities, attributes, or variables. This ability is central to scientific reasoning, but existing evaluations of relational reasoning in large language models often focus on structured inputs such as tables, graphs, or synthetic tasks, and do not isolate the difficulty introduced by higher-arity relational binding. We study this problem through the lens of Relational Complexity (RC) , which we define as the minimum number of independent entities or operands that must be simultaneously bound to apply a relation. RC provides a principled way to vary reasoning difficulty while controlling for confounders such as input size, vocabulary, and representational choices. Building on RC, we introduce REL , a generative benchmark framework spanning algebra, chemistry, and biology that varies RC within each domain. Across frontier LLMs, performance degrades consistently and monotonically as RC increases, even when the total number of entities is held fixed. This failure mode persists with increased test-time compute and in-context learning, suggesting a limitation tied to the arity of the required relational binding rather than to insufficient inference steps or lack of exposure to examples. Our results identify a regime of higher-arity reasoning in which current models struggle, and motivate re-examining benchmarks through the lens of relational complexity. Project Page GitHub Hugging Face Figure 1: a Performance decreases as relational complexity increases, even when the number of entities varies across tasks. Entity count is therefore a noisy proxy for task difficulty. b Relational complexity increases with the number of entities that must be jointly bound to satisfy a shared constraint, i.e., when correctness depends on a higher-arity relation. c REL evaluates relational reasoning in LLMs across algebra, biology, and chemistry. 1 Introduction Relational reasoning, the process of inferring an unknown from the interaction of multiple entities and relations, is widely regarded as a core component of human reasoning ( 32 ; 2 ; 21 ) . Despite recent progress on a broad range of reasoning tasks, Large Language and Reasoning Models (LLMs and LRMs) are rarely evaluated on relational reasoning ( 15 ; 16 ; 34 ; 28 ; 44 ; 73 ) . Research that studies relational reasoning in these models focuses on graph-based settings, including networks and knowledge graphs ( 72 ; 68 ; 76 ; 82 ; 25 ) , or on multi-hop reasoning over knowledge bases ( 78 ; 36 ; 69 ) . This leaves open a broader question: how well do state-of-the-art LLMs/LRMs handle relational structure in scientific reasoning , such as numerical pattern rules, algebraic constraints, and chemical structure regularities? We address this question with a unified set of tasks that varies relational complexity while controlling for other sources of difficulty, including entity complexity, across three scientific domains. In many scientific problems, the answer is not carried by any single cue. Instead, a model must combine multiple constraints that link variables, measurements, or symbols to reach a correct conclusion ( 4 ; 65 ) . When we cannot measure where models break under this multi-constraint integration, benchmark performance becomes difficult to interpret: strong results may reflect saturation rather than progress on harder forms of reasoning ( 19 ) . Identifying unsaturated dimensions of reasoning performance is necessary to understand where current models still fail and where further improvements are possible. Evaluating this capability is challenging because standard proxies for “difficulty” do not isolate the relational bottleneck. Performance can drop for reasons that have little to do with relational reasoning, such as longer prompts, different prompt templates, or additional background knowledge being required. As a result, evaluations often mix the cost of parsing and retrieval with the cost of relational inference. Existing studies have largely evaluated relational reasoning through graph-centric formulations ( 45 ) . Beyond graph tasks, we still lack a task-agnostic notion of relational difficulty. Here we introduce Relational Complexity (RC) as a principled measure of how many independent operands and entities must be represented and jointly composed to solve a task (Fig. Evaluating Relational Reasoning in LLMs with REL b). Importantly, relational complexity has a history outside of machine learning, where it is used in cognitive science and related fields ( 32 ; 11 ; 18 ) to characterize reasoning demands. In this paper, we present REL , a suite of tasks where relational complexity can be controlled. Our approach has the following advantages: (1) Parameterization of RC for scientific reasoning. We design tasks across mathematics, biology, and chemistry that allow systematic control over relational complexity (Fig. Evaluating Relational Reasoning in LLMs with REL c). (2) Isolating the effect of RC on performance. We isolate the impact of RC on LLM performance by controlling for and marginalizing over confounding factors. (3) A scalable framework for probing scientific relational reasoning. We introduce a generative benchmark that produces novel questions at systematically increasing levels of difficulty, enabling evaluation across model capabilities. Evaluating frontier LLMs on REL , we observe that performance degrades sharply as relational complexity increases across mathematical, biological, and chemical domains. Measures of RC are complementary to performance changes observed in size-based proxies including input length and entity count (Fig. Evaluating Relational Reasoning in LLMs with REL a). For Raven’s matrices and tensors in REL -A, performance drops by 45% when RC increases from 3 to 9. Applying RC to reasoning over evolutionary history with REL -B1, we find increasing RC from 5 to 20 leads to accuracy decreasing by 93%. In the chemistry tasks, task completion rate decreases by 39.7% from REL -C1 to REL -C3 when models reason over molecules represented as SMILES. Relational complexity reveals a clear and consequential limitation of current state-of-the-art models. 2 Related Work Reasoning Benchmarks in Machine Learning. Reasoning benchmarks in machine learning have expanded rapidly alongside the development of LLMs and LRMs. Existing benchmarks span a wide range of capabilities, including arithmetic and symbolic manipulation ( 34 ; 16 ) , program synthesis ( 3 ; 12 ) , logical deduction ( 15 ; 46 ; 67 ) , tool use ( 60 ; 41 ) , and multi-hop question answering ( 78 ; 36 ; 69 ) . A key limitation of existing benchmarks is the lack of explicit control over the relational structure underlying a task. Recent work has begun to probe LLMs’ ability to reason over graphs ( 72 ; 68 ; 76 ; 82 ; 25 ) and knowledge graphs ( 23 ; 84 ; 33 ; 42 ; 48 ) . 45 introduces a generative benchmark for relational reasoning, but their framework focuses on changing the underlying relational graph structure of tasks. While valuable, these settings rely on graph-specific formalisms that do not generalize cleanly to broader scientific reasoning tasks and often vary surface representations without systematically altering the underlying relational complexity. Relational Reasoning in Cognitive Science. In cognitive science, relational reasoning is commonly studied as the ability to represent relations among entities, align roles across multiple structures, and compose several relations to infer a missing element or choose a consistent completion ( 2 ; 20 ; 11 ; 32 ; 18 ) . Tasks such as

Read the complete text