wikillm

Paper · 2025-11-12 · cs.AI, cs.CL, cs.MA

Solving a Million-Step LLM Task with Zero Errors

MAKER splits a 20-disk Towers of Hanoi solution into 2^20-1 single-move subtasks, each answered by a separate LLM call. Each move is chosen by first-to-ahead-by-k voting, and replies that are overlong or malformed are discarded. With gpt-4.1-mini and k=3 the authors report a full run with zero errors. Author-reported.

Task decompositionMulti-agent systemsSelf-consistencyagentserror-correctiontask-decompositionvotinglong-horizon

arXivPDFCodeMarkdown12 min read

AI-compiled by claude-haiku-5-5 on 2026-11-12, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.

In plain words

Picture a job made of a million small decisions where one wrong move spoils the whole thing. A language model gets each decision right most of the time, but at this length even a 1% error rate on each step makes failure almost certain. This paper's system, MAKER, copes by cutting the job into the smallest possible steps and giving each step to its own fresh model call, which sees only the current situation. For each step it asks the model several times and keeps the answer that first leads the others by a set margin. It also throws away replies that run too long or come out in the wrong format, since those tend to come from a confused model.

The test case is the Towers of Hanoi puzzle with 20 disks, which takes 1,048,575 moves. The authors report that the full run finished with no wrong moves. The bet is that many small, checked steps can scale further than hoping one bigger model never slips.

TL;DR

MAKER splits the 20-disk Towers of Hanoi task into 2^20-1 single-move subtasks, each handled by its own LLM call. Each move is decided by first-to-ahead-by-k voting, and replies with overlong or malformed output are discarded. With gpt-4.1-mini and k=3, the authors report a full run with zero errors. The authors argue that many small checked steps may scale better than ever-larger single models §5. The repository's notebook covers only a 4-disk example; the 20-disk run is not released.

Problem

A task of s steps, each done correctly with probability p, succeeds with probability p^s. At a 1% per-step error rate, a million-step task is expected to break down within roughly a hundred steps §1. Single-agent runs on Towers of Hanoi fail after five or six disks §2.3, which the paper takes from prior work.

The method rests on one informal condition: steps must be small enough that a correct answer has a reasonable chance of being sampled, and no wrong answer is more probable than the right one §2.1. The paper assumes the step definition is given, and does not address how to find a good decomposition §2.1.

Method

The method has three parts §3. The paper's experiments use a single LLM for all agents §5.

  1. Maximal decomposition. Split the task into s steps, one agent per step, so each agent's input is only the previous action and the current state §3.1 eq. 5-7. The single-agent baseline draws all s actions in one context eq. 4. Each decomposed step is a separate call, so there are s chances to fail instead of one §3.1.
  2. First-to-ahead-by-k voting. For a step, sample candidates until one leads every rival by k votes §3.2 alg. 2. Votes are exact matches §3.2; see Paper vs code for which value is compared.
  3. Red flags. Discard any sample whose output is overlong or does not parse, and draw a new one §3.3 alg. 3. The paper argues that such samples come from a model already in a confused state, so their errors are correlated §3.3.

The main loop, from the paper's Algorithm 1 alg. 1, with the voting and red-flag steps from Algorithms 2 and 3:

Pseudocode
# MAKER main loop  [alg. 1]
# Input:  initial state x0, LLM M, margin k, number of steps s
# Output: list of s actions

def generate_solution(x0, M, k, s):
    # Start with no previous action and the initial state  [alg. 1]
    actions = []
    action = None
    state = x0
    for step in range(s):
        # One agent decides one step, given the previous action and state
        # [§3.1] [eq. 2-3]
        action, state = do_voting((action, state), M, k)
        actions.append(action)
    return actions
Pseudocode
# First-to-ahead-by-k voting over red-flag-filtered samples  [alg. 2]
# Input:  x = (previous action, state), LLM M, margin k
# Output: winning (action, next state) pair

def do_voting(x, M, k):
    # Count each candidate (action, next state) pair  [§3.2]
    vote_counts = {}
    while True:
        candidate = get_vote(x, M)  # one valid sample  [alg. 3]
        vote_counts[candidate] = vote_counts.get(candidate, 0) + 1
        # Strongest rival's count, 0 if there is none  [alg. 2]
        rival_max = max(
            (count for other, count in vote_counts.items()
             if other != candidate),
            default=0,
        )
        # Win once the candidate leads every rival by k  [eq. 9] [alg. 2]
        if vote_counts[candidate] >= k + rival_max:
            return candidate
Pseudocode
# Sample until a reply passes the red-flag parser  [alg. 3] [app. C]
# Input:  x = (previous action, state), LLM M
# Output: one (action, next state) candidate

