Multi-agent debate: protocols, update semantics, and evaluation

Separate sampling, interaction, and aggregation

Generating N candidates for a question q and selecting an answer already forms ensemble inference. Debate adds a different operation: candidates read information from one another and revise. Which candidates initialization produces, how interaction changes them, and how aggregation selects a result are three computational stages that can be replaced and measured separately. Gains from adding agents cannot automatically be attributed to communication.

x is a candidate state passed between agents. It contains an answer, atomic claims, evidence references, and unresolved issues. M contains the messages visible to this update; E contains external material or tool results. F includes the prompt, model, decoding settings, and context construction, and is generally stochastic. The equation describes an admitted update. If a call fails or its result violates the protocol, the runner retains the last valid state and records a failed attempt separately.

A configuration Π describes the protocol more usefully than the name "multi-agent debate." It should specify initialization, message selection, update order, topology, verifiers, aggregation, and stopping. The same models under different configurations can implement different algorithms. Different role names can still repeat the same computation.

Make initialization and messages reconstructable

Freeze the question, input material, and model configuration first. Initial calls cannot see peer candidates, vote counts, or review comments. Preserve their input digests, model versions, and decoding settings. "Independent" here means no peer messages were read; shared models or material can still produce correlated errors. If agents retrieve different evidence, retain their separate inputs rather than interpreting information differences as reasoning differences.

Store candidate states separately from invocation records. The host assigns state_version and increments it when admitting a new state. Timeouts and retries add attempt records. run_id and question_hash identify the task, protocol_hash fixes prompts and scheduling rules, and evidence_snapshot binds the material version. An answer overwritten in place cannot reveal whether a challenge addresses an old error or a claim already revised.

State:
  run_id, question_hash, protocol_hash, evidence_snapshot
  agent_id, state_version, parent_version, round_id
  answer, claims[], evidence_refs[], unresolved[]
  checks[]
Message:
  message_id, kind: PROPOSAL | CHALLENGE | CHECK | REVISION
  sender, recipients, source_state_version
  target: {agent_id, state_version, claim_id, claim_hash}
  read_set: [{agent_id, state_version, content_hash}]
  payload, evidence_refs[], check_refs[]

The runner constructs read_set from the inputs it actually supplies. A model may explain its reasoning, but cannot certify which versions it read. claim_id identifies a claim, while claim_hash distinguishes content revisions. Check the target version before applying a challenge. Preserve older challenges in history, applying them to the current candidate only when the target claim remains compatible.

A "valid state" here means that its structure parses, source versions can be located, and check records conform to the interface. It does not mean the answer is correct. Messages need not contain complete reasoning transcripts. Short assertions, checkable support, and reasons for changes are often easier to bound. Serialization order, truncation, and summarization prompts are part of the versioned protocol.

Synchronous, sequential, and asynchronous updates use different operators

A Jacobi-style synchronous update freezes the complete previous state S^t−1. Every agent reads that snapshot and writes into a separate buffer; the runner commits after collection. Calls may run concurrently and finish at different times, but an early result cannot enter another call's context within the same round. Double buffering controls read semantics, not merely thread count.

A Gauss-Seidel-style sequential update follows a predefined permutation. Later agents read neighbors already committed in the current round and use previous-round states for the rest. The permutation is therefore an algorithm parameter. Swap or randomize orders and record the seed when comparing sequential protocols. An apparent model advantage may otherwise come from always seeing more updates. These numerical-analysis names describe read semantics here; they do not import convergence properties.

Event-driven asynchronous execution has no global round barrier. On receiving a message, agent i can update from different versions of different neighbors. Record the version vector consumed by each call, message deduplication rules, and staleness limits. An older call from the same agent that returns after a newer state must not overwrite that state. The runner compares parent_version atomically at commit (CAS), rejecting a mismatch or recomputing from the newer state. Agents now have their own version counters rather than one shared round index.

The diagram fixes three agents: synchronous and sequential modes each show two rounds; asynchronous mode shows six local update events without two global rounds. It illustrates visible versions rather than measured speed or accuracy. Some implementations call concurrent computation asynchronous while still reading only previous-round snapshots. Their logical update remains synchronous. Distinguish executor parallelism from state-read semantics. Asynchronous scheduling can also give faster models more frequent opportunities to influence peers, so report actual update counts per agent.

