Solving a Million-Step LLM Task with Zero Errors

Imagine asking today’s AI to help run something like a national tax system, a hospital network, or even the global supply chain that builds your phone. Not just answering a single question, not just drafting one email—but quietly making a million tiny decisions in a row, day after day, without a single serious mistake. Right now, that’s beyond what large language models can reliably do. Today I’ll walk you through a paper that takes that challenge head‑on. It’s called “Solving a Million-Step LLM Task with Zero Errors” by Elliot Meyerson and colleagues. And the big message is this: instead of trying to build one gigantic, ever‑smarter model and hoping it never slips up, we can “smash intelligence into a million pieces” and use lots of tiny, focused AI agents with built‑in error correction to get extremely reliable behavior over very long tasks. This paper doesn’t just talk about it in theory. The authors actually get an AI system to complete a task that needs more than one million separate AI “steps,” in sequence, with zero errors. That’s a milestone, and it has big implications for how we might safely scale AI in the real world. Let’s start with the big picture problem. Modern language models are impressive. They can pass exams, write code, explain physics, and so on. But the way we usually test them is a bit deceptive. We mostly give them short, independent questions: solve this math problem, answer this question, write this function. If the model gets 99% of those right, we call that great performance. But now think about what 99% accuracy means for a long chain of decisions. If every step has a 1% chance of going wrong, and you need a thousand steps to all be correct, the chance that everything goes perfectly plummets. For a million steps, it’s basically zero. As the authors point out in the introduction, a 1% per‑step error rate “is expected to fail after only 100 steps of a million-step task.” The paper leans on a concrete example that’s become a standard stress test for AI reasoning: the Towers of Hanoi puzzle. You might know it: three pegs, a stack of disks of different sizes on one peg, and the goal is to move the whole stack to another peg, moving one disk at a time, never putting a larger disk on top of a smaller one. For a handful of disks, this is easy for AI models. But the number of moves grows very fast: with 10 disks you already need just over a thousand moves; with 20 disks, just over a million moves. Previous work showed that state‑of‑the‑art reasoning models fall apart once the puzzle gets beyond about five or six disks. Their success rate drops to zero as the number of required moves mushrooms. That failure is a concrete illustration of a deeper issue: language models, as we currently use them, are terrible at long-horizon execution. They can come up with a plan, they can understand the rules, but if you ask them to follow even a very clear plan for thousands of steps in a row, they drift, they get confused, and eventually they make mistakes that derail the process. The authors of this paper are basically asking: is there any way to use current models—even small, cheap ones—to execute a million-step process with the kind of reliability you’d want in, say, a safety‑critical system? Before we get into what they do, it’s helpful to distinguish two roles that language models can play, a distinction the paper emphasizes. Role one is “insight.” That covers creativity, figuring out a good strategy, coming up with a plan, making a novel connection. It’s where we ask the model: “How should we approach this?” Role two is “execution.” That’s just: “Given a clear plan and a current situation, what is the next correct step?” It’s about faithfully carrying out instructions, not inventing them. Most demos of AI mix these together. You ask the model to both plan and execute in one long response. When that fails, it’s hard to know: did the planning fail, or the execution, or both? This paper deliberately isolates execution. In their Towers of Hanoi setup, every single AI “agent” is given the strategy upfront in the prompt. The agent doesn’t have to figure out how to solve the puzzle, only to follow a known recipe and apply it to the current state. That choice is important: the million‑step challenge they solve is about “Can we execute a known plan with nearly perfect reliability?”, not “Can we discover a brilliant new plan?” Now let’s talk about the core idea the authors propose: what they call Massively Decomposed Agentic Processes, or MDAPs, and their concrete system, named MAKER. The traditional way to use a language model on a multi‑step task is what you might call the “single‑agent” approach. You give one big model a long prompt describing the whole problem and ask it to generate an entire solution sequence at once—maybe the whole list of a million moves. There are two problems with that. First, as the paper notes, language models are “auto‑regressive”: they generate each new token of text based on everything generated so far. So the longer the output, the more past context they carry, and the more ways they can get confused. Second, once that single model makes a mistake at step 57, there’s no way for later steps to fix it; the whole sequence is compromised. Instead, the authors say: let’s flip this around. Take the big task and break it into the smallest meaningful subtasks you can. In their case, they go all the way to what they call “maximal agentic decomposition”—that is, one step per agent. Each agent’s only job is: given the current state of the puzzle and the last move, decide the single next legal move and the resulting next state. On page 4, they lay this out: with “MAD” (maximal agentic decomposition), there are s agents for s steps, and each one sees just enough information to choose that next move correctly. No more, no less. Think of this like assembly-line work: instead of one super‑worker building an entire car from start to finish, you have a line of many workers, and each one tightens a specific bolt. That’s all they do, but they do it reliably. Why does this help? Because each micro‑agent doesn’t need to juggle a long history. It only has to look at a compact snapshot: the three pegs, which disks are where, and what the last move was. The paper points out that this extreme focus reduces confusion and lets you use smaller, cheaper models with shorter “memory,” because they don’t need to know the whole story, just the local situation. So we have ingredient one: smash the task into micro‑steps, each handled by a tiny, specialized agent. But of course, that introduces a new problem: if each little agent has, say, a 0.5% chance of making a mistake, and you have a million of them in a row, the overall chance that no one ever errs is minuscule. You’ve just multiplied the number of failure points. This is where ingredient two comes in: aggressive error correction at each micro‑step. The way they do error correction is simple in spirit but powerful: they use voting. Here’s the basic idea. For each step, instead of asking one agent once, they ask the model multiple times—independently—with a bit of randomness (they use temperature in sampling). Each of those calls produces a candidate move and resulting state. Then they hold a little election among these candidates. But it’s not just “majority wins after a fixed number of samples.” The paper uses a scheme they call “first‑to‑ahead‑by‑k” voting, described in Algorithms 1 and 2 on page 4. For each step, the system repeatedly samples new candidates and keeps a tally: how many times has each distinct answer appeared? You stop when some answer is at least k votes ahead of every other answer. That candidate is declared the winner and becomes the chosen move for that step. Why is this clever? Because if the correct answer is even just a little more likely than any particular wrong answer—for example, suppose the right move has a 99.5% chance and the most common wrong move has 0.5%—then as you keep sampling, the right move will, with very high probability, eventually pull ahead by k and win. The more “head start” k you demand, the closer your confidence gets to 100%, at the cost of a few more samples. The authors build a simple math model of this on pages 5 and 6. They show a formula where the chance the system solves the entire s‑step task without any errors depends on three things: the base per‑step success rate p, the level of decomposition, and k, this vote margin. They then plot these “scaling laws” in Figures 3, 4, and 5. Let me describe one of these pictures. In Figure 3a, they consider a task with one million steps and show curves of “probability of solving with zero errors” versus k, for different values of p, the base per‑step success rate. When p is 0.99 (a 1% error per sample), a small k gives you a decent, but not perfect, chance of overall success. As k increases, the curve shoots up towards nearly 1: by the time k hits around 7 or 8, the probability of completing a million steps without any mistake becomes very high. Even when p is as low as 0.9 (10% error rate per sample), with a large enough k you can still drive the overall task’s failure probability way down. Then in Figure 4, they look at cost. The more you sample and vote, the more API calls you make, so cost increases. But a key point from their formulas and plots is that the voting threshold k only needs to grow roughly like the logarithm of the number of steps. That’s a slow growth. So even as your tasks go from a thousand steps to a million, the required extra voting—k—only grows modestly, and the expected cost grows roughly like “s times log s,” which is manageable. An important twist here is decomposition. Figure 5 on page 8 is especially striking. It shows what happens if, instead of giving each agent just one step, you give each one a bigger chunk—say 100 steps, or 1000 steps. The expected cost needed to get a reliable whole‑task solution skyrockets, worse than exponentially. Why? Because then the chance that two samples agree exactly on a whole 100‑step sequence becomes tiny, so voting loses power. That’s why the paper really emphasizes “maximal” decomposition: one meaningfully different decision per agent is the sweet spot for scalable error correction. So at this point, the recipe for their system, MAKER, looks like this. For each step in the million-step task: 1. Show a small language model the current state of the puzzle and the last move. 2. Sample answers from that model multiple times, each time asking: “What is the next move, and what will the next state be?” 3. Discard any answers that look “red‑flagged” (we’ll come back to this). 4. Treat the remaining answers as votes and keep sampling until some answer is ahead by k. 5. Adopt that as the official move and state, and pass it to the next step’s agent. Now we need the third ingredient: red‑flagging. Red‑flagging is based on a simple observation, noted in Section 3.3 and tested in Section 4.5: when a language model starts behaving strangely in one way, it’s often a sign that other errors are present. In the authors’ words, “ ‘bad’ behaviors are correlated.” They exploit two easy‑to‑spot warning signs: First, overly long responses. In their preliminary tests they noticed that when the model got confused, it started to ramble. It would go into long, tangled chains of reasoning, revisiting the same points, and often reached the wrong conclusion. On page 11, they mention that once replies got past about 700 tokens, the error rate jumped sharply, even though the overall average error rate across all responses stayed low. In Figure 9a, they plot how the fraction of wrong answers rises rapidly for those long responses. Second, bad formatting. Remember that each agent is supposed to output its answer in a very strict format, like “move = [disk, from_peg, to_peg]” and “next_state = [[...], [...], [...]]”. If the text doesn’t follow that pattern, it’s a hint that the model’s internal reasoning may have gone off track. In earlier experiments they had tried to “repair” such malformed outputs with a helper script, but they discovered that this often meant accepting answers that came from already‑confused reasoning. So MAKER takes a hard line. If a response is too long, or if the formatting doesn’t match exactly, that entire sample is thrown away and doesn’t count as a vote at all. The system just resamples. Intuitively, this does two things. It slightly raises p, the per‑step success rate among the remaining “valid” responses. But more importantly, it reduces “correlated errors”—situations where, for some particular tricky step, many runs of the model keep making the same wrong move over and over. Figure 9b on page 12 captures this. The authors measure “collisions”: how many steps, out of all the million, had their first two valid votes both wrong. If errors are independent and rare, that number should be tiny. But they find that with a generous token limit and a forgiving parser (one that tries to repair formatting), the number of collisions is much higher than expected: some steps repeatedly trip up the model, in similar ways. When they switch to the stricter, red‑flag parser, which discards suspect outputs outright, these collisions drop dramatically. That matters because a step with unusually high, correlated error rates can overwhelm voting if you’re unlucky; reducing that correlation is vital for reliability on very long tasks. With those three pieces in place—maximal decomposition, first‑to‑ahead‑by‑k voting, and red‑flagging—the authors are ready to tackle the full 20‑disk Towers of Hanoi problem. That requires 2^20 − 1 steps—1,048,575 moves—and they aim to get every single one right. Before spending real money on a million‑step run, they do something very practical: they estimate, for several different models, what the per‑step error rate p is and how expensive each step is in tokens and dollars. On page 9, in Figure 6a, they show how several language models behave when asked to do just one step at a time for puzzles of different sizes. The interesting finding is that for a given model, the per‑step error rate stays roughly flat even as the total puzzle size increases. That’s good news: it suggests that per‑step reliability doesn’t crumble just because the overall task is large, at least when you decompose to single‑step agents. Figure 6b is a table that’s particularly revealing. It lists several models—from a tiny “gpt-4.1-nano” up through larger proprietary and open‑source models—and, for each, the observed error rate per step, the cost per million tokens, and an estimated total cost to solve the full million‑step task with a 95% chance of success using MAKER’s voting scheme. What jumps out is this: small, relatively cheap, non‑“reasoning” models can be more cost‑effective than fancy advanced reasoning models for this kind of micro‑step, execution‑heavy work. For instance, a model called gpt‑4.1‑mini, when run at low randomness, has a very low per‑step error rate (around 0.2% to 0.4%), and because it’s cheap per token, the projected total cost to solve the full 20‑disk task reliably is a few thousand dollars. Some more advanced reasoning models, even if they had near‑zero observed errors on the small samples, would still cost more overall simply because their tokens are far more expensive. The authors ultimately choose gpt‑4.1‑mini as their base model for the actual million‑step run, primarily because of this cost/error trade‑off and because the OpenAI API was more reliable at the required scale than the open‑source hosting service they tested. They set the output token limit to 750 to avoid the rambling failure mode, turn on the strict red‑flag parser, and use k = 3 for their voting threshold. For each step, they generate at least three responses in parallel, then more if needed, until some candidate has three more votes than any other. The first vote per step is done with zero randomness, to almost guarantee that the most likely answer is represented; subsequent votes use a low level of randomness to explore nearby alternatives. Then they run the full thing: over a million agent calls, each one a tiny decision in a chain. The result, reported in Section 4.4, is that MAKER solves the entire 20‑disk Towers of Hanoi puzzle with zero errors. Every move is correct. The state evolves exactly as it should, step after step, all the way to the perfect finished configuration. On page 10, Figure 7 shows a snapshot of this process as a visualization: imagine a grid of a million dots, each representing a step; green for steps that have been successfully decided, blue for upcoming ones. At about halfway through, they show the system steadily marching forward, each step decided correctly by its little voting committee of agents. There’s also a video animation mentioned in the caption where you can watch the disks move between pegs as the agents fire in sequence. Beyond the headline “it worked,” they also analyze how the votes converged. Figure 8 plots, for each “round” of sampling, how many steps remain undecided. After the first three rounds, the number of undecided steps drops exponentially with each additional round. This matches their theoretical expectations: most steps are easy, so a correct candidate quickly dominates the vote count. Only a tiny fraction of steps require many more samples. In fact, they highlight one especially pathological step—step 10,241—which needed 18 rounds of voting before a clear winner emerged. In Appendix D and Figure 11 on page 28, they show the “vote race” among three competing candidates for that step. Two of these candidates are wrong but fairly plausible, and the correct one eventually edges ahead. This one weird step serves as a reminder that there are inputs where the model behaves unpredictably, yet the combination of voting and red‑flagging was enough to steer the system to the right outcome. Crucially, the overall cost overhead from these hard cases is tiny. Because such tricky steps are very rare, the vast majority of total compute is spent on the first few votes for each step, and the tail of extra sampling hardly moves the total cost. So what does all this mean beyond a cool Towers of Hanoi demo? The authors argue in their discussion section that this work points to an “orthogonal” path for scaling AI. Typically, we think: bigger models, more data, more training, better results. That’s like building ever taller skyscrapers by making the concrete stronger and the steel thicker. In Figure 1 on page 1 (and again on a log scale in Appendix A, Figure 10), they plot two axes. One axis is “intelligence”—they proxy it by API cost per token, since more capable models tend to cost more. The other axis is “consecutive error-free steps” the system can handle. Standard large models might be very high on the intelligence axis but still relatively low on consecutive steps because they occasionally make mistakes. MAKER, using a relatively modest base model but extreme decomposition and error correction, shoots far to the right: it achieves a million consecutive correct steps, something no single‑agent model did in their tests. This suggests that instead of pouring all our effort into making a single model smarter, we could invest more in building “massively decomposed agentic processes”—networks of many simple, specialized, error‑corrected agents that, together, can reliably carry out very long and complex tasks. There are some powerful analogies here. The paper explicitly compares these micro‑agents to microservices in software engineering: instead of one giant monolithic program, you break it down into lots of little services, each with a narrow responsibility, communicating through clear interfaces. That helps with modularity, scalability, and fault isolation. Similarly, micro‑agents each do one tiny job, manage their own little bit of “state,” and can be scaled up or replaced independently. They also draw parallels to error correction in communication and quantum computing. In those fields, we accept that individual bits or qubits are noisy and unreliable; we get reliability by arranging them cleverly, duplicating information, and voting or correcting at each step. Here, language models are the noisy components, and linguistic “steps” are the units we correct. From a safety and ethics perspective, the authors make some thought‑provoking points. If you can decompose real-world systems—like parts of government processes, hospital workflows, or industrial operations—into tiny, clearly defined micro‑steps, you get much stronger levers for control and oversight. Each agent sees only a narrow slice of the world and has very limited power. You can audit those actions step‑by‑step, sandbox them, and reduce the chance that a powerful model develops unwanted “goals” or harmful emergent behavior. They even connect this to concerns about AI sentience and suffering. If we can accomplish most practical work using many small, non‑sentient models focused on limited tasks, rather than a few extremely capable, potentially more “conscious” systems, we might reduce the risk of accidentally creating entities that can suffer. There are, of course, open questions. The Towers of Hanoi task is highly structured, and the authors freely admit that in this paper they assume the decomposition is given: they know what each micro‑step should look like and how many steps are needed. In the real world, discovering good decompositions is a challenging research problem. They mention this as an “orthogonal open question” and hint at early work where agents also decompose tasks recursively and vote on decompositions—work they sketch in Appendix F with multiplication problems. Another limitation is the need to manage and decorrelate errors in more diverse, messy domains. Here, every step is similar—“What’s the next move in this puzzle?” In a real workflow, steps can be very different from each other, with varying difficulty and error rates. The authors suggest future techniques like prompt paraphrasing and using different underlying models for different roles to decorrelate failures further. But the main conceptual takeaway is clear and, I think, very powerful: reliability over long horizons doesn’t have to come solely from making ever‑more‑perfect AI components. It can come from architecture—from how we arrange imperfect components, how we decompose tasks, how we detect and correct mistakes at the smallest possible scale. To close, let’s go back to where we started: societies depend on long, intricate chains of action. From building airplanes to processing benefits payments, success often means doing thousands or millions of things in exactly the right order, with vanishingly few critical errors. This paper demonstrates, in a clean and concrete way, that current language models, when organized as many small, voting, error‑correcting agents, can already achieve that level of reliability in at least one demanding, million‑step domain. It suggests a future where powerful AI systems look less like a single wise entity and more like a vast, disciplined organization of micro‑workers—each doing one tiny thing, checked and cross‑checked, building up to something far greater than any one agent. As AI continues to move into the machinery of our institutions, this kind of architecture—massively decomposed, error‑corrected, and carefully monitored—may be one of the keys to making that future both feasible and safe.