BEDA: Belief Estimation as Probabilistic Constraints for Performing Strategic Dialogue Acts

You know how when you play games like Guess Who? you don’t just blurt out everything—you ask questions that fit what both players already know? Before this paper, many chatty AIs were pretty good at guessing what someone else might think (their beliefs), but not so good at using those guesses to choose exactly what to say next. That meant they could list or reason about lots of facts, yet still talk in unhelpful ways—oversharing, repeating, or revealing things at the wrong time.

The world before: Large language models (LLMs) became great at talking, explaining, and even reasoning with tools like Chain-of-Thought. Researchers also began teaching AIs about what others know (sometimes called theory of mind), which helps in tricky conversations like negotiation, debate, or finding common ground. But there was a missing step: Once you estimate what the other person believes, how do you directly turn that estimate into better, more strategic talk?

The problem: Existing approaches often poured all belief information into a prompt and hoped the LLM would figure out how to use it. In messy situations, that floods the model with details. The AI might mention facts the other person already knows (wasting turns) or reveal things the other person shouldn’t know (hurting strategy). It’s like having a map but no rulebook for using it during the match.

Failed attempts: Popular prompting tricks like Chain-of-Thought (think out loud) and Self-Reflect (revise yourself) can improve reasoning, but they don’t give a clear, enforceable rule for what’s allowed to be said right now. Another approach, MindDial, gives the LLM all known beliefs, but without constraints it can still choose unhelpful or off-target details. Randomizing beliefs is even worse—like giving random clues in a treasure hunt.

The gap: What was missing was a principled, mathematical bridge from “what I believe and what you believe” to “what I’m allowed to say for this specific strategy.” In other words, a way to turn beliefs into constraints—soft rules that filter which utterances are okay for a chosen dialogue act (like aligning or pushing adversarially).

What this paper brings: BEDA (Belief Estimation as probabilistic constraints for Dialogue Acts) says: don’t just estimate beliefs—use them as constraints that shape generation. Two core acts get formal rules: Alignment (stick to common ground) and Adversarial (confidently introduce things the other likely doesn’t know). The system builds a small world set (possible events/facts), estimates which events are true and which the other person knows, then lets the LLM speak only using events that pass the act’s constraints.

Real stakes (why you should care):

• Negotiations: Saying just the right shared fact builds trust; hiding non-shared info protects leverage.
• Teamwork: Clear, on-target clues help partners find answers faster (fewer turns, fewer words).
• Safety and honesty: Controlling what’s revealed reduces accidental leaks and curbs hallucinated detours.
• Efficiency: A small encoder can steer a big frozen LLM, saving compute while improving outcomes.
• Everyday relevance: From customer support to classroom helpers, conversations get shorter, clearer, and more successful when guided by belief-aware rules.

In short, the paper turns belief estimation from a side note into the steering wheel for strategic speaking.

The “Aha!” in one sentence: Turn the AI’s beliefs into soft rules (probabilistic constraints) that filter what it’s allowed to say for each strategic move—Alignment or Adversarial—so generation stays helpful and on-target.

Three analogies:

1. Flashlight in a dark attic: Beliefs are your sense of where the good stuff is; constraints are the mask around your flashlight beam that blocks glare and keeps you focused right where it matters for this moment.
2. Sports playbook: The team knows many plays (beliefs), but the coach calls just one that fits the situation (constraints), so players don’t collide or waste time.
3. Food allergies at a picnic: You might have lots of tasty dishes (facts), but constraints (no nuts, no dairy) decide what you can actually serve now so everyone stays safe and happy.

Before vs. after:

• Before: The AI estimated beliefs but dumped everything into prompts, hoping the LLM would figure it out; results were often wordy, repetitive, or strategically clumsy.
• After: The AI estimates beliefs and then constrains generation: Alignment only permits shared knowledge; Adversarial only permits confident facts the opponent likely doesn’t know. The LLM now speaks with a purpose.

Why it works (intuition, not equations):