def get_vote(x, M):
    previous_action, state = x
    while True:
        # Ask one agent for the next move and the resulting state [app. C]
        response = M(build_prompt(previous_action, state))
        # Overlong output is cut off at the token cap and fails to parse
        candidate = parse_flagged(response)  # None if any red flag fires
        if candidate is not None:
            return candidate

The prompt gives the agent the full strategy for the puzzle and the current state, plus the previous move. The strategy is the one the authors' LLMs most often proposed unprompted. When the last move left disk 1 alone, the agent shifts disk 1 one peg around the cycle; when it moved disk 1, the agent makes the one legal move that leaves disk 1 where it is §4.1 app. C. The agent replies with a move and the next state in fixed text formats §4.1 app. C.

The red-flag parser accepts a reply only if it contains a move of three integers and a next state of three lists that together hold disks 1 to N exactly once app. C parsers.py.

Pseudocode
# Red-flag parser: a candidate, or None when a red flag fires  [app. C]
# The last 'move' and last 'next_state' are taken, each matched on its own

def parse_flagged(response_text, num_disks):
    move = last_match(response_text, "move = [a, b, c]")
    next_state = last_match(response_text, "next_state = [[..], [..], [..]]")
    if move is None or next_state is None:
        return None
    # Inner brackets must not nest: each value matches [^\[\]]*
    if not is_three_ints(move):
        return None
    # Three pegs, disks 1..num_disks each exactly once across them
    if not is_valid_state(next_state, num_disks):
        return None
    return (tuple(move), tuple(tuple(peg) for peg in next_state))

The paper also uses a looser repairing parser, written by an LLM, in its exploratory runs. It tries to fix common formatting mistakes and extracts an answer from any reply that is not too long §4.2 app. C.

Scaling laws. For m=1 (one step per agent), the probability of a correct answer after voting is p^k over p^k plus (1-p)^k eq. 9. The probability of solving all s steps is then eq. 13:

p_{full} = \left(1 + \left(\frac{1-p}{p}\right)^{k}\right)^{-s/m} \qquad \text{[eq. 13]}

The smallest k that reaches a target success t is eq. 14:

k_{min} = \left\lceil \frac{\ln\left(t^{-m/s} - 1\right)}{\ln\left(\frac{1-p}{p}\right)} \right\rceil = \Theta(\ln s) \qquad \text{[eq. 14]}

This needs p > 0.5 app. B. The paper's worst-case model has the correct candidate racing against a single alternative §3.2. The expected cost for m=1 is eq. 17 eq. 18:

c_{full} \approx \frac{c\, s\, k_{min}}{p^{m-1}(2p-1)} \qquad E[\text{cost}] = \Theta\!\left(p^{-1} c\, s \ln s\right) = \Theta(s \ln s)

Here c is the cost of one step's sample, and the paper assumes cost is linear in tokens §3.2. With red flags, where v is the probability that a sample is valid §3.3:

E[\text{cost of MAKER}] \approx \frac{c\, s\, k_{min}}{v(2p-1)} \qquad \text{[eq. 19]}

Hyperparameters

NameValueWhereNotes
Disks N20§4.42^20-1 = 1,048,575 steps §4.4 §2.3
Model (full run)gpt-4.1-mini, OpenAI API§4.3 §4.4chosen over gpt-oss-20B because the OpenAI API was more reliable
Vote margin k3§4.4equals k_min at t=0.95 for gpt-4.1-mini fig. 6 eq. 14
Target success t0.95fig. 6cost table; fig. 4 uses 0.9 (see Pitfalls)
Samples per stepat least 3 in parallel§4.4"at least" because a step may need more votes
Temperature, full run0 for the first sample, 0.1 for the rest§4.4"first step" is ambiguous (see Pitfalls)
Max output tokens, full run750§4.4the cap that triggers the overlong red flag
Max output tokens, exploratory2048§4.2 §4.5used for error-rate estimates and for the red-flag analysis
Red flagsoverlong reply; reply not in required format§3.3 §4.4
Single-step success, gpt-4.1-mini (T=0.1)p = 0.9978 (1-p = 0.0022)fig. 6estimated on random steps §4.3
Random steps for estimates10K§4.3
Open-source temperature0.1app. Eserved via together.ai
Multiplication: decomposition depth5 (fixed)fig. 12 app. Fk varies; the paper does not state its values

Models and prices used tab. 1:

Model# ParamsEndpointInput USD/MTokOutput USD/MTok
Qwen-3235BQwen/Qwen3-235B-A22B-Instruct-2507-tput0.20.6
DeepSeek-v3.1671Bdeepseek-ai/DeepSeek-V30.61.7
Kimi-K21Tmoonshotai/Kimi-K2-Instruct1.03.0
GPT-OSS-20B20BOpenAI/gpt-oss-20B0.050.2
Llama-3.2-3B3.2Bmeta-llama/Llama-3.2-3B-Instruct-Turbo0.060.06

