🤖 machine learning

Accuracy, Stability, and Repeated-Run Reliability of Large Language Models on Deterministic Programming Tasks

This paper demonstrates that standard run-level accuracy metrics significantly overstate the reliability of large language models on deterministic programming tasks by ignoring the substantial gap between single-run success and consistent retry-free performance, particularly for mid-tier models, thereby establishing the necessity of repeated-run stability analysis for accurate evaluation.

Original authors: Yongxi Zhou, Lai Yun Choi, Jiaxi Wen, Wenbo Ye

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yongxi Zhou, Lai Yun Choi, Jiaxi Wen, Wenbo Ye

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 hire a team of chefs to cook a specific dish based on a recipe you give them. You ask each chef to try cooking the dish five times in a row, using the exact same ingredients and instructions.

Most people would look at the results and say, "Wow, Chef A got it right 4 out of 5 times! That's an 80% success rate. They are great."

But this paper asks a different, more practical question: "If I ask Chef A to cook this dish right now, can I trust that it will be perfect every single time, or do I have to keep asking them to try again until they get it right?"

The researchers found that the standard way of measuring success (the "80% success rate") often lies to us. It makes the chefs look more reliable than they actually are.

Here is a breakdown of their findings using simple analogies:

1. The "Average" vs. The "Perfect Streak"

The paper introduces two ways to measure a chef (or an AI model):

Run-Level Pass Rate (The Average): This is like counting how many perfect plates came out of the kitchen total. If a chef makes 100 plates and 80 are perfect, they have an 80% score. This is what most people look at.
Perfect Stability Rate (The "No Retry" Score): This asks: "How many of the orders did the chef get right on the very first try, without ever messing up?"

The Big Discovery: The "Average" score is almost always higher than the "No Retry" score.

The Analogy: Imagine a chef who flips a coin to decide whether to add salt.
- Scenario A: They get the dish right 50% of the time, but when they get it wrong, they get it really wrong. They are inconsistent.
- Scenario B: They get the dish right 50% of the time, but they are either always perfect or always terrible.
- The paper found that for "mid-level" chefs (those who are good but not perfect), the gap between their "Average" score and their "No Retry" score is huge. One model might look like it's 86% accurate on average, but if you need it to work perfectly without a second guess, it's actually only 75% reliable. That's a 17.8% difference—a massive gap that changes who you would hire.

2. The "Mid-Range" Trap

The researchers found that the biggest lies happen with the "middle-of-the-road" models.

Top-tier models are so good they rarely make mistakes, so their "Average" and "Stability" scores are close.
Bottom-tier models are so bad they almost always fail, so their scores are also close (both low).
The Middle Models: These are the tricky ones. They succeed often enough to look good, but they fail often enough to be annoying. Because they are "on the fence," their results bounce around wildly. The paper found that for these models, the "Average" score overstates their reliability by nearly 18 percentage points.

3. The "Prompt" (The Recipe Card)

The team tested if giving the chef a more detailed recipe card (a "Detailed Prompt") versus a short one (a "Minimal Prompt") made them more consistent.

The Result: It depends entirely on the chef.
For some models, a detailed recipe helped. For others, a short recipe was better. For some, it didn't matter at all.
The Lesson: There is no "magic prompt" that fixes everyone. You can't just give a better instruction to a mid-tier model and expect it to suddenly become perfectly stable.

4. The "Thinking" Models (Reasoning vs. Standard)

Some modern chefs are trained to "think step-by-step" before cooking (Reasoning Models). The researchers wondered if this "thinking" made them more consistent.

The Result: Not necessarily.
While some "thinking" models were surprisingly stable, others were actually less stable than their non-thinking counterparts. The act of "thinking" didn't guarantee a perfect streak. In fact, for some, the extra thinking steps introduced more chances for things to go wrong.

5. Why This Matters

The paper argues that we need to stop just looking at the "Average" score.

The Real World: If you are building a software system that needs to run automatically (like a self-driving car or a banking script), you don't want a system that works "most of the time." You want a system that works every single time without you having to hit the "retry" button.
The Conclusion: To know if an AI is truly ready for the real world, you have to test it repeatedly. You need to know not just if it can solve the problem, but how reliably it solves it on the first try.

In short: A high score on a test doesn't mean the student is consistent. This paper shows us how to measure the difference between "getting it right eventually" and "getting it right every time."

Technical Summary: Accuracy, Stability, and Repeated-Run Reliability of Large Language Models on Deterministic Programming Tasks

Problem Statement

Large language models (LLMs) are increasingly deployed for text-conditioned tasks with deterministic specifications, such as program synthesis, where correctness is binary and verified by executable test suites. Conventional evaluation benchmarks (e.g., HumanEval, MBPP) typically report single-run accuracy or "eventual success" metrics like pass@k, which measure a model's capability to produce at least one correct solution within $k$ attempts.

However, many practical deployment scenarios require stability: the ability of a model to produce consistent, correct outcomes across repeated invocations under identical task descriptions. While recent work has framed repeated sampling as a form of inference-time compute, the systematic relationship between correctness and stability—specifically, the gap between a model's average run-level success and its reliability without retries—remains under-explored. This paper addresses the question of how much observed accuracy translates into reliable, retry-free behavior, particularly for mid-performing systems where variability is highest.

