Communication and Verification in LLM Agents towards Collaboration under Information Asymmetry

AI summary

Overview

Research area: Natural Language Processing / LLM agents, specifically multi-agent collaboration, communication, and human-AI interaction under information asymmetry.

Technical level: Intermediate. The paper assumes familiarity with supervised fine-tuning of LLMs, chain-of-thought prompting, and multi-agent setups, but the core ideas and the game environment are explained clearly enough for readers with a general NLP background.

Scope: The paper studies how two LLM agents with complementary, partial information can collaborate on an adapted Einstein Puzzle tabletop task, and whether environment-derived verification and different communication abilities improve their joint performance and interaction quality.

What This Paper Is About

Most LLM agent research focuses on single agents acting on instructions, and the work that does study multi-agent systems usually assumes information transparency, one-way communication, or asymmetric role assignments. This paper targets the harder case of symmetric collaborative roles where each agent holds only part of the necessary knowledge and cannot see what the partner knows.

The goal is to test how communication abilities (asking, sharing, both, or neither) and a lightweight, training-free verifier that reads feedback from the environment affect both task success and the quality of collaborative behavior, including with human partners.

Key Contributions

1. A collaborative tabletop environment built from Einstein Puzzles. Two agents sit on opposite sides of a table, each with partial constraints that jointly and uniquely determine a goal placement (C1 ∪ C2 = C), and neither can solve the task alone. The environment supports object placement, information sharing, and information seeking as moves.

2. A systematic study of four communicative action spaces (Provide Only, Seek Only, Provide & Seek, No Information Exchange) using supervised fine-tuning of Meta-Llama-3-8B-Instruct, Llama3.1-8B-Instruct, and Qwen2.5-7B-Instruct, plus closed-source GPT-4o evaluated via API.

3. A training-free, environment-based reasoning verifier that checks physical affordances, communication validity, and known constraints, and uses a graph expansion algorithm over object and bin nodes to infer new constraints. At each step it samples 4 candidate responses (temperature=0.2, top-p=0.9) and selects the first valid one.

4. A human study with 30 participants (32 recruited, 2 excluded) using a within-participant design, testing four model variants against three game sizes (4, 6, and 8 objects), with both quantitative metrics and qualitative questions about usefulness, responsiveness, and confusion.

Main Findings

• Bidirectional communication works best in the strongest setting. In the Llama3.1-8B CoT configuration, Provide & Seek achieves the highest success rate among action spaces — 58.67% without the verifier and 89.33% with it. The paper notes StepR rankings are less consistent, so higher success does not always mean greater step efficiency.

• Seeking generally beats providing. Across matched settings, Information Seeking Only tends to outperform Information Providing Only, which the authors attribute to targeted queries requesting exactly the missing information, whereas unprompted sharing often adds redundant or irrelevant constraints.

• Mismatched communication capabilities hurt. In the four asymmetric pairings tested, performance consistently drops. Provide & Seek paired with Provide Only reaches 67.33% success, Provide Only paired with Seek Only reaches only 41.00%, and structural mismatches where one agent cannot initiate or respond force random guessing.

• The verifier helps broadly. Holding action space and reasoning setting fixed, the environment-based verifier produces absolute success-rate gains of 10 to 40 percentage points across action spaces — for example, GPT-4o CoT goes from 51.00% to 80.00%, and Llama3-8B CoT from 29.67% to 70.00%.

• High success without communication can be misleading. Llama3-8B with No Information Exchange reaches 81.33% success without a verifier (97.67% with it), and Llama3.1-8B reaches 84.67% (94.33% with it). Qwen2.5-7B does not show the same effect (34.67% to 61.33%), suggesting the phenomenon is model-specific. Error analysis shows rule-understanding error rates are broadly similar across action spaces even when success differs, so the high No-Communication success comes from repeated manipulation attempts and the absence of communication errors rather than stronger reasoning.

• Communication is often inefficient. Under no verifier, 59.86% of information-providing actions under Provide & Seek and 79.35% under Provide Only are labeled redundant. The verifier reduces these to 39.44% and 69.37% respectively.

• The verifier reduces errors and action counts. Reductions are particularly pronounced for Wrong Rule Understanding, which directly reflects the verifier's intended role. In the Provide & Seek configuration without a verifier, Wrong Rule Understanding accounts for 28.22% of all 6,704 steps and 38.15% of the 4,959 move actions.

• Some generalization to unseen game sizes. Models fine-tuned only on 4–6 object games were evaluated on unseen 7 and 8 object games, where absolute performance drops but the ordering across action spaces largely holds; the verifier raises success from 31.00% to 76.00% under Provide & Seek on those held-out sizes.

• Humans succeed similarly but get confused more without communication. In the human study, Provide & Seek reaches 92.22% success and None reaches 91.11%, with similar step counts (18.99 vs. 18.76, p = .73). But the None agent nearly doubles rejected placement attempts (3.64 vs. 1.92 per game, p < .001), while the Provide & Seek agent uses about 1.9 communicative acts per game. Participants report the most confusion in the None condition and the least with Provide & Seek (p = .045), and rate Provide & Seek information as significantly more useful than None (p = .020). Participants attempted to communicate at the same rate in the None condition as in Provide & Seek (3.0 acts per game, p = .94) despite never receiving a response.

• Provide Only is the weakest human-collaboration variant, with 77.78% success overall and 46.7% success on the hardest 8-object games. The authors suggest that useful providing is harder to learn than useful seeking, because providing requires inferring what the partner already knows and when to volunteer information.

Methodology in Plain English

