PaperlayerView exact revision on arXiv

Source-linked AI summary

The Decrypto Benchmark for Multi-Agent Reasoning and Theory of Mind

Andrei Lupu, Timon Willi, Jakob Foerster

arXiv:2506.20664v1cs.AIcs.CLcs.HCcs.MA

TL;DR

LLM theory of mind and multi-agent abilities remain poorly understood, while real-world agentic settings involve complex interactions that current benchmarks do not capture. The paper introduces Decrypto, a game-based benchmark and interactive ToM experiment platform, and evaluates frontier models and human-AI play. LLMs struggle at game play, and newer reasoning models perform significantly worse than older models on some ToM tasks.

  • Problem

    Real-world agentic applications involve multi-agent interactions, but current benchmarks do not capture their multi-step, partially observable, stochastic character, and LLM theory of mind remains poorly understood.

    Source: §1 · p. 1

  • Method

    The authors introduce Decrypto, a multi-agent game benchmark and interactive ToM platform, and adapt cognitive psychology experiments to evaluate belief reasoning and perspective taking.

    Source: §1 · pp. 1–2, §3.2 · pp. 4–5

  • Results

    LLMs often underperform simple baselines in cooperative and competitive play, and newer reasoning models such as Claude 3.7 Sonnet and o1 high are significantly worse at some ToM tasks than older models.

    Source: §7 · p. 10

  • Takeaways & Limitations

    Decrypto provides an interactive platform for evaluating multi-agent reasoning and ToM, including experiments inspired by cognitive psychology.

    Source: §1 · p. 2, §7 · p. 10

    Specialist agents may overfit to Decrypto, and rule-based agents that coordinate flawlessly with a pre-agreed strategy can fail catastrophically in cross-play with other agents, including humans and LLMs.

    Source: §4.1 · p. 5

Abstract

from arXiv · show

As Large Language Models (LLMs) gain agentic abilities, they will have to navigate complex multi-agent scenarios, interacting with human users and other agents in cooperative and competitive settings. This will require new reasoning skills, chief amongst them being theory of mind (ToM), or the ability to reason about the "mental" states of other agents. However, ToM and other multi-agent abilities in LLMs are poorly understood, since existing benchmarks suffer from narrow scope, data leakage, saturation, and lack of interactivity. We thus propose Decrypto, a game-based benchmark for multi-agent reasoning and ToM drawing inspiration from cognitive science, computational pragmatics and multi-agent reinforcement learning. It is designed to be as easy as possible in all other dimensions, eliminating confounding factors commonly found in other benchmarks. To our knowledge, it is also the first platform for designing interactive ToM experiments. We validate the benchmark design through comprehensive empirical evaluations of frontier LLMs, robustness studies, and human-AI cross-play experiments. We find that LLM game-playing abilities lag behind humans and simple word-embedding baselines. We then create variants of two classic cognitive science experiments within Decrypto to evaluate three key ToM abilities. Surprisingly, we find that state-of-the-art reasoning models are significantly worse at those tasks than their older counterparts. This demonstrates that Decrypto addresses a crucial gap in current reasoning and ToM evaluations, and paves the path towards better artificial agents.

1 Introduction

Real-world agentic applications involve multi-agent interactions, but existing benchmarks do not capture their multi-step, partially observable, stochastic character, and LLM theory of mind remains poorly understood. The paper introduces Decrypto as an interactive benchmark and ToM platform for studying these abilities.

1 Introduction

  • Real-world agentic applications involve many actors, making them multi-step, multi-agent, partially observable, and stochastic in ways existing benchmarks do not capture.Source: §1 · p. 1
  • Most existing ToM benchmarks lack interaction and rely on Sally-Anne task variants, while textual translations of embodied scenarios can introduce confounds and bias.Source: §1 · p. 1
  • Decrypto addresses limited interactive ToM evaluation with a multi-agent secret-message game in which two agents communicate while preventing a third party from intercepting them.The game is designed to make other capabilities as easy as possible for LLMs, apart from multi-agent reasoning.Source: §1 · p. 1
  • Decrypto is presented as the first platform for interactive LLM ToM experiments, with new experiments requiring only prompts and a few lines of code.The authors demonstrate its use through variants of two classic cognitive psychology experiments.Source: §1 · p. 2
  • The authors introduce a game metric using the determinant of the Hessian matrix to measure outcome sensitivity to changes in players or prompts.Source: §1 · p. 2

