Engineering Large-Scale Multi-Agent Systems: Task Decomposition, Deterministic Verification, and Cost Governance

1. From Single-Shot Q&A to Agent Cluster Collaboration

For the past two years, most LLM usage has stayed in a “one question, one answer” pattern: developers paste in a code snippet or a log file, and the model returns an explanation or a patch. The ceiling of this pattern is clear — limited context window, limited task duration, limited single-point reasoning capacity.

Some recent public demonstrations show a different shape: clusters of hundreds or even thousands of agents autonomously advancing a complex goal over a time scale of tens of hours to several days, with almost no step-by-step human intervention. The value of such systems is not that “the model got smarter.” It is that long-horizon, decomposable, verifiable engineering work has shifted from human scheduling to machine scheduling.

Understanding this matters more than memorizing the benchmark numbers of any single release.

2. Formal Proofs: Turning “Correct” into Machine-Verifiable “Correct”

2.1 What formalization means

Formalization means translating a natural-language or semi-rigorous mathematical proof into a formal language that a computer can check step by step. Such a setup has three parts:

1. A formal language and logical foundation: what counts as a well-formed expression, and what the inference rules are;
2. A proof assistant (interactive theorem prover): a kernel that performs type checking and proof checking — a proof only counts if the kernel accepts it;
3. A mathematics library: existing theorems deposited in a machine-checkable form so they can be reused later.

The significance is that correctness no longer depends on “reviewers think it’s fine.” It becomes compiles means correct. That is why formal verification has long been a hard requirement in domains where mistakes are extremely expensive: chip design, compilers, operating system kernels, cryptographic protocols.

2.2 A widely cited case

In a public demonstration, a team had a cluster of roughly a thousand agents complete the full formalization of Fermat’s Last Theorem: about 30 hours. With the same configuration swapped to the previous generation of the model, the run spent 18 hours and reached only about 26% before stalling out. For comparison, earlier comparable work relied on an undisclosed research version of a model, took about 11 days, and additionally required building a dedicated framework with researchers guiding the process throughout.

Three technical details in that case are worth a developer’s attention:

• Almost no human involvement: how to split the work, who takes which piece, and how to retry after a conflict were all decided by the agents themselves;
• No reference material: the only artifact available was an intermediate theorem list used for scoring — essentially “where the proof stands right now and which lemmas are still missing”;
• Scoring is scheduling: the list served as both a progress bar and the basis for task dispatch — whichever milestone was not yet closed got the compute.

Put differently, a task board plus a checker is the real protagonist of this kind of system.

3. The Operating System Case: Another Shape of Long-Horizon Autonomous Engineering

A second demonstration is more explicitly engineering-flavored: an engineer had a model build an operating system starting from an empty folder. It orchestrated more than 1,000 sub-agents, ran continuously for 8 days, and ultimately produced a system that boots on a laptop — including device drivers, file storage, window management, a login screen, and an installer, with an AI assistant integrated.

The genuinely hard part here is not “writing code.” It is four things:

1. State persistence: an 8-day run far exceeds a single session, so progress, decisions, and failure reasons must be written to external storage;
2. Dependency management: drivers depend on kernel interfaces, the file system depends on the block device layer — get the order wrong and everything has to be redone;
3. Context isolation: 1,000+ subtasks cannot share one context, so necessary information has to be passed along via “summaries + retrieval + a task board”;
4. Per-phase acceptance: every completed layer needs an executable verification (it compiles, it boots, it mounts), otherwise errors amplify exponentially.

4. A Replicable Engineering Methodology

The following section abstracts these cases into an architecture that can actually ship.

4.1 Task decomposition: draw the DAG before discussing parallelism

The first-principles question for any large-scale agent system is dependencies, not concurrency. Start by decomposing the goal into a task graph with explicit dependencies:

{
  "task_id": "t-0431",
  "title": "Add boundary cases for the paginator",
  "depends_on": ["t-0402", "t-0409"],
  "status": "pending",
  "acceptance": [
    "All unit tests pass",
    "New cases cover both out-of-range scenarios: offset < 0 and offset > total"
  ],
  "budget": { "max_turns": 40, "max_tokens": 120000 },
  "artifacts": ["docs/design.md", "src/pagination/mod.test.ts"]
}

The critical fields are depends_on and acceptance: the former determines scheduling order, the latter determines “when is it done.” A task without an executable acceptance criterion should not enter the queue at all.

4.2 The execution loop: sandbox isolation plus verifier judgment

TASK_BOARD = load_board()
while TASK_BOARD.has_runnable():
    batch = TASK_BOARD.take_runnable(limit=CONCURRENCY)
    for task in batch:
        sandbox = Sandbox(image=task.image, timeout_s=task.timeout)
        try:
            result = agent.run(task, tools=["read", "edit", "shell", "test"])
            if verifier.check(result, task.acceptance):
                TASK_BOARD.complete(task, diff=result.diff)
            else:
                TASK_BOARD.requeue(task, reason=verifier.reason,
                                   attempts=task.attempts + 1)
        finally:
            sandbox.destroy()   # must be destroyed to avoid state pollution and resource leaks

Three engineering points:

• Execution must be isolated: each task runs in its own sandbox (container or ephemeral function instance), so a failure can be discarded and replayed;
• Completion is decided by deterministic tools: compile, unit tests, static analysis, a formal kernel check — not model self-assessment;
• Retries need a budget cap: max_turns, max_tokens, and a timeout are all mandatory, otherwise a single task can consume the whole cluster’s compute.

4.3 Carrying the scheduling layer with general-purpose cloud components

