MAKER: Massively Decomposed Agentic Processes for Reliable Million-Step LLM Tasks

This post analyzes MAKER, an AI system that claims to be the first to complete a task requiring over one million LLM steps with zero errors — the 20-disk Towers of Hanoi problem (2^20 − 1 = 1,048,575 moves) — using the economical gpt-4.1-mini model rather than a frontier reasoning model.

Key points

The problem: error accumulation in long-horizon tasks

• LLMs have a persistent per-step error rate. Even a 1% per-step error makes failure essentially certain over a million sequential steps.
• State-of-the-art models typically fail benchmarks like Towers of Hanoi within a few hundred steps.
• MAKER's thesis: decouple task reliability from single-model intelligence via system architecture, rather than building a stronger monolithic model.

The MDAPs framework — three core components

1. Maximal Agentic Decomposition (MAD)

• Decomposes a task of s steps into s atomic subtasks, each handled by a dedicated micro-agent that receives the current state x_i, generates one action a_{i+1}, and yields the next state x_{i+1}.
• Minimizes each agent's cognitive load and context, enabling smaller, cheaper models.

2. First-to-ahead-by-K voting

• Multiple LLM samples produce candidate answers per subtask; a candidate wins once it leads every other candidate by k votes (a sequential-probability-ratio-test-like scheme).
• Probability of selecting the correct answer: p_sub = p^k / (p^k + (1-p)^k). Example: with p = 0.9, k=3 gives p_sub ≈ 0.973; k=5 gives ≈ 0.995.
• Overall success: p_full = [1 / (1 + ((1-p)/p)^k)]^s.

3. Red-flagging

• Pre-vote heuristic filter that discards suspicious responses: overly long outputs (threshold 750 tokens in the Hanoi experiments; error rates spike beyond ~700 tokens) and malformed outputs.
• Breaks correlated errors — experiments showed strict red-flagging parsers reduced "collision" steps (where the first two votes were both wrong) versus repair-style parsers.

Scaling laws

• Minimum voting threshold: k_min = ⌈ln((1/t^(1/s)) − 1) / ln((1−p)/p)⌉, which yields the key law k = Θ(ln s) — k grows only logarithmically with task length.
• Expected cost: E[cost] = Θ(s ln s) — log-linear growth in cost, assuming per-call cost c and success rate p (calls scale roughly as s·k/(2p−1)).

Experimental validation (20-disk Towers of Hanoi)

• Task: 1,048,575 steps; setup: gpt-4.1-mini, k=3, red-flagging at 750 max tokens.
• Result: full completion with zero errors across all steps.
• Undecided steps decreased exponentially with voting rounds, matching theory.

Comparison with conventional monolithic LLM approaches

| Aspect | MAKER (MDAPs) | Monolithic LLM | |---|---|---| | Reliability | Zero errors over 10^6 steps | Fails within hundreds of steps | | Scaling | Θ(s ln s) cost | Success decays as (p_sub)^s | | Model needs | Small, cheap models suffice | Large reasoning models, still failing |

Limitations

• Compute cost: redundant sampling makes total LLM calls far exceed s; discarded red-flagged responses are pure overhead.
• Infrastructure: high-throughput voting benefits from large-scale parallel compute (GPU clusters / elastic cloud), plus engineering for batching and scheduling.
• Applicability: requires decomposable tasks with verifiable correct answers; poorly suited to holistic, creative, or open-ended tasks with no single correct output.

Takeaway

MAKER demonstrates that architectural innovation — extreme decomposition plus statistical error correction — can deliver near-perfect reliability on tasks far beyond any single LLM, suggesting a path for high-stakes automation (supply chains, compliance, scientific workflows) and a design philosophy emphasizing trustworthy, auditable AI over raw model scale.