PaperlayerView exact revision on arXiv

Source-linked AI summary

Communication and Verification in LLM Agents towards Collaboration under Information Asymmetry

Run Peng, Ziqiao Ma, Amy Pang, Sikai Li, Zhang Xi-Jia, Yingzhuo Yu, Cristian-Paul Bara, Joyce Chai

arXiv:2510.25595v2cs.CLcs.AI

TL;DR

LLM agents’ ability to collaborate under information asymmetry remains underexplored, despite its relevance to agents working together on shared tasks. The paper adapts Einstein Puzzles into a tabletop game and studies communication strategies alongside environment-based verification. Agents with both information-seeking and -providing abilities collaborate most effectively in most cases, while task success alone does not capture rule compliance or interaction quality.

  • Problem

    LLM agents’ collaboration toward shared goals is less explored than action planning, particularly when agents have different knowledge and must coordinate.

    Source: §1 · p. 1

  • Method

    The authors adapt Einstein Puzzles into a tabletop task with split destination constraints and test fine-tuned agents using different communication abilities and an environment-based verifier.

    Source: §1 · pp. 1–2, §3.1 · pp. 3–4

  • Results

    Agents that can both seek and provide information collaborate most effectively in most cases, and verifier assistance yields absolute SR gains of 10 to 40 percentage points.

    Source: §5.2 · p. 7, §6 · p. 10

  • Takeaways & Limitations

    Task success alone does not capture behavioral reliability or interaction quality, since non-communicative agents can succeed while showing more rule-inconsistent and rejected actions and eliciting greater confusion.

    Source: §6 · p. 10

    Evidence for generalization is limited to one task family; the verifier is evaluated on held-out game sizes, not other logic games or more realistic collaborative settings.

    Source: G Limitations · p. 20

Abstract

from arXiv · show

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

1 Introduction

The paper examines LLM collaboration under information asymmetry, a capability less explored than individual action planning. It adapts Einstein Puzzles into a collaborative tabletop task and studies communication strategies and environment-based verification.

1 Introduction

  • LLM agents’ ability to collaborate toward a shared goal, especially under information asymmetry, remains underexplored compared with action planning and goal completion.The paper frames coordination under asymmetric knowledge as important for agents acting as collaborators or human proxies.Source: §1 · p. 1
  • The authors adapt Einstein Puzzles into a tabletop task where two agents use spatial and relational constraints despite having partial, asymmetric information.The agents must infer the goal configuration and place the objects accordingly.Source: §1 · p. 1, Figure 1 · p. 2
  • A fine-tuning-plus-verifier framework tests agents with different abilities to ask for or share information and uses environment signals to check actions and communication.The described checks cover physical affordances, communication validity, and consistency with known constraints.Source: §1 · p. 2
  • Communication effects depend on model and reasoning configuration; in the strongest Llama 3.1 setting, Provide & Seek has the highest success rate, while verifier assistance improves task performance and reduces rule-inconsistent and redundant actions.Human participants report greater confusion with non-communicative agents than with fully communicative agents, despite similar task success and step counts.Source: §1 · p. 2

2 Related work

Prior LLM multi-agent work spans collaborative tasks, but much of it assumes transparent information, one-way communication, or asymmetric roles. This paper studies symmetric collaborative roles under information asymmetry and proposes environment feedback as an alternative verification signal.

2 Related work

  • LLM multi-agent systems have been applied to collaborative coding, social simulation, and problem-solving, building on longstanding work in multi-agent coordination and communication.The cited work also includes human-AI collaboration.Source: §2 · p. 2
  • Most cited LLM collaboration work uses information transparency, one-way communication, or information asymmetry tied to asymmetric role assignments, unlike this paper’s symmetric collaborative roles.The paper also includes a human study of interaction.Source: §2 · p. 2
  • Where common verification approaches use a separate value model, this work uses objective, fine-grained environmental feedback for training-free, compute-efficient verification in interactive tasks.The passage contrasts methods with and without further training.Source: §2 · p. 3

3 Collaboration Under Information Asymmetry

The paper turns Einstein Puzzles into a distributed constraint-satisfaction game: two agents hold incomplete information about object destinations and must coordinate to place them. It compares communication action spaces and fine-tunes models on generated game trajectories.

3.1 Understanding Einstein Puzzles on the tabletop setup

  • Einstein Puzzles becomes a collaborative placement game in which agents hold different pieces of destination information and do not know what their partner knows.Neither agent can complete the task independently, but together they possess the necessary constraints.Source: §3.1 · pp. 3–4
  • The task is modeled as distributed constraint satisfaction, with pairwise object and object-to-bin constraints specifying the goal configuration.The listed pairwise relations include same bin, same column, same row, and same diagonal.Source: §3.1 · p. 3
  • The minimal constraint set uniquely specifies the goal, while the task’s moves include object placement, information exchange, or passing and are counted toward completion.A further starting constraint grounds one object to a specific bin.Source: §3.1 · p. 4

