Reasoning Models Reason Well, Until They Don’t

Revanth Rameshkumar, Jimson Huang, Yunxin Sun, Fei Xia, Abulhair Saparov · 2025

Read Reasoning Models Reason Well, Until They Don’t by Revanth Rameshkumar, Jimson Huang, Yunxin Sun, Fei Xia, Abulhair Saparov (2025) 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-2510-22371.txt.

Introduction

Revanth Rameshkumar and four co-authors test whether large reasoning models, trained to argue step by step and check their own work, truly reason in general. High scores on graph and reasoning benchmarks had fed bold claims about such models. The team argues that those tests top out at modest difficulty, so they built a harder, scalable test set.

Their Deep Reasoning Dataset can produce endless examples at rising difficulty for graph connection and proof planning tasks. Model scores fell sharply once difficulty grew enough, showing weak generalisation. Most real world cases sit in the range models handle, but long hard tails remain.

Catalog record

CREATORRevanth Rameshkumar, Jimson Huang, Yunxin Sun, Fei Xia, Abulhair Saparov
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE59 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-22371

Browse the full library · About the Tower of Babel

Full text

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

Reasoning Models Reason Well, Until They Don’t Revanth Rameshkumar, Jimson Huang, Yunxin Sun, Fei Xia, Abulhair Saparov Abstract Large language models (LLMs) have shown significant progress in reasoning tasks. However, recent studies show that transformers and LLMs fail catastrophically once reasoning problems exceed modest complexity. We revisit these findings through the lens of large reasoning models (LRMs)—LLMs fine-tuned with incentives for step - by - step argumentation and self - verification. LRM performance on graph and reasoning benchmarks such as NLGraph seem extraordinary, with some even claiming they are capable of generalized reasoning and innovation in reasoning-intensive fields such as mathematics, physics, medicine, and law. However, by more carefully scaling the complexity of reasoning problems, we show existing benchmarks actually have limited complexity. We develop a new dataset, the Deep Reasoning Dataset ( DeepRD ), along with a generative process for producing unlimited examples of scalable complexity. We use this dataset to evaluate model performance on graph connectivity and natural language proof planning. We find that the performance of LRMs drop abruptly at sufficient complexity and do not generalize. We also relate our LRM results to the distributions of the complexities of large, real-world knowledge graphs, interaction graphs, and proof datasets. We find the majority of real-world examples fall inside the LRMs’ success regime, yet the long tails expose substantial failure potential. Our analysis highlights the near-term utility of LRMs while underscoring the need for new methods that generalize beyond the complexity of examples in the training distribution. 1 Introduction Large language models (LLMs) have recently demonstrated impressive performance on reasoning-intensive tasks. This is, in a large part, due to methods such as reinforcement learning with verifiable rewards (RLVR) Lambert et al. 2024 , thereby producing large reasoning models (LRMs). LRMs seemingly excel at coding, mathematics, and small graph puzzles OpenAI 2025 ; DeepSeek-AI et al. 2025 . Some proponents claim that the reasoning abilities of LRMs have advanced to the point of being capable of performing original scientific research Jansen et al. 2025 , Zheng et al. 2025 ; Xu and Peng 2025 . However, despite improved performance on moderately more complex problems, it is less clear whether LRMs can generalize to highly-complex reasoning problems. Scaling experiments on transformers suggest that they have difficulty learning tasks such as multi-hop search, graph coloring, or finding Hamiltonian paths ( Saparov et al. 2025 ; Wang et al. 2023a ; Heyman and Zylberberg 2025 ) —suggesting fundamental limitations for LLMs and LRMs. If LRMs cannot generalize to more complex reasoning tasks, then it is unlikely that they will succeed in more reasoning-intensive applications such as automated research. Thus, establishing a performance baseline on complex reasoning is important, but not without challenges: existing corpora and benchmarks (i) might be present in the models’ training data and (ii) complexity of existing benchmarks is limited. Real-world reasoning tasks, including those in natural language, do not have a fundamental upper bound in their complexity. There are many real-world domains where completing queries or tasks require deeper reasoning, such as in multi-hop question-answering Saxena et al. 2020 where many reasoning steps are required to answer questions correctly. For example “How many asteroids were found between one of Jupiter’s large Trojan asteroids and 4239 Goodman?” would require 177 reasoning steps (or “hops”) in Wikidata5M Wang et al. 2021 . Relatedly, biomedical queries such as “How are the genes of tuberculosis bacteria used in lung cancer research?” Xu et al. 2025 , or about drug interaction that can involve reasoning over complex drug interaction graphs Wishart et al. 2018 . In instruction following, narrative understanding, and dialogue planning, a reasoning system might need to consider very long chains of events to properly characterize or summarize events. For example, in Rameshkumar and Bailey 2020 , there are dialogue chains that are over 2000 turns long for a turn-based roleplaying game—a model might need make long traversals to piece together narrative information. To answer questions like “What motivated a character to pick up the sword?”, a traversal of the character’s actions may be required. Natural language proof generation, producing strictly connected logical inference chains, and program synthesis are also problems with potentially unbounded complexity Welleck et al. 2022 ; Chen et al. 2024 . Figure 1: An example from DeepRD . The example has complexity metrics: lookahead L=2 and number of branches B=2 (see Section 3.2 for definitions of complexity metrics). The same underlying graph is transformed into a symbolic graph query for an LLM to find a valid path, and into a natural language query for an LLM to plan the next step in a proof. Recently, Shojaee et al. 2025 evaluated LRMs on arbitrarily complex reasoning problems by using four puzzle scenarios. However, an exponential number of steps is required to solve some of the puzzles, and so the inability to solve the puzzles may be due to model token limits rather than reasoning limitations Lawsen 2025 . Although the puzzles were complex in terms of the number of steps required to solve them, they were simple to describe, and LRMs are able to generate code to programmatically solve the puzzles. Therefore, more analysis is needed on more realistic reasoning problems. Particularly for scenarios like natural language deduction and proof planning which is not as easily solved programmatically. To test the limits of LRM reasoning, we query models to solve synthetically-generated graph reasoning and proof planning tasks with unbounded, but controllable, complexity. This new dataset, called Deep Reasoning Dataset or DeepRD , contains problems with widely varying complexity (in terms of the number of required reasoning steps; hence “deep”), but are simultaneously simple to generate synthetically. Thus, the examples serve as a “lower bound” on the complexity of realistic reasoning problems, and a reasoning system would need to perform well on DeepRD if they are able to solve similarly complex and novel real-world reasoning tasks. Research Questions and Contributions In this paper, we study the following research questions: • RQ1 How does LLM/LRM performance on graph reasoning scale with complexity? • RQ2 How does performance scale on natural language proof planning? • RQ3 How complex are reasoning problems found “in the wild” or in the training data of LLMs and LRMs? We make the following contributions 1 1 1 All code, data, and model responses are open source at https://github.com/RevanthRameshkumar/DeepRD . : • C1 We comprehensively characterize the performance of LLMs and LRMs on symbolic graph connectivity problems with well-defined complexity metrics. • C2 We evaluate model performance when the same graph structures in RQ1 and C1 are encoded as natural language axioms, in order to mirror a proof planning task. • C3 We introduce the Deep Reasoning Dataset ( DeepRD ), which contains 2220 examples of symbolic graph connectivity and proof planning examples; along with the parameterized generator for producing unlimited synthetic examples of any requested complexity. • C4 We carry out a detailed analysis of the complexity distribution of a variety of real-world reasoning scenarios (graphs and proofs), with results suggesting that LRMs are not able to generalize beyond the complexity of examples that typically occur in their training. • C5 We evaluate LRMs on real-world natural language proofs from the NaturalProofs dataset, showing that their ability

Read the complete text