💬 NLP

ReasonBENCH: Benchmarking the (In)Stability of LLM Reasoning

The paper introduces ReasonBench, a benchmark suite demonstrating that LLM reasoning performance exhibits significant, structured instability across repeated executions, thereby arguing that single-point evaluations are insufficient and advocating for distribution-aware assessment to accurately capture the trade-offs between quality, cost, and reliability.

Original authors: Nearchos Potamitis, Vansh Ramani, Har Ashish Arora, Dhairya Kuchhal, Lars Klein, Akhil Arora

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nearchos Potamitis, Vansh Ramani, Har Ashish Arora, Dhairya Kuchhal, Lars Klein, Akhil Arora

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

The Big Idea: The "Coin Flip" Problem

Imagine you hire a chef to make a specific dish. You ask them to cook it 30 times.

The Old Way: You ask them to cook it once, taste it, and say, "This chef is a 9/10."
The Reality: When you ask them to cook it 30 more times, sometimes the dish is a 10/10, sometimes it's a 4/10, and sometimes it burns the kitchen down. Yet, the average might still look like a 9/10.

This paper argues that for Large Language Models (LLMs)—the AI brains behind chatbots—we have been lying to ourselves by only looking at the average.

The researchers found that even when you tell the AI to be "greedy" (meaning it should always pick the most obvious, safe answer, like a robot with no randomness), the results still jump around wildly. One time it solves a math problem perfectly; the next time, it fails the same problem.

The New Tool: ReasonBENCH

To prove this, the authors built a testing lab called ReasonBENCH. Instead of asking an AI to solve a problem once, they made it solve the same problem 30 times in a row. They did this for:

12 different AI models (from companies like OpenAI, Google, Anthropic, etc.).
10 different thinking strategies (like "Chain of Thought," "Tree of Thoughts," or just "Ask and Answer").
6 different types of tasks (math puzzles, coding, writing poems, answering tricky questions).

Key Findings (The "Aha!" Moments)

1. The "Stability Taxonomy" (The Four Types of Chefs)

The researchers realized that "instability" isn't just random noise. It has a pattern. They created a map with two axes:

Global Noise: How much does the AI's performance change depending on what task you give it? (Is it a specialist who only works on math but fails at poetry?)
Run Noise: How much does the AI's performance change when you give it the same task twice? (Is it a chef who flips a coin to decide if the soup tastes good today?)

They found four types of systems:

Stable Generalists: Good at everything, every time. (The reliable chef).
Noisy Generalists: Good at everything, but sometimes they have a bad day.
Stable Specialists: Great at one thing, terrible at others, but consistent.
Doubly Noisy: Unpredictable and inconsistent.

The Surprise: The type of "thinking strategy" the AI uses predicts which category it falls into. Some strategies are naturally more chaotic than others, regardless of how smart the AI model is.

2. The "Cost vs. Quality" Trap

We often think: "If I pay more for a smarter AI or use a more complex thinking method, I'll get better results."
The paper says: Not necessarily.

The Expensive Failure: Some very expensive, high-end models and complex strategies often fail more often when you run them multiple times. They might get the right answer on average, but they also burn a lot of money (compute costs) to get there, and sometimes they just crash.
The Cheap Immunity: Surprisingly, the cheap, simple methods (like just asking the AI directly) are "immune" to a specific type of failure. They never cost a fortune, so even if they get the answer wrong, they haven't wasted your money.
The Analogy: Imagine buying a lottery ticket.
- Cheap Method: You buy a $1 ticket. You lose, but you only lost $1.
- Expensive Method: You buy a $1,000 "premium" ticket. You might win big, but you might also lose the $1,000. The paper found that the expensive tickets often lose more often than we think, even if they win big occasionally.