Topology changes information as well as cost

Let a directed edge j → i mean that i can read j. The neighborhood N_i determines visible candidates. H_i then selects complete answers, claims, evidence, or summaries, together with their order and length. Full connectivity, rings, stars, and targeted challenges change both message volume and where an error or useful counterexample can propagate.

If exchanged candidates are bounded to length L and only current snapshots are sent, peer input for R fully connected rounds is approximately O(RN²L). With fixed indegree d it is O(RNdL). These estimates exclude the question, private history, outputs, and verification. If the full history accumulates each round, message length grows and the fixed-L estimate no longer applies.

Sparse links can reduce repeated input while cutting off the only correct candidate's route to other agents. A central summary compresses material but introduces another model call and possible omissions. Dynamic routing also incurs selection cost and selection bias. Record messages selected, truncated, and dropped so that topology changes can be explained in terms of what actually changed.

For topology comparisons, reuse initial answers and control message format where possible. A ring that also uses shorter summaries changes connectivity and compression together. Test message-order perturbations separately: identical neighborhoods do not imply identical model inputs.

How correlated errors limit the benefit of more candidates

Separate model calls do not guarantee independent errors. Shared training, retrieved material, prompts, and familiar reasoning shortcuts can cause candidates to fail on the same questions. Interaction can then move previously different candidates toward a common error. Different answers do not establish uncorrelated errors either: several distinct wrong answers can occur together on difficult items.

A simplified model illustrates the variance scale. Let X_i be a binary error indicator. Under a specified distribution of tasks and run sampling, assume every agent has marginal error probability p, with 0 < p < 1, and every distinct pair has correlation ρ. The diagram varies ρ from 0 to 0.9; the formulas cover 0 ≤ ρ ≤ 1.

Expand the covariance of the mean: there are N marginal variance terms and N(N−1) pairwise covariance terms. N_eff is the equivalent count obtained by expressing this variance as an independent mean. It equals N at ρ = 0 and 1 at ρ = 1. Additional candidates may serve other purposes; this quantity describes only the variance of the mean error.

This is neither a voting-accuracy formula nor an empirical LLM result. In general, p and pairwise correlation alone do not determine the probability of a majority of errors. Multiclass plurality also depends on how wrong answers are distributed. Real candidates often have unequal marginal accuracies; inspect their error vectors and covariance rather than forcing them into one ρ.

Retain paired results by question and examine difficulty strata when estimating dependence. Mixing easy and hard items can itself produce shared failures, so correlation is not a direct causal measure of communication. Deduplicating source material organizes inputs without testing these statistical assumptions. Whether a design adds useful complementary information still needs comparisons against reference outcomes.

Target claims that a verifier can actually check

A useful challenge identifies a target rather than merely asking an agent to reconsider. After decomposing an answer into claims, a challenger can identify a missing premise, supply a counterexample, flag a conflict with evidence, or attach a failing test. The recipient states which claim it retains, revises, or withdraws and why. Checks cannot automatically survive a change to the claim's content.

Challenge:
  target: {state_version, claim_id, claim_hash}
  type: missing_premise | contradiction | counterexample | test_failure
  evidence_refs, proposed_check, expected_observation
CheckRequest:
  target_claim_hash, artifact_hash, evidence_snapshot
  verifier_id, verifier_version, test_spec, resource_cap
CheckResult:
  status: PASS | FAIL | UNKNOWN
  scope, observed, evidence_refs, verifier_version, input_hash

A challenge to a boundary-condition judgment, for example, can provide a minimal input, expected property, and observed result. The runner replays the check in an isolated environment, verifies input and artifact hashes, and supplies the result to the reviser. The proposed test also needs review: it must test the agreed property rather than manufacture a failure by changing the task.

PASS must carry a scope. A passing unit test establishes only that its input and assertions passed. A citation match establishes that a passage exists. A formal proof depends on its axioms and specification. Whether evidence supports an open-ended claim may require model or human assessment, whose errors also need measurement. UNKNOWN covers timeouts, missing inputs, and checks that cannot decide the issue; it must not be treated as PASS.