The researchers turned Einstein Puzzles into a two-player tabletop game. A target placement of objects into bins is described by a minimal set of pairwise constraints (same bin, same column, same row, or same diagonal) plus one grounding constraint that fixes a single object to a bin. This constraint set is split between the two players so that each has only half the information. The table is divided into a region in front of each player and a shared center area, so each player can only reach certain objects and four destination bins.

Each turn counts as a move, whether it is placing an object, sharing information, asking for information, or passing. Because move count is the efficiency measure, players are pushed to communicate concisely. The team ran four action-space conditions: Provide Only, Seek Only, Provide & Seek, and No Information Exchange.

To train the agents, they built a planner that does breadth-first search from a single player's perspective, tracking the player's knowledge and communication history, and generating both optimal and near-optimal trajectories. Games with 4, 5, and 6 objects yielded 250, 500, and 500 games respectively; five trajectories per game were generated, and 1,000 trajectories averaging about 10 steps each were sampled, producing roughly 10,000 chat-formatted training samples. Reasoning traces were generated with GPT-4o. Evaluation used 300 unseen games (100 per object count), with and without chain-of-thought.

For verification, rather than training a separate reward or value model, they let the environment do the checking. The verifier tests whether an action respects physical affordances, whether shared information is redundant, and whether an action is consistent with constraints the agent has inferred. A graph expansion algorithm treats objects and bins as nodes and constraints as edges, iteratively adding inferred constraints through transitivity (for example, if A and B are on the same row, and B and C are on the same row, then A and C are on the same row). At inference, the model samples 4 candidate responses (temperature=0.2, top-p=0.9) and the verifier selects the first valid one.

Metrics were Success Rate (SR) and subgoal success rate (Sub.R) at first attempt, Step Ratio (StepR, executed steps divided by optimal steps), and correction rate (Corr.R) when a verifier was in use, all with standard errors reported. The human study used a web interface, a within-participant design crossing three game configurations with four model variants, and post-game questions about usefulness, responsiveness, and confusion. A full error taxonomy was developed for the error analysis.

Why This Matters

Impact on research. The paper's central claim is a dissociation: task success alone does not capture behavioral reliability or interaction quality. Agents with no communication can score high by brute-force manipulation while making more rule-inconsistent and rejected actions, and humans notice the difference even when step counts are identical. This argues for evaluating collaborative agents on communication behavior, not just outcomes, and it offers a training-free verification mechanism that needs no reward engineering or extra model training.

Real-world applications:

• Human-AI assistants in shared physical or spatial tasks, such as collaborative robotics or tabletop manipulation, where an agent must ask for and share partial knowledge rather than guess.
• Multi-agent workflow automation, where different agents hold different fragments of context and must coordinate without a shared full picture.
• Web agents and tool-use pipelines, where verifying proposed actions against environment feedback could filter invalid steps before execution.
• Interactive tutoring or assistive systems, where perceived clarity and responsiveness matter as much as raw task completion.

Industry relevance. The finding that mismatched communication protocols sharply degrade performance is directly relevant to deploying heterogeneous agent fleets, where models from different vendors or with different capabilities must interoperate. The environment-based verifier is presented as lightweight and broadly applicable, which matters for cost-sensitive deployments that cannot afford a separate trained verifier model. The human study's result that users keep trying to communicate with agents that cannot respond signals a concrete product gap.

Future Directions

• Extending to more diverse environments and richer task structures. The paper's generalization test is limited to unseen game sizes (7 and 8 objects) with models fine-tuned on 4–6 objects; the limits of the environment-based verifier across other simulated environments are not established.

• Understanding why non-communicative success is model-specific. Llama variants exploit memorized high-probability transition patterns while Qwen2.5-7B does not; the paper calls this model-specific rather than intrinsic to the environment, leaving the underlying cause unexplained.

• Improving information-providing behavior. Provide Only is the weakest variant in both agent and human studies, and the authors suggest useful providing requires modeling what the partner already knows and when to volunteer it — a capability that appears harder to learn than seeking.

• Aligning communication protocols across heterogeneous agents. Since mismatched action spaces consistently degrade performance and sometimes force random guessing, designing shared or interoperable communication conventions for multi-agent systems remains open.

Target Audience

This paper is most useful for researchers and practitioners working on LLM agents, multi-agent coordination, and human-AI collaboration, especially those interested in information asymmetry, communication protocols, or inference-time verification without additional training. It is also relevant to HCI researchers studying how users perceive agent behavior, and to applied teams building collaborative agent systems that must work alongside people or with other agents of differing capabilities. Readers should be comfortable with LLM fine-tuning, prompting strategies, and basic constraint-satisfaction concepts.

Authors’ abstract

While Large Language Model (LLM) agents are often approached from the angle of action planning/generation to accomplish a goal (e.g., given by language descriptions), their abilities to collaborate with each other to achieve a joint goal are not well explored. To address this limitation, this paper studies LLM agents in task collaboration, particularly under the condition of information asymmetry, where agents have disparities in their knowledge and skills and need to work together to complete a shared task. We extend Einstein Puzzles, a classical symbolic puzzle, to a table-top game. In this game, two LLM agents must reason, communicate, and act to satisfy spatial and relational constraints required to solve the puzzle. We apply a fine-tuning-plus-verifier framework in which LLM agents are equipped with various communication strategies and verification signals from the environment. Empirical results highlight the critical importance of aligned communication, especially when agents possess both information-seeking and -providing capabilities. Interestingly, agents without communication can still achieve high task performance; however, further analysis reveals a lack of true rule understanding and lower trust from human evaluators. Instead, by integrating an environment-based verifier, we enhance agents' ability to comprehend task rules and complete tasks, promoting both safer and more interpretable collaboration in AI systems. https://github.com/Roihn/EinsteinPuzzles