PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Hengli Li, Zhaoxin Yu, Qi Shen, Chenxi Li, Mengmeng Wang, Tinglang Wu, Yipeng Kang, Yuxuan Wang, Song-Chun Zhu, Zixia Jia, Zilong Zheng

arXiv:2512.24885v1cs.CLcs.GTcs.MA

TL;DR

Prior work often estimates beliefs in strategic dialogue without a principled way to use them during generation. BEDA formalizes adversarial and alignment acts as probabilistic constraints and uses a world set, belief estimators, and a conditional generator. Across adversarial, cooperative, and negotiation settings, it reports improved strategic reliability over baselines.

  • Problem

    Prior methods model beliefs but often pass available belief information to generation without a principled criterion for what to reveal and how.

    Source: §1 · p. 1

  • Method

    BEDA treats estimated beliefs as constraints on Adversarial and Alignment acts and uses a world set, belief estimators, and a conditional generator to select events and generate utterances.

    Source: §1 · p. 1, §2.3 · p. 4

  • Results

    Across CKBG, Mutual Friends, and CaSiNo, BEDA improves strategic reliability, including up to +20.6 points on CKBG with GPT-4.1-nano and higher-quality CaSiNo agreements than strong prompting baselines.

    Source: §1 · p. 2, §8 · p. 9

  • Takeaways & Limitations

    The results indicate that constraining generation by inferred belief structure is an effective organizing principle for dialogue agents, complementary to generic dialogue heuristics such as CoT or selfreflection.

    Source: §8 · p. 9

    The work holds the world set fixed, leaving dynamic online expansion, pruning, or reweighting for future work.

    Source: §7 · p. 8

Abstract

from arXiv · show

Strategic dialogue requires agents to execute distinct dialogue acts, for which belief estimation is essential. While prior work often estimates beliefs accurately, it lacks a principled mechanism to use those beliefs during generation. We bridge this gap by first formalizing two core acts Adversarial and Alignment, and by operationalizing them via probabilistic constraints on what an agent may generate. We instantiate this idea in BEDA, a framework that consists of the world set, the belief estimator for belief estimation, and the conditional generator that selects acts and realizes utterances consistent with the inferred beliefs. Across three settings, Conditional Keeper Burglar (CKBG, adversarial), Mutual Friends (MF, cooperative), and CaSiNo (negotiation), BEDA consistently outperforms strong baselines: on CKBG it improves success rate by at least 5.0 points across backbones and by 20.6 points with GPT-4.1-nano; on Mutual Friends it achieves an average improvement of 9.3 points; and on CaSiNo it achieves the optimal deal relative to all baselines. These results indicate that casting belief estimation as constraints provides a simple, general mechanism for reliable strategic dialogue.

1 INTRODUCTION

Strategic dialogue depends on estimating interlocutors’ beliefs and using them selectively during generation, but prior methods often pass along belief information without a principled criterion. BEDA formalizes Adversarial and Alignment acts as constraints on generated content and evaluates this approach across strategic dialogue settings.

1 INTRODUCTION

  • Strategic dialogue acts can shape interlocutors’ beliefs toward an agent’s objectives, such as emphasizing common preferences in negotiation or taking an adversarial stance toward individual differences.The paper identifies negotiation, debate, deception for good, and common-ground alignment as settings where such acts arise.Source: §1 · p. 1
  • Prior work has emphasized explicit belief modeling but often relays all available belief information without a principled criterion for what or how to reveal it.The paper argues this can be suboptimal when belief states are complex.Source: §1 · p. 1
  • Adversarial acts introduce or emphasize events outside an interlocutor’s belief support, while Alignment acts restrict utterances to shared common knowledge.The paper treats belief estimates as constraints on the permissible space of dialogue acts during generation.Source: §1 · p. 1
  • Across CKBG, Mutual Friends (MF), and CaSiNo, BEDA improves all evaluation settings; on CKBG it improves 20.6 over baseline with GPT-4.1-nano, and MF success rate improves up to 30.4 versus the vanilla baseline.Source: §1 · p. 2
  • The introduction presents BEDA as integrating belief estimation with dialogue-act generation and reports refining the Keeper–Burglar dataset for evaluation.Its evaluation argues that accurate estimation functions as a constraint on both adversarial and alignment behaviors.Source: §1 · p. 2