2 Decrypto: The Game

Decrypto is a three-player code-guessing game in which an encoder must help a teammate decode a secret code without enabling an interceptor to do so. Shared histories make interception easier over time, while the game’s language-based strategic demands can be analyzed through pragmatic inference and theory of mind.

2 Decrypto: The Game

  • Each episode lasts at most eight turns, with Alice encoding, Bob decoding, and Eve intercepting in a three-player variant of the board game.Source: §2 · p. 2
  • Alice and Bob share four ordered secret keywords, while each turn Alice gives three hints for a code of three distinct digits from 1 to 4.Codes do not repeat within an episode; Bob and Eve independently guess, and incorrect decoding or successful interception earns the opposing side a token.Source: §2 · p. 2
  • After each turn, guesses, the code, and game events become public, so Eve can use accumulated code and hint histories to infer keyword associations without seeing the keywords.Eve wins after two intercepts or two miscommunications; Alice and Bob win by surviving eight rounds.Source: §2 · pp. 2–3
  • Hints may be open-ended and multiword, but must be real words referring to keyword meanings and rely on publicly available information.Source: §2 · p. 3

Beyond word associations

  • Decrypto can be formalized as a Rational Speech Act pragmatic inference game in which Bob and Eve update beliefs about Alice’s intended meaning; optimal play requires Bob to model Alice’s beliefs about Eve’s beliefs.Source: Beyond word associations · p. 3

3 Decrypto: The Benchmark

Decrypto is designed to isolate language-based reasoning and theory of mind while supporting competitive, cooperative, and interactive ToM evaluations. The section describes benchmark properties, agent-matchup settings, and adaptations of cognitive psychology tasks for assessing belief reasoning and perspective taking.

3 Decrypto: The Benchmark

  • Decrypto avoids requiring symbolic, mathematical, spatial, or tool-use reasoning and avoids state tracking and text-based embodied scenarios that can introduce confounds.Source: §3 · p. 3
  • Even Llama 3.1-8B understands the rules, but much stronger models still struggle to play well.Source: §3 · p. 3
  • Its two-team, three-player dynamics support both competitive and cooperative scenarios, and difficulty can vary with the agents assigned to each role.The benchmark includes 680 possible keywords, yielding over 8.8 billion keyword combinations, plus open-ended hints and human-play compatibility for human-AI comparisons.Source: §3 · p. 3

3.1 Multi-Agent Reasoning

  • Competition compares a model playing both Alice and Bob against another model as Eve, while ad-hoc coordination pairs different Alice and Bob models against a fixed Eve.Human-AI coordination is a subset in which either Alice or Bob is played by a human.Source: §3.1 · p. 4
  • Miscommunications and intercepts expose distinct failure modes, while average turns per episode captures both; game length is more informative than win rate given LLMs’ weaker hinting than interception.Source: §3.1 · p. 4

3.2 Theory of Mind

  • Decrypto’s strategic communication requires reasoning about other players’ beliefs and world knowledge, and its platform supports interactive ToM experiments with new prompts and about 15 lines of code.Source: §3.2 · p. 4
  • The adapted Smarties tasks measure representational change and false belief by comparing Eve’s pre-reveal keyword guesses with her own or another interceptor’s predicted beliefs.Weak variants accept any answer differing from ground truth; strong variants require predicting the original answer, which likely requires self-consistent representation or strong counterfactual reasoning.Source: §3.2 · p. 4
  • The perspective-taking task asks Alice to predict Eve’s code guess, measuring prediction accuracy and how often Alice expects Eve to intercept.The latter measure can indicate whether Alice considers information available to Eve and integrates that perspective into hint choices.Source: §3.2 · p. 5

4 State of the Art