Results

Author-reported. Setup: Towers of Hanoi, 20 disks, gpt-4.1-mini, k=3, red flags §4.4. The authors claim it is the first system to finish a task of more than a million steps without an error §4.4 [abstract].

SettingMetricValueSource
20-disk run, gpt-4.1-mini, k=3, 750 tokens, red flagsMoves completed with zero errorsAll 2^20-1 = 1,048,575 moves; the authors state the problem was solved with no errors§4.4
Same runMost votes needed for one step18 votes, for step 10241, which was still decided correctlyapp. D fig. 11
Same runUndecided steps over sampling roundsFalls exponentially after the first k=3 rounds; plotted onlyfig. 8
Red-flag analysis, 2048 tokensError rate past about 700 output tokensAbout 90% correct per step; about 1 in 1000 for shorter replies§4.5 fig. 9
Red-flag analysisCollisions (two first votes both wrong)Lower with the strict parser than with the repairing one; plotted only§4.5 fig. 9
Projected cost, gpt-4.1-mini (T=0.1), t=0.95Expected costUSD 3.5K, k_min=3, 538 output tokensfig. 6

Single-step estimates, Towers of Hanoi, 20 disks fig. 6b. Error rate 1-p, estimated k_min and projected cost at t=0.95 fig. 6:

ModelUSD/MMean output tokens1-pk_minE[cost] (USD)
gpt-4.1-nano0.48420.35712941.9K
gpt-4.1-mini (T=1.0)1.65800.004044.9K
gpt-4.1-mini (T=0.1)1.65380.002233.5K
o3-mini (low)4.45350.001839.4K
haiku-4.55.05880.18391271.2K
llama-3.2-3B0.064341.0--
gpt-oss-20B0.211040.035861.7K
qwen-30.64490.23421511.5K
deepseek-v3.11.710040.0569614.6K
kimi-k23.09250.0393622.9K

The error rate stays flat as the number of disks grows fig. 6a. On 10K random steps, two separate low-temperature runs of gpt-4.1-mini found no step that both runs got wrong, which the authors read as decorrelated errors §4.3.

Multiplication (appendix). Using gpt-4.1-mini for all agents with decomposition depth 5, the system reaches a perfect solve rate on 5x5 multiplication and the t=0.95 target on 6x6, as k grows fig. 12 app. F.

Paper vs code

The official code is cognizant-ai-lab/neuro-san-benchmarking, Apache-2.0 LICENSE.txt. The owner is the authors' lab (the paper's authors are Cognizant AI Lab). The paper links it for the multiplication results app. F, and its README links the paper back README.md. I read the default branch at commit 146a144 (shallow clone). The Towers of Hanoi code is in maker_playground/. The 20-disk run is not in the repository. Searching for a separate Hanoi repository turned up nothing: GitHub repository searches for "MAKER", "massively decomposed agentic processes", and "hanoi" within the org all returned no matches. Code search needs authentication, so code inside other repositories was not searched. Two third-party hits (mpesce/MDAP, EasyCodie/Veridict) were excluded.

