A Notion of Complexity for Theory of Mind via Discrete World Models (2024)

Abstract: Theory of Mind (ToM) can be used to assess the capabilities of Large Language Models (LLMs) in complex scenarios where social reasoning is required. While the research community has proposed many ToM benchmarks, their hardness varies greatly, and their complexity is not well defined. This work proposes a framework inspired by cognitive load theory to measure the complexity of ToM tasks. We quantify a problem’s complexity as the number of states necessary to solve it correctly. Our complexity measure also accounts for spurious states of a ToM problem designed to make it apparently harder. We use our method to assess the complexity of five widely adopted ToM benchmarks. On top of this framework, we design a prompting technique that augments the information available to a model with a description of how the environment changes with the agents’ interactions. We name this technique Discrete World Models (DWM) and show how it elicits superior performance on ToM tasks.

## introduction theory of mind (tom) studies how agents form and use beliefs to reason in dynamic environments @xcite . originally developed to describe human interactions @xcite as well as toddlers' psychological development @xcite , tom has been quickly adopted by other fields, including artificial intelligence @xcite , bayesian inference @xcite and machine learning @xcite . in machine learning, tom has both descriptive and pre-figure 1 : example of the dwm prompting technique on a classical sally-anne qa task @xcite . inspired by our complexity framework (section 3.1), dwm takes the original task and splits it into sequences, the state events (see def. 3.1), and prompts the llms to describe the states. we show that, in most cases, this aids the llm in providing correct answers. in this work, we propose a framework to characterise a tom benchmark's difficulty, i.e., its complexity, as the number of state events that are sufficient to track the state of an object, including k th -order beliefs motivated by theoretical parallelisms with sweller's cognitive load theory @xcite . we characterise the complexity of five standard tom benchmarks, from false belief to commonsense and social reasoning, and compute their complexity as a proxy of their inherent difficulty. in-spired by prompting techniques that split a task into elementary sub-problems that are solved sequentially, like tree of thoughts @xcite and least-to-most prompting @xcite , we introduce a technique that stimulates a model's reasoning capabilities via discrete world models (dwm). dwm leverages the notion of statefulness via a succinct and coherent representation of each state events, as illustrated in figure 1 . we test dwm on tomi @xcite , mindgames @xcite , adv-csfb @xcite , socialiqa @xcite , and fantom @xcite , eliciting superior performance than chain of thoughts (cot) @xcite and tree of thoughts (tot) @xcite on those problems whose state spaces are informative. we further assess whether memorisation affects a model's performance, and we discover that while this phenomenon happens for standard benchmarks such as tomi @xcite , with input-output pairs that can be retrieved word for word via prompting, it does not strongly correlate with a drop of performance on memorised tom benchmarks. we conduct our experiments on a variety of open-and closed-source llms, including gpt-3.5-turbo, @xcite , llama3-70b (ai@meta, 2024; @xcite and mixtral 8x7b @xcite . in summary, in this paper: we consider our work a step towards a framework that formalizes the hardness of a tom problem in an unambiguous way, inspired by the theory of world models @xcite . ## related work over 40 years of research on tom in psychology @xcite @xcite on human development has created a fertile ground for the development of these ideas in adjacent fields. in the last decade, many works studied tom in artificial intelligence and machine learning @xcite , with applications to multi-agent systems and reinforcement learning @xcite . more recently, the rise in popularity of llms shifted the interest towards understanding and benchmarking large models' capacity to solve increasingly complex tom tasks @xcite @xcite . while some researchers believe llms have already become proficient in solving tom tasks @xcite @xcite , others show scepticism and illustrate cases where they fail on trivial variations of well-known problems @xcite @xcite . in a joint effort between computer scientists and psychologists, many tom benchmarks have been developed and used to test neural-network models, including llms @xcite @xcite . recently, concepts such as world models @xcite have found applicability mostly as discrete prompting techniques in conjunction with optimisation procedures @xcite . researchers have found evidence of an emergent internal representation (e.g., world model's surrogates) of the state games @xcite and state-tracking abilities @xcite @xcite , necessary for correct belief tracking in tom problems. cognitive load theory emerged in the late eighties with sweller's work on human problem solving @xcite . most measures of cognitive load are based on subjective reports from humans @xcite . even though some attempts at automatic cognitive load measures have been present @xcite , they have not been widely adopted in the community. the works that are more similar to our complexity framework are only tangentially related to tom. inspired by the work in @xcite and the results in @xcite , our prompting technique is inspired by @xcite and @xcite : the former develops an architecture to record the agent's experiences. the latter proposes a prompting technique that forces a model to express the intermediate computational steps to solve a problem. for obj 1 , an optimal split to track the apple merges the first two states and chunks of the input prompt. for obj 2 , which involves the 1 st -order belief of bob, the statefulness is higher, with e 2 that cannot be merged with e 3 as it introduces partial observability. the complexity of the task (bottom) is computed as per eq. 2, where the complexity of objects that are not directly relevant to the question/answer is discounted. ## methodology in this section, we introduce a notion of complexity for tom problems which quantifies the hardness of a problem as the number of computational steps humans take to solve them and compare it with sweller's cognitive load theory. we then present the dwm prompting technique within the complexity framework and show how it differs from standard methods like cot and tot. we further characterise its efficiency with the number of input/output tokens and queries to a model as the control variables. ## experimental evaluation the experiments are organised as follows. we first test the performance of dwm on tomi @xcite , mindgames @xcite , adv-csfb @xcite , socialiqa @xcite , and fantom @xcite , comparing it with cot @xcite , tot @xcite and prompting with structured data (struct), i.e., the model is queried to first represent the problem in a structured format such as json or yaml. we further show that tomi has been memorised word for word by gpt models, with cot (and any technique that leaves the input unchanged) being the best-performing method. we then quantify the complexity of the benchmarks introduced above and highlight the correlation with the models' performances. our framework shows complexity ranges between easy and hard problems, even within a benchmark. we conduct our experiments on gpt-3.5-turbo, gpt-4 (openai, 2023), llama3-70b (ai@meta, 2024; @xcite and mixtral 8x7b (jiang et al., 2024). ## conclusions this paper introduces a complexity framework to measure the difficulty of theory of mind (tom) problems. it quantifies the difficulty by tracking necessary states (stateful) and unnecessary states (stateless), with the latter discounted in the complexity computation. the framework evidences a strong correlation between complexity and model performance. inspired by this framework, we propose dwm, a prompting technique that splits a prompt into parts to query a model for a consistent representation of the environment and agents' beliefs. dwm outperforms cot and tot by extracting implicit but relevant information.