Cracking the Million-Step Problem with Multi-Agent AI System

LLM has a fundamental wall: reliability at scale. Even the most advanced models inevitably derail after a few hundred consecutive steps, making them unsuitable for the complex, multi-step processes that organizations and societies routinely execute.

A new paper from Cognizant AI Lab introduces MAKER (Maximal Agentic decomposition, first-to-ahead-by-K Error correction, and Red-flagging), the first system to successfully solve a task requiring over one million LLM steps with zero errors. This breakthrough suggests a radical alternative to the prevailing approach of building ever-larger, more “intelligent” base models.

The Fundamental Problem: Error Accumulation

Consider this: a 1% per-step error rate sounds impressive on traditional benchmarks. But for a task requiring a million steps, such a system is expected to fail after just 100 steps. The math is unforgiving—errors compound exponentially.

Recent experiments with the Towers of Hanoi benchmark starkly illustrated this limitation. State-of-the-art LLMs handle five or six disks reliably, but their success rate plummets to zero beyond that threshold. The problem isn’t lack of intelligence—it’s the persistence of errors over long horizons.

This matters because real-world applications—from hospital operations to supply chain management to financial processing—require executing detailed plans with extreme precision. A 1% error rate isn’t acceptable when errors can range from inconvenience to economic harm to physical danger.

The MDAP Framework: Scaling Through Decomposition

The paper introduces a counterintuitive solution: instead of relying on smarter models, break tasks into the smallest possible pieces and let focused “microagents” handle each step. This approach, called Massively Decomposed Agentic Processes (MDAPs), consists of three core components:

1. Maximal Agentic Decomposition (MAD)

Rather than having a single agent solve an entire problem, decompose it into minimal subtasks—one step per agent. This extreme modularity allows each agent to focus entirely on its tiny role, avoiding the context overload and confusion that plague monolithic approaches.

The math is revealing: while decomposition creates more potential failure points (s opportunities instead of one), it enables something crucial that single-agent approaches cannot achieve: effective error correction at each step.

2. First-to-Ahead-by-k Voting

Here’s where the magic happens. For each step, multiple agents independently solve the same subtask. The system uses a “first-to-ahead-by-k” voting process—a candidate answer must receive k more votes than any alternative before being accepted.

The theoretical analysis shows that with this approach, even if the base per-step success rate is just 90%, the probability of selecting the correct answer at each step can be pushed arbitrarily close to 100% by increasing k. The key insight: k grows only logarithmically with the number of steps, making the approach practical even at massive scale.

3. Red-Flagging: Detecting Unreliability

Not all LLM outputs are created equal. The system discards responses showing signs of confusion—particularly those that are overly long or incorrectly formatted. These “red flags” correlate strongly with incorrect reasoning.

This simple heuristic has profound effects. When an LLM produces a response that violates basic formatting requirements, it often indicates the model has been “conditioned into a strange starting point.” By discarding such responses before they enter the voting process, the system reduces both overall error rates and dangerous correlated errors.

The Million-Step Achievement

The researchers applied MAKER to solve Towers of Hanoi with 20 disks—requiring 2^20 - 1 = 1,048,575 steps—with zero errors.

Remarkably, they accomplished this using gpt-4o-mini, not a state-of-the-art reasoning model. The estimated cost was just $3,500, compared to tens of thousands of dollars for more powerful models. This efficiency emerges because each individual step is so small that relatively modest models suffice.

The system’s behavior validated the theoretical predictions. The number of undecided steps decreased exponentially with each voting round, with the vast majority of cost incurred in the first k rounds. A few pathological steps required up to 18 voting rounds, but the error correction mechanism handled them gracefully.

Scaling Laws and Cost Analysis

The paper derives formal scaling laws showing that MAKER’s expected cost grows at the same efficiency class that enabled classical computing to scale.

In contrast, systems that assign multiple steps to each agent face exponentially increasing costs. As agents handle more steps, the probability that their outputs will match exactly across multiple samples vanishes—the curse of dimensionality in action.

The formula for expected cost reveals a critical insight: before running expensive large-scale experiments, you can calibrate on a small number of steps to estimate per-step success rates, then predict the cost of the full task. This allows selecting the most cost-effective model for your specific problem.

Implications and Future Directions

Microagents as Microservices

The parallels with software architecture are striking. Just as microservices revolutionized system design through modularity, independent scaling, and fault tolerance, microagents offer similar benefits for cognitive tasks. Each agent manages its own data, can be tested in isolation, scales independently, and is designed to tolerate failures.

Safety and Superintelligence

Extreme decomposition may offer unexpected safety benefits. When each step has a clearly defined, limited purpose, agents can be more effectively sandboxed and audited. Multiple focused agents running independently reduce collusion risks. And since most work can be performed by smaller models handling tiny steps, the system avoids risks associated with more powerful models.

As the authors provocatively suggest: “LLMs today have just about all the raw intelligence needed to scaffold them into the great superintelligent skyscrapers of the coming age. MDAPs present an alternative path to realizing the benefits of superintelligence, which, compared to endlessly building bigger and smarter single-agent models, comes with substantially reduced risks to both humans and machines.“

Open Questions

The framework assumes tasks can be decomposed into sufficiently small, simple steps. How broadly does this assumption hold? Can we automate the discovery of optimal decompositions? How do we extend the approach to handle insights and creativity, not just execution?

Preliminary experiments on multi-digit multiplication show promise—the system achieved 95% success rates on 6×6 digit multiplication, a notoriously difficult task for transformers. But extending to more open-ended problems remains an active area of research.

The Takeaway

This work challenges the dominant narrative that AI progress requires ever-larger, more capable foundation models. Instead, it demonstrates that extreme decomposition combined with error correction can achieve reliable performance at unprecedented scale using relatively modest models.

The implications are profound: by “smashing intelligence into a million pieces,” we may be able to build AI systems that are not only more reliable and efficient, but also safer and more aligned with human values.

The race to AGI may not be won by building the biggest brain, but by learning to coordinate millions of small ones.

Paper: “Solving a Million-Step LLM Task with Zero Errors” by Meyerson et al., Cognizant AI Lab, November 2025

Full paper available at: arXiv:2511.09030