• Constraints are filters. They shrink the space of possible utterances to the ones that make sense for your goal (cooperate or challenge).
• Less wandering means fewer hallucinations and tighter teamwork.
• The LLM remains the language expert, but beliefs hold the steering wheel.
• When multiple candidate facts pass the constraints, choose among them without extra bias (treat allowed options fairly), then let the LLM phrase it naturally.

Building blocks (explained with the sandwich pattern, in dependency order):

🍞 Top Bread (Hook): You know how you can often guess what a friend thinks based on past chats? 🥬 The Concept: Belief Estimation is the AI’s way of guessing what’s true in the world and what the other person knows.

• How it works: (1) Read the dialogue so far; (2) Check each possible event; (3) Score how likely it’s true; (4) Score how likely the other person knows it; (5) Update as more messages arrive.
• Why it matters: Without it, the AI talks blindly—oversharing, repeating, or missing key clues. 🍞 Bottom Bread (Anchor): In a friend-finding game, belief estimation might say, “We both probably know they work at Salem Communications,” so it can focus there.

🍞 Top Bread (Hook): Imagine a menu of all possible facts you could mention. 🥬 The Concept: The World Set is that menu—a list of relevant events the AI can consider.

• How it works: (1) Collect possible events from the task; (2) Keep them simple (true/false); (3) Track which are shared or private; (4) Update beliefs over them.
• Why it matters: Without a menu, the AI rummages in an infinite fridge and wastes time. 🍞 Bottom Bread (Anchor): In Keeper–Burglar, “Noise comes from the resin container” is one event on the world set.

🍞 Top Bread (Hook): Think of a filter that lets through only the right clues. 🥬 The Concept: Probabilistic Constraints are soft rules that say, “Only talk about events that pass these belief checks for this move.”

• How it works: (1) Pick your act (Alignment or Adversarial); (2) Keep events that fit the act’s belief tests; (3) Treat the kept ones fairly; (4) Let the LLM speak using a kept event.
• Why it matters: Without constraints, the AI might reveal too much or say unhelpful things. 🍞 Bottom Bread (Anchor): If you want to align, you only speak about facts both sides likely know; if you want to be adversarial, you pick facts you’re confident in but the other likely doesn’t know.

🍞 Top Bread (Hook): When you and a partner build a puzzle, you talk about the pieces you both see. 🥬 The Concept: Alignment Dialogue Act means sharing from common ground—facts both sides likely know—to coordinate and build trust.

• How it works: (1) Check which events are shared; (2) Select one; (3) Phrase it clearly; (4) Invite the other person to confirm or build on it.
• Why it matters: Without alignment, teams waste turns and talk past each other. 🍞 Bottom Bread (Anchor): In Mutual Friends, you might say, “We both know the friend works at Salem Communications.”

🍞 Top Bread (Hook): In chess, a surprise move can change the game. 🥬 The Concept: Adversarial Dialogue Act means confidently emphasizing a fact the other likely doesn’t know, to shift the conversation in your favor.

• How it works: (1) Find a high-confidence event; (2) Check the other likely doesn’t know it; (3) Present it strategically; (4) Watch their response.
• Why it matters: Without it, you can’t protect your interests or steer outcomes when goals differ. 🍞 Bottom Bread (Anchor): In Keeper–Burglar, the keeper hints about the safer container using info the burglar hasn’t seen.

🍞 Top Bread (Hook): A great speaker still needs the right topic. 🥬 The Concept: The Conditional Generator is the LLM that speaks, but only using an event that passed the chosen constraints.

• How it works: (1) Take the selected event and dialogue history; (2) Generate a natural utterance; (3) Stay within the act’s rules; (4) Repeat next turn with updated beliefs.
• Why it matters: Without conditioning, even strong LLMs ramble, repeat, or reveal too much. 🍞 Bottom Bread (Anchor): In negotiation, given “we both value water most,” the generator proposes a split that respects that shared fact.

That’s the core: beliefs become filters, filters shape acts, and the LLM delivers the words—now with purpose.

High-level recipe: Input (dialogue + task) → Belief Estimator (what’s true; what the other knows) → Select an event that passes the chosen act’s constraints → Conditional Generator (LLM speaks with that event) → Output (the next utterance).

Step-by-step:

1. Gather the world set (the menu of events)