Methodology

Experimental Setup

The study utilizes a curated dataset of 100 deterministic programming problems (LeetCode-style), selected based on recency to minimize contamination from historical training data. The dataset includes 20 Easy, 50 Medium, and 30 Hard problems, covering various algorithmic topics. All problems are self-contained, require no external network access, and are graded via a fixed, deterministic test harness.

Models and Configuration

The evaluation covers 16 models from five provider families (OpenAI, Anthropic, Google, Qwen, DeepSeek), including both standard and reasoning-specialized architectures (e.g., o4-mini, DeepSeek-R1).

Protocol: Each model is evaluated under two prompt templates (DETAILED and MINIMAL) with 5 repeated runs ( $R=5$ ) per problem.
Parameters: Most models use $T=0.3$ and $top\_p=0.9$ to simulate realistic stochastic decoding. Reasoning-specialized models and specific API constraints (e.g., o4-mini) involve adjusted token budgets or fixed internal decoding regimes.
Total Instances: The experiment yields 16,000 evaluation instances.

Metrics

The paper introduces a repeated-run evaluation protocol with three primary metrics:

Run-Level Pass Rate (RLPR): The probability that a random single invocation succeeds.
$RLPR = \frac{1}{NR} \sum_{i=1}^{N} \sum_{r=1}^{R} Y_{i,r}$
Perfect Stability Rate (PSR): The fraction of tasks for which the system succeeds on all $R$ runs without requiring a retry.
$PSR = \frac{1}{N} \sum_{i=1}^{N} \mathbb{I}\left(\sum_{r=1}^{R} Y_{i,r} = R\right)$
Note: PSR is mathematically equivalent to pass@k at $k=R$ with an "all-successes" threshold, but is interpreted here as a deployment reliability measure rather than a capability measure.
Average Variance (AV): A measure of per-problem instability, capturing the variance in success probabilities across tasks.

Key Results

The Accuracy–Stability Gap

The study finds a strong correlation between RLPR and PSR ( $r = 0.985$ ), yet RLPR consistently overstates production reliability.

Magnitude of the Gap: The difference $\Delta = RLPR - PSR$ is non-uniform across models, reaching a maximum of 17.8 percentage points (observed in Gemini 2.5 Flash under the DETAILED prompt).
Mid-Accuracy Peak: The gap is largest for mid-performing systems. Models with intermediate success probabilities exhibit the highest variance (Bernoulli variance is maximized at $p \approx 0.5$ ), leading to significant discrepancies between average success and perfect stability.
Ranking Reversals: RLPR and PSR can yield divergent model rankings. For instance, GPT-4.1 outperforms GPT-4.1-mini in RLPR (59.6% vs. 58.4%) but trails in PSR (47.5% vs. 50.0%), driven by a larger accuracy–stability gap in the former.

Problem-Level Variability

Polarization vs. Instability: Models like Qwen-Turbo exhibit low AV because their outcomes are polarized (either consistently passing or failing all runs), resulting in a small gap despite low overall accuracy. Conversely, models like Gemini 2.5 Flash show high AV, indicating substantial trial-to-trial variability.
Failure Modes: The dominant failure mode is "Wrong Answer" (~~58%), followed by Time Limit Exceeded (~~27%). Instability is linked not only to algorithmic inconsistency but also to implementation fragility (timeouts/runtime errors), which increases with problem difficulty.

Prompt Sensitivity and Architecture

Prompt Effects: Prompt sensitivity is model-dependent rather than uniform. While most models show minor differences (<3 pp) between DETAILED and MINIMAL prompts, some (e.g., Claude Sonnet 4.5) show reversals. No single template uniformly dominates, and statistical significance for prompt effects was generally low given the sample size.
Reasoning Architectures: The study investigates whether reasoning-specialized models (e.g., Chain-of-Thought) exhibit systematically smaller accuracy–stability gaps. The results are heterogeneous: DeepSeek-R1 shows better-than-expected stability, while others (QwQ-Plus, Gemini 2.5 Flash+Think) show larger gaps. A permutation test ( $p=0.97$ ) found no systematic advantage for reasoning architectures in this sample, though the analysis is noted as underpowered due to the small number of reasoning models.

Significance and Claims

The paper argues that repeated-run stability analysis is a necessary complement to conventional accuracy reporting for deterministic text-conditioned generation.

Beyond Capability Measurement: While pass@k measures a model's capability to find a solution eventually, PSR measures deployment reliability (consistency). These two metrics target different downstream concerns and can diverge significantly, particularly for mid-accuracy systems.
Revealing Hidden Risks: Relying solely on RLPR can mask substantial instability. A model with a 60% run-level pass rate but only 47% perfect stability leaves a significant fraction of tasks in a "retry-required" regime, which may be unacceptable in automated workflows expecting reproducible behavior.
Methodological Contribution: The paper establishes PSR and Average Variance (AV) as first-class evaluation targets. It demonstrates that the accuracy–stability gap is an observable, model-specific, and practically significant phenomenon that cannot be inferred solely from mean performance.

The authors conclude that while their findings are specific to single-turn Python code generation, the framework provides a critical lens for understanding reliability in reproducibility-sensitive workflows. They caution that their results are snapshot-specific to the evaluated API versions and do not account for broader orchestration or multi-turn dependencies.