Bayesian Partner Modelling enables Adaptive Replanning for LLM Coordination

Harsh Goel; Aditya Sai Ellendula; Vaishnav Tadiparthi; Ehsan Moradi Pari; Hossein Nourkhiz Mahjoub; Sandeep P. Chinchali

cs.MAAug 19, 2026

Bayesian Partner Modelling enables Adaptive Replanning for LLM Coordination

Authors: Harsh Goel, Aditya Sai Ellendula, Vaishnav Tadiparthi, Ehsan Moradi Pari, Hossein Nourkhiz Mahjoub, Sandeep P. Chinchali

Organizations: The University of Texas at Austin · Honda Research Institute, USA

Abstract

Multi-agent Large Language Model (LLM) systems often struggle to collaborate with new teammates whose strategies shift mid-task. Because agents execute multi-step or temporally extended skills, they frequently continue executing outdated plans long after public evidence shows that a partner has changed its skill. Existing methods either treat partner tracking as passive context-leaving the agent aware of the shift but slow to act-or replan indiscriminately. We introduce BayesBeliefAgent, which pairs a hierarchical LLM planner with a Bayesian tracking module. Rather than replanning constantly, our agent interrupts its current skill only when a partner's actions directly contradict the inferred skill. Beyond standard reward, we evaluate performance using replanning efficiency and the belief-action gap: the fraction of total decisions where an agent with a correct partner estimate executes a non-complementary skill. Across benchmark Overcooked environments, contradiction-conditioned control drastically narrows this belief-action gap while requiring an order of magnitude fewer replans than heuristic methods

Figures & tables

Figure 1: Belief alone is not enough. An LLM agent may correctly model its teammate yet still act redundantly if it does not revise its plan when partner behavior changes. BayesBeliefAgent addresses this by maintaining a Bayesian posterior over latent teammate coordination skills, detecting visible contradictions, and triggering replanning when the current plan becomes stale. This turns teammate belief into coordinated, complementary action.

Figure 2: BayesBeliefAgent overview. From the teammate’s publicly observed primitive actions and the ego agent’s observation history, the agent maintains a posterior over the teammate’s active skill. Each newly observed teammate action is first evaluated under the previous MAP teammate-skill estimate. The posterior is then updated using the new observation. If the action is contradictory and the previous estimate is stable and sufficiently confident while the ego agent is mid-skill and out of cooldown, the current skill is interrupted and the LLM planner is queried using the updated posterior and MAP estimate. Otherwise, the agent continues executing its current skill.

	Group 1 (Logistics)			Group 2 (Cooking)			Group 3 (Sourcing)
Agent	FC	Ring	Open	FC	Ring	Open	FC	Ring	Open
BP	95 (116)	927 (406)	1625 (457)	84 (159)	622 (246)	484 (179)	76 (130)	793 (228)	792 (334)
GAMMA	46 (79)	1124 (225)	1189 (415)	64 (111)	649 (159)	360 (114)	54 (77)	864 (216)	692 (167)
TALENTS	53 (91)	1019 (307)	1212 (193)	34 (60)	935 (298)	398 (158)	38 (49)	1237 (308)	1101 (321)
Hypothetical-Minds	11 (19)	388 (361)	608 (274)	0 (0)	188 (64)	369 (164)	0 0	275 (124)	480 (239)
ProAgent	0 (0)	313 (252)	732 (310)	0 (0)	161 (143)	388 (253)	9 (15)	271 (234)	549 (327)

Table 1: Coordination performance (mean reward

\pm

std. dev.) across all three BP partner groups. FC = Forced Coordination. Best LLM-based result per cell in bold ; best overall underlined. BayesBeliefAgent outperforms all LLM-based agents.

Metric	Method	Open	Ring	FC
Skill acc. ( $\uparrow$ )	BayesBeliefAgent	0.79	0.71	0.61
Skill acc. ( $\uparrow$ )	ProAgent	0.78	0.71	0.60
Gap rate ( $\downarrow$ )	BayesBeliefAgent	0.20	0.28	0.42
Gap rate ( $\downarrow$ )	ProAgent	0.41	0.38	0.47
Comp@3 ( $\uparrow$ )	BayesBeliefAgent	0.66	0.54	0.31
Comp@3 ( $\uparrow$ )	ProAgent	0.39	0.43	0.26

Table 2: Mechanism metrics averaged across partner groups G1–G3. Despite nearly identical teammate-skill prediction accuracy, BayesBeliefAgent reduces the belief–action gap and duplicate-skill rate and improves contradiction-conditioned recovery relative to ProAgent , with the largest gains in Open and Ring. Arrows indicate the improving direction.

