Solving a Million-Step LLM Task with Zero Errors

TL;DR

LLMs have a stubborn per-step error rate (often 1-in-100 to 1-in-1000). On a task where every step depends on the last, that error rate is fatal: a 1% error rate means almost-certain failure after ~100 steps, and state-of-the-art models fall apart on long tasks like Towers of Hanoi after a few hundred steps. This paper’s system, MAKER, solves a 1,048,575-step Towers of Hanoi instance (20 disks) with zero errors — the first system ever to do so at that scale. The trick has three parts: (1) decompose the task to the extreme so each agent does exactly one step with minimal context; (2) error-correct each step by voting — sample the step until one answer is “first to ahead by k” votes; (3) red-flag and discard suspicious responses (too long, malformed) because those correlate with deeper reasoning failures. The punchline for anyone building agents: you don’t need the frontier model. A small, cheap, non-reasoning model (gpt-4.1-mini) was the most cost-effective choice, and the whole million-step run was a four-figure dollar cost.

Problem & Motivation

Real organizations run processes with enormous numbers of dependent steps — building an iPhone touches a ~1B-person supply chain; processing a nation’s tax returns; running a hospital. Each step has to be right, because errors compound. We want to drop LLMs into these processes, but there’s a hard wall: LLMs make errors at a roughly constant per-step rate, and on a chain of dependent steps the success probability decays exponentially.

Make the pain concrete. Say a model is right 99.9% of the time on a single step — that would be a great score on a normal benchmark. Now chain 10,000 dependent steps. Probability all succeed = 0.999^10000 ≈ 0.000045. Effectively zero. The recent “Illusion of Thinking” work showed exactly this: top reasoning models nail Towers of Hanoi up to 5–6 disks, then success plummets to zero as the step count climbs into the hundreds. The horizon length, not the per-step difficulty, is what kills them.

Why don’t existing fixes work?

• Bigger/smarter models lower the per-step error rate but don’t change the exponential shape. You’d need an essentially zero error rate, which no model has, and you’d pay frontier prices on every one of a million steps.
• Single-agent long context — letting one agent carry the whole problem — worsens things: as context grows, the model gets more unreliable, and one bad step derails everything downstream.
• Coarse voting / ensembling (majority vote over whole programs or whole answers) is the right idea applied at the wrong granularity. Two independent million-step trajectories will never agree end-to-end, so voting at the trajectory level is useless.

The paper’s bet: the granularity at which you apply error correction is everything. Push decomposition to the limit, and suddenly error correction becomes cheap and effective per step.

What’s New (Core Contribution)

1. The MDAP framework (Massively Decomposed Agentic Processes). Before: agents were given human-sized roles (“researcher”, “coder”) spanning many decisions. Now: break the task into the smallest possible steps and assign each to a disposable “microagent” with minimal context. The novelty isn’t decomposition per se — it’s pushing it to m = 1 step per agent and showing that’s the regime where error correction works.
2. First-to-ahead-by-k voting as per-step error correction, with closed-form scaling laws. Before: ensembling at the level of full answers, with no theory tying vote-count to task length. Now: sample each single step until one candidate leads by k votes (borrowed from the Sequential Probability Ratio Test / gambler’s ruin), and a derivation showing the required k grows only logarithmically with task length s, so total cost is log-linear — the same scaling class that made classical computing tractable.
3. Red-flagging to kill correlated errors. Before: “repairing parsers” that try to salvage malformed LLM output. Now: the opposite — discard any response that’s too long or malformed, because those signals correlate with the model having gone “off the rails,” and salvaging them reintroduces the correlated errors that voting can’t fix.
4. The empirical headline + a counterintuitive cost finding. First-ever zero-error million-step LLM run, and the demonstration that small non-reasoning models (gpt-4.1-mini, gpt-oss-20B) beat expensive reasoning models on cost-effectiveness, because per-step cost dominates when you have a million steps.

How It Works (Technically)

