Solving a Million-Step LLM Task with Zero Errors

As large language models have improved, increasing consideration has been given towards real world economic tasks that require multi-step, long horizon reasoning [kwa2025]. Research in this direction has repeatedly confirmed an inherent property of LLMs: their performance deteriorates significantly (and often exponentially) with the length of the task horizon, regardless of task complexity [schaeffer2023, Dziriexp]. This observation has led to the recent focus on the ability (and failure) of LLMs to execute, i.e., failing to complete many-step tasks, even when a correct plan to follow is explicitly provided to them [sinha2025]. While this work identified a fundamental liability of LLMs in long-horizon execution, it also presented an opportunity: Even small improvements in individual subtask performance could lead to exponential improvements in achievable task lengths [sinha2025].

At the same time, recent theoretical work has claimed that decomposing large tasks into the smallest possible subtasks can have substantial efficiency benefits [meyersonposition]. The rise of decomposing tasks into subtasks solvable by focused “small language model” (SLM) agents in industry, motivated by both reliability and cost [belcak2025smalllanguagemodelsfuture], as well as the burgeoning study of multi-agent LLM systems in academia [guo2024largelanguagemodelbased, wang2024llm_agents_survey], provides evidence for the practicality of this idea. This paper continues this line of work. It is based on the premise that tasks should be broken up into the smallest possible elements, so that an LLM agent can focus on them one step at a time, improving per step error rate, and thus enabling scaling, reliability, and efficiency in the limit. Critical to the feasibility of such an approach is the granularity of the decomposition, i.e., what defines a single step. Since this paper focuses on execution, it is assumed the definition of step is given a priori; an orthogonal open question is how to automatically discover optimal decompositions [russell1991principles, horvitz2021ideal]. Informally, the main condition required for the methods in Section 3 to work is that steps are small enough that, for each step, a correct solution is likely to be sampled, and no incorrect solution is more likely.

Now, when an agentic system is applied to a long and expensive multi-step task, there is a natural desire to extract relevant information from responses even when formatted incorrectly. As a result, substantial work has gone in to generating correctly structured output from an LLM. Grammar-constrained (JSON/CFG) decoding reliably enforces structure and often improves downstream pipelines [geng2025jsonschemabench, openai2024structured], LLMs are fine-tuned to get the format right [grattafiori2024llama3herdmodels, qiu2025evolution], sampling is performed in a way that only tokens respecting the required format are selected [chen2022relation], and Python packages are developed dedicated to fixing an LLM’s output post-hoc so that it can be parsed in a meaningful way [pydantic, json_repair, guardrails_ai]. However, as described in Section 3.3, when an agent makes an error in the output format, this error may indicate that its other reasoning is wrong as well. When a task has been broken into tiny pieces, this property may be exploited to mitigate errors.

Error correction is a critical capability across many important areas of computing, including communication [clark1981error, lin2004error], memory storage [chen1984error], and quantum computing [roffe2019quantum]. Error correction makes it possible to pretend that digital communication and classical computation are deterministic, when in fact, single bits are getting lost and flipped all the time [normand1996single, wang2008single]. Similarly, improved error correction is the single most important ingredient to achieving scalable quantum computing [fowler2012surface_code]. In biological systems, error correction is critical to large processes growing and persisting over time. Error correction is necessary both at the population level, e.g., through the error-correcting effects of recombination [otto2002resolving], and at the individual level, e.g., the cancer-fighting ability of mammals. At the individual level, it correlates highly with lifespan and body size (i.e., scale), with elephants showing the most impressive resistance [abegglen2015potential]. LLMs now serve as the basis of another substrate of computing, linguistic computing, whose constituent processes are language-based algorithms (LbAs) [meyersonposition, chen2024design]. It should then come as no surprise that error correction is critical to achieving LbAs that scale, mitigating for the inherent nondeterminism that results from producing language by pulling from a probability distribution.