2 BEDA

BEDA formulates dialogue-act generation as constrained optimization over events and utterances using estimated beliefs. Its components combine a world set, belief estimators, and a conditional generator, with only the belief estimator trained in the described learning setup.

2.1 Preliminaries: Logical Definition of Beliefs

  • The preliminaries define an information partition over a finite state set and an event as a subset of states; an agent knows an event when its information subset lies within that event.The section also introduces probabilistic beliefs over states and events.Source: §2.1 · pp. 2–3

2.2 Belief Information as Probabilistic Constraints

  • Adversarial acts communicate events the speaker believes true but the listener does not know, whereas Alignment acts convey events within shared common ground.The paper frames estimated beliefs as constraints on permissible generation and models event–utterance probabilities using Bayes’ rule, an LLM, and maximum entropy over constraint-satisfying events.Source: §2.2 · p. 3
  • Under either dialogue act, generation is formulated as constrained optimization; in practice, the paper says P_A can be modeled with a discriminator neural network.The constraints determine which events or utterances are feasible for the selected act.Source: §2.2 · p. 3

2.3 Components of the BEDA framework

  • BEDA’s world set contains relevant dialogue or environment events, and its belief estimators predict both event truth and the interlocutor’s knowledge of events.The conditional generator selects events according to the estimated beliefs and dialogue act, then generates an utterance from the event and context; the world set is fixed in this work.Source: §2.3 · pp. 3–4

2.4 Learning and Inference of BEDA

  • The described training setup fixes the conditional-generation LLM and trains only the belief estimator with supervised dialogue data whose beliefs are known.Training and inference use separate data to avoid leakage; the authors report that supervised belief estimators generalize well to unseen settings.Source: §2.4 · p. 4

3 DATASETS

The experiments cover competitive, cooperative, and mixed negotiation settings, with each dataset’s world set and belief estimator tailored to its task. CKBG adds environmental conditions to the Keeper–Burglar game, while MF and CaSiNo use friend attributes and negotiators’ preferences, respectively.

3 DATASETS

  • The evaluation uses competitive, cooperative, and mixed experiments, testing Adversarial acts in CKBG and Alignment acts in Mutual Friends.The framework is implemented on one agent in CKBG and on both agents in the other experiments.Source: §3 · p. 4

Conditional Keeper-Burglar Game (CKBG)

  • CKBG extends the Keeper–Burglar game with environmental conditions, and the belief estimator predicts which conditions the burglar knows.The keeper forwards conditions it knows but the burglar does not to conditional generation.Source: §3 · p. 4
  • The CKBG dataset’s reported statistics include condition counts, known conditions, training-dialogue word counts, average conditions per setting, and vocabulary size.The passage defines the statistical columns but does not provide their values.Source: Table 1 · p. 4

Mutual Friends (MF)

  • Mutual Friends is a cooperative task to identify a shared friend, represented through the friend’s attributes and estimates of the other player’s beliefs about them.Conditional generation uses the other player’s estimated beliefs to produce information within common ground.Source: §3 · p. 4

CaSiNo

  • CaSiNo models campsite-neighbor negotiations with preferences for both negotiators and separate estimators for the opponent’s preferences and our preferences from the opponent’s perspective.Alignment selects mutually known elements, while adversarial acts select elements known only to our side; both condition generation.Source: §3 · p. 4

4 EXPERIMENT

The experiments evaluate BEDA across CKBG, Mutual Friends, and CaSiNo using multiple language-model backbones and task-specific metrics. BEDA improves CKBG success rates and MF success and efficiency measures, and achieves the highest average agreement reward among evaluated methods in closed-source CaSiNo experiments.

