Routing Messages by What Teammates Know for Embodied Multi-Agent Cooperation

Embodied agents built on large language models (LLMs) coordinate by exchanging natural-language messages, and each message must be delivered to some subset of teammates. Most existing methods choose these recipients from structure fixed in advance, such as roles, a communication graph, or a learned policy. However, how useful a message is to a teammate depends on what that teammate knows when the message is sent, and this changes at every step. We derive an approximation of a message's expected information gain for each recipient that depends on the recipient only through one fact: whether it already holds valid information about the goal-relevant entities the message mentions. Choosing the recipients of each message therefore reduces to tracking which agent knows about which entity, and the messages the agents exchange provide the evidence for this. We present CREAC (Cooperative Router for Embodied Agent Communication), a training-free router that infers from the team's messages which agents know about which entities, delivers each message only to the teammates for whom it is expected to be informative, and asks a teammate directly when it can no longer tell who knows. CREAC does not modify the agents' planners or prompts; it changes only which messages each agent receives. On household tasks with three to six agents and wildfire response with fifteen heterogeneous agents, CREAC outperforms broadcasting to all teammates in all ten combinations of planner, benchmark, and team size, reducing steps by up to 28% on household tasks and damage by 21–30% on wildfire response. The precision of its recipient selection increases with team size. In a user study, participants preferred teams that used CREAC over teams that broadcast every message and teams that did not communicate.