Discrepancies:

  • Vote key. The text says exact matches between "actions" are required §3.2. Algorithms 2 and 3 return and count (action, next state) pairs alg. 2 alg. 3, and so does the notebook hanoi.ipynb. Two samples with the same move but different next states do not add to the same vote.
  • Temperature schedule. The paper uses temperature 0 for the first sample of the full run and 0.1 afterwards §4.4. The notebook uses 0.1 for every sample hanoi.ipynb. The notebook is a 4-disk example with k=2 and 15 steps hanoi.ipynb; it is not the 20-disk configuration.
  • Retry caps. The paper gives no cap on samples or votes. The notebook caps both at 10 hanoi.ipynb [code: maker_playground/hanoi.ipynb#L151] hanoi.ipynb. Step 10241 took 18 votes app. D, which would raise an error at that cap.
  • Sequential, not parallel. The paper says at least three samples per step were drawn in parallel §4.4. The notebook draws them one after another. Its own comment says the large run needs a parallelization "not included here" hanoi.ipynb.
  • Parser return type. The paper's listing returns lists app. C. The repository's validators return tuples, which can serve as dictionary keys parsers.py parsers.py parsers.py. The notebook passes n_disks to the parser, whose default is 20 parsers.py hanoi.ipynb.
  • Prompts. The prompt wording matches the paper's appendix on visual comparison; I did not diff it character by character prompts.py app. C.
  • Multiplication code. The paper says voting continues until a candidate reaches k, "else argmax", without giving a cap app. F, alg. 4. The linear reasoner caps votes at 2k-1 and then takes the argmax linear_multiagent_reasoner.py [code: decomposer/linear_multiagent_reasoner.py#L256-L273]. The default WINNING_VOTE_COUNT is 2 in multiagent_reasoner.py [code: decomposer/multiagent_reasoner.py#L41-L42] and hard-coded 8 in the linear file linear_multiagent_reasoner.py. The README says the appendix results come from commit a7a22f8 with WINNING_VOTE_COUNT=10 and MAX_DEPTH=5 README.md. I did not check out a7a22f8, so the code I read may not produce those results.

Pitfalls

  • The 20-disk run cannot be reproduced from the repository. Only the notebook for 4 disks is provided. Implementers must write the parallel sampler and the cost bookkeeping themselves.
  • Temperature for "the first step" is ambiguous. The paper's wording could mean the first sample of each step or the first step of the task §4.4. The notebook uses 0.1 throughout.
  • Retry caps can silently cap votes. The notebook raises an error after 10 votes or 10 samples per vote hanoi.ipynb. A step like 10241, which needed 18 votes, would stop the run there app. D.
  • The parser takes the last match of each field. move and next_state are matched separately, so they may come from different lines of the reply. If the model repeats an old move, the last one is used app. C.
  • Probability estimates use a different setup from the full run. The single-step error rates come from runs with 2048 output tokens and the repairing parser, with no red flags §4.2. The full run used a 750-token cap and red flags §4.4. The projected costs assume the first setup §4.3.
  • Projected costs in the table cannot be reproduced from its columns. The table gives one price per token fig. 6. The paper's cost formula also uses input tokens §4.3, but no input-token count is given. My own check, mean tokens times price times k_min times s over (2p-1) for the T=0.1 row, gives about USD 2.7K. The printed value is USD 3.5K. Treat the table as estimates, not exact costs.
  • Target inconsistency. The scaling figure caption uses a 0.9 solution probability fig. 4. The cost table uses t=0.95 fig. 6. The full run's target is not stated.
  • Correlated errors are reduced, not removed. A few steps needed far more votes than others, and the authors call this an open problem §5 app. D. Their i.i.d. analysis §3.2 assumes errors are independent across steps.
  • The k_min result needs p > 0.5. The formula's sign depends on p > 0.5, and the derivation uses a single worst-case alternative §3.2 app. B.
  • Red-flag costs are not separated. Discarded samples add to cost eq. 19. The paper gives no actual cost of the 20-disk run §4.4.
  • Overlong replies are cut off. A reply cut off at the 750-token cap has no complete next state, so it fails the parser. This follows from the parser listing app. C; the paper does not state it.
  • Single run. The full result is one run on one puzzle with one model. No variance across runs is reported §4.4.
  • Asymptotics assume constant p, c and t. The Theta(s ln s) cost holds only when these are held fixed §3.2. Choosing the model by c/p matters more than the asymptotic form §3.2.
  • Plot-only numbers. The collision counts and the undecided-step curves are given only in figures fig. 8 fig. 9. Do not quote exact values from the text.

Lineage

  • Builds on: Towers of Hanoi as an LLM benchmark and its prompt and state format, from "The illusion of thinking: Understanding the strengths and limitations of reasoning models via the lens of problem complexity" (Shojaee et al., 2025) §2.3 app. C. The paper's focus on execution alone, with the strategy given, comes from "The Illusion of Diminishing Returns: Measuring Long Horizon Execution in LLMs" (Sinha et al., 2025) §2.1 §4.1.
  • Builds on (voting): "Self-Consistency Improves Chain of Thought Reasoning in Language Models" (Wang et al., 2022) §2.2. MAKER applies voting per step instead of per complete answer, and uses a race rule instead of a majority §2.2 §3.2.
  • Builds on (cost analysis): "Position: Scaling LLM Agents Requires Asymptotic Analysis with LLM Primitives" (Meyerson et al., ICML position track) §3.2.
  • Compared against: single-agent runs without decomposition, which the paper models through eq. 4 and which fail after five or six disks §2.3.
  • Superseded by: not known.

Source and license

Adapted from “Solving a Million-Step LLM Task with Zero Errors” by Elliot Meyerson, Giuseppe Paolo, Roberto Dailey, Hormoz Shahrzad, Olivier Francon, Conor F. Hayes, Xin Qiu, Babak Hodjat, Risto Miikkulainen (arXiv:2511.09030), used under CC BY 4.0. Changes: condensed and restructured for implementation, with tables, equations and algorithms taken from the paper and its code, each cited to its source. Not affiliated with or endorsed by the authors. Code citations refer to https://github.com/cognizant-ai-lab/neuro-san-benchmarking at commit 146a1443c983 (Apache-2.0). Any quoted code is shown under that license.