4 EXPERIMENT

  • The section reports results across three experiments, with figures and tables presenting CaSiNo, CKBG, and Mutual Friends results.CaSiNo experiments are repeated three times except those using GPT-4.Source: §4 · p. 4, Table 2 · p. 5, Table 3 · p. 5

4.1 Settings

  • The evaluation reports success rate for CKBG and MF, with MF efficiency ratios, and agreement rate and reward for CaSiNo.The experiments use GPT, LLaMA, and Qwen backbones; open-source models use q4_k_m quantization, with act-specific epsilon held constant across backbones.Source: • CKBG · pp. 4–5

4.2 Conditional Keeper-Burglar Game (CKBG)

  • 5.0 is the minimum CKBG success-rate increase over w/o belief, while BEDA’s average gains over CoT and Self-Reflect are 15.5% and 15.4%, respectively.The maximum increase over w/o belief is 20.6 with Qwen2.5-14b; Table 2 presents CKBG results.Source: Table 2 · p. 5, §4.2 · p. 6

4.3 Mutual Friends (MF)

  • 9.3 points is BEDA’s average Mutual Friends success-rate gain over the w/o belief variant; it also achieves state-of-the-art results on four backbones.On GPT-3.5, the maximum improvement is 30.4; Table 3 reports the Mutual Friends results.Source: Table 3 · p. 5, §4.3 · p. 6
  • BEDA has the highest average success rate and fewest average turns on Mutual Friends, with an average SR/# Avg. Turn improvement of 2.3 over w/o belief.Its SR/# Avg. Token reaches 0.11, the highest among comparison methods; richer exchange produces longer individual utterances but fewer turns.Source: §4.3 · pp. 6–7

4.4 CaSiNo

  • BEDA achieves the highest average agreement reward among evaluated methods for closed-source CaSiNo models and generates higher-quality deals than baselines with LLaMA2 (7B).Its average agreement rate is competitive for GPT-3.5 and GPT-4; Figure 2a reports reward and Figure 2b reports agreement rate.Source: Figure 2 · p. 6, §4.4 · p. 7

5 FURTHER ANALYSIS

The further analysis examines case studies of belief-guided dialogue and the reliability of belief estimation, including weaker performance on CaSiNo.

5.1 Case Study

  • The CKBG case study describes belief predictions becoming more accurate as dialogue unfolds.The example is generated by GPT-4.1.Source: §5.1.1 · p. 7

5.1.1 Conditional Keeper-Burglar Game (CKBG).

  • In the CKBG case, the estimator updates shared beliefs with an implicitly mentioned container-opening event and detects the burglar's suspicious attitude.The keeper then responds vaguely while maintaining ambiguity in line with the estimated belief context.Source: §5.1.1 · p. 7
  • In the Mutual Friends comparison, CoT often reproduces the backbone output verbatim and performs worse than BEDA for Alignment Dialogue Acts.The comparison uses identical samples and shows only the first two turns.Source: §5.1.2 · p. 7

5.1.2 Mutual Friends (MF).

  • In MF, belief constraints can relieve friend-list comparison and looping hallucinations; one case ends with the burglar choosing Tupperware instead of the watch's container, resin.The reported hallucinations include failing to isolate a mutual friend and reintroducing eliminated candidates.Source: §5.1.2 · p. 7

BEDA (Ours)

  • Belief estimation reaches approximately 0.9 accuracy on synthetic MF and CKBG, while CaSiNo performance is lower amid its cooperative-competitive setting and more difficult multi-class beliefs.The authors attribute the CaSiNo gap to these setting-specific challenges.Source: §5.2 · p. 7, BEDA (Ours) · p. 8

6 RELATED WORKS

The related work covers dialogue-act generation and belief-based modeling of other agents, alongside earlier approaches to persuasion, negotiation, and debate.

Dialogue Acts Generation

  • Dialogue-act research has shifted from classification toward generation, with persuasion, negotiation, and debate studies addressing different interaction goals and strategies.The cited work includes attitude modification in persuasion, emotional intelligence, negotiation [7, 11, 24, 48], and debate argumentation.Source: §6 · p. 8
  • Text-based social deduction games are established application settings for dialogue-act generation.Source: §6 · p. 8

