Multi-Agent Formal Verification: Decomposition, Validation, and Cost Optimization Practices

1. Complex Reasoning Is Moving from One-Shot Generation to System Engineering

In intelligent programming, complex question answering, rule validation, research assistance, and similar scenarios, the shape of the task has clearly changed:

1. Long dependency chains: The conclusion of one step affects later judgments, and errors can amplify along the chain.
2. Multiple constraints: The output must not only appear reasonable, but also satisfy format rules, business rules, boundary conditions, and operational standards.
3. High verifiability requirements: When code, mathematics, compliance, or data validation is involved, the result must be testable, checkable, or provable.
4. Need for multi-path exploration: Complex problems often do not have a single obvious solution.
5. High failure cost: Human rework, production incidents, and wrong decisions are far more expensive than the cost of one inference call.

This means that a single model, a single round, or a single execution chain will eventually hit a bottleneck. A multi-agent system does not simply provide “a stronger one-shot generation.” It provides a closed loop of task decomposition, parallel validation, quality evaluation, and cost optimization. Formal verification determines whether that closed loop is trustworthy.

This article provides practical role divisions, metric definitions, parameter rules, and a governance checklist that can be applied directly.

2. Multi-Agent Roles, Applicability Boundaries, and Failure Conditions

Role	Input	Output	Failure signal
Task planner	Goal + constraints	Subtask list + decision conditions	Subtasks cannot be written as decidable conditions
Solution generator	Subtask	Candidate solutions, code, or proof ideas	All candidates violate hard constraints
Verifier	Candidate + rules/tests	Pass/fail + failed rule ID	Rule set has incomplete coverage, causing missed detections
Critic and repairer	Failure information	Repair suggestions + next-round solution	Same failure cause repeats across multiple rounds
Aggregator	Multiple passing candidates	Final output	Candidate quality is close, but cost is high

Applicability boundaries are important. Multi-agent systems deliver the most value when the task can be split into mutually independent subproblems and each subproblem has an objective validation standard.

When a task is strongly coupled, cannot be split into independently verifiable units, or the verifier is not stronger than the model itself, a multi-agent system becomes “more cost for the same wrong answer.” In that case, teams should fall back to a single-agent workflow plus manual spot checks.

The verifier’s own false positives and false negatives must also be measured:

• Build a human-labeled dataset to estimate the verifier’s false-positive rate, where it passes incorrect results, and false-negative rate, where it blocks correct results.
• Construct a negative-sample set, meaning intentionally incorrect answers, and require a target interception rate before going live.
• When the verifier conflicts with human judgment, send the case to an arbitration queue: if the verifier fails a result but humans pass it, the rule set is too strict; if the verifier passes a result but humans fail it, the rule set is too loose.
• Manage verification rules and model policies as separate versioned artifacts. Every rule change should trigger regression testing.

3. The Boundary Between Formal Verification and Conventional Validation

This is one of the most commonly misunderstood points: unit tests, rule-engine checks, and syntax or structure checks are executable validation, not strict formal proof.

• Executable validation uses engineering rules as the decision standard. It can only cover cases encoded in those rules. If the encoding is incomplete, missed detections occur.
• Semi-formal validation includes type systems, schema constraints, assertions, and property-based tests. These provide stronger guarantees, but coverage gaps still exist.
• Strict formal verification requires the task itself to be formalizable as a specification plus invariants, and the relevant logic fragment must be decidable, such as SMT solving or theorem proving.

Some scenarios are inherently undecidable. These include arbitrary program equivalence, the general halting problem, code containing undefined behavior, and open-domain natural-language compliance judgment. Complete proofs are not available in these cases. The only practical option is sampling-based testing with confidence intervals.

In these scenarios, claiming “formally verified” is incorrect. The correct practice is to label the validation method and coverage scope.

4. Evaluation Metrics: Define the Measurement First, Then Compare Numbers

Assume a pilot evaluation set of 200 cases, including 40 boundary cases, accounting for 20%, plus additional negative samples.

Task completion quality

• Full pass rate = number of tasks satisfying all constraints ÷ total number of tasks
• First-pass rate = number of tasks passing validation on the first generated round ÷ total number of tasks
• Post-repair pass rate = number of tasks eventually passing after multiple repair rounds ÷ total number of tasks
• Partial completion rate = number of achieved milestones ÷ total planned milestones

The judgment criteria must be documented: who judges the result, with automated validation as the default and dual human annotation for ambiguous cases, how conflicts are arbitrated, how many samples are used, and what percentage are boundary cases.

If boundary cases account for less than 15%, the metrics will be systematically optimistic. If they exceed 25%, they may no longer represent real traffic. Pass rates measured on very small samples, such as 20 cases, fluctuate significantly and should not be used as a basis for version comparison.

Inference efficiency

