PaperlayerView exact revision on arXiv

Source-linked AI summary

LLM-Coordination: Evaluating and Analyzing Multi-agent Coordination Abilities in Large Language Models

Saaket Agashe, Yue Fan, Anthony Reyna, Xin Eric Wang

arXiv:2310.03903v3cs.CLcs.MA

TL;DR

LLMs’ coordination strengths and limitations remain unclear despite their reasoning and planning capabilities. This paper introduces a benchmark combining agentic play with coordination questions; results show strength in environment-focused coordination but persistent challenges in Theory of Mind and Joint Planning.

  • Problem

    Although LLMs show planning, reasoning, and hints of Theory of Mind, their strengths and limitations in coordination games remain unclear.

    Source: §1 · p. 1

  • Method

    The LLM-Coordination Benchmark evaluates LLMs in four pure coordination games through multi-turn Agentic Coordination and single-turn CoordinationQA.

    Source: §1 · p. 1

  • Results

    LLM agents match or outperform RL in environment-focused settings and collaborate with unseen partners, but partner-belief reasoning and Joint Planning remain weak.

    Source: §5 · pp. 6–9

  • Takeaways & Limitations

    The benchmark indicates LLMs have potential as agents in pure coordination, while identifying Theory of Mind and Joint Planning as areas needing improvement.

    Source: §5 · p. 8, §6 · p. 9

    Effective coordination reasoning relies primarily on larger models such as GPT-4-turbo, whose latency and compute demands make them less suitable for real-time applications.

    Source: §8 · p. 9

Abstract

from arXiv · show

Large Language Models (LLMs) have demonstrated emergent common-sense reasoning and Theory of Mind (ToM) capabilities, making them promising candidates for developing coordination agents. This study introduces the LLM-Coordination Benchmark, a novel benchmark for analyzing LLMs in the context of Pure Coordination Settings, where agents must cooperate to maximize gains. Our benchmark evaluates LLMs through two distinct tasks. The first is Agentic Coordination, where LLMs act as proactive participants in four pure coordination games. The second is Coordination Question Answering (CoordQA), which tests LLMs on 198 multiple-choice questions across these games to evaluate three key abilities: Environment Comprehension, ToM Reasoning, and Joint Planning. Results from Agentic Coordination experiments reveal that LLM-Agents excel in multi-agent coordination settings where decision-making primarily relies on environmental variables but face challenges in scenarios requiring active consideration of partners' beliefs and intentions. The CoordQA experiments further highlight significant room for improvement in LLMs' Theory of Mind reasoning and joint planning capabilities. Zero-Shot Coordination (ZSC) experiments in the Agentic Coordination setting demonstrate that LLM agents, unlike RL methods, exhibit robustness to unseen partners. These findings indicate the potential of LLMs as Agents in pure coordination setups and underscore areas for improvement. Code Available at https://github.com/eric-ai-lab/llm_coordination.

1 Introduction

The paper addresses unclear strengths and limitations of LLMs in pure coordination games. It introduces full-game and component-level evaluations, finding stronger performance on environmental reasoning than on partner-belief reasoning and joint planning.

Benchmark contribution

  • The benchmark evaluates individual LLMs in pure coordination through multi-turn Agentic Coordination and single-turn CoordinationQA across four collaborative games.It assesses innate ability to understand and act in these scenarios, rather than orchestration of multiple LLMs to solve tasks.Source: §1 · pp. 1–2

Agentic Coordination

  • LLM agents match or outperform RL baselines when decisions rely on observable environment variables, but struggle when coordination requires considering partners’ beliefs and intentions.They also collaborate with new partners, unlike self-play MARL methods that fail to adapt to unseen agents.Source: §1 · p. 2

CoordinationQA

  • CoordinationQA shows LLMs are strongest at Environment Comprehension, weaker at Theory of Mind, and often especially poor at Joint Planning.Some models perform worse than random choices on Joint Planning; GPT-4-turbo has a marked performance gap over other LLMs across the question types.Source: §1 · p. 2

Evaluation contributions

  • The study compares LLM agents with RL baselines in self-play and cross-play, evaluating their potential as coordination agents.The paper also investigates Environment Comprehension, Theory of Mind Reasoning, and Joint Planning as components of coordination.Source: §1 · pp. 2–3

2 Related Work

Prior coordination research largely develops and aligns RL agents, while LLM research explores reasoning, tools, and multi-agent cooperation. This paper distinguishes its evaluation through established pure coordination games and component-level analysis.

Multi-agent Coordination

  • Coordination work has largely enhanced RL methods, including efforts to align Overcooked self-play agents with humans and learn grounded Hanabi policies over arbitrary conventions.Earlier work also highlighted the importance of human data for effective Human-AI collaboration.Source: §2 · p. 3

