- Rating
- 2
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper mainly investigates how the randomness of LLM agent outputs and different levels of agreement granularity affect the validity of traditional Byzantine Fault Tolerance in multi-agent systems. The authors examine three main aspects: how often the validity condition is triggered, how reliably honest agents' answers can be certified, and how accurately different tools measure agreement. They also provide theoretical analysis to explain the relationship between agreement granularity, output distributions, and fault-tolerance thresholds. The experiments cover benchmarks such as GSM8K, MMLU, and MBPP, using different language models, adversarial agent interventions, and human annotations for validation. The results show that different levels of agreement granularity can significantly change agreement probabilities and certification outcomes. They also find that simple text matching and LLM judges struggle to accurately identify whether agents use the same reasoning steps.
Critical strengths
-
The paper provides a useful theoretical perspective by connecting agreement granularity with the randomness of LLM agent outputs, showing how output distributions affect agreement probabilities and fault-tolerance thresholds, which I think helps explain why traditional BFT validity conditions may become less informative in multi-agent systems.
-
The experiments are quite comprehensive, covering multiple benchmarks, different models, adversarial agents, and also like human annotations, and I particularly like how the authors examine the limitations of Exact String Matching and LLM Judges, showing that these methods may fail to accurately capture agreement in reasoning steps.
Critical weaknesses
-
I think the theoretical novelty of the paper needs further clarification. Some of the certification criteria in Section 4.2 are based on prior work, while the derivations of collision probabilities and fault-tolerance thresholds mainly rely on classical probability analysis. Also, these results depend on specific assumptions, such as independent sampling and a common view, and do not directly apply to general BFT protocols. I think the authors should better explain what new theoretical contributions this paper makes compared to existing studies.
-
The experimental validation of fine-grained agreement is still somewhat limited. In Section 6.3, human annotators judge whether reasoning steps are equivalent based only on the final answers and short KEY summaries, without seeing the full reasoning process. Also, the direct fine-grained partitioning experiment covers only 24 model–task configurations, and the inter-annotator agreement for reasoning operations is relatively moderate (κ = 0.532). I think these limitations may affect the reliability of the fine-grained agreement measurements.
-
Some of the statistical estimation methods need further clarification. In Appendices B and G, the authors use the empirical mode from the samples to calculate the corresponding U-statistic and describe it as an unbiased estimator. However, selecting the mode and estimating its probability from the same samples may introduce selection bias. I think the authors should clarify this issue and explain whether it could affect the reported certification coverage results.
Questions for authors
-
Could the authors further clarify the main theoretical novelty of this work compared to existing studies, especially regarding the certification criteria and the derived fault-tolerance threshold?
-
In Section 6.3, human annotators only see final answers and short KEY summaries rather than full reasoning traces. How do the authors ensure that these summaries accurately represent the agents' actual reasoning steps, and could this affect the reported agreement results?
-
In Appendices B and G, the empirical mode is selected and evaluated using the same samples. Could this introduce selection bias into the U-statistic estimates, and how might it affect the reported certification coverage?
I appreciate the authors’ responses but I still question the novelty and contribution and thus maintain my current score.