An agent cluster is fundamentally a distributed system that is high-concurrency, long-running, and heavily observable. You do not have to build the entire infrastructure stack yourself; you can reuse general-purpose capabilities available on cloud platforms:

Requirement	General cloud component	Role
Task dispatch and decoupling	Message queue	Peak smoothing, redelivery, dead-letter fallback
Code and artifact hosting	Object storage	Intermediate files, diffs, run logs
Execution isolation	Container platform / function compute	Start and stop sandboxes on demand, elastic by nature
Progress and state	Database / cache	Task board, locks, idempotency keys
Observability	Logging service + monitoring and alerting	Failure attribution, cost dashboards, circuit breaking

On Baidu AI Cloud, the combination of “message queue + object storage + container platform + logging service and monitoring/alerting” is a common way to land agent orchestration, and it fits scenarios that need long batch runs with highly elastic compute demand particularly well.

4.4 Context and memory: don’t let the cluster “forget” or “blow up”

Long-horizon tasks usually fail not because the model can’t do the work, but because critical information is lost or the context balloons. Four practical strategies:

1. Structured summarization: after each milestone, compress into a four-part note — goal, done, conclusion, open questions;
2. Retrieval on demand: raw logs and source code do not go directly into context; fetch them through retrieval when needed;
3. Cache reuse: reuse cached inference for requests sharing the same prefix, which both speeds things up and cuts cost;
4. Context budget: set a hard ceiling per subtask and force summarization once exceeded, so a single task cannot crowd out the global budget.

4.5 Model routing: tier capability to the task

Not every step needs the strongest model. A common pattern is three-tier routing:

MODEL_ROUTES = {
    "plan":      "strong_reasoning",   # decomposition, key lemma proofs, architecture decisions
    "implement": "balanced_fast",      # routine coding, filling in tests
    "verify":    "deterministic_tool", # compile/test/formal kernel -- no model involved
}

The most important principle here: hand verification to deterministic tools whenever possible. Model self-scoring has an inherent optimism bias — using it for acceptance is like letting the candidate grade their own exam.

5. Performance, Latency, and Cost: Is the Switch Worth It?

Improvements cited in public cases usually concentrate on three dimensions: capability (benchmark scores), speed (output throughput), and price (cost per call). For an individual developer, these three should not be viewed in isolation — they have to be converted into cost per unit of useful output:

effective cost = (input token cost + output token cost + retry overhead) / number of tasks passing acceptance

A model with a low unit price but a high rework rate can end up costing more in practice. Build a small regression set of your own to quantify it:

Evaluation dimension	Concrete metric	Collection method
Coding capability	Unit test pass rate, injected-defect detection rate	Sampling tasks from private repositories
Long-task capability	Multi-turn task completion rate, average turns	Sandbox replay
Reasoning and formalization	Proof compilation pass rate	Proof assistant kernel
Engineering efficiency	Output tokens/s, time to first token	Load-testing scripts
Stability	Timeout rate, malformed-output rate, retry rate	Monitoring and alerting

Without a regression run on your own business data, no benchmark score can serve directly as a migration basis.

6. Quota and Entitlement Governance: From Pay-Per-Call to Subscription Quotas with Reset Mechanisms

The flip side of stronger next-generation models is rising resource governance complexity. Current mainstream product shapes fall into roughly two categories:

• Pay-as-you-go: suited to bursty, low-volume, or experimental usage;
• Subscription plus weekly quota: suited to steady daily usage, typically tiered by seat, often with a “quota reset” type mechanism (for example, a number of dedicated resets granted based on subscription duration, or the ability to allocate part of the weekly quota to specific models, with a defined expiry).

Whichever shape you use, governance has to come first on the team side:

1. Quota tiering: keep individual developer quotas, a shared team pool, and a production-dedicated pool separate, so debugging tasks cannot crowd out production;
2. Usage attribution: tag by project or service so cost can be traced to a specific owner;
3. Threshold circuit breaking: set daily/weekly usage thresholds and alerts to prevent runaway loops (an agent stuck in a loop is the most common cost black hole);
4. Transparent reset policy: be explicit about what a reset covers (all quota or only certain models), its validity period, and how resets stack, so you don’t assume you have capacity when you’re actually over.

Note that quota rules differ substantially between providers and do get adjusted. For the exact rules, always refer to the provider’s official documentation rather than copying someone else’s experience values into your capacity planning.

7. Risk Boundaries and Deployment Recommendations

• Formalization ≠ business correctness: formal verification checks whether a model or algorithm satisfies a specification. If the specification itself is wrong, no proof, however elegant, helps. The prerequisite is still the quality of requirements and specs.
• Long-horizon drift: after running for days, agents may drift away from the original goal. The countermeasure is fixed milestone acceptance plus periodic human spot checks — not fully hands-off execution.
• Licensing and compliance: the large volume of auto-generated code raises open-source licensing, cross-border data transfer, and security review questions; these belong in pipeline gates.
• Best-fit scenarios first: large-scale refactoring and migration, test and case backfill, formal verification of mathematical and algorithmic work, long-tail feature implementation.
• Not suitable for full autonomy: any decision point touching money, production data changes, or external release must keep a human approval step.

8. Conclusion

Thousand-agent collaboration completing a formal proof and building an operating system yields a conclusion that is more useful to developers than “a model got stronger again” — three reusable engineering principles:

1. Decomposable: the goal must break down into a dependency-bearing task graph with acceptance criteria;
2. Verifiable: correctness judgment goes to deterministic tools — compilers, tests, formal kernels;
3. Governable: compute, context, and cost each need hard ceilings and an observable dashboard.

Model capabilities will keep iterating; these three principles stay stable. Turn them into platform capabilities, and every model upgrade converts directly into business value.