Theory-of-Mind and Opponent Modeling

  • Theory of Mind models beliefs and intentions to predict behavior, and appears in LLM belief-state studies and opponent modeling for reinforcement learning and strategic games.The passage cites ToM, LLM studies, and opponent-modeling work.Source: §6 · p. 8

7 DISCUSSION AND FUTURE WORKS

The discussion considers estimator efficiency, a fixed-world-set assumption, and the coarse granularity of the dialogue-act categories.

Applying LLMs for belief estimation

  • A compact encoder estimates beliefs with accuracy comparable to an LLM at a fraction of the computational cost, while LLM estimators are reserved for broader world knowledge or distribution-shift robustness.Source: §7 · p. 8

Dynamic construction of the world set

  • The experiments hold the world set fixed; future work could learn to expand, prune, or reweight it online using interaction signals.The authors suggest this could improve coverage and downstream performance.Source: §7 · p. 8

Finer modeling of dialogue acts

  • The two broad dialogue-act categories subsume specific acts such as Agreement; finer-grained or hierarchical schemas may improve control and learning credit assignment.Examples of finer distinctions include Agreement, Concession, Hedging, and Commitment.Source: §7 · p. 8

8 CONCLUSIONS

The conclusion presents BEDA as a constraint-based framework for strategic dialogue and reports improvements across adversarial, cooperative, and negotiation settings. It also describes the study's ethical safeguards and implementation scope.

8 CONCLUSIONS

  • BEDA uses inferred belief structure as probabilistic constraints for strategic dialogue acts, with a world set, dual belief estimators, and a conditional generator.The acts are Adversarial, which introduces or emphasizes events outside an interlocutor's belief support, and Alignment, which restricts utterances to common ground.Source: §8 · p. 8
  • Across CKBG, MF, and CaSiNo, BEDA improves strategic reliability, including up to +20.6 points on CKBG with GPT-4.1-nano and higher-quality CaSiNo agreements than strong prompting baselines.MF success gains are 4.3–11.2 points, with up to +30.4 in some configurations, while reducing turns.Source: §8 · p. 9

A ETHICS STATEMENT AND SOCIETAL IMPACT

B DERIVATION OF THE CONSTRAINT OPTIMIZATION

  • The constraint derivation treats the event distribution given common knowledge as constant because events are chosen equally to avoid introducing new constraints.This makes the optimization problem equivalent to the subsequent form described in the derivation.Source: B DERIVATION OF THE CONSTRAINT… · p. 11

C DETAILS ON LARGE LANGUAGE MODELS

E CONDITIONAL KEEPER-BURGLAR GAME (CKBG)

  • The CKBG extends the Keeper-Burglar game with environmental conditions, including container inspections and noises, to diversify and contextualize interactions.The original game has the homeowner mislead a burglar about which of two containers holds a valuable item.Source: §E.0.1 · p. 11

E.0.1 The CKBG Task.

The CKBG setup randomizes conditions between keeper and burglar, then uses a world set and estimated beliefs to constrain conditional generation. The section also describes the Mutual Friends task as a cooperative search for a shared friend.

E.0.1 The CKBG Task.

  • 450 condition instances form the CKBG test set, with five condition classes randomly assigned to keeper and burglar.The listed classes are informer, burglar inspection, keeper inspection, outsider inspection, and noise.Source: §E.0.2 · p. 11

E.0.2 Construction of CKBG Dataset.

  • The CKBG dataset extends Hagendorff with contextual conditions intended to add variability and information asymmetry.Its world set organizes potential conditions into five categories, from which conditions are selected for the burglar’s background information.Source: §E.0.3 · p. 11

E.0.3 Details of World Set Designation and Selection Process.

  • The keeper’s listed conditions are treated as known, while a neural network predicts the burglar’s beliefs and passes events believed unknown to conditional generation.The belief estimator uses BERT utterance representations, event embeddings, self-attention, and an MLP with softmax to predict awareness of each event.Source: §E.0.3 · p. 12, §E.0.4 · p. 12