• Average time per task = total time ÷ number of successful tasks
• Parallel search scale = number of candidate solutions × number of validation rounds
• Average number of repair rounds = total repair rounds ÷ number of tasks requiring repair

Cost

• Average invocation cost per task = total cost ÷ total number of tasks
• Average cost per successful result = total cost ÷ number of successful tasks. This is the primary metric for cross-comparison.
• Cache hit rate = number of requests hitting cache ÷ total number of requests
• Cost share of ineffective exploration = cost consumed by early-stopped or abandoned branches ÷ total cost

Arithmetic example: Strategy A runs 200 tasks, costs CNY 400, and succeeds on 160 tasks, giving a cost per successful result of CNY 2.5. Strategy B costs CNY 300, succeeds on 120 tasks, and also has a cost per successful result of CNY 2.5. Strategy B has a lower total cost but a worse completion rate. If teams only look at total cost, they may choose the wrong strategy. These numbers are used only to illustrate the formulas and do not represent the performance or pricing of any real product.

Stability

The following should be tracked separately:

• Consistency rate when the same task is executed five times
• Failure rate on complex inputs
• Susceptibility rate to distractor items
• Failure rate on ultra-long context inputs

5. Five Practical Rules for Cost Control

1. Tiered model scheduling

• Lightweight models: formatting, extraction, classification, syntax checking
• General reasoning models: medium-complexity rewriting, unit test generation
• Strong-capability models: planning, proof generation, complex code generation

Routing example: the planner provides a difficulty score. If the score is below 0.4, use a lightweight model. If it is between 0.4 and 0.7, use a general model. If it is above 0.7, use a strong model. The share of strong-model calls should have an upper limit, for example no more than 20%. If the limit is exceeded, requests should enter a queue rather than silently degrade.

2. Adaptive parallelism

• Lower bound: 1
• Upper bound: min(8, floor(single-task budget ÷ cost per call))
• Simple tasks: P=1
• Medium-complexity tasks: P=2~3
• High-complexity tasks: P=4~8

If all branches fail validation for two consecutive rounds, halve the parallelism and return to the planner for replanning. When the number of candidates reaches a threshold, enable the aggregator to choose the best candidate. Otherwise, directly take the first candidate that passes validation.

3. Early stopping and verification-first

• Hard early stop: After each candidate is generated, immediately check syntax, structure, and hard rule constraints. If it fails, discard it immediately.
• Count-based early stop: Stop the search once K candidates have passed validation, for example K=1~2.
• Budget-based early stop: If any of the token limit, call-count limit, or wall-clock-time limit is exceeded, trigger a circuit breaker, output a degraded result, and mark it as “not fully validated.”

4. Caching and reuse

The cache key should include at least:

• Task template ID
• Normalized input hash
• Rule-set version
• Model version
• Prompt version
• Temperature parameter

If the rule set or prompt changes, the key becomes invalid as a whole. This prevents conclusions generated under old rules from being used to answer new questions. Historically successful solutions can be distilled into parameterized templates. When a template is hit, planning and parallel execution can be skipped.

5. Quotas and staged rollout

Allocate daily and weekly quotas by user tier. For new capabilities, start with a 5% gray release and observe full pass rate, cost per successful result, and failure-reason distribution. Tasks involving funds, permissions, or compliance must require manual confirmation.

6. Production Architecture and Security Audit Requirements

The control plane is responsible for task prioritization, model routing, timeout and retry degradation, and isolation across users, projects, and resources.

The execution plane includes task queues, containerized isolated execution, a tool-invocation layer covering testing, retrieval, validation, and computation, and a state manager that records intermediate results at each step and supports rollback and resumption.

The data plane includes object storage, message queues, a task-state database, and version management for prompts and rule sets.

The observability plane includes logs, monitoring alerts, and full-chain tracing.

In addition, security and audit requirements must be completed.

Permission matrix example

Role	Read input	Read intermediate artifacts	Tool permissions	Modify rule set	Trigger review
Anonymous/trial user	Only own session	No	Restricted toolset	No	No
Project member	Within project	Yes	Standard toolset	No	No
Project administrator	Within project	Yes	High-risk tools require approval	No	Yes
Platform operations	Desensitized	Yes	Full access with complete audit trail	Yes	Yes

Data desensitization rules

Fields such as national ID numbers, phone numbers, bank card numbers, keys, and tokens must be replaced with irreversible placeholders before being written to logs. Only the hash and prefix length should be retained.

Prompts and responses should not retain plaintext by default. Only desensitized summaries should be stored. Cross-tenant data must not enter the same cache-key space.

Mandatory log fields

Each log entry should include:

• task_id
• trace_id
• Desensitized user and project IDs
• Model ID and version
• Prompt version
• Rule-set version
• Parallelism degree
• Token count and latency for each round
• Validation result and failed rule ID
• Final decision source, automatic or human
• Estimated cost
• Error code