3.2 Information Providing & Seeking

  • The study compares providing-only, seeking-only, both communication actions, and no information exchange, where agents may have to guess destinations they cannot deduce.Seeking-only agents may share a constraint only after a partner asks about an object involved in it.Source: §3.2 · p. 4
  • The authors fine-tune Llama and Qwen models on 1,000 generated trajectories, then evaluate on 300 unseen games across three object counts.The training trajectories cover games with 4, 5, and 6 objects; evaluation uses 100 games per object count.Source: §3.2 · p. 4

4 Environment-based Verifier

The verifier uses environment feedback to assess proposed actions without training a dedicated verifier. Its reasoning component expands a symbolic constraint graph to infer additional constraints and screen actions against current knowledge.

4 Environment-based Verifier

  • Rather than training a dedicated verifier, the approach uses environment-provided feedback during inference as a lightweight verification source.The paper evaluates this training-free approach for collaborative reasoning under information asymmetry.Source: §4 · p. 5
  • The verifier checks actions against game rules and prior communication, then iteratively expands an object-and-bin constraint graph using transitivity to infer new constraints.The inferred constraints help assess whether a proposed action aligns with current knowledge and avoid unnecessary trials.Source: §4 · p. 5

5 Experiments and Results

The experiments compare communication configurations, verifier assistance, mismatched agent capabilities, and human preferences in collaborative puzzle-solving. Results favor full bidirectional communication and verifier assistance, while showing that high task success can mask weak rule understanding and differences in interaction quality.

5.1 Experiment Setup

  • Experiments tested self-play across 4–6 objects, verifier-filtered action selection, mismatched pairings, and human collaboration across 4, 6, and 8 objects.The verifier setup sampled four candidate responses per decision; human participants completed 12 games each.Source: §5.1 · pp. 5–6

5.2 Result Analysis

  • Above 81% success for some Llama variants without communication coexists with similar rule-understanding error rates across action spaces.The paper attributes None's success to repeated manipulation attempts and random guessing rather than stronger task reasoning.Source: §5.2 · pp. 6, 8
  • 10–40 percentage-point absolute SR gains result from adding the reasoning verifier across action spaces; Table 1 compares models with and without verifier assistance.The comparison holds communicative action space and reasoning setting fixed.Source: §5.2 · p. 7, Table 1 · p. 7
  • In the strongest Llama 3.1-8B CoT setting, Provide & Seek has the highest Success Rate, and verifier assistance further improves performance and rule compliance.Across matched settings, seeking generally outperforms providing alone; verifier assistance also reduces errors and total actions.Source: §5.2 · pp. 6, 8
  • Mismatched communication capabilities consistently reduce performance; some pairings force agents to rely on random guessing.For example, a Seek Only agent cannot proactively share with a Provide Only partner that cannot ask questions.Source: §5.2 · p. 8, Table 3 · p. 9
  • 92.2% vs 91.1% SR for Provide & Seek vs None; Provide Only reached 77.8%, while their step counts were similar (18.99 vs 18.76).None made nearly twice as many rejected placement attempts as Provide & Seek: 3.64 vs 1.92 per game.Source: §5.2 · pp. 8–9, Table 4 · p. 9
  • Participants rated Provide & Seek information as more useful than None, found Seek Only better at using shared information, and reported least confusion with Provide & Seek.The None condition drew communication attempts at the same rate as Provide & Seek despite never replying.Source: §5.2 · pp. 9–10, Figure 2 · p. 9

6 Conclusion

The conclusion frames collaboration under asymmetric knowledge and reachability as a joint task, and argues that task success alone misses behavioral reliability and interaction quality. Its supplementary materials include a full gameplay example and additional technical and evaluation details.

6 Conclusion

  • Agents without communication can achieve high task success through repeated physical attempts, yet show more rule-inconsistent and rejected actions and confuse human participants despite similar step counts.The environment-based verifier improves constraint-consistent action selection and task completion using signals available directly from the environment.Source: §6 · p. 10

Appendix

  • The appendix includes data-generation details, verifier ablations, out-of-distribution evaluations, experiment and ethics information, limitations, an error taxonomy, and human-study materials.It also includes prompts used across training, evaluation, and reasoning-trace generation.Source: Appendix · p. 15

A Example of Game Play

  • The gameplay example illustrates turn-taking, decision-making, and communication during a complete puzzle session.The ask action is absent in this relatively simple example and is used more often with more objects or specific information needs.Source: A Example of Game Play · p. 15

B Data Generation

The data-generation planner searches from each player's limited perspective, maintaining knowledge from communication and board state to select valid actions. The demonstrations combine optimal and near-optimal trajectories to represent alternative communication strategies.

