🤖 AI

Reasoning Structure of Large Language Models

This paper introduces a scalable benchmark and pipeline to convert unstructured reasoning traces into verifiable graphs, enabling the quantitative analysis of reasoning structure and efficiency to better diagnose failure modes and compare model behaviors beyond traditional accuracy and token count metrics.

Original authors: Frédéric Berdoz, Luca A. Lanzendörfer, Fabian Farestam, Roger Wattenhofer

Published 2026-06-03

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Frédéric Berdoz, Luca A. Lanzendörfer, Fabian Farestam, Roger Wattenhofer

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are watching two chefs try to bake the exact same cake. Both chefs hand you a perfect, delicious cake at the end. If you only look at the final product, you might think they both did the same job. But what if one chef followed a precise, step-by-step recipe, while the other wandered around the kitchen, tried ten different ingredients, burned a few batches, and finally stumbled upon the right mix by accident?

For a long time, when we tested AI "reasoning" models, we only looked at the final cake (the answer) or how many words they used to describe the process (token count). This paper argues that this is like judging a chef only by the taste of the cake, ignoring whether they actually knew how to cook or just got lucky.

Here is what the researchers did to peek behind the curtain, explained simply:

1. The Puzzle Playground

Instead of asking the AI to write an essay or solve a vague riddle, the researchers gave them a set of 21 different logic puzzles (like "Tents," where you have to place tents next to trees based on strict rules). These puzzles are like a controlled gym for the brain. They have clear rules, and you can't cheat; you either solve it or you don't. The researchers made these puzzles harder and harder, like increasing the weight on a barbell.

2. Turning Words into a Map

When an AI solves a puzzle, it usually writes out a long stream of thoughts (a "trace"). The researchers built a special tool that takes this messy stream of text and turns it into a visual map (a graph).

Nodes (Dots): Each dot is a single fact or claim the AI made (e.g., "There is a tree at this spot").
Edges (Lines): The lines connect the dots to show how one fact led to another (e.g., "Because there is a tree here, there must be a tent there").

This turns a paragraph of text into a structured diagram that you can measure.

3. The New Scorecard: "Reasoning Efficiency"

The researchers introduced a new metric called Efficiency ( $\eta$ ). Think of this as measuring how "focused" the AI's thinking is.

High Efficiency (The Laser): The AI's map looks like a straight, narrow tunnel. It gathers the necessary facts and moves directly to the solution without wandering.
Low Efficiency (The Fog): The AI's map looks like a messy spiderweb. It explores many dead ends, repeats the same facts over and over, and wanders around the edges of the problem before (maybe) finding the answer.

4. What They Discovered

By using this map and the efficiency score, they found some surprising things that the old "final answer" score missed:

More Words $\neq$ Better Thinking: Just because an AI uses more words (tokens) doesn't mean it's thinking better. In fact, the researchers found that extra words were often just the AI "double-checking" itself or wandering in circles, not actually solving the problem.
The "Diffuse" Problem: Some models would get the right answer but had a very messy, scattered map. They were like a detective who finds the criminal but had to interview 50 innocent people first. Other models were "focused," finding the answer with a clean, direct path.
The Wall of Difficulty: As the puzzles got harder, the AI models started to fail. Even when the researchers let them use massive amounts of words (computing power), the models still couldn't solve the hardest puzzles. It turns out that just giving an AI more time to "think" (more tokens) doesn't fix fundamental reasoning gaps.
Structure Matters: The "Efficiency" score could tell the difference between a model that was smart and focused versus one that was just guessing and checking, even if both got the same final score.

The Bottom Line

This paper gives us a new way to look at AI thinking. Instead of just asking, "Did it get the answer right?" we can now ask, "How did it get there?"

It's the difference between a student who memorizes the answer key and a student who actually understands the math. The researchers built a tool to see the "understanding" part by mapping out the logical steps, proving that how an AI reasons is just as important as what it answers.

Technical Summary: Reasoning Structure of Large Language Models

Problem Statement

Large Reasoning Models (LRMs) have demonstrated impressive performance on complex tasks by leveraging increased test-time compute through long Chain-of-Thought (CoT) traces. However, current evaluation paradigms rely heavily on one-dimensional metrics such as final-answer accuracy and token count. The authors argue that these metrics are insufficient because they conflate fundamentally different reasoning behaviors. Identical scores can hide "diffuse exploration" (inefficient, scattered reasoning) versus "focused deductions" (efficient, structured reasoning). Furthermore, simply allocating more compute (tokens) does not guarantee better performance, as models often exhibit "overthinking" or "trace-level collapse" where additional tokens translate into verification overhead rather than improved logical flow. There is a lack of scalable, structured methods to analyze the intermediate reasoning process beyond the final output.

Methodology

The paper introduces a framework to convert unstructured textual reasoning traces into structured, verifiable reasoning graphs, enabling quantitative analysis of reasoning topology.

1. Scalable Benchmark