Setting	Full	No prompt	No replan	No belief
Open G1	$1533{\pm}{410}$	$1405{\pm}{430}$	$1190{\pm}{455}$	$1080{\pm}{470}$
Open G2	$337{\pm}{270}$	$305{\pm}{250}$	$263{\pm}{152}$	$274{\pm}{290}$
Open G3	$1420{\pm}{390}$	$1325{\pm}{420}$	$1110{\pm}{440}$	$1015{\pm}{465}$
Ring G1	$663{\pm}{468}$	$610{\pm}{430}$	$566{\pm}{348}$	$212{\pm}{206}$
Ring G2	$231{\pm}{232}$	$225{\pm}{215}$	$264{\pm}{218}$	$215{\pm}{227}$
Ring G3	$506{\pm}{161}$	$475{\pm}{185}$	$439{\pm}{177}$	$607{\pm}{582}$

Table 3: We report the mean reward

\pm

standard deviation across posterior-guided control ablations. Posterior-gated interruption generally outperforms posterior prompting alone, indicating its effectiveness as a control signal.

Setting	Full	Periodic-10	Compl./held	LLM-judge
Open G1	1533 / 2.0	1490 / 43.0	1510 / 169.0	1480 / 119.0
Open G2	337 / 1.8	515 / 15.0	304 / 50.4	403 / 34.0
Open G3	1420 / 3.0	1395 / 51.0	1370 / 115.0	1400 / 98.0
Ring G1	663 / 1.6	695 / 66.9	629 / 107.1	721 / 97.1
Ring G2	231 / 7.5	218 / 76.3	202 / 87.5	201 / 110.6
Ring G3	506 / 9.3	416 / 52.8	455 / 110.9	558 / 103.3

Table 4: We report the mean reward / replans per episode to compare replanning triggers. All LLM-planner conditions receive identical public observations and belief prompt; they differ only in the interruption signal. BayesBeliefAgent (Full) attains comparable reward with far fewer replans than the heuristic or LLM-based triggers.

Group	Behavior Feature	Reward(s)
Group 1 (Logistics)	Plating Ingredients	$\{-30,+20\}$
	Washing Plates	$\{-30,+20\}$
	Delivering Dishes	$+20$ (fixed)
Group 2 (Cooking)	Chopping Ingredients	$\{-30,+20\}$
	Potting Rice	$\{-30,+20\}$
	Grilling Meat	$+20$ (fixed)

Table 5: Event-weight configurations used to train the 12 BP partner policies. Within each group, the two non-fixed weights are crossed, producing four policies; the third weight is fixed across those four policies.

Parameter	Value
Prior smoothing $\alpha$	$1$
Contradiction threshold $\theta_{\mathrm{obs}}$	$0.04$
Stability window $K$	$3$ updates
Replanning cooldown $C_{\mathrm{cool}}$	$6$ steps
Macro-skill timeout	$30$ steps
Pass / PutDown likelihood weight	$0.35$

Table 6: Experimental hyperparameters.

Parameter	Value	Reward	Replans/ep.	Gap rate
Obs. threshold	0.02	1450	0.8	0.23
	0.04 (default)	1533	2.0	0.17
	0.06	1490	5.6	0.19
Conf. floor	0.55	1475	4.8	0.20
	0.65 (default)	1533	2.0	0.17
	0.75	1460	0.9	0.22

Table 7: One-at-a-time sensitivity analysis on Open G1. Defaults are shown in bold.

Setting	$\Delta$ Reward (95% CI)	$\Delta$ Gap (95% CI)
Open G1	$+343\ [+75,\ +601]$	$-0.26\ [-0.35,\ -0.16]$
Open G2	$+74\ [-92,\ +231]$	$-0.15\ [-0.26,\ -0.04]$
Open G3	$+310\ [+42,\ +566]$	$-0.21\ [-0.31,\ -0.11]$
Ring G1	$+98\ [-131,\ +322]$	$-0.13\ [-0.23,\ -0.03]$
Ring G2	$-33\ [-165,\ +102]$	$-0.05\ [-0.14,\ +0.04]$
Ring G3	$+67\ [-58,\ +190]$	$-0.12\ [-0.21,\ -0.03]$

Table 8: Paired Full

-

No replan differences with

95\%

bootstrap confidence intervals.

Setting	4o reward	5.2 reward	4o gap	5.2 gap
Open G1	1533	1485	0.17	0.19
Open G2	337	395	0.24	0.22
Open G3	1420	1360	0.20	0.21
Ring G1	663	705	0.25	0.23
Ring G2	231	285	0.32	0.29
Ring G3	506	470	0.27	0.28

Table 9: Reward and belief–action gap rate with GPT-4o and GPT-5.2 as the high-level planner backbone.

