# Reasoning Large Language Model Errors Arise from Hallucinating Critical Problem Features

arXiv: https://arxiv.org/abs/2505.12151 · HTML: https://mlsanity.com/paper/2505.12151/

## Key facts

- Cited by 6 papers in the map (data through 14 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.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

## Builds on (most cited first, 11 of 11)

- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Siren's Song in the AI Ocean: A Survey on Hallucination in Large Language Models](https://mlsanity.com/paper/2309.01219/) (2023)
- [A Comprehensive Overview of Large Language Models](https://mlsanity.com/paper/2307.06435/) (2023)
- [GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models](https://mlsanity.com/paper/2410.05229/) (2024)
- [Reasoning Models Don't Always Say What They Think](https://mlsanity.com/paper/2505.05410/) (2025)
- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning](https://mlsanity.com/paper/2502.01100/) (2025)
- [On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Tasks](https://mlsanity.com/paper/2402.08115/) (2024)
- [LLMs Still Can't Plan; Can LRMs? A Preliminary Evaluation of OpenAI's o1 on PlanBench](https://mlsanity.com/paper/2409.13373/) (2024)
- [100 Days After DeepSeek-R1: A Survey on Replication Studies and More Directions for Reasoning Language Models](https://mlsanity.com/paper/2505.00551/) (2025)
- [Evaluating the Systematic Reasoning Abilities of Large Language Models through Graph Coloring](https://mlsanity.com/paper/2502.07087/) (2025)

## Built on by (most cited first, 6 of 6)

- [KnowRL: Exploring Knowledgeable Reinforcement Learning for Factuality](https://mlsanity.com/paper/2506.19807/) (2025)
- [PRISM: Probing Reasoning, Instruction, and Source Memory in LLM Hallucinations](https://mlsanity.com/paper/2604.16909/) (2026)
- [Evaluating Large Language Models on Solved and Unsolved Problems in Graph Theory: Implications for Computing Education](https://mlsanity.com/paper/2602.05059/) (2026)
- [Are Large Language Models Suitable for Graph Computation? Progress and Prospects](https://mlsanity.com/paper/2606.06865/) (2026)
- [ThinkRetrieve: Retrieval-Augmented Reasoning Traces for Test-Time Scaling](https://mlsanity.com/paper/2608.10928/) (2026)
- [Hallucination Across the Reasoning Lifecycle: Interface Visibility, Causal Evidence, and Release Control in Large Reasoning Models](https://mlsanity.com/paper/2610.05472/) (2026)

## 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.