PaperlayerView exact revision on arXiv

Source-linked AI summary

The Illusion of Diminishing Returns: Measuring Long Horizon Execution in LLMs

Akshit Sinha, Arvindh Arun, Shashwat Goel, Steffen Staab, Jonas Geiping

arXiv:2509.09677v3cs.AI

TL;DR

The paper asks whether diminishing gains on short-task benchmarks obscure continued scaling benefits for long-horizon LLM tasks, and isolates execution by supplying the needed knowledge and plan. It finds that model scaling increases executable turns and sequential test-time compute extends single-turn task length, while synthetic-task results do not fully capture real-world agentic complexity.

  • Problem

    The paper asks whether diminishing marginal gains on short-task benchmarks obscure continued scaling benefits for long-horizon LLM tasks.

  • Method

    The authors isolate execution by explicitly providing the knowledge and plan while controlling turns and steps per turn in a controlled task.

  • Results

    Scaling model size increases executable turns, while sequential test-time compute increases the length of tasks a model can perform in a single turn.

  • Takeaways & Limitations

    Long-horizon execution improves dramatically through model scaling and sequential test-time compute, helping distinguish execution failures from inability to reason.

  • Takeaways & Limitations

    Improvement on the synthetic task is necessary but not sufficient for long-horizon execution on real-world tasks with varied actions and possible correct plans.

Abstract

from arXiv · show

Does continued scaling of large language models (LLMs) yield diminishing returns? In this work, we show that short-task benchmarks may give an illusion of slowing progress, as even marginal gains in single-step accuracy can compound into exponential improvements in the length of tasks a model can successfully complete. Then, we argue that failures of LLMs when simple tasks are made longer arise from mistakes in execution, rather than an inability to reason. So, we propose isolating execution capability, by explicitly providing the knowledge and plan needed to solve a long-horizon task. First, we find that larger models can correctly execute significantly more turns even when small models have near-perfect single-turn accuracy. We then observe that the per-step accuracy of models degrades as the number of steps increases. This is not just due to long-context limitations -- curiously, we observe a self-conditioning effect -- models become more likely to make mistakes when the context contains their errors from prior turns. Self-conditioning does not reduce by just scaling the model size. But, we find that thinking mitigates self-conditioning, and also enables execution of much longer tasks in a single turn. We conclude by benchmarking frontier thinking models on the length of tasks they can execute in a single turn. Overall, by focusing on the ability to execute, we hope to reconcile debates on how LLMs can solve complex reasoning problems yet fail at simple tasks when made longer, and highlight the massive benefits of scaling model size and sequential test-time compute for long-horizon tasks.

1 INTRODUCTION

The paper measures long-horizon execution separately from planning and knowledge, arguing that scaling and thinking can substantially extend the tasks LLMs complete despite apparent diminishing returns on short-task benchmarks.

  • Motivation: The paper asks how many steps an LLM can reliably execute and whether long-task failures reflect execution rather than inability to reason.It distinguishes planning—deciding what information or tools to use—from execution, which carries out the plan.
  • Approach: The authors isolate execution by explicitly providing the knowledge and plan while controlling turns and steps per turn.These controls determine task length in a controlled long-horizon setting.
  • Scaling: Diminishing improvements in single-step accuracy can compound into exponential growth in the length of tasks a model completes.This challenges the inference that slowing short-task progress implies limited gains on long-horizon capabilities.
  • Self-conditioning: Models’ per-step error rate rises as tasks progress because prior errors increase the likelihood of later errors, an effect not mitigated by scaling model size.The paper calls this self-conditioning and distinguishes it from previously identified long-context limitations.
  • Thinking: Thinking models avoid prior-mistake effects and sequential test-time compute enables much longer single-turn execution.DeepSeek-R1 executes over 100 steps where DeepSeek-V3 fails at four, while GPT-5 thinking exceeds 2100 steps versus Claude-4 Sonnet’s 432.
  • Conclusion: Long-horizon execution improves dramatically with model scaling and sequential test-time compute, suggesting short-task benchmarks can understate potential value.The paper frames this conclusion in terms of task length as an indicator of economic value.

2 FORMULATION

