💻 computer science

Bayesian Partner Modelling enables Adaptive Replanning for LLM Coordination

The paper introduces BayesBeliefAgent, a hierarchical LLM system that combines Bayesian partner tracking with contradiction-conditioned replanning to efficiently adapt to teammates' strategy shifts, significantly reducing unnecessary replans and the belief-action gap compared to existing methods.

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

Published 2026-08-20

📖 5 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of artificial intelligence, a major frontier is teaching computers to work together. Imagine two people trying to build a table; if one person suddenly decides to sand the wood while the other is still sawing, the project stalls. For decades, researchers have tried to get computer programs to coordinate, but a specific kind of failure has remained stubborn. Large language models, the powerful AI systems that can write stories or solve puzzles, are often excellent at understanding what a partner intends to do. They can look at a teammate's actions and correctly guess, "Ah, they are trying to chop vegetables." However, knowing what a partner is doing does not automatically mean the AI knows when to stop its own current task. An AI might correctly realize its partner has changed plans, yet continue chopping vegetables for ten more minutes because it is too rigid to change its own course. This gap between understanding a partner and actually changing one's own behavior is the central problem researchers are trying to solve.

A team of researchers from the University of Texas at Austin and Honda Research Institute has introduced a new approach to fix this disconnect. They built an AI agent called BayesBeliefAgent, designed to work in a simulated kitchen environment where two cooks must prepare meals together. In these scenarios, the AI and its unseen partner must coordinate tasks like chopping onions, cooking rice, or plating food. The challenge is that the partner's strategy can shift in the middle of the task. The researchers found that simply giving the AI a better understanding of its partner was not enough. Instead, they gave the AI a specific mechanism to decide exactly when to stop its current action and start over. The system constantly watches the partner's moves and compares them to what the AI expects based on its current guess of the partner's plan. When the partner does something that clearly contradicts that guess, the AI immediately interrupts its own work and recalculates a new plan.

The key innovation is that this interruption happens only when necessary. Many existing methods either never change their plans once started, or they change them too often, wasting time and energy. The new system uses a statistical method to track the partner's likely skill. It waits until the evidence is strong and consistent before acting. If the partner makes a single odd move that could be a mistake, the AI ignores it. But if the partner's actions consistently show they are doing something completely different than expected, the AI stops what it is doing and asks for a new plan. This approach prevents the AI from getting stuck in a loop of doing the wrong thing while knowing it is wrong.

The researchers tested this system in various kitchen layouts, including open spaces and circular arrangements, pairing their AI with different types of partners who had distinct preferences for how to cook. They compared their new agent against other methods that either replanned at fixed time intervals, replanned whenever a specific event happened, or relied on a separate AI judge to decide when to change plans. The results showed that the new agent achieved similar or better scores in terms of how many meals were successfully delivered, but it did so with far fewer interruptions. While other methods had to stop and restart their plans dozens or even hundreds of times per game, the new agent typically needed to replan only a handful of times. This efficiency came from its ability to distinguish between noise and a genuine change in strategy.

Crucially, the study revealed that having a correct guess about a partner's role is not the same as coordinating well. In one set of tests, the new agent and a standard agent both guessed the partner's skill with nearly the same accuracy. Yet, the standard agent continued to execute outdated plans long after the partner had changed, leading to a high rate of duplicate efforts where both agents tried to do the same task. The new agent, by contrast, used its correct guess to trigger a change in behavior at the right moment. This reduced the "belief-action gap," a measure of how often an agent knows the truth but fails to act on it. The study suggests that for AI to truly collaborate, it needs more than just a model of its partner; it needs a reliable signal to know when that model has become obsolete and when to switch gears.

The researchers also tested whether the system worked better if the partner's information was just fed into the planning process as background context, or if it was used as a direct trigger to stop and restart. They found that using the information as a trigger was far more effective. Simply telling the AI "your partner is doing X" did not guarantee it would change its plan. The system only improved when the information was used to actively interrupt the current action. This distinction highlights that the value of understanding a partner lies in the ability to act on that understanding immediately, rather than just holding it in memory.

Despite these successes, the researchers acknowledge limitations. The system currently relies on a fixed list of pre-defined skills, such as "chopping" or "cooking," rather than learning new skills on the fly. In very tightly coupled environments where the two agents must move in perfect sync, the system was less effective, suggesting that the underlying planning brain of the AI still needs improvement. The team notes that future work will need to address how to learn these skills automatically and how to handle partners whose strategies change even more rapidly. For now, however, the work demonstrates a clear path forward: by connecting the understanding of a partner directly to the decision of when to stop and start again, AI agents can move from merely observing their teammates to truly working with them.

Technical Summary: Bayesian Partner Modelling Enables Adaptive Replanning for LLM Coordination

Problem Statement

Multi-agent Large Language Model (LLM) systems frequently struggle to collaborate with new teammates whose strategies shift mid-task. While agents may successfully infer a partner's intent (a capability associated with "Theory of Mind"), they often fail to translate this updated belief into timely behavioral changes. Specifically, agents tend to continue executing outdated, multi-step skills even after public evidence indicates a partner has changed their strategy. This creates a belief–action gap: the agent possesses an accurate model of the partner's current role but fails to interrupt its own ongoing execution to select a complementary skill. Existing methods either treat partner tracking as passive context (leading to slow reaction times) or trigger replanning indiscriminately (causing excessive computational churn).