Many possible LbA error correction methods can be derived from instances in other fields [shannon1948]. One way to reduce errors is for an LLM to reflect on its output and explicitly correct any error it sees [manakul2023selfcheckgpt]. Another approach is to quantify and exploit LLM uncertainty explicitly [xue2023dynamicvoting, xin2024semantic]. For example, work on semantic density shows that the semantic content most consistently sampled from an LLM for a given prompt is more likely to be correct than a greedy decoding [xin2024semantic]. This promise of semantic consistency in sampling makes a third, simpler, approach possible: voting, or ensembling, which has been a core machine learning technique for decades [opitz1999popular, mienye2022survey, ganaie2022ensemble], and is now commonly used to boost the accuracy of LLM-based systems [Trad2025voting]. To date, ensembling has mostly been implemented in LLMs at an action level far above that of a single minimal step. For example, state-of-the-art LLM-based coding systems often use a majority vote of outputs of complete programs that are each a candidate solution to a coding challenge [li2022alphacode, wang2022selfconsistency]. However, when scaling to tasks with thousands or millions of dependent steps, the level of granularity at which error correction is applied is critical, as will be shown in Section 3.

Towers of Hanoi was recently introduced as a test domain for investigating the capabilities and limitations of state-of-the-art LLM reasoning models [shojaee2025illusion]. This benchmark is based on the classic game in which there are three pegs and $D$ disks, and the goal is to move all disks from the first to the third peg, moving only one disk at a time, and maintaining the condition that a larger disk never sits atop a smaller one [hinz2013tower]. In the benchmark, an LLM system is asked to produce a sequence of moves $(m_{i}=[d_{i},s_{i},t_{i}])_{i=1}^{n}$ whose execution completes the task, where the $i$th move is executed by moving disk number $d_{i}\in\{1,...,D\}$ from source peg $s_{i}\in\{0,1,2\}$ to target peg $t_{i}\in\{0,1,2\}$. The problem scales naturally to enormous numbers of required steps by simply adding more disks, since the optimal number of steps to complete the task is $2^{D}-1$. For example, solving Towers of Hanoi with ten disks takes just over a thousand steps, and with twenty disks just over a million steps. In its most famous (mythological) incarnation, monks work continuously on an instance with 64 disks, which is expected to take around 585 billion years, at which point the universe will end [moscovich20011].

Performance of state-of-the-art LLMs degrades catastrophically on this benchmark: They are able to complete the task with a high success rate up until five or six disks, after which the success rate plummets to zero [shojaee2025illusion]. What this degradation means with respect to whether or to what extent an LLM is really ‘thinking’ or ‘reasoning’ is up for philosophical debate and is outside the scope of this paper [varela2025rethinking, khan2025comment, opus2025illusion]. However, this result made it clear that the reliability of state-of-the-art LLMs is fundamentally limited: If they need to complete every step correctly in order to solve a task, after a certain number of steps they will almost surely fail as a result of an underlying propensity to make errors, even when the answer should be obvious. While an error rate of 1-in-1,000 seems low, and would be great on a traditional LLM benchmark, on a task that requires successful execution of thousands of steps in a row, such a system results in inevitable failure.

Two critiques of Towers of Hanoi as a benchmark should be addressed upfront. First, one could argue that it is not an ideal LLM task since one could write code to solve the problem, and optimal algorithms are known [hinz2013tower]. True, but producing solutions is not the point: instead, the domain provides an ideal testbed for investigating the capacity of LLM-based systems to scale their inherent intelligence to increasingly large numbers of steps. Second, one could argue that this problem is too hard, since large real-world tasks might allow for a handful of errors without catastrophic results [simon1957models]. However, focusing on a case where no error can be tolerated forces us to pursue the elimination of any kind of error that is likely to arise on a long timescale, and this focus can lead to insights and practical methods that might otherwise be overlooked. There also are real-world safety-critical systems where no error can be tolerated [kremer1993ring]. Therefore, as LLM-based systems become ubiquitous in real-world decision making processes, it is essential these systems can reliably make decisions without error. Thus, the problem provides an ideal testbed for developing techniques that will be critical to scaling LLM-based systems to one million steps and beyond.

In a long-horizon agentic task with $s$ steps, the goal of an LLM-based system is to produce a sequence of actions $a_{1},\ldots,a_{s}$ that yields a target output $y$ given the initial input $x$ [sinha2025]. This paper is concerned with the following question: How does the decomposition of the task into subtasks affect its solvability?