Planning and Reasoning with Large Language Models

  • LLM reasoning research uses memory and tools for long-horizon tasks and complex games, and explores strategies such as ReAct, Self-Verification, and Self-Consistency.These strategies establish baseline performance for the paper’s language-agent implementations.Source: §2 · p. 3

Multi-agent LLMs

  • Prior multi-agent LLM studies examine cooperation in varied tasks, while this work focuses on fully cooperative established games and analyzes coordination components.The paper contrasts its setting with scenarios that may include competitive incentives and its component-level analysis with broader coordination evaluations.Source: §2 · p. 3

3 LLM-Coordination Benchmark

The benchmark pairs multi-turn play in four pure coordination games with single-turn questions drawn from challenging game states. Together, these settings evaluate holistic agent behavior and specific coordination reasoning abilities.

3.1 Multi-turn Agentic Coordination

  • The benchmark selects four pure coordination games to isolate coordination challenges in controlled, well-studied settings with clear metrics and reproducible scenarios.The games are Hanabi Challenge, Overcooked-AI, Collab Capture, and Collab Escape.Source: §3.1 · p. 3
  • Hanabi tests perspective-taking and implicit communication under incomplete information, while Overcooked requires agents to locate resources and synchronize soup preparation and delivery.In Hanabi, players see their partner’s cards rather than their own; in Overcooked, soup requires three onions and cooks for 20 time steps.Source: §3.1 · p. 4
  • Collab Capture scenarios test positioning and door-control strategies, while Collab Escape scenarios vary proximity to adversaries and generators to test cooperative escape strategies.Capture scenarios include prioritizing door control to enable a teammate; escape scenarios include luring the adversary away or continuing generator repairs to protect a partner.Source: §3.1 · p. 4

3.2 Single-turn Coordination QA

  • CoordinationQA uses manually selected edge cases that require agents to understand state, infer partner intentions, and plan, with ambiguous cases removed.The suite contains 66 scenarios and three questions per scenario, for 198 questions total.Source: §3.2 · pp. 4–5
  • Environment Comprehension questions test indirect inferences about layouts, observations, and artifact counts.Source: §3.2 · p. 4
  • Theory of Mind questions ask models to predict partner intentions and identify partners’ requirements.Source: §3.2 · p. 4
  • Joint Planning questions ask models to choose the best next action for coordination from a scenario’s state or observation.The questions target a decision that agents repeatedly face during gameplay.Source: §3.2 · p. 5

4 Experimental Setup

The experimental setup evaluates LLM coordination through self-play and cross-play games, supported by an agent framework and comparisons with reinforcement-learning baselines. It also tests multiple-choice coordination reasoning across environment comprehension, Theory of Mind, and joint planning.

4.1 Agentic Coordination

  • Agentic experiments use self-play with same-type agents and cross-play with unseen partners requiring behavioral adaptation.The setup reports no prompt or setup differences between the two settings.Source: §4.1 · p. 5, §4.1.1 · p. 5

4.1.1 LLM Agents

  • The LLM agent framework combines memory of game rules, current observations, and prior actions with LLM action selection and game-specific action grounding.Grounding also filters infeasible actions.Source: §4.1.1 · p. 5
  • Hanabi agents receive an answer-verification step, while ToM reasoning interprets partner actions or positions before action generation in Hanabi and CollabEscape.Additional ToM reasoning was not tested in Overcooked because of significant latency and cost constraints and marginal benefits.Source: §4.1.1 · p. 5

4.1.2 MARL Agents

  • The MARL comparisons use PPO and Population-Based Training for Overcooked, and BAD, SAD, and Off-Belief Learning for Hanabi self-play.Cross-play baselines include behavior-cloning-based partners for Overcooked and SAD or Off-Belief Learning for Hanabi.Source: §4.1.2 · pp. 5–6
  • GPT-4-turbo demonstrates superior coordination in 3 of the five scenarios compared in Table 1.The table compares MARL and LLM-agent methods across five layouts.Source: Table 1 · p. 6
  • Table 2 compares LLM agents on CollabCapture and CollabEscape across layouts and reports the impact of explicit ToM reasoning.Results are based on three trials for each layout configuration.Source: Table 2 · p. 6
  • Performance is measured by Overcooked delivery score, Hanabi correctly arranged cards, and capture or escape success rate and average turns.Each Overcooked delivery provides 20 points to both agents.Source: §4.1.2 · p. 6

4.2 CoordinationQA

  • CoordinationQA evaluates multiple-choice answers in Environment Comprehension, Theory of Mind Reasoning, and Joint Planning using fuzzy string matching.Models receive identical prompts, are tested in three trials, and are compared with a random baseline.Source: §4.2 · p. 6

5 Discussion

LLM agents match or surpass trained RL methods in environment-focused coordination and show robustness to unseen partners, but struggle when effective play requires reasoning about partners’ beliefs and intentions. CoordinationQA and the correlation analysis further reveal weaker Theory of Mind and Joint Planning performance than Environment Comprehension.

