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
Venue: ICLR 2025 Poster (2025)
Keywords: theory of mind reasoning
adversarial data generation
program-guided data generation
Primary area: applications to computer vision, audio, language, and other modalities
TL;DR: We develop an A*-powered algorithm for adversarially generating challenging and diverse theory of mind data, that can be effectively used as to stress-test LLMs capabilities or as fine-tuning data

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.

Published as a conference paper at ICLR 2025
Explore Theory of Mind: PROGRAM-GUIDER ADVERSARIAL DATA GENERATION FOR THEORY OF MIND REASONING
Melanie S Jane Yu' Maryam Pazel-Zarande
Yulia Tsvetkov 2
Yonatan Bisk3.*
Yejin Choi*
Asli Celikyilmaz!
FAIR at Meta Uniierriity of Washington *Carneiee Mellon University *Stanford University
msclarêcs. washington.ed.
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 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 evalu- ation and an overestimation of model capabilities, We introduce EXPLORE TOM,, 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 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-att LLMs, such as Llama-3.11700 and GPT-4o, show accuracies low 0% and 9% on EXPLORE PPPLLORETMM-gennerrtte data, highlighting the need for more robust theory mind evaluation. As our gen- erations are conceptual superset of prior work, fine-tuning 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 imbal- ances, which may contribute to models' poor performance on benchmarks
data yields
INTRODUCTION
Reasoning about other people's intentions, goals, thoughts, and beliefs is foundation of social in- telligence. Known as Theory of Mind (ToM) (Premack & Woodruff 1978). this capability is crucial for effective human interaction. There has been plethora of recent research that develops theory of mind benchmarks and test LLM capabilities, usually inspired in standard tests for research in chil- dren such as the Sally-Anne test (Wimmer & Perner 1983). However, these tests are not well-suited for extensively evaluating models, as they focus on specific scenarios and lack the variability and complexity required to remain challenging after online pre-training. As a result, many existing com- putational benchmarks may not be effective in robustly evaluating models' theory of mind abilities.
We introduce EXPLORETON OM., an A Aoooeeedd algorithm for generating reliable, diverse, and chal- lenging theory mind data that can be effectively employed for testing or fine-tuning LLMs. Our approach leverages
Nommin--speciff language to generate synthetic story structures and their char- acter's mental states. We then use LLMs to create plausible stories based on these plots, allowing for precise control over the narrative and tracking each character's 's mental state with high confidence. We employ A search (Hart et al. 1968) to efficiently navigate the vast space of possible narratives and pinpoint those that are most likely to fool state-of-the-an LLMs. This turn allows create a robust, rich dataset that effectively tests the limits of current models (Fig. [ By generating story structures separately from lexical realizations, we can distinguish the model s core understanding of the social reasoning from vocabulary cues that might give away stylistic hints.
Our contributions are three-fold: we algorithmically address blind spots in theory of mind eval- uation, we provide recipe to create complex training data that helps imbue models with better theory of mind reasoning skills, and we provide insights into why theory of mind skills are still clusive for LLMs.
Work done at Meta. Results presented here reflect latest results collected up to Dec. 12 2024. www.spoorrtttteo oret.om
Code and data can be found at http:/gtttuuu..e http:////gg.tttoeec/eeeeeeeeeeee

---