F MUTUAL FRIEND (MF)

  • Mutual Friends has two players exchange information about distinct friend lists containing exactly one shared friend, aiming to identify and select that same person.Success requires both players to confirm the mutual friend and select the same individual.Source: §F.0.1 · p. 12

F.0.1 The MF task.

The MF setup uses belief-conditioned generation to support coordination about a shared friend. For CaSiNo, the world set encodes preference rankings and supports both alignment and adversarial generation.

F.0.1 The MF task.

  • MF agents use a symmetric two-agent setup, with conditional generation assessing whether they have identified a mutual friend before final selections.The evaluation ends when both confirm a friend or reach the 20-turn limit; success requires both to select the same person.Source: §F.0.3 · p. 13

F.0.3 Experimental Details.

  • MF belief estimation classifies utterance–attribute–value triples, and its estimator achieved 90.1% test accuracy.The BERT-based estimator predicts whether the other player’s perceived attribute value matches the given value.Source: §F.0.3 · p. 13

G.0.1 Details of World Set Designation and Selection Process.

  • CaSiNo’s world set represents resource-preference rankings, and its classifier selects a most-probable ranking for the prompt.Conditional generation receives one event for alignment and one for adversarial generation; alignment uses the first 12 conditions and adversarial generation the last 12.Source: §G.0.1 · pp. 13–14

G.0.2 Experimental Details.

The CaSiNo estimator is assessed through pairwise preference comparisons. The failure cases describe belief-use and hallucination problems in CKBG and Mutual Friends.

G.0.2 Experimental Details.

  • CaSiNo fine-grained accuracy measures the proportion of correct pairwise preference relationships across each example’s three-resource ranking.The estimator performs six-class classification to select preference permutations for both negotiators.Source: §G.0.2 · p. 14

H FAILURE CASE STUDY

  • In a CKBG failure, the keeper did not use belief information effectively, and one estimated belief incorrectly marked a burglar-known event as unknown.The burglar therefore remained unmisl ed by the keeper.Source: H FAILURE CASE STUDY · p. 14
  • A Mutual Friends failure involved an agent hallucinating a friend’s hobby, which led to an incorrect final decision.The cited passage also identifies hallucinations in GPT-4 Mutual Friends runs without belief-state constraints.Source: H FAILURE CASE STUDY · pp. 14–15

I DISCUSSION AND FUTURE WORKS

The discussion argues that a smaller encoder can estimate beliefs, while reporting a limitation for unmodified Llama models on Mutual Friends. Dynamic world-set construction is left for future work.

I DISCUSSION AND FUTURE WORKS

  • The authors consider a smaller encoder sufficient for belief estimation, although using an LLM for estimation remains possible.They report that their experimental results show a simple encoder can capture beliefs from conversations.Source: I DISCUSSION AND FUTURE WORKS · p. 15
  • Unmodified Llama models achieved no more than 5% success across five Mutual Friends settings in 50 sampled test cases.The authors attribute this outcome to difficulty extracting information from the larger friend-list world set, leading to generation hallucinations.Source: I DISCUSSION AND FUTURE WORKS · p. 15
  • The paper focuses on connecting belief estimation with dialogue acts and identifies dynamic world-set construction as future work.The current framework takes the world set as given rather than constructing it dynamically.Source: I DISCUSSION AND FUTURE WORKS · p. 15

1. Unable to understand the task setup (Llama-2-7b (cot))

  • In the first round, Bob proposes identifying their mutual friend quickly and, after checking his list, says Megan is the only friend they share.In rounds 10–13, Alex and Bob alternate describing a friend: Alex repeats the Baylor, Metallurgical Engineering, and Inline skating profile, while Bob repeats the West Liberty State College, Agricultural Business & Management, and Dog sport profile.Source: §1 · p. 18, §3 · p. 18
Loading 2512.24885v1…