We sincerely appreciate your insightful feedback. Our responses below address each point and further clarify our work's contributions. If you have any other questions, please feel free to let us know. Otherwise, if our responses have addressed your comments satisfactorily, we kindly invite you to consider updating the rating.

Q1. Analysis of computational overhead.

A1. We would like to clarify that although the calculation of conflict score requires additional computation time, it is a lightweight operation, which does not require GPU resources, thus its computation time is practically negligible. To better understand the computational efficiency, we separately count the average number of tokens per case (denoted by "#Token") as an estimate of computational cost for both our proposed BCCS and the SOTA baseline on each dataset of MATH and MMLU, as shown in the tables below. The results demonstrate that BCCS achieves better results with lower computational cost.

Q2. Probability-based belief representation.

A2. Thank you for pointing out the probability may not always reflect true uncertainty. Following prior work [1], we adopt the output probability of LLMs as a proxy for belief. While we acknowledge that LLM's output probabilities may not always perfectly reflect uncertainty, this approximation is a widely used and practical method for belief estimation in large language models.

Q3. Performance on more scenarios.

A3. Thank you for your constructive suggestion. We have extended the evaluation on two NLP benchmark datasets with two reasoning scenarios, including FOLIO [2] of logical reasoning and CommonsenseQA [3] of commonsense reasoning. We compare our proposed BCCS with three best performed baselines, the results are listed in the table below, which demonstrate that our proposed BCCS performs better than the baselines on the two datasets.

Q4. Sensitivity of hyperparameters.

A4. Thank you for your insightful comment. We would like to clarify that the values of hyperparameters including the consensus and conflict thresholds are derived mathematically, with detailed derivations presented in Section 4. To demonstrate the sensitivity of these thresholds, we compare the performance of different values for the thresholds of full consensus, partial consensus, and conflict scores, as shown in the tables below. The results show that the mathematically derived values are optimal consistently.

For other hyperparameters, including agent number, leader number and rounds, we follow the existing multi-agent methods [4] to select these hyperparameters and provide the comparision of different values of these thresholds in Appendix D.1 to demonstrate the sensitivity of these hyperparameters.

References

[1] Chiwei Zhu, Benfeng Xu, Quan Wang, Yongdong Zhang, and Zhendong Mao. On the Calibration of Large Language Models and Alignment. Findings of EMNLP 2023.

[2] Simeng Han, Hailey Schoelkopf, Yilun Zhao, Zhenting Qi, Martin Riddell, Wenfei Zhou and etc. FOLIO: Natural Language Reasoning with First-Order Logic. EMNLP 2024.

[3] Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. CommonsenseQA: A Question Answering Challenge Targeting Commonsense Knowledge. NAACL 2019.

[4] Yilun Du, Shuang Li, Antonio Torralba, Joshua B. Tenenbaum, Igor Mordatch. Improving factuality and reasoning in language models through multiagent debate. ICML 2024.

Thank you for your valuable comments, and we have carefully addressed all of your comments, if there are still any questions requiring further clarification, we sincerely hope you could point them out. If you consider that our revisions have met your expectations, we would be grateful if you could consider raising the evaluation rating accordingly. Your feedback is of utmost importance to us!

We sincerely appreciate your positive feedback on our proposed insights for building reliable collaborative systems, as well as your constructive suggestions. We have carefully addressed each comment below to further clarify our contributions. If you have any other questions, please feel free to let us know. Otherwise, if our responses have addressed your comments satisfactorily, we kindly invite you to consider updating the rating.

Q1. Performance with heterogeneous backbones.

A1. Thank you for raising an interesting point. Our main experiments follow most current multi-agent works to use identical models as the backbones. To demonstrate the effectiveness of our approach with heterogeneous backbones, we utilize Qwen2.5-7B-Instruct, Phi-3-mini-4k-Instruct (3.8B), and Llama-3.2-1B-Instruct as backbones. The results are presented in the tables below, which showcase that our proposed BCCS outperforms the SOTA baseline on each dataset when applied to heterogeneous backbones.

Q2. Analysis of computational overhead.

A2. We would like to clarify that although the calculation of conflict score requires additional computation time, it is a lightweight operation, which does not require GPU resources, thus its computation time is practically negligible. To better understand the computational efficiency, we separately count the average number of tokens per case (denoted by "#Token") as an estimate of computational cost for both our proposed BCCS and the SOTA baseline on each dataset of MATH and MMLU, as shown in the tables below. The results demonstrate that BCCS achieves better results with lower computational cost.

Q3. Literature review enrichment.

A3. We sincerely appreciate your valuable suggestion to enhance our literature review by including the work "Do as We Do, Not as You Think: The Conformity of Large Language Models" (ICLR). We will incorporate this reference in the related work section of the final version.

Q4. Justification and sensitivity of consensus and conflict thresholds.

A4. Thank you for your insightful comment. We would like to clarify that the values of hyperparameters including the consensus and conflict thresholds are derived mathematically, with detailed derivations presented in Section 4. To demonstrate the sensitivity of these thresholds, we compare the performance of different values for the thresholds of full consensus, partial consensus, and conflict scores, as shown in the tables below. The results show that the mathematically derived values are optimal consistently.