Published as a conference paper at ICLR 2025
<story start>
Anne entered the kitchen. Beth entered the kitchen.
update #1
wortiSenn locaton) -> Mathn bote Relt, locator 1- kichen
Beth polsoned the apple. Beth the apple chocolate.
Beth salted the apple. Beth left the kitchen.
update #2
beloryyene, anpks salod > beteryyene, Boft xpple salted oo
Beth texted to Charles to let him know the apple is salted. Charles entered the kitchen.
Charles entered the kitchen. Charles told Anne that today will rain.
update
Where the app e right now!? fridge
fdge v lable no yes x
updist
Charles moved the apple to the trigge.
tracker- generated
Wher dlsss Figth think the apple is? table
questions
Docs know the apple is salled? yes
Does Anre thinc Charles knows that the apple sahod?
acc 0.5
<selected ends
Figure 1: EXPLORETOM finds challenging stories for a given language model by searching through the space of stories supported by its domain-specific language for mental state tracking (o)), sam- pling& k supported actions at a time (shown as a node, A = 2 in the example). Difficulty evaluation (simplified in the figure as easy, medium, hard) of each partial story is done through automatically generated questions with reliable ground-truth answers thanks to our tracking procedure.
First, our work helps to address the conflicting results from large number of prior research on evalu- ating theory of mind (e.g. (Sag.SSap et al., [0222] Shapira et | 2023a Kim et al.) [023) Zhou al.) [2023] Gandhi et al. 2024, [Strachan et al. (024), including reports that due to oversimplified datasets, prior theory of mind estimates may be overly optimistic (Ullman 2023). Our algorithmic approach also helps address the issue of developing benchmarks that may be close to saturation the time of release, given the increasingly harder task of anticipating LLM failures (e.g.. Kim et al. 2024). EXPLORETOM' 's adversarial nature allows for generating stories to stress test any LLM, dimmnsshing the risk of data leakage onto training data, and thus being more robust than manually-crafted bench- marks. Our experiments show that EXPLORE --g-rreeede data is extremely challenging, with GPT-40 and Llama-3.1 70B accuracies as low as 9% and 0% respectively. EXPLORETON supports significantly more scenarios than previously possible, with the unique addition of knowl- edge gain asymmetry during an interaction, among other improvements.
Second, our method allows creating complex and diverse theory of mind data that can be lever- aged for model fine-tuning, Given theory of mind's implicit nature, it is challenging to find data that explicitly articulates the required reasoning, and existing benchmarks are not suitable to use as training data: they are often limited in scale (Xu et al., 2024), portray specific scripted scenar- ios (Wu et al.] 2023] Le et al.] 2019), and are prone to leakage risks that would make them fully unsuitable for future use. Fine-tuning with this data has been shown to overfit to specific story struc- tures instead of learning the underlying reasoning required (Sclar et al., 2023). leading to works focused on creating inference- time algorithms to improve the model's 's capabilities through prompt- ing or more sophisticated strategies (Sclar et al. 2023; Zhou et al. 2023 Wilf et al.] 2023) Jung let al. 2024 While inference-time methods have proven useful for improving performance in the- ory of mind benchmarks, the benefits of these methods cannot be readily transferred to downstream applications that may also require customized inference-time algorithms for their specific use cases. Fine-tuning Llama-3.1 1 8B Instruct on EXPLORETOM's data achieves a substantial +27 accuracy point improvement on the classic ToMi benchmark (Le et al., 2019), showing good generaliza- tion to even more complex EXPLORETON stories than those seen during training, while still retaining general reasoning capabilities.
Finally, EXPLORETOM enables providing new insights into why basic theory of mind reasoning is still challenging for L.LMs. We show that LLMS struggle with basic state tracking, fundamental skill underlying theory of mind reasoning: tracking mental states necessarily requires being able to track states. Our experiments also reveal that in order to improve on theory of mind during fine-tuning, it is crucial to use data that requires theory of mind as opposed to simply requiring state tracking. However, found data (either in-the-wild, or randomly generated) is unlikely to have this necessary property. which may be key contributor to lagging model performance. Overall, EXPLORETOM offers a valuable tool for advancing the theory of mind research, enabling the devel- opment of more effective L.MMs that can better handle complex social interactions.
2

---

Published as a conference paper at ICLR 2025
A. Sample story context
C. Search for difficult story structures with mental-state tracker
Infill story incrementally
People: Armo, nead chot: Rish e peanry
buszling High end restourant, spomt frssiyy
Charle,
1od0 #1 000300
Location: Paclaura kithenn
sammering tauces the minging clinking sharp station toliowed by Bert, who made beeling the counter lone spple wattedt traneformed into the avoning's cossent mastorplcco Betn's silled hands moved with presision sprinkling g pirch af salt onto the apple's londor flcsh drow out natural sweetnen ose. With the apple pericatly seasonec blth tumed on her heel and di ppedd thmough the eoinngngg riningg doons, dicappeorin into the dining area to contor with the ovoning's matre di about the final dosse' 1 prescrtation Both quackly pulled her phono from her pooket and shot off a lest Charles "Apple's sahed"
Object: spple.
Alternative location: Welk in permy.
A1
Ante and Belh ertared the sitchen
Plausible containers: wooden fidges
sconning
partod,
Discussion topics: food sciry pistocols: monu changes.
full
Bell sadted the spple and kithenn
Batt fextted to Chades Charlee ertered the kttchen
Node 98
Visible changes: covering aople
cnoclllle paeling l apple,
Invisible state changes: soiling the apple.
polso Ih's applet....
n1 [hhdde iissrdd the Applle to the Hidges
B. Sample state updates
Figure 2: Overview of EXPLORETOM's story generation procedure. We first sample a plausible story context using LLM (shown in A and B). Topics discussed, location changes of objects and people, and object state updates, may all be required to track in order to pass our theory of mind tests. We then search for difficult story structures (i.e., the story points) by sampling and analyzing different orders in which these actions may be performed using A search (shown in C, and Fig. []- This ensures that the resulting stories will all be challenging tests for models, and may be used for further improvement. Finally, these story structures (nodes #1-4) are iteratively infilled, one story action at a time, using language model, yielding a -oundinng story. Infilled stories are used as training data; benchmarking is done with story structures since they have the highest reliability.
ADVERSARIALLY CONSTRUCTED STORIES WITH EXPLORETOM
Building on the standard approach in theory of mind of assessing mental state understanding through question answering (Wimmer& & Perner 1983; Kinderman et al.) 1998 Baron-Coher et al.) 1999), ExpLoReTOM creates stories where different characters may have different beliefs about the cur- rent world state and about other people's 's beliefs, paired with questions to probe model understand- ing (see Fig. Ts highlighted story, along with associated questions probing understanding that e.g. "Anne does not know that Charles knows that the apple has been salted")).
EXPLORETOM's 's story generation process is divided into three main steps: plausible story context sampling (Section 2. adversarial story structure generation (Section 2.2 and optionally story in- filling (Section 2.3) an example is outlined in Figure 2 We automatically generate questions to probe understanding of said stories as part of the adversarial story structure generation process (Sec- tion 2.2.2): : this process finds challenging story structures, i.e., story structures that would yield low accuracy with generated questions. Because questions generated automatically and directly from the tracked mental and world states, ground truth answers have high degree of reliability: we do not use language models at all in the question-answer generation procedure.
2.1 PLAUSIBLE STORY CONTEXT SAMPLING
We use an LLM zero-shot to generate consistent and plausible story context, comprising essential elements such as character names, roles, locations, relevant objects, object containers, and discus- sion topics (see Fig. 2 for full example). This single-step process ensures a coherent and be- lievable setup for our theory of mind stories. Previous approaches (such as ToMi (Le et al.) 2019)) sample objects (e.g., an apple) and object containers independently (e.g. bottle), often resulting in commonsense violations. Unlike these approaches, our method generates a coherent context by sampling these elements jointly in a single LLM call: autorregresive LLMs will naturally suggest contextually plausible elements based on the ones they already generated, and especially so when explicitly requesting it in the prompt. Additionally, we sample possible object state updates (Fig- ure B), which are then refined through using LLM as a judge to filter out implausible and low quality generations. The role of these state updates will be discussed in further detail in Section 2.2. The exact prompts used for sampling story contexts are shown in App. C
3

---

Published as a conference paper at ICLR 2025
2.2
ADVERSARIALLY GENERATING CHALLENGING YET PLAUSIBLE STORY SCRIPTS
2.2.1 THEORY OF MIND-SPECIFIC LANGUAGE DEFINITION
EXPLORETOM's theory of mind-specific language consists of diverse set of actions A, each trans- forming the world state and the belief's of the people involved (the story state E S). A story is thus defined as a sequence of actions (d1,.... (,), where each action a; E A a function a; :S - S. Each action also has preconditions to be able apply it, ie.. restrictions its domain. For example, a precondition for "Charles entering the kitchen" is to not be in already. Applying an action also automatically updates our world state tracking and belief tracking: for example, "Charles is now in the kitchen"; "Anne knows that Charles is in the kitchen since they were also in the kitchen"; "Charles knows that Anne is in the kitchen since he can see her"; and so forth. All these updates and conditions are specifically programmed and tested; see App. [.. for the full programs.
EXPLORETOM enables the generation of diverse stories by significantly expanding the range of supported actions. These actions include physical changes to the world state such as entering and leaving a room (denoted Genter Qleae),, moving an object to a container (or in general, updating its state; denoted OmnvvOOhjContaiierr OupdateOijState respectively), relocating an object to different room (AmoveChjRoom). Additionally, EXPL.ORETON supports various forms of communication, including: private conversations between two characters, or public broadcasts to all characters in a room; ca- sual discussions about a topic (denoted chit-chat), or notifications about changes in the world state (denoted info): these actions are referred to Cinfo-private. Oinfo-public- OchiiChat-private- and dchitChat-publie- These actions can occur at any point in the story, allowing for a rich and dynamic narrative (see formal definition in App. A.I) and expanding prior work (Wu et al. 2023).
Each new action requires carefully writing the implied belief and world state updates, which pre- cludes scaling the number of actions supported. However, we alleviate this by noting that from theory of mind perspective, many actions are equivalent. For example, "peeling an apple" or "cov- ering apple in chocolate" have the same implications with respect belief updates (a visible property of the apple is being updated, and the witnesses would be the same). Similarly, poisoning an apple has the same implications as moving an apple from drawer to a fridge (an invisible prop- erty is updated, witnesses would be the same, and non-witnesses would not assume there has been an update). The instantiations of these equivalent state updates from a belief perspective are done with an LLM during the story context sampling (see Figure B).
Asymmetric belief updates In prior work, all belief updates were symmetric: if A and B witnessed an action, then A knows that B witnessed the action and vice versa. Our framework introduces the ability to model asymmetric scenarios. Specifically, we enable the addition of secret witnesses to an action such as someone observing through a security camera, or removal of witnesses without others' knowledge, as in the case of someone becoming distracted by their phone. This added nuance allows for more realistic and complex social scenarios. Asymmetries Opeok and ddistracted are modifier functions, c.g., as a modifier to "Beth salted the apple" (dugdanobi/State (-)) there may be a secret person peeking (Apeek (OupdaneObiStttte (-))): "While this was happening, Diane witnessed it in secret."
2.2.2 GENERATING QUESTIONS AND ASSESSING RESULTING STORY DIFFICULTY
We assess a model's understanding of generated story s=(a)...., a.) by probing it with automat- ically generated question-answer pairs. EXPLOREToM--eeerate answers are more reliable than purely-LLM generated ones, since they are directly produced from the states' trajectory with our tracker. Questions may be testing first-order beliefs, second-order beliefs, or regular state track- ing: First-order refers to asking about someone's mental state (e.g.. "Does Anne know the apple is salted?"); Second-order refers to one extra level of recursion in mental state tracking (e.g.. "Does Anne think that Charles know the apple is salted?"); State tracking may probe about the current state (ground truth) or prior ones (memory).
We expand the complexity of memory questions with respect to prior work by asking about any intermediate state (e.g. "Where was the object before happened?") instead of solely about the ini- tial one ("hhere was the object at the beginning?"". Our generated questions simple to evaluate: they are either binary (yes/no), or are answered by stating an object, container, or room. Specific question formulations differ based on the property, e.g., location ("Where does Charles think that
4

---

Published as a conference paper at ICLR 2025
Anne will search for the apple?") knowledge ("Does Charles know that the apple is salted?"). See App. A.2 for the full list of supported questions.
A question is considered interesting if the answer would change depending the person being asked about. For example "Does Anne think that Charles knows that the apple is salted?" is interesting because the answer would differ if asked about someone else, such as "Does Beth think that Charles knows the apple is salted?". EXPLORETOM'S tracker very easily allows for automatically detecting interestingness.
2.2.3 A SEARCH
Given a context C and a set of actions A. our main goal is to find challenging story structures. To increase EXPLORETOM's usage flexibility, we support the option of searching for stories that fulfill desired user conditions (sDesired (s) E {0, such as the number of people involved, or the number of actions belonging to a subset A' C of important actions.
We search over the space of plausible story structures of up to m actions. We define this space as directed graph, where each node is a sequence of valid actions s = (a ,a:), and there an edge between and s' if and only if is prefix of s', and s' contains k more actions than k > 1 is the grouping factor for actions, defining the granularity with which we will sample and evaluate nodes. For simplicity, Figure depicts only the new ls = 2 actions that each node introduces.
To find challenging stories that simultaneously fulfiil the user constraints we use A search (Hart et al. 1968). By definition, A selects the path that minimizes f(s) g(s) h(s), where g(s) is the cost of the path from the start to node 8, and h(s) is a heuristic that estimates the cost of the cheapest path from to goal node (one of the nodes where it would be acceptable to finish the search). In our context, goal nodes are those such that isDesired search algorithm precisely because it enables to search this space prioritizing desired user conditions through hs), as we will detail below.
1. We choose A as our
A story is said be challenging for a model it incorrectly answers our generated questions, i.c., it shows low accuracy. Thus, we define g(s) as our target model's accuracy among all questions for s. We define the heuristic function h(s) as a proxy estimation of the likelihood of generating full story + s' that fulfills user constraints isDesired (s) = 1, where s' is the continuation of story s:
h(s) -1- Σ
1 Σ 1 (isDesired is x/) +x)==1 1))
Here, all s are randomly sampled continuations of s and 0 < < 1 is scaling factor. A* requires to evaluate all neighbors of a node s. Since this would be infeasible given the vast space to explore, and that each f()) evaluation requires several LLM calls (one per question), we restrict the evaluation to a pre-defined constant number of neighbors, prioritized by the closeness this node to fulfilling the conditions described by isDesired()). This pre-defined constant may depend on f() to prioritize more promising partial stories (i.e., with lower (s) values).
2.3 STORY INFILLING
Story infilling is the process of transforming a full story structure (a1, a2..... an) with story context into natural-sounding narration (see Fig-2p), We infill stories iteratively with an LLM by transforming each action into more natural sounding one, according to some stylistic desiderata d, and conditioned on the previously infilled context (denoted infill =, d)). Supported stylistic desiderata d are length requests (e.g.. "use up two sentences") style requests (e.g., "make this into a conversation"); we optionally also include sampled character goals y and an initial narration context based on the story s, also generated with an LLM (e.g., Anne's 's goal may be to oversee that all dishes are rapidly delivered to customers; see initial context example in Fig. Concretely, the full story infilling ST is as follows:
ST = infill(a,, ST(i - 1), d). g) where ST(O) =
Infilling is done iteratively to ensure that the order of the actions stays the same, since this is impor- tant for keeping the mental state tracking valid. To further increase reliability, we use LLM as judge after each infilling step to confirm that each mental state tracked after executing the story step a, still holds even after infilling. This discards infillings that introduced ambiguity hallucinations.
5

---

