Explore Theory of Mind: program-guided adversarial data generation for theory of mind reasoning

Authors: Melanie Sclar, Jane Dwivedi-Yu, Maryam Fazel-Zarandi, Yulia Tsvetkov, Yonatan Bisk, Yejin Choi, Asli Celikyilmaz
Primary area: applications to computer vision, audio, language, and other modalities
Keywords: theory of mind reasoning, adversarial data generation, program-guided data generation

Abstract:
Do large language models (LLMs) have theory of mind? A plethora of papers and benchmarks have been introduced to evaluate if current models have been able to develop this key ability of social intelligence. However, all rely on limited datasets with simple patterns that can potentially lead to problematic blind spots in evaluation and an overestimation of model capabilities. We introduce ExploreToM, the first framework to allow large-scale generation of diverse and challenging theory of mind data for robust training and evaluation. Our approach leverages an A* search over a custom domain-specific language to produce complex story structures and novel, diverse, yet plausible scenarios to stress test the limits of LLMs. Our evaluation reveals that state-of-the-art LLMs, such as Llama-3.1-70B and GPT-4o, show accuracies as low as 0% and 9% on ExploreToM-generated data, highlighting the need for more robust theory of mind evaluation. As our generations are a conceptual superset of prior work, fine-tuning on our data yields a 27-point accuracy improvement on the classic ToMi benchmark (Le et al., 2019). ExploreToM also enables uncovering underlying skills and factors missing for models to show theory of mind, such as unreliable state tracking or data imbalances, which may contribute to models' poor performance on benchmarks.

Decision: accept (poster)
Reviewer scores: 6, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1730523483398

thread_type:
official_review

<thread_object>
creator: reviewer_p4tc

<content>
summary:
This paper introduces the TrackTheMind method, which is used to generate a theory of mind story with specific constraints, such as having exactly 3 people in the story.

Generally speaking, TrackTheMind is a tree search process. It starts from a "root node": TrackTheMind uses an LLM to generate a context, including characters, environment, objects, and possible actions. Then, it generates n leaf nodes from this node, where each leaf node can contain n actions that modify the environment state. Among these n leaf nodes, A search is used to select one while discarding the others. The A value function f(s) = g(s) + h(s), where g(s) is the accuracy rate of all questions that the LLM can generate at leaf node s, and h(s) is the probability that subsequent nodes from this leaf node can fulfill the specific constraints.

The authors first used TrackTheMind to generate evaluation data, demonstrating that current LLMs still need improvement in their performance on complex theory of mind datasets. Furthermore, the authors used TrackTheMind to generate training data, and experimental results showed that this training data can effectively improve the model's theory of mind capabilities while maintaining the model's basic utility.

strengths:
1. This paper is well-structured and generally easy to follow, except for Section 2, especially in describing the overall TrackTheMind pipeline and the description of the A* search.
2. The types of ToM questions considered are comprehensive, especially those containing asymmetric belief updates, which can create complex questions.
3. The ToM question generation process is automatic, and given the 'tree' structure, its correctness can be easily verified.

weaknesses:
1. First, how can we quantitatively evaluate the complexity of the generated ToM stories? If complexity is quantified by the number of people and actions involved, why do the experiments in Fig 3 show that model performance increases as the number of people involved increases?
2. In A* search, g(s) requires to evaluate LLM performance of the entire question generated by state s, which maybe time-consuming.
3. The authors demonstrated that models trained on the TrackTheMind training set largely maintain their utility. However, only Multi3Woz and MMLU were evaluated. I expect to evaluate it on more common datasets as it is easy to implement.
4. In Section 2.1, the story context structure is simple and may not be general enough for complex, real-world scenarios.

questions:
Please refer to the weaknesses part.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730592735766

thread_type:
official_review

<thread_object>
creator: reviewer_xwk4

<content>
summary:
The paper introduces TrackTheMind, a framework for generating challenging theory of mind (ToM) testing and training data for LLMs. To generate stories, this work samples plausible contexts, uses A* search to find challenging story structures, and infills these with an LLM. The results show that LLMs seriously struggle on some scenarios, potentially due to poor state tracking skills and the scarcity of training data that specifically requires ToM reasoning, which can be alleviated to some degree by finetuning.