The paper formulates long-horizon execution as sequential state updates, analyzes how step accuracy compounds into horizon length, and introduces a controlled retrieve-then-compose task that separates execution from planning and knowledge.

  • 2 FORMULATION: Planning chooses steps and their order, whereas execution carries out those steps using relevant knowledge about how to perform and compose them.The paper applies these definitions to both reasoning and agentic tasks and focuses on execution as a critical long-horizon capability.
  • 2 FORMULATION: Even with perfected planning and world knowledge, long-horizon execution can still produce mistakes, motivating its separate measurement.The paper argues that execution failures have often been misattributed to reasoning or planning limitations.
  • 2 FORMULATION: A long-horizon task consists of many sequential steps from an initial state to a final goal, with task length defined by the number of required steps.The formulation evaluates step accuracy, turn accuracy, task accuracy, turn complexity, and horizon length.
  • 2 FORMULATION: Horizon length H_s is the first step where mean task accuracy falls below success threshold s, interpreted as completing that length with probability s.The paper uses s = 0.5 unless otherwise specified.
  • 2.1 DIMINISHING RETURNS IN STEP ACCURACY COMPOUND OVER A LONG HORIZON: Under independent constant step accuracy p and no self-correction, task success at length H follows a logarithmic relation between success rate s and p.The simplifying assumptions make the relationship analytically tractable.
  • 2.1 DIMINISHING RETURNS IN STEP ACCURACY COMPOUND OVER A LONG HORIZON: Horizon length grows hyperbolically with step accuracy, with sharp growth beyond 80% single-step accuracy.The figure illustrates this behavior across different success-rate values.
  • 2.1 DIMINISHING RETURNS IN STEP ACCURACY COMPOUND OVER A LONG HORIZON: Small step-accuracy improvements can yield rapidly increasing task lengths, so short-task benchmarks may understate long-horizon and economic gains.The paper notes that frontier-model horizon length at s = 0.5 has been observed to double every 7 months on software-engineering tasks.
  • 2.2 ISOLATING EXECUTION BY DECOUPLING PLANNING AND KNOWLEDGE: The empirical framework supplies knowledge and a plan for sequential retrieve-then-compose steps, measuring execution through updates to a running state.The setup uses a fixed key-value dictionary, explicit key plans, and controlled numbers of turns and keys per turn.

3 EXPERIMENTS

The experiments isolate long-horizon execution by providing models with the required knowledge and plan, then vary task length, model size, prior errors, and thinking. They find that execution degrades over turns, scaling improves executable horizons, self-conditioning worsens errors beyond context length, and thinking supports longer execution.

  • Setup: The task provides a fixed dictionary and explicit per-turn plans, requiring retrieval and composition while varying turns and steps per turn.The setup is designed to test execution separately from knowledge and planning.
  • Effect of increasing the number of turns: Even with near-perfect first-step accuracy, Qwen3-32B falls below 50% task accuracy within 15 turns.This demonstrates that long-horizon execution can fail despite the knowledge and plan needed for individual steps.
  • Effect of increasing the number of turns: Larger models sustain higher task accuracy for more turns, producing non-diminishing improvements in executable horizon length without establishing a formal scaling law.The task is not knowledge-constrained, since models achieve near-perfect first-step accuracy; output-level aggregation does not reproduce the scaling gains.
  • Why does turn accuracy degrade? The self-conditioning effect: Turn accuracy degrades from both increasing context length and self-conditioning on prior mistakes.At turn 100, injected errors further reduce accuracy, while frontier models largely solve long-context degradation on error-free histories but remain susceptible to self-conditioning.
  • Thinking and single-turn execution: Thinking prevents self-conditioning in Qwen3 models and substantially increases the number of sequential steps executable in one turn.Without CoT, several large and frontier non-thinking models fail beyond six steps per turn, whereas CoT improves execution length.
  • Thinking and single-turn execution: GPT-5 thinking executes 2176 steps in one turn, compared with 432 for Claude-4 Sonnet, 384 for Grok 4, and 120 for Gemini 2.5 Pro.Qwen3-Next outperforms larger standard-attention models, suggesting architecture may affect long-horizon execution.

4 RELATED WORK