B.1 Perspective Taking

  • The planner uses breadth-first search over action sequences while tracking each player's constraints, communication history, and object positions.It selects actions consistent with the player's evolving knowledge, including sharing uncommunicated constraints or asking about unknown objects.Source: §B.1 · p. 15
  • The game playthrough depicts alternating turns in which players make physical moves, share information, or ask questions until all objects are placed.The illustration introduces the actions and rationales used in a full session.Source: Figure 3 · p. 16
  • The planner uses inferred knowledge to avoid redundant questions and select placements when an object's goal is known, while tracking prior sharing to prevent repeated information.The same inferred knowledge is used by the reasoning verifier.Source: §B.1 · p. 16
  • Figure 4 depicts environment feedback for action affordance, communication, and strategy as signals that can verify agents' decisions.The illustration uses the same game setup as Figure 1.Source: Figure 4 · p. 17
  • When no valid move remains, the planner can add a pass, but prunes trajectories ending in consecutive passes to avoid stalling.In settings with no communication or unidirectional information flow, it may guess reachable object placements only after exhausting valid actions.Source: §B.1 · p. 17

B.2 Optimal And Near-Optimal Trajectories

  • The dataset combines optimal and near-optimal trajectories one or two steps longer, ensuring both information-providing and information-seeking actions are represented.Optimal-only demonstrations would overrepresent unprompted sharing because it often yields shorter solutions.Source: §B.2 · p. 17
  • For random-guessing settings, demonstrations also include trajectories that try multiple bins because first-try correct guesses provide little guidance for robust guessing.Several fine-tuned models learned this multi-bin strategy.Source: §B.2 · p. 17

C Ablation on Environment-Based Verifiers

The verifier design separates checks of physical action feasibility and communication validity from a reasoning verifier that also uses inferred knowledge. The reasoning verifier performs best in the described design but is least portable because it relies on a domain-specific symbolic constraint graph.

C.1 Verifier Design

  • The affordance verifier checks whether physical actions are executable, while the communication verifier identifies redundant or uninformative exchanges.Examples include unreachable objects or bins, already-known information, repeated constraints, and questions about placed objects.Source: §C.1 · pp. 17–18
  • The reasoning verifier builds on affordance and communication checks and extends coverage through inferred knowledge.The table is described as comparing success rate and step ratio across verifier settings, but supplied text gives no cell values.Source: §C.1 · p. 18, Table 5 · p. 18
  • The reasoning verifier performs best but is least portable because adapting its explicit symbolic constraint graph requires domain-tailored algorithms.Affordance checks are broadly available, and communication checks are accessible when the task includes communication.Source: §C.1 · p. 18

C.2 Ablation Study

Environment-based affordance and communication verifiers improve task success through feedback on physical preconditions and interaction history. The approach requires no additional training or computational overhead.

C.2 Ablation Study

  • The affordance verifier improves success rates by 2–7%, while the communication verifier contributes up to a 9% increase in task completion success.The affordance check evaluates physical action preconditions; the communication check filters redundant or uninformative exchanges.Source: §C.2 · p. 18
  • The verifiers use only environmental and interaction-history feedback, with no additional training or computational overhead.The authors characterize environment feedback as a lightweight, model-free source of verification signals that can guide agent behavior.Source: §C.2 · p. 18

D Out-of-Distribution Generalization

On held-out game sizes, the relative ordering of communicative action spaces remains largely unchanged, and the reasoning verifier continues to yield substantial gains. The appendix also reports model configuration, fine-tuning, deployment, and licensing details.

D Out-of-Distribution Generalization

  • To test dependence on fine-tuning game sizes, all models were fine-tuned exclusively on 4-, 5-, and 6-object games and evaluated on held-out games with 7 and 8 objects; absolute performance decreased as object count increased.Source: D Out-of-Distribution Generalization · p. 18, Table 6 · p. 19
  • The relative ordering of communicative action spaces remains largely unchanged on held-out game sizes, and the reasoning verifier continues to yield substantial gains.Absolute performance decreases as object counts increase; Table 6 includes held-out sizes 7 and 8 and in-distribution results for reference.Source: D Out-of-Distribution Generalization · pp. 18–19, Table 6 · p. 19

E.1 Model Configuration, Fine-tuning and Deployment

  • GPT-4o used version GPT-4o-20241120; fine-tuning used LoRA with rank 32, batch size 128, learning rate 2e-4, cosine decay, and one epoch.Training took approximately 30 minutes on four A40 GPUs; evaluation used PeFT, while human-study inference used vLLM.Source: §E.1 · p. 19
  • The implementation follows the Llama3.1, Qwen2.5, and GPT-4o license requirements and is licensed under MIT.Source: §E.1 · p. 19

E.2 Human Evaluation Setup

The human evaluation compared four communication configurations across game sizes in a counterbalanced, within-participant study. The paper also reports ethics review and data-protection practices.