The runner can perform cheap schema, version, and executability checks before spending resources on tools or semantic verifiers. Versioned check results enter the next F as external feedback. A model's own "verified" label cannot create a check record. If a revision changes the tested program or premise, invalidate the affected checks rather than retaining one blanket verified flag.

Define the answer space and tie policy before aggregation

For discrete answers, define a normalization map g before counting votes. Fix the treatment of numeric formats, units, option aliases, and abstentions. Selecting the most frequent answer is plurality. A candidate has a strict majority only when it receives more than half of valid votes. Multiclass plurality need not exceed half, and ties need a predefined policy rather than selection of the earliest response.

For open answers, vote over predefined atomic claims or use a judge for pointwise or pairwise assessment. The textual mode of complete free-form reports has no stable meaning. If another model implements g, normalization becomes a component with its own cost and errors and needs auditing. Check consistency after combining claims: individually popular claims need not form a jointly satisfiable answer.

A judge can read candidates and scoped checks, then select, synthesize conditionally, or abstain. Order, length, and identities can influence its decisions. Fix the rubric, hide unnecessary identities, perturb order, and assess decisions against independent references or human labels. Separate benefits from a stronger judge from benefits of a different interaction protocol.

Confidence weighting requires another validation layer. Neither self-reported confidence nor generation probability automatically represents correctness probability. Evaluate calibration on untuned samples representative of deployment, using measures such as the Brier score and reliability diagrams, and version the calibrator. Even well-calibrated marginal probabilities do not remove shared errors; simple weighting can count one signal repeatedly. Without adequate calibration data, retain unweighted voting and abstention as comparison conditions.

Calibration also needs a defined event and reference. If the target is answer correctness, labels must come from answer checks; calibration against preferences cannot be substituted for factual accuracy. For predicted probability r_k and binary correctness label y_k, the Brier score is the mean of (r_k−y_k)². Inspect sample counts and errors across probability ranges as well, since an overall score can hide confidently wrong answers. Keep calibration data separate from test tasks and reassess after model or distribution changes.

Stopping describes progress, not truth

A fixed round count is easy to implement and useful for ablations. Adaptive stopping needs explicit observables: changes in normalized answers, reductions in unresolved challenges, new check results, and sufficient remaining resources for another update. Compute these from state changes rather than relying solely on a model saying that discussion is complete.

With fixed inputs and deterministic updates, a fixed point S* satisfies G(S*) = S*. It says only that the operator no longer changes that state; a wrong answer can also be a fixed point. Several unchanged answers under stochastic generation do not even establish a strict fixed point. Stability helps control computation without replacing external checks.

Return a stopping reason: round limit, insufficient budget, deadline, stable candidates, decisive checks passed, or unresolved challenges. Passing checks establishes completion only within a scope that covers the task requirements. Otherwise, return candidates and unresolved issues. Reserve resources and time for final aggregation rather than assuming a judge can produce an answer after debate has exhausted them.

Saved states bind to an evidence snapshot. If new retrieval is permitted, changes to E can reopen challenges and require new evidence versions and dependency checks. The minimal loop below fixes E and stores verification feedback in states, avoiding the difficulty of introducing dynamic retrieval and scheduling simultaneously.

A bounded synchronous runner

This skeleton uses Jacobi updates. t = 0 is blinded initialization, followed by at most R revision rounds. propose_and_verify generates and checks within one allocation, returning a candidate and check records. admit checks schema, epoch, read_set, target versions, and record provenance. It admits a protocol state rather than certifying correctness. eligible_candidates excludes answers with decisive failures while preserving conditional or unresolved outputs for insufficient evidence.