strengths:
1- Do large language models (LLMs) have theory of mind? I think this is a very important research question!
2- Overall, the paper does a good job of presenting arguments and claims.
3- The proposed benchmark seems to be very challenging for LLMs, as indicated by the results.

weaknesses:
1- The paper argues that "basic theory of mind is still elusive to LLMs," and thus this "demonstrates the need for training data that purposefully requires theory of mind." Do the authors think the lack of theory of mind skills can be "resolved" (we know it can be "alleviated") with enough training data? The results on the FANToM benchmark in Table 3 suggest that even finetuning on 114,000 data points of TrackTheMind does not necessarily improve the theory of mind abilities of LLMs. Instead, the reported gain can be explained by the fact that the proposed benchmark is similar to some benchmarks, and by training on TrackTheMind data, models can perform better on similar benchmarks like ToMi without really developing an internal skill that can be generalized across other scenarios.

2- While providing a new benchmark is a contribution, in terms of "new insights," it is not very clear to me how much contribution this work makes. Several other works are suggesting the lack of abilities in the context of theory of mind. But it is not clear to me what "new" insights this work offers researchers that cannot be obtained from other similar works.

While I appreciate the effort for development of this new and challenging benchmark, the work falls short of providing novel insights into theory of mind capabilities in LLMs.

questions:
In addition to the questions above, I have the following question:

1- In the caption of Figure 3, the authors mention that "A story with greater number of people suggests lower difficulty, possibly because there is a fixed number of actions, thus fewer actions per person." However, I'm not sure if I completely followed the reasoning here. When representing the state programmatically, we need to include the status of each person before/after action. So I would argue the number of people has an impact on the state size, and also total number of actions has an impact on number of times we need to update state. Thus, both of them should have an impact on difficulty, but Figure 3 shows otherwise. Could the authors explain this?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730656360838

thread_type:
official_review

<thread_object>
creator: reviewer_bpye

<content>
summary:
This paper introduces a novel methodology for generating program-based Theory of Mind stories using state control, difficulty evaluation, and A* search to ensure a suitably challenging benchmark. The authors conduct two main experiments:

- Benchmark Evaluation: They first evaluate the performance of LLMs on the new benchmark created with TrackTheMind-generated stories. Results indicate that even advanced models struggle with this benchmark, highlighting its potential as a rigorous test for mind reasoning.

- Model Fine-Tuning with Synthesized Data: Using their framework, the authors synthesize training data to fine-tune a model, resulting in significant improvements on both in-domain and out-of-domain benchmarks.

Additionally, the authors offer insights into potential factors contributing to the observed limitations in model performance on mind reasoning tasks.

strengths:
- A novel framework for synthesizing mind reasoning data.
- A sufficiently challenging benchmark to evaluate the mind reasoning capabilities of LLMs.
- A robust training set offering more data, a complex structure, and strong generalization potential.
- Facilitates investigation into why mind reasoning tasks remain challenging for LLMs.

weaknesses:
- The predefined action sets may limit the variety and richness of the story, potentially constraining creativity and depth.
- Other weaknesses align with the questions section, where I have shared thoughts on things needing further explanation.

questions:
- In the title, you mention "adversarial," but there is little explicit explanation of what makes the dataset adversarial. Could you expand on this concept?
- Could you provide additional statistics on your synthetic dataset to offer a clearer understanding of its characteristics? I think detailed dataset statistics are often essential in synthetic data-related research.
- Is there a significant difference in the quality of synthetic stories generated by different models, such as Llama3-8B-Instruct and Llama3-70B? It would be useful to investigate how the varying capabilities of these models impact the quality and characteristics of the synthetic data.
- If time permits, could you try gathering training data from other Mind Reasoning Datasets to train the Llama3-8B-Instruct model and evaluate it on your benchmark? This cross-evaluation could offer valuable insights into model performance across datasets.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730715190087

thread_type:
official_review

<thread_object>
creator: reviewer_rkk5

<content>
summary:
This paper proposes TracktheMind, an adversarial data generation pipeline to collect challenging ToM data via A* search.

With adversarial control on the difficulty of the generated data, the collected evaluation data poses a significant challenge to existing LLMs.

