Paper deep dive
Narrowing the Collaboration Gap, Probably
Mirah Shi, Marcel Hussing, Ira Globus-Harris, Natalie Collina, Aaron Roth, Surbhi Goel
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 96%
Last extracted: 10/15/2026, 5:26:18 AM
Summary
This paper investigates multi-agent collaboration under partial information, comparing action-only communication with probabilistic communication. Theoretical analysis on a chained-parity task demonstrates that communicating calibrated probabilities allows for complete information aggregation, whereas action-only communication often stalls. Empirical results on transformer models and pretrained LLMs in a collaborative maze-solving task confirm that probability communication outperforms action communication when probabilities are calibrated. The authors introduce a post-hoc conversational calibration intervention to correct biases (such as overconfidence and sycophancy) in raw probability reports, significantly improving decision-making performance.
Entities (15)
Relation Signals (10)
Mirah Shi → affiliatedwith → University of Pennsylvania
confidence 99% · Mirah Shi University of Pennsylvania
Marcel Hussing → affiliatedwith → MIT
confidence 99% · Marcel Hussing11footnotemark: 1 MIT
Ira Globus-Harris → affiliatedwith → Cornell University
confidence 99% · Ira Globus-Harris Cornell University
Natalie Collina → affiliatedwith → MIT
confidence 99% · Natalie Collina MIT
Aaron Roth → affiliatedwith → University of Pennsylvania
confidence 99% · Aaron Roth University of Pennsylvania
Surbhi Goel → affiliatedwith → University of Pennsylvania
confidence 99% · Surbhi Goel University of Pennsylvania
Post-hoc calibration → improves → Decision-making
confidence 95% · post-hoc conversational calibration intervention that consistently improves decision-making
Probability communication → outperforms → Action communication
confidence 95% · communicating unbiased probabilities can be strictly more powerful than communicating actions
Sycophancy → →
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Large language models are increasingly deployed as teams of agents that hold different private information about a shared task. How should such agents concisely communicate in a way that promotes aggregation of decision-relevant information? Communicating only proposed actions can discard decision-relevant uncertainty: two agents may prefer the same action for different reasons. We study an alternative interface in which agents communicate calibrated beliefs over actions. We first analyze a simple synthetic setting that captures the structure of multi-round reasoning under partial information. In this setting, we show theoretically and empirically that communicating unbiased probabilities can be strictly more powerful than communicating actions. We then test the same principle in a collaborative maze-solving task with trained transformers and pretrained LLM agents. Our results demonstrate that probability communication outperforms action communication when the exchanged predictions preserve calibrated uncertainty. When communicated probabilities are biased, we show that the benefits of probability communication can disappear. We give a post-hoc conversational calibration intervention that consistently improves decision-making by correcting these biases both in a toy transformer setting and when pretrained LLMs use the corrections in context. These results suggest that probabilistic communication is useful for multi-agent collaboration not merely because it transmits more information, but because calibrated uncertainty gives other agents a reliable object to update on.
Tags
Links
- Source: https://arxiv.org/abs/2610.19215v1
- Canonical: https://arxiv.org/abs/2610.19215v1
Trouble viewing inline? Open PDF directly →
Full Text
105,549 characters extracted from source content.
Expand or collapse full text
Narrowing the Collaboration Gap, Probably Mirah Shi University of Pennsylvania Marcel Hussing11footnotemark: 1 MIT Ira Globus-Harris Cornell University Natalie Collina MIT Aaron Roth University of Pennsylvania Surbhi Goel University of Pennsylvania †thanks: Equal contribution. Correspondence to mirahshi@seas.upenn.edu or mhussing@mit.edu Abstract Large language models are increasingly deployed as teams of agents that hold different private information about a shared task. How should such agents concisely communicate in a way that promotes aggregation of decision-relevant information? Communicating only proposed actions can discard decision-relevant uncertainty: two agents may prefer the same action for different reasons. We study an alternative interface in which agents communicate calibrated beliefs over actions. We first analyze a simple synthetic setting that captures the structure of multi-round reasoning under partial information. In this setting, we show theoretically and empirically that communicating unbiased probabilities can be strictly more powerful than communicating actions. We then test the same principle in a collaborative maze-solving task with trained transformers and pretrained LLM agents. Our results demonstrate that probability communication outperforms action communication when the exchanged predictions preserve calibrated uncertainty. When communicated probabilities are biased, we show that the benefits of probability communication can disappear. We give a post-hoc conversational calibration intervention that consistently improves decision-making by correcting these biases both in a toy transformer setting and when pretrained LLMs use the corrections in context. These results suggest that probabilistic communication is useful for multi-agent collaboration not merely because it transmits more information, but because calibrated uncertainty gives other agents a reliable object to update on. 1 Introduction Large language models (LLMs) are increasingly used within multi-agent systems where agents may share a task but hold different private information. For example, physical robots may see different sensor data, and coding agents may inspect different files when the relevant repository is too large for any single context window. To succeed in such settings, agents must communicate to combine their private information to make better decisions than any single agent could alone. In practice, the same constraints that motivate multi-agent design often make full information sharing infeasible. Communication may be limited by bandwidth, memory, context length, or by the fact that different agents’ observations are not mutually legible across modalities. And even if one agent could transmit its full observation, the receiving agent may not be able to process it into a correct answer (Davidson et al., 2025). More generally, recent work has shown that LLMs often struggle in these collaborative settings, exhibiting failures in information sharing (Cemri et al., 2025), belief updating (Li et al., 2023; Wilie et al., 2024), and joint decision-making under partial information (Davidson et al., 2025; Eisenstein et al., 2026). These failures reveal a broader “collaboration gap" (Davidson et al., 2025): current LLM agents do not reliably aggregate distributed observations into well-coordinated decisions. Narrowing this gap requires answering a fundamental question: What should agents communicate in order to aggregate distributed private information? A natural low-bandwidth alternative to communicating their hidden information is for agents to exchange only their proposed actions. However, communicating actions can omit decision-relevant uncertainty. A promising direction comes from the agreement literature, which shows that Bayesian reasoners with different observations can exchange beliefs to converge towards predictions that aggregate their information (Frongillo et al., 2023). More recent work weakens Bayesian rationality to calibration-style conditions, including conversation calibration, and studies when agreement would lead to optimal actions given the agents’ combined observations (Collina et al., 2025; Collina et al., 2026; Kearns et al., 2026). This perspective suggests that reliable multi-agent LLM collaboration may require mechanisms that go beyond ad hoc message exchange: agents must be able to recognize their own uncertainty and interpret others’ uncertainty. Figure 1: Multi-agent collaboration under partial information. Agents observe different views of the same maze and exchange messages over multiple rounds before producing a final action. We compare action-only messages, verbalized probabilities, sampled probabilities from multiple rollouts, and a post-hoc calibrated probability channel. Figure adapted from Davidson et al. (2025). 1.1 Our contributions Our hypothesis is that, under partial information, agents collaborate more effectively when they communicate calibrated beliefs rather than only their preferred decisions. We investigate this hypothesis theoretically in a stylized theoretical model and empirically on the collaborative maze task of Davidson et al. (2025). We study both transformers trained for the task and large-scale, pretrained LLM agents. Across these settings, we compare two low-bandwidth communication protocols: 1. Action-only communication: In each round, the speaker sends a single action that it currently believes is most likely correct. For transformers this is the action with highest softmax probability; for LLM agents, it is the action selected in the model’s response. 2. Probability communication: In each round, the speaker sends a distribution over actions. For transformers this is the softmax vector. For LLM agents, we consider verbalized probabilities, where the model reports a probability vector in text, and sampled probabilities, where the message is the empirical distribution over independent response rollouts. Our results are threefold. First, in a stylized chained-parity model of multi-round collaboration, we show a theoretical separation between communicating probabilities and communicating actions. Exact probability messages aggregate one new piece of information per round, ultimately leading to full information aggregation. Meanwhile, action-only messages can reveal only the first agent’s information and then stall. Second, we test the same principle in controlled transformer experiments on collaborative maze solving (see Figure 1). We see that probability communication improves over action communication when the learned messages preserve calibrated uncertainty. When probability messages are biased, this advantage can disappear. To address this, we introduce a post-hoc calibration algorithm that corrects biased reports and recovers much of the performance lost when raw probability reports are distorted. Third, we evaluate the same communication protocols using pretrained LLM agents on the maze task. We find that simply asking models to verbalize probabilities is not enough: raw verbalized probabilities are often no better than action messages. We show that across the tested models, applying post-hoc calibration as an intervention consistently improves performance, indicating that probabilistic messages become substantially more useful in-context when corrected into forecasts that other agents can reliably update on. Beyond the agreement literature discussed above, our work also draws on research on calibrated forecasting, uncertainty elicitation in language models, sampling-based uncertainty, multi-agent LLM debate and collaboration, and learned communication in multi-agent reinforcement learning. We defer an extended discussion of these connections to Appendix A. 2 Preliminaries Formally, we study a setting with two agents, Alice and Bob, who collaborate to find a correct action to take. Each data point consists of a feature x∈x and its associated correct action a∗∈a^* , drawn from a joint distribution over ×X×A. Neither agent observes the full feature: Alice observes xA∈Ax_A _A and Bob observes xB∈Bx_B _B, with x=(xA,xB)∈A×Bx=(x_A,x_B) _A×X_B. The correct action depends on the full feature x, so neither agent can reliably identify a∗a^* from their own observations alone. In the special case where a∗a^* is deterministically determined by x, the agents’ combined information is sufficient to identify a⋆a . Communication protocol. The agents communicate for a fixed number of rounds K before selecting an action. Alice speaks on odd rounds and Bob on even rounds; we write σ(k)∈A,Bσ(k)∈\A,B\ for the round-k speaker. We focus on the bandwidth-limited regime, in which each round’s message is much smaller than the speaker’s private observation. We consider two types of communication protocols. In the action-communication protocol, the round-k message is a single proposed action a^k∈ a_k . In the probability-communication protocol, the round-k message is a distribution over actions p^k∈Δ() p_k∈ (A). After round K, the agents execute the action chosen by the final speaker: the final action message a^K a_K under action communication, and argmaxap^K(a) _a p_K(a) under probability communication. Calibration. Calibration formalizes when a probability message can be interpreted as meaningful uncertainty. Intuitively, a probabilistic message is calibrated if its probabilities agree with long-run frequencies. For example, among all instances in which an agent assigns probability 0.70.7 to an action a, that action should be correct approximately 70%70\% of the time. Definition 2.1 (Calibration). Let p p be a Δ() (A)-valued random variable, where the randomness is over the draw of the instance and any randomness in the agents’ procedure. We say p p is calibrated if, for every action a∈a , Pr(a⋆=a∣p^)=p^(a) (a =a p)= p(a) almost surely. Calibration is a marginal property: it says that an agent’s stated uncertainty is correct in aggregate over all instances in which the agent sends the same distribution. With multiple agents, we may also ask if one agent’s forecast remains calibrated after accounting for another communicated forecast. This is the notion of cross-calibration. Intuitively, Alice’s forecast is cross-calibrated with Bob’s forecast if, among all instances where Alice sends a particular distribution, subdividing those instances according to Bob’s distribution does not change the correctness of Alice’s probabilities. Definition 2.2 (Cross calibration). Let p p and q q be Δ() (A)-valued random variables. We say p p is cross-calibrated with respect to q q if, for every action a∈a , Pr(a⋆=a∣p^,q^)=p^(a) (a =a p, q)= p(a) almost surely. Calibration requires an agent’s probabilities to be correct in aggregate, while cross-calibration requires them to remain correct even after conditioning on another communicated forecast. This definition conditions only on the communicated probabilities, not on the other agent’s private observation. Conversation calibration instantiates cross calibration in a communication protocol, requiring forecasts in every round to be cross-calibrated with respect to forecasts of the previous round. Definition 2.3 (Conversation calibration). Following Collina et al. (2025), in a probability-communication protocol, the conversation is calibrated through round K if the initial forecast p^1 p_1 is calibrated and, for every round 2≤k≤K2≤ k≤ K, the round-k forecast is cross-calibrated with respect to the previous round’s forecast: Pr(a⋆=a∣p^k,p^k−1)=p^k(a) for all a∈ (a =a p_k, p_k-1)= p_k(a) for all a almost surely. 3 When do probabilities outperform actions? This section establishes when probability communication can be more useful than exchanging only actions. The gap appears when the best action is too coarse to reveal which evidence state produced it, which we demonstrate via a multi-round separation using a chained parities task. A warm-up example for one-round, where two posterior states induce the same best action but different probabilities, is included in Appendix B. The chained-parity task is intended as a stylized abstraction of general multi-round reasoning problems. In particular, many reasoning problems can be represented as a computation over a chain or graph of interdependent states: each state represents an intermediate reasoning step that incorporates new evidence towards solving the problem. This structure appears, for instance, in multi-hop or inductive reasoning, where intermediate facts are composed along a graph (Yang et al., 2018; Trivedi et al., 2022; Sinha et al., 2019); and in proof-style reasoning, where intermediate claims support later ones (Tafjord et al., 2021; Dalvi et al., 2021). In the chained-parity task, each “prefix parity" represents an intermediate state, and the next bit in a bitstring is the evidence needed to advance the chain (Figure 2). We are interested in such problems in collaborative settings, where no single agent observes all information needed to perform the reasoning task, and each agent refines its prediction by using information supplied by the other. We will show that probability messages can preserve a sufficient summary of the accumulated state, allowing each round to incorporate one new piece of private information, whereas action messages can collapse intermediate states and thereby prevent later information from being aggregated. Chained-parity task. We now define the task. We consider a binary action space =0,1A=\0,1\. Our task is parameterized by the number of rounds K≥1K≥ 1; for each value of K, the joint information space consists of K independent uniform bits b1,…,bKb_1,…,b_K in −1,+1\-1,+1\. Let dA:=⌈K/2⌉d_A:= K/2 and dB:=⌊K/2⌋d_B:= K/2 . Alice and Bob observe the odd- and even-indexed bits as fixed-length vectors: xA:=(b1,b3,…,b2dA−1)∈−1,+1dA,xB:=(b2,b4,…,b2dB)∈−1,+1dB.x_A:=(b_1,b_3,…,b_2d_A-1)∈\-1,+1\^d_A, x_B:=(b_2,b_4,…,b_2d_B)∈\-1,+1\^d_B. Figure 2: Chained-parity dependency structure. Define the prefix parity, the ±1± 1-valued product (equivalently, the XOR) of the first j bits, S0:=1,Sj:=∏ℓ=1jbℓfor j=1,…,K.S_0:=1, S_j:= _ =1^jb_ j=1,…,K. Conditional on x=(xA,xB)x=(x_A,x_B), the target action a⋆a is a Bernoulli random variable with parameter p⋆:=12+∑j=1KαjSj,p := 12+ _j=1^K _jS_j, which we call the full-information posterior probability of a⋆=1a =1. Throughout this section, p⋆p denotes this random variable, a deterministic function of the bit vector b=(b1,…,bK)b=(b_1,…,b_K). The weights α1,…,αK _1,…, _K are positive and satisfy ∑j=1Kαj<1/2 _j=1^K _j<1/2, which keeps p⋆∈(0,1)p ∈(0,1). Define h⋆:=p⋆≥12∈0,1h :=1\p ≥ 12\∈\0,1\, the Bayes-optimal action under 00–11 loss. Because each term αjSj _jS_j with j≥2j≥ 2 depends on both agents’ bits (Figure 2), no agent can evaluate p⋆p alone. Communication protocol. At round k, Alice speaks if k is odd and Bob speaks if k is even; write this speaker as σ(k)∈A,Bσ(k)∈\A,B\. Thus the round-k speaker observes bkb_k. When Alice and Bob communicate probabilities, define p0:=1/2p_0:=1/2 and let the speaker’s Bayes posterior probability that a⋆=1a =1, given their own features and the previous probability message, be pk:=Pr(a⋆=1|xσ(k),pk−1)∈[0,1].p_k:= (a =1\, |\,x_σ(k),\,p_k-1 )∈[0,1]. The probability communicated is p^k=pk p_k=p_k. When actions are communicated instead, let p~k p_k be the analogous Bayes posterior computed from the speaker’s own features and the public action transcript so far; the speaker’s action that they communicate to the other player will then be their best response, a^k=p~k≥12∈0,1. a_k=1\ p_k≥ 12\∈\0,1\. The distinction is that pkp_k can preserve how strongly the speaker favors an action, while a^k a_k keeps only the sign of that preference. Later, we also consider how information aggregation is affected when the communicated probability p^k p_k is biased transformation of the Bayes posterior pkp_k. Information aggregation with probabilities. We now add the condition that makes the previous probability message a sufficient scalar summary of the parities revealed so far. Assumption 3.1. Distinct bit prefixes (S1,…,Sk)∈−1,+1k(S_1,…,S_k)∈\-1,+1\^k yield distinct partial sums ∑j≤kαjSj _j≤ k _jS_j for each k≤Kk≤ K (e.g. αj=2−j−1 _j=2^-j-1). The distinct-partial-sums condition ensures that a scalar probability message identifies the prefix parities already revealed. Therefore the previous probability message is not merely a confidence score; it is an invertible summary of the information accumulated so far. This lets the probability exchange advance one message at a time: pk=pk−1+αkSk=12+∑j≤kαjSj.p_k=p_k-1+ _kS_k= 12+ _j≤ k _jS_j. By Assumption 3.1, the previous scalar message pk−1p_k-1 identifies the prefix (S1,…,Sk−1)(S_1,…,S_k-1); the round-k speaker also observes bkb_k, and hence determines Sk=Sk−1bkS_k=S_k-1b_k. All later parity terms contain an unseen bit and have conditional mean zero. Since pkp_k is a Bayes posterior conditioned on the speaker’s information and the previous probability message, the probabilities communicated satisfy conversation calibration in the sense of Definition 2.3. Theorem 3.2 (Probability exchange aggregates information). In the chained-parity model, under Assumption 3.1, when probabilities are communicated, the round-k message equals pk=12+∑j≤kαjSjp_k= 12+ _j≤ k _jS_j for every k≤Kk≤ K; in particular pK=p⋆p_K=p . The round-k excess squared loss [(a⋆−pk)2]−[(a⋆−p⋆)2]E[(a -p_k)^2]-E[(a -p )^2] equals ∑j>kαj2 _j>k _j^2 and decreases by αk2 _k^2 each round, so after K rounds the agents attain the full-information Bayes risk [(a⋆−p⋆)2]E[(a -p )^2]. Proof sketch. The recurrence above gives pk=1/2+∑j≤kαjSjp_k=1/2+ _j≤ k _jS_j by induction, so pK=p⋆p_K=p . At any k<Kk<K, pkp_k differs from p⋆p by the unrevealed tail ∑j>kαjSj _j>k _jS_j. Distinct parities are orthogonal, so the excess squared loss is [(p⋆−pk)2]=∑j>kαj2E[(p -p_k)^2]= _j>k _j^2, and the one-round improvement is αk2 _k^2. Information loss with actions. By contrast, the action exchange can collapse all later evidence states to the same first action. Theorem 3.3 (Action exchange transmits only the first bit). In the chained-parity model, assume K≥2K≥ 2 and α1>α2 _1> _2. When actions are exchanged, every round-k message equals b1=+11\b_1=+1\, so the induced decision is constant in k. In particular, for K=3K=3 and α=(0.20,0.15,0.10)α=(0.20,0.15,0.10), this decision disagrees with the full-information Bayes action h⋆h on an event of probability 1/41/4. Figure 3: Squared loss of action vs probability exchange over 55 rounds on chained parities. Learned probability communication attains the theoretical optimum. Proof sketch. The action message keeps only the sign of the speaker’s current posterior and discards the magnitude. Alice’s first posterior is 1/2+α1b11/2+ _1b_1, so her action message is b1=+11\b_1=+1\. If Alice speaks later, she still lacks b2b_2, so her posterior again has sign b1b_1. If Bob speaks, he can use b2b_2, but later terms average out and his posterior is 1/2+α1b1+α2b1b2=1/2+b1(α1+α2b2)1/2+ _1b_1+ _2b_1b_2=1/2+b_1( _1+ _2b_2). Since α1>α2 _1> _2, this posterior also has sign b1b_1. Thus every action message repeats the first bit and no later bit is transmitted. For the displayed K=3K=3 coefficients, on the event b2=−1,b3=+1\b_2=-1,b_3=+1\, the full posterior satisfies p⋆−1/2=b1(α1−α2−α3)<0p -1/2=b_1( _1- _2- _3)<0, so h⋆h is the opposite of the action-channel decision; this event has probability 1/41/4. Empirical validation. We validate this separation with trained transformers on the same chained-parity task (Appendix E for details). Figure 3 shows learned probability messages track the theoretical loss curve, while learned action messages stall as predicted. 4 When do probability reports need calibration? Theorem 3.2 assumes the round-k speaker transmits its Bayes posterior pkp_k exactly. In practice, reported probabilities may be distorted. One way to model this failure is to combine two deviations that are well-documented in LLMs: global miscalibration of confidence (Zhao et al., 2021; Xiong et al., 2024), where stated probabilities are systematically too extreme or too mild, and sycophancy (Perez et al., 2023; Sharma et al., 2024), where an agent’s report is pulled toward the previous speaker’s report regardless of its own evidence. We analyze a single round of such distortion: the previous agent is calibrated and sends the ideal pk−1p_k-1, while the round-k agent outputs a biased report, p^k=12+c(pk−12)+λ(pk−1−12), p_k= 12+c (p_k- 12 )+λ (p_k-1- 12 ), (1) with (c,λ)(c,λ) chosen so that p^k∈[0,1] p_k∈[0,1]. The parameter c>0c>0 controls the confidence scale (c=1c=1 is calibrated, c>1c>1 overconfident, c<1c<1 underconfident), and λ∈ℝλ controls the strength of sycophantic anchoring to the previous report. This illustrates the broader problem: raw probability reports need not be reliable objects for the next agent to update on. To recover calibrated messages, we can learn the conditional label distribution from the communicated probabilities themselves. Theorem 4.1 (Post-hoc calibration recovers the prediction guarantee). In the chained parity model, suppose the previous message is the ideal posterior pk−1p_k-1. For any c>0c>0 and λ∈ℝλ so that p^k∈[0,1] p_k∈[0,1], let Z=(p^k,pk−1)Z=( p_k,p_k-1). If the predictor class contains the conditional label distribution, then training a predictor h to predict a⋆a from Z using a strictly proper loss yields, at the population optimum, the one-step post-hoc forecast h⋆(p^k,pk−1):=Pr(a⋆=1∣p^k,pk−1)h ( p_k,p_k-1):= (a =1 p_k,p_k-1) which recovers the posterior: h⋆(p^k,pk−1)=pkh ( p_k,p_k-1)=p_k. Moreover, the learned forecast is conversation-calibrated. Applied inductively, with each previous calibrated message equal to the corresponding ideal posterior, this recovers the guarantee of Theorem 3.2 for any (c,λ)(c,λ). Proof sketch. A strictly proper loss is minimized at the true conditional label distribution, so the population optimum satisfies h⋆(Z)=Pr(a⋆=1∣Z)h (Z)= (a =1 Z). Since c>0c>0, observing (p^k,pk−1)( p_k,p_k-1) in (1) determines pkp_k; the unrevealed tail still has conditional mean zero given these messages. Therefore Pr(a⋆=1∣p^k,pk−1)=pk (a =1 p_k,p_k-1)=p_k. Finally, because Z includes the previous forecast, the tower property gives Pr(a⋆=1∣h⋆(Z),pk−1)=h⋆(Z), (a =1 h (Z),p_k-1)=h (Z), so the learned forecast is cross-calibrated with respect to pk−1p_k-1. Full details are in Appendix D. The affine form in (1) is only a convenient example. The same conclusion holds for any distortion p^k=F(pk,pk−1) p_k=F(p_k,p_k-1) such that, after fixing pk−1p_k-1, the map pk↦F(pk,pk−1)p_k F(p_k,p_k-1) is invertible on the possible round-k posteriors. The gap from calibration is already visible in the first two rounds: if a receiver treats a biased report as a valid posterior and projects it to the nearest possible message, the first bit can be decoded correctly while the second bit may be flipped by confidence or anchoring bias. Appendix D formalizes this. A post-hoc calibration algorithm. The above observation suggests a natural training procedure for collaborative agents that communicate probabilistic predictions. In each round, the active agent produces a raw forecast from its own observation and the previous message. A post-hoc map then recalibrates this forecast using labelled transcripts and the previous message as inputs. This yields an iterative procedure in which agents alternately improve their predictive accuracy while aligning their communicated probabilities through conversation calibration. We summarize this procedure in Algorithm 1. Algorithm 1 post-hoc calibration for probability communication 1: Data (xiA,xiB,ai⋆)i=1n\(x_i^A,x_i^B,a_i )\_i=1^n, rounds K, base protocols π~k π_k producing raw forecasts, strictly proper loss ℓ 2: Initialize p^0,i=∅ p_0,i= for all i=1,…,ni=1,…,n 3: for k=1,…,Kk=1,…,K do 4: Let s=σ(k)s=σ(k) be the round-k speaker 5: For each example i=1,…,ni=1,...,n, run the base protocol to obtain raw forecasts p~k,i=π~k(xis,p^k−1,i). p_k,i= π_k(x_i^s, p_k-1,i). 6: Fit a post-hoc calibration map using only the raw forecast and previous calibrated forecast: gk∈argmin∑i=1ng∈kℓ(g(p~k,i,p^k−1,i),ai⋆).g_k∈ _g _k _i=1^n \! (g( p_k,i, p_k-1,i),a_i ). 7: For each example i=1,…,ni=1,...,n, set the calibrated round-k message p^k,i=gk(p~k,i,p^k−1,i). p_k,i=g_k( p_k,i, p_k-1,i). 8: end for 9: return Calibrators g1,…,gKg_1,…,g_K 5 Maze experiments with learned and pretrained agents We next move beyond chained parities to test these communication principles on a more natural decision problem: collaborative maze-solving. The task, proposed by Davidson et al. (2025) to test collaborative capabilities of language models, preserves the same core structure: agents have partial information and must aggregate information over multiple rounds before choosing an action. However, the underlying object of uncertainty is now much more complex: agents must form and update beliefs about the correct next move by reasoning over partially observed paths. This setting therefore lets us test whether the lessons from the chained parities example extend to richer collaborative problems. Figure 4: (R1) Action performance stagnates; communicating probabilities increases performance gradually. Figure 5: (R2) Global miscalibration and sycophantic anchoring cause performance to drop over rounds, while post-hoc recalibration partially recovers performance under self-miscalibration and cross-calibration recovers nearly all performance when both biases are present. Maze task. The maze-solving task consists of a dataset of N×N× N mazes, each with a fixed start state, fixed end state, and cells denoting either a path or a wall, see Figure 1. Mazes are sampled according to a wall-density parameter, which controls the expected fraction of cells that are walls. In our collaborative setup, each agent observes only a partial map of the maze with half of the cells hidden. Together, the two agents’ maps recover the full maze. Our experimental setup follows the primary setting studied by Davidson et al. (2025). We use N=6N=6, a wall density of 30%. The start state is in the top left corner and the end state in the bottom right corner, which creates a directional bias where some actions are more likely than others. Unlike Davidson et al. (2025), we restrict attention to mazes with a single correct solution for ease of evaluation. An example maze (and the corresponding two views) are presented in Figure 12. 5.1 Controlled transformer experiments We first study the problem in a controlled setup, where, as in Section 3, we train a sequence of transformers that communicate across rounds. Transformer setup. We train small transformers on a supervised next-move prediction task. Each example is represented as a partial-view maze string with the @ symbol denoting the current position, along with any previously communicated message. The target label is the next move along the solution path. Full experimental details are in Appendix E. We report maze success rate, defined as the fraction of mazes for which the model predicts every move in the solution path correctly. (R1) Probability messages improve controlled maze-solving. Figure 5 shows that trained models under probability communication indeed outperform trained models under action communication. Moreover, it shows that over four rounds of communication, maze success rate improves consistently when agents communicate probabilities; this is not the case for action communication. In Appendix F we give examples of mazes where communicating probabilities over multiple rounds converge to the correct answer. (R2) Calibration repairs biased transformer messages. Next, we study the two biases that conversation calibration is designed to mitigate when agents communicate probabilities: global miscalibration and sycophantic anchoring. Rather than communicating the transformer probabilities directly, we first distort them according to Equation 1, and then optionally apply a post-hoc debiasing protocol. The debiasing model is a single-layer network trained with cross-entropy loss against the true label. We compare self-calibration, which uses only the current transformer’s probabilities, with conversation calibration, which uses both the current and previous round’s probabilities. The unbiased probability baseline improves monotonically over four rounds; see Figure 5. In contrast, global miscalibration alone and global miscalibration combined with anchoring cause performance to collapse and deteriorate over rounds. Self-calibration recovers a substantial fraction of the lost success under global miscalibration, but its imperfect corrections still accumulate through the conversation. When both biases are present, conversation calibration recovers nearly all of the baseline performance. Thus, cross-calibrating against the previous round’s probabilities can recover approximately unbiased messages and substantially improve downstream maze success. 5.2 Pretrained LLM experiments We now test if the same principle holds for large-scale, pretrained language models on the maze task. LLM setup. We use the maze task described in Section 5 and evaluate four models of varying strengths: GPT-4.1-mini, GPT-5, GPT-5.4-nano, and GPT-5.4-mini. We allow models to generate reasoning (up to 2048 tokens). We consider three communication protocols: actions, verbalized probabilities, or sampled probabilities. In the action exchange protocol, each agent communicates the action chosen in its response. In the verbalized probability exchange protocol, each agent communicates the probability vector reported in its response. In the sampled probability exchange protocol, we sample M independent responses from the model, and the message communicated is the empirical distribution over the answers. For both the verbalized and sampled probability exchange protocol, we measure the accuracy of the answer assigned the highest probability value. Full prompts are in Appendix E.3. All results are over 30 fixed mazes with 10 rollouts per maze. For maze success rates, we report means and 90%90\% bootstrapped confidence intervals over all rollouts, computed as a pooled variance across mazes. We compute conversation calibration losses separately for each of the 10 rollouts, again pooling moves from all 30 mazes, and report the mean and 90%90\% bootstrapped confidence intervals across rollouts. (a) Maze success rate. (b) Conversation calibration loss. Figure 7: (R3) We train one-hidden-layer MLP calibrators according to Algorithm 1 on a set of 100 mazes and report outcomes on a validation set of 30 mazes with 10 rollouts each. We report the success rate (top) as well as the calibration loss (bottom). For success rate, we also include the full-information solo baseline. Bars that do not appear indicate zero success. Post-hoc calibration of verbalized probabilities increases success and lowers conversation calibration loss. Details of conversation calibration loss computation is in Appendix E.3. (R3) Calibration makes verbalized LLM probabilities useful. In our first experiment, we highlight the value of conversation calibration for verbalized probabilities. Recent work has shown that the probabilities verbalized by LLMs often fail to faithfully reflect the models’ underlying uncertainty (Xiong et al., 2024; Kapoor et al., 2024). To illustrate the consequences of this miscalibration in a collaborative setting, we directly compare action-based and probability-based communication using prompted LLMs. We then apply post-hoc conversation calibration to the verbalized probabilities to test whether the lost information can be recovered through simple debiasing. In Figure 7(a), we report the success rates of solving the mazes across multiple models and communication modes. We find that verbalized probability exchange performs similarly to, or worse than, action exchange for GPT-5.4-nano, GPT-5.4-mini, and GPT-5, and yields only a small improvement for GPT-4.1-mini. Single verbal reports of uncertainty therefore do not appear to faithfully represent the model’s uncertainty in a form that improves collaboration. Applying Algorithm 1 to verbalized probabilities consistently improves performance across all models. In particular, mean maze success rates at least double after four rounds of communication relative to the base verbalized probability protocol. These gains suggest that communicated uncertainty can support collaboration when the exchanged probabilities are first adjusted to account for model-specific miscalibration. To illustrate that this improved performance is in fact correlated with (conversation) calibration, we show the corresponding calibration losses of the verbalized probabilities before and after post-processing in Figure 7(b). In the first round, we report self calibration loss and in consecutive rounds we report conversation calibration loss. For all four models, post-hoc calibration leads to a significant decrease in calibration loss, supporting our hypothesis that conversation calibration is in fact a driving factor in improving communication in our setting. We note that final performance is far below what can be achieved by training a next-move predictor on the maze data, as shown in the previous section. This gap can be attributed to three factors. First, the LLMs were not explicitly trained on mazes like ours, and so their prior knowledge this task is limited. Second, the calibration procedure does not help the model re-interpret information: it is trained only on the communicated probabilities and therefore does not introduce new knowledge specific to each maze that is absent from what is communicated. If the verbalized probabilities carry little information, calibration cannot alleviate that. Third, the LLM must interpret probabilities in-context, and it may not reason reliably about uncertainty information. Whereas prior work has highlighted the benefits of calibration in a single-agent setting (Zhao et al., 2021), our results point to the need for improved uncertainty calibration in multi-agent contexts. Figure 8: (R4) Post-hoc calibration can learn corrections beyond the marginal action frequencies. On GPT-5.4-nano, the calibrator performs similarly to a naive baseline that replaces verbalized predictions favoring rare actions with the marginal action distribution. On GPT-5, the calibrator outperforms this baseline after multiple rounds of communication. (R4) What does the post-hoc calibrator learn? Next, to better understand where the calibrator’s gains come from, we investigate what the post-hoc calibration procedure learns, and in particular whether it learns anything beyond the marginal action frequencies. Because our mazes start from the top left, the correct action is down or right 97% of the time (with roughly equal frequencies on down and right), while left or up only 3% of the time. Since the calibrator is trained on the distribution of correct actions, it could exploit this imbalance by simply learning a correction that suppresses predictions on the rare actions. We test this hypothesis with a naive rare-action correction baseline. Whenever the model’s verbalized probability vector assigns the highest probability to up or left, we replace it with the vector assigning probability 0.5 to each of down and right; otherwise, we leave the prediction unchanged. Note that this baseline uses only the marginal action frequencies and does not depend on the models’ reported probabilities beyond the argmax. Figure 8 shows the results. For GPT-5.4-nano, the naive baseline performs similarly to the calibrator, indicating that much of the calibrator’s gains can be explained by correcting the mode bias. For GPT-5, the calibrator slightly outperforms the naive baseline. This suggests that the calibration procedure learns corrections that cannot simply be reduced to suppressing rare actions and that LLMs can sometimes leverage nuanced probabilities to improve downstream performance. Further work on analyzing and improving how LLMs output and interpret calibrated probabilities offers the opportunity to unlock the full benefits of conversation calibration. (R5) Sampled probabilities only partially elicit model uncertainty. Having established that verbalized probabilities are unreliable, we next compare against a stronger elicitation baseline: empirical probabilities from multiple sampled rollouts. This protocol estimates the model’s action distribution directly from repeated responses, but is more expensive than a single verbalized probability report. We compare sampled against verbalized-probability exchange as well as post-hoc calibration. Figure 9: (R5) Our post-hoc calibration procedure matches or outperforms sampled probabilities constructed from M=10M=10 sampled responses. Figure 9 shows that on GPT-4.1-mini, sampled probability exchange improves over verbalized probability exchange and is within variance of our post-hoc calibration approach. On GPT-5.4-nano, sampled probability exchange performs similarly to verbalized probability exchange. Here, post-hoc calibration consistently achieves higher mean success rates. These results suggest that this simple post-hoc procedure can compete with a sampling-based uncertainty estimate at a fraction of the cost, since it only requires one rollout. Figure 10: (R6) Histogram of maximum assigned probabilities and corresponding argmax-action accuracy under verbalized and sampled probability exchange. For GPT-4.1-mini, sampled probabilities are better calibrated than verbalized probabilities and lead to stronger downstream performance. For GPT-5.4-nano, sampled probabilities are more overconfident, while verbalized probabilities are comparatively better calibrated. (R6) Calibration explains when sampled probabilities help. GPT-4.1-mini behaves as expected: it performs poorly with verbalized probabilities but improves with sampled probabilities. For GPT-5.4-nano, however, sampled probabilities are on par with verbalized probabilities. This might be surprising at first glance, since we would expect the sampled probability measure to perform better according to our hypothesis. To understand why this might happen, we dig deeper into the distribution of both the verbalized and sampled probabilities in Figure 10. We plot a histogram of maximum probability values under the verbalized and sampled probability exchange protocols, together with the accuracy of the corresponding argmax action. For GPT-4.1-mini, the verbalized and sampled top-choice confidences are similarly miscalibrated across most bins in both rounds 11 and 22. However, in round 22, sampled probabilities more often assign a maximum probability of 11, and these predictions are reasonably well-calibrated. By contrast, verbalized probabilities continue to be overconfident. As a result, sampled probabilities achieve higher accuracy in round 22. For GPT-5.4-nano, we observe a similar pattern in the 1.01.0 probability bin, but sampled probabilities do not outperform verbalized probabilities overall. This can be attributed to the fact that, outside the 1.01.0 probability bin, the sampled probabilities are highly overconfident. This contrast further highlights the close relationship between calibration and downstream performance. The behavior of both models is consistent with broader trends in LLMs. As model capability improves, LLMs appear to become better at expressing uncertainty through verbalized probabilities (Xiong et al., 2024), which may help explain GPT-5.4-nano’s improved verbal calibration. One possible explanation is that GPT-5.4-nano’s sampled rollouts reflect stronger commitment due to more alignment training such as RLHF. This is consistent with prior work linking RLHF-style alignment to sharpened output distributions and increased overconfidence (Leng et al., 2025). Figure 11: (R7) Communicating more information does not always help. Solely communicating probabilities produced by our post-hoc calibration procedure leads to higher success than communicating the full response. (R7) Communicating more information does not necessarily improve collaboration. Finally, using GPT-4.1-mini and GPT-5.4-nano, we compare against an unconstrained communication baseline, in which each agent receives the previous agent’s full response, including any generated reasoning. This is the setup studied by Davidson et al. (2025). For GPT-4.1-mini, we use the same prompt as in our other experiments, which asks the model for its uncertainty; therefore the communicated full response includes both the model’s reasoning and verbalized probabilities. For GPT-5.4-nano, we slightly modify the prompt to also explicitly have the model tell us what to communicate to the other agent, as otherwise it’s reasoning is hidden inside the API. We provide the modified prompt in Appendix E. The results are found in Figure 11. For both models, we see that unrestricted communication performs poorly as its success rate across all rounds is close to zero. This failure is unlikely to reflect a basic inability to parse or reason about any maze structure the communicated message may contain, since GPT-5.4-nano solves more than 85%85\% of the mazes when given the full maze directly (Figure 7). Rather, this experiment demonstrates that simply providing the next agent with more information does not necessarily improve collaboration, and probability exchange can be more effective between agents than unconstrained natural-language communication, especially when long or noisy contexts make full-response communication difficult to use. Acknowledgements The authors gratefully acknowledge support from a Google PhD Fellowship, the Simons Collaboration on Algorithmic Fairness, an Amazon Research Award, and the NSF EnCore Tripods Institute. SG was additionally supported by NSF CAREER #2543725. MH was partially supported by DARPA grant #HR00112420305, the U.S. National Science Foundation under Cooperative Agreement No. 2433450. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the U.S. army or the U.S. National Science Foundation. MH is also a Novo Nordisk Fellow supported by the MIT-Novo Nordisk Artificial Intelligence Postdoctoral Fellows Program. References Aaronson [2005] Scott Aaronson. The complexity of agreement. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 634–643, 2005. Aumann [1976] Robert J. Aumann. Agreeing to Disagree. The Annals of Statistics, 4(6):1236 – 1239, 1976. doi: 10.1214/aos/1176343654. URL https://doi.org/10.1214/aos/1176343654. Aumann and Hart [2006] Robert J Aumann and Sergiu Hart. Agreeing on decisions. Unpublished manuscript, The Einstein Institute of Mathematics, Jerusalem, Israel, http://math. huji. ac. il/˜ hart/papers/agree. pdf (Last accessed: 17/04/2015), 2006. Cemri et al. [2025] Mert Cemri, Melissa Z Pan, Shuyi Yang, Lakshya A Agrawal, Bhavya Chopra, Rishabh Tiwari, Kurt Keutzer, Aditya Parameswaran, Dan Klein, Kannan Ramchandran, Matei Zaharia, Joseph E. Gonzalez, and Ion Stoica. Why do multi-agent LLM systems fail? In The Thirty-ninth Annual Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2025. Chan et al. [2024] Chi-Min Chan, Weize Chen, Yusheng Su, Jianxuan Yu, Wei Xue, Shanghang Zhang, Jie Fu, and Zhiyuan Liu. ChatEval: Towards better LLM-based evaluators through multi-agent debate. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=FQepisCUWu. Chen et al. [2024] Justin Chen, Swarnadeep Saha, and Mohit Bansal. ReConcile: Round-table conference improves reasoning via consensus among diverse LLMs. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar, editors, Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics, pages 7066–7085, Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10.18653/v1/2024.acl-long.381. URL https://aclanthology.org/2024.acl-long.381/. Collina et al. [2025] Natalie Collina, Surbhi Goel, Varun Gupta, and Aaron Roth. Tractable agreement protocols. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1532–1543, 2025. Collina et al. [2026] Natalie Collina, Ira Globus-Harris, Surbhi Goel, Varun Gupta, Aaron Roth, and Mirah Shi. Collaborative prediction: Tractable information aggregation via agreement. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4712–4798. SIAM, 2026. Dalvi et al. [2021] Bhavana Dalvi, Peter Jansen, Oyvind Tafjord, Zhengnan Xie, Hannah Smith, Leighanna Pipatanangkura, and Peter Clark. Explaining answers with entailment trees. In Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih, editors, Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 7358–7370, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics. doi: 10.18653/v1/2021.emnlp-main.585. URL https://aclanthology.org/2021.emnlp-main.585/. Das et al. [2019] Abhishek Das, Théophile Gervet, Joshua Romoff, Dhruv Batra, Devi Parikh, Mike Rabbat, and Joelle Pineau. TarMAC: Targeted multi-agent communication. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1538–1546. PMLR, 09–15 Jun 2019. URL https://proceedings.mlr.press/v97/das19a.html. Davidson et al. [2025] Tim R Davidson, Adam Fourney, Saleema Amershi, Robert West, Eric Horvitz, and Ece Kamar. The collaboration gap. arXiv preprint arXiv:2511.02687, 2025. Dawid [1982] A. P. Dawid. The well-calibrated bayesian. Journal of the American Statistical Association, 77(379):605–610, 1982. doi: 10.1080/01621459.1982.10477856. Desai and Durrett [2020] Shrey Desai and Greg Durrett. Calibration of pre-trained transformers. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu, editors, Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, pages 295–302, Online, November 2020. Association for Computational Linguistics. doi: 10.18653/v1/2020.emnlp-main.21. URL https://aclanthology.org/2020.emnlp-main.21/. Du et al. [2024] Yilun Du, Shuang Li, Antonio Torralba, Joshua B. Tenenbaum, and Igor Mordatch. Improving factuality and reasoning in language models through multiagent debate. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 11733–11763. PMLR, 21–27 Jul 2024. URL https://proceedings.mlr.press/v235/du24e.html. Eisenstein et al. [2026] Jacob Eisenstein, Fantine Huot, Adam Fisch, Jonathan Berant, and Mirella Lapata. Mt-pingeval: Evaluating multi-turn collaboration with private information games, 2026. URL https://arxiv.org/abs/2602.24188. Farquhar et al. [2024] Sebastian Farquhar, Jannik Kossen, Lorenz Kuhn, and Yarin Gal. Detecting hallucinations in large language models using semantic entropy. Nature, 630(8017):625–630, 2024. doi: 10.1038/s41586-024-07421-0. URL https://w.nature.com/articles/s41586-024-07421-0. Foerster et al. [2016] Jakob N. Foerster, Ioannis Alexandros Assael, Nando de Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. In Advances in Neural Information Processing Systems, volume 29, 2016. URL https://proceedings.neurips.c/paper/2016/hash/c7635bfd99248a2cdef8249ef7bfbef4-Abstract.html. Foster and Vohra [1998] Dean P. Foster and Rakesh V. Vohra. Asymptotic calibration. Biometrika, 85(2):379–390, 1998. doi: 10.1093/biomet/85.2.379. Frongillo et al. [2023] Rafael Frongillo, Eric Neyman, and Bo Waggoner. Agreement implies accuracy for substitutable signals. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 702–733, 2023. Geanakoplos and Polemarchakis [1982] John D Geanakoplos and Heraklis M Polemarchakis. We can’t disagree forever. Journal of Economic theory, 28(1):192–200, 1982. Guo et al. [2017] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1321–1330. PMLR, 06–11 Aug 2017. URL https://proceedings.mlr.press/v70/guo17a.html. Guo et al. [2024] Taicheng Guo, Xiuying Chen, Yaqi Wang, Ruidi Chang, Shichao Pei, Nitesh V. Chawla, Olaf Wiest, and Xiangliang Zhang. Large language model based multi-agents: A survey of progress and challenges. In Kate Larson, editor, Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI-24, pages 8048–8057. International Joint Conferences on Artificial Intelligence Organization, August 2024. doi: 10.24963/ijcai.2024/890. URL https://doi.org/10.24963/ijcai.2024/890. Survey Track. Jiang et al. [2021] Zhengbao Jiang, Jun Araki, Haibo Ding, and Graham Neubig. How can we know when language models know? on the calibration of language models for question answering. Transactions of the Association for Computational Linguistics, 9:962–977, 2021. doi: 10.1162/tacl_a_00407. URL https://aclanthology.org/2021.tacl-1.57/. Kadavath et al. [2022] Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zac Hatfield-Dodds, Nova DasSarma, Eli Tran-Johnson, Scott Johnston, Sheer El-Showk, Andy Jones, Nelson Elhage, Tristan Hume, Anna Chen, Yuntao Bai, Sam Bowman, Stanislav Fort, Deep Ganguli, Danny Hernandez, Josh Jacobson, Jackson Kernion, Shauna Kravec, Liane Lovitt, Kamal Ndousse, Catherine Olsson, Sam Ringer, Dario Amodei, Tom Brown, Jack Clark, Nicholas Joseph, Ben Mann, Sam McCandlish, Chris Olah, and Jared Kaplan. Language models (mostly) know what they know, 2022. URL https://arxiv.org/abs/2207.05221. Kapoor et al. [2024] Sanyam Kapoor, Nate Gruver, Manley Roberts, Katherine M. Collins, Arka Pal, Umang Bhatt, Adrian Weller, Samuel Dooley, Micah Goldblum, and Andrew Gordon Wilson. Large language models must be taught to know what they don’t know. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. Karpathy [2022] Andrej Karpathy. NanoGPT. https://github.com/karpathy/nanoGPT, 2022. Kearns et al. [2026] Michael Kearns, Aaron Roth, and Emily Ryu. Networked information aggregation via machine learning. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4799–4845. SIAM, 2026. Kuhn et al. [2023] Lorenz Kuhn, Yarin Gal, and Sebastian Farquhar. Semantic uncertainty: Linguistic invariances for uncertainty estimation in natural language generation. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=VD-AYtP0dve. Leng et al. [2025] Jixuan Leng, Chengsong Huang, Banghua Zhu, and Jiaxin Huang. Taming overconfidence in LLMs: Reward calibration in RLHF. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=l0tg0jzsdL. Li et al. [2023] Huao Li, Yu Quan Chong, Simon Stepputtis, Joseph Campbell, Dana Hughes, Charles Michael Lewis, and Katia P. Sycara. Theory of mind for multi-agent collaboration via large language models. In The 2023 Conference on Empirical Methods in Natural Language Processing, 2023. Lin et al. [2022] Stephanie Lin, Jacob Hilton, and Owain Evans. Teaching models to express their uncertainty in words. Transactions on Machine Learning Research, 2022. URL https://openreview.net/forum?id=8s8K2UZGTZ. Manakul et al. [2023] Potsawee Manakul, Adian Liusie, and Mark J. F. Gales. SelfCheckGPT: Zero-resource black-box hallucination detection for generative large language models. In Houda Bouamor, Juan Pino, and Kalika Bali, editors, Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 9004–9017, Singapore, December 2023. Association for Computational Linguistics. doi: 10.18653/v1/2023.emnlp-main.557. URL https://aclanthology.org/2023.emnlp-main.557/. Mielke et al. [2022] Sabrina J. Mielke, Arthur Szlam, Emily Dinan, and Y-Lan Boureau. Reducing conversational agents’ overconfidence through linguistic calibration. Transactions of the Association for Computational Linguistics, 10:857–872, 2022. doi: 10.1162/tacl_a_00494. URL https://aclanthology.org/2022.tacl-1.50/. Perez et al. [2023] Ethan Perez, Sam Ringer, Kamile Lukosiute, Karina Nguyen, Edwin Chen, Scott Heiner, Craig Pettit, Catherine Olsson, Sandipan Kundu, Saurav Kadavath, Andy Jones, Anna Chen, Benjamin Mann, Brian Israel, Bryan Seethor, Cameron McKinnon, Christopher Olah, Da Yan, Daniela Amodei, Dario Amodei, Dawn Drain, Dustin Li, Eli Tran-Johnson, Guro Khundadze, Jackson Kernion, James Landis, Jamie Kerr, Jared Mueller, Jeeyoon Hyun, Joshua Landau, Kamal Ndousse, Landon Goldberg, Liane Lovitt, Martin Lucas, Michael Sellitto, Miranda Zhang, Neerav Kingsland, Nelson Elhage, Nicholas Joseph, Noemi Mercado, Nova DasSarma, Oliver Rausch, Robin Larson, Sam McCandlish, Scott Johnston, Shauna Kravec, Sheer El Showk, Tamera Lanham, Timothy Telleen-Lawton, Tom Brown, Tom Henighan, Tristan Hume, Yuntao Bai, Zac Hatfield-Dodds, Jack Clark, Samuel R. Bowman, Amanda Askell, Roger Grosse, Danny Hernandez, Deep Ganguli, Evan Hubinger, Nicholas Schiefer, and Jared Kaplan. Discovering language model behaviors with model-written evaluations. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki, editors, Findings of the Association for Computational Linguistics: ACL 2023, pages 13387–13434, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10.18653/v1/2023.findings-acl.847. URL https://aclanthology.org/2023.findings-acl.847/. Sharma et al. [2024] Mrinank Sharma, Meg Tong, Tomasz Korbak, David Duvenaud, Amanda Askell, Samuel R. Bowman, Esin DURMUS, Zac Hatfield-Dodds, Scott R Johnston, Shauna M Kravec, Timothy Maxwell, Sam McCandlish, Kamal Ndousse, Oliver Rausch, Nicholas Schiefer, Da Yan, Miranda Zhang, and Ethan Perez. Towards understanding sycophancy in language models. In The Twelfth International Conference on Learning Representations, 2024. Sinha et al. [2019] Koustuv Sinha, Shagun Sodhani, Jin Dong, Joelle Pineau, and William L. Hamilton. CLUTRR: A diagnostic benchmark for inductive reasoning from text. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), 2019. Sukhbaatar et al. [2016] Sainbayar Sukhbaatar, arthur szlam, and Rob Fergus. Learning multiagent communication with backpropagation. 29, 2016. Tafjord et al. [2021] Oyvind Tafjord, Bhavana Dalvi, and Peter Clark. ProofWriter: Generating implications, proofs, and abductive statements over natural language. In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, 2021. Tian et al. [2023] Katherine Tian, Eric Mitchell, Allan Zhou, Archit Sharma, Rafael Rafailov, Huaxiu Yao, Chelsea Finn, and Christopher D Manning. Just ask for calibration: Strategies for eliciting calibrated confidence scores from language models fine-tuned with human feedback. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 2023. Trivedi et al. [2022] Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. Musique: Multihop questions via single-hop question composition. Transactions of the Association for Computational Linguistics, 10, 2022. Wang et al. [2023] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2023. Wei et al. [2022] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems, volume 35, 2022. Wilie et al. [2024] Bryan Wilie, Samuel Cahyawijaya, Etsuko Ishii, Junxian He, and Pascale Fung. Belief revision: The adaptability of large language models reasoning. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, 2024. Xiong et al. [2024] Miao Xiong, Zhiyuan Hu, Xinyang Lu, Yifei Li, Jie Fu, Junxian He, and Bryan Hooi. Can LLMs express their uncertainty? an empirical evaluation of confidence elicitation in LLMs. In The Twelfth International Conference on Learning Representations, 2024. Yang et al. [2018] Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. HotpotQA: A dataset for diverse, explainable multi-hop question answering. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, 2018. Zhao et al. [2021] Tony Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. Calibrate before use: Improving few-shot performance of language models. In Proceedings of the 38th International Conference on Machine Learning, 2021. Appendix A Additional Related Work Calibration, scoring rules, and agreement-based aggregation. Our use of probabilistic messages is closely related to the classical literature on calibrated forecasting. Dawid [1982] formalized the idea that a forecaster’s stated probabilities should match empirical frequencies, while Foster and Vohra [1998] showed that calibrated forecasting can be achieved constructively in repeated prediction. The theoretical backbone of our work also connects to agreement and information aggregation. Classical agreement results show that Bayesian agents with common priors cannot sustain common-knowledge disagreement [Aumann, 1976, Aumann and Hart, 2006], and that repeated exchange of beliefs can converge to agreement [Geanakoplos and Polemarchakis, 1982, Aaronson, 2005]. Recent work replaces ideal Bayesian assumptions with tractable calibration-style conditions [Collina et al., 2025, Collina et al., 2026, Kearns et al., 2026]. Frongillo et al. [2023] show that agreement need not imply accuracy without additional signal-structure assumptions. Our contribution is complementary: we study how these ideas behave in LLM-agent collaboration, and empirically compare action messages, raw probabilistic messages, sampled probabilities, and post-hoc conversation-calibrated probabilities. Uncertainty and calibration in language models. A large body of work shows that neural-network and language-model probabilities are not automatically calibrated. Guo et al. [2017] showed that modern neural networks can be substantially miscalibrated and that simple post-hoc temperature scaling can improve calibration. Desai and Durrett [2020] studied calibration in pretrained transformers such as BERT and RoBERTa, while Jiang et al. [2021] evaluated when generative language models’ confidence estimates align with correctness. Zhao et al. [2021] showed that few-shot language-model predictions can be biased by prompt artifacts and proposed contextual calibration to mitigate these effects. Recent work studies how to elicit uncertainty from large language models more directly. Kadavath et al. [2022] evaluate whether language models can predict their own correctness, finding that self-evaluation can be informative but is format- and scale-dependent. Lin et al. [2022] train models to express uncertainty in words, and Mielke et al. [2022] study whether conversational agents’ linguistic expressions of confidence are calibrated. Tian et al. [2023] compare confidence-elicitation strategies for RLHF-trained models, while Xiong et al. [2024] provide a broad empirical evaluation of verbalized, token-probability, and sampling-based confidence estimates. Kapoor et al. [2024] show that verbalized uncertainty in LLMs remains unreliable under prompting alone. These papers motivate our distinction between verbalized probabilities and probabilities that are calibrated for use by another agent in a conversation. In addition, work on sycophancy [Perez et al., 2023, Sharma et al., 2024] motivates our biased-report model, where an agent’s stated probability may be pulled toward a previous speaker’s report rather than reflecting only its private evidence. Sampling-based uncertainty and reasoning. Sampling multiple model outputs is another common way to estimate uncertainty. Chain-of-thought prompting [Wei et al., 2022] and self-consistency decoding [Wang et al., 2023] use multiple reasoning traces to improve single-agent reasoning by marginalizing over sampled answers. SelfCheckGPT [Manakul et al., 2023] uses consistency across sampled generations as a black-box signal for hallucination detection. Kuhn et al. [2023] and Farquhar et al. [2024] argue that uncertainty in language generation should often be measured over semantic equivalence classes rather than surface forms. Our sampled-probability protocol uses a related sampling signal, but for a different purpose: the empirical distribution over actions is communicated to another agent with complementary private information, rather than being used only to choose a single model’s final answer. Multi-agent LLM collaboration. Our maze experiments build on the collaborative maze-solving benchmark of Davidson et al. [2025], which demonstrates a “collaboration gap” between single-agent and multi-agent performance under partial observability. Eisenstein et al. [2026] study stylistically similar tasks to evaluate multi-agent LLM collaboration in partially observable settings. Other work studies multi-agent LLM interaction as a general reasoning or evaluation scaffold. Du et al. [2024] use multi-agent debate to improve factuality and reasoning, Chen et al. [2024] propose a round-table consensus procedure among diverse LLMs, and Chan et al. [2024] use multi-agent debate for LLM-based text evaluation. Guo et al. [2024] survey the broader literature on LLM-based multi-agent systems. Unlike these works, our agents have different private observations, and our main question is not whether discussion helps in aggregate, but which low-bandwidth message format preserves decision-relevant information. Learned communication in multi-agent reinforcement learning. There is also a large literature on learning communication protocols in cooperative multi-agent reinforcement learning. Foerster et al. [2016] introduce RIAL and DIAL, showing that agents can learn discrete or differentiable communication protocols in partially observable cooperative tasks. Sukhbaatar et al. [2016] propose CommNet, where agents learn continuous communication alongside their policies. Das et al. [2019] introduce TarMAC, which learns targeted communication by deciding both what to communicate and whom to address. Our work differs from this line by focusing on an interpretable communication channel—beliefs over actions—and by identifying conversation calibration as the condition under which such messages can be reliably used by another agent. Appendix B Warm-Up Example for Section 3 We include a two-bit example showing that best-action communication can discard information that is preserved by probability communication. Let the state y=(y1,y2)y=(y_1,y_2) be drawn from 00,01,10,11\00,01,10,11\ with Pr(y=00)=14−ϵ,Pr(y=01)=Pr(y=10)=Pr(y=11)=14+ϵ3, (y=00)= 14-ε, (y=01)= (y=10)= (y=11)= 14+ ε3, where 0<ϵ<1/40<ε<1/4. Alice observes y1y_1, Bob observes y2y_2, and the correct action a⋆=f∗(y)a =f^*(y) is y00011011f∗(y)a2a1a1a1. array[]c|cy&00&01&10&11\\ f^*(y)&a_2&a_1&a_1&a_1. array Thus a1a_1 is correct except in the single state 0000. Suppose Alice speaks first and may send only her Bayes-optimal action. If y1=1y_1=1, she knows the state is either 1010 or 1111, so a1a_1 is certainly correct: Pr(a⋆=a1∣y1=1)=1 (a =a_1 y_1=1)=1. If y1=0y_1=0, Alice compares the two states 0000 and 0101, and still strictly prefers a1a_1: Pr(a⋆=a1∣y1=0)=Pr(y=01∣y1=0)=(14+ϵ3)/(12−2ϵ3)>12. (a =a_1 y_1=0)= (y=01 y_1=0)= ( 14+ ε3 )/ ( 12- 2ε3 )> 12. Therefore, she sends the same action, a1a_1, no matter which bit she observes: The action message carries no information about y1y_1. Bob faces the same situation symmetrically, so an action-only conversation cannot identify the exceptional state 0000; the agents play a1a_1, which is correct with prior probability 3/4+ϵ3/4+ε. Under probability communication, Alice instead sends her posterior probability that a1a_1 is correct. This message equals 11 when y1=1y_1=1 and equals (14+ϵ3)/(12−2ϵ3)( 14+ ε3)/( 12- 2ε3) when y1=0y_1=0. These two values are distinct, so the probability message reveals her bit. Since Bob already observes y2y_2, he can identify the full state and report the correct action with probability one. The lesson is that the separation is not between actions and probabilities as syntactic objects, but between messages that preserve distinct posterior states and messages that collapse all evidence states inducing the same best action. Appendix C Proofs for Section 3 We start with a recurring observation used throughout. For shorthand, let uk:=∑j≤kαjSj,rk:=∑j>kαjSj,u_k:= _j≤ k _jS_j, r_k:= _j>k _jS_j, (2) with u0:=0u_0:=0 and r0:=p⋆−1/2r_0:=p -1/2, so that p⋆=1/2+uk+rkp =1/2+u_k+r_k for every k. Lemma C.1 (Conditional vanishing). Let G be a σ-algebra and suppose bib_i is independent of σ(,bℓ:ℓ≠i)σ(G,\b_ : ≠ i\) for some i∈[K]i∈[K]. For any random variable W that is a function of bℓ:ℓ≠i\b_ : ≠ i\, [biW∣]=[bi][W∣]=0E[b_iW ]=E[b_i]\,E[W ]=0. In particular, if J⊆[K]J [K] is nonempty and some i∈Ji∈ J is independent of σ(,bℓ:ℓ≠i)σ(G,\b_ : ≠ i\), then [∏ℓ∈Jbℓ∣]=0E[ _ ∈ Jb_ ]=0. Proof. Since W is measurable with respect to σ(bℓ:ℓ≠i)σ(\b_ : ≠ i\), it is also measurable with respect to σ(,bℓ:ℓ≠i)σ(G,\b_ : ≠ i\). By the assumed independence, [bi∣σ(,bℓ:ℓ≠i)]=[bi]=0.E[b_i σ(G,\b_ : ≠ i\)]=E[b_i]=0. Therefore [biW∣]=[W[bi∣σ(,bℓ:ℓ≠i)]|]=0.E[b_iW ]=E\! [W\,E[b_i σ(G,\b_ : ≠ i\)]\, |\,G ]=0. For the product claim, write ∏ℓ∈Jbℓ=biW _ ∈ Jb_ =b_iW with W=∏ℓ∈J∖ibℓW= _ ∈ J \i\b_ . ∎ C.1 Proof of Theorem 3.2 See 3.2 Proof. Following the shorthand notation introduced above in Equation 2, we first prove that pk=1/2+∑j≤kαjSj=1/2+ukp_k=1/2+ _j≤ k _jS_j=1/2+u_k by induction on k. For k=1k=1, the previous message is empty; Alice knows b1b_1, and every later term SjS_j with j≥2j≥ 2 contains Bob’s unseen bit b2b_2, so Lemma C.1 gives [Sj∣xA]=0E[S_j x_A]=0 and therefore p1=1/2+α1b1=1/2+u1p_1=1/2+ _1b_1=1/2+u_1. Inductively assume pk−1=1/2+uk−1p_k-1=1/2+u_k-1. By Assumption 3.1, the round-k speaker recovers the prefix (S1,…,Sk−1)(S_1,…,S_k-1) from the scalar pk−1p_k-1; combined with its own bit bkb_k, the speaker also determines Sk=Sk−1bkS_k=S_k-1b_k. Every later SjS_j with j≥k+1j≥ k+1 contains the next bit bk+1b_k+1, which has opposite parity from the speaker, so Lemma C.1 forces its conditional mean to vanish. Hence pk=[p⋆∣xσ(k),pk−1]=12+∑j≤kαjSj=12+uk.p_k=E[p x_σ(k),p_k-1]= 12+ _j≤ k _jS_j= 12+u_k. We now turn to the claim about the excess risk induced by stopping conversation at round k instead of achieving full information by stopping at round K. First, we note that we can rewrite the expected squared error of pkp_k compared to the true action a∗a^* in terms of the difference between the risk induced by p∗p^*, the weight of the Bernoulli coin that the true action is drawn from and a∗a^*, and the difference between p∗p^* and pkp_k: [(a∗−pk)2] [(a^*-p_k)^2] =[(a∗−p∗+p∗−pk)2] =E[(a^*-p^*+p^*-p_k)^2] =[(a∗−p∗)2]+2[(a∗−p∗)(p∗−pk)]+[(p∗−pk)2].(∗) =E[(a^*-p^*)^2]+2E[(a^*-p^*)(p^*-p_k)]+E[(p^*-p_k)^2]. (*) Note that the cross term is equal to zero by the law of total expectation, conditioning on the value of the secret bits b=(b1,…,bK)b=(b_1,…,b_K) held by Alice and Bob: [(a∗−p∗)(p∗−pk)] [(a^*-p^*)(p^*-p_k)] =[(p∗−pk)[a∗−p∗|b]] =E[(p^*-p_k)E[a^*-p^*|b]] =[(p∗−pk)⋅0] =E[(p^*-p_k)· 0] =0. =0. Thus, setting the cross term in Equation (*) to zero and rearranging terms, we find that [(a∗−pk)2]−[(a∗−p∗)2]=[(p∗−pk)2].E[(a^*-p_k)^2]-E[(a^*-p^*)^2]=E[(p^*-p_k)^2]. Note that p∗−pk=∑j=1KαjSj−∑j=1kαjSj=∑j>kαjSj.p^*-p_k= _j=1^K _jS_j- _j=1^k _jS_j= _j>k _jS_j. Expanding, we find that [(a∗−pk)2]−[(a∗−p∗)2] [(a^*-p_k)^2]-E[(a^*-p^*)^2] =[(∑j>kαjSj)2] =E [ ( _j>k _jS_j )^2 ] =[∑j>kαj2Sj2]+[∑k<j<j′≤Kαjαj′SjSj′] =E [ _j>k _j^2S_j^2 ]+E [ _k<j<j ≤ K _j _j S_jS_j ] =∑j>kαj2+∑k<j<j′≤Kαjαj′[(b1⋯bj)(b1⋯bj⋅bj+1⋯bj′] = _j>k _j^2+ _k<j<j ≤ K _j _j E[(b_1·s b_j)(b_1·s b_j· b_j+1·s b_j ] =∑j>kαj2+∑k<j<j′≤Kαjαj′[bj+1⋯bj′] = _j>k _j^2+ _k<j<j ≤ K _j _j E[b_j+1·s b_j ] =∑j>kaj2(∗), = _j>ka_j^2 (**), since each of the bits bj+1,…,bj′b_j+1,…,b_j are independent fair Bernoulli draws over −1,1\-1,1\ and hence their expected product is zero. For the final claim, about the improvement in risk in each round, we apply the above result, Equation (**), at both round k−1k-1 and k: [(a∗−pk−1)2]−[(a∗−pk)2] [(a^*-p_k-1)^2]-E[(a^*-p_k)^2] =([(a∗−pk−1)2]−[(a∗−p∗)2]) = (E[(a^*-p_k-1)^2]-E[(a^*-p^*)^2] ) −([(a∗−pk)2−[(a∗−p∗)2]) - (E[(a^*-p_k)^2-E[(a^*-p^*)^2] ) =∑j>k−1αj2−∑j>kαj2 = _j>k-1 _j^2- _j>k _j^2 =αk2. = _k^2. And, as a corollary to Equation (**) when k=Kk=K and hence ∑j>kαj2=0 _j>k _j^2=0, [(a∗−pK)2]=[(a∗−p∗)2]E[(a^*-p_K)^2]=E[(a^*-p^*)^2]. ∎ Remark C.2 (Full history vs. previous-message sufficiency). The distinct-partial-sums condition in Assumption 3.1 is used only to make the previous scalar message a sufficient summary of the public history. Dropping it gives a weaker protocol whose rounds still reduce risk by [(pk−pk−1)2]E[(p_k-p_k-1)^2], but without a closed-form per-round improvement. Alternatively, sending the full message history in place of just pk−1p_k-1 restores the closed-form improvement αk2 _k^2, because the increment pk−pk−1=αkSkp_k-p_k-1= _kS_k always reveals the next parity. Remark C.3 (Loss-adaptive stopping vs. exact recovery of h⋆h ). To achieve squared-loss excess at most ε it suffices to run until ∑j>kαj2≤ε _j>k _j^2≤ , which can be much smaller than K. Exact recovery of h⋆h may instead require all K rounds: if ∑j≤kαj<∑j>kαj _j≤ k _j< _j>k _j for every k<Kk<K, the unrevealed tail can flip the sign of uk+rku_k+r_k, so no k<Kk<K prediction message determines h⋆h . C.2 Proof of Theorem 3.3 Proof. For the parity algebra, let p~k p_k be the round-k speaker’s posterior under the action-channel transcript, and let Ak:=2 1p~k≥1/2−1=sign(p~k−1/2)∈−1,+1A_k:=2\,1\ p_k≥ 1/2\-1=sign( p_k-1/2)∈\-1,+1\ be the ±1± 1 recoding of the round-k action message. The claim in Theorem 3.3 that every message equals b1=+11\b_1=+1\ is equivalent to Ak=b1A_k=b_1 for every k. We show Ak=b1A_k=b_1 by induction. At round 11, Alice has no previous message and knows b1b_1; every SjS_j with j≥2j≥ 2 contains Bob’s unseen b2b_2 and vanishes in conditional expectation by Lemma C.1, so her posterior is 1/2+α1b11/2+ _1b_1 and A1=sign(α1b1)=b1A_1=sign( _1b_1)=b_1. Suppose all previous action messages equal b1b_1, so the public transcript reveals no information beyond the first bit. If Alice speaks at round k, she still lacks b2b_2, so the same conditional-expectation calculation gives p~k=1/2+α1b1 p_k=1/2+ _1b_1 and Ak=b1A_k=b_1. If Bob speaks, he knows b2b_2; every SjS_j with j≥3j≥ 3 contains the unseen bit b3b_3 and averages out, so his posterior is p~k=12+α1b1+α2b1b2=12+b1(α1+α2b2). p_k= 12+ _1b_1+ _2b_1b_2= 12+b_1 ( _1+ _2b_2 ). Since α1>α2 _1> _2, the factor α1+α2b2 _1+ _2b_2 is positive for both values of b2b_2, so Ak=b1A_k=b_1. Hence Ak=b1A_k=b_1 at every round and the induced decision does not change after round 11. For the constant-gap instance, take K=3K=3, α1=0.20 _1=0.20, α2=0.15 _2=0.15, α3=0.10 _3=0.10, which satisfy α1>α2 _1> _2 and α1+α2+α3<1/2 _1+ _2+ _3<1/2. Theorem 3.2 gives p3=p⋆p_3=p . Meanwhile, the action message at every round equals b1=+11\b_1=+1\ (equivalently, Ak=b1A_k=b_1). On E:=b2=−1,b3=+1E:=\b_2=-1,b_3=+1\, which has probability 1/41/4, the prefix parities are S1=b1S_1=b_1 and S2=S3=−b1S_2=S_3=-b_1, so p⋆−1/2=b1(α1−α2−α3)<0p -1/2=b_1( _1- _2- _3)<0; hence h⋆=p⋆≥1/2=b1=−1h =1\p ≥ 1/2\=1\b_1=-1\, which disagrees with the action message on E. Thus Pr[a^k≠h⋆]≥1/4 [ a^k≠ h ]≥ 1/4 at every round. ∎ Appendix D Proofs for Section 4 Throughout this appendix section, we work in the chained-parity model of Section 3 under Assumption 3.1. We begin with the following observation: Observation D.1 (Learning cross-calibrated forecasts). Let Z be any information available at prediction time, such as a pair of communicated forecasts Z=(p^Ak,p^Bℓ)Z=( p_A^k, p_B ). Suppose the predictor class can represent the true conditional label probabilities. If the training loss is one whose best population prediction is the true conditional probability, such as cross-entropy or squared loss for binary probabilities, then training a predictor h to predict a⋆a from Z gives h⋆(Z)(a)=Pr(a⋆=a∣Z).h (Z)(a)= (a =a Z). Therefore the learned forecast p~=h⋆(Z) p=h (Z) is calibrated even after conditioning on Z: Pr(a⋆=a∣p~,Z)=p~(a) (a =a p,Z)= p(a) almost surely. Moreover, if Z=(W,q^)Z=(W, q) includes a previous communicated forecast q q, then also Pr(a⋆=a∣p~,q^)=p~(a) (a =a p, q)= p(a) almost surely. Thus loss minimization on features that include the previous forecast learns a forecast that is cross-calibrated with respect to that forecast. Proof. By the assumption on the loss, the best population predictor outputs the true conditional label probabilities, so h⋆(Z)(a)=Pr(a⋆=a∣Z)h (Z)(a)= (a =a Z). Let p~=h⋆(Z) p=h (Z). Since p~ p is a function of Z, Pr(a⋆=a∣p~,Z)=Pr(a⋆=a∣Z)=p~(a). (a =a p,Z)= (a =a Z)= p(a). If Z=(W,q^)Z=(W, q), then averaging the last display over the remaining information W, while keeping (p~,q^)( p, q) fixed, gives Pr(a⋆=a∣p~,q^)=[Pr(a⋆=a∣Z)∣p~,q^]=[p~(a)∣p~,q^]=p~(a). (a =a p, q)=E[ (a =a Z) p, q]=E[ p(a) p, q]= p(a). ∎ We then expand the calibration claim of Theorem 4.1 into self- and cross-calibration (Definitions 2.1 and 2.2), and quantify the excess squared loss from using raw reports p^k p_k in place of pkp_k. We first consider the direct-use benchmark in which the receiver treats the raw report p^k p_k itself as the round-k prediction. This benchmark isolates the squared-loss cost of reporting a biased scalar before applying any post-hoc calibration or projection rule. Proposition D.2 (Self-calibration removes global miscalibration). If λ=0λ=0 and c>0c>0 in (1), then self-calibration already recovers the ideal scalar: Pr(a⋆=1∣p^k)=pk (a =1 p_k)=p_k. Using raw p^k p_k in place of pkp_k incurs excess squared loss [(p^k−pk)2]=(c−1)2[(pk−12)2]=(c−1)2∑j≤kαj2.E[( p_k-p_k)^2]=(c-1)^2\,E [ (p_k- 12 )^2 ]=(c-1)^2 _j≤ k _j^2. Proof. When λ=0λ=0, p^k=1/2+c(pk−1/2) p_k=1/2+c(p_k-1/2) is invertible: pk=1/2+(p^k−1/2)/cp_k=1/2+( p_k-1/2)/c. Since p⋆=pk+rkp =p_k+r_k and p^k p_k is a function of b1,…,bkb_1,…,b_k, Lemma C.1 gives [rk∣p^k]=0E[r_k p_k]=0, so Pr(a⋆=1∣p^k)=[p⋆∣p^k]=pk (a =1 p_k)=E[p p_k]=p_k. The raw-report loss is [(p^k−pk)2]=(c−1)2[(pk−1/2)2]=(c−1)2∑j≤kαj2E[( p_k-p_k)^2]=(c-1)^2E[(p_k-1/2)^2]=(c-1)^2 _j≤ k _j^2. ∎ Proposition D.3 (Cross-calibration removes previous-message bias). For any c>0c>0 and λ∈ℝλ in (1), the conditional label distribution given the raw report and the previous agent’s report recovers the ideal scalar: Pr(a⋆=1∣p^k,pk−1)=pk. (a =1 p_k,p_k-1)=p_k. Thus a post-hoc forecast learned from (p^k,pk−1)( p_k,p_k-1) is cross-calibrated with respect to pk−1p_k-1 and outputs pkp_k. Using raw p^k p_k in place of pkp_k incurs excess squared loss [(p^k−pk)2]=(c−1)2∑j≤kαj2+(2(c−1)λ+λ2)∑j<kαj2.E[( p_k-p_k)^2]=(c-1)^2 _j≤ k _j^2+ (2(c-1)λ+λ^2 ) _j<k _j^2. Proof. For any λ, observing (p^k,pk−1)( p_k,p_k-1) determines pk=12+1c[(p^k−12)−λ(pk−1−12)],p_k= 12+ 1c [ ( p_k- 12 )-λ (p_k-1- 12 ) ], so p⋆=pk+rkp =p_k+r_k with [rk∣p^k,pk−1]=0E[r_k p_k,p_k-1]=0 by Lemma C.1. Hence Pr(a⋆=1∣p^k,pk−1)=[p⋆∣p^k,pk−1]=pk (a =1 p_k,p_k-1)=E[p p_k,p_k-1]=p_k. If the raw report is used directly then p^k−pk=(c−1)(pk−1/2)+λ(pk−1−1/2) p_k-p_k=(c-1)(p_k-1/2)+λ(p_k-1-1/2). With pk−1/2=ukp_k-1/2=u_k and pk−1−1/2=uk−1=uk−αkSkp_k-1-1/2=u_k-1=u_k- _kS_k, cross-term cancellation via Lemma C.1 gives [uk2]=∑j≤kαj2E[u_k^2]= _j≤ k _j^2 and [uk−12]=[ukuk−1]=∑j<kαj2E[u_k-1^2]=E[u_ku_k-1]= _j<k _j^2, yielding the stated identity. ∎ Proposition D.3 is exactly the chained-parity instance of Observation D.1: learning Pr(a⋆=1∣p^k,pk−1) (a =1 p_k,p_k-1) from labelled transcripts produces a cross-calibrated forecast that equals pkp_k, and hence recovers Theorem 3.2 regardless of the raw report’s confidence distortion (c) or anchoring to the previous message (λ). This proves Theorem 4.1. Round-by-round behavior under projection. Propositions D.2 and D.3 say that, given enough labelled data, calibration recovers the ideal scalar pkp_k from a biased report. We now analyze a different receiver model: a receiver that does not know the bias model and therefore treats p^k p_k as if it were the true posterior. When p^k p_k is not a possible message under any valid speaker posterior, the receiver rounds p^k p_k to the closest valid message before updating. Formally, if S is the set of valid speaker messages, the receiver’s Bayesian update is computed with respect to p¯k∈argmins∈S|p^k−s|. p_k\;∈\; _s∈ S\,| p_k-s|. (3) The set S should be read as the receiver-consistent valid set: the posterior values that could have been sent by the speaker among worlds consistent with the receiver’s own private observation and the public transcript so far, which avoids assigning positive probability to a message the receiver already knows to be impossible. Under this rule, bias is harmless until it pushes p^k p_k across the midpoint between two adjacent valid messages, at which point the receiver decodes the wrong latent bit and pays a discrete cost. We work with the original biased-report model of (1), with the same (c,λ)(c,λ) across rounds, and trace what happens round by round. Round 11. Alice observes b1b_1 and her ideal posterior is p1=12+α1b1p_1= 12+ _1b_1. From Bob’s view the valid messages are 12−α1,12+α1\ 12- _1, 12+ _1\, symmetric around p0=12p_0= 12 at distance α1 _1. Since p0=12p_0= 12, the anchoring term in (1) vanishes and p^1−12=cα1b1 p_1- 12=c _1b_1 has the same sign as b1b_1 for every c>0c>0. Nearest-valid projection therefore recovers b1b_1, and the round-11 message conveys the same information it would under a calibrated speaker. Round 22. Conditional on correct round-11 decoding, Bob now sees p1=12+α1b1p_1= 12+ _1b_1 as a public scalar and observes his own bit b2b_2. His ideal posterior is p2=p1+α2b1b2p_2=p_1+ _2b_1b_2, and from Alice’s view the valid round-22 messages are p1−α2,p1+α2\p_1- _2,p_1+ _2\, symmetric around p1p_1 at distance α2 _2. Nearest-valid projection of p^2 p_2 recovers p2p_2 iff p^2 p_2 lies on the same side of p1p_1 as p2p_2 (with equality corresponding to a tie). Unlike at round 11, the biased report now picks up an anchoring contribution from pk−1=p1p_k-1=p_1, and this is the source of failure. Proposition D.4 (Decoding failure at round 2). Under the biased reports of (1) with c>0c>0, conditional on correct round-11 decoding, nearest-valid projection at round 22 decodes incorrectly on the event b2=−sign(c+λ−1)\b_2=-sign(c+λ-1)\, of probability 1/21/2, whenever |c+λ−1|α1>cα2.|c+λ-1|\, _1\;>\;c\, _2. A wrong decode flips α2S2 _2S_2 in the receiver’s projected posterior. Conditional on the wrong-decode event, this contributes squared-loss excess 4α224 _2^2 relative to the ideal round-22 posterior; averaged over b2b_2 conditional on correct round-11 decoding, the contribution is 2α222 _2^2. Proof. Conditional on correct round-11 decoding, p1=12+α1b1p_1= 12+ _1b_1 and p2=p1+α2b1b2p_2=p_1+ _2b_1b_2, so (1) gives p^2−p1=cα2b1b2+(c+λ−1)α1b1. p_2-p_1=c _2b_1b_2+(c+λ-1) _1b_1. Correct decoding requires this to have the same sign as b1b2b_1b_2; multiplying by b1b2b_1b_2 gives the equivalent condition cα2+(c+λ−1)α1b2>0c _2+(c+λ-1) _1b_2>0, which fails on the unfavorable sign b2=−sign(c+λ−1)b_2=-sign(c+λ-1) exactly when |c+λ−1|α1>cα2|c+λ-1| _1>c _2 (with equality corresponding to a tie in nearest-valid projection). On the wrong-decode event, projection flips α2S2 _2S_2 to −α2S2- _2S_2, so the projected posterior differs from the ideal round-22 posterior by 2α2S22 _2S_2. By the squared-loss identity used in Theorem 3.2, the conditional excess is (2α2)2=4α22(2 _2)^2=4 _2^2. Since the wrong-decode event has probability 1/21/2 conditional on correct round-11 decoding, its expected contribution is 2α222 _2^2. ∎ This parallels Theorem 3.3: action communication transmits b1b_1 correctly and then stalls; affine-biased probability communication also transmits b1b_1 correctly under projection, but begins to lose b2b_2 once the imbalance condition |c+λ−1|α1>cα2|c+λ-1| _1>c _2 holds. The round-22 projection failure disappears when c+λ=1c+λ=1, while true calibration of the affine report corresponds to the stronger condition c=1c=1 and λ=0λ=0. The two parts of the appendix are thus complementary: Propositions D.2–D.3 say that post-hoc calibration suffices to recover the ideal scalar pkp_k, while Proposition D.4 identifies a regime in which an uncalibrated projection-based receiver flips the second latent bit. Appendix E Experimental details Here, we provide additional information on reproducibility of our experiments. E.1 Task design Chained Parities For the parity task, we construct our dataset as prescribed by the theory in Section 3. We generate bitstrings of length 30 and choose a total of 3030 corresponding coefficients. We set the first four values to [0.2,0.15,0.1,0.02][0.2,0.15,0.1,0.02] and assign the remaining 2626 values equally so that ∑jαj=0.49 _j _j=0.49. The bits of each datapoint are split disjointly between the two agents in alternating order, and the binary label is sampled from P(Y=1∣b)=12+∑jαjsjP(Y=1 b)= 12+ _j _js_j, where sjs_j is the j-th prefix product of the hidden signs. Then, we generate a total of two million datapoints which we split into a 90%90\% train and 10%10\% test split. All results are reported on the test split. Mazes For the maze task, we construct mazes similar to those introduced by [Davidson et al., 2025]. We consider mazes of size 6×66× 6. For evaluation purposes, we only consider mazes with a single correct path. The wall density is 30%30\%. Each agent sees exactly half of the maze cells, assigned uniformly at random, and the agents receive disjoint masks so that each maze is always solvable from the joint information. An example maze is shown below. Again, we generate two million datapoints in total, split the data into a 90%90\% train and 10%10\% test split, and report our results on the test set. The data contains one example per step along the unique solution: the agent’s masked grid is rendered with the current position marked, and the correct next move is used as the label. There are four answer tokens that can represent the true label: up, down, left, and right. x: @##.#. .##... ...#.. .#.##. #..### .#...* xAx_A: @#??#? ?#??.? ?.??.? .?.##? #..##? .#.??* xBx_B: @?#.?. .?#.?. .?.#?. ?#???. ?????# ???..* Figure 12: Example of full maze and agents’ private observations. E.2 Transformer experiments For both tasks we use a small, character-level GPT based on the NanoGPT implementation [Karpathy, 2022]: 44 transformer blocks, 66 attention heads, embedding dimension 240240, and a causal mask. Each agent maintains its own per-task vocabulary derived from the raw character set of its inputs, so all sequences are tokenized at the character level. The context length is set to prefix_size+1 prefix\_size+1, where the prefix is the serialized example up to (but not including) the answer; any annotations appended by a collaborator (see below) extend the prefix accordingly. We treat each task as next-token prediction with the loss measured only at the answer position(s). Per-agent inputs. For chained parity, agent 00 ("Bob") sees the odd-indexed bits and agent 11 ("Alice") sees the even-indexed bits; the unobserved positions are replaced with a mask token, and the label bit is appended after an = delimiter. For mazes, each agent’s input is the flattened 6×66× 6 grid restricted to its assigned half of the cells, with the current position marked by @, followed by = and the next move from d,r,u,l\d,r,u,l\. A single maze with path length ℓ contributes ℓ training examples, each predicting the next move from the current position. Conversation loop. We instantiate our protocol as iterative training across rounds: in round r, agent rmodKr K (with K the number of agents) trains a fresh transformer from scratch on its currently annotated dataset. After a fixed number of optimizer steps, the trained agent runs over its inputs and emits a message for each example, which is then appended to the prefix of the next agent’s inputs in round r+1r+1. Because each round trains a freshly initialized model, any improvement in joint performance must come through the appended messages rather than transferred weights. Optimization. Each agent is trained from scratch with AdamW (β1=0.9 _1=0.9, β2=0.99 _2=0.99, weight decay 0.10.1, gradient clip 1.01.0) in bfloat16 mixed precision on a single GPU, with batch size 10241024 and no gradient accumulation. The learning rate uses linear warmup over 100100 steps to a peak of 10−410^-4, followed by cosine decay to 10−510^-5 over the remainder of training. We run 20002000 iterations per round on chained parity (55 rounds) and 50,00050,000 iterations per round on mazes (44 rounds); in both cases we keep the checkpoint with the best validation loss within each round. E.3 LLM experiments The LLM experiments follow the same per-round procedure as our transformer experiments, with each agent now replaced by a pretrained LLM queried through the API rather than a model trained from scratch. Unless otherwise noted we use temperature 1.01.0, run 44 rounds of conversation per maze, and evaluate on N=30N=30 mazes, with 10 rollouts each, drawn from the held-out test split. At each round, the active agent receives a prompt containing (i) a legend-annotated rendering of its own masked 6×66× 6 maze, (i) the sequence of moves taken so far (from which the current position can be inferred), and (i) the other agent’s most recent response from the previous round. We consider three communication settings, which differ only in what part of the partner’s response is appended to the next prompt: the full free-form message, a single move token in d,r,u,l\d,r,u,l\, or a probability vector over the four moves. Probabilities can either be elicited directly from the model in the response, post-calibrated from the verbalized answer, or obtained from rollouts. The agent is to produce a single move after the delimiter ~, and – in the verbalized setting – a probability vector after the delimiter %. The joint trajectory advances by one step after each conversation of K rounds; a single incorrect move terminates the maze, and we report the resulting per-maze success rate. E.3.1 Prompts The prompt we use to query the LLM at each step is: ⬇ Task: You are going to play the collaborative maze game together with another agent. The maze consists of a grid with walls and a goal. Your task is to jointly determine the next move on the path. You and the other agent will take that action together. You will each get your own map of the same maze, with some coordinates hidden. Because of the hidden coordinates, you will need to communicate with the other agent to share information about the maze and coordinate your next move. Both agents together have enough information to solve the maze, so you do not need to explore. Rules: - You can only move to adjacent cells [down(d), right(r), up(u), left(l)]. - You can not move diagonally or through walls. - Once you make an incorrect move, you lose. Here is **your** map of the maze with a legend of the symbols: @?#.?. .?#.?. .?.#?. ?#???. ?????# ???..* Legend: @ - Current Position * - Goal Position . - Path # - Wall ? - Hidden Cell You must answer with one of d, r, u, l. Put your final answer after the delimiter ~. For example, if your final answer is d, your response should contain ~d. Finally, give the probabilities you think each move d, r, u, l is correct after the delimiter %. For example, if you think the probability of d, r, u, l is 0.8, 0.1, 0.05, 0.05, your response should contain %[0.8, 0.1, 0.05, 0.05]. Make sure it is a valid probability vector, i.e. the sum of the probabilities is 1. Your moves are timed for speed so hurry up! For our experiment communicating full responses (Figure 11), we slightly modify the above prompt for GPT-5.4-nano to ensure its response includes content beyond the elicited probabilities (otherwise, while it generates reasoning in the background, its reasoning is hidden). The modified prompt is: ⬇ Task: You are going to play the collaborative maze game together with another agent. The maze consists of a grid with walls and a goal. Your task is to jointly determine the next move on the path. You and the other agent will take that action together. You will each get your own map of the same maze, with some coordinates hidden. Because of the hidden coordinates, you will need to communicate with the other agent to share information about the maze and coordinate your next move. Both agents together have enough information to solve the maze, so you do not need to explore. Rules: - You can only move to adjacent cells [down(d), right(r), up(u), left(l)]. - You can not move diagonally or through walls. - Once you make an incorrect move, you lose. Here is **your** map of the maze with a legend of the symbols: @?#.?. .?#.?. .?.#?. ?#???. ?????# ???..* Legend: @ - Current Position * - Goal Position . - Path # - Wall ? - Hidden Cell First, provide what you would like to communicate to the other agent. Then, you must answer with one of d, r, u, l. Put your final answer after the delimiter ~. For example, if your final answer is d, your response should contain ~d. Finally, give the probabilities you think each move d, r, u, l is correct after the delimiter %. For example, if you think the probability of d, r, u, l is 0.8, 0.1, 0.05, 0.05, your response should contain %[0.8, 0.1, 0.05, 0.05]. Make sure it is a valid probability vector, i.e. the sum of the probabilities is 1. Your moves are timed for speed so hurry up! Finally, the prompt we use for the full-information solo baseline (Figure 7(a)) is: ⬇ Task: You are going to play a maze game. The maze consists of a grid with walls and a goal. Your task is to navigate through the maze, avoiding walls, to reach the goal. Rules: - You can only move to adjacent cells [down(d), right(r), up(u), left(l)]. - You can not move diagonally or through walls. - Once you make an incorrect move, you lose. Here is **your** map of the maze with a legend of the symbols: @...#. .#.##. .#...# .###.. #...#. ..#.#* Legend: @ - Current Position * - Goal Position . - Path # - Wall ? - Hidden Cell You must answer with one of d, r, u, l. Put your final answer after the delimiter ~. For example, if your final answer is d, your response should contain ~d. Finally, give the probabilities you think each move d, r, u, l is correct after the delimiter %. For example, if you think the probability of d, r, u, l is 0.8, 0.1, 0.05, 0.05, your response should contain %[0.8, 0.1, 0.05, 0.05]. Make sure it is a valid probability vector, i.e. the sum of the probabilities is 1. Your moves are timed for speed so hurry up! E.3.2 Conversation Calibration Loss In Figure 7(b), we compute conversation calibration loss as follows. At round k the model is evaluated on N examples (one per move per maze), indexed i=1,…,Ni=1,…,N. Given D possible actions, for each example: let p~k,i∈[0,1]D p_k,i∈[0,1]^D be the model’s predicted action distribution at round k, p^k−1,i∈[0,1]D p_k-1,i∈[0,1]^D be the collaborator’s communicated distribution at the previous round k−1k-1, and yi∈0,1Dy_i∈\0,1\^D be the one-hot encoding of the true action. Discretize [0,1][0,1] into B equal-width bins, Ib=[b−1B,bB)I_b=[ b-1B, bB) for b=1,…,Bb=1,…,B (with IBI_B closed at 11). For a vector p∈[0,1]Dp∈[0,1]^D and a bin multi-index =(b1,…,bD)∈1,…,BDb=(b_1,…,b_D)∈\1,…,B\^D, write the cell indicator as a product over the D coordinates, p∈I=∏d=1Dp(d)∈Ibd.1\p∈ I_b\\;=\; _d=1^D1\! \p^(d)∈ I_b_d \. A cross bin is a pair (,′)(b,b ) that jointly bins the model’s own distribution and the collaborator’s distribution. We use hard binning — that is, the weight on cross bins (,′)(b,b ) for example i is simply the indicator of if it lies in the bins: wk,i(,′)= 1p~k,i∈I 1p^k−1,i∈I′∈0,1.w_k,i(b,b )\;=\;1\ p_k,i∈ I_b\\;1\ p_k-1,i∈ I_b \\;∈\0,1\. Let N,′=∑i=1Nwk,i(,′)N_b,b = _i=1^Nw_k,i(b,b ) be the bin count, and let p¯,′=1N,′∑i=1Nwk,i(,′)p~k,i,y¯,′=1N,′∑i=1Nwk,i(,′)yi p_b,b = 1N_b,b _i=1^Nw_k,i(b,b )\, p_k,i, y_b,b = 1N_b,b _i=1^Nw_k,i(b,b )\,y_i be the bin-averaged prediction and empirical outcome frequency. The conversation calibration loss at round k is the average weighted ℓ2 _2 gap between the two: ConvCalk=1N∑,′N,′‖p¯,′−y¯,′‖2=1N∑,′‖∑i=1Nwk,i(,′)(p~k,i−yi)‖2,ConvCal_k\;=\; 1N _b,b N_b,b \, \| p_b,b - y_b,b \|_2\;=\; 1N _b,b \| _i=1^Nw_k,i(b,b ) ( p_k,i-y_i ) \|_2, The second equality follows since p¯,′−y¯,′=1N,′∑iwk,i(,′)(p~k,i−yi) p_b,b - y_b,b = 1N_b,b _iw_k,i(b,b )( p_k,i-y_i), so the factor N,′N_b,b cancels. At round k=1k=1 there is no collaborator, so we bin on p~1,i p_1,i alone (i.e. drop ′b and the p p indicator), recovering the standard (self) calibration loss. In our results, we report conversation calibration losses using B=10B=10. Appendix F Examples of Multi-Round Communication in Mazes Here we give examples of “hard” moves in mazes — those that require multiple rounds of communication — and how our trained transformer models converge to the correct move when iteratively exchanging probabilities. x: @...#. .#.##. .#...# .###.. #...#. ..#.#* xAx_A: @...?? ?#???? .?.?.? ?#?#?? ?..??. ..#?#* xBx_B: @???#. .?.##. ?#?.?# .?#?.. #??.#? ???.?* (a) Hard maze example 1. x: ..#.#. #.#... ..@..# .#.### #..... .##.#* xAx_A: ..???? ?????. ..@?.? ????#? #..??? .?#?#* xBx_B: .?#.#. #.#..? ??@.?# .#.#?# ???... ?#?.?* (b) Hard maze example 2. Figure 14: Two examples of hard moves in mazes. For each maze, the panels show the full maze x, agents’ partially observed mazes xAx_A and xBx_B with the current position denoted by @, and the probabilistic predictions made by our trained transformer models on this move over 4 rounds (details are in Appendix E). Agent A communicates on odd rounds and Agent B communicates on even rounds. The correct answer is shaded. Figure 14 shows two examples where both agents are initially uncertain about the next move. In the first example (Figure 14(a)), agent A assigns 78% probability to moving right in the first round, which is the correct move. Subsequent rounds progressively reinforce this prediction, and by the fourth round, agent B is almost completely certain that this is the correct next move. In the second example (Figure 14(b)), agent A is initially fairly uncertain and assigns most of its probability mass to moving right, which is incorrect. Agent B corrects this in the second round by assigning 89% probability to moving down. Agent A then resolves almost all of its uncertainty and ends up assigning 99% probability to moving down. Note that in all other moves in these mazes, two rounds suffice: one agent exactly knows the next move. Appendix G Limitations Our work studies one specific axis of multi-agent LLM collaboration—the communication protocol when information is partitioned between two agents—and we make no claim to have addressed the full complexity of this space, including issues of task decomposition, trust between agents, and prompt sensitivity. On the theory side, while we establish a clean separation between action and probability communication in the chained parity model, a complete characterization of when and why this gap arises in general remains open. The maze task, though a useful controlled testbed, is stylized relative to real collaborative tasks. Finally, our setting is restricted to two agents; extending the framework to networks of more than two agents is a natural direction for future work. Appendix H Compute Resources Our experiments were conducted partially on a local desktop computer and on a compute cluster with various types of graphical processing units (GPUs), including Nvidia RTX3090 and Nvidia A6000 GPUs. Training a single parity experiment can be done on a household-grade GPU in less than one hour time. The training of the maze transformers took approximately 6-12 hours per run depending on the GPU. Our experiments thus amount to approximately 300−400300-400 GPU hours. This is an estimate for the experiments included in the paper and does not reflect potential developing and debugging runtime. All LLM experiments were conducted directly via OpenAI’s public API and did not require local computational resources beyond a standard laptop.