Retention and circuit-breaker thresholds example

Audit logs for critical tasks can be retained for 180 days, while ordinary tasks can be retained for 30 days. Version records for rule sets and evaluation sets should also be retained.

For a single task, the retry limit can be set to 3 times, with a wall-clock limit of 10 minutes. If queue backlog exceeds a threshold, or if the failure rate exceeds 20% over five minutes, the system should degrade to single-agent mode.

Manual review trigger conditions

Manual review should be triggered when:

• The verifier conflicts with human labeling
• The task involves funds, compliance, or permission changes
• Confidence is below a threshold
• Two consecutive repair rounds still fail
• A sensitive-data rule is hit

7. End-to-End Flows for Four Typical Scenarios

Intelligent programming and automated testing

Input: requirement description + interface contract.

Decompose into implementation, unit tests, and boundary cases.

The verifier includes compilation, unit tests, linting, dependency checks, and license scans.

If validation fails, feed the error stack back to the repairer. The repairer may modify only the implementation, not the tests, to prevent the model from passing tests by cheating.

Set a retry limit of 3. If the limit is exceeded, output a partial implementation plus a failure list.

Metrics: test pass rate, first-pass rate, average repair rounds, and cost per successful result.

Data validation and business rule review

Input: structured data + natural-language rules.

Decompose the task into executable validators for each rule. High-risk rules require human confirmation.

The verifier is a rule engine.

When validation fails, do not modify the data. Output the violating fields, rule ID, and location.

Set a retry limit of 1, and only allow reparsing of the rules themselves.

Metrics: rule coverage rate, false-positive rate, false-negative rate, and audit-trail completeness rate.

Research assistance and mathematical reasoning

Input: proposition + known premises.

Decompose into goal decomposition and lemma generation.

The verifier is a proof checker operating on a decidable fragment. Key steps should be manually reviewed. If the task is undecidable, explicitly mark it as “not formally verified.”

Run K proof paths in parallel. If all paths fail, return the lemmas that have already been established.

Metrics: proof completeness rate, path hit rate, and human intervention rate.

Enterprise knowledge processing and complex question answering

Input: question + knowledge source.

Decompose into retrieval, cross-validation, and conflict detection.

The verifier checks whether provenance is traceable. Every conclusion must include a source ID. Permission checks are also required.

If evidence is insufficient, rephrase the answer as “insufficient evidence.” Fabrication is prohibited.

Metrics: citation completeness rate, conflict identification rate, and number of unauthorized outputs, which must be 0.

8. Risks and Governance

Error amplification mainly comes from the planning stage. Therefore, planner output must be checked by a verifier to confirm that steps are executable and constraints are complete before it is sent downstream.

Pseudo-validation comes from a verifier that is too permissive. It should be mitigated by periodically testing the verifier against a negative-sample set.

Data leakage can be controlled through a permission matrix, field-level desensitization, and cache isolation.

Unexplainable decisions can be investigated through full-chain tracing using trace_id to locate the model, prompt, and rule-set versions involved.

Resource abuse can be controlled through quotas, budget limits, and circuit-breaker thresholds.

High-risk tasks should retain manual review, and the verification rules themselves should also be tested.

9. Rollout Roadmap and Acceptance Criteria for Each Step

1. Define task boundaries
   Acceptance criterion: The task goal can be written as a decidable condition. Tasks that cannot be decided should not enter the pilot.

2. Build the evaluation set
   Acceptance criterion: 150 to 200 cases, with boundary cases accounting for 15% to 25%, including negative samples, and dual human annotation consistency meeting the required threshold.

3. Run a limited gray release, up to 5%
   Acceptance criterion: Obtain baseline data for full pass rate, first-pass rate, cost per successful result, and failure-task share.

4. Optimize the strategy
   Acceptance criterion: First fix the failure type with the highest share, then reduce average repair rounds and cost per successful result.

5. Complete platform capabilities
   Acceptance criterion: All six capabilities must be online: permission matrix, desensitization, log fields, retention period, circuit-breaker thresholds, and manual review.

6. Expand to new scenarios
   Acceptance criterion: The completion rate of the new scenario must not be lower than the pilot baseline, and the cost per successful result must not be higher than the baseline.

10. Conclusion: Three Things Must Be Done

1. Define validation criteria before pursuing automation.
   Without an executable verifier, a multi-agent system is just a more expensive generator.

2. Use “average cost per successful result” as the primary cost metric, not total invocation volume.
   The three rules of parallelism bounds, early stopping, and cache keys should be implemented first.

3. Make audit and security prerequisites, not afterthoughts.
   Permission matrices, desensitization, log fields, retention periods, and circuit-breaker thresholds should be in place before gray release, not added only after an incident occurs.