Decrypto evaluations distinguish generalist models used out of the box from task-designed specialist agents, making their assumptions explicit. The section describes embedding baselines and human-game collection as ways to study coordination and cross-play.

4 State of the Art

  • The authors caution that Decrypto’s many evaluation settings require explicit assumptions when declaring state of the art.They distinguish generalist benchmarking from specialist-agent research as separate perspectives.Source: §4 · p. 5, §4.1 · pp. 5–6

4.1 Specialist vs Generalist Agents

  • Generalists play out of the box without external fine-tuning or in-context learning, while specialist agents may use task-specific strategies, training, or prompt engineering.The paper recommends prompt variation for generalist evaluations and states that prompt engineering is the designer’s burden for specialists.Source: §4.1 · p. 5
  • Embedding baselines use top-K semantically similar hints, but differing embeddings can undermine cross-play even when agents coordinate under a shared strategy.The paper uses K=16 for the remaining experiments; larger K increases miscommunications and decreases average game length.Source: §4.1 · pp. 5–6, Figure 2 · p. 6

4.2 Human-Data Collection

  • The human-data collection gathered 10 full games against a fixed Llama 3.1-70B-Instruct interceptor, with play continued to eight turns even after two interception tokens.Figure 3 reports cooperative cross-play and competitive results for six agents over 32 games and three seeds.Source: §4.2 · p. 6, Figure 3 · p. 7

5 Results

Across coordination, competition, and human cross-play, LLMs show substantial weaknesses, while embedding baselines can outperform them in selected settings. ToM evaluations find poor performance on strong tasks and perspective taking, with Llama 3.1-70B outperforming newer reasoning models on several ToM measures.

Human Evaluation

  • In ad-hoc human coordination, all tested agents perform worse than humans; Claude 3.7 with extended thinking is strongest in both tested roles, while DeepSeek-R1-32B trails GPT-4o and Llama 3.1-70B as decoder.The replay evaluation uses 10 human games; only Claude 3.7 with extended thinking comes close to human decoders.Source: Table 1 · p. 8, §5 · p. 8

Coordination

  • At K=16, baseline-baseline teams outperform tested LLM agents but coordinate poorly with them, and baseline-LLM teams have significantly more miscommunications than baseline-baseline or LLM-LLM teams.Among LLMs, the Bob model is the main determinant of miscommunications, with Llama-3.1-8B seeing the most.Source: §5 · pp. 7–8

Competition

  • Novice humans achieve a 33% win rate against even the strongest Eve agents, indicating that LLMs’ strong Eve advantage is not a property of the game itself.Larger models generally perform better in competitive roles, but most teams rarely survive against Eve.Source: §5 · p. 8

Theory of Mind

  • All models achieve ≤10% accuracy on the strong representational-change and false-belief tasks, and Llama 3.1-70B outperforms recent reasoning models across all three ToM tasks.In perspective taking, models often answer using privileged information rather than the other agent’s limited viewpoint; this persists when the prompt emphasizes Eve does not know the secret keywords.Source: §5 · pp. 8–9, Figure 4 · p. 9

6 Related Work

Related work spans multi-agent environments, language games, and ToM benchmarks. The paper positions Decrypto as a structured interactive setting for language-based reasoning and ToM across human and artificial agents.

Multi-agent settings

  • Prior multi-agent studies often emphasize spatial reasoning, while social deduction and negotiation games offer less structured insight because of free-form dialogue and deception.AgentPro studies competitive games but lacks Decrypto’s cooperative component.Source: §6 · p. 9

Theory of Mind

  • Decrypto connects work on modelling human beliefs with work on modelling artificial agents, and differs from cited ToM benchmarks by enabling interactive belief modelling and influence.The passage contrasts Decrypto with both recent benchmarks and Rabinowitz et al. (2018).Source: §6 · p. 9

Language games

  • Decrypto can support persona-based studies of cultural backgrounds in pragmatic inference, a direction raised by work on Codenames.Shaikh et al. (2023) study cross-cultural pragmatics but do not evaluate LLMs.Source: §6 · p. 9

7 Conclusion