The authors also demonstrate the effectiveness of the TracktheMind-generated data as a training corpus to enhance ToM reasoning.

strengths:
* **A controllable and generalizable data generation pipeline to collect ToM reasoning data**.
With predefined ToM-specific language and a rule-based state tracker, the proposed pipeline can automatically collect ToM data of various difficulty levels with high-precision annotated labels.

* **Intriguing results regarding the effect of interestingness in training and evaluation data**.
The superior model performance on interesting questions against the "uninteresting" ones is unexpected and insightful. This may indicate a mechanism different from that of humans in LLMs to tackle ToM tasks.

* **Details of hyperparameter settings and prompt designs**.
The authors provide plenty of details about the hyperparameters and categories of actions, scenarios, etc. they consider in data construction. This ensures the reproducibility and the convincingness of the experimental results in the paper.

weaknesses:
* **Potential bias in topics, scenarios, and stories generated by LLMs**.
The LLMs are included in several crucial stages of the TracktheMind pipeline. For example, the plausible context creation and sampling is important as an initial stage to determine the topics and possible actions that can be covered in the data. However, this process is done by LLMs themselves, which can introduce inherent bias that hinders the generalizability of the generated data. The authors could provide more statistics and strategies they utilize to balance the story topics and scenarios in data generation to better fit real-world situations.

