Abstract
While Large Language Model (LLM) agents are often approached from the angleof action planning/generation to accomplish a goal (e.g., given by languagedescriptions), their abilities to collaborate with each other to achieve ajoint goal are not well explored. To address this limitation, this paperstudies LLM agents in task collaboration, particularly under the condition ofinformation asymmetry, where agents have disparities in their knowledge andskills and need to work together to complete a shared task. We extend EinsteinPuzzles, a classical symbolic puzzle, to a table-top game. In this game, twoLLM agents must reason, communicate, and act to satisfy spatial and relationalconstraints required to solve the puzzle. We apply a fine-tuning-plus-verifierframework in which LLM agents are equipped with various communicationstrategies and verification signals from the environment. Empirical resultshighlight the critical importance of aligned communication, especially whenagents possess both information-seeking and -providing capabilities.Interestingly, agents without communication can still achieve high taskperformance; however, further analysis reveals a lack of true ruleunderstanding and lower trust from human evaluators. Instead, by integrating anenvironment-based verifier, we enhance agents' ability to comprehend task rulesand complete tasks, promoting both safer and more interpretable collaborationin AI systems. https://github.com/Roihn/EinsteinPuzzles