def debate(q, E, agents, protocol, ledger, deadline):
    # Reserve final aggregation AND its output checks before sampling.
    final_ticket = ledger.reserve_final(protocol.final_cost_cap)
    if final_ticket is None:
        return unresolved("insufficient_final_budget")
    work_deadline = deadline - protocol.final_time_cap
    last_valid = {i: None for i in agents}  # keep all configured IDs
    active = list(agents)
    history = []
    stop_reason = "round_limit"

    for t in range(protocol.max_revision_rounds + 1):
        if now() >= work_deadline:
            stop_reason = "work_deadline"
            break
        snapshot = freeze(last_valid)       # immutable read buffer
        epoch = open_epoch(t, snapshot.hash, E.hash)
        next_state = dict(snapshot.states)  # separate write buffer
        jobs, admitted_agents = [], set()
        round_deadline = min(work_deadline, now()+protocol.round_timeout)

        for i in active:
            if now() >= round_deadline:
                break
            messages = [] if t == 0 else select_messages(
                i, snapshot, protocol.graph, protocol.message_cap)
            inputs = make_inputs(q, E, snapshot[i], messages)
            cap = bound_proposal_and_verification_cost(inputs, protocol)
            ticket = ledger.try_reserve_atomic(cap, round_deadline)
            if ticket is None:
                record_skip(i, epoch, "worker_budget")
                continue
            jobs.append(submit_propose_and_verify(
                i, inputs, epoch, ticket,
                timeout=min(protocol.call_timeout, round_deadline-now())))

        for event in collect_until(jobs, round_deadline):
            ledger.settle_or_hold(event)    # charge known use; hold unknown use
            record_attempt(event, epoch)
            if event.status != SUCCEEDED or event.result is None:
                continue
            result = event.result
            if admit(result, epoch, snapshot, E):
                next_state[event.agent] = host_versioned(result, snapshot)
                admitted_agents.add(event.agent)

        close_epoch(epoch)                 # late results cannot alter this round
        cancel_unfinished(jobs)             # cancellation does not imply no bill
        ledger.keep_unsettled_reservations(jobs)
        last_valid = commit(next_state)
        history.append(record_last_valid(t, last_valid, admitted_agents))
        if t == 0:
            active = [i for i in agents if last_valid[i] is not None]
        if not active:
            stop_reason = "no_admitted_initial_states"
            break
        if not jobs:
            stop_reason = "no_jobs_dispatched"
            break
        if t > 0 and not admitted_agents:
            stop_reason = "no_admitted_updates"
            break
        if t > 0 and len(admitted_agents) == len(active):
            reason = stop_by_state_diff(history, protocol)
            if reason is not None:
                stop_reason = reason
                break

    history.append(record_stop(stop_reason))
    candidates = eligible_candidates(last_valid, protocol)
    final = aggregate_and_check(
        q, candidates, history, final_ticket, deadline)
    if final.admitted:
        return final.with_trace(history, ledger)
    return local_unresolved_fallback(last_valid, history, ledger)

Three execution details define the loop. First, reserve resources atomically, or concurrent calls may spend the same balance. Bounds must cover input, maximum output, and verification, and automatic retries consume the same budget. Second, results arriving after the round deadline can enter attempt logs but cannot change a closed snapshot. Third, malformed or failed returns do not overwrite last_valid, so failure is not recorded as a new valid answer.

Cancellation may not stop provider billing immediately; retain reservations for unsettled consumption. The budget boundary depends on conservative estimates and enforceable provider caps. An interface without complete caps cannot support a strict guarantee on actual charges. The final call also has a timeout. If it fails, return a local unresolved result rather than adding unplanned model calls.

These functions specify contracts rather than a directly executable framework API. An implementation still needs provider adapters, schema validation, and persistence. Protocol tests should include out-of-order results, duplicate messages, parse failures, and insufficient budget. These test execution semantics without pretending to measure answer correctness.

Freeze the active set after initialization. Agents without an admitted blinded initial answer leave revision for this run, while their original IDs and failures remain in logs and scoring denominators. Check stability only after admitted updates. This skeleton requires valid updates from every active agent in that round and does not trigger stable stopping from an initialization record alone. A round with no admitted updates receives a separate failure reason.

Events use typed outcomes such as SUCCEEDED, FAILED, CANCELLED, and TIMEOUT; only success with a result reaches admit. Generation, verification, and aggregation adapters must convert expected timeouts and provider errors into structured outcomes. Failed aggregation returns admitted=False so that the local fallback is reachable. A background receipt handler still records late invocations and settles their charges, without authority to alter closed states.