Published as a conference paper at ICLR 2025
Table I: Accuracy results of EXPL.RRETOM's story structures 18 action sets A, each aggregating 90 total stories from different settings (number of people, actions, and rooms). Each set is either based on actions supported by well-known theory of mind tests or includes our novel expansions, and is analyzed excluding or including asymmetry (X, v) Each setting requires at least one action in the story to be from one of the squared actions encourage non-overlapping story structure characteristics between action sets shown. Data was generated using each model as its own evaluator (i.e., as 9())), and results shown include all first-order questions- the most basic theory of mind level, not requiring recursion, Lowest accuracy for each model is bolded.
EXPLORETOM action set
Llama-3.1 70B Inst.
Mixtral 8x7B Inst.
GPT-4o
Centerr Gleave
include asymmetry modifiers? (Apeskk Adistmetedd)
X
/
X
X
AmoveObjContainer
.18
.00
.40
.25
.37
.33
Oujdat:ObjStatec
.27
.24
.25
.24
.03
.01
CmooeeObyConttine
SupditeObjStatee
.26
.03
.35
.31
.24
.09
OmoveObjRooom
.11
.10
.09
.16
.00
.00
OmmveeOhiCommainerr
Oinlo
.06
.07
.29
.25
.35
.36
UmoxeOhhjContainer OmoveohjRoom:
Oinfo
.11
.07
.24
.24
.03
.04
ComovoOijoontineess AmoveObjRoom- GchirChat-",
Cinfo-
.72
.69
.73
.68
.53
.47
OchisChat-prival
.75
.66
.77
.59
.51
.45
OhhitChat-pablic
.60
.55
.49
.47
.37
.34
0.5
0.5
Accuracy
Accuracy
0.3
0.3
Uama 708 inst
0.2
got 40
0.2
g0t40
Mutrral-BccB-ree
Mixtral-Bx<7B-Ime
0.1
2
4
Actions (from .0
People
Figure 3: Accuracy EXPLORETOM's story structures when increasing the number of ac- tions or people involved, Accuracy is computed across all story structure settings. Difficulty of Www.LORETTM-geeeeee
stories tends to increase stay similar when increasing the number of actions. story with greater number of people suggests similar or lower difficulty, possibly because when fixing the number of actions there fewer actions per person (see details in App. B.5
EXPLORETOM AS AN EVALUATION BENCHMARK
We begin by showcasing how EXPLORETOM story structures can be used as a challenging bench- mark, highlighting its unique features and advantages.
Experimental setup We use EXPLORETOM generate story structures for each of tion sets (each with and without asymmetry) and each set of user conditions. Each story genera- tion allowed evaluate 50 nodes. User snaitiionn-iDDesred(((ffef -erruurrd exactly p (2, 4) people involved, with E (,,3.4) 4} actions belonging to the set of important actions A', span- ning across either r or r rooms, and with m S 15 actions total-leading to a to- tal of 162 settings. In all experiments, A'' are the actions that add new basic world knowledge: A' = {amovsObiCommanns @updateObjjtatee OmsveobiRoom 4c We then infill every story. We use lama-3.1-70B Instruett (Dubey et al. 2024). GPT-4o (OpenAl (2024); queried early Dec. 2024), and Mixtral-88 B--7BBIIntuuu (Jiang et al. (024) to generate story structures. A is run with a = 0.1, P = 50, and (i.e. grouping three actions per node). See generation examples in App.D
EXPLORETOM finds challenging story structures for frontier models
As shown in Table EXPLORFTOM consistently identifies story structures that highly challenging for models

---

Published as a conference paper at ICLR 2025
Table 2: Accuracy results EXPL.ORFTOM- data built minimize accuracy for each particular model. A random sample of 1000 (story structure, question) pairs is shown. Data remains challenging even if it was built with different model, and even including questions we did not optimize for: story structures were selected adversarially towards first-order belief questions only (g()), accuracies shown include all belief questions.
Model used for evaluation
Model used in EXPLORETOM
Llama-3.1 70B Inst.
Mixtral
GPT-4o
generation (g(-)
7x8B Inst.
Ilama-3.1 1 70B Inst.
0.57
0.68
0.32
GPT-4o
0.60
0.61
0.32
Mixtral 7x8B Inst.
0.68
0.74
0.30
across various action sets, with average performances in EXPLOREToM-generrae datasets low as 0.09 for GPT-4o (i.e., 9%). When increasing the number of actions, difficulty tends to increase or remain similarly challenging. Performance tends to stay the same or decrease when increasing the number of people involved, possibly because with a fixed number of chanechhngging actions there will be fewer actions per person which may be easier to track. See Figure 3 and App
A is better strategy than over-generation and filtering Over-generation and filtering has become a standard procedure for synthetic data generation (e.g. West et al. [022] Wang al. 2023). We measure the effectiveness of A by comparing the A A data to the data resulting from over-generating stories with our domain-specifet language-using the same isDesired criteria and budget as used in the A search- and retaining only the most difficult stories. In a set of 81 maddoll--selected settings (50% of the original 162 settings, due to the experiment's 's high cost), we generate 50 stories with each method using Llama-3.117000 1..1--0B-Instruce and a budget of 2500 accuracy evaluations each. A yielded a more challenging dataset (by accuracy points), with shorter stories on average (1.6 fewer actions). This length difference is possibly due the pressures A * induces towards shorter stories through the heuristic h(s). See Figure for the full distribution of results.
Story structures found adversarially for a model remain challenging for other models We evaluate the difficulty of a SAMPLLRRTTMM-geeeattee dataset with each model, and find that although there is an increased difficulty towards data generated adversarially with the same model, remains challenging for all others. Notably, the generated datasets remain challenging even when adding question types not included in the (-) optimization (second-order belief questions). See Table 2
Humans agree with EXPL.ORFToM--geeeeee evaluation to verify the quality of the story structures' automatically-geneaaale labels and the story infillings. For labels, we annotated 100 questions across 12 cundomly-sampled story structures from all settings generated for Table and found 99% agreement with our expected answers-likel) due to the clear and concise nature of our stories and that the ground truth labels were generated by our Nomain-specinf language. We measure story infilling quality by repeating the aneesion-answerne procedure with different set of 100 questions across 12 randomly-sampler infilled story structures. In this case, the human agreed with the ground truth label 89% of the time-a small degradation likely due the powered method introducing ambiguity.
story structures labels
We conducted human
Infilled stories remain challenging Infilled stories with Llama-3.1 70B yielded an average ac- curacy of 0.61. Although the average accuracy increased by 0.12 through the infilling process, the samples remained challenging thanks to the highly challenging underlying storie One key factor for this accuracy difference comes from models sometimes making the mental states more explicit through the infilling process: results shown correspond to a single attempt at infilling each story (41% % of the samples ended successfully in a single attempt, judged by an LLM). Although stories remain challenging, since infilling with an LLM may introduce some ambiguities or hallucinations we only use them as training data. See App. B.2 for detailed results for all action sets.
Infilling can be also added to the * search; we deemed it unnecessary given that this simpler method still yiclds highly challenging henchmark and it is less costly.
7

---

Published as a conference paper at ICLR 2025
Table 3: Performance major false-belief benchmarks; accuracy (in %) unless otherwise
stated. Parenthesis reflect differences between out-of-the-box model and fine-tuned version using EXPLOREToM-generate data. Bold reflects higher overall performance.
ToMi
Hi-ToM
BigToM
OpenToM (F1)
FANTOM
Llama-3.1 1 8B Instruct
68% 95% (+27)
30%
75%
.39
0.3%
EXPLORETOMM-88
59% (+29)
81 % (+6)
.46 (+.07)
0.2% (-0.01)
1.000
1.00
ToM Accuracy
Accuracy
0.975
0.75
0.950
3,4)
0.50
0.925
0.25
Explore To training variants
0.900
5
7
8
10
20
40
60
80 100
Actions (from A4)
Training potentially requiring ToM
Figure 4: EXPLORETOM-SB accuracy when evaluating on EXPLoREToM-genneee with more people p and/or more actions than seen during training (p < 5, < 5). Perfor- mance remains high when adding several ac- tions and/or up to two people.
Figure 5: ToMi accuracy when training with EXPLORETOM-ganne -eM-eeeeetted data with different proportions of interesting questions (i.e.. ques- tions potentially requiring theory of mind to answer). Here, variants are fine-tuned with 85000 story structure samples for I epoch.
data
4 EXPLORETOM IS EFFECTIVE AS TRAINING DATA GENERATOR
Experimental setup We fine-tune Llama-3.1 8B Instruct using dataset of 79700 (story, question, answer) triples, focusing solely on the completion tasks, and dub the resulting model EXPLORETOM-BB The dataset comprises both raw story structures and infilled stories, incorpo- rating story structures from each of the 9 action sets listed in Table [ (excluding asymmetry, and with balanced number of questions per story type), and various user constraints -te same in Section 3 We do full fine-tuning with the following hyperparameters: a learning rate of 10-6, 100 warm-up steps, effective batch size of 40 samples, where fine-tune solely completions.
Fine-tuning with EXPLORETOM generalizes well to S.PPLORRToMMMeeeerrate data with more people and more actions than used in training with Www.LORETTM-ggeerree
Since EXPLORETOM--S is trained data involving p (2, 3,44 4) people with m {2, 3, 4} actions from the set of important actions A', we evaluate generalization within the EXPLORETOM domain by evaluating on MoPLLRRTTMM-eenerare data involving 5 people, and to 11 actions. This data is generated with 1lama-3.1, the same model original training data. See Figure 4
Fine-tuning with EXPLORETOM improves or maintains performance on theory of mind benchmarks without hurting general reasoning capabilities We evaluate our fine-tuned CXPLORETOM-S -88 model on five prominent theory of mind benchmarks: ToMi (Le et al.) 2019). Hi-ToM (w et al. 2023), BigToM (Gandhi et al. 2024), OpenToM (Xu et al. 2024). and FAN- ToM (Kim et al. 2023). Results show significant improvements in performance on ToMi and HiToM, with accuracy gains of +27 points on both benchmarks (see Table 3). The model main- tains shows small gains the remaining three similar benchmarks, indicating that fine-tuning ExPLoRETOM data enhances or preserves performance across a range of theory of mind tasks
We also evaluate oft-oo-domain reasoning skills using the two datasets: Multi3Woz (Hu et al. 2023 a commonly-use used dataset for dialogue state tracking, and MMLU (Hendrycks et al. 2021) which tests both world knowledge and problem-solving abilities. Dialogue state tracking capabilities preserved: both the base model and EXPI.ORETOM-83 achieve 96%. Broader reasoning capabilities also generally preserved, with small 2% performance difference (base model achieves 69%; EXPLORETOMES 67%). Given the out-of-domain nature, we expect that intermixing data with samples more similar to MMLU's domains will substantially alleviate this slight regression.
'The lack of performance difference in FANToM is likely due its length confounding factor: data points have 1000+ tokens, yet our model is fine-tuned with maximum length of 300 tokens.
8

---

Published as a conference paper at ICLR 2025
Data mixture affects downstream performance We fine-tune five models, with 0%, 25%, 50%, 75%, or 100% of the stories requiring theory of mind to answer at least one question about the story. Figure [ shows that training with as much stories that require theory of mind is crucial for achieving high downstream performance (using ToMi as a proxy dataset), even if some of the individual questions used for training do not require theory of mind.
5 ON UNDERLYING SKILLS NEEDED FOR THEORY OF MIND
EXPLORETOM enables uncovering and quantifying underlying causes for models' poor theory of mind reasoning models out-of-the-box. We specifically focus on the lack of robust state tracking skills, and the need for targeted training data in order to improve theory of mind capabilities.
EXPLORETOM's objective is to find story structures where models fail to answer questions; some of these questions simply require state tracking, specif- ically the ones where every person would give the same answer (i.e., their mental state is the same in this regard: e.g.. in Fig. all X E {Anne, Beth, Charles} would answer the same to "Where does X think Anne right now?"). By definition (see $ 2.2.22 these are the uninteresting questions. EXPLORE TAAEEToo---ee -ggeeerrte questions are approximately evenly split between interesting and uninter- esting, and uninteresting ones are even more challenging on average: the accuracy of interesting and uninteresting questions is 49% and 31% respectively for Llama-3.1 70B, 58% and 37% for GPT-4o, and 45% and 26% for Mixtral. See Table 6 in App. B.3 for full breakdown for all settings.
LLMs lack robust state tracking skills
State tracking questions are subset of theory of mind questions, and arguably easier case since the required logic for answering questions is simpler. Therefore, improving models' performance on state tracking may be crucial prerequisite for achieving theory of mind reasoning in LLMs. As have demonstrated, EXPLORETON can be easily adapted to stress test pure state tracking, simply by retaining only the uninteresting questions.
Training data biases against theory of mind and its implications Figure shows that to successfully improve performance the ToMi benchmark, EXPLORETOM fine-tuning data needs to be biased towards interesting questions. However, a significant portion of models' training data likely biased against requiring the tracking of divergent mental states (e.g., news articles).
As conceptual proof that this phenomena occurs even within our custom domain-specific language unless we explicitly bias towards theory of mind, we demonstrate that randomly-sampled story structures tend not to require theory of mind. Using EXPLORETOM's domain-specinf language, we randomly generate 1000 story structures with ToMi primitives (feenter Gleave OmoveObiCComtaine } for stories involving {2, 3, 4} people and {2, 3, 4} object movements. We consider story to not require theory mind if all first-order and second-order theory of mind questions are un-interesting, as defined in $ 2.2.2 (i.e., all share the same mental state). This stringent criterion evaluates all questions simultancously. Nevertheless, our results show that 78% or more of the sandommy-samppl stories meet this condition across all settings, with up to 87% of stories fulfilling the condition for the smallest setting (2 people, 2 object movements). When considering each question individually, 91 9-95% are uninteresting questions. See App. B.4 for more details.
6 RELATED WORK
Theory of mind benchmarking for language models Theory of mind benchmarks in language models can be categorized into human-generated and model-generated datasets. While human- generated datasets (Shapira et al. 20236 Kim et al. 2024] Chen et al. 2024) test reasoning about goals, emotions of others, and future actions, they are often limited in size and scope. Machine- generated datasets, such as foundational ToMi (Le et al. 2019) and its successor Hi-ToM (Wu et al.) 2023) focus primarily on mental state tracking, but have significant limitations: ToMi only supports restricted set of actions (f (frenter: Qleave (mooeOOh(Comaiieer)) )). while Hi-ToM adds Ointo but only as the last action in a story, and both datasets have extremely restricted interactions to orders. In con- trast, our method, EXPLORETOM, significantly expands the scope of machine-generated datasets by supporting a larger number of actions, diverse wording, and plausible contexts. Unlike recent approaches that rely LLMs for generation (Kim et al. 2023) Xu et al.) 2024 Gandhi al. (024), EXPLORETOM ensures reliability and multii-ineeaaction storytelling, making it a more comprehen- sive and robust benchmark for theory of mind in L.Mss.

---

Published as a conference paper at ICLR 2025
Theory of mind beyond language modeling Theory of mind has been explored in various areas, including human computer interaction (Wang et al.] (021), explainable AI (Akula et al. (0222, and multi-agent reinforcement learning (Rabinowitz et al. 2018 Sclar et al. 2022; Zhu et al. [22II) Recent benchmarks have evaluated theory of mind in multi-modal settings (Jin et al. 2024) and
multi-agent collaboration (Bara et al.] 2021 [Shi al. 2024), but these focus on goal-driven in- teractions. Psychologists distinguish between affective (emotions, desires) and cognitive (beliefs, knowledge) theory of mind (Shamay-Tsoory et al. 2010), with cognitive theory of mind developing later in children (Wellman 2014). Our work targets cognitive theory of mind, which is well-suited for generating situations with homainn-specife language and provides unambiguous answers across cultures. By focusing on cognitive theory of mind, our approach complements existing research and provides a comprehensive benchmark for this crucial aspect of human reasoning in language models.
Synthetic data generation Synthetic data has become promising approach for acquiring high- quality data in various domains, including multihop question- question-answering answering (Lupidi et al., 2024), and language model evaluation (Wang et al. (024). The process involves data augmentation generaatonn and curation, with techniques such as permutation-based augmentation (Yu et al. 20244 Li et al. 2024a) and iterative prompting (Yang et al. 2022). However, model hallucination (Guarnera et al, 2020 Van Breugel al., 2023; Wood et al. 2021 Zhang et al. (202)) requires careful filtration and curation to ensure data quality. While prior works have used external feedback (Zelikman et al.) 2022 Luo et al. 2024), our approach leverages external LLM-as-judge to evaluate the plausi- bility and challenge of generated stories, both before and after infilling. Recently, AutoBencher (Li et al. 2024b) has also been proposed to automatically search for datasets that meet a salience, nov- elty, and difficulty desiderata, highlighting the importance of careful benchmark creation. Unlike AutoBencher, which over-generates under the assumption that text-based conditioning minimizes hallucinations, our approach lifts this assumption and actively searches the space of possible narra- tives. This enables create high-quality synthetic data regardless of the likelihood of story being generated zero-shot and generating even more challenging stories than with serereeerrtio...
7 CONCLUSIONS
Theory of mind (ToM) is essential for social intelligence, and developing agents with theory of mind is a requisite for efficient interaction and collaboration with humans. Thus, it is important to build path forward for imbuing agents with this type of reasoning, as well methods for robustly assessing the of models' theory of mind reasoning capabilities.
We present EXPLORETOM, an A A-ooweeed algorithm for generating reliable, diverse and chal- lenging theory of mind data; specifically, creating synthetic stories that require theory of mind to understand them, along with questions to probe understanding. EXPLORETOM's ss adversarial nature enables the stress testing of future models and making our evaluation more robust to data leakage. We show that EXPLORETTM generates challenging theory of mind evaluation sets for many frontier models, with accuracies as low as 0% for Llama-3.1 1 70B Instruct and 9% for GPT-4o. Moreover, we show that EXPLORETOM can be used as method for generating training data, leading to im- provements of up to 29 accuracy points in well-known theory of mind benchmarks. Synthetic data is crucial for this domain, given that data that articulates theory of mind reasoning is difficult to find in the wild: children have access to wide range of naturalistic social settings that incentivize the development of theory of mind but there is no such parallel pressure for LLMS.
Finally, we provide insights to why basic theory of mind is still elusive to LLMs, including poor state tracking skills and demonstrating the need for training data that purposefully requires theory of mind, which is likely not present in the wild nor in aandmly-genneatee data.
LIMITATIONS
EXPLORETOM offers a valuable tool for theory of mind research, and is first step towards develop- ing LLMS that can handle social interactions effectively. Although its data encompasses diverse and challenging settings- -oore than previously available- and is grounded in established psychologi- cal tests, EXPLORETOM necessarily simplifies the complexity of real-world states and narratives by constraining it to the supported types of actions and interactions. Our framework requires manual coding of new actions, wich can be time- consuming process but comes with the benefit of signif- icant reliability improvement. Furthermore, our stories are not necessarily goal- oriente narratives, highlighting an important avenue for future work: creating datasets where actions stem directly from character goals to further enhance diversity and plausibility.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We thank Ansong Ni for the valuable discussions. We gratefully acknowledge the Meta AIM fellowship support for Melanie Sclar. This material based upon work partly funded by the Defense Advanced Research Projects Agency (DARPA) under Contract No. FA8650-23-C-731 and ONR N00014-24-1-2207 Gift from Amazon. Any opinions, findings, conclusions, or recommendations expressed in this material are those of the authors and do not necessarily state reflect those of the United States Government or any agency thereof.
REFERENCES
Arjun R. Akula, Keze Wang. Changsong Liu, Sari Saba-Sadiya, Hongjing Lu, Sinisa Todor- ovic, Joyce Chai, and Song-Chun Zhu. Cx-tom: Counterfactual explanations with theory- of-mind for enhancing human trust in image recognition models. iScience, 25(1):003581 2022. ISSN 2589-0042. doi: http://ww........eeeeaaaaaaaaaaa
URL httpsts::
rciencedirectt
Cristian-Paul Bara, CH-Wang Sky, and Joyce Chai. Minderaft: Theory of mind modeling for situated dialogue in collaborative tasks. In Proceedings the 2021 Conference on Empirical Methods in Natural Language Processing, pp. I112-1 125, 2021.
Simon Baron-Cohen, Michelle O'Riordan, Rosie Jones, Valerie Stone, and Kate Plaisted. A new test of social sensitivity: Detection of faux pas in normal children and children with asperger syndrome. Journal of Autism and Developmental Disorders, 29(5):407-418, 1999.
Zhuang Chen, Jincenzi Wu, Jinfeng Zhou, Bosi Wen, Guanqun Bi, Gongyao Jiang, Yaru Cao, Mengting Hu, Yunghwei Lai, Zexuan Xiong, et al. Tombench: Benchmarking theory of mind in large language models. arXiv preprint arXiv:2402.15052, 2024.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, al. The llama 3 herd of models. arXiv preprint arXiv:2407.21178 2024.
Kanishk Gandhi, Jan-Philipp Fränken, Tobias Gerstenberg, and Noah Goodman. Understanding social reasoning in language models with language models. Advances in Neural Information Processing Systems, 36, 2024.
Luca Guarnera, Oliver Giudice, and Sebastiano Battiato. Deepfake detection by analyzing con- volutional traces. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognition workshops, pp. 666 667, 2020.
Peter E Hart, Nils Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2):100-107, 1968.
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song. and Jacob Steinhardt. Measuring massive multitask language understanding. In International Conference on Learning Representations, 2021.
Songbo Hu, Han Zhou, Mete Hergul, Milan Gritta, Guchun Zhang, Ignacio Iacobacci. Ivan Vulić, and Anna Korhonen. Multi 3 woz: A multilingual, multi-domain multi-parallel dataset for training and evaluating culturally adapted task-oriented dialog systems. Transactions of the Association for Computational Linguistics. 11:1396-1441 2023.
X. Angelo Huang, Emanuele La Malfa, Samuele Marro, Andrea Asperti, Anthony G. Cohn, and Michael J. Wooldridge. A notion of complexity for theory of mind via discrete world models. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Findings of the Association for Computational Linguistics: EMNLP 2024, pp. 2964-2983, Miami, Florida, USA, November 2024. Association for Computational Linguistics. doi: 10.18653/v1/2244 1/202/...i/22....ng....... URL wtt.htttt///ee aathacaaaaanooocoooooooo www.thooooy..oooooooooooo org.oogg/0000 find ngs- 1p. 167

---

Published as a conference paper at ICLR 2025
Albert Q Jiian,, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bam- ford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, et al. Mixtral of experts. arXiv preprint arXiv:2401 0000240000008,, 04088, 2024.
Chuanyang Jin, Yutong Wu, Jing Cao, Jiannan Xiang, Yen-Ling Kuo, Zhiting Hu, Tomer Ullman, Antonio Torralba, Joshua Tenenbaum, and Tiammin Shu. MMToM-QA: Multimodal theory of mind question answering. Lun- Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 16077-16102, Bangkok, Thailand, August 2024, Association for Computational Lin- guistics. httlst/t::// acc antho logy. org/ 2024. ac -olloloonnn.. 851
Chani Jung, Dongkwan Kim, Jiho Jin, Jiseon Kim, Yeon Seonwoo, Yejin Choi, Alice Oh, and Hyunwoo Kim. Perceptions to beliefs: Exploring precursory inferences for theory of mind in large language models. arXiv preprint arXiv:2407.060M) 2024.
Hyunwoo Kim, Melanie Sclar, Xuhui Zhou, Ronan Bras, Gunhee Kim, Yejin Choi, and Maarten Sap. Fantom: A benchmark for stress-testing machine theory of mind in interactions. In Proceedings of the 2023 Conference on Empirical Methods Natural Language Processing, pp.
14397-14413, 2023.
Seungone Kim, Juyoung Suk, Ji Yong Cho, Shayne Longpre, Chaceun Kim, Dongkeun Yoon, Gui- jin Son, Yejin Cho, Sheikh Shafayat, Jinheon Back, et al. The biggen bench: A principled benchmark for fine-graines evaluation of language models with language models. arXiv preprint arXiv:2406.05761, 2024.
Peter Kinderman, Robin Dunbar, and Richard P Bentall. Theory-of-minn mind deficits and causal attri- butions. British journal of Psychology, 89(2):1912204, 1998.
Matthew Le, Y-Lan Boureau, and Maximilian Nickel. Revisiting the evaluation of theory mind through question answering. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-UUCNLP,, pp. 5872-5877, 2019.
Qintong Li, Leyang Cui, Xueliang Zhao, Lingpeng Kong, and Wei Bi. Gsm-plus: A comprehensive benchmark for evaluating the robustness of Ilms as mathematical problem solvers. arXiv preprint SxXv:2402.199555 2024a.
Xiang Lisa Li, Evan Zheran Liu, Percy Liang, and Tatsunori Hashimoto. Autobencher: Creating salient, novel, difficult datasets for language models, 2024b. URL https://arxiv.ortt
abs/2407. 08351
Ziyang Luo, Can Xu, Pu Zhao, Qingfeng Sun, Xiubo Geng, Wenxiang Hu, Chongyang Tao, Jing Ma, Qingwei Lin, and Daxin Jiang. Wizardeoder: Empowering code large language models with evol-instruct. 2024.
Alisia Lupidi, Carlos Gemmell, Nicola Cancedda, Jane Dwivedi- Yu, Jason Weston, Jakob Foer- ster, Roberta Raileanu, and Maria Lomeli. Source2synth: Synthetic data generation and curation grounded in real data sources. arXiv preprint arXiv:2409.082333 2024.
OpenAI, 2024.
gpt-4p
David Premack and Guy Woodruff. Does the chimpanzee have theory of mind? Behavioral and brain sciences, 144):515-526, 1978.
Neil Rabinowitz, Frank Perbet, Francis Song, Chiyuan Zhang, SM Ali Eslami, and Matthew Botvinick. Machine theory of mind. In International conference on machine learning, pp. 4218- 4227. PMLR, 2018
Maarten Sap, Ronan LeBras, Daniel Fried, and Yejin Choi. Neural theory-of-mind? on the lim- its social intelligence in large Ims. In Proceedings of the Association for Computational Linguistics: EMNLP 2022, pp. 3762-3780, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. URL org/ eegg/mml2a ingst emn 1p-mall 248
aclanthology.
12

---

Published as a conference paper at ICLR 2025
Melanie Sclar, Graham Neubig, and Yonatan Bisk. Symmetric machine theory of mind. In Ka- malika Chaudhuri, Stefamie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 19450-19466. PMLR, 17-23 Jul 2022. URL htttps://proceediinn ngs. ml www.sressvvev.... w2/sclar22a........a.aa.aaaaaaaa httml
Melanie Sclar, Sachin Kumar, Peter West, Alane Suhr, Yejin Choi, and Yulia Tsvetkov. Minding language models' (lack of) theory of mind: A plug-and-play multi-character belief tracker. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 13960- 13980, Toronto, Canada, July 2023. Association for Computational I. Linguistics. doi: 10.18653/ 11/203..ccl-long7888 URL https::/p//... aalaaclanthht
2tt...orrr/222..c11orrrr.. 780
Simone G Shamay-Tsoory. Hagai Harari, Judith Aharon- Peretz, and Yechiel Levkovitz. The role of the orbitofrontal cortex in affective theory of mind deficits in criminal offenders with psychopathic tendencies. Cortex, 46(5):668- 677, 2010.
Natalie Shapira, Mosh Levy, Seyed Hossein Alavi, Xuhui Zhou, Yejin Choi, Yoav Goldberg, Maarten Sap, and Vered Shwartz. Clever hans or neural theory of mind? stress testing social reasoning in large language models, 2023a.
Natalie Shapira, Guy Zwirn, and Yoav Goldberg. How well do large language models perform on faux pas tests? In Findings of the Association for Computational Linguistics: ACL 2023, pp. 10438-10451, 2023b.
Haojun Shi, Suyu Ye, Xinyu Fang, Chuanyang Jin, Layla Isik, Yen-Ling Kuo, and Tianmin Shu. Muma-tom: Multi-modal multi-agent theory of mind. arXiv preprint arXiv:2408, 122524444..177,,,. 2024.
James WA Strachan, Dalila Albergo, Giulia Borghini, Oriana Pansardi, Eugenio Scaliti, Saurabh Gupta, Krati Saxena, Alessandro Rufo, Stefano Panzeri, Guido Manzi, et al. Testing theory of mind in large language models and humans. Nature Human Behaviour, pp. 1-11, 2024.
Tomer Ullman. Large language models fail trivial alterations theory-of-mind tasks. arXiv preprint arXiv:2302.08399 2023.
Boris Van Breugel, Zhaozhi Qian, and Mihaela Van Der Schaar. Synthetic data, real errors: how (not) to publish and use synthetic data. In International Conference on Machine Learning, pp- 34793-34808. PMLR, 2023.
Qiaosi Wang, Koustuv Saha, Eric Gregori, David Joyner, and Ashok Goel. Towards mutual theory of mind in human-ai interaction: How language reflects what students perceive about virtual teaching assistant. In Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems, pp. 1-14, 2021.
Tianlu Wang, Ilia Kulikov, Olga Golovneva, Ping Yu, Weizhe Yuan, Jane Dwivedi- Yu, Richard Yuanzhe Pang, Maryam Faral-Zarandi, Jason Weston, and Xian Li. Self-taught eval- uators. arXiv preprint arXiv:2408.02666 2024.
Yizhong Wang, Yeganeh Kordi, Swaroop Mishra, Alisa Liu, Noah A. Smith, Daniel Khashabi, and Hannaneh Hajishirzi. Self-instruct: Aligning language models with self-generated instructions. In Anna Rogers, Jordan Boyd-Grabel and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 13484- 13508, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10. 18653/ v1/2023.acl aalp:.3..llooog55... URL https: : htl///allaann awtpaaaaaaaacctcccaaaaaaaa www.:y/.rrg/020 acl acl- 754
Henry M Wellman. Making minds: How theory of mind develops. Oxford University Press, 2014.
Peter West, Chandra Bhagavatula, Jack Hessel, Jena Hwang. Liwei Jiang. Ronan Le Bras, Ximing Lu, Sean Welleck, and Yejin Choi. Symbolic knowledge distillation: from general language mod- els to commonsense models. In Marine Carpuat, Marie-Catherinn de Marneffe, and Ivan Vladimir Meza Ruiz (eds.), Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 4602-4625, Seattle, United States, July 2022. Association for Computational Linguistics. doi: 10. 18653vv/l 2022. 0022.naacl-nn main.341. URL /ttpttttpp............ //acl anthology org/2022 naacl -ma n. 341
13

---

Published as a conference paper at ICLR 2025
Alex Wilf, Sihyun Shawn Lee, Paul Pu Liang, and Louis-Philiipe Morency. Think twice: Perspective-taking improves large language models' theory-of -f-ind capabilities. ar preprint arXiv:2311. 100227, 2023.
Heinz Wimmer and Josef Perner. Beliefs about beliefs:
Representation and constraining function of wrong beliefs in young children's understanding of deception. Cognition, 13(1):103-128, 1983.
Erroll Wood, Tadas Baltrušaitis, Charlie Hewitt, Sebastian Dziadzio, Thomas J Cashman, and Jamie Shotton. Fake it till you make it: face analysis in the wild using synthetic data alone. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 3681-3691, 2021.
Yufan Wu, Yinghui He, Yilin Jia, Rada Mihalcea, Yulong Chen, and Naihao Deng. Hi-ToM: A benchmark for evaluating higher-order theory of mind reasoning in large language models. pp. 10691-10706, December 2023. doi: 122.8863/11/2223.nnnimm hwn..iiiiiiingeem...111.1 URL https://
aclanthology org wtt.::ss....dddddssmmm.......... 717
Hainiu Xu, Runcong Zhao, Lixing Zhu, Jinhua Du, and Yulan He. Opentom: A comprehensive
benchmark for evaluating theory-of-mind reasoning capabilities of large language models. arXiv preprint arXiv:2402.0604 2024.
Kevin Yang, Yuandong Tian, Nanyun Peng, and Dan Klein. Re3: Generating longer stories with
recursive reprompting and revision. pp. 4393 4479, December 2022. doi: 10.18653/v 1/2022.
emnlp-main.29%. URL https: / aoclannhoooyy.... oro.org//////// 2022. emn 1 p 1-pp-pmma--- ma...... i 296
Longhui Yu, Weisen Jiang, Han Shi, Jincheng YU, Zhengying Liu, Yu Zhang, James Kwok, Zhen- guo Li, Adrian Weller, and Weiyang Liu. Metamath: Bootstrap your own mathematical ques- tions for large language models. 2024. URL https:: ptttp::///penreview... net http://wwwweeeoouuutr.e. ?id N8N0hgNDRt
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: Bootstrapping reasoning with reasoning. Advances in Neural Information Processing Systems, 35: 2022.
Yue Zhang, Yafu Li, Leyang Cui, Deng Cai, Lemao Liu, Tingchen Fu, Xinting Huang, Enbo Zhao, Yu Zhang, Yulong Chen, et al. Siren's ' song in the ai ocean: a survey on hallucination in large language models. arXiv preprint arXiv:2309.01219, 2023.
Pei Zhou, Aman Madaan, Srividya Pranavi Potharaju. Aditya Gupta, Kevin McKee, Ari Holtzman, Jay Pujara, Xiang Ren, Swaroop Mishra, Aida Nematzadeh, et al. How far are large language models from agents with theory-of-mind? arXiv preprint arXiv:2310.03051, 2023.
Hao Zhu, Graham Neubig, and Yonatan Bisk. Few-shot language coordination by modeling theory of mind. In International Conference on Machine Learning, pp. 12901-12911. PMLR, 2021.
A APPENDIX
A. ACTIONS' FORMAL DEFINITION (CONT. FROM 2.2.1
All actions functions that transform state into another state, updating the world state and the beliefs of everyone involved up to two levels of recursion. All actions have preconditions, e.g. to enter room you need not be in it already.
A state E S is comprised of a world state wss (the things currently true physically about the world described), the first-order beliefs b,, and the second-order beliefs b2. First-order beliefs describe what each person believes to be the current world state, e.g. Anne believes that the apple is salted. Second-order beliefs describe what each person estimates that each other person believes to be the current world state, e.g. Anne believes that Beth thinks that the apple is salted.
Let's describe the definition of leaving in room through an example: "Beth left the kitchen.". and build the definition of the action function dieave Beth, kitchen S + S. As described above, the state is comprised of a world state, first-order beliefs, and second-order beliefs, i.e.,
Oleave Beth, kitchen (ws,. by, bz) (ws', - b1. bb)
14

---

Published as a conference paper at ICLR 2025
Let's first describe the world state update ws'. The world state remains the same for every entity (object, container, person, etc.), except for the person leaving the room Beth. Thus,
ws((g room) ws' (q. room) bq * Beth and ws' (q. room) -kitchen
Let's then describe the first-order belief updates 84. Here, assume that everyone in the same room as Beth (the kitchen) will know that Beth has left. We denote this group of people as witnesses(kitchen):
witnesses<kitchen) := {ples(p, room) = kitchen]
Everyone not in the kitchen will assume that Beth is still there unless communicated otherwise, since they have reason to believe she has left. Thus,
b1 (p. Beth, room) = b' (p. Beth, room) = kitchen vp & witnesses(kitchen) by (p, Beth, room) kitchen Vp E witnesses<kitchhen)
We now describe the second-order belief updates b/2 Here, we assume that everyone in the kitchen (including Beth) assumes that everyone else in the kitchen knows Beth left (and only them). If someone was not the kitchen, they will assume nothing has happened. Formally,
(p q, Beth, room) (p, q, Beth, room) kitchen Vp & wimmesse<(kichhen, Vi (p 9, Beth, room) -kitchen Vp witnesses(kitchenn Vq witmesses(kitchen) (p q, Beth, room) kitchen Vp E witnssess(kitchen) 4i & witnesses(kitchen)
Finally, the function can only be applied if Beth in the kitchen, i.e. it has the precondition ws (Beth, room) kitchen.
All other functions definitions can be found verbatim in the code to be released.
15

---

container name Published as a conference paper at ICLR 2025
A.2 ALL SUPPORTED QUESTIONS (CONT. FROM SECTION 2.2.2)
Table 4: List of all supported EXPLORETOM questions per property discussed and level of theory of mind, transcribed verbatim.
Property asked about Order
ToM
Expected Answers
Question (requesting Short Answer: in prompt)
room location
In which room was the <object>>> at the begin- ning?
room name
room location
In which room is the <object> now?
room name
room location
In which room was the <ohject>> before <action>>
room name
room location
1st
In which room will <person>> search for the room name <object>>
room location
2nd
In which room does <personI> think that room name <person2> will search for the <object>?
container location
In which container was the <object>> at the be- ginning?
container location
In which container is the <object>> now?
container name
container location
In which container was the <oojjet">> before <action>>
container name
container location
1st
In which container will <person>> search for the <object>>
container name
container location
2nd
In which container does <person think that <person2> will search for the <object>>
container name
abstract
topic
1st
Does
<person1>
know about yes or no
knowledge
<topicDiscussed>?
abstract
topic
2nd
What does <person1> think about knows about it
knowledge
<person2>>'s belief on <topieDiseussed>? or does not know (knows about it does not know about it) about it
knowledge about state update
1st
Does <person> believe that the <object> yes or no <newState>>? Answer yes or no.
knowledge about 2nd state update
Does <personI> believe that <person2> be- lieves that the <object>> <newState>? An- swer yes or no.
yes
16

---

Published as a conference paper at ICLR 2025
B ADDITIONAL EXPERIMENTS
B.1 AM-GENERATED STORIES ARE MORE CHALLENGING THAN OVERGENERATING AND FILTERING (CONT. FROM
40
Count
30
20
10
0
1100
-0.8
-0.6
-0.4
-0.2
0.0
0.2
Acc. Diff. between A and Baseline generated data
Figure 6: Histogram depicting accuracy differences between A A*-gnnerated datasets for Llama-3.1- 70B-Instruct and dataset created by over-generating and filtering with the same budget (i.e., base- line). Results show that A# is better at finding story structures that make challenging benchmark by showing low accuracy (negative values mean A is better finding challenging story structures).
B.2 INFILLED STORY STRUCTURES REMAIN CHALLENGING (CONT. FROM
Table 5: Changes in accuracy when infilling SEPLLORRTTMM-geeeee story structures to output natural-sounding stories. We only include comparison between the 40% of stories where the LLM as judge (Llama-3.1-70B 1-7BB Instruct) determined that all infilled actions were high quality.
Action Set
Include
Ace. Story Acc. Infilled
Acc.
Gentery Oleave
asymmetry
Structure
Diff.
0.20
0.43
0.22
Omooeobjjoontiierr>> (denoted A₁)
0.02
0.36
0.35
0,40
0.44
0.03
OOupaaeehhjSttte (denoted A2)
/
0.49
0.48
-0.01
0.45
0.48
0.03
.... OmweeeOiiiimmmmnneerrr Oupdeeehheee (AAs)
/
0.17
0.60
0.43
0.12
0.73
0.62
OmoweOOiiCommnnnee OmoveOhjRoom (Aa)
0.13
0.37
0.23
0.09
0,45
0.37
mmwee@lljContaiieere... (mtio= (As)
0.10
0.42
0.32
0.08
0.31
0.23
Ommeeebyyaarainerr OnsveChjRRomm Amioo (Aa)
0.13
0.51
0.38
0.73
0.86
0.13
GmoveOhijC Comiieer OmmmeOhjRoomm OchiChaa** (into (A7)
0.75
0.85
0.10
x
0.75
0.82
0.07
OchiiChat prrvitthatprrivate } (AAs)
0.68
0.76
0.08
0.61
0.68
0.07
OchiiChtt-puiiz (AAg)
0.54
0.61
0.07
Table 5 shows breakdown across all settings. 40% of the stories were infilled in single attempt.
Next step options are sampled simultancously with repetition penalty for added wording diversity. This is due to the stringent L.M as judge conditions to ensure quality. Without these quality and
17

---

Published as a conference paper at ICLR 2025
diversity constraints, 81% of the story structures are infilled within single attempt (73% with only quality constraints).
B.3 MODELS FAIL BOTH AT THEORY OF MIND AND PURE STATE TRACKING (CONT. FROM
5
Table Accuracy breakdown of the experiment shown in Table discriminating if each question is interesting or not. A question is interesting if the answer would change depending on the entity asked about, thus potentially requiring theory of mind. Results show that part of model's difficulty with EXPLORE To''s generated data could be attributed to poor state tracking (i.e., the uninteresting questions, noted lnt.)).
Llama
GPT4o
Mixtral
Includes Symmetry?
Acc. Int.
Acc.
%
Acc. Int.
Acc. Inn.
Acc. Int.
Acc. IItt.
%
Action Set
Int.
Int.
Int.
Int.
A1
x
0.42
0.20
44%
0.47
0.43
45%
0.44
0.38
48%
0.31
0.01
49%
0.46
0.28
49%
0.37
0.40
50%
A2
0.61
0.25
42%
0.57
0.24
41 %
0.39
0.01
50%
/
0.49
0.22
50%
0.56
0.23
49%
0.19
0.00
34%
Aa
0.54
0.24
47%
0.55
0.35
47%
0.46
0.18
46%
/
0.42
0.04
50%
0.57
0.31
48%
0.36
0.04
48%
A4
X
0.56
0.11
16%
0.58
0.09
2.%%
0.49
0.00
25%
0.25
0.18
49%
0.47
0.21
35%
0.44
0.00
31 31%
As
0.36
0.09
50%
0.50
0.30
45%
0.44
0.40
48%
/
0.24
0.15
50%
0.44
0.29
48%
0.44
0.47
50%
As
0.37
0.18
50%
0.64
0.25
44%
0.50
0.03
48%
/
0.31
0.14
50%
0.64
0.25
41% %
0.49
0.04
48%
A7
x
0.74
0.74
46%
0.76
0.76
44%
0.58
0.72
42%
0.74
0.67
43%
0.72
0.75
47%
0.47
0.67
42%
As
0.81
0.62
67%
0.80
0.72
66%
0.55
0.42
67%
0.62
0.59
74%
0.63
0.37
75%
0.41
0.42
74%
Ag
0.48
0.67
40%
0.50
0.42
40%
0.52
0.27
40%
0.54
0.51
50%
0.65
0.41
50%
0.54
0.27
50%
Total
0.49
0.31
48%
0.58
0.37
47%
0.45
0.26
47%
B.4 HOW LIKELY IS RANDOMI.Y-SAMPLE STORY TO REQUIRE THEORY OF MIND? (CONT. FROM 5
Table 7: Probability that a randomly-sampled story would require theory mind for answering at least one question. Actions considered are {aeaters ajeaee @moveObjjoontiiee } all settings of (2, people and {2. 3, 4} Cmnveeeijoontaine movements, with maximum actions, are shown.
Number of movements
Number of people
2
3
4
0.131
0.208
0.235
3
0.195
0.234
0.288
0.210
0.259
0.315
18

---

Published as a conference paper at ICLR 2025
Table 8: Probability that randomly-sampled (story, question) pair would potentially require the- ory of mind, meaning that the answer to the question varies depending on the entities considered. Actions considered are (Center djaave. @moveOhiConnainer) all settings of (2,3, 43 people and {2,3, 4] OmmvenejCnmtainee movements, with 10 maximum actions, are shown.
Number of movements
Number of people
2
3
4
0.090
0. 0.123
0.124
3
0.120
0.109
0.121
4
0.111
0.101
0.112
Table 9: Probability that a randomly-sampled (story, question, answer) triple would require an- swer that is different from the true world state (i.e., a false-helief question. Actions considered
are (eettor Gleave. OmoveOhiComainer) all settings of {2, 4) people and {2, 3, 4] AmoveOhiContainer move- ments, with 10 maximum actions, are shown.
Number of movements
Number of people
2
3
4
2 0.059
0.084
0,086
0,065
0.065
0.072
4
0.056
0.049
0.058
B.5 ON WHY STORY WITH A GREATER NUMBER OF PROPLE MAY COUNTERINTUITVVIIY IMPLY A LOWER AGER DIFFICULTY
In EXPLORETOM, the number of people and actions is important from a controllability and diver- sity perspective, but does directly quantify task mind is an active area of research. Huang et al. (2024) quantifies a theory mind problem complex- ity as the number of states necessary to solve it correctly (note that their approach requires manual annotation). While the number of states tends to increase with the number of people and actions, many questions do not require analyzing the whole story, e.g. if someone only entered the scene right at the end. When randomly sampling stories while fixing the number of core actions to e.g. 5, it's more likely to have some characters with little involvement in the scene if there are people in total than if there are 2 people. Since accuracy is computed across all questions about all characters, having larger number of people may bump the average accuracy. EXPLORETONN. s flexible frame- work allows for minimizing these cases through modifying the lookahead, but we chose against both doing this or filtering questions to show the performance is low even without these considerations.
quantification for theory of
19

---

Published as a conference paper at ICLR 2025
C PROMPTS USED FOR GENERATING AND VALIDATING EXPLORETOM'S DATA
C.I GENERATING STORY CONTEXTS (CONT. FROM 22.
Suggest short context where (num_people) people are together in room. should be at most two sentences long, and they should be able to observe each other. later in the story, characters are going to move around and store objects, so your context should be plausible under those constraints. Do not explicitly include that they can all see each other, it should clear from context. The could in house, work environment, etc.
Here's 8 an example for three people. Follow the same format.
LIST CHARACTERS' NAMES:
1. Emily, meticulous office manager.
2.
Jason, a tech-savvy intern.
3. Karen, diligent accountant.
GIVE STORY CONTEXT:
Emily, Jason, and Karen gathered around the central table in the sleek office's conference room, discussing the upcoming audit. As they strategized, the shelves and storage compartments lining the walls around them held the tools and documents they would need to organize and pack away.
ROOM IN WHICH THIS STORY BEGINS:
NAME ONE REASONABLE ALTERNATIVE ROOM THEY COJLD MOVE TO:
NAME ONE OBJECT TO BE MOVED BY A PERSON NURING THE STORY:
LIST (num containers) REASONABLE OPAQUE CONTAINERS THAT COULD CONTAIN
THIS OBJECT:
LIST (num_topics) DISTINCT AND REASONABLE TOPICS THEY COULD BE CHATTING ABOUT:
To get inspired, make this context happen in [sampled_lccationn Suggested names are cimplled_names]) but feel free to come up with your own names 1s it would suit the story better. Be direct with your answers: do not include parentheses responses requested. a singular thing is requested. The object could be anything--an apple, pen, spoon, a pair of scissers, a chocolate bar, etc.==, be creative! Avoid vases and microphones, or adding too many details to the object's description general.
clarifications beyond the not refer to plural oojects or give options
Figure 7: Prompts used for generating a story context, after infilling the variables (number of people, containers, topics, names, and location). Names and location are sampled independently to increase diversity, prompts shown Fig.
20

---

Published as a conference paper at ICLR 2025
List 100 names. Do not include any other text.
Suggest 100 different general contexts in which story may happen. The context should be able to have several people in the Location easily listening and observing each other.
1. school
2. hospital
3. vet shop
4. family living room
Follow the format and make the descriptions as short as possible. Do not include any text before the 1ist.
Figure 8: Prompts used for generating list of possible characters' names and locations for the story.
C.2 PROMPTS USED FOR STORY INFILLING
You are expert writer that uses simple language, avciding sounding unnatural cliché. You are clear, creative, and helpful. use simple sentence constructions and words so that everyone may understand you.
Figure 9: System prompt used for story infilling
Given the following story and knowing the descripticn of the characters involved, write the start of story. Don't actually describe any actions in the story, just the setting in which the stery will happen. Only include the characters that are mentioned in the story.
STORY:
(story_script)
CHARACTERS:
Seaaracters_dsscriptie
TWO-SENTENCE STORY BEGINNING THAT DOES NOT INCLUDE OR SUGGEST ANY INFORMATION OF WHAT HAPPEN IN THE STORY. DO NOT MENTION PEOPLE:
Figure 10: System prompt used for sampling narration (the start of the story, before infilling).
21

---

Published as a conference paper at ICLR 2025
Given the following story and knowing the description of the characters involved, suggest reasonable goal for each character. Only include the characters that were menticned in the story.
STORY:
(story_script]
CHARACTERS:
intaractera_descriptiin
CHARACTERS GOALS: <insert here>
Follow the format and do not include any other text. Only include the characters mentioned in the story, and do not even mention the others in your list.
Figure 11: System prompt used for sampling character goals.
22

---

Published as a conference paper at ICLR 2025
Continue the story Istory_lengthj, clearly conveying the action information below without altering it. Do not contradict any prior information, Avoid repeating the information verbatim, instead naturally (and possibly implicitly, but still unambiqucuslyy conveying the meaning. Do not add characters or actions that were not explicitly described. Do not replace characters even if this would improve flow. Combining actions into a single sentence OK as long as you do not alter the original information.
Make it short, yet interesting story to read. Make the text exciting to read as well g. starting all the sentences the same way. The stery needs to follow common sense, e.g. do not magically change an object's location without mentioning it. Do not include any notes, comments, parentheses, or any other form of extra text that would not belong in stcry. Feel free to hint or describe characters' goals and motivations fer performing the actions if it would make the story flow better.
character's speech, so try avoid e.
As warning, take into account that when someone tells someone privately they might
in the same location, e.g. they might be sending a text message or making a phone call; they might also be in the same location, in that case they could also communicate through gesture, a whisper, eto. Do not assume person is in the same room if it has not been made explicit before. Also, if someone they were distracted and did not forget to include it! Remember that in this case, it should be clear that the distraction or spying applies only to the action mentioned and they go back to nermal after the actien is finished. Avoid making multiple copies of the object.
spying, listen or saw something happen,
Give (num_tried srriee_completionee responses, ensuring to give num www.trresscoppletinnnn different phrasings of cont continuing the story conveying the action. Use very different wordings and sentence structures, but avoid changing object or room names!
WHO ARE THE CHARACTERS: {people_with_person
WEAT ARE THEIR GOALS: haa.iccal_chaaacterss.oo
NEW ACTION OR INFORMATION TO INCLUDE: (now_informaticn)
CURRENT SHORT STORY: [story_context)
Follow the format and do not include any other text. De not include any text before the list. Do not enumerate. Continue the story { story Length/. Avoid repeating the information verbatin, instead naturally (and possibly implicitly, but still unambigucusly) conveying the meaning.
STORY CONTINUATION: <fill>
STORY CONTINUATION: <fill>
Prompt used for iterative story infilling including characters' goals, and allowing for simultaneous sampling of several possible infillings, which when associated with repetition penalty, yields more diverse infillings. Infilling length is uniformly chosen between 'with a single sentence' and 'with up to two sentences', and infilling text type is uniformly chosen between 'Make the new text be declarative, without including conversations. and 'Make the new text conversational, using direct quotes to convey the words spoken by character'
Figure 12:
23

---

Published as a conference paper at ICLR 2025
D EXPLORETOM EXAMPLES (CONT. FROM 3
See a large sample of EXPLoREToMM-eeneraae data fataaets/faobboo//xplooore We also include few examples below.
co/
D.1 STORY STRUCTURE EXAMPLES
Addison entered the monastery dining hall.
Addison filled the large ceramic vase with fresh sunflowers.
Addison left the monastery dining hall.
Charlotte entered the monastery dining hall.
Charlotte painted the large ceramic vase with intricate designs in gold.
Charlotte glued few loose diamonds around the neck of the large ceramic vasc. While this action was happening, Addison witnessed this action in secret (and only this action).
Amelia entered the staff room.
Amelia moved the large first aid kit to the plastic storage bin, which is also located in the staff room.
While this action was happening, Alexis witnessed this action in secret (and only this action).
Amelia entered the equipment storage
Amelia the equipment storage room.
Amelia entered the staff room.
Amelia moved the large first aid kit to the equipment storage room, leaving the plastic storage bin in its
original location.
Amelia moved the large first aid kit to the metal cabinet, which also located in the equipment storage room.
Alexander entered the city hall planning department.
Alexander moved the large map of the city to the cardboard tube, which is also located in the city hall planning department.
Alexander told privately to Lestic that the large map of the city is the cardboard tube. Victoria entered city hall planning department. Leslie told privately Peyton the large map of the city is in the cardhoard tube.
Victoria moved the large map of the city to the plastic storage bin, which is also located in the city hall planning department.
Figure 13: Examples of the following story structures: OupdateChjfStnte (A2) with asymmetry;
[OmoveChjConttiner (moveOhjRoom) } (A4) with asymmetry; and (#moveOhjContainer (A5) without asym- metry.
24

---

Published as a conference paper at ICLR 2025
D.2 STORY INFILLING EXAMPLES
Table 10:
Example of adversarially sampled story structure and iterative infilling with Llama-3.1 70B Instruct, including story context (first row). This example showcases how the infilling process able to group sentences when they depict the same event but for more than one person, allowing for even more natural-sounding story.
Story Structure (list of actions)
Infilling for each action
<initial context>
The operations center, a bustling hub of activity during the park's peak festival season, was dimly lit except for few overhead fluorescent lights that cast sterile glow over the rows of workstations and storage units. The air was thick with the smell of stale coffee and fresh printer paper, a familiar scent to anyone who spent time behind the scenes of the busy amusement park.
Brooklyn entered the operations center.
As she entered the operations center, Brooklyn's 's presence was swiftly followed by James, whose rugged demeanor stood in contrast to the sterile environment of the room.
James entered the operations center. James moved the large festival schedule poster to the cardboard box, which is also located in the op- erations center.
James neatly relocated the oversized festival schedule poster, carefully placing it within the confines card- board box, a receptacle that had been securely positioned a comer of the operations center.
James left the operations center. Brooklyn Ieft the operations center.
Brooklyn stepped out into the bright sunlight, a stark contrast the dimly lit operations center she had just left, while James followed suit, the warm rays illuminating his weathered features. The festival preparations were now unfolding across the park, with both of them poised to tackle their respective tasks.
Tyler entered the operations center. Broōklyn entered the operations center.
As Tyler walked into the operations center, the soft hum of idle machinery and the faint scent of printer paper enveloped him, familiar yet calming atmosphere before the chaos of the festival. The room's sterile lighting seemed to intensify, reflecting off the polished surfaces as Brooklyn slipped in, her footsteps quiet on the worn floor.
Brooklyn moved the large festival schedule poster to the plastic storage bin, which also located in the op-
Brooklyn's 's hands moved swiftly as she carefully slid the oversized festival schedule poster into the large plastic storage bin the operations center.
erations center.
25

---

Published as a conference paper at ICLR 2025
Table 11: Example of adversarially sampled story structure and simple iterative infilling with Llama- 3.1 70B Instruct, along with example questions and model answers.
Story Structure (list actions)
Infilling for each action
David entered the study room. Sarah entered the study room.
David walked into the study room, scanning the organized chaos of files on the desk, just as Sarah stepped in, clutching her tablet and determined look.
Sarah moved the prototype model to the metal filing cabinet, which is also located in the study room. David left the study room.
Sarah moved the prototype model the metal filing cab- inet, her fingers brushing against the cool surface before turning to David with confident smile.
After a brief exchange with Sarah, David grabbed his briefcase and left the study room, mindful of the upcom- ing meeting downtown.
Mark entered the study room.
Mark entered the study room, his eyes quickly assessing the scattered documents and half-finished sketches on the table, before settling into his favorite chair by the window to brainstorm new ideas.
Mark moved the prototype model to the wooden chest, which is also lo- cated in the study room.
Mark, contemplating his latest concept, carefully picked up the prototype model from the metal filing cabinet and transferred it to the wooden chest, a better place for such inspiration-spurring creation.
EXPLORETOM
-generated answer using our domain- specific language
Selected Questions
GPT-4o's responses
Correct?
In which container will David search for the prototype model?
metal filing cabinet
david will search for the Yes prototype model in the metal filing cabinet.
In which container will Sarah search for the prototype model?
wooden chest
sarah will search for the No prototype model in the metal filing cabinet.
In which container will Mark search for the prototype model?
wooden chest
mark will search for the prototype model in the wooden chest.
Yes
In which container will David search for the prototype model? In which container will Sarah search for the prototype model?
metal filing cabinet
the metal filing cabinet.
Yes
wooden chest
sarah will search for the prototype model in the metal filing cabinet. the wooden chest.
No
In which container will Mark search for the prototype model?
wooden chest
Yes
26


Reviews:
[{"review_id": "aIDdAljhNj", "reviewer": "Reviewer_rkK5", "summary": "This paper proposes TracktheMind, an adversarial data generation pipeline to collect challenging ToM data via A* search.\n\nWith adversarial control on the difficulty of the generated data, the collected evaluation data poses a significant challenge to existing LLMs.\n\nThe authors also demonstrate the effectiveness of the TracktheMind-generated data as a training corpus to enhance ToM reasoning.", "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.\n\n* 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?\n\n* What is the background of the annotators? Does this matter for the performance in task completion?\n\n* 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?\n\n* 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.\n\n* 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?\n\n* 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.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "* **A controllable and generalizable data generation pipeline to collect ToM reasoning data**.\nWith 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.\n\n* **Intriguing results regarding the effect of interestingness in training and evaluation data**.\nThe 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.\n\n* **Details of hyperparameter settings and prompt designs**.\nThe 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**.\nThe 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.\n\n* **Lack of detailed discussion on the exact cost of data generation via A\\* search**.\nA\\* 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.\n\n* **Lack of deep analysis to disentangle the specific factors that bottleneck the LLM ability of ToM reasoning**.\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MC81eJLaN9", "reviewer": "Reviewer_BPYe", "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:\n\n- 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.\n\n- 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.\n\nAdditionally, the authors offer insights into potential factors contributing to the observed limitations in model performance on mind reasoning tasks.", "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?\n- 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.\n- 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.\n- 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.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- A novel framework for synthesizing mind reasoning data.\n- A sufficiently challenging benchmark to evaluate the mind reasoning capabilities of LLMs.\n- A robust training set offering more data, a complex structure, and strong generalization potential.\n- 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.\n- Other weaknesses align with the questions section, where I have shared thoughts on things needing further explanation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ovDUyAdgUW", "reviewer": "Reviewer_XWk4", "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.", "questions": "In addition to the questions above, I have the following question:\n\n1- 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?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1- Do large language models (LLMs) have theory of mind? I think this is a very important research question!\n2- Overall, the paper does a good job of presenting arguments and claims.\n3- 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.\n\n2- 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.\n\nWhile 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6p54CRAo1d", "reviewer": "Reviewer_p4tC", "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.\n\nGenerally 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.\n\nThe 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.", "questions": "Please refer to the weaknesses part.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "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.\n2. The types of ToM questions considered are comprehensive, especially those containing asymmetric belief updates, which can create complex questions.\n3. 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?\n2. In A* search, g(s) requires to evaluate LLM performance of the entire question generated by state s, which maybe time-consuming.\n3. 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.\n4. In Section 2.1, the story context structure is simple and may not be general enough for complex, real-world scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)