From Debate to Equilibrium: Belief‑Driven Multi‑Agent LLM Reasoning via Bayesian Nash Equilibrium

Dear Reviewer t4Dv, thanks for the feedback and suggestions, we will add clarification where needed as space permits.

Q1:Explain the Implementation of BNE in Sec 2.3

Regarding the definition of belief: belief represents each Execution LLM's policy derived from partial observations and local history, we use belief network to update belief. To enable coherent joint behavior, belief encoder aggregates individual belief states into group-level representation. Then the mix network coordinates this integrated belief information for global Q-value and compute loss and reward after commitment made. This architecture aligns with our formal definition of BNE in Sec 2.2, where optimizes agent policies through belief network updates until reaching a strategy profile where no agent can unilaterally improve its payoff given its beliefs.

Regarding the effectiveness of belief-based coordination, we conduct additional experiments to response this concern. The result of performance comparison with /without achieving BNE demonstrated an average performance improvement of 14%, which can be found at the response to reviewer 7mra Q1.

Q2: Explain the Result in Figure 4

We would like to clarify that Figure 4 in Sec 3.4 intentionally demonstrates that simply increasing the number of execution LLMs without appropriate coordination mechanisms can actually decrease performance. We attribute this to the challenge faced by the Coordinator LLM in managing an excessive number of Execution LLMs in Sec 3.4.

To address this scalability challenge, we propose a global Nash equilibrium through local Nash equilibria by introducing additional coordinators in our manuscript (Sec 3.4). This setup ensures that each Coordinator handles a reasonable amount of data, as demonstrated by the improvements reported in Figure 5. We provide the corresponding pseudocode and detailed explanation for scaling up ECON in Appendix A.4.

Q3: Regarding The Inter-agent Communication in ECON

I believe the direction of this area should improve the efficiency of inter-agent communication instead of giving it up.

We would like to clarify that ECON does not eliminate inter-agent communication entirely, but rather adopts an incomplete-information perspective that minimizes communication (as recognized by Reviewers sVjj and hmqe). ECON's optimization objective focuses on achieving consensus and constructing implicit communication among execution LLMs.

Although ECON is implicit inter-agent communication, it is not conflicted with explicit inter-agent communication, we make additional experiment to demonstrate that by incorporating explicit interaction into ECON (which makes it become a complete information formation). The performance improve 1.1% while the token consumption increase 42.4% on average, demonstrate potential to achieve stronger performance with sufficient token budget.

Q4: The Effectiveness of Different Modules of the Mix Network

Theoretically, the design of our mixing network optimizes local policies to improve the global objective, monotonicity guarantee are demonstrated in Appendix A.5. We make additional ablation experiments to validate this point by removing the concatenation of $e$ and remove belief encoder to claim that each parts of ECON is essential, as shown in the experiments.The baseline result is ECON.

Q5: Why are Multi-LLM Methods are Even Worse Than Single Ones?

Our abstract needs clarification: the 10.9% for MA-LLM is averaged across six datasets, while the 11.2% for Single is across five datasets (exclude TravelPlanner). Since single agent approach with open-source model have 0% pass rate on TravelPlanner, ECON's improvement ratio cannot be calculated. With TravelPlanner excluded, ECON's comparative results on five datasets are reported in Sec 3.2 which indicates the single-LLM methods are worse than multi-LLM methods.

Q6: The Missing References Need to Discuss

We agree that it's necessary to incorporate discussions of these works. We will update our related work section in the revised version.

Q7: Clarification about Figure 2

Figure 2 illustrates both the inference phase and optimization phase of ECON. The inference phase (left part) is primarily based on LLMs, where the Coordinator LLM and Execution LLMs work together to generate solutions. For a more detailed understanding of this process, we provide a comprehensive case study of the inference process in Appendix D.1.

Dear Reviewer hmqe: Thanks for your constructive review, we provide some response regarding your question:

Q1: About the inference phase of ECON

Section 2 mainly focuses on the optimization phase and it is not clear how the inference phase works in ECON. What is the observation of each agent, what is the strategy provided by the coordinator, how Coordinator aggregates the answers, etc are not mentioned.

We provide a more intuitive and detailed explanation of our framework below:

1. Intuitive Framework Explanation

During the inference phase of ECON, a Coordinator LLM generates an informative strategy and a format based on the input question. These are then disseminated to the Execution LLMs, which independently produce their respective answers. Finally, the Coordinator LLM aggregates these answers to form a final commitment. A detailed case study demonstrating this inference process is provided in Appendix D.2.

In the optimization phase of the ECON framework, we update each Execution LLM's belief state through its belief network, aggregate these belief states via the belief encoder to form group-level information, then the mixing network outputs the final Q_tot. After the current answer is completed, we calculate loss and reward based on the commitment, which are then used to update the parameters of each Execution LLM's belief network and the belief encoder. We describe our specific DEC-POMDP components setting as follows:

1. Detailed DEC-POMDP Components