The $s$-step task can be decomposed into subtasks, with the granularity of the decomposition defined by the number of steps $m$ per subtask. Subtasks can then be solved by separate calls to LLM agents, where a templating function $\phi$ maps the input and specification of a subtask to a prompt for an LLM $M$, an extractor $\psi_{a}$ parses actions from the LLM’s output response $r$, and a second extractor $\psi_{x}$ parses information from $r$ to include in the input to the next subtask. Let $x_{0}=x$. A solution to the full task can then be sampled recursively:

Of particular interest are the two extreme cases: the case of no decomposition, i.e., $m=s$, termed single-agent:

and the case of maximal agentic decomposition (MAD), i.e., $m=1$:

Because LLMs are auto-regressive, when generating the $i$th action, a single agent $M$ is increasingly burdened by the context produced in generating actions $a_{1},\ldots,a_{i-1}$. Therefore, as the context increases, its outputs become increasingly unreliable [du2025contextlengthhurtsllm]. However with MAD, an agent’s context is limited to an amount of information sufficient to execute its single assigned step, allowing it to focus on its assigned role and avoid confusion that can creep in from irrelevant context. This focus also allows the use of smaller LLMs with more limited context sizes.

One might argue that this decomposition might improve the reliability of any given LLM call, but by decomposing the task into $s$ independent calls, there are now $s$ possible points of failure, instead of just one. That is, there are $s$ opportunities for a weakest link to compromise the entire system, since for a correct action sequence $a_{1}^{*},\ldots,a_{s}^{*}$, the probability of generating it without error is exponentially decaying as the number of steps increases:

First, note that a single long LLM call also suffers from a form of exponentially decaying probability of correctness [Dziriexp]. Second, and more importantly, the modularity induced through maximal decomposition allows for a form of effective and efficient error mitigation and unreliability detection (“red-flagging”) that is not possible with a single large call. These capabilities will be described in the next two subsections.

For simplicity, the error correction in this paper uses the statistical power of independent samples from a stochastic process (here an LLM). To determine a winner from these samples, a first-to-ahead-by-$k$ voting process is used, motivated by the optimality of such an approach in the sequential probability ratio test (SPRT) [wald2004sequential, lee2025consol]. Many improvements are possible beyond this first implementation. For example, in the experiments in this paper, exact matches between actions are required, but in general, a classification function could be used to determine semantically equivalent outputs (e.g., implemented by an LLM, see Section 5).

Concretely, given an LLM $M$, candidate samples are drawn for a subtask (Eq. 2 & 3) until one has been sampled $k$ times more than any other (Alg. 2). This process is a generalization of the classic gambler’s ruin problem [bernoulli1713ars], but with simultaneous dependent races between all pairs of candidates [ross2025first]. Since there is no known closed form for this general case, the analysis is simplified by assuming the worst case, i.e., that a correct candidate with probability $p$ races against a single alternative with probability $1-p$. If $p>0.5$, the probability that the correct candidate gets selected through this process is

and there exists some $k$ such that this voting process will result in the correct candidate winning with probability $1-\epsilon$, for any given error rate $\epsilon\in(0,1)$.

Now, suppose that the task requires $s$ total steps to complete, with an inherent per-step success rate $p$, a decomposition level given by the number of steps per subtask $m$, and suppose that a margin of $k$ votes is required to decide an action for each subtask. Again, assume that the correct solution for each subtask races against only a single most-likely alternative. Note that this assumption is much more favorable to larger values of $m$, i.e., less decomposition, since a most likely alternative captures a vanishing proportion of the total alternative (incorrect) probability mass as $m$ grows. Let $p_{\textrm{vote}}$ be the probability of sampling a correct vote for a subtask, $p_{\textrm{alt}}$ the probability of sampling the alternative, $p_{\textrm{sub}}$ the probability that the voting procedure succeeds on a subtask, and $p_{\textrm{full}}$ the probability that it succeeds on all subtasks, i.e., that the full task is completed successfully. Then,

where Eq. 12 comes from plugging $p_{\textrm{vote}}$ and $p_{\textrm{alt}}$ into the hitting probability formula for gambler’s ruin [ross2025first]. Figure 3 uses Eq. 13 to illustrate how a high probability of overall success $p_{\textrm{full}}$ can be maintained by increasing $k$ in the case of $m=1$, i.e. in a maximal decomposition.