Methodology: BayesBeliefAgent

The authors introduce BayesBeliefAgent, a hierarchical LLM coordination agent designed to bridge the gap between partner belief and control. The system operates through three core mechanisms:

1. Online Bayesian Partner-Skill Belief Update

The agent maintains a recursive posterior belief $b_t(\psi)$ over the teammate's active skill $\psi$ from a finite skill library $\Psi$ . Since the teammate's high-level policy is unobservable, the agent infers the skill using Bayesian inverse planning based on publicly observable primitive actions.

Inference Window: The agent updates beliefs over a recent trajectory segment, assuming the teammate's skill remains fixed within a window of $k$ steps.
Likelihood Approximation: Because the true teammate low-level controller is unknown, the agent approximates the action likelihood using its own low-level action controller $\pi^i_{low}$ to predict what the partner would do if they were executing a specific skill $\psi$ .
Prior Initialization: The prior belief is initialized using a smoothed count model based on the history of completed partner skills within the current episode, allowing the agent to learn behavioral preferences over time.

2. Contradiction-Conditioned Skill Interruption

Rather than replanning constantly, the agent employs a gated interruption mechanism. The agent evaluates the likelihood of the teammate's newly observed actions under the current Maximum A Posteriori (MAP) skill estimate.

Contradiction Signal: If the likelihood of the observed actions falls below a threshold $\theta_{obs}$ , a contradiction signal is triggered.
Interruption Gates: To prevent noise-induced replanning, interruption occurs only if:
1. A contradiction is detected.
2. The MAP skill estimate has remained stable over recent updates.
3. The current belief confidence exceeds a threshold $\Gamma_{conf}$ .
4. The ego agent is currently mid-skill and not in a cooldown period.

3. Selective Replanning

When the interruption gates are satisfied, the agent halts its current skill and invokes the high-level LLM planner. The planner receives the updated posterior belief and the new MAP estimate as coordination context to select a complementary skill. This ensures the agent only replans when the current plan is demonstrably inconsistent with the partner's behavior.

Key Contributions

Method: The introduction of BayesBeliefAgent, which uses likelihood-based contradictions under a current teammate-skill estimate to selectively interrupt and replan, rather than relying on periodic or event-based triggers.
Diagnostics: A novel evaluation protocol defining the belief–action gap rate (the fraction of decisions where the agent has a correct partner estimate but executes a non-complementary skill), contradiction-conditioned recovery, and replan efficiency. These metrics reveal coordination failures that aggregate reward metrics often obscure.
Evidence: Empirical results demonstrating that posterior-gated interruption converts partner beliefs from passive context into active control signals, significantly narrowing the belief–action gap while requiring orders of magnitude fewer replans than heuristic baselines.

Experimental Results

The system was evaluated in Overcooked and Burrito environments across three layouts (Open, Ring, Forced Coordination) and three groups of partners with diverse behavioral preferences.

Coordination Performance: BayesBeliefAgent outperformed LLM-based baselines (ProAgent, Hypothetical Minds) in Open and Ring layouts, particularly against partners with distinct logistics or sourcing preferences. However, RL-based baselines (TALENTS, GAMMA) generally achieved higher raw rewards, indicating that the underlying LLM planner remains a performance bottleneck.
Closing the Belief–Action Gap: Despite achieving nearly identical teammate-skill prediction accuracy to the baseline ProAgent, BayesBeliefAgent significantly reduced the belief–action gap (e.g., from 0.41 to 0.20 in the Open layout) and reduced duplicate-skill rates.
Replan Efficiency: The method achieved comparable rewards to generic replanning heuristics (Periodic-10, Completion-triggered, LLM-judge) but with drastically fewer replans. For instance, in the Open G1 setting, BayesBeliefAgent averaged 2.0 replans per episode, whereas heuristics triggered between 43 and 169 replans for similar performance.
Ablation Studies: Experiments confirmed that using the posterior as a control signal (triggering interruption) is more effective than using it merely as context in the planner prompt. Direct coupling of belief to replanning decisions was shown to be the primary driver of improved coordination.

Significance and Claims

The paper argues that effective multi-agent coordination requires more than just accurate partner modeling; it requires a principled mechanism for deciding when to act on that model. The authors claim that:

Belief is insufficient without control: Correctly inferring a partner's intent does not guarantee coordination if the agent fails to interrupt an obsolete plan.
Selective replanning is superior to frequent replanning: Reacting to every behavioral change causes excessive churn. Detecting specific contradictions against a stable belief allows for efficient adaptation.
Bridging the ToM Gap: The work addresses the "literal–functional Theory of Mind" gap by demonstrating that updating beliefs must be directly coupled with control signals to prevent agents from continuing to execute redundant or conflicting strategies.

The authors modestly note limitations, specifically that the method relies on a fixed, manually specified skill library and is less effective in tightly coupled environments (Forced Coordination) where the underlying LLM planner's limitations are more pronounced. They identify learning the skill space and jointly adapting belief estimation with action selection as necessary future directions.