Partial Observation: In our framework, each agent receives only three types of information: the question it needs to answer, the format and strategy provided by the coordinator, and the final commitment (aggregated response) after the coordinator combines all LLM answers. This setting prevents Execution LLMs from directly accessing the outputs of others.

Local History: Local history includes its actions and received observations. This local history enables the agent to learn from past behaviors and environmental feedback, refining its situational understanding and updating its belief state accordingly.

Action: Prompt embedding The action space is represented by the prompt embedding, which encodes the agent's action output. The prompt embeddings directly influence the LLM's generation process, adjusting the balance between exploration and exploitation.

State Transition: The state transition in our framework is essentially the update of the agent's belief state. The belief network updates the belief state based on the agent's local history and current observation, influencing future actions.

Q2: Clarification about prompt embedding:

the prompt embedding e_i = [T_i, p_i], where T_i is the temperature and p_i is the threshold for repetition. How do T_i and p_i construct the token embedding for the prompt?

Thank you for your insightful comments. We agree that our description of the prompt embedding requires clarification.

• The prompt Embedding actually the action generated by belief state, we use this expression because it embeds control parameters that directly influence the Execution LLM's generation process. We will rename this in the revised manuscript to avoid confusion about embedding of answer output.

Q3: About the scalability of ECON:

How does ECON scale up to more agents? Does it require additional training? We would like to clarify how we make our framework scalable and yes, scalable ECON require additional training:

• Our solution enhances scalability by forming a global Nash equilibrium through local Nash equilibria by introducing additional coordinators. Simply increasing the number of Execution LLMs would cause performance degradation since coordinator LLMs cannot handle excessive information (especially for weaker models).
• As shown in Figure 4, merely increasing Execution LLMs causes performance decline as coordinator LLMs struggle to manage numerous agents, particularly with weaker models.
• Results in Figure 5 demonstrate that our scaled-up system (9 Execution LLMs, 3 coordinators, 1 central LLM) achieved an 18.1% improvement over the baseline system (3 Execution LLMs, 1 coordinator), indicating potential for further scaling.
• More details about ECON's scalability can be found in Section 3.4, with detailed explanation and pseudocode in Appendix A.4.

Q4: Figure Presentation Issues

In Figure 2, the red gradient flow is missing. In Figure 3, it would be more effective to group the bins by LLMs rather than baseline methods, as this would better highlight differences between baselines rather than between different LLMs.

Response: We appreciate your constructive feedback. We will address these visualization issues in the revised manuscript by adding the missing red gradient flow to Figure 2 and reorganizing Figure 3 to group bins by LLMs, which will indeed better emphasize the comparative performance.

Dear reviewer sVjj, we'd like to thank you for your careful readings and valuable comments, we provide point to point response as follow:

Q1: The proof of sublinear convergence rate (Appendix B.2)

We acknowledge that the proof in Appendix B.2 would benefit from a more rigorous presentation. In the revised manuscript, we enhance this proof with the following improvements, while we cannot include the rewritten proof in this rebuttal due to space limitations and URL limitation, we provide the procedure as follow:

• Formally justify the $O(t^{-1/2})$ convergence rates for both Q-function estimation errors and policy suboptimality through stochastic approximation theory and convex optimization results.
• Explicitly demonstrate how our learning rate schedule $\eta_t = \eta_0/\sqrt{t}$ ensures these convergence properties under stated assumptions.
• Include the complete mathematical derivation from regret definition to final bound, showing:
  • Precise Q-value decomposition into error terms
  • Rigorous bounding of each error component
  • Explicit summation across agents and time steps
  • Formal harmonic sum bound: $\sum_{t=1}^T 1/t^{1/2} \leq 2\sqrt{T}$
• We present the complete derivation of the final $O(N\sqrt{T}/(1-\gamma))$ bound with all intermediate mathematical steps included.

Q2: The token consumption of ECON

Yes, the token usage reported in Table 3 including the coordinator LLM's output strategy and formatting instructions, the execution LLMs' answers, and the coordinator LLM's aggregated answers. We provide a case study about ECON Inference process in Appendix D.1 and a token usage for strategy formulation and formatting in Appendix D.2.

Q3: Regarding the confusion caused by Table 4

We apologize for the presentation of Table 4. You are correct that R3 and S3 are missing from the table, which makes it difficult to interpret. We have provided a revised Table 4 as follow:

Q4: Explanation of notations

I suggest the author to explain what the local history and partial observation consist of.

We make a more detailed explanation about local history and partial observation, as the limitation of space, please refer to the response of reviewer 7mra Q2.

What is U in the definition of Sec 2.2, can you write the math form? What R consists of?

Utility Function: In our framework, the utility function $U_i$ represents the expected cumulative reward for agent i, calculated as:

$U_i(\pi_i(\theta_i), \pi_{-i}(\theta_{-i}), \theta_i, \theta_{-i}) = \mathbb{E} \left[\sum_{t=0}^{\infty} \gamma^t r_i^t \mid \pi_i, \pi_{-i}, \theta_i, \theta_{-i} \right],$