Mechanism ablations and budget comparisons answer different questions

A mechanism ablation preserves one set of initial answers and branches into direct aggregation, separate revision, revision after reading peers, and targeted challenges with verification. Fix models, initial evidence, aggregation, and scoring to examine how the same candidates change. Direct voting makes no subsequent calls, so common initial answers do not imply equal resources. This design localizes the contribution of added computation without establishing efficiency on its own.

When a method introduces new material, add a shared-evidence condition without dialogue. Give each agent the same evidence package for separate revision; the discussion condition reads that package too before receiving peer feedback. If only discussion receives new evidence, retrieval coverage and interaction are confounded. Ablate changes in the aggregator, verifier, and message compression separately as well.

For complete-workflow comparisons, give methods the same budget caps and let them allocate initial samples, revision rounds, and checks. Include a single agent, plurality with additional independent sampling within budget, and independent self-revision. Do not force equal N here: candidate generation competes with communication for resources. Report actual consumption and quality curves without wasting unused budget.

Count input and output, cache pricing, routing, summarization, verification, answer mapping, judging, and retries. Report elapsed time and concurrency limits separately so that lower latency is not mistaken for less computation. Different model prices or local hardware make equal-token and equal-cost settings different experiments.

Select topology, prompts, and stopping on validation data, then compare on held-out tasks. Pair runs by question, repeat sampling, and preserve seeds and failure states. If only high-disagreement items enter Debate, report conditional performance after routing and results for the complete workflow, retaining timeouts, invalid formats, and unresolved outputs in the denominator.

Define the denominators of revision metrics

Let c_di^t = C(q_d, x_di^t) ∈ {0,1} indicate whether agent i is correct on question d at time t. C uses independent references, tests, or predefined annotation rules. The following metrics condition on the initial answer and count question-agent pairs. A zero denominator is undefined, not zero.

For one-step transitions, replace 0 with t−1 and report by round; do not mix these with initial-to-final rates. Under the scoring convention here, an unscorable output receives 0, with INVALID, TIMEOUT, and other statuses listed separately. A timed-out revision that retains an old state is scored using that retained candidate. Report actual revision coverage and failures rather than counting only successful revisions. Any additional analysis restricted to valid initial answers must state that subset's size.

Compute question-level outcomes separately. Let z_d^t indicate correctness of the aggregated output. Accuracy change is the mean of z_d^T−z_d⁰. A higher agent repair rate does not guarantee higher aggregate accuracy: aggregation can discard a correct candidate or combine incompatible claims.

Two further conditional metrics operate at question level: final aggregate success among questions where every initial answer was wrong, and loss of the correct result among questions that initially contained a correct minority. Define "minority" first, for example a correct count k satisfying 1 ≤ k < N/2. Their denominators are eligible question counts, not agent counts or the whole test set.

Report paired differences by question and uncertainty. Cluster interval estimates by question rather than treating agents on one item as independent observations. Separate model scores, human judgments, and objective checks for open tasks. Also report abstention coverage and the error rate among answered tasks so that answering fewer questions cannot hide failures.

If N varies by question or protocol, pooling agent-level revisions gives more weight to questions with more candidates. Also summarize by question and state whether rates are macro-averaged or pooled by candidate. Complete-workflow accuracy remains a question-level measure.

Treat the protocol as a reproducible experimental object

Preserve Π, model and prompt hashes, evidence snapshots, initial answers, every read_set, admitted and rejected updates, check artifacts, aggregation inputs, stopping reasons, and the resource ledger. These records let an investigator replay message selection and distinguish model proposals from host commits. Replaying a log is different from calling the model again; the latter generates new random outcomes.

Start implementation with blinded sampling and plurality, add synchronous double-buffered updates, then introduce claim-level challenges and bounded verifiers. Test execution semantics before comparing each added component with existing paths on paired tasks. More asynchronous scheduling or complex routing becomes justified when failures can be traced to message timing or context exposure.

A final report should answer a concrete question: under specified models, tasks, and budgets, which exchanges repair which initial answers, and which correct answers do they lose? That level of evidence can justify retaining a protocol or simplifying it. Round counts, consensus, and graph structures cannot provide it on their own.