Reasoning Large Language Model Errors Arise from Hallucinating Critical Problem Features
On the map: LLM reasoning → Reasoning benchmarks and evaluation
Abstract (arXiv)
Large language models have recently made great strides in reasoning task performance through chain-of-thought (CoT) strategies trained via reinforcement learning; however, these "reasoning large language models" (RLLMs) remain imperfect reasoners, and understanding the frequencies and causes of their failure modes is important for both users and developers. We test o1-mini, o3-mini, DeepSeek-R1, Claude 3.7 Sonnet, Gemini 2.5 Pro Preview, and Grok 3 Mini Beta on graph coloring as a variable-complexity constraint-satisfaction logic problem, and find evidence from both error rate comparisons and CoT/explanation text analysis that RLLMs are prone to hallucinate graph edges not specified in the prompt. This phenomenon persists across multiple problem complexity levels and semantic frames, and it appears to account for a significant fraction of the incorrect answers from every tested model, and the vast majority of them for some models. We also validate the generalizability of this input-conflicting hallucination phenomenon with smaller-scale experiments on a type of stable matching problem. Our results indicate that RLLMs may possess broader issues with misrepresentation of problem specifics, and we offer suggestions for design choices to mitigate this weakness.
Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning. Builds on 11 of its 17 references that are in the map. First posted on arXiv 17 May 2025.
Builds on
11 of 17 references.
Closest ancestors · 2
Same direction, newest first
- 2025100 Days After DeepSeek-R1: A Survey on Replication Studies and More Directions for Reasoning Language Models1 May
- 2025ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning3 Feb
Other references · 9
- 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,146
- 2023Siren's Song in the AI Ocean: A Survey on Hallucination in Large Language Modelscited by 695
- 2023A Comprehensive Overview of Large Language Modelscited by 639
- 2024GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Modelscited by 533
- 2025Reasoning Models Don't Always Say What They Thinkcited by 388
- 2025Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Modelscited by 381
- 2024On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Taskscited by 137
- 2024LLMs Still Can't Plan; Can LRMs? A Preliminary Evaluation of OpenAI's o1 on PlanBenchcited by 93
- 2025Evaluating the Systematic Reasoning Abilities of Large Language Models through Graph Coloringcited by 10
Built on by
Citing papers per year: 2025: 1; 2026: 4.
5 papers.
- 2025KnowRL: Exploring Knowledgeable Reinforcement Learning for Factualitycited by 17
- 2026PRISM: Probing Reasoning, Instruction, and Source Memory in LLM Hallucinationscited by 3
- 2026Evaluating Large Language Models on Solved and Unsolved Problems in Graph Theory: Implications for Computing Educationcited by 1
- 2026Are Large Language Models Suitable for Graph Computation? Progress and Prospectscited by 0
- 2026ThinkRetrieve: Retrieval-Augmented Reasoning Traces for Test-Time Scalingcited by 0
- 2026ThinkRetrieve: Retrieval-Augmented Reasoning Traces for Test-Time Scaling11 Aug 2026
- 2026Are Large Language Models Suitable for Graph Computation? Progress and Prospects5 Jun 2026
- 2026PRISM: Probing Reasoning, Instruction, and Source Memory in LLM Hallucinations18 Apr 2026
- 2026Evaluating Large Language Models on Solved and Unsolved Problems in Graph Theory: Implications for Computing Education4 Feb 2026
- 2025KnowRL: Exploring Knowledgeable Reinforcement Learning for Factuality24 Jun 2025
Similar, not cited
Close in wording, no citation either way
- 2025Large Reasoning Models are not thinking straight: on the unreliability of thinking trajectories
- 2025Reasoning Models Reason Well, Until They Don't
- 2025Mitigating Hallucinations in Large Language Models via Causal Reasoning
- 2025Advancing Reasoning in Large Language Models: Promising Methods and Approaches
- 2025Large Language and Reasoning Models are Shallow Disjunctive Reasoners
- 2026Dissecting Failure Dynamics in Large Language Model Reasoning
- 2026When Do Hallucinations Arise? A Graph Perspective on the Evolution of Path Reuse and Path Compression
- 2026Reasoning Error from Known Fact: Step-Level Self-Consistency Group Relative Policy Optimization for LLM