3. Why is this happening? (It's not just "Randomness")

You might think, "Oh, the AI is just rolling dice to pick words."
The researchers tested this by turning off the "dice rolling" (setting the temperature to 0, which forces the AI to be deterministic). The instability didn't go away.

This means the problem isn't just the AI picking random words. The instability comes from deeper issues:

The API: The servers running the AI might be shifting data around in the background.
The Strategy: Some ways of thinking (like searching through many possibilities) are inherently messy.
The Evaluator: If the AI has to grade its own work, and the grader is a bit shaky, the whole process becomes shaky.

What Should We Do? (The Takeaway)

The paper suggests we need to change how we judge AI:

Stop looking at single numbers: Don't just say "Model A is 85% accurate." Say "Model A is 85% accurate, but it swings between 60% and 95% every time you run it."
Check the "Joint Failure": When deploying an AI, you need to know: "What are the odds this AI will be both expensive AND wrong?" The paper shows that expensive methods are much more likely to be both expensive and wrong than cheap methods.
Fix the Evaluator, not just the AI: If you are using a complex strategy (like a search tree), the biggest thing you can do to make it stable is to make sure the "judge" (the part that checks the answer) is perfect. Fixing the prompt or the AI model itself helps less than fixing the judge.

Summary

ReasonBENCH is a wake-up call. It tells us that AI reasoning is like a weather system, not a light switch. It's not just "on" or "off." It fluctuates. If we only look at the average weather report, we might get caught in a storm. We need to look at the distribution of outcomes to know if an AI is truly reliable or just lucky.

Technical Summary: ReasonBench: Benchmarking the (In)Stability of LLM Reasoning

Problem Statement

Current benchmarks for Large Language Model (LLM) reasoning systems report performance as single-point estimates (e.g., a single accuracy score). However, the paper argues that LLM generation is an inherently stochastic process. Even under greedy decoding ( $T=0$ ), identical model–strategy–task configurations can produce meaningfully different answers, reasoning paths, and costs across repeated executions.

Collapsing these run-level outcomes into a single mean discards the variance that distinguishes a reliably correct system from one that is correct only in expectation. This variance is not merely a statistical nuisance; the paper demonstrates that the highest-performing strategy wins only 77% of head-to-head runs against its nearest competitor, and the top model wins only 88%. Consequently, a single observed score can silently misrank systems, leading to suboptimal model selection and deployment decisions. Furthermore, existing literature often treats bias (systematic error) and variance (stochasticity) as co-equal properties, yet LLM evaluation has largely reported only the former.

Methodology: REASONBENCH

To address this, the authors introduce REASONBENCH, a benchmark suite and open-source library designed for controlled multi-run evaluation. The framework decouples the reasoning method, task environment, model interface, and evaluation state, allowing strategies to be rerun across tasks and models without changing the experimental harness.

Experimental Setup:

Scope: The study evaluates 12 contemporary reasoning models (spanning providers like OpenAI, Anthropic, Google, DeepSeek, etc.) and 10 representative reasoning strategies (including IO, CoT, ReAct, Tree of Thoughts, Graph of Thoughts, etc.) across 6 diverse tasks (Game of 24, HumanEval, HotpotQA, Humanity's Last Exam, SciBench, and Shakespearean Sonnet Writing).
Protocol: Each configuration is executed 30 independent times. This sample size is justified by a two-stage power analysis to ensure the detection of meaningful variance and reliable confidence intervals.
Metrics: The study treats quality and cost as empirical distributions rather than point estimates. It introduces two primary noise metrics:
1. Global Noise: Captures cross-benchmark unevenness (structural variability) after z-score normalization.
2. Run Noise: Captures within-benchmark stochasticity (repeated-run instability).
Variance Decomposition: A hierarchical decomposition attributes score variance to benchmark, system, item structure, and usage, isolating the residual unexplained variance.

Key Contributions

1. Instability is Structured, Not Random

The paper establishes that variance is substantial, benchmark-dependent, and axis-dependent. Through a two-component taxonomy (Global Noise vs. Run Noise), the authors show that:

Strategy Architecture Predicts Stability: Deterministic execution suppresses Run Noise, while search-based execution amplifies it. The quadrant a strategy occupies in the noise space is predictable by its architecture.
Hierarchical Attribution: Approximately three-quarters of score variance is structured (attributable to benchmark, system, and item interactions), while a persistent residual remains unexplained by design factors.

2. Models and Strategies are Non-Substitutable Axes

The study treats models and strategies as orthogonal axes that shift different parts of the performance distribution:

Models move the ceiling: Model choice determines the maximum achievable performance (capability).
Strategies move the procedure: Strategy choice determines the execution variance and task-level sensitivity.
Cost-Quality Decoupling: Cost and quality decouple asymmetrically. Cheap methods are structurally immune to "joint cost-quality failure" (simultaneously high cost and low quality), whereas expensive methods remain exposed to this risk regardless of their average accuracy.

3. Controlled Source Elimination

The authors systematically test potential sources of instability:

Decoding Temperature: Variance persists even at $T=0$ , ruling out token-level sampling as the dominant explanation.
Prompts and Parsers: Refining prompts and parsers corrects bias (improves mean quality) but does not reduce run-to-run variance.
Evaluator Quality: Replacing heuristic evaluators with ground-truth oracles in search-based strategies reduces both mean quality and variance, identifying the evaluator as a direct stability lever.
Reasoning Effort: Increasing test-time compute (effort) increases cost monotonically but does not reliably improve quality or reduce variance.

4. Open Infrastructure

REASONBENCH provides a modular library with decoupled abstractions (Method, Agent, Model, State, Environment) to facilitate reproducible, distribution-aware evaluation.

Key Results

Overlapping Distributions: Run-level distributions for both strategies and models overlap substantially. For instance, on the HotpotQA benchmark, the top strategy (FOA) and its nearest competitor (TOT-BFS) have overlapping confidence intervals, and the top strategy only outperforms the runner-up in 77% of runs.
Noise Taxonomy: Plotting systems in (Global Noise, Run Noise) space reveals distinct quadrants. Models tend to concentrate on the anti-diagonal (structural unevenness and stochastic instability are anti-correlated), while strategies populate all four quadrants based on their architecture.
Variance Decomposition: In the strategy axis, 75.2% of variance is structured; in the model axis, 73.3% is structured. Pure repeat effects account for only ~1% of variance, while benchmark-system interactions and item difficulty dominate.
Cost-Quality Asymmetry: Expensive methods (e.g., DeepSeek R1, which is the most expensive model tested) often exhibit high joint failure rates. Conversely, cheap methods (e.g., IO, COT) never exceed the cost threshold, making them immune to joint failure even if their quality is lower.
Ineffectiveness of Common Fixes: The study finds that standard "fixes" like lowering temperature, refining prompts, or increasing reasoning effort do not reduce variance. Only improving evaluator fidelity and increasing model scale (within a family) show stabilizing effects.

Significance and Claims

The paper claims that instability is an inherent property of reasoning systems, not an artifact of poor experimental design. The authors argue that:

Stability is part of capability: A system that solves a task consistently has a different capability profile than one that solves it only in expectation, even if their averages match.
Evaluation must evolve: Single-number benchmarks are insufficient. Evaluation practices should shift toward reporting distributions, confidence intervals, and noise metrics (Global and Run Noise).
Orthogonality of axes: Models and strategies should be co-developed rather than treated as substitutes. A benchmark suite that discriminates models may not discriminate strategies, and vice versa.
Risk-aware deployment: Practitioners must budget for "joint cost-quality risk." A nominally better but expensive method may dominate on mean quality while being substantially worse on the risk of simultaneous high cost and low quality.

The paper concludes by calling for "distribution-aware leaderboards" as a community standard and suggests that future research should focus on stability-aware routing and co-developed reasoning systems that match problems to appropriate model-strategy pairs.