Decrypto provides an interactive benchmark for evaluating language-model coordination, competition, and theory of mind. The authors report that frontier models struggle with strategic communication and human coordination, and that newer reasoning models can underperform older models on some ToM tasks.

7 Conclusion

  • Decrypto is an interactive benchmark for assessing coordination, competition, and theory of mind in language models, and a platform for designing interactive ToM experiments.It addresses limitations of existing ToM benchmarks, including bias from textual translation of embodied scenarios and lack of interactivity.Source: §7 · p. 10
  • Frontier models struggle with nuanced communication and strategic reasoning, often underperforming simple baselines in cooperative and competitive settings.Human-AI experiments also indicate limited ability to coordinate with humans or understand their communications.Source: §7 · p. 10
  • Newer reasoning models, including Claude 3.7 Sonnet and o1 high, are significantly worse than older models on some ToM tasks.The experiments adapt two classic cognitive-science experiments for interactive evaluation.Source: §7 · p. 10
  • The authors identify improving model ToM, comparing how models represent humans versus other agents, and applying multi-agent RL to fine-tune LLMs as research directions.They also describe Decrypto as a platform for future work on inter-AI and human-AI interactions.Source: §7 · p. 10

A Limitations and Future Work

The authors identify limitations in model accessibility, evaluation cost and scope, and the range of ToM abilities assessed. They also describe extensions and supporting materials, including interactive experiments, a code-example rationale, and word-embedding baselines.

A Limitations and Future Work

  • Weaker models may find Decrypto's game dynamics and ToM tasks too complicated; Llama 3.1-8B-Instruct failed to understand the perspective-taking prompt.The authors note that they largely eliminated confounding factors affecting LLM performance, but not this remaining difficulty.Source: A Limitations and Future Work · p. 14
  • Computing Figure 3 is costly at scale: the combinations grow as n^3, or 2n^2 for matrix slices, and the human study collected only 10 games.The authors provide local evaluation tools and a lightweight command-line interface for human studies; they call for more extensive studies, including with humans as interceptors.Source: A Limitations and Future Work · p. 14
  • Decrypto assesses some ToM abilities, including representational change, false belief, and perspective taking, but may miss reasoning about other agents' intentions or emotions.The authors suggest extending the benchmark with additional ToM experiments and other research directions, including multi-agent RL and pragmatic inference.Source: A Limitations and Future Work · p. 14

B Impact Statement

  • The authors caution that Decrypto measures only a subset of ToM and that benchmark performance should not be equated with broader abilities such as intent inference or emotion understanding.They cite Hu et al. (2025) when noting that similar overclaims have been made about other benchmarks.Source: B Impact Statement · p. 14

C Rationale for the code in Figure 1

  • The Figure 1 code example relies on assumptions about readers' knowledge of geometry, GitHub, Star Wars, and the song “Thunderstruck” to make its hints interpretable.The authors present the example as an illustration of Alice using ToM and player-specific information to choose hints.Source: C Rationale for the code in Figure 1 · p. 15

D Diagrams for Theory of Mind Experiments

  • Figure 5 evaluates representational change and false belief by comparing Eve's post-reveal beliefs about past keywords with her initial prediction.Strong passes match the initial answer; weak passes differ from the real keywords, and evaluation uses turns where the initial answer was incorrect.Source: Figure 5 · p. 15

E Baseline Details

  • The word-embedding baselines select hints from 5,696 common nouns, favoring hints more similar to each coded keyword than to the others; Eve then assigns hints by cosine similarity.Eve uses hint-history averages and combinatorial optimization to choose a globally optimal guess.Source: E Baseline Details · p. 16

F Experimental Details

The experiments use text-only, prompt-driven interactions with role-specific instructions and multi-turn context. The authors describe output handling and generation settings, then report local and API-hosted model evaluation and associated computational costs.

F.1 Prompting

  • Experiments are text-only and prompt-driven, with shared game-rule instructions and role-specific prompts that summarize the game, provide role information, explain the task, and specify output format.Models without a system prompt receive it as a prefix to the first user message.Source: §F.1 · p. 16
  • Prompts and model outputs remain in context across turns; malformed outputs trigger up to 10 re-prompts, while ToM prompts and outputs are excluded from later-turn context.If no correctly formatted answer appears after 10 attempts, the system defaults to a dummy answer.Source: §F.1 · pp. 16–17