The whole system is three nested loops. The outer loop walks the s steps of the task. The middle loop runs the vote for one step. The inner loop samples the LLM until it gets a response with no red flags. Let’s build it up.

Setup notation (demystified). A task takes you from input x to a target output y via a sequence of actions a_1, ..., a_s. You decompose it into subtasks of m steps each. Three helper functions glue an LLM into this:

• phi(x) — a templating function that turns the current state into a prompt. (Just string-formatting your prompt template.)
• psi_a(r) — an action extractor that parses the action(s) out of the LLM’s raw response r. (Regex/parse the move = ... line.)
• psi_x(r) — a state extractor that parses the next state to feed forward. (Parse the next_state = ... line.)

So one subtask is literally: r ~ M(phi(x_i)), then actions = psi_a(r), x_{i+1} = psi_x(r). The ~ means “sample from the model” (the LLM is stochastic).

The two extremes. If m = s (no decomposition) you have a single agent doing everything in one giant generation. If m = 1 you have Maximal Agentic Decomposition (MAD) — one fresh agent per step, each seeing only the minimal context (strategy + current state). MAD is the regime this paper lives in.

Why MAD over a single big call? Two reasons. First, because LLMs are autoregressive, a single agent generating action i is dragging along all the context it produced for actions 1..i-1; the longer that context, the more unreliable it gets. MAD resets context every step. Second — and this is the key insight — decomposition creates modularity, and modularity is what makes per-step error correction possible and cheap. You can’t error-correct a million-step trajectory; you can trivially error-correct one move.

The objection: “but now I have s independent points of failure instead of one!” True — the naive probability of getting the whole chain right is the product over all steps (Eq. 8), which decays exponentially. The answer to that objection is the next piece: voting.

First-to-ahead-by-k voting (the heart). For one step, keep drawing candidate answers from the model. Maintain a tally. Stop and return a candidate the moment its vote count is at least k ahead of every other candidate. This is the SPRT-optimal stopping rule, equivalent to a biased random walk (gambler’s ruin): the correct answer (sampled with probability p) races the most likely wrong answer (probability 1-p), and you wait until one is k ahead.

If p > 0.5, the probability the correct candidate wins the race is (Eq. 9):

p(correct wins) = p^k / (p^k + (1-p)^k)

In plain English: raising both p and 1-p to the k-th power amplifies the gap between them. If p = 0.9, then with k = 3 the win probability is 0.9^3 / (0.9^3 + 0.1^3) = 0.729 / 0.730 ≈ 0.9986. You converted a 90% step into a 99.86% step by paying for a few extra samples. Crank k and you can hit any target reliability 1 - ε.

The scaling law (why this is feasible, not just possible). Chain that across all s steps. The probability the whole task succeeds (Eq. 13) and the minimum k you need (Eq. 14) work out to:

k_min = ceil( ln( t^(-m/s) - 1 ) / ln( (1-p)/p ) )  =  Θ(ln s)

The thing to take away: k_min grows only logarithmically with the number of steps s. Going from a thousand steps to a billion steps barely moves the required vote margin. And since cost per step is roughly c · k, the total expected cost is (Eq. 18):

E[cost] = Θ(p^{-1} · c · s · ln s)  =  Θ(s ln s)   when p, c are fixed

Log-linear. That’s the same complexity class as a good sort. This is the whole argument that MDAPs can scale. Contrast with larger m: cost grows exponentially in m (Eq. 17), because for a multi-step block to win a vote, all m sub-decisions must match across samples, and the chance of exact agreement vanishes as m grows. The math actively pushes you toward m = 1.

And because the ln s votes per step are independent, you can run them in parallel — so wall-clock time scales just linearly in s.

Red-flagging (squeezing p higher and decorrelating). Voting only works if p > 0.5 and errors are roughly independent across samples. Two failure modes break this: overly long responses (the model “over-analyzes itself into a cycle of self-destruction”) and malformed output. Both signal the model entered a weird internal state — and crucially, that state produces correlated errors (the same wrong answer repeatedly), which voting can’t fix. So MAKER simply discards any response that exceeds a token cutoff (750 tokens here) or fails format checks, and resamples. With v = probability a response is valid (un-flagged), expected cost becomes (Eq. 19) Θ(c·s·ln s / (v·p)). You trade a few discarded samples for a higher effective p and, more importantly, decorrelated errors.