E.2 Human Evaluation Setup

  • Thirty-two participants played all four model variants across games with 4, 6, and 8 objects, yielding 360 sessions after two participants were excluded.Each participant played 12 games; variant and game order were randomized and counterbalanced, and participants were not told which model variant they faced.Source: §E.2 · p. 19
  • Participants received a tutorial, then played sequential games with explicit constraints and could give up; a 30- or 40-step limit applied across evaluations.The 40-step limit applied to games with 8 objects.Source: §E.2 · p. 20

F Code of Ethics

  • The IRB considered the project exempt from ongoing review; the study used non-personal information, maintained confidentiality, and did not plan public release of the data.The research team controlled the game setting and tasks to minimize potential safety concerns.Source: F Code of Ethics · p. 20

G Limitations

The paper limits its verifier's practical scope to structured-feedback simulations and qualifies its generalization evidence as confined to one task family. It also notes that transfer beyond the current symbolic verifier remains untested.

G Limitations

  • Environment-based verification assumes invalid actions can be tried without irreversible consequences, so the current approach is best suited to simulated environments with structured feedback.Physical settings would require stronger perception and a more accurate understanding of environment dynamics.Source: G Limitations · p. 20
  • Generalization evidence covers only one task family; the reasoning verifier expands an explicit symbolic constraint graph, and transfer to other domains remains future work.The paper reports held-out game-size results but does not evaluate other logic games or more realistic collaborative settings.Source: G Limitations · p. 20

H Error Taxonomy

This section defines a rule-based taxonomy for classifying agent errors and documents the human-study interface and prompts used to train and evaluate agents. It describes how evaluation and fine-tuning prompts differ in their guidance and rationales, vary by action-space configuration, and address uncertainty or suboptimal actions.

H Error Taxonomy

  • The error taxonomy groups failures into format following, physical understanding, communication, and task reasoning, with labels assigned deterministically from environment logs.Scripts were manually checked against sampled trajectories; examples include invalid actions, unreachable-bin moves, communication failures, and incorrect rule understanding.Source: H Error Taxonomy · pp. 20–21

I Study Interface Used for the Reported Human Study

  • The study’s web platform supported the human-study sessions and presented the game and post-game questionnaire.The reported human-study results were collected with this platform.Source: I Study Interface Used for the… · p. 21

I.1 Onboarding Tutorial

  • Before play, participants completed an eight-step tutorial covering the goal, board geometry and reachability, knowledge types, actions, termination, and turn budget.Each session comprised 12 games, with 30–40 actions allowed per game depending on the number of objects.Source: §I.1 · p. 21, Figure 5 · p. 22, Figure 6 · p. 23

I.2 Gameplay Interface

  • The gameplay view combined a reachability-marked board, action controls, a panel of held facts, and a turn-by-turn history log.Invalid moves remained possible and consumed a turn, preserving the task’s cost structure.Source: §I.2 · pp. 21–22, Figure 7 · p. 24

I.3 Post-Game Questionnaire

  • After each game, participants rated bot usefulness, use of shared information, and confusion on a five-point Likert scale.An instructed-response attention check flagged sessions for review, and participants had to complete all items before proceeding.Source: §I.3 · p. 22, Figure 8 · p. 25

J.1 Prompts for Model Training & Evaluation

  • Training and evaluation prompts covered four action-space configurations, with and without chain-of-thought reasoning, and varied permitted actions and examples accordingly.CoT prompts requested reasoning and action tags, whereas prompts without CoT requested only an action.Source: §J.1 · pp. 23–24

J.2 Prompts for Evaluation with GPT4o

  • GPT-4o evaluation used more detailed explanations and guidance because preliminary tests indicated it struggled to understand the game setting with the same prompts.The additional guidance was intended to make the comparison relatively fair.Source: §J.2 · p. 28
  • Evaluation prompts require agents to follow access and knowledge-sharing rules, reason before acting, and avoid repeating moves flagged as incorrect in the action history.They also treat a block already placed in a bin as correctly placed, because the game prevents incorrect placements.Source: §J.2 · pp. 28–29

J.3 Prompts for Generating Reasoning Traces with GPT4o for Model Fine-tuning

  • For fine-tuning, a planner generates a solution, then GPT-4o receives each game state and suggested action and writes a first-person rationale for taking it.The process uses distinct system prompts for each of the four action-space configurations while keeping the user prompt consistent.Source: §J.3 · pp. 29–30
  • Trace-generation instructions ask for concise explanations of the given action even when it is not the best move, and require uncertain or lucky guesses to be identified as guesses.The prompts also distinguish information-sharing capabilities: Seeking-Only agents cannot initiate sharing and must wait to be asked.Source: §J.3 · pp. 30, 32

Related papers

Loading 2510.25595v2…