Setting	Method	Skill acc. ( $\uparrow$ )	Gap rate ( $\downarrow$ )	Comp@3 ( $\uparrow$ )	Dup. Skill ( $\downarrow$ )
Open G1	BayesBeliefAgent	0.82	0.17	0.71	0.12
Open G1	ProAgent	0.81	0.43	0.36	0.31
Open G2	BayesBeliefAgent	0.76	0.24	0.61	0.18
Open G2	ProAgent	0.75	0.39	0.42	0.29
Open G3	BayesBeliefAgent	0.79	0.20	0.66	0.15
Open G3	ProAgent	0.78	0.41	0.39	0.30

Table 10: Mechanism metrics for the full agent and the No replan variant. Forced Coordination aggregates Groups 1–3. Arrows indicate the preferred direction.

Agent ( $P_{0}\downarrow$ , $P_{1}\rightarrow$ )	Bayes	Pro	GAMMA	TALENTS	Mean over $P_{1}$
Open
Bayes	720.3 (256.8)	853.0 (738.8)	779.3 (373.9)	1917.0 (529.6)	1067.4 (474.8)
Pro	827.0 (582.2)	561.3 (675.2)	853.0 (372.5)	1934.0 (677.6)	1043.8 (576.9)
GAMMA	608.3 (86.1)	1698.7 (531.5)	440.7 (61.6)	1262.3 (74.1)	1002.5 (188.3)
TALENTS	1034.0 (195.4)	1305.0 (149.3)	1160.0 (216.1)	1390.7 (157.8)	1222.4 (179.6)
Mean over $P_{0}$	797.4 (280.1)	1104.5 (523.7)	783.2 (256.0)	1625.8 (359.8)	–

Table 11: Zero-shot cross-play reward, reported as mean with standard deviation in parentheses. Rows identify the

P_{0}

ego agent and columns identify the

P_{1}

partner.

Dynamic Replanning

See all 17 papers

TeamTR: Trust-Region Fine-Tuning for Multi-Agent LLM Coordination
May 1, 2026Yi Xie, Siao Liu, Falong Fan +3Multi-Agent System Optimization Multi-Agent Coordination
Department of Electrical & Computer Engineering, University of Arizona · Future Science and Engineering College, Soochow University · INSAIT, Sofia University ”St. Kliment Ohridski” +1
SyncPlan: Long-Horizon LLM Coordination with Explicit Synchronization and Adaptive Correction
Aug 3, 2026Shen You, Xiaoming Zhu, Weining Weng +17Multi-Agent Coordination LLM Planning
1City University of Hong Kong · 2Tencent · 3Shenzhen University +1
Training-Free Agentic AI: Probabilistic Control and Coordination in Multi-Agent LLM Systems
Feb 24, 2026Mohammad Parsa Hosseini, Ankit Shah, Saiyra Qureshi +3Multi-Agent LLM Systems LLM Agent Orchestration
Accenture.

May 1, 2026J/K move · Enter open · S save

TeamTR: Trust-Region Fine-Tuning for Multi-Agent LLM Coordination

Yi Xie, Siao Liu, Falong Fan, Yuanqi Yao+2

Department of Electrical & Computer Engineering, University of Arizona · Future Science and Engineering College, Soochow University · INSAIT, Sofia University ”St. Kliment Ohridski”+1

Multi-Agent System Optimization Multi-Agent Coordination Trust-Region Optimization Multi-Agent LLMs RL Fine-Tuning Multi-Agent Reinforcement Learning

Open paper AskPDF arXiv

Multi-agent LLM systems have shown promise for complex reasoning, yet recent evaluations reveal they often underperform single-model baselines. We identify a structural failure mode in sequential fine-tuning of shared-context teams: updating one agent shifts the team's context distribution, and when subsequent updates are evaluated on cached rollouts, this mismatch compounds. We formalize this as the compounding occupancy shift and prove that stale-occupancy evaluation incurs a penalty that scales quadratically with the number of agents. In contrast, intermediate-occupancy evaluation reduces this to linear scaling. We propose TeamTR, a trust-region framework that resamples trajectories after each component update and enforces per-agent divergence control, yielding rigorous per-update and per-stage improvement lower bounds. Experiments show that TeamTR outperforms single-agent and sequential baselines with 7.1% on average, mitigates coordination regressions, and supports plug-and-play component replacement. Code is available at https://github.com/Yydc/TeamTR.

Abstract

Dynamic Replanning

Explore similar work

TeamTR: Trust-Region Fine-Tuning for Multi-Agent LLM Coordination

SyncPlan: Long-Horizon LLM Coordination with Explicit Synchronization and Adaptive Correction

Training-Free Agentic AI: Probabilistic Control and Coordination in Multi-Agent LLM Systems