Skip to content

AsymPuzl: An Asymmetric Puzzle for multi-agent cooperation

🕒 Published (v1): 2025-12-03 05:42 UTC · Source: Arxiv · Venue: NEURIPS · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

AsymPuzl is a controlled two-agent puzzle environment where each agent holds complementary partial information (one knows positions/shapes, the other knows shapes/colors) and must cooperate via message-passing to solve a position-shape-color matching task. The benchmark isolates communication under information asymmetry, revealing sharp capability gaps across LLMs and non-obvious feedback design effects. GPT-5 and Claude-4.0 achieve 100% success by sharing all information in two turns; smaller models fail to cooperate effectively.

Problem

Existing LLM multi-agent benchmarks emphasize open-ended role-play and lack controlled settings for evaluating communication strategies under partial information. No prior testbed allows systematic manipulation of task difficulty, feedback granularity, or information asymmetry in a minimal, confound-free multi-agent scenario.

Method

Two agents (Alice and Bob) are assigned complementary views of an N-position symbolic puzzle: Alice sees correct position-shape pairs (unknown colors); Bob sees correct shape-color pairs (unknown positions). Agents exchange messages in alternating turns and submit JSON-formatted actions to update their working hypotheses. The environment re-injects full state (instructions, original cues, current hypothesis, message history, feedback) at each turn. Six feedback modes are evaluated: no feedback, own (solved/unsolved per agent), own-detailed (which positions are wrong), joint (overall solved status), both (each agent's solved status), and both-detailed (positional errors for both agents). Puzzles scale from N=3 to N=20; max turns = 2N. Experiments run over 30 seeds at temperature 0.0 with LangChain + vLLM for open-source models.

Key Contributions

  • AsymPuzl environment: a minimal, reproducible two-agent cooperative puzzle testbed with controllable difficulty (puzzle size) and feedback granularity.
  • Empirical analysis across 7 LLMs (GPT-3.5-turbo, GPT-4o, GPT-5, OSS-120B, Llama 3.2-11B, Claude-3.5, Claude-4.0) showing stark performance stratification.
  • Finding that simple self-feedback improves success rates while detailed joint feedback (other agent's wrong positions) can hurt performance due to information overload without context.
  • Characterization of three failure modes: non-cooperation (ignoring partner messages), over-correction (repeated hypothesis rewrites), and miscommunication (false assumptions about shared visibility).

Results

  • GPT-5 and Claude-4.0: 100% success on 5-piece puzzles across all six feedback modes; nearly optimal action count (~1 modification per position); solve in 2 turns by sharing all information.
  • OSS-120B: 53.3% (no feedback) → 100.0% (own-detailed feedback) on 5-piece puzzles.
  • GPT-4o: 43.3% (no feedback) → 63.3% (own-detailed) but drops to 40.0% under joint feedback; degrades to 16.7% at N=20.
  • Claude-3.5: 66.7% (no feedback) → 86.7% (own-detailed) but collapses to 36.7% under both-detailed feedback; degrades to 16.7% at N=20.
  • GPT-3.5-turbo and Llama 3.2-11B: 0% across all feedback modes and puzzle sizes.
  • Single-agent baseline (full information): most models achieve 100% across all puzzle sizes, confirming failures in two-agent setup stem from multi-agent coordination, not puzzle difficulty.

Limitations

  • State is re-injected each turn (original cues, full history), so agents do not exercise persistent memory; this differs from fully autonomous agent settings.
  • History length is limited to 1 (agent sees only its previous message and the partner's latest), constraining communication continuity.
  • Puzzle structure is noise-free and unambiguous; noisy/ambiguous cues (e.g., extra shapes or colors) are left for future work.
  • Only two agents evaluated; scaling to three or more agents is not explored.
  • No communication bandwidth constraints (token limits per message) are imposed.

Relevance to Agentic AI / LLM Agents

AsymPuzl provides a clean, reproducible testbed for diagnosing LLM communication strategies in multi-agent cooperation — a core capability for agentic systems that must coordinate across partial-information contexts. The finding that frontier models (GPT-5, Claude-4.0) converge to near-optimal full-information sharing while mid-tier models exhibit miscommunication or over-correction has direct implications for designing reliable multi-agent pipelines. The non-monotonic effect of feedback granularity (detailed joint feedback hurts) is a practically important signal for prompt and protocol engineering in LLM-MAS. This work complements role-play-centric benchmarks by offering controlled measurement of a specific coordination failure mode.