Solving a Million-Step LLM Task with Zero Errors
Authors: Elliot Meyerson, Giuseppe Paolo, Roberto Dailey, Hormoz Shahrzad, Olivier Francon, Conor F. Hayes, Xin Qiu, Babak Hodjat, Risto Miikkulainen (Cognizant AI Lab / UT Austin) Source: arXiv:2511.09030 (Nov 2025) (Notice) | Pages: ~29 | Chapters: 7 | Generated: 2026-08-26
How to Use This Skill
- Without arguments — load core frameworks below for reference
- With a topic — ask about
voting,red-flagging,cost scaling,decomposition, or another indexed topic; I find and read the relevant chapter - With a chapter — ask for
ch03; I load that specific chapter - Browse — ask "what chapters do you have?" to see the full index
When you ask about a topic not covered in Core Frameworks below, I will read the relevant chapter file before answering.
Core Frameworks & Mental Models
The problem: LLMs have a persistent per-step error rate. A 1%-per-step error rate is expected to fail by step ~100. Standard benchmarks (independent examples, averaged accuracy) hide this — they don't expose what happens once you chain thousands or millions of dependent steps. This paper solves a task requiring over one million dependent LLM steps with zero errors, and argues the fix is architectural, not "wait for a smarter model."
MDAP (Massively Decomposed Agentic Process) — the general paradigm: decompose a task into the smallest possible subtasks, then apply subtask-level error correction. MAKER is this paper's concrete implementation: Maximal Agentic decomposition + first-to-ahead-by-K Error correction + Red-flagging.
1. Maximal Agentic Decomposition (MAD) — set subtask size m=1 (one action per LLM call).
Each agent gets only (current state, fixed strategy) — never the accumulated history of past
actions. This avoids the reliability degradation single agents suffer as their own context
grows, and lets you use small, cheap, non-reasoning models. Use X when Y: use MAD whenever a
task decomposes into a chain/recursion of minimal, independently-checkable actions.
2. First-to-ahead-by-k voting — resample a subtask until one candidate has been chosen k
more times than every other candidate. Grounded in the Sequential Probability Ratio Test and
the gambler's-ruin problem. Critically, k_min (the smallest k hitting a target success
probability) grows only Θ(ln s) — logarithmically in total step count s.
3. Red-flagging — discard (don't repair) any response whose structure signals confusion: overlong output, or output that fails a strict format parser. Its main benefit is suppressing correlated errors (independent votes colliding on the same wrong answer), not just raising average per-step success rate.
The scaling-law punchline (the single most important equation): total expected cost is
Θ(p^-m · c · s · ln s) — exponential in subtask size m, but only log-linear in
total step count s. Corollary: decompose maximally (small m); don't fear long tasks (large
s). Bundling steps "for efficiency" is the single biggest cost mistake this framework warns
against.
Model/cost selection rule: rank candidate models by c/p (cost per token ÷ per-step
success rate), not by raw price or "reasoning" reputation. Calibrate p on a small, cheap,
ground-truth-known sample before committing to a large-scale run. In this paper's
experiments, small non-reasoning models matched or beat reasoning models on cost-effectiveness.
Verify voting is actually working: don't trust average error rate alone — explicitly count collisions (steps whose first two independent votes are both wrong). A low average error rate can still hide dangerous correlated failures that only collision-counting exposes.
Scope: this paper covers execution (faithfully carrying out a given strategy) — not insight (generating the strategy/plan itself). Know which one your problem needs.
Chapter Index
| # | Title | Key Frameworks |
|---|---|---|
| ch01 | Introduction — Why Million-Step Tasks Break LLMs | MDAP, MAKER, multi-agent advantage |
| ch02 | Background — Error Correction and the Hanoi Testbed | LbAs, voting/ensembling, decomposition granularity |
| ch03 | Methods — MAD, Voting, Red-Flagging | MAD, first-to-ahead-by-k voting, red-flagging, cost/scaling equations |
| ch04 | Experiments — The 20-Disk Zero-Error Run | Calibrate-then-scale, model/cost selection, convergence behavior |
| ch05 | Red-Flagging Impact, Discussion, Future Work | Collision counting, insight-vs-execution, microservices analogy, safety |
| ch06 | Appendix A/B — k_min Derivation | Full derivation of k_min = Θ(ln s) |
| ch07 | Appendix C/D — Prompts, Parsers, Samples | Reusable prompt template, repairing vs. red-flagging parsers |
Topic Index
- Calibrate-then-scale workflow → ch04
- Collision counting / correlated errors → ch05
- Cost scaling laws (Θ(s ln s), Θ(p^-m)) → ch03, ch04, ch06
- Decomposition granularity (m) → ch02, ch03
- First-to-ahead-by-k voting → ch03, ch06
- Insight vs. execution → ch05
- k_min derivation → ch03, ch06
- MAD (Maximal Agentic Decomposition) → ch01, ch03
- MAKER (the implementation) → ch01, ch03, ch04
- MDAP (the general framework) → ch01
- Microservices analogy → ch05
- Model selection / cost projection → ch04
- Multi-agent advantage → ch01
- Parsers (repairing vs. red-flagging) → ch03, ch07
- Prompt template (Towers of Hanoi agent) → ch07
- Red-flagging → ch03, ch05, ch07
- Safety implications of decomposition → ch05
- Towers of Hanoi benchmark → ch02, ch04
- Voting theory (SPRT, gambler's ruin) → ch02, ch03
Supporting Files
- glossary.md — all key terms with definitions
- patterns.md — MAD, voting, red-flagging, calibrate-then-scale, collision counting
- cheatsheet.md — decision rules, thresholds, model-selection matrix
Scope & Limits
This skill covers this single paper's content only (arXiv:2511.09030, v1, Nov 2025). It addresses execution of long-horizon agentic tasks, not open-ended plan/strategy generation ("insight"). Numeric thresholds cited (e.g. the ~700-token red-flagging cutoff) are specific to this paper's Towers-of-Hanoi setup and prompt design — re-derive them empirically for any other domain rather than reusing them as universal constants. For applying these ideas to your own codebase or agent framework, combine with project-specific tools; for topics beyond this paper, ask directly.