• What happens: The system lists all task-relevant events as simple true/false candidates (e.g., “Tupperware contains a pen cap”).
• Why it exists: It bounds the problem so the model isn’t guessing from the whole universe of facts.
• Example: CKBG includes events like “Noise from resin container” and “Keeper opened container 10 hours ago.”

1. Estimate beliefs

• What happens: A small encoder (BERT-like) reads the dialogue and scores: (a) how likely each event is true; and (b) how likely the other person knows it. These are updated turn by turn.
• Why it exists: You need grounded, up-to-date guesses to act strategically.
• Example: In Mutual Friends, after the partner says “indoors” and “Salem Communications,” the estimator boosts those shared attributes.

1. Choose a dialogue act and apply constraints

• What happens: You pick Alignment (stay in common ground) or Adversarial (confidently share what they likely don’t know). Then you filter events using simple belief checks:
  • Alignment: Keep events likely true and likely known by the other person.
  • Adversarial: Keep events likely true and likely not known by the other person. Treat remaining candidates fairly (don’t inject extra bias), then pick one to use this turn.
• Why it exists: This is the “steering wheel” that turns beliefs into actions.
• Example: In CKBG, if the burglar doesn’t know “friend opened the tin 7 hours ago,” that event is eligible for adversarial messaging.

1. Generate the utterance (conditional generator)

• What happens: The LLM takes the selected event and the dialogue history, then crafts a natural-sounding sentence that fits the act.
• Why it exists: The LLM is the language expert; we give it the right topic at the right time.
• Example: Given “shared: works at Salem Communications,” the LLM proposes narrowing to English-major vs. Greek-major to test alignment.

1. Update and repeat

• What happens: The new utterance may change what’s shared or private. The estimator refreshes scores; the next turn repeats steps 2–4.
• Why it exists: Conversations evolve; beliefs must track the flow.
• Example: In CKBG, the burglar mentions “David opened the Tupperware 3 hours ago,” which moves that event into common ground.

Training and efficiency tricks:

• Freeze the big LLM: Keep the generator fixed; only train the small belief estimator. This saves compute and keeps style consistent.
• Supervised labels: For each dataset, generate or collect ground-truth labels of which events are true and which the other person knows; train the estimator to predict them.
• Fair selection among allowed events: When multiple events pass constraints, treat them equally and let the LLM handle phrasing—no heavy hand-tuning.

Concrete walk-throughs:

• CKBG (adversarial): The world set includes inspections, noises, and who opened what when. The estimator flags what’s likely true and what the burglar knows. Adversarial filtering keeps high-confidence, not-known events. The LLM crafts a careful nudge directing the burglar toward the wrong container while staying within the event.
• Mutual Friends (alignment): The world set lists attribute-value pairs (company, major, time, location). The estimator identifies shared cues. Alignment filtering keeps likely-true, likely-known attributes, so the LLM focuses each turn on diagnostic, shared clues; fewer turns, higher success.
• CaSiNo (mixed): The world set encodes each side’s preference orderings. One alignment cue (mutually known preference) and one adversarial cue (private preference the other likely doesn’t know) can be passed to the generator to balance trust and leverage; results show higher-quality deals.

Secret sauce:

• The key is making beliefs actionable. By enforcing constraints, BEDA narrows the generation space to utterances that serve a clear strategic role, which:
  • Reduces chatter and loops,
  • Lowers hallucination risk,
  • Increases success and efficiency across tasks,
  • Works even with a small, cheap estimator and a frozen LLM.

What they measured and why:

• CKBG (adversarial): Success Rate—how often the keeper successfully misleads the burglar. This tests whether adversarial constraints help strategic deception/defense.
• Mutual Friends (alignment): Success Rate and efficiency (turns and tokens). This checks if alignment constraints speed up cooperative problem-solving.
• CaSiNo (negotiation): Agreement Rate (reach a deal) and Agreement Reward (quality of the deal). This tests whether mixing alignment and adversarial cues produces better outcomes.

Who they compared against:

• w/o belief: Just the base LLM.
• w/o belief + Chain-of-Thought: LLM reasons out loud.
• w/o belief + Self-Reflect: LLM revises its answer.
• Random belief: Uses random belief states.
• MindDial: Feeds belief info but without constraints on what to use.