Related work examines increasing task complexity, long-context behavior, self-correction, scaling, and tool use, while distinguishing long-horizon execution from these capabilities.

  • Prior work often attributes worsening performance on longer or more complex problems to reasoning failures and studies planning failures in agentic benchmarks.
  • Long-context research evaluates performance as input length grows, whereas long-horizon execution concerns output length; self-conditioning separates the two.
  • Self-correction methods aim to make models respond to prior mistakes by correcting them rather than repeating them, including reinforcement-learning and training-free approaches.
  • Scaling laws report diminishing returns for single-token prediction loss, motivating measures beyond single-step knowledge benchmarks.
  • Unlike symbolic plans that can execute reliably once formalized, LLMs can fail during straightforward long-horizon execution even when the plan is provided.

5 CONCLUSION

The conclusion argues that short-task benchmarks can understate progress on long-horizon execution, while synthetic-task results have important scope limits. It connects scaling model size and sequential test-time compute with longer executable horizons and motivates further study.

  • Scaling model size increases the number of turns a model can execute, while sequential test-time compute increases the task length achievable in one turn.
  • Together, model scaling and sequential test-time compute dramatically increase horizon lengths for LLMs.
  • Improvement on the controlled synthetic task is necessary but not sufficient for long-horizon execution on real-world tasks.
  • The study does not capture the varied actions, action accuracies, and multiple correct plans possible in complex agentic tasks.
  • Long-horizon execution is presented as important for realizing the potential of general, open-ended agents and for agents trained in generative simulated environments.

REPRODUCIBILITY STATEMENT

The reproducibility statement directs readers to detailed methodology, theoretical derivations, prompts, and model specifications across the paper’s supplementary sections.

  • The paper provides comprehensive details of its methodology, experiments, and theoretical results to support reproducibility.
  • The derivation and assumptions for Proposition 1 appear in Section J, while experimental methodology is consolidated in Section G.
  • Section G covers synthetic task design, data generation, prompts for standard and thinking models, and model specifications.

A SELF-CONDITIONING IN REALISTIC AGENTIC TASKS

The authors examine annotated failures from realistic agent benchmarks for signs of self-conditioning, finding recurring patterns in which prior outputs contribute to later failure trajectories. They estimate that such failures constitute substantial shares of failures across GAIA, ALFWorld, and WebShop, while noting that step correctness is subjective in these tasks.

  • Annotated failed trajectories from GAIA, ALFWorld, and WebShop were manually analyzed for potential instances of self-conditioning.
  • The search includes inefficient plans, progress misjudgments based on prior outputs, and causal misattributions that misguide subsequent planning.
  • 20% of GAIA, 48% of ALFWorld, and 33% of WebShop failures were estimated to resemble self-conditioning.
  • WebShop examples include endless query reformulation and paging through irrelevant results, making success impossible.
  • ALFWorld examples show prior memory outputs causing later outputs to ignore visited objects, performed actions, and observations.
  • GAIA examples show inefficient plans repeating similar unsuccessful actions.
  • Because step correctness is subjective in these tasks, the controlled synthetic study helps isolate execution failures from planning and knowledge gaps.

B SEQUENTIALITY OF THE SINGLE-TURN TASK

The single-turn matrix task tests whether models can execute multiple retrieval, multiplication, and addition steps within one response. Without sequential test-time compute, models fail even at two matrices, while thinking substantially improves execution; context management and self-verification have mixed effects.

  • Task design: The task maps keys to 2×2 matrices and requires maintaining a running product across groups of K matrices.Each step retrieves matrices and composes them with the previous state.
  • Sequential computation: Without sequential test-time compute, models cannot multiply even two matrices, whereas thinking substantially increases task performance.The task requires repeated retrievals, multiplications, and additions.
  • Self-verification: Self-verification initially improves Gemma3 performance with CoT but later accelerates collapse by consuming context, while Qwen3 thinking gains little.The extra validation increases tokens per turn and exhausts context sooner.
  • Context engineering: Reducing the context window improves sustained execution on this Markovian task by limiting exposure to prior errors.The approach is task-dependent because fixed sliding windows do not suit long-range dependencies.

D CAN PARALLEL TEST-TIME COMPUTE SCALING MATCH THINKING?