F.2 Generation parameters

  • The authors set temperature to 0.6 for Figure 3 and Table 1 and to 0 for Figure 4; token limits range from 750 to 10,000 to avoid prematurely cutting generations.Some closed-source models remain nondeterministic even at temperature 0.Source: §F.2 · p. 17

F.3 Computational Costs

  • Open-source models ran locally on a cluster using vLLM, with each instance on eight Nvidia A100 GPUs; Claude 3.7 Sonnet with Extended Thinking cost about $0.10 per role per episode.A 32-episode run with three seeds and Claude 3.7 Sonnet in all roles cost approximately $30.Source: §F.3 · p. 17

G Additional Results

Additional results indicate that game performance is robust to tested prompt variations, while model size remains a significant predictor. The authors also report that current LLM abilities are skewed toward Eve winning most games.

G Additional Results

  • Prompt variants did not significantly change average game length for Llama-3.1-8B and Llama-3.1-70B, suggesting poor play is more likely due to reasoning limits than prompt tuning.The evaluation covered 625 prompt setups, with 32 games over three seeds per setup.Source: G Additional Results · p. 17
  • Current LLM abilities are skewed toward Eve: she wins a vast majority of games, while Alice/Bob teams rarely survive.Figure 7 reports survived games over 32 games, with means and standard deviations across three model seeds; the authors expect the balance to shift as hinting improves.Source: Figure 7 · p. 18
  • Across 625 prompt combinations, both tested models were robust to substantial prompt variations, and model size remained the most significant predictor of performance.The combinations varied whether encoder and decoder system prompts and user prompts matched.Source: Figure 8 · p. 18

H Decrypto as a pragmatic inference game

This section formalizes Decrypto as an iterated RSA pragmatic inference game in which successful communication requires modeling other players, and examines inaccurate Eve models, lexical differences, and role-defining system prompts. It also describes how system and user prompts use hint history, constrain codes to non-repeating digits, and request role-specific guesses or predictions.

H Decrypto as a pragmatic inference game

  • Decrypto can be modeled as an iterated RSA game in which speakers balance successful communication against interception, requiring listeners to model how the speaker models Eve.The literal listener assigns probability only to meanings semantically compatible with the hints, using a uniform prior over codes not seen on previous turns; the speaker’s utility can weight miscommunication and interception differently by turn.Source: H Decrypto as a pragmatic inference game · pp. 19–20

H.2 Further refinements

  • Different player lexicons can cause miscommunication or be exploited, while uncertain RSA offers a way to study how cultural differences between speaker and listener affect understanding.The framework predicts more miscommunication when Alice’s culturally informed hints are unlikely under Bob’s distribution.Source: H Decrypto as a pragmatic inference game · p. 20, §H.2 · p. 21

H.1 Modelling Eve

  • Even with perfect rationality and no miscommunication cost, an inaccurate model of Eve lowers Alice’s expected utility; LLMs may also ignore interception costs when choosing hints.Expected utility is maximized only when Alice’s model of Eve matches Eve’s true probabilities.Source: §H.1 · p. 21

I System Prompts

  • The system prompts define Encoder, Decoder, and Interceptor roles, specify ordered hint and guess formats, and include five variants for robustness evaluation.The basic prompt outlines the game rules; role-specific prompts provide examples of how to generate hints or infer codes.Source: I System Prompts · p. 22
  • System prompts remind agents that keywords may be anything, encourage using recent hint history, and specify that code digits are distinct numbers from 1 to 4.Eve’s system prompt also includes an example of reasoning about a guess.Source: I System Prompts · p. 24

