Source-linked AI summary
Solving a Million-Step LLM Task with Zero Errors
Elliot Meyerson, Giuseppe Paolo, Roberto Dailey, Hormoz Shahrzad, Olivier Francon, Conor F. Hayes, Xin Qiu, Babak Hodjat, Risto Miikkulainen
TL;DR
LLMs struggle to execute long tasks reliably because persistent per-step errors compound across many dependent steps. The paper introduces MDAPs and MAKER, which use extreme decomposition and subtask-level error correction, and reports solving over one million steps with zero errors. The authors conclude that massively decomposed agentic processes may offer an alternative to continually enlarging individual LLMs.
Problem
LLMs have not reliably executed tasks requiring vast numbers of dependent steps, despite their growing use in complex real-world processes.
Method
MAKER implements MDAPs by assigning microagents minimal subtasks and applying subtask-level voting and red-flagging for error correction.
Results
MAKER successfully solved a task with over one million steps with zero errors, and the formalization found effective scaling under extreme decomposition.
Takeaways & Limitations
Massively decomposed agentic processes may provide an alternative to relying on continual improvement of individual LLMs for scaling AI.
Takeaways & Limitations
MAKER assumes tasks can be decomposed into sufficiently small and simple steps, and the theory assumes errors are independent across steps.
Abstract
from arXiv · showhide
LLMs have achieved remarkable breakthroughs in reasoning, insights, and tool use, but chaining these abilities into extended processes at the scale of those routinely executed by humans, organizations, and societies has remained out of reach. The models have a persistent error rate that prevents scale-up: for instance, recent experiments in the Towers of Hanoi benchmark domain showed that the process inevitably becomes derailed after at most a few hundred steps. Thus, although LLM research is often still benchmarked on tasks with relatively few dependent logical steps, there is increasing attention on the ability (or inability) of LLMs to perform long range tasks. This paper describes MAKER, the first system that successfully solves a task with over one million LLM steps with zero errors, and, in principle, scales far beyond this level. The approach relies on an extreme decomposition of a task into subtasks, each of which can be tackled by focused microagents. The high level of modularity resulting from the decomposition allows error correction to be applied at each step through an efficient multi-agent voting scheme. This combination of extreme decomposition and error correction makes scaling possible. Thus, the results suggest that instead of relying on continual improvement of current LLMs, massively decomposed agentic processes (MDAPs) may provide a way to efficiently solve problems at the level of organizations and societies.
1 Introduction
The paper asks whether LLMs can execute enormous tasks with extreme precision and proposes massively decomposed agentic processes to make this possible. MAKER combines minimal subtasks, subtask-level error correction, and micro-roles to solve over one million steps with zero errors.
- The motivating challenge is reliable execution of large real-world processes where even a 1% per-step error rate is unacceptable.
- MDAPs decompose tasks into minimal subtasks, apply subtask-level voting for error correction, and use red-flagging to reduce correlated errors.
- The framework’s scaling laws indicate effective scaling under extreme decomposition but infeasibility without it.
- Over one million steps were solved with zero errors, showing that relatively small non-reasoning models can suffice.
- MAKER assigns each agent a single subtask and uses tiny micro-roles rather than human-level roles, enabling independent repeated solutions for error correction.
- The results demonstrate a multi-agent advantage: MAKER solves a problem that a monolithic single-agent system cannot solve.
2 Background
Long-horizon LLM performance deteriorates as tasks require more dependent steps, motivating decomposition and error correction. Towers of Hanoi provides a scalable testbed because its required steps grow exponentially with the number of disks.
- Performance on long-horizon tasks deteriorates significantly, often exponentially, as task length increases.
- The paper assumes steps are defined a priori and small enough for an LLM agent to solve with reasonable probability; discovering optimal decompositions remains open.
- MAKER exploits malformed output as a possible signal of reasoning errors rather than merely repairing its format.
- Error correction supports scalable computation across communication, storage, quantum computing, and biological systems.
- Towers of Hanoi requires 2^D − 1 optimal steps, so twenty disks require just over one million steps.
- State-of-the-art LLMs’ Towers of Hanoi success rate drops to zero beyond five or six disks, exposing catastrophic long-task reliability limits.
- The benchmark’s goal is to test whether LLM-based systems can scale their intelligence across increasingly many steps, not to replace known algorithms.
3 Methods
MAKER combines maximal task decomposition with voting-based error correction to make million-step reliability theoretically scalable. Its analysis shows that extreme decomposition avoids exponential cost growth, while the required voting margin grows only logarithmically with task length.
- 3.1 Maximal Agentic Decomposition: MAKER decomposes long-horizon tasks into single-step subtasks, limiting each agent’s context and enabling modular error correction.The decomposition parameter m denotes steps per subtask; maximal agentic decomposition uses m = 1.
- 3.2 First-to-ahead-by-k Voting and Scaling Laws: First-to-ahead-by-k voting samples subtask outputs until one candidate leads every alternative by k votes, using stochastic agreement to select actions.The analysis simplifies the competition to a correct candidate with probability p versus one alternative with probability 1 − p.
- 3.2 First-to-ahead-by-k Voting and Scaling Laws: For maximal decomposition, increasing k can maintain high-probability zero-error solutions for million-step tasks even when base per-step error approaches 1-in-10.For lower per-step error rates, the supplied scaling result indicates that even low k can support tasks far beyond one million steps.
- 3.2 First-to-ahead-by-k Voting and Scaling Laws: The voting margin required for a target full-task success probability grows logarithmically with the number of steps, k_min = Θ(ln s).Figure 4a presents this scaling for maximal decomposition.
- 3.3 Red-Flagging: Recognizing Signs of Unreliability: Expected cost grows exponentially with steps assigned per agent, but under maximal decomposition the full-task cost scales as Θ(s ln s).The logarithmic voting factor can be parallelized across Θ(ln s) processes, while larger subtasks incur orders-of-magnitude additional cost.
4 Experiments
MAKER decomposes Towers of Hanoi into single-step agent tasks, calibrates per-step success and cost, and combines voting with red-flagging to solve over one million steps without errors.
- 4.1 Setup: Each agent performs one disk move using only the overall strategy and current disk configuration, separating execution from task-level insight.The setup also requires agents to produce the resulting state for the next agent.
- 4.2 Estimating single-step success rates: Single-step error rates remained stable as disk count increased, while relatively small non-reasoning models matched more advanced reasoning models despite similar output lengths.These findings support using smaller non-reasoning models for long-range MAKER tasks.
- 4.3 Projecting the cost of error correction: Equation 18 projected full-task costs from per-token prices, output lengths, per-step success rates, and minimum voting rounds, identifying gpt-4.1-mini and gpt-oss-20B as preferred choices.gpt-4.1-mini was selected for scale-up because the OpenAI API was more reliable for millions of calls.
- 4.4 Solving the 20-disk problem: Over one million steps with zero errors: The full MAKER system solved the 20-disk Towers of Hanoi task—over one million LLM steps—with zero errors.The result is presented as the first successful million-step, zero-error solution and demonstrates scaling to large time horizons.
- 4.4 Solving the 20-disk problem: Over one million steps with zero errors: Undecided steps decreased exponentially after the first k = 3 sampling or voting rounds, concentrating most LLM calls and cost in those initial rounds.The task remained perfect even with the less statistically powerful first-to-k voting rule.
- 4.5 Investigating the impact of red-flagging: Red-flagging reduced correlated errors, especially collisions where both initial votes were incorrect, addressing unusually difficult steps that required extra rounds.The observed collision count exceeded the i.i.d. expectation at high token cutoffs, particularly with the repairing parser.
5 Discussion and Future Work
The discussion presents MDAPs and MAKER as a framework for scaling reliable LLM execution through decomposition, while identifying boundaries involving decomposition, correlated errors, and broader task types.
- General applications: The framework currently focuses on execution, whereas insight generation remains future work because it is more open-ended and may have irreducible step-wise uncertainty.A broader system would need to handle unknown step counts, heterogeneous step types and success rates, inexact matches, and matching failures.
- General applications: MAKER’s generalization achieved promising results on large-digit multiplication, extending preliminary evidence beyond the Towers of Hanoi domain.The generalized system uses decomposition agents, decomposition discriminators, solution discriminators, and minimal-subtask solvers.
- Correlated errors: The analysis assumes independent identically distributed errors, but red-flagging and independent sampling addressed anomalously difficult steps while more sophisticated decorrelation may be needed elsewhere.A single step with an abnormally high error rate can cause a long-range reasoning process to fail.
- Framework and system properties: MDAPs decompose tasks into minimal subtasks, enabling focused agents and modular system properties such as independent development, scaling, monitoring, and failure tolerance.The framework parallels microservice architectures in its modularity, communication, and separation of responsibilities.
- Limits of decomposition: MAKER assumes tasks can be decomposed into sufficiently small, simple steps that LLM agents solve with reasonable probability, leaving resistant or computationally infeasible decompositions as an open boundary.The authors identify the range between primitive computation and whole-problem reasoning as a key area for investigation.
- Safety and future directions: Extreme decomposition could support sandboxing, auditing, and control by limiting each agent’s scope and reducing opportunities for agents to collude on harmful actions.The discussion also links smaller, limited-scope models to potentially reduced risks for humans and machines.
6 Conclusion
The conclusion frames MDAPs as a scalable alternative to building ever-larger individual LLMs, demonstrated by MAKER on a million-step Towers of Hanoi task.
- Conclusion: Decomposing tasks into minimal subtasks enables efficient error correction for scaling to millions of steps and beyond.The conclusion characterizes this approach as massively decomposed agentic processes, or MDAPs.
- Conclusion: MAKER is presented as the first implementation of MDAPs and its Towers of Hanoi experiments as the first demonstration of their value.The conclusion describes this foundation as opening directions toward general-purpose and long-running applications.
- Conclusion: MDAPs are positioned as an alternative to endlessly larger and more intelligent LLMs, aiming for efficient, safe, and reliable AI by distributing intelligence across many pieces.
A Log Scale Version of Figure 1
Figure 10 reproduces Figure 1 while changing the horizontal axis to a logarithmic scale.
- A Log Scale Version of Figure 1: Figure 10 is the same figure as Figure 1.
- A Log Scale Version of Figure 1: The x-axis in Figure 10 uses a log scale.
- A Log Scale Version of Figure 1: The figure provides a logarithmic-axis presentation rather than a different underlying visualization.
B Additional Derivations
The appendix derives the minimum voting parameter needed to reach a target full-task success probability and examines its asymptotic behavior.
- Additional Derivations: The derivation seeks the minimum k required to achieve target probability t for solving the full task with zero errors.
- Additional Derivations: The algebra transforms the threshold condition into a logarithmic lower bound on k, followed by selection of the first satisfying integer.
- Additional Derivations: The asymptotic analysis considers the regime t > e^-1, where x lies in (0, 1) and classic bounds apply.
C Prompts and Parsers
The prompts specify Tower of Hanoi state-transition reasoning and exact output formats, while parsers extract and validate the move and resulting state.
- Prompt templates: The task follows standard Tower of Hanoi rules: move one top disk at a time, never place a larger disk on a smaller one, and transfer the stack to peg three.
- Prompt templates: Prompts require one next move and its resulting state in exact `move` and `next_state` formats, using 0-indexed pegs.The requested move is represented as [disk id, from peg, to peg], and the state as three peg lists.
- Prompt templates: The procedure moves disk 1 clockwise when the previous move did not move it; otherwise, it selects the only legal move not involving disk 1.
- Parsers: Parsers locate the final move and next_state expressions, evaluate them as Python literals, and raise errors when either field is absent or malformed.
D Sample Responses
The sample responses illustrate both successful move selection and failure modes in long-horizon Tower of Hanoi reasoning, including ambiguity when multiple legal non-disk-1 moves appear.
- Correct and incorrect samples: An incorrect step-10241 sample becomes confused after an early reasoning error, loops until the token limit, and never produces a correctly formatted answer.
- Ambiguous long-horizon reasoning: Another sample exposes an ambiguity: three moves excluding disk 1 are legal, contradicting the instruction that exactly one such move exists.
- State interpretation: The samples resolve peg-stack interpretation by treating the last list element as the top disk, then enumerate legal and illegal moves from that ordering.
- Correct and incorrect samples: At pathological step 10241, the correct sample selects disk 2 from peg 2 to peg 1 as the only legal move excluding disk 1.
E Open-source Model Details
The paper reports open-source model access through the together.ai API, with a uniform temperature setting; the supplied material also includes a pathological voting-step figure.
- Model access: Open-source models were accessed through the together.ai API, and temperature 0.1 was used for all open-source models.
- Model details: Table 1 is identified as providing details on the open-source models used in the paper.
F Multiplication Experiments
The multiplication experiments evaluate recursive multi-agent decomposition and voting, showing improved solve rates as voting strength increases on 5×5 and 6×6 tasks.
- Voting experiments: Increasing voting parameter k improves accuracy for both 5×5 and 6×6 multiplication, reaching perfect 5×5 solve rate and target t = 0.95 solve rate for 6×6.
- Scope: The MDAP implementation is presented as more general than multiplication-specific mechanisms because it recursively decomposes any given task.
- Recursive multi-agent solve: The recursive solver samples and votes on decompositions until an atomic subtask or depth limit, then samples and votes on atomic answers before composing the result.