SocialGrid: A Benchmark for Planning and Social Reasoning in Embodied Multi-Agent Systems

1. Problem Statement

As Large Language Models (LLMs) evolve from passive text processors into autonomous agents, there is a critical need to evaluate their capabilities in embodied multi-agent environments. Current evaluation frameworks suffer from two main limitations:

• Siloed Assessment: Planning is typically tested in single-agent gridworlds, while social reasoning is tested in disembodied text simulations. Real-world deployment requires agents to simultaneously handle spatial navigation and complex social inference.
• Confounding Factors: In existing multi-agent benchmarks, poor spatial navigation (e.g., getting stuck, failing to reach tasks) often masks or confounds the evaluation of higher-level social reasoning. It is difficult to determine if an agent fails socially because it lacks "Theory of Mind" or simply because it cannot navigate the environment to gather the necessary evidence.

The paper addresses the gap in evaluating joint spatial planning, task execution, and adversarial social reasoning in a unified, controllable environment.

2. Methodology: SocialGrid

The authors introduce SocialGrid, an embodied multi-agent benchmark inspired by the social deduction game Among Us.

• Environment: Built on the MiniGrid framework, it features a gridworld with multiple rooms, doors, and tasks.
• Agents & Roles:
  • Crewmates: Must navigate the map, complete assigned tasks (toggling objects), and identify/eliminate hidden Impostors via voting.
  • Impostors: Must sabotage tasks, eliminate Crewmates, and deceive others to survive.
• Mechanics:
  • Embodiment: Agents operate under physical constraints (limited field of view, collision avoidance, door blocking). Actions have spatial consequences.
  • Phases: The game alternates between a Task Phase (navigation and task completion) and a Voting Phase (social deduction based on observed behavior, with no explicit verbal communication allowed to isolate behavioral reasoning).
• The Planning Oracle: A key innovation is the inclusion of an optional Planning Oracle (a symbolic A* pathfinding module).
  • Purpose: To decouple spatial planning deficits from social reasoning capabilities.
  • Levels: High (provides optimal path suggestions), Mid (provides suggestions requiring structured reasoning), and Low (no assistance).
• Evaluation Metrics:
  • Task Performance (TP): Weighted fraction of completed tasks.
  • Planning Success Rate (PSR): Fraction of assigned tasks reached.
  • Planning Performance (PP): Efficiency of the path taken vs. the optimal path.
  • Social Reasoning: Measured via Detection Accuracy (voting correctly), Trust Calibration (Brier Score of trust beliefs), and Trust Volatility.
• Failure Analysis: The system automatically categorizes agent failures into Passive (e.g., NOOP deadlock, task fixation) and Active (e.g., door spam, position ping-pong, backtracking loops).

3. Key Contributions

1. Unified Benchmark: SocialGrid is the first controllable, embodied benchmark that unifies spatial planning, task execution, and adversarial social reasoning into a single framework.
2. Quantification of Spatial Deficits: The study reveals that even the strongest open models (up to 120B parameters) struggle significantly with basic navigation and task execution in embodied settings without assistance.
3. Identification of Social Reasoning Bottlenecks: The paper demonstrates that social reasoning does not scale with model size. Agents fail to detect deception at near-random chance levels, relying on shallow heuristics rather than accumulating behavioral evidence.
4. Standardized Leaderboard: Establishment of a competitive leaderboard using Elo ratings derived from adversarial league play (Head-to-Head matchups).

4. Experimental Results

The authors evaluated 8 models (ranging from 14B to 120B parameters, including GPT-OSS-120B, Llama3.1-70B, DeepSeek-R1-70B, and Qwen3 variants).

A. Spatial Planning & Navigation (Q1)

• Severe Deficits: Without the Planning Oracle, even the strongest model (GPT-OSS-120B) achieved <60% task completion and frequently got stuck in repetitive behaviors (e.g., oscillating, backtracking).
• Oracle Impact: Providing the Planning Oracle significantly improved task completion and path efficiency, proving that navigation is a primary bottleneck for current LLMs in embodied settings.

B. Social Reasoning & Deception Detection (Q2)

• Near-Random Performance: Even with navigation assistance, agents performed at ~29.9% detection accuracy, hovering near the random baseline of 33% (for 2 impostors among 7 players).
• No Scaling Law: Unlike task performance, social reasoning accuracy did not improve with model size. A 30B model (Qwen3) often outperformed 70B+ models in league rankings.
• Failure Modes: Qualitative analysis of 64,000+ votes revealed three failure modes:
  1. Evidence Scarcity (15.7%): Agents admit lack of evidence and vote arbitrarily.
  2. Weak Heuristics (62.8%): Agents rely on superficial cues (e.g., "erratic movement") that do not correlate with actual impostor behavior.
  3. Over-trust (46.7%): Agents assign high trust scores to Impostors who successfully mimic cooperative behavior.

C. Complexity & RL (Q3, Q5)

• Complexity: As map complexity (number of rooms) increased, task performance degraded linearly, but voting accuracy remained stagnant at random chance, confirming social reasoning failures are orthogonal to navigation difficulty.
• Reinforcement Learning (RL): Fine-tuning a 4B model with PPO yielded minimal gains in spatial planning, suggesting that basic RL cannot easily overcome the fundamental reasoning bottlenecks of LLMs in these environments.

5. Significance and Implications

• Diagnostic Tool: SocialGrid provides granular metrics and automated failure analysis, allowing developers to distinguish between "can't move" (planning) and "can't think" (social reasoning) failures.
• Reality Check for Embodied AI: The results challenge the assumption that scaling LLMs will automatically solve embodied social reasoning. The paper suggests that current models lack the ability to accumulate behavioral evidence over time, relying instead on shallow, immediate heuristics.
• Safety & Trust: The findings highlight a critical limitation in deploying LLM agents in multi-agent systems where deception and trust calibration are required. The inability to detect deception at better-than-chance levels poses risks for autonomous multi-agent systems.
• Future Directions: The paper argues that solving embodied social reasoning will require architectural changes beyond simple scaling, potentially involving memory-augmented architectures or new training paradigms, rather than just larger models.

In summary, SocialGrid establishes that while LLMs are improving at text-based reasoning, they remain fundamentally weak at embodied spatial planning and adversarial social inference, with these two deficits acting as independent bottlenecks that current scaling laws fail to resolve.