  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 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.
