- Rating
- 1
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper proposes A2A-BFT, a three-phase consensus protocol for LLM agents under Byzantine and soft faults. It combines fault-aware voting with LLM-based validation and evaluates the method on 7750 real LLM runs. The results show strong robustness with execution-based validation, but much weaker safety with imperfect LLM judges, and the proposed reputation mechanism often penalizes honest agents.
Critical strengths
The paper addresses an important problem and usefully distinguishes protocol agreement from the reliability of the validation oracle. The paper make the contrast clear between execution validation and fallible LLM judges, which makes the safety-coverage trade-off concrete (rather than hiding semantic errors behind a consensus rate). The paper also explicitly reports an important negative-result audit.
Critical weaknesses
- The safety proof focuses on consistency for the same proposal, but it does not clearly rule out conflicting commits across views because view changes carry no commit certificate or lock. The liveness proof also relies on unstated cross-round randomness assumptions, even though the inference is with zero temperature.
- The implementation is centralized and does not test message delays or cross-view state transfer, which are important to distributed BFT. Also, semantic-task wrong-commit rates are high.
Questions for authors
Without transferring a commit certificate or lock during view change, what prevents two different proposals from being committed in different views? Please clarify the cross-view agreement argument.
2 comments
Thank you for the detailed response. I appreciate the authors' acknowledgment of the theoretical limitations and their efforts to correct the experimental results.
However, I think the author's point to reframe the contribution as a centralized propose–validate–retry system substantially weakens the paper's original theoretical contribution. The newly identified experimental issues are also significant. The corrected MBPP+ results seem to no longer demonstrate a clear safety boundary. This does not eliminate my concerns about the reliability of the original evaluation.
I appreciate the authors' transparency and corrections, but these issues substantially affect the paper's central theoretical and empirical contributions. I therefore plan to maintain my original rating.
cross-view agreement, cross-round liveness, evaluation scope
[R1.1] Cross-view agreement. This point is correct for the submitted version. The cross-view argument in Appendix A.1.3 (L366-L368) assumes that a commit terminates the task globally and that the task is never re-instantiated. The view-change messages carry neither a lock nor a commit certificate, so the protocol itself does not enforce that assumption. What the paper supports is narrower: for one proposal and a common, complete set of non-Byzantine votes, the two thresholds cannot yield ACCEPT at one end and REJECT at the other (Theorem 5.1(i), L213 and its proof, L217). In the evaluated prototype one coordinator collects votes, rotates the proposer and returns at the first accepted proposal, so each invocation commits at most once; the code has no durable per-task guard across invocations or restarts. The at-most-one-commit statement therefore holds only under an assumed single trusted coordinator with an atomic persistent per-task guard. Such a guard makes the central commit record unique; it does not show that independent replicas learn or adopt the committed value. The final version will (i) restate the claim in the abstract (L55), introduction (L70) and conclusion (L316) as a centralized propose-validate-retry result, (ii) move the coordinator and the per-task termination guard into the system model as explicit assumptions, and (iii) delete the extra statement in Theorem 5.1(i) that disagreement can only be ACCEPT/PENDING, because a counterexample with (n,f,s)=(4,1,0) admits REJECT/PENDING.
[R1.2] Cross-round liveness. Agreed. Theorem 5.3 and Lemma 5.4 (L227-L240) use a geometric bound (1−q)k without stating the condition it needs: a uniform lower bound q>0 on acceptance, conditional on the full preceding history, while valid honest-primary attempts keep occurring. Zero-temperature judges can violate it, since a persistent error makes the conditional probability zero. We will define a qualified attempt (after GST, task undecided, strictly honest primary, valid proposal) and assume that qualified attempts keep occurring and that the next one accepts with probability at least q given every reachable undecided history. The single-attempt bound phn−1−f−s supplies q only if it holds conditionally on history. A validator whose error repeats on every retry breaks this: in a finite example (n=5, f=s=1) acceptance has probability 1/4 unconditionally and 0 after a failed attempt (checked in a finite Lean model). The bound (1−q)k is stated over qualified attempts only and does not say the decision is correct. The fixed-budget prototype is reported separately through its measured coverage.
[R1.3] Centralized evaluation and semantic tasks. Agreed. The experiments exercise centralized validation and proposer rotation. They do not exercise network delay or replica state transfer. The high wrong-commit rates of the semantic judges are a limitation of the evaluated judges, and the final version will report them as such with the verifier, attack and execution scope stated for each result (experiments, L260-L290). Re-examining the experiments also found two errors in our submitted results, which the final version will correct.
(1) On MBPP, the final judge in the submitted sweep executed the same visible tests as the validators, so the reported 0.0% wrong-commit rate held by construction. Judged by held-out MBPP+ tests, wrong commits are 15.2-22.4% within the boundary and 14.4-27.2% in the sub-boundary cells. The ranges overlap, so the code data show no sharp boundary. Re-judging every saved candidate of the matched-baseline run (848 candidates, 192 tasks), 102 of the 615 candidates that pass all visible tests (16.6%) fail MBPP+. This is a candidate-level share and not a validator false-accept rate.
(2) The submitted sweep entry applied the Sybil voting rule to every attack label. After routing each label to its own rule and applying the corrected grader, we re-ran the GSM8K sweep (5 seeds x 50 tasks). Within-boundary wrong commits are 4.4-14.8% and the sub-boundary cells reach 21.6-96.8%. Strategic rejection at (4,1,0) moves from 23.2% to 4.4%, and collusion at (5,2,0) from 72.4% to 96.8%. We also re-ran the MMLU sweep the same way. Within the boundary, wrong commits under attack are now 34.4-52.8% (fault-free 4.0%), and below the boundary 61.6-98.8%. The direction of the change is not uniform: random faults at (4,1,0) rise from 35.6% to 52.4%, strategic rejection at (5,2,0) falls from 85.2% to 64.8%, and collusion at (5,2,0) rises from 90.0% to 98.8%. The new tables will replace the submitted ones; the rerun changed the grader, the voting implementation and the random stream together, so we do not attribute any single difference to one cause.
Thank you.