where $r_i^t$ is the reward at time step $t$, the components of this reward function are detailed in Sec 2.3 under "Reward Design." And $R$ consists of $[r_i]$, i.e., $r_1, r_2, ..., r_n$.

Can you write the math definition of θ?

Yes you are right, the θ in Sec 2.1 defined as local history $\mathbf{\tau}_i^t$ and observation $O_i^t$.

Q5: Clarification of Sec 2.3

I wonder why this can be called "embedding", and can you explain why you concatenate it with Ei It is confusing where ϕ comes from.

Regarding Prompt Embeddings

• The prompt Embedding actually the action generated by belief state, we use this expression because it embeds control parameters that directly influence the LLM's generation process. We will rename this in the revised manuscript to avoid confusion about embedding of answer output.
• Our approach encodes the action $e$ and the global state $E_t$ to jointly optimize the global $Q$-function $Q_{tot}$. The former focuses on local action decisions, enhancing diversity and aiding cooperative exploration, while the latter captures comprehensive group context to foster more efficient inter-agent coordination. We make additional ablation experiments to validate this point by removing the concatenation of $e$ and remove belief encoder; please refer to the response of reviewer t4DV Q4.

Regarding φ: You are correct that there is an unclear relationship between $\phi$ and $\theta_i^B$. In our revised manuscript, we will explicitly denote $\phi_i \subset \theta_i^B$ to indicate that Q-value function parameters are a subset of the belief network parameters.

Q6: Deeper analysis of weaker models

Though deeper analysis of weaker models' contributions would strengthen validity.

We have conducted additional experiments with smaller language models and found that our framework still provides significant improvements over baseline approaches, the comparison is made with few-shot CoT.

Dear Reviewer 7mra: Thanks for your constructive review, we provide point to point response regarding your question:

Q1: The Clear Definition of DEC-POMDP and the ECON Framework

Reply: We provide a more intuitive and detailed explanation of our framework below:

---

Detailed DEC-POMDP Component

Partial Observation: In our framework, each agent receives only three types of information: the question it needs to answer, the format and strategy provided by the coordinator, and the final commitment (aggregated response) after the coordinator combines all LLM answers. This setting prevents Execution LLMs from directly accessing the outputs of others.

Local History: Local history includes its actions and received observations. This local history enables the agent to learn from past behaviors and environmental feedback, refining its situational understanding and updating its belief state accordingly.

Action: Prompt embedding The action space is represented by the prompt embedding, which encodes the agent's action output. The prompt embeddings directly influence the LLM's generation process, adjusting the balance between exploration and exploitation.

State Transition: The state transition in our framework is essentially the update of the agent's belief state. The belief network updates the belief state based on the agent's local history and current observation, influencing future actions.

---

Intuitive Framework Explanation

During the inference phase of ECON, a Coordinator LLM generates an informative strategy and a format based on the input question. These are then disseminated to the Execution LLMs, which independently produce their respective answers. Finally, the Coordinator LLM aggregates these answers to form a final commitment. A detailed case study demonstrating this inference process is provided in Appendix D.1.

In the optimization phase of the ECON framework, we update each Execution LLM's belief state through its belief network, aggregate these belief states via the belief encoder to form group-level information, then the mixing network outputs the final Q value. After the current answer is completed, we calculate loss and reward based on the commitment, which are then used to update the parameters of each Execution LLM's belief network and the belief encoder.

---

Q2: Explanation of the Learning Target of ECON Framework

Reply: We clarify how setting BNE as the learning target leads to better aggregated answers as follows:

As mentioned in MAD, the key improvement in Multi-Agent Debate lies in agreement intensity, indicates the degree to which agents agree with each other can provide significant performance gains. This principle underlies our approach, where we set BNE as the optimization target to establish consensus among the agents. We then analyze the total Bayesian regret of the joint policy (i.e., the aggregated answer output by the MA-LLM system) based on learning towards BNE in Lemma 2.2 and Appendices B.2–B.3.

To further validate that learning towards BNE can lead to better aggregated answers, we provide additional experiments showing the actual performance differences of the ECON framework before and after achieving BNE as follow:

---

Q3: Discuss the Issue of ECON Scalability

Reply: We would like to clarify how we make our framework scalable:

• Our solution enhances scalability by forming a global Nash equilibrium through local Nash equilibria by introducing additional coordinators. Simply increasing the number of Execution LLMs would cause performance degradation since coordinator LLMs cannot handle excessive information (especially for weaker models).
• As shown in Figure 4, merely increasing Execution LLMs causes performance decline as coordinator LLMs struggle to manage numerous agents, particularly with weaker models.
• Results in Figure 5 demonstrate that our scaled-up system (9 Execution LLMs, 3 coordinators, 1 central LLM) achieved an 18.1% improvement over the baseline system (3 Execution LLMs, 1 coordinator), indicating potential for further scaling.
• More details about ECON's scalability can be found in Section 3.4, with detailed explanation and pseudocode in Appendix A.4.