5 Discussion

  • LLM agents match or surpass trained RL methods across Overcooked-AI layouts, while also completing CollabCapture and CollabEscape in most cases.These results are reported without game-specific training or fine-tuning; the authors note that LLM agents are significantly slower and larger than RL models, limiting real-time use at present.Source: §5 · pp. 6–7
  • Across games, Agentic Coordination performance is positively aligned with CoordinationQA scores, but the ability–performance correlations vary by game and capability.Overcooked success correlates highly with Environment Comprehension and more moderately with ToM; Hanabi success correlates strongly with both, while CollabEscape shows higher ToM correlation than CollabCapture.Source: Figure 2 · p. 7, §5 · p. 7
  • Hanabi is harder for LLM agents than environment-focused play: mistakes cost life tokens, and actions require reasoning about partners’ beliefs, intentions, and reactions to implicit communication.The Table 3 caption says RL methods obtain near-perfect scores, while even the best GPT-4-turbo agent is much weaker; removing ToM reasoning and verification further degrades performance.Source: §5 · p. 7, Table 3 · p. 7
  • Verification reduces fatal wrong-card plays, while ToM reasoning separates clue interpretation from action generation and is more useful in CollabEscape than in observable CollabCapture.The authors report that without verification, agents lose all three lives before the game ends in every trial; ToM has relatively low benefit in CollabCapture because agent positions and doors are observable.Source: §5 · p. 7
  • In Overcooked-AI proxy-human gameplay, GPT-4-turbo outperforms BC and PPO_BC and matches HSP in most cases, with results reported from either starting side.The table caption describes the comparison and role-dependent starting sides, but provides no numerical scores in the supplied passage.Source: Table 4 · p. 8, §5 · p. 8
  • On CoordinationQA, Environment Comprehension is strongest, while even the best model scores below 40% on Joint Planning and some open-source models perform worse than random.GPT-4-turbo gets more than 80% of Environment Comprehension questions correct; overall performance also drops on Theory of Mind questions.Source: §5 · p. 8, Figure 3 · p. 8
  • With unseen Hanabi partners, GPT-4-turbo scores 15 points with OBL-1 versus 13.66 in self-play, while SAD’s self-play strength does not transfer reliably to OBL partners.The authors report that SAD scores 22.00 points in self-play but suffers significant degradation with OBL-1 and OBL-4; GPT-4-turbo results use a single trial from either position due to cost and time constraints.Source: §5 · pp. 8–9, Table 5 · p. 9

6 Conclusion

The paper introduces LLM-Coordination to evaluate LLMs as agents and as coordination reasoners in pure coordination games. It compares LLM agents with multi-agent reinforcement-learning agents and evaluates environment comprehension, Theory of Mind reasoning, and joint planning.

6 Conclusion

  • The LLM-Coordination benchmark evaluates LLMs in pure coordination games through Agentic Coordination and CoordinationQA.The two settings support comparative studies of LLMs as agents and fine-grained evaluation of their coordination reasoning.Source: §6 · p. 9
  • The study compares LLM agents with existing Multi-agent Reinforcement Learning agents and discusses conditions in which LLMs thrive or fail.Source: §6 · p. 9
  • The benchmark evaluates Theory of Mind reasoning, Environment Comprehension, and Joint Planning as prerequisites for coordination.Source: §6 · p. 9

8 Limitations

The authors identify latency and compute demands, manual prompt configuration, and manual curation of CoordinationQA edge cases as limitations. They also leave game-specific prompt optimizations for future work.

8 Limitations

  • LLMs with effective coordination reasoning, such as GPT-4-turbo, have significant latency and compute demands that make them less suitable for real-time applications.Source: §8 · p. 9
  • Optimal reasoning requires careful manual configuration of initial game-description prompts, which must be formatted for the LLM agent.Source: §8 · p. 9
  • The authors defer prompt engineering and increased text generation to future work focused on improving individual-game performance rather than benchmarking.Source: §8 · p. 9
  • CoordinationQA's manually curated unambiguous edge cases can hinder scaling the benchmark to new scenarios.The authors note that curating these examples supports more reliable studies.Source: §8 · p. 9

A Overcooked Implementation Details

Overcooked-AI requires two chefs to coordinate soup preparation and delivery. Layouts impose different spatial and role-assignment demands, so players must adapt their actions and paths.

A Overcooked Implementation Details

A.1 Game and Layout Description

The implementation describes each Overcooked layout and supplies the LLM with a natural-language game prompt. Its state description converts game state into natural language, including agent locations, inventories, cooker status, and counter contents.