Q5. More failure case.

A5. Thank you for your suggestion. We add an additional failure case in the table below. This case demonstrates that BCCS is able to correctly identify the incorrect result produced by the agent as unreliable and appropriately selects a conflicting agent as the collaborator. However, due to limitations in model performance, all agents fail to generate the correct answer, thus the agent can not update a correct anwer in the next round.

Case:

Question: A cannon is mounted on a truck that moves forward at a speed of 5 m/s. The operator wants to launch a ball from a cannon so the ball goes as far as possible before hitting the level surface. The muzzle velocity of the cannon is 50 m/s. At what angle from the horizontal should the operator point the cannon? A) 5°, B) 41°, C) 45°, D) 49°

Q6. Typos correction.

A6. We sincerely appreciate your careful reading and valuable feedback. We will correct the typos identified in the final version.

Thank you for your valuable comments, and we have carefully addressed all of your comments, if there are still any questions requiring further clarification, we sincerely hope you could point them out. If you consider that our revisions have met your expectations, we would be grateful if you could consider raising the evaluation rating accordingly. Your feedback is of utmost importance to us!

We are grateful for your valuable comments. We provide detailed responses to each comment below, aiming to better articulate the contributions of our work. If you have any other questions, please feel free to let us know. Otherwise, if our responses have addressed your comments satisfactorily, we kindly invite you to consider updating the rating.

Q1. Significance of performance gains.

A1. Thank you for your comment. We agree that the performance gains are more significant on more challenging tasks. For simple tasks, since the original model itself can already achieve relatively stable consensus, the marginal benefit of further introducing collaborative mechanisms is relatively limited. We will add a clarification of this comment in the final version.

Q2. Generalizability to other NLP tasks.

A2. Thank you for your suggestion. We extend the evaluation on two widely used NLP benchmark datasets for multi-agent reasoning scenarios, including FOLIO [1] of logical reasoning and CommonsenseQA [2] of commonsense reasoning. We compare our proposed BCCS with three best performed baselines, the results are listed in the table below, which demonstrate that our proposed BCCS performs better than the baselines on the two datasets.

Q3. Analysis of computational overhead.

A3. We would like to clarify that the conflict score calculation is a lightweight operation that does not require GPU resources, which computation time is practically negligible. Therefore, although the number of conflict score calculations increases with the growth of agent numbers and opinion groups, it does not lead to a significant rise in time and space complexity. To better understand the computational efficiency, we separately count the average number of tokens per case (denoted by "#Token") as an estimate of computational cost for both our proposed BCCS and the SOTA baseline on each dataset of MATH and MMLU, as shown in the tables below. The results demonstrate that BCCS achieves better results with lower computational cost.

Q4. Determination of the hyperparameters of agent numbers and iteration rounds.

A4. Thank you for your insightful comment regarding the empirical determination of the optimal number of agents and iteration rounds. We would like to clarify that our approach of determination for these hyperparameters is consistent with common practices in the existing multi-agent collaboration systems [3], where the number of agents and interaction rounds are often determined empirically.

Q5. Robustness of leader selection in BCCS.

A5. Thank you for your valuable comment. We fully agree with the observation that selecting leaders with lower beliefs compromises the system’s robustness by reducing consensus reliability, while higher-belief leaders facilitate faster convergence. Our proposed method selects the agent with the highest beliefs as the leaders in each iteration to avoid non-robust outcomes, thereby preventing suboptimal agents from serving as long-term leaders. Situations where all agents have relatively low belief are rare. If such a case does occur, it indicates that none of the agents are capable of solving the problem, making it impossible to accomplish the task through collaboration mechanism, instead it will complete the task through the voting mechanism.

Q6. Specific methodologies used for belief calibration.

A6. Thank you for your constructive question regarding belief calibration. We have already described the details of the methods of belief calibration in Section 4. Specifically, the BCCJ module utilizes belief to calibrate the judgment of multi-agent system consensus states based on Byzantine consensus theory. When the multi-agent system is in partial consensus state, after the CA module determines the conflict level between opinion groups, it selects the agents with the highest beliefs as the collaborators to enhance the reliability of the multi-agent system. When the multi-agent system is in no consensus state, LS module selects the agents with the highest beliefs as the leaders to guide the opinions of other agents.

References

[1] Simeng Han, Hailey Schoelkopf, Yilun Zhao, Zhenting Qi, Martin Riddell, Wenfei Zhou and etc. FOLIO: Natural Language Reasoning with First-Order Logic. EMNLP 2024.

[2] Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. CommonsenseQA: A Question Answering Challenge Targeting Commonsense Knowledge. NAACL 2019.

[3] Yilun Du, Shuang Li, Antonio Torralba, Joshua B. Tenenbaum, Igor Mordatch. Improving factuality and reasoning in language models through multiagent debate. ICML 2024.