Architecture & data flow

flowchart TB
  subgraph OUTER["generate_solution: walk all s steps"]
    direction TB
    S0["state x_i"] --> V
    subgraph V["do_voting: one step"]
      direction TB
      VT["vote tally V"] --> GV
      subgraph GV["get_vote: sample until clean"]
        direction TB
        P["phi(x): build minimal prompt"] --> M["sample r ~ M (cheap LLM)"]
        M --> RF{"red flags?<br/>too long / malformed"}
        RF -- yes --> P
        RF -- no --> EX["psi_a(r)=action, psi_x(r)=next state"]
      end
      GV --> TALLY["V[answer] += 1"]
      TALLY --> AHEAD{"leader ahead by k?"}
      AHEAD -- no --> VT
      AHEAD -- yes --> WIN["return winning action + next state"]
    end
    WIN --> S1["state x_{i+1}"]
    S1 -. next step .-> S0
  end
  WIN --> OUT["append action to solution A"]

First-to-ahead-by-k voting as a biased random walk. The correct answer (sampled with prob p) races the top wrong answer; the vote stops when one is k ahead. Drag the sliders for p and k and watch how a low-reliability step (small p) is rescued by a slightly larger k — and how rarely the wrong answer ever wins. Schematic, driven by the paper's Eq. 9.

The algorithm, simplified

# MAKER core: solve an s-step task with zero errors using a cheap LLM.
# Stubs: llm(prompt) -> str ;  build_prompt(state) -> str (this is phi)
#        parse(resp) -> (action, next_state) or raises (this is psi_a, psi_x)

def get_vote(state, max_tokens=750):
    """Inner loop: sample until we get a response with NO red flags."""
    while True:
        resp = llm(build_prompt(state), temperature=0.1, max_tokens=max_tokens)
        if len(resp) >= max_tokens:        # red flag 1: ran long -> likely confused
            continue                       # discard, don't repair
        try:
            return parse(resp)             # returns (action, next_state)
        except FormatError:
            continue                       # red flag 2: malformed -> likely confused

def do_voting(state, k):
    """Middle loop: first-to-ahead-by-k. k ~ Theta(ln s), here k=3."""
    tally = {}                             # candidate (action,next_state) -> count
    while True:
        cand = get_vote(state)             # one clean sample
        tally[cand] = tally.get(cand, 0) + 1
        lead = tally[cand] - max((c for x, c in tally.items() if x != cand), default=0)
        if lead >= k:                      # this candidate is k votes ahead of the field
            return cand                    # decided -> exponentially likely correct

def generate_solution(x0, s, k=3):
    """Outer loop: walk all s dependent steps, error-correcting each."""
    actions, state = [], x0
    for _ in range(s):                     # the s votes are independent -> parallelizable
        action, state = do_voting(state, k)
        actions.append(action)
    return actions

Three loops, no fine-tuning, no RL training, no tools. The intelligence is entirely in the orchestration, not in a better model.

Built on Prior Work

Results & Evidence

Headline: With gpt-4.1-mini, max 750 output tokens, red-flagging parser, k_min = 3, temperature 0.1 (first vote at temp 0), MAKER solved the 20-disk Towers of Hanoi — 1,048,575 steps — with zero errors. First time anyone has done a million-step LLM task error-free.

Convergence matches theory. The number of undecided steps decays exponentially with sampling/voting rounds. Practically: the vast majority of cost is the first k rounds; finishing the stragglers is a rounding error. One pathological step needed 18 rounds — but error decorrelation kept the vote from being overwhelmed.

Cost / model selection (the actionable bit). Estimating per-step error rate p on a small random sample of steps (you know the correct answer a priori in Hanoi) lets you project total cost via Eq. 18 before running. Estimated full-run costs at t=0.95:

• gpt-4.1-mini (τ=0.1): p≈0.9978, k_min=3, ~$3.5K — the winner.
• gpt-oss-20B: cheapest projected open-source choice (~$1.7K) but the together.ai API was less reliable at scale, so they used gpt-4.1-mini.
• gpt-4.1-nano: cheapest per token but error rate 0.36 → k_min=29 → ~$42K. Cheap-per-token ≠ cheap-at-scale.
• o3-mini / haiku-4.5 (reasoning models): lower error but per-token cost makes them more expensive overall.
• Surprises: small non-reasoning models have per-step error rates comparable to reasoning models, and the per-step error rate is roughly flat as disks increase — the encouraging sign that this scales.

Error decorrelation evidence: two independent 10K-step runs of gpt-4.1-mini had zero steps wrong in both runs. Red-flagging (vs. a repairing parser) sharply reduced “collisions” (steps with the first two votes both wrong), confirming it attacks correlated errors.

What the evidence does NOT establish (be honest):

• One domain, and a special one. Towers of Hanoi has a known correct answer per step, exact-match voting, a fixed strategy supplied in the prompt, and i.i.d.-ish steps. That’s the friendliest possible case.
• Execution, not insight. The strategy was given. MAKER was tested on following a known plan, not on discovering one. The hard, open-ended part of real work (deciding what the steps even are) is future work (only “promising preliminary” results in the appendix).
• Exact-match voting only. Real tasks need semantic equivalence (an LLM judge), which reopens the correlated-error problem.
• No real-world task with messy state, variable per-step p, or unknown step count was demonstrated end-to-end.

How You’d Use It

This is the most directly transferable agent paper in a while because it’s an orchestration pattern, not a model. For an AI services company, the move is: stop trying to make one agent reliable over a long workflow; make each step a disposable, voted microagent.

Where it slots in:

• Deterministic, verifiable back-office pipelines. Document processing, data migration/ETL with per-row transforms, ledger reconciliation, claims adjudication, multi-step form filling, compliance checklists — anywhere a step is small, has a checkable answer, and the chain is long. These are exactly the “1% error rate is unacceptable” jobs clients pay for.
• A reliability tier on top of a cheap model. You can sell “zero-error execution” as a capability built on gpt-4.1-mini-class models, with cost that scales s ln s. The voting/red-flag layer is your IP and moat, not the model.
• Pre-flight cost quoting. Eq. 18 lets you quote a long job: sample a few hundred steps, estimate p, compute k_min and projected dollar cost, then decide go/no-go and which model. That’s a real differentiator in proposals — most shops can’t price agentic jobs.
• Decorrelation = safety/audit story. Independent microagents that can’t see the whole task and can’t collude is a genuinely strong governance pitch for regulated clients.

What it does not solve for you: the open-ended “figure out the plan” half of most real jobs. Use MAKER for the execution spine; keep a smarter (possibly human-checked) planning layer above it.

Build Your Own (Minimal Recipe)

You can build a working MDAP executor in an afternoon — the cleverness is in the discipline, not the code.

Components (build in this order):

1. Single-step prompt + state contract. Define the smallest unit of work and a strict output format that carries (a) the action and (b) the next state (so the next agent needs nothing else). This is phi. The “produce next state too” requirement is what lets steps be stateless and parallel-estimable.
2. Strict parser = your red-flag detector. Write parse(resp) that raises on any format deviation, plus a hard token cap. Do not write a forgiving parser. Rejection is the feature.
3. get_vote inner loop. Sample → check red flags → reject-and-resample until clean.
4. do_voting first-to-ahead-by-k loop. Exact-match tally; stop at lead ≥ k.
5. generate_solution outer loop. Thread state forward; fan the k votes out in parallel (async / batch API).
6. Calibration script. On a sample of steps with known answers, estimate p, compute k_min from Eq. 14, and project cost from Eq. 18 to pick the model that minimizes c/p.

