MultiTalk: A Highly-Branching Dialog Testbed for Diverse Conversations

Yao Dou, Maxwell Forbes, Ari Holtzman, Yejin Choi

Abstract

Most conversational AI is trained on linear datasets, ignoring the inherent "what if" nature of human interaction. We introduce MultiTalk, a massive dataset of branching conversations where every turn offers 10 distinct possible responses. To evaluate this complexity, we propose a novel scoring metric based on bipartite graph matching that rewards diversity and present a "Theory of Mind" task where models must influence a listener's emotional state.

Introduction: Beyond Linear Dialog

Most conversational AI research relies on datasets where one prompt leads to exactly one response. This linear approach fails to capture the richness of human social interaction, where a single statement can lead to dozens of valid continuations. Furthermore, standard metrics like BLEU are ill-suited for diverse generation; they either penalize creativity or allow models to "cheat" by repeating safe, high-probability responses. MultiTalk aims to provide both the data and the evaluation framework to move conversational AI toward true, multi-path human-like diversity.

The MultiTalk Dataset

The MultiTalk dataset consists of over 320,000 sentences across 120 conversation trees. Each turn features a branching factor of 10 and a depth of 6 turns. These human-written responses ensure high relevance and fluency. Human evaluations show that MultiTalk references are consistently rated as more diverse and relevant than outputs from state-of-the-art models like GPT-2 XL.

MultiTalk branching structure and Theory of Mind task illustration.

Evaluation via Bipartite Graph Matching

To evaluate a set of $n$ generated responses against $n$ references, we employ a bipartite graph matching approach using the Kuhn-Munkres algorithm. This finds the optimal one-to-one mapping between generations and references that maximizes the total score (e.g., BLEU or BERT-Score). This "fair" assignment ensures that a model must produce a diverse set of high-quality responses to score well, preventing the exploitation of repetitive "safe" responses.

Bipartite graph matching metric and model performance comparison.

Modeling and Results

We introduced a Dialog Tree Model, a fine-tuned GPT-2 adapted for tree structures. By calculating loss only on the final utterance of a given path, we prevent bias toward frequent early turns. The Dialog Tree Model achieved a BLEU-4 matching score of 0.28, doubling the performance of GPT-2 XL (0.14). Human evaluations confirmed these gains, with the Dialog Tree Model rated significantly more relevant and fluent than its baseline counterparts.

Theory of Mind and Future Frontiers

MultiTalk enables a "Theory of Mind" task: intentionally influencing a partner's emotion. We developed a Lookahead Model that incorporates a recursive estimate of future emotional states. While this model achieved the lowest perplexity, inducing specific target emotions remains difficult. Current models often fall back on "mirroring"—expressing the target emotion themselves—rather than employing complex social strategies.

Researchers also identified a "Reference Gap": with only one reference, standard metrics cannot distinguish between a diverse model and a repetitive one. Approximately 10 references are required to clearly stratify model performance by diversity. While our Dialog Tree Model improves quality, future work must explore architectures that explicitly optimize for diverse paths. The Theory of Mind task remains an open challenge, suggesting that current LLMs lack a deep understanding of how their words impact the internal states of others.

Summary updated

Abstract

We study conversational dialog in which there are many possible responses to a given history. We present the MultiTalk Dataset, a corpus of over 320,000 sentences of written conversational dialog that balances a high branching factor (10) with several conversation turns (6) through selective branch continuation. We make multiple contributions to study dialog generation in the highly branching setting. In order to evaluate a diverse set of generations, we propose a simple scoring algorithm, based on bipartite graph matching, to optimally incorporate a set of diverse references. We study multiple language generation tasks at different levels of predictive conversation depth, using textual attributes induced automatically from pretrained classifiers. Our culminating task is a challenging theory of mind problem, a controllable generation task which requires reasoning about the expected reaction of the listener.
BibTeX
@inproceedings{dou2021multitalk,
  author = {Yao Dou and Maxwell Forbes and Ari Holtzman and Yejin Choi},
  title = {{MultiTalk: A Highly-Branching Dialog Testbed for Diverse Conversations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i14.17510},
}
Figure