Parallel majority voting does not reproduce the gains from sequential thinking under matched token budgets. The trade-off between turn count and turn complexity also varies across model families and can affect inference cost differently.

  • Parallel scaling: Parallel majority voting with tokens matched to CoT does not match CoT performance.The comparison samples multiple non-thinking Gemma3 outputs and selects the majority answer.
  • Turn complexity: For the same total number of steps, changing turn complexity produces different outcomes without a consistent trend across model families.Higher turn complexity reduces the number of turns needed for a fixed operation count.
  • Inference cost: Increasing turn complexity lowers turn count but raises per-turn inference cost, with token-use trade-offs diverging across model families.The study tracks output tokens, including thinking tokens, for this comparison.

F DECONSTRUCTING ERRORS IN RETRIEVE-THEN-COMPOSE STEPS

Error decomposition shows that models perform retrieval and addition accurately in isolation, while stateful composition degrades over time. The broader experiments also examine thinking, temperature, and prompt-history effects on long-horizon execution.

  • Error decomposition: Near-perfect stateless retrieval and addition contrast with gradual degradation on the stateful prefix-sum task.The prefix-sum task combines arithmetic with maintaining a running state.
  • State tracking: The main difficulty is state management: models must concurrently retrieve information and update the running state.Atomic operations are accurate in isolation, but their combination introduces more opportunities for error.
  • Evaluation setup: The evaluation uses long rollouts with grouped keys, specifying task length through turn complexity and the number of turns.Qwen3 and Gemma3 experiments use 100 rollouts, while frontier evaluations use 20–50.
  • Prompting: CoT prompting requires retaining traces in history to preserve instruction following, increasing the model’s input context.Thinking-model traces are removed from conversation history.

G.4 MODEL SPECIFICATIONS

The experiments use fixed decoding and hardware settings, explicit answer formatting, and format-failure tracking. Format errors are generally low, though some models fail through cheating attempts or context exhaustion.

  • Decoding and hardware: Gemma models use temperature 0.6 and top-p 0.95, while Qwen settings differ by thinking mode; temperature does not materially change observed trends.Experiments ran on 4× NVIDIA A100 GPUs, with frontier evaluations through OpenRouter.
  • Prompt specification: The prompt requires a running total and an answer enclosed in <answer> tags, with examples illustrating the expected interaction.The supplied examples include dictionary values and assistant outputs.
  • Format evaluation: Format failures include missing answer tags or invalid integers, and the study measures their fraction separately from execution accuracy.Clear instructions and few-shot examples are used to reduce these failures.
  • Observed failures: Format failures are generally around 0.1, but Qwen3-8B is an exception and some failures arise from attempting forbidden computation inside answer tags.Gemma3 4B and Gemma3 12B can also encounter context-length-related format failures at later turns.

I CHAIN-OF-THOUGHT SELF-CONDITIONING

The paper finds that CoT does not mitigate self-conditioning, but analyzing this effect for CoT is methodologically difficult because traces are verbose and controlled error injection can be unfaithful or intractable.

  • Including prior CoT traces is necessary for reliable CoT reasoning because Gemma3 models may stop generating CoT when preceding turns lack traces.
  • Verbose CoT histories rapidly exhaust frontier models’ context windows, making the required experimental setup practically infeasible.
  • Altering only final answers creates contradictory histories that test inconsistency resolution rather than execution reliability.
  • Programmatically generated flawed traces introduce multiple failure points and require controlling error type, frequency, and location, making experiments intractable.
  • The paper therefore limits self-conditioning analysis to non-thinking and thinking models.
  • CoT does not mitigate self-conditioning in Gemma3 models, even with programmatically generated CoT histories.

J PROOF AND ANALYSIS OF PROPOSITION 1

Under constant independent step accuracy and no self-correction, task success declines exponentially with horizon length. The analysis shows that near-perfect single-step accuracy makes horizon length especially sensitive to small accuracy gains.

  • Under independent constant per-step accuracy p and no self-correction, horizon length H is defined where task success reaches a target rate s.
  • Task Accuracy at turn H follows TA(H) = p^H because all H steps must be executed correctly.
  • Horizon Length (H0.5) is the number of turns at which Task Accuracy drops to s = 0.5.
  • The formulation enables sensitivity analysis of horizon length to small changes in per-step accuracy.
  • As p →1, a fixed gain in step accuracy produces a quadratically larger improvement in horizon length, highlighting compounding benefits of scale.
Loading 2509.09677v3…