Thank you for your valuable comments, and we have carefully addressed all of your comments, if there are still any questions requiring further clarification, we sincerely hope you could point them out. If you consider that our revisions have met your expectations, we would be grateful if you could consider raising the evaluation rating accordingly. Your feedback is of utmost importance to us!

We sincerely appreciate your favorable evaluation of the theoretical analysis and empirical results presented in our work, along with your valuable feedback. We have addressed each comment thoroughly below, with the intention of clarifying and further substantiating the significance of our contributions. If you have any other questions, please feel free to let us know. Otherwise, if our responses have addressed your comments satisfactorily, we kindly invite you to consider updating the rating.

Q1. Generalizability to other tasks.

A1. Thank you for your constructive suggestion. We extend the evaluation on two common used NLP benchmark datasets, including FOLIO [1] of logical reasoning and CommonsenseQA [2] of commonsense reasoning. We compare our proposed BCCS with three best performed baselines, the results are listed in the table below, which demonstrate that our proposed BCCS performs better than the baselines on the two datasets.

Q2. Analysis of computational scalability.

A2. To better understand the computational scalability, we separately count the average number of tokens per case (denoted by "#Token") as an estimate of computational cost for both our proposed BCCS and the SOTA baseline on each dataset of MATH and MMLU, as shown in the tables below. The results demonstrate that BCCS achieves better performance with lower computational cost. Besides, although the conflict score calculation requires additional time, it is a lightweight operation that does not require GPU resources, thus the computation time is practically negligible.

Q3. Hyperparameter choices, edge cases and failure modes.

A3. The values of hyperparameters including the consensus and conflict thresholds are derived mathematically, with detailed derivations presented in Section 4. For other hyperparameters, including agent number, leader number and rounds, we follow the existing multi-agent collaboration methods [3] to select these hyperparameters and provide the comparision of different values of these hyperparameters in Appendix D.1. Moreover, Appendix D.3 presents a variety of edge cases, covering both those successfully handled by BCCS and the challenging instance where it fails. The dominant failure modes originate from the inherent limitations of the backbone models, which restrict the agents' ability to generate or select correct responses. Our proposed framework aims to mitigate the limitations as much as possible compared to other baselines.

Q4. Sensitivity or calibration of generation probability.

A4. We sincerely appreciate your insightful question regarding the sensitivity and calibration of generation probability as a belief across different LLMs and tasks. This is an interesting research direction. However, our study follows the previous works [4] to estimate belief via probability, we primarily focus on proposing a collaboration framework for improving reasoning performance using beliefs estimated by probabilities, which is a widely used approximation for belief estimation in large language models, rather than enforcing a best configuration of beliefs across all models and tasks.

Q5. Performance with misreporting beliefs in adversarial scenarios involving noisy agents.

A5. To simulate adversarial and noisy scenarios, we conduct an analysis experiment by misreporting beliefs. Specifically, we introduce adversarial conditions of misreporting beliefs by perturbing the belief of one randomly selected agent in each round (denoted as "AdvNoise"), either by increasing lower beliefs or decreasing higher beliefs. The results are shown in the tables below, which demonstrate that misreporting beliefs can lead to some performance degradation, yet the overall performance remains higher than the SOTA baseline on each dataset. This is because the remaining correct beliefs are still capable of calibrating the inaccurate or misreported answers, demonstrating the robustness of our proposed BCCS in adversarial scenarios involving noisy agents.

Q6. Empirical evidence and ablation studies for matching theoretical predictions.

A6. We appreciate your suggestion. We would like to clarify that we have already conducted empirical studies to verify the alignment between LLM agent behavior and theoretical predictions. Specifically:

• Figures 4 (a)-(b) present the ablation results validating the conclusions in Theorem 3.2, with corresponding analyses located in the first part of Section 6.3.
• Figures 4 (c)-(d) present the ablation results validating the conclusions in Theorem 3.3, with corresponding analyses located in the second part of Section 6.3.

We hope the analyses in Section 6.3 sufficiently address your concerns.

References

[1] Simeng Han, Hailey Schoelkopf, Yilun Zhao, Zhenting Qi, Martin Riddell, Wenfei Zhou and etc. FOLIO: Natural Language Reasoning with First-Order Logic. EMNLP 2024.

[2] Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. CommonsenseQA: A Question Answering Challenge Targeting Commonsense Knowledge. NAACL 2019.

[3] Yilun Du, Shuang Li, Antonio Torralba, Joshua B. Tenenbaum, Igor Mordatch. Improving factuality and reasoning in language models through multiagent debate. ICML 2024.

[4] Chiwei Zhu, Benfeng Xu, Quan Wang, Yongdong Zhang, and Zhendong Mao. On the Calibration of Large Language Models and Alignment. Findings of EMNLP 2023.

Thank you for your valuable comments, and we have carefully addressed all of your comments, if there are still any questions requiring further clarification, we sincerely hope you could point them out. If you consider that our revisions have met your expectations, we would be grateful if you could consider raising the evaluation rating accordingly. Your feedback is of utmost importance to us!