* **Lack of detailed discussion on the exact cost of data generation via A\* search**.
A\* search can be computationally expensive as the size of the search space increases. The authors mentioned that they reduced the cost by restricting the number of neighbors to consider in $f(x)$ evaluation. The authors could elaborate on how this hyperparameter balances the quality, diversity, and cost of data generation and clarify the exact cost (e.g., #tokens) required in different settings. This could help estimate the proposed method's efficiency and how it would work in practice.

* **Lack of deep analysis to disentangle the specific factors that bottleneck the LLM ability of ToM reasoning**.
The results of ablation on #people and #actions in Figure 3 are a bit confusing. On the one hand, the number of actions seems to matter as fewer actions per person reduce the task difficulty. On the other hand, the increase in the number of actions makes little difference in the model performance in the right plot. Unless the variance in performance causes this, given the limited ranges of #people and #actions or number of test samples considered, there might be some factors (or even spurious features) that dominate the model performance. For example, the number of people and actions may not be directly related to the reasoning steps required to answer some ToM questions, whether it is interesting or not. The authors could provide some meso-analysis on the factors that can reflect the task difficulty more directly.

questions:
* As the accuracy of LLMs on some TracktheMind data is quite low (e.g., $5$%), have you tried finer-grained metrics to assess the model's ability? For example, instead of directly enforcing the model to answer yes/no, it would help to diagnose its understanding of the context by extracting its confidence regarding the question and probing the level of uncertainty in the corresponding scenario.

* How the *important actions* are defined to determine a desired user condition? Is this a crucial design to control the generated data's difficulty, quality, and diversity? Would it generalize across different scenarios?

* What is the background of the annotators? Does this matter for the performance in task completion?

* Could you elaborate on the difference among the chosen ToM benchmarks in Table 3? Why the last two did not benefit from the TracktheMind training?

* Why does the model performance on ToMi drop significantly (compared to llama3.1-8b-instruct baseline) when training with 0% of interesting questions? It should be at least the same level as the baseline performance unless I missed something.

* It appears that interestingness and asymmetry are not the crucial factors that impact task difficulty or model performance in evaluation. What might be the cause of such misalignment/inconsistency?

* OpenAI o1 with inference-time scaling may boost the performance by exploring more possibilities for better state tracking. It would provide some insights by assessing it using the TracktheMind-generated ToM data to check whether it can improve performance as expected. This could help to better understand the bottleneck in existing LLMs to tackle such ToM reasoning tasks.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732157744630

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We thank the reviewers for their feedback! We are pleased to hear that reviewers found that our work tackles a “very important research question” [Reviewer XWk4]. Reviewers mention that our synthetic data generation framework creates a “robust training set” [Reviewer BPYe] with “strong generalization potential” [Reviewer BPYe; Reviewer rkK5] and thanks to its structure, data “correctness can be easily verified” [Reviewer p4tC]. TrackTheMind’s data can be also used as a “challenging benchmark to evaluate the mind reasoning capabilities of LLMs” [Reviewer BPYe; Reviewer XWk4] and it also “facilitates investigation into why mind reasoning tasks remain challenging” [BPYe] with some “unexpected and insightful” results [Reviewer rkK5] that may “indicate a mechanism different from that of humans in LLMs to tackle ToM tasks” [Reviewer rkK5].

**We address some common questions below, including several new analyses based on reviewers’ suggestions**: a detailed cost analysis of A* in terms of # tokens, o1-preview evaluation, and more detailed dataset statistics.

---
### _Additional statistics on TrackTheMind’s resulting dataset._
Stories shown in Table 1 were obtained by using one of 100 generated contexts, which were generated by first independently sampling a list of names and initial locations and then jointly sampling the full context. Table 1 stories contain 77 people in total, 28 objects, 47 containers, 52 rooms, 143 discussion topics. Object state updates ($a_{\text{updateObjState}}$) include 38 distinct visible and 26 invisible updates. 

Story structures are diverse: if we consider the first 5 actions in each story (e.g. $[a_{\text{enterRoom}}, a_{\text{moveObjContainer}}, a_{\text{leaveRoom}}, a_{\text{enterRoom}}, a_{\text{moveObjRoom}}]$, without considering any variables), then a sequence of actions is repeated only 2.30 times on average (std=2.92; median is exactly 1). Story structures have 8.02 actions on average (std=2.37). Given that we request to infill each action with up to 2 sentences, resulting infilled stories are not long (avg token length=380, std=144), and there are 10K+ distinct tokens used.

---
### _o1-preview analysis, since inference-time scaling may boost performance_ 
Inference-time scaling will definitely help for ToM reasoning, as introduced in SymbolicToM (Sclar et al., 2023). As discussed in the intro, these high-cost inference-time solutions may not always be feasible, and o1 is an extreme example. Concretely, we evaluated o1-preview with 25x the completion tokens that we permitted to regular models on a sample of 500 TrackTheMind (story structure, question) pairs generated using GPT-4o. This is just 5% of the data analyzed in Table 2, and yet o1-preview evaluation costs ~$120. **We found that this extensive budget was not enough compute for o1-preview to produce _any final answer_ in 46% of the questions**. o1-preview was correct also for 46% of the questions; and plain incorrect for the remaining 8%.

---
### _On the cost of A* search_
Running A* with a budget of $N$ nodes (i.e., partial stories) costs exactly N times the cost of evaluating that node (story) if it were to be included as part of a final dataset. N can be modified as desired if efficiency is a concern. We selected $N=50$ since we believe that for the evaluation benchmark application it is vital to find the most challenging data points for evaluation and this outweighs efficiency concerns.

Since each node is a potentially shorter version of the final data point, and evaluating a final story over all first-order questions takes on average 681 input tokens (std=431) and 21 completion tokens (std=16), we can confidently say that A* with N = 50 nodes will take on average less than 681 * 50 = 34050 input tokens, and 21 * 50 = 1050 completion tokens. This relaxed upper bound totals $0.0478 per story generated adversarially for the frontier model GPT-4o.

---

[response continues in the following message]
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces a framework for generating synthetic theory of mind datasets using programmatic A* search over story structures. The framework produces diverse, challenging, and high-quality theory of mind evaluation and training data. The results highlight significant limitations of existing large language models (LLMs) in theory of mind reasoning and demonstrate that fine-tuning on TrackTheMind data improves performance on several benchmarks.

Reviewers generally agreed on the soundness of the experiments, particularly the analyses on the impact of interesting/uninteresting questions and the conceptual insights into LLM performance. The authors' response effectively clarified concerns, particularly around computational cost, dataset diversity, and complexity metrics, and provided additional experimental results. 

Some reviewers raised concerns around new insights into ToM reasoning beyond confirming LLM limitations, bias of LLMs for generated context, and computational efficiency of the search. The authors provided clarifications and additional analyses (e.g., cost analysis, o1-preview evaluation), which addressed most concerns. All reviewers ultimately leaned towards acceptance.