J User Prompts

  • Turn prompts give Alice, Bob, and Eve role-specific histories and current game information before asking Alice to give hints or Bob and Eve to guess.The histories include prior hints, outcomes, and counts of miscommunications and interceptions; decoder and interceptor prompts also emphasize matching guesses to hint order and using hint history.Source: J User Prompts · pp. 25–27
  • In prediction experiments, Alice is explicitly asked to predict the Interceptor’s guess from the hints she provided.The prompt gives the code and hints, then requests a step-by-step prediction in a specified answer format.Source: J User Prompts · p. 27

K.1 Human Data Collection Details

Human data collection used a monitored hot-seat setup and was not intended as a representative measure of human ability. The interfaces gave each role its relevant game information, confirmed answers, and summarized prior turns while limiting information leakage.

K.1 Human Data Collection Details

  • The human dataset was not representative; it was intended to show LLMs performing worse than non-expert players and to seed future human–AI coordination and ToM studies.Participants were told Eve was AI, played on one computer, and were monitored by an author to prevent cheating.Source: §K.1 · p. 27

K.2 Interfaces

  • At the start, Alice sees the current code and four keywords, while Bob sees Alice’s hints and current keywords and Eve sees only Alice’s hints.Humans use the same prompt as LLMs but enter responses directly rather than using the LLMs’ “ANSWER: ...” format.Source: Figure 9 · p. 28, Figure 10 · p. 29, Figure 11 · p. 30
  • Role-specific confirmation screens ask Alice to verify hints and Bob and Eve to verify guesses, reducing input errors such as typos or submitting the wrong response type.The confirmations are intended to prevent human errors.Source: Figure 12 · p. 30, Figure 13 · p. 31, Figure 14 · p. 31
  • After the first turn, each role receives a summary of the previous turn and accumulated histories; a waiting screen appears after Eve’s guess to prevent her seeing Alice’s next interface.The turn summary includes the code, hints, both guesses, hint history mapped to keywords, and code history.Source: Figure 15 · p. 31, Figure 16 · p. 32, Figure 17 · p. 32

L Representative Failure Cases

The examples show several distinct failure modes: Alice may give obvious or repetitive hints that risk interception, Alice and Bob may associate the same hint differently, and Eve may misorder otherwise correct keyword mappings.

L Representative Failure Cases

  • LLMs generally produce relatively obvious hints, and Alice’s failure to make them sufficiently different from earlier hints risks interception by Eve.The example describes this as a failure to come up with creative hints significantly different from previous ones.Source: L Representative Failure Cases · p. 34
  • Alice can reuse hints for the same digits, while another example shows hints similar to those previously used, leaving Eve an interception opportunity.The example with Llama 3.1-8B says Alice should aim for completely different hints to avoid interception and losing the game.Source: L Representative Failure Cases · p. 35
  • Eve can map repeated hints to the right keywords yet still give the code in keyword-enumeration order rather than the required hint order.In the example, Eve’s guess is wrong despite assigning the hints to the right keywords.Source: L Representative Failure Cases · p. 37

M Representative Model Outputs for Perspective Taking

The examples contrast a model that predicts an interceptor’s first-turn guess will be random with models that assume the interceptor knows the secret keywords. Even when prompted with the interceptor’s information limits, o1 makes the latter mistake.

M Representative Model Outputs for Perspective Taking

  • Llama 3.1-70B correctly predicts a random first-turn interceptor guess because the interceptor has no actual knowledge of the keywords.The example uses the keywords hill, library, material, and marriage.Source: M Representative Model Outputs for… · pp. 38, 40
  • Claude 3.7 Sonnet and o1 incorrectly assume the interceptor can access the keywords and predict that it will guess the correct code.Both examples concern the first turn of the same environment seed.Source: M Representative Model Outputs for… · pp. 39–40
  • Even after a modified prompt explicitly states the interceptor’s information limits, o1 still assumes it can link the hints to the keywords and guess correctly.The modified prompt says the interceptor does not know the keywords or even the set of possible keywords.Source: M Representative Model Outputs for… · pp. 40–41
  • The examples and Figure 4 provide evidence of a significant regression in ToM abilities in newer models compared with Llama 3.1-70B.The paper states that reasoning models lack key ToM abilities, including perspective taking.Source: M Representative Model Outputs for… · p. 40

Related papers

Loading 2506.20664v1…