Research map / Large language models / Reasoning and chain of thought

Exposing Weaknesses of Large Reasoning Models through Graph Algorithm Problems

ICLR 2026 · Large language models › Reasoning and chain of thought · approach: Efficient and adaptive thinking · 0 citations (OpenAlex)

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 GrAlgoBench, a graph-algorithm benchmark (9 tasks, 2,700 real-world-sourced graphs of 8–160 nodes) for large reasoning models, showing accuracy collapse on large graphs and over-thinking driven by ineffective self-verification.

Problem

Existing reasoning benchmarks lack long-context evaluation, offer insufficient difficulty, and have answers that are hard to verify programmatically; graph algorithm problems are proposed to address this for large reasoning models.

Approach

Organize graph algorithm tasks into a reasoning taxonomy (Enumeration, Exploration, Intuition) grounded in CLRS algorithm design paradigms, use real-world graphs with controllable size levels, and analyze long-context failure modes and over-thinking via entropy-based response segmentation.

Key results

• Qwen3-32B achieves 87.0% pass@k on 31–50 node graphs but drops to 59.0% on 81–120 nodes and 47.0% on 121–160 nodes.
• On Triangle Sum with fixed topology, DeepSeek-R1 falls from 100.0% at 4k tokens to 22.0% at 64k tokens.
• Model-wise correlation of GrAlgoBench with GPQA is ρ=0.77 and with LongBench-v2 is ρ=0.60.

Surprising findings

• Self-verification is frequent but fewer than 30% of attempts detect prior errors in most cases, so it mainly inflates traces.
• Outcome efficiency on graph tasks stays above 0.88, so post-answer generation is not the main source of over-thinking.

Limitations

• Only 9 tasks and graph sizes capped at 160 nodes.
• Tool-augmented code execution substantially improves results, so the benchmark measures intrinsic reasoning only without tools.
• Task classification relies on an LLM judge (Qwen2.5-72B) validated on a subset by human annotators.

Experimental setup

Datasets: DBLP Street Network OpenFlight Wikipedia DBpedia Erdős-Rényi graphs

Benchmarks: GrAlgoBench LongBench-v2 GPQA MMLU-Pro

Metrics: pass@k cons@k z-score outcome efficiency accuracy

Baselines: GPT-OSS-120B Qwen3-235B-A22B-Thinking DeepSeek-R1 Gemini-2.5-pro GPT5-mini QwQ-32B

Builds on: CLRS GraphArena GraphWalks NLGraph

Closest papers by meaning

• Topology of Reasoning: Understanding Large Reasoning Models through Reasoning Graph Properties (NeurIPS 2025 · similarity 0.93)
• The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity (NeurIPS 2025 · similarity 0.91)
• Reasoning Structure of Large Language Models (ICML 2026 · similarity 0.90)
• DAG-Math: Graph-Guided Mathematical Reasoning in LLMs (ICLR 2026 · similarity 0.89)
• Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning (ICLR 2024 · similarity 0.89)
• On Reasoning Strength Planning in Large Reasoning Models (NeurIPS 2025 · similarity 0.89)