{"id":"b00d52a0-a9bb-4b5c-b370-56569b5cd06b","arxiv_id":"2412.12175","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"ExploreToM uses A* search over a domain-specific language to generate adversarial theory-of-mind stories that make LLMs, including GPT-4o, score as low as 0% and 9%, and fine-tuning on the data lifts ToMi accuracy by 27 points.","lead":"This paper introduces ExploreToM, a system that automatically generates tricky theory-of-mind stories for testing AI chatbots, using a search algorithm to select the hardest ones. It reports that top models like GPT-4o score as low as 9% on these stories, and that training on them improves performance on standard benchmarks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The load-bearing premise is that the hand-coded belief-update rules in §2.2.1/App. A.1 are correct; only 100 raw and 100 infilled human labels validate a large rule space, so a systematic error in any update rule would corrupt every ground-truth answer and downstream conclusion.","rationale":"The central claim of the paper is that ExploreToM produces valid, diverse, challenging theory-of-mind data for both evaluation and training. Every part of that claim — the benchmark accuracies in Table 1, the cross-model transfer in Table 2, the fine-tuning gains in Table 3, and the state-tracking analysis in §5 — is computed against ground-truth labels produced by the DSL tracker. If any of the hand-coded update rules is wrong in a way that the 100-question human check does not catch, the label is wrong and every downstream number inherits the error. The paper's strongest evidence is the deterministic nature of the tracker and the 99% human agreement on a random sample, which is real support; the weakness is that the sample is far too small for the rule space. The DSL includes multiple action types (enter/leave, move object to container/room, state update, private/public info, chit-chat), two asymmetry modifiers (peek and distracted), first- and second-order beliefs, and numerous preconditions; the appendix formalizes only one action, and the rest is deferred to code. The update rules contain genuine modeling choices that are easy to get subtly wrong, for example the order in which the world-state update and belief updates are applied, the default for non-witnesses ('assume no change'), and how second-order beliefs are revised when a character receives private information. These choices determine the answer to questions such as 'Does Anne think Charles knows the apple is salted?' and 'Where will X search?' A single wrong default would systematically corrupt all labels for that action class, which is exactly the load-bearing condition. This does not require the authors to have made an error; it means the paper's central claim is not yet secured without a more systematic check. The concrete test — an independent reimplementation of the tracker with differential testing, plus a stratified human study — would settle it. Because the reader already flagged this as the weakest assumption and issued a CONDITIONAL verdict, my stress-test does not change the verdict.","tokens_in":21907,"tokens_out":8757,"duration_ms":92853,"concrete_test":"Re-implement the tracker independently from the prose specification in App. A.1 and the released code, then run both trackers on (a) all reachable states generated by exhaustively applying every supported primitive action and modifier in sequences of length up to 6, and (b) 1,000 randomly sampled scripts from each of the 18 action sets plus the full released dataset. Any divergence in world state, first-order beliefs, or second-order beliefs is a bug. Additionally, run a stratified human study with at least 50 questions per action set and per question type (first-order, second-order, asymmetric, private-info) on raw story structures; if human disagreement concentrates in any rule class, recompute Tables 1-3 excluding that class to see whether the central claims survive.","verdict_should_be":"UNCHANGED","load_bearing_attack":"ExploreToM's validity rests on the deterministic tracker: questions and answers are generated directly from the state trajectory, and every experimental result (Table 1 difficulties, cross-model transfer in Table 2, fine-tuning gains in Table 3, and the state-tracking analysis in §5) inherits the tracker's correctness. The paper states that the update rules are 'specifically programmed and tested' (§2.2.1) and defers the full definitions to code ('found verbatim in the code to be released'), but App. A.1 shows only one rule, aleave. The human label check is 100 questions across 12 story structures (99% agreement) plus 100 infilled-story questions (89% agreement); this sample is far too small to cover the combinatorial space of actions, modifiers, rooms, containers, belief levels up to order 2, and asymmetric peek/distracted modifiers. The risk is concentrated exactly where subtle modeling decisions are made: for example, when Beth privately texts Charles, does the tracker update Charles's belief but not Anne's second-order belief about Charles's knowledge? Does a peek modifier update the witness's second-order beliefs correctly? Do non-witnesses' 'assume no change' defaults apply before or after the action's world-state update, and does this affect answers to 'where will X search'? A single wrong default would systematically corrupt every generated label for that action class, making the low benchmark accuracies and the fine-tuning gains untrustworthy. This is not an accusation of error; it is an identification of the least-secure load-bearing condition, which the manuscript's own small validation sample does not yet secure.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces ExploreToM, an A*-search-based pipeline that generates synthetic theory-of-mind (ToM) story structures from a domain-specific language with a deterministic belief tracker, and produces ground-truth QA pairs without using an LLM in the QA generation step. The authors show that such generated stories are challenging for Llama-3.1-70B, GPT-4o, and Mixtral, with per-model minima as low as 0% and 9% accuracy, that the difficulty transfers across models, and that fine-tuning Llama-3.1-8B on the generated data improves accuracy on ToMi (+27) and Hi-ToM (+29) while roughly preserving MMLU and dialogue state tracking. They also use the framework to attribute part of the failure to unreliable state tracking and to show that training data must contain theory-of-mind-requiring questions to improve downstream ToM performance.","tokens_in":22219,"tokens_out":9338,"duration_ms":97810,"significance":"The strongest contributions are the deterministic QA generation, the A* search over a larger action space than prior benchmarks, the cross-model transfer demonstration, and the fine-tuning gains on external benchmarks; the state-tracking and data-mixture analyses are concrete and falsifiable. The 99% human agreement on 100 raw labels, though limited in coverage, is a useful sanity check. The paper's main claims, however, depend on two points that need strengthening before they are fully convincing: the correctness of the hand-coded tracker is not demonstrated at the required coverage, and the headline difficulty scores are minima of an optimization over each model's own accuracy rather than distributional estimates. These are fixable with additional reporting and code/appendix completeness, so I recommend major revision rather than rejection.","major_comments":[{"comment":"The headline finding that frontier models score \"as low as 0% and 9%\" is a direct consequence of the search objective: g(s) is defined as the target model's accuracy on all generated questions, and A* minimizes f(s)=g(s)+h(s). The resulting scores are minima of an optimization run for each model, not estimates of typical performance on the generated distribution. To support the claim that ExploreToM reveals general limitations rather than just that an optimizer can find a failing story for any model, please report the full distribution (mean, median, quantiles) of accuracies over generated stories, and compare against randomly sampled stories with the same isDesired constraints, in addition to the current 2-point average A* vs over-generation result. This should be accompanied by confidence intervals, since Table 1 shows per-action-set accuracies ranging from 0.00 to 0.77.","section":"Section 2.2.3 / Abstract / Table 1"},{"comment":"Every experimental result in the paper inherits the correctness of the hand-coded belief tracker, but the manuscript does not actually provide the full tracker: Section 2.2.1 refers to App. A.1 for \"the full programs\", while App. A.1 defines only aleave and states that \"all other functions definitions can be found verbatim in the code to be released.\" The human label check (100 questions across 12 story structures, 99% agreement) is too sparse to cover the combinatorial space of actions, asymmetric modifiers (apeek, adistracted), belief levels up to order 2, and interaction orders. A single incorrect update rule, for example how a private info message updates non-recipients' second-order beliefs or how a peek modifier updates witnesses' higher-order beliefs, would silently corrupt the ground truth for an entire action class and all downstream fine-tuning results. Please include full formal definitions or the code in the supplement, and add human validation stratified by action type, modifier, and belief order. The formal definition of aleave also appears to have a typo in the first-order belief update (the witness line uses b1 where b'1 is presumably intended), which further underscores the need for a careful presentation of the tracker.","section":"Section 2.2.1 / Appendix A.1 / Limitations"},{"comment":"The claims about cross-model transfer and about A* being better than over-generation are under-specified statistically. Table 2 reports single numbers on a random sample of 1000 (story, question) pairs, but because pairs are clustered within stories, the standard errors are not captured; similarly, the A* vs over-generation comparison in Section 3 reports a 2-point average difference with no confidence interval or paired significance test. Given the large variance across action sets (Table 1), these comparisons should be presented with per-setting paired differences and bootstrap or cluster-robust intervals. This does not undermine the existence of transfer, but it currently prevents the reader from assessing its magnitude.","section":"Section 3 / Table 2 / Figure 6"}],"minor_comments":[{"comment":"The caption says \"18 action sets\" but the table lists 9 action sets each evaluated with and without asymmetry; please clarify the counting.","section":"Table 1"},{"comment":"Typo: \"autorregresive\" should be \"autoregressive\".","section":"Section 2.1"},{"comment":"The model name \"Mixtral 7x8B\" is inconsistent with \"Mixtral-8x7B-Instruct\" used elsewhere in the paper.","section":"Table 2"},{"comment":"The Section 4 text reports 79,700 (story, question, answer) triples while the Figure 5 caption says 85,000 story structure samples; please reconcile or clarify the distinction between triples and story samples.","section":"Section 4 and Figure 5 caption"},{"comment":"In the aleave definition, the first-order belief update for witnesses is written as b1(p,Beth,room) = not kitchen, but this line appears to use the old belief variable where the updated belief b'1 was intended; please fix the notation.","section":"Appendix A.1"},{"comment":"Typo: \"wich\" should be \"which\".","section":"Limitations"}],"recommendation":"major_revision","confidential_remarks":"The main risk is that the belief tracker's full definitions are only available in the promised code release; I would treat verification of that code, and stratified human validation of the novel asymmetric updates, as conditions for acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First: this is a real contribution, and it mostly does what it says. The core new thing is the A* search over a purpose-built DSL with a deterministic belief tracker, plus asymmetric updates (peek/distracted) and intermediate-state memory questions. That combination isn't in ToMi, Hi-ToM, BigToM, OpenToM, or FANToM. The framework is released with code and data, and the ground truth comes from the tracker, not an LLM, which is the right call.\n\nWhat it does well: the human validation (99% on 100 raw structures, 89% on infilled) is decent for a synthetic generator, and the cross-model transfer results (Table 2) show the difficulty isn't just an artifact of one model. The fine-tuning gains on external benchmarks are large and credible: +27 on ToMi, +29 on Hi-ToM, with only a 2-point MMLU dip. The decomposition into interesting vs. uninteresting questions, and the finding that state tracking questions are harder, is a genuinely useful diagnostic. The random-generation study (78–87% of randomly sampled stories have no ToM-requiring question) is a nice conceptual point about training data bias.\n\nNow the soft spots, in rough order of importance.\n\nFirst, the headline numbers—'as low as 0% and 9%'—are searched-for minima. The A* objective is the target model's own accuracy, so of course the search finds stories where that model is at chance or worse. That's fine for stress-testing, but the abstract should say 'lower bound on performance under adversarial construction' rather than implying these are typical or independent measurements. It's a framing issue, not a flaw in the method.\n\nSecond—and this is the one I'd want the authors to address—the correctness of the entire pipeline rests on the hand-coded belief-update rules, and the validation is thin relative to the rule space. The appendix defines one rule (aleave) in detail and defers the rest to code. Only 100 raw and 100 infilled questions were checked against humans, which is a lot less than the combinatorial space of actions, modifiers, belief levels, and asymmetries. A single systematic error in, say, how non-witnesses' default beliefs interact with an action, would corrupt every downstream result. I don't see evidence of such an error, and the 99% agreement on a random sample is reassuring, but I'd want either a formal specification of all rules, or a stratified human sample covering each action type and modifier. This is fixable, and it's the difference between 'mostly trustworthy' and 'fully trustworthy.'\n\nThird, the A* vs. over-generation comparison shows only a 2-point gap with no significance testing, on half the settings. Minor, because the contribution isn't that A* is dramatically better.\n\nFourth, there's an internal inconsistency: Section 3 says 162 settings, but the product of the listed factors (9 action sets × 2 asymmetry × 3 people × 3 actions × 2 rooms) is 324. The paper needs to reconcile that.\n\nWho is this for? Anyone building or evaluating ToM benchmarks, and anyone interested in adversarial synthetic data generation for LLM evaluation. It deserves a serious referee—the method is sound, the release is reproducible, and the weaknesses are addressable. I'd accept it for review and push for the rule-specification and validation improvements.","headline":"ExploreToM is a serious, well-executed adversarial-generation framework for ToM; the central claims hold, but the headline difficulty numbers are searched-for minima and the tracker's correctness needs more validation.","tokens_in":22848,"tokens_out":3523,"would_cite":true,"duration_ms":33991,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"LLMs drop to near-zero accuracy on theory-of-mind stories generated by ExploreToM, a search over hand-coded mental-state rules.","keywords":["theory of mind","large language models","adversarial data generation","A* search","domain-specific language","mental state tracking","benchmark generation","state tracking"],"falsifier":"Take 100 ExploreToM story structures that use each action type and modifier at least once, and have two independent human annotators write out every character's first- and second-order beliefs after each action; if the tracker's labels disagree with human judgment on any rule (for example, a private message updating only the recipient, or a distracted witness not knowing an action occurred), the paper's reliability claim and the reported model accuracies would rest on the wrong ground truth.","tokens_in":21687,"feed_emoji":"🧠","tokens_out":8285,"duration_ms":78735,"temperature":0.7,"pith_summary":"This paper argues that existing theory-of-mind benchmarks are too simple and can overstate model ability, and it introduces ExploreToM to close that gap: a generator that searches a hand-written domain-specific language for story structures whose characters have divergent mental states. The search minimizes a target LLM's accuracy on auto-generated questions, so the resulting data is deliberately hard; the paper reports accuracies as low as 0% for Llama-3.1-70B and 9% for GPT-4o on the hardest settings. The same data, when used for fine-tuning, transfers to classic benchmarks, raising ToMi accuracy by 27 points and Hi-ToM by 29 points while mostly preserving general reasoning. The paper also reports that LLMs fail at basic state-tracking questions even more than at explicitly social ones, and that randomly generated stories rarely require theory of mind, suggesting why natural training data may under-develop the skill.","feed_headline":"LLMs score as low as 0% on theory-of-mind test","feed_subtitle":"A* search builds these stories; fine-tuning on them lifts classic ToMi accuracy by 27 points.","key_machinery":"The load-bearing mechanism is the mental-state tracker embedded in a domain-specific language for theory of mind. Every supported action—entering and leaving rooms, moving objects, updating object state, private and public messages, chit-chat, and asymmetric modifiers like secret witnesses or distractions—is a function that updates a world state plus first-order and second-order beliefs, with preconditions on when it can apply. Because the tracker generates the questions and answers, ground truth is exact, and A* search (a best-first search that minimizes cumulative cost plus a heuristic estimate of remaining cost) uses a model's accuracy as the cost while a heuristic pushes toward stories satisfying user constraints such as number of people, rooms, or key actions. This combination lets the generator actively seek out hard cases and supports both evaluation and training.","core_discovery":"The central claim is that a program-guided adversarial generator can produce theory-of-mind stories that are simultaneously correct, diverse, and hard for current LLMs. A story is a sequence of actions from a domain-specific language; each action updates the physical world and every character's first- and second-order beliefs, so ground-truth answers to generated questions are produced by the tracker, not by an LLM. The A* search scores partial stories by the target model's question accuracy and drives toward narratives with low accuracy, yielding stories on which frontier models score as low as 0% (Llama-3.1-70B) and 9% (GPT-4o). Fine-tuning Llama-3.1-8B on this data improves the classic ToMi benchmark by 27 accuracy points, showing the same data can serve as training material, not just evaluation.","pith_inferences":["A natural next experiment is to run the A* search against a fixed model while varying the target model, and check whether the difficulty gap between models predicts downstream performance differences; the paper only reports the 2-point accuracy difference between A* and over-generation, not stability across random seeds.","The finding that uninteresting state-tracking questions are harder suggests that part of LLMs' ToM failure may be a broader event-tracking deficit; a testable extension is to train on state-tracking-only questions and see whether ToM questions improve.","Because the DSL separates the logical story structure from the lexical story surface, ExploreToM could be extended to test whether models answer from reasoning or from wording cues, an avenue the paper does not pursue.","The 78%-of-random-stories-do-not-require-ToM statistic implies that other synthetic-data pipelines that sample stories without an adversarial objective may quietly under-exercise belief divergence; measuring the 'interesting' fraction of those pipelines would show whether this is a general phenomenon."],"forward_implications":["ExploreToM can serve as a benchmark that is refreshed against whatever model the A* search targets, so it should stay challenging even as LLMs improve, without waiting for manual benchmark writing.","Fine-tuning on ExploreToM-generated stories transfers to existing theory-of-mind benchmarks: +27 points on ToMi and +29 on Hi-ToM, with small gains or no loss on BigToM, OpenToM, and FANToM.","State tracking is a separable and harder component of theory of mind in this data; uninteresting questions (where every character would give the same answer) are answered less accurately than interesting ones by all three models tested.","Randomly sampled stories from the same domain-specific language require theory of mind only 13–31% of the time, so curated search rather than random generation is what produces useful ToM training data.","Infilled natural-language stories remain challenging (average accuracy 0.61 for Llama-3.1-70B), and human agreement with tracker labels is 99% on a 100-question check, supporting the reliability of the ground truth."],"supporting_citations":[{"why":"Supplies the A* search algorithm that ExploreToM uses to find story structures a target model answers poorly.","marker":"Hart et al., 1968"},{"why":"Defines the ToMi benchmark and action primitives; the paper reports large gains on it after fine-tuning with ExploreToM data.","marker":"Le et al., 2019"},{"why":"Prior Hi-ToM benchmark with a restricted action set, which ExploreToM extends by allowing info actions anywhere and supporting richer interactions.","marker":"Wu et al., 2023"},{"why":"Source of the Llama-3.1 models used both as target models for the A* search and as the base model for fine-tuning.","marker":"Dubey et al., 2024"},{"why":"Source of GPT-4o, one of the frontier models evaluated on ExploreToM-generated data.","marker":"OpenAI, 2024"},{"why":"FANToM benchmark used to test whether fine-tuning on ExploreToM data transfers to another theory-of-mind evaluation.","marker":"Kim et al., 2023"},{"why":"OpenToM benchmark used to check transfer of the fine-tuned model to another theory-of-mind evaluation.","marker":"Xu et al., 2024"},{"why":"BigToM benchmark used to check transfer of the fine-tuned model to another theory-of-mind evaluation.","marker":"Gandhi et al., 2024"}],"fun_headline_variants":["A* generated stories break LLMs' theory of mind","LLMs score 0% on adversarial theory-of-mind test","From 0% to +27 points: adversarial data fixes theory-of-mind","Adversarial stories: LLMs hit 0%, fine-tuning lifts ToMi by 27"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The hand-written belief-update rules in the domain-specific language correctly predict what a person knows when they witness, miss, or are told about an action; only 100 labels were human-checked, so an error in any rule would corrupt the ground-truth answers and the accuracy numbers.","fun_headline_variants_meta":{"raw":{"variants":["A* generated stories break LLMs' theory of mind","LLMs score 0% on adversarial theory-of-mind test","From 0% to +27 points: adversarial data fixes theory-of-mind","Adversarial stories: LLMs hit 0%, fine-tuning lifts ToMi by 27"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000995,"raw_usage":{"total_tokens":4221,"prompt_tokens":960,"completion_tokens":3261,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":576,"completion_tokens_details":{"reasoning_tokens":3191}},"tokens_in":576,"tokens_out":3261,"duration_ms":23501,"temperature":1.0,"reasoning_tokens":3191,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T16:48:40.858436+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take 100 ExploreToM story structures that use each action type and modifier at least once, and have two independent human annotators write out every character's first- and second-order beliefs after each action; if the tracker's labels disagree with human judgment on any rule (for example, a private message updating only the recipient, or a distracted witness not knowing an action occurred), the paper's reliability claim and the reported model accuracies would rest on the wrong ground truth.","supporting_citations":[{"cited_title":"Fantom: A benchmark for stress-testing machine theory of mind in interactions","cited_arxiv_id":null,"evidence_quote":"FANToM benchmark used to test whether fine-tuning on ExploreToM data transfers to another theory-of-mind evaluation."},{"cited_title":"https://openai.com/index/hello-gpt-4o","cited_arxiv_id":null,"evidence_quote":"Source of GPT-4o, one of the frontier models evaluated on ExploreToM-generated data."},{"cited_title":"Understanding social reasoning in language models with language models","cited_arxiv_id":null,"evidence_quote":"BigToM benchmark used to check transfer of the fine-tuned model to another theory-of-mind evaluation."}],"review_version":1}