Scoreboard with context:

• CKBG: BEDA consistently beats baselines. It improves success rate by at least 5 points across backbones, and by 20.6 points with GPT‑4.1‑nano—like jumping from a mid B to a solid A.
• Mutual Friends: BEDA averages a 9.3-point success boost over w/o belief (peaking at +30.4 with GPT‑3.5). It also finishes in fewer turns and with better SR per token, meaning it cooperates smarter, not just longer.
• CaSiNo: With GPT-3.5/4 and LLaMA2-7B, BEDA gets competitive agreement rates and the best agreement rewards among compared methods—akin to not just making a deal, but getting a better one.

What’s surprising:

• More thinking (CoT) isn’t always better. Without constraints, Chain-of-Thought can still meander or repeat.
• Feeding all beliefs (MindDial) can blur focus; on GPT‑4 it can perform close to random belief because there’s no rule for what to reveal now.
• A small, trained encoder (~BERT) estimates beliefs well (~0.9 accuracy on CKBG and MF) and is enough to steer a frozen LLM effectively.
• On CaSiNo, belief estimation is harder (multi-class, mixed motives), so accuracy drops, but constrained generation still improves deal quality.

Takeaway: Belief-as-constraints turns raw belief estimates into reliable, strategic gains across adversarial, cooperative, and mixed settings.

Limitations:

• Fixed world set: This work assumes the menu of possible events is given. Real conversations may require discovering and pruning events on the fly.
• Estimator dependence: If belief estimation is off (especially about what the other person knows), constraints might filter out the best clues or allow the wrong ones.
• Mixed motives are hard: Negotiations juggle trust and leverage; modeling both precisely is tough and belief accuracy drops.
• Granularity: Only two coarse acts (Alignment, Adversarial) are formalized; real dialogue uses finer moves like Hedging, Concession, or Commitment.
• Safety scope: Adversarial acts can be misused; the paper restricts to safe models and datasets, but broader guardrails are needed in deployment.

Required resources:

• A small encoder (e.g., BERT) fine-tuned on labeled belief data.
• A frozen LLM for conditional generation.
• Task-specific world set and labels (true/false; known/unknown) to train the estimator.
• Tuning epsilon-like thresholds that decide what “likely” means.

When not to use:

• Free-form creative chat where constraints might squelch imagination.
• Tiny-talk tasks where estimating beliefs costs more than it helps.
• High-stakes settings involving deception without strong safety policies.

Open questions:

• Dynamic world sets: Can the agent grow, prune, or reweight events mid-conversation?
• Finer act inventories: Add Agreement, Concession, Hedging, Commitment, etc., and learn when to switch.
• Calibration: How to keep belief probabilities well-calibrated across domains and backbones?
• Interactive learning: Can the agent ask targeted questions to fix belief gaps before acting?
• Multi-party scaling: How to handle many agents with overlapping and conflicting beliefs?

Overall, BEDA shows that constraints are a sturdy backbone for strategy, but richer world modeling and act vocabularies could push reliability even further.

Three-sentence summary: BEDA turns belief estimation into soft rules that guide what the AI is allowed to say for two core dialogue acts: Alignment (stick to common ground) and Adversarial (confidently use what the other likely doesn’t know). With a simple architecture—world set, small belief estimator, and a frozen LLM generator—BEDA consistently improves results across adversarial, cooperative, and negotiation tasks. The key win is reliability: tighter, on-target utterances that boost success and efficiency.

Main achievement: A principled bridge from beliefs to generation—probabilistic constraints—that consistently outperforms strong prompting baselines without retraining the LLM.

Future directions: Learn and update the world set dynamically; add finer-grained dialogue acts; improve belief calibration in mixed-motive tasks; and explore active questioning to reduce belief uncertainty during conversation.

Why remember this: BEDA reframes belief modeling from a sidekick to the rulebook—beliefs don’t just sit in prompts; they decide what you’re allowed to say next. That simple shift produces shorter, clearer, and more successful conversations, making AI partners more reliable in the real, strategic world.