It is now possible to write down the expected cost in terms of calls to LLM primitives, i.e., perform AALPs analysis [meyersonposition]. Let $c$ be the cost of generating a response for a single step with LLM $M$. Assuming the cost of generating tokens scales linearly with the number of tokens (since this is how APIs are priced), the cost of an agent generating a sample for $m$ steps is $c_{\textrm{sample}}=cm$. Let $c_{\textrm{vote}}$ be the expected cost of sampling either a correct vote for a subtask or the alternative against which it races, $c_{\textrm{sub}}$ the expected cost of completing a subtask, and $c_{\textrm{full}}$ the expected cost of completing the full task. Then,

where Eq. 16 comes from plugging Eq. 12 into the hitting time for gambler’s ruin [bernoulli1713ars], Eq. 17 comes from multiplying by the number of subtasks, and the approximation holds when $p_{\textrm{sub}}\approx 1$, i.e., when the error tolerance is low. Notably, the cost grows exponentially with $m$. Figure 5 illustrates this phenomenon. As the number of meaningful decisions assigned to an agent grows, the chance that its sequence of decisions will match exactly across multiple samples vanishes. In contrast, in the MAD case, the system scales log-linearly with $s$:

when $p$, $c$, and $t$ are held constant. Figure 4(b) illustrates this efficient scaling. The discovery of algorithms that scale log-linearly has been critical to the scalability in classical computing [cormen2022introduction]. This result is therefore encouraging: It shows the potential of LLM-based systems to scale in a similar manner, increasing their reliability to a point where it is possible to trust them to complete long-running tasks. Furthermore, the $\Theta(\ln s)$ factor in Eq. 18 corresponds to the number of votes required per step, which in practice can be parallelized across $\Theta(\ln s)$ processes. So, the time cost of the parallelized system scales only linearly with $s$.

Since $p$ plays such an important role in the cost of the system, when possible, it is worth taking practical measures to push it higher. The simple premise is that “bad” behaviors are correlated in LLMs, so if an LLM produces a response that signals pathological behavior, the response should be flagged and simply discarded. Since in MAD each agent is responsible for only a single step, each step is not too expensive, and it can be discarded and a new action resampled (i.e., by making another agent call). In this paper, two signs of unreliability are used as red flags: (1) overly long responses, and (2) incorrectly formatted responses. The hypothesis is that not only will discarding flagged respones increase $p$, it will also meaningfully reduce correlated errors, since both flag types indicate that the LLM has been conditioned into a strange starting point before sampling. It is simple to detect these signs and discard their responses, but, since the paper focuses on understanding the impact on the expected cost of highly scaled long-horizon tasks, it is worth elaborating on the motivation and impact of this implementation choice.

Consistent with observations in prior work that longer answers tend to have more errors [liu2024lostinthemiddle], preliminary experiments for this paper showed that once an LLM gets initially confused, it can go off the rails and over-analyze a situation in a cycle of self-destruction. In MAD, each agent’s role is highly focused and relatively simple; if an agent is doing too much work to figure out its answer, it is likely to be confused and missing the point, and therefore more likely to give an incorrect answer. Even if the success rate is increased only from 99% to 99.9%, such an increase can have a large impact when the number of steps is large.

Similarly, preliminary experiments showed that when an agent produces an answer in an incorrect format, it is more likely to have become confused at some point on the way to that answer. So, instead of trying to fix the format of the answer in some way, the detection of the incorrect format can be flagged and the sample discarded.

Experimental evidence for the above two phenomena is detailed in Section 4. Formally, if $v$ is the probability that a valid response is parsed from the LLM’s output, i.e., no red flags, then the expected cost of MAKER can be written as:

where $p$ now indicates the per-step success rate given that the response is valid. In practice, this formula can be used to decide the trade-off between incorporating more red flags to increase $p$ (potentially resulting in a lower $k_{\min}$, whose calculation depends on $p$ but not $v$) and the incurred cost overhead of discarded samples.

The most straightforward approach is to estimate $p$ on a relatively small number of steps to determine the choice of model and red flags, i.e., $c$ and $v$, as well as the value of $k$, before running the system on the full task with $s$ steps. An example application of this approach is demonstrated in the next section.