A.1 Game and Layout Description

  • The general game description explains Overcooked rules and objectives, while each layout description specifies facility counts, agent access across partitions, and environment shape.Source: §A.1 · p. 12
  • The agent prompt names the player and partner, includes the layout description, rules, conventions, action history, current state, teammate status, and available actions, and requests one action with a brief explanation.Source: §A.1 · p. 12

A.2 State Description

  • The state S is represented as natural-language D(S), containing necessary layout and player details equivalent to the state representation available to an RL agent.Source: §A.2 · p. 12
  • D(S) includes both agents' inventories and processed distances to points of interest; inaccessible or blocked locations are explicitly identified.Source: §A.2 · p. 12
  • D(S) reports each cooker's onion count and operating and soup states, plus the closest empty kitchen counter, filled counters, and shared-counter contents.Source: §A.2 · pp. 12–13

B Hanabi Implementation Details

The Hanabi implementation describes the game and agent interface, then supplies state information and prompts for partner reasoning and action verification.

B.1 Game Description

  • Hanabi requires teammates to build five ascending color sequences while giving clues about cards teammates can see but players cannot see in their own hands.Clues use scarce reveal tokens; an incorrect play loses a life, and losing three lives ends the game with zero points.Source: B Hanabi Implementation Details · p. 14, §B.1 · p. 14

B Hanabi Implementation Details

  • The Hanabi description is organized around the game’s objective and rules, including legal actions and end conditions.Players can reveal a color or rank, discard to regain a reveal token, or play a card; three lost lives end the game.Source: §B.1 · p. 14

B.2 State Description

  • Hanabi agents receive a structured state containing stacks, both players’ card knowledge, discards, lives, reveal tokens, and deck size.The state also lists each stack’s next playable card, which the authors precalculate because LLMs often miscount it.Source: §B.2 · p. 15

C.1 Hanabi LLM Prompt

  • The standard prompt gives the LLM the game rules and current information, asks it to choose a legal next action, and prescribes an explanation-and-action response format.It also identifies which player the model is acting as.Source: §C.1 · p. 16

C.2 Prompt for Theory of Mind Reasoning step

  • The Hanabi ToM prompt asks the model to interpret its partner’s previous action and suggest information to reveal based on the partner’s knowledge.The prompt supplies the partner’s selected action and the latest state after that action.Source: §C.2 · p. 16

C.3 Prompt for Answer Verification Step

  • An action-verification prompt checks whether a proposed move follows the rules and avoids ending the game immediately.It directs the verifier to consider the current stack, remaining lives, and reveal tokens.Source: §C.3 · p. 16

C.4 Ablation on Theory of Mind Reasoning and Verification Steps

This block reports an ablation finding, describes the CoordinationQA question types, and outlines the CollabCapture coordination scenarios.

C.4 Ablation on Theory of Mind Reasoning and Verification Steps

  • Answer Verification markedly improves Hanabi performance, with explicit Theory of Mind reasoning providing further improvement, according to the ablation caption.The supplied caption gives no numerical results.Source: Table 6 · p. 16

D.1 Environment Comprehension Questions

  • Environment Comprehension questions probe indirect inferences about layouts, current observations, and artifact counts, requiring attention to spatial and dynamic state details.The authors describe selecting salient points in scenarios to test understanding of the environment and rules.Source: §D.1 · p. 17

D.2 Theory of Mind Reasoning Questions

  • Hanabi ToM questions ask what information a partner needs or what their last action implies, while other games ask models to predict the partner’s next intended action.Source: §D.2 · p. 17

D.3 Joint Planning Questions

  • Joint Planning questions ask the model to choose the best next action for effective coordination, matching a decision it repeatedly faces as an agent.Source: §D.3 · p. 18

E.1 CollabCapture

  • CollabCapture places two agents in connected rooms to capture an adversary that moves away greedily; agents can open or close doors using distant buttons.The task has one layout and four gate-state scenarios, covering pincer coordination and cases where one agent enables or disables the other’s pursuit.Source: §E.1 · p. 19

E CollabCapture and CollabEscape

  • CollabCapture is framed as a common-payoff pursuit task: the agents share the objective of capturing the adversary, with no mixed incentives.The passage compares this shared objective with the common payoff for chefs delivering in Overcooked.Source: §E.1 · p. 19

E.2 CollabEscape

CollabEscape requires two agents to repair generators and escape an adversary, with scenarios that demand assistance and coordinated risk-taking.

E.2 CollabEscape

  • In CollabEscape, two agents must fix both generators and reach the exit before an adversary catches either player; only one needs to escape for both to win.Source: §E.2 · p. 19
  • Its two scenarios vary the agents’ starting positions and call for tactics such as luring the adversary, continuing repairs to protect a partner, or manipulating adversary movement.Figure 6 shows the CollabEscape map layout.Source: §E.2 · p. 19, Figure 6 · p. 20

Related papers

Loading 2310.03903v3…