The authors utilize a suite of 21 deterministic 2D grid puzzles (e.g., Tents, Sudoku, Lightup, Galaxies) derived from Simon Tatham's puzzle collection. These puzzles are chosen for their "easy to learn, hard to master" nature, fully specified rules, and unambiguous verification. The benchmark includes four difficulty levels (Trivial, Human easy, Human normal, Human hard) with adjustable grid sizes and clue densities, allowing for controlled scaling studies.

2. Graph Extraction Pipeline

The core innovation is a pipeline that transforms free-form text into a directed acyclic graph (DAG) $G = (V, E)$ :

Nodes (Claims): The pipeline extracts "atomic claims" (e.g., "Cell (3,1) is a tent") from the reasoning trace. Claims are categorized by status (stated, derived, tentative) and scope (mainline vs. hypothetical branches).
Edges (Dependencies): The pipeline identifies deductive dependencies, linking premises to conclusions. This is achieved through a hybrid approach combining deterministic pattern matching and LLM-based extraction, followed by rule extraction to map claims to specific puzzle logic rules.
Verification: Claims are verified against an executable puzzle environment. Static claims (e.g., puzzle rules, final placements) are verified deterministically. State-dependent claims are handled carefully to avoid cascading errors.

3. Reasoning Metrics

Building on the graph representation, the authors define several metrics:

Structural Topology: Measures such as graph depth, diameter, and the fraction of the graph supporting the solution ( $|V_{sol}|/|V|$ ).
Reasoning Flow Efficiency ( $\eta$ ): This is the primary contribution. The authors model the reasoning process as an absorbing Markov chain on the DAG. They calculate the "structural entropy" ( $H_{str}$ $H_{s t r}$ ) of the logical flow, which measures how dispersed the model's attention is across the graph.
$\eta = \frac{\log |V| - H_{str}(G)}{\log |V| - \log |C^*|}$
Where $|V|$ $∣ V ∣$ is the total number of claims, $H_{str}(G)$ $H_{s t r} (G)$ is the structural entropy, and $|C^*|$ $∣ C^{*} ∣$ is the size of the minimal claim set required for the solution.
- $\eta \approx 1$ indicates highly focused reasoning (low entropy, flow concentrated on the solution path).
- Lower $\eta$ indicates diffuse reasoning (high entropy, flow scattered across peripheral or redundant claims).

Key Results

The framework was applied to evaluate frontier and open-source models (GPT-5, Qwen3 235B, DeepSeek V3.2, Kimi K2) across the puzzle suite.

Accuracy vs. Structure: As puzzle difficulty increases, accuracy drops sharply for all models (e.g., GPT-5 drops from 83.8% to 5.7%), while token counts rise significantly (from ~4k to ~60k). However, increased token usage does not correlate with improved reasoning quality.
Token Count is a Poor Proxy: The study finds that token count is essentially uncorrelated with reasoning efficiency ( $\eta$ ) ( $r = -0.05$ ). Extra tokens primarily manifest as increased verification overhead ( $|V_{ver}|/|V_{sol}|$ ) rather than expanding the core solution-supporting chain.
Efficiency Distinguishes Behaviors: The metric $\eta$ $η$ successfully separates models and behaviors that accuracy and token count conflate.
- Focused vs. Diffuse: Models with higher $\eta$ exhibit concentrated logical flow. Models with lower $\eta$ engage in "graph bloat" via branching, detours, and redundant structure.
- Failure Modes: Failed traces are substantially less efficient (lower $\eta$ by >50%) and spread reasoning across larger, more diffuse graphs, with the first error appearing earlier.
- Correlations: Higher efficiency correlates positively with claim accuracy and the fraction of the graph supporting the solution. It also correlates with later first-error depth.
Scaling Limits: Even with massive token budgets, the hardest regime remains largely unsolved, suggesting fundamental limitations in current reasoning scaling that are not resolved by simply allocating more compute.

Significance and Claims

The paper claims to provide a practical tool for diagnosing failure modes and comparing reasoning structures that traditional metrics miss.

Beyond Accuracy: The work demonstrates that structural measurements (specifically $\eta$ ) reveal differences in how solutions are produced, even when models achieve the same accuracy or use similar token budgets.
Diagnostic Utility: By converting traces into verifiable graphs, the framework allows researchers to distinguish between "solving" and "meandering" or excessive verification. It helps identify early-error cascades and inefficient behaviors.
Generalizability: While the claim extraction is puzzle-specific, the structural layer (graph construction, Markov chain analysis, and the $\eta$ metric) is domain-agnostic. The authors suggest this framework extends to any setting with verifiable intermediate steps, such as mathematical reasoning (symbolic verification) and code generation (unit tests).
Future Impact: The authors posit that if extraction becomes sufficiently reliable, graph-based signals like $\eta$ could serve as auxiliary feedback in post-training (e.g., shaping rewards) to encourage solution-focused reasoning while preserving correctness.

The paper maintains a modest stance, acknowledging limitations such as the reliance on LLMs for extraction (introducing potential variance, though stability checks show low variance) and the need for domain-specific claim definitions. It frames the metric as a diagnostic tool rather than a single leaderboard score.