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.
- 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.
- 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.
- 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:
# 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# 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# 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 candidateThe 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.
# 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
| Name | Value | Where | Notes |
|---|---|---|---|
| Disks N | 20 | §4.4 | 2^20-1 = 1,048,575 steps §4.4 §2.3 |
| Model (full run) | gpt-4.1-mini, OpenAI API | §4.3 §4.4 | chosen over gpt-oss-20B because the OpenAI API was more reliable |
| Vote margin k | 3 | §4.4 | equals k_min at t=0.95 for gpt-4.1-mini fig. 6 eq. 14 |
| Target success t | 0.95 | fig. 6 | cost table; fig. 4 uses 0.9 (see Pitfalls) |
| Samples per step | at least 3 in parallel | §4.4 | "at least" because a step may need more votes |
| Temperature, full run | 0 for the first sample, 0.1 for the rest | §4.4 | "first step" is ambiguous (see Pitfalls) |
| Max output tokens, full run | 750 | §4.4 | the cap that triggers the overlong red flag |
| Max output tokens, exploratory | 2048 | §4.2 §4.5 | used for error-rate estimates and for the red-flag analysis |
| Red flags | overlong 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. 6 | estimated on random steps §4.3 |
| Random steps for estimates | 10K | §4.3 | |
| Open-source temperature | 0.1 | app. E | served via together.ai |
| Multiplication: decomposition depth | 5 (fixed) | fig. 12 app. F | k varies; the paper does not state its values |
Models and prices used tab. 1:
| Model | # Params | Endpoint | Input USD/MTok | Output USD/MTok |
|---|---|---|---|---|
| Qwen-3 | 235B | Qwen/Qwen3-235B-A22B-Instruct-2507-tput | 0.2 | 0.6 |
| DeepSeek-v3.1 | 671B | deepseek-ai/DeepSeek-V3 | 0.6 | 1.7 |
| Kimi-K2 | 1T | moonshotai/Kimi-K2-Instruct | 1.0 | 3.0 |
| GPT-OSS-20B | 20B | OpenAI/gpt-oss-20B | 0.05 | 0.2 |
| Llama-3.2-3B | 3.2B | meta-llama/Llama-3.2-3B-Instruct-Turbo | 0.06 | 0.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].
| Setting | Metric | Value | Source |
|---|---|---|---|
| 20-disk run, gpt-4.1-mini, k=3, 750 tokens, red flags | Moves completed with zero errors | All 2^20-1 = 1,048,575 moves; the authors state the problem was solved with no errors | §4.4 |
| Same run | Most votes needed for one step | 18 votes, for step 10241, which was still decided correctly | app. D fig. 11 |
| Same run | Undecided steps over sampling rounds | Falls exponentially after the first k=3 rounds; plotted only | fig. 8 |
| Red-flag analysis, 2048 tokens | Error rate past about 700 output tokens | About 90% correct per step; about 1 in 1000 for shorter replies | §4.5 fig. 9 |
| Red-flag analysis | Collisions (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.95 | Expected cost | USD 3.5K, k_min=3, 538 output tokens | fig. 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:
| Model | USD/M | Mean output tokens | 1-p | k_min | E[cost] (USD) |
|---|---|---|---|---|---|
| gpt-4.1-nano | 0.4 | 842 | 0.3571 | 29 | 41.9K |
| gpt-4.1-mini (T=1.0) | 1.6 | 580 | 0.0040 | 4 | 4.9K |
| gpt-4.1-mini (T=0.1) | 1.6 | 538 | 0.0022 | 3 | 3.5K |
| o3-mini (low) | 4.4 | 535 | 0.0018 | 3 | 9.4K |
| haiku-4.5 | 5.0 | 588 | 0.1839 | 12 | 71.2K |
| llama-3.2-3B | 0.06 | 434 | 1.0 | - | - |
| gpt-oss-20B | 0.2 | 1104 | 0.0358 | 6 | 1.7K |
| qwen-3 | 0.6 | 449 | 0.2342 | 15 | 11.5K |
| deepseek-v3.1 | 1.7 | 1004 | 0.0569 | 6 | 14.6K |
| kimi-k2 | 3.0 | 925 | 0.0393 | 6 | 22.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_disksto 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_COUNTis 2 inmultiagent_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.
moveandnext_stateare 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.