The 1–2 genuinely hard parts:

• Defining the decomposition so each step is small enough that the correct answer is the most likely sample (p > 0.5) and the state hand-off is lossless. For Hanoi it’s handed to you; for real work this is the whole game.
• Voting on non-exact answers. The moment answers aren’t string-identical, you need a semantic-equivalence check (an LLM judge), which can itself be wrong and correlated — so you’ll want diversity (different models/temperatures/paraphrased prompts) to keep errors independent.

Reach for: any chat-completions API with async/batch (cost + speed), a cheap non-reasoning model first (gpt-4.1-mini / gpt-oss-20B / qwen-class), asyncio or a batch endpoint for the parallel votes, and a tiny tally dict. No training, no RL, no vector DB needed for the core.

How to Improve It

1. Semantic voting with a judge. Replace exact-match with an LLM equivalence classifier so MAKER applies to open-ended steps (summaries, code edits). Test whether judge errors stay decorrelated enough to keep voting valid — this is the make-or-break extension.
2. Per-step adaptive k and model routing. Estimate p per step type (or detect hard steps online by high disagreement) and raise k or escalate to a stronger model only there. The paper assumes uniform p; real tasks have a few nasty steps that dominate failure.
3. Active decorrelation. The paper notes resampling at temperature isn’t always enough. Inject diversity deliberately: paraphrase the prompt, perturb context, mix models across votes. Measure collision counts as your decorrelation metric.
4. Close the insight loop (recursive MAKER). Treat creating each subtask as itself a voted step (the appendix’s 4-agent decomposition/composition prototype, which already showed promise on large-digit multiplication). This is the path from “executes a given plan” to “solves an open problem.”
5. Verifier-in-the-loop instead of pure voting. Where a cheap external check exists (a parser, a unit test, a constraint solver), use it to break ties or certify a vote, slashing k. Voting is a stand-in for a verifier you don’t have; when you have one, use it.
6. Streaming / unknown horizon. Extend the outer loop to handle an unknown s (terminate on a “done” signal) and to checkpoint/resume — necessary for any real long-running production job.

Glossary

• MDAP (Massively Decomposed Agentic Process) — the paradigm: solve a big task by splitting it into the smallest possible steps, each handled by a disposable agent with error correction.
• MAKER — this paper’s concrete MDAP system (Maximal Agentic decomposition, first-to-ahead-by-K voting, Red-flagging).
• MAD (Maximal Agentic Decomposition) — the extreme where each agent handles exactly one step (m = 1), with minimal context.
• microagent — a fresh LLM call assigned one tiny step; the role is defined by the subtask, not a human persona. Cf. microservice.
• per-step success rate (p) — probability the model gets one isolated step right; the single most important parameter for cost and feasibility.
• first-to-ahead-by-k voting — sample a step repeatedly; accept the candidate that leads all others by k votes. SPRT-optimal.
• k_min — smallest vote margin that hits your target reliability; grows only like ln s.
• red-flagging — discarding (not repairing) responses that are too long or malformed, because those correlate with deeper reasoning errors.
• correlated errors — when independent samples of a step make the same mistake; the failure mode voting can’t fix, and what red-flagging + decorrelation target.
• SPRT (Sequential Probability Ratio Test) — classic statistics: keep sampling until evidence for one hypothesis is decisively ahead; the basis for the voting rule.
• gambler’s ruin — a biased random walk between two absorbing barriers; the math behind win-probability and expected number of votes.
• autoregressive — generates one token at a time conditioned on all prior tokens; why a single agent’s long context degrades reliability.
• log-linear scaling (Θ(s ln s)) — cost grows roughly proportionally to step count times its log; the “good” complexity class that makes million-step runs affordable.
• AALP analysis — accounting for cost in terms of calls to LLM primitives (from Meyerson & Qiu); used to derive the cost equations.
• τ (temperature) — sampling randomness; low τ (0.1) keeps votes focused yet diverse enough to decorrelate.