The implementation of MAKER for this problem was derived from the single-agent approach introduced in prior work [shojaee2025illusion]. The single-agent prompts were modified so that each agent knows that it must only perform a single step of the problem, i.e., to move a single disk.

For efficiency, and to focus the agents as much as possible, each agent is given the minimal context it needs to perform its single step. In the case of Tower of Hanoi, everything the agent needs to know is the overall strategy and the current state of the problem, i.e., the configuration of disks. As in prior work [sinha2025, shojaee2025illusion], the overall strategy is provided in the prompt for each agent. The strategy works for any even number of disks and is the one most often suggested by the LLMs themselves when no strategy is provided a priori. (Appendix C). This design choice effectively isolates the ability of agents to execute clear instructions from the ability of LLMs to have insights about how tasks should be solved (Section 5; see also [sinha2025]). Both insight and execution are essential to the capabilities of LLMs, but often they are entangled in experiments, making it difficult to identify the source of failure. Focusing on execution makes it possible to pursue the goal of finding minimal conditions for scaling LLM systems with respect to the number of steps.

The full agent prompt template is given in Appendix C. Given the current state (i.e., configuration of disks) and prior move (which disk was moved from where to where), each agent is asked to provide the next move and the resulting next state. Unlike in the single-agent case, where only the sequence of moves needs to be produced, in the MAD case each agent must produce the resulting state, since this is critical information to be fed to the next agent. Each agent is asked to format its answers as “move = <move>” and “next_state = <next_state>”. Superficially, the requirement to produce the next state along with the action creates even more potential points of failure beyond the single-agent case, but, as it turns out, any drawbacks are overcome by the advantages of extreme decomposition and error correction.

Running an LLM-based system at the scale of a million steps is expensive. It is thus desirable to calibrate the parameters of the system and estimate the success rate and cost before any large experiments are run. Equation 18 provides such a calibration and estimation method. Key to this estimation is the per-step success rate $p$, which depends on the underlying LLM used.

A straightforward way to estimate the per-step success rate is to run the system on a random subset of steps. One advantage of having the same strategy in the prompt of each agent is that the correct answer is known for each step, and, assuming every prior step is correct, the inputs are known as well. This knowledge also makes it possible to use the API to obtain a batch of answers for many steps asynchronously, thus greatly speeding up wall-clock time of experiments and reducing cost [OpenAI_BatchAPI_Pricing]. These properties are part of what makes Towers of Hanoi such a practical testbed for many-step methods. For other problems, it may not be possible to estimate $p$ as efficiently, but, in any case, it should be possible to estimate it to a practical degree.

These initial exploratory estimation experiments were run without red-flagging. That is, agents were given a maximum of 2048 output tokens as an initial conservative upper bound, ensuring they have plenty of space to express whatever answer they need to express. They also used a “repairing parser” (written by an LLM, Appendix C) that attempted to correct some of the more common formatting errors in order to extract the LLM’s intended answer reliably out of its output. Importantly, since these experiments focus on the inherent generative reasoning capabilities of LLMs, they do not include LLMs that have access to auxiliary tools.

There are two important and perhaps surprising takeaways from this figure: (1) Different LLMs have different base error rates, but those of relatively small non-reasoning models are comparable to more advanced reasoning models, suggesting that non-reasoning models may be a more effective fit for long-range tasks with MAKER. Figure 6(b) shows that this difference cannot be explained by a difference in output tokens, since the models use a similar number of tokens. (2) The per-step error rate is remarkably stable as the number of disks increases, a highly encouraging sign that MAKER will enable scaling to a large number of steps without the kind of exploding error rates often seen with single agents.

Based on the single-step error rates estimated above, it is possible to estimate the cost of successfully solving the full 20-disk task for models with $p>0.5$, i.e., models for which voting converges to correct subtask answers as $k$ increases. The table in Figure 6(b) shows these estimates, given the per-token cost of the model, the mean number of output tokens per step, and the empirical estimates of $p$ and $k_{\min}$. For a given model, its estimated cost per sample (Section 3.2) is:

where $c_{\textrm{in}}$ and $c_{\textrm{out}}$ are the cost of input and output tokens, respectively, and $n_{\textrm{in}}$ and $n_{\textrm{out}}$ are the estimated average number of input and output tokens per sample. The cost per sample is multiplied by the expected number of samples to get the overall cost. For the target probability of success $t=0.95$, these results make it clear that the most effective proprietary choice is gpt-4.1-mini, and the most effective open-source choice is gpt-oss-20B. Whether these estimates are useful depends on whether the errors are sufficiently decorrelated across runs. Indeed they appear to be: In two independent runs of gpt-4.1-mini ($\tau=0.1$) on the set of 10K random samples, there were zero steps that had errors in both runs. Decorrelation of errors is discussed further in Sections 4.5 and 5.

Although the projected cost of gpt-oss-20B is lowest overall, in the scale-up experiment, gpt-4.1-mini was used because the OpenAI API was found to be more reliable than that of together.ai (a critical factor for experiments requiring millions of agentic calls). Note also that for reasoning LLMs with higher per-token cost than those in Figure 6(b), even if their estimated per-step error rate were zero, and therefore $k_{\min}=1$, their overall cost would be higher than that of gpt-4.1-mini, simply due to the cost of running on all $2^{20}-1$ steps, and it would be practical to assume the error estimate is a lower bound and set $k=2$. Thus, using the non-reasoning gpt-4.1-mini saves thousands of dollars in the scale-up experiment compared to the other proprietary models.

With gpt-4.1-mini as the base model, the maximum output token threshold was set to 750, and a red-flagging output parser was used to enforce the basic formatting requirements. Beyond this cutoff, the model often found itself in confusing logical loops; misformatted output was often correlated with such twisted reasoning, allowing them to be detected and discarded (as will be discussed further in Section 4.5). Since $k_{\min}=3$, at least three responses were generated in parallel for each step. The first step was generated with a temperature of 0 to make sure the best possible guess is included in the votes. For all subsequent votes, a temperature of 0.1 was used.

With these calibrations, the full system solved the problem perfectly. Figure 7 shows a snapshot of an animation visualizing the movement of the disks through the million steps as well as the sequence of agent activations that accomplish it. This result constitutes the first successful solution of a task with one million LLM steps with zero errors, establishing that scaling LLM-based systems to large time horizons is possible.

The exponential decay in the number of undecided steps mirrors the theoretical prediction. Due to this exponential decay, the vast majority of LLM calls (and therefore cost) is spent in the first $k$ calls, while the remaining cost is, for practical purposes, a rounding error. Notably, the task is solved perfectly even when using a less statistically powerful first-to-$k$ voting (i.e., the first candidate $k$ votes wins), illustrating the robustness of the approach.

Although the system completes with zero errors and as efficiently as expected, the fact that a few of the steps take notably more sampling and voting rounds than others could be cause for concern. The next section looks into how red-flagging reduces the negative impact of such correlated errors.

Red-flagging was hypothesized to reduce the per-step error rate, but also the impact of correlated errors, i.e., particular steps that have unusually high error rates compared to the average step. Figure 9 shows evidence for both of these phenomena; however, the impact on correlated errors turns out to be a much more important effect. In the first two rounds of voting, the max number of output tokens (when calling the API) was set to 2048 to enable this analysis. Figure 9(a) shows that the per-step error rate increases precipitously once the response length crosses about 700. Although $p$ past this threshold is still around 90%, this is a drastic degradation compared to error rates on the order of 1-in-1000 with shorter responses. Even so, since so few of the overall responses are overly long, the overall $p$ at higher max token thresholds is not much larger, and in particular, not large enough to induce an increase in $k_{\min}$.

However, the main benefit of red-flagging becomes clear in Figure 9(b). This figure plots the number of collisions across the first two votes of all steps in the 20-disk experiment, i.e., how many steps have both votes incorrect. The number of collisions is computed across max token cutoffs for both the repairing parser used in Section 4.2, as well as the red-flagging parser used in Section 4.4. Assuming the steps are i.i.d. with a uniform success rate, the expected number of collisions is no more than one or two in all cases. However, with a high max token cutoff the observed number of collisions is much higher, especially with the repairing parser. Red-flagging successfully reduces some of these correlated errors and may be critical to the success of the method on many-step tasks. Appendix D illustrates what correlated errors in this domain can look like, and Section 5 discusses techniques for reducing correlation.