cs.MAOct 26, 2026

The Inbox as a Coordination Primitive for LLM Agent Societies

Authors: Karthik Sreedhar, Leo Yuan, Pradyumna Chari, Ramesh Raskar

Organizations: MIT Media Lab, Cambridge, USA

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Language-model agents increasingly coordinate in large groups, and current agent protocols focus on delivering messages. For these agents, however, the scarce resource is not delivery but reading: every message costs tokens, and the context is finite. Current infrastructure works by push: the sender decides when a message enters the recipient's context, so the recipient reads in arrival order and drops the oldest messages once its context is full. We study the alternative, pull, in which messages wait in an inbox outside the context and the recipient's own rules decide what it reads and keeps. We argue that the inbox is a coordination primitive: each agent sets its rules privately, and those rules decide whether other agents' requests reach it. In simulated societies of up to 16,000 agents, with every decision an LLM judgment, we report three findings. First, push fails as an agent takes part in more coordination at once: an agent leading 20 negotiations with a full memory proposes options already rejected 97% of the time, because it has dropped the oldest replies. Second, an inbox is necessary under heavy, noisy traffic. Where first come, first read misses every request, an inbox that first reads messages carrying a refundable deposit still finds about 60% of the agents a request needs, at every size from 1,000 to 16,000. On a real email network, losses compound: when half the agents adopt such an inbox, forwarded search recovers only 5% of full adoption, against 42% for one-hop search. Third, an inbox comprises four decisions (what to read, what to keep, what a sender pays, and what a reply may say), and the best rule for each depends on the traffic and the agent's role. Multi-agent coordination under load requires an inbox layer designed for the traffic each agent receives.

Figures & tables

Figure 1. Push and pull. Under push, every message enters the context in arrival order and the oldest is forgotten when it fills. Under pull, messages wait in an inbox: a reading rule picks what is read, a memory rule what stays, and only judgment calls the model. Two-row diagram. Top row, push: a request, a reply, a follow-up and a spam message go straight into the recipient's context in arrival order, and the oldest are dropped when the context is full. Bottom row, pull: the same four messages wait in an inbox. A reading rule picks which are read, a memory rule picks which conversations stay in context, and only the judgment step calls the model. Headline numbers from Experiments 1 to 3 appear under each row.
Reading RiR_{i} : what to read
First come, first readRead in arrival order
Check in batchesWait several steps, then clear the queue
Sort into foldersPrioritize by category; ignore junk
Newest firstRead newest messages first
Paid mail firstRead messages with stakes first
Closest matchRank by similarity to published interests
Table 1. The four inbox decisions and the rules compared. Push uses first come, first read; forget the oldest; no stake; and unrestricted replies.
ExperimentConditions comparedMeasures
1. Concurrent negotiations2, 5, 10, 20 meetings; memory rules at 375, 750, 1,500 tokens; full-memory and best-case controls; five invitees, two rounds, five societiesRepeated proposals; tokens
2.1 Team size2, 5, 8, 12 invitees; memory for one or two conversations; concurrent meetings; five societiesRepeated proposals
2.2 Agent role2, 5, 10, 20 invitations; memory rules including a promise list; five societiesConflicting commitments
2.3 Society size1,000, 4,000, 16,000 agents; push and paid mail first; three search methods; 24 matching agents, group of ten; heavy traffic, ten societiesShare found; groups formed
2.4 Network structure50, 250, 1,005 agents; direct and forwarded search; inbox rules, traffic, and adoption; 20 requests, three societies per sizeShare found; forwarding losses
3. Reading rules4, 8, 16 reads from 32 messages; reading rules and reply conditionsTarget read; correct replies; tokens
Table 2. Summary of experiments. Reading and memory rules are defined in Table 1 . Experiments 1, 2.1, 2.2, and 3 use 100 decisions per setting.
Figure 2. An organizer running 2 to 20 meetings at once; five invitees, 100 decisions per cell, Wilson 95% intervals ( Wilson, 1927 ) ≤0.10\leq 0.10 . (a) Keeping every reply matches the best case; with a full memory, forgetting the oldest (push) collapses and the inbox rules collapse less. (b) Keeping every reply costs 1.5–10.5 ×\times the best case’s tokens. Two line charts over 2, 5, 10 and 20 meetings at once, one line per memory rule. Left: share of proposed hours already rejected. Keeping it all tracks the best case at every load. Forgetting the oldest rises to 0.97 at twenty meetings. Keeping whole conversations and letting the assistant choose stay lower. Right: input tokens per decision. Keeping it all grows with load to about ten times the best case, while the two inbox rules read a fifth to a quarter as much.
Figure 3. Why forgetting the oldest fails. Six replies from two negotiations, A and B. Push with a full context drops A1 and B1 by age, so the organizer re-proposes hours A1 had rejected. A pull inbox keeps A whole outside the model and reads only A. Diagram of three ways to hold six replies from two conversations, A and B. Push with memory not yet full keeps all six. Push with a full memory keeps only the newest replies and splits both conversations. A pull inbox stores whole conversations outside the model and reads only the conversation the decision needs.
Figure 4. Push degrades with each agent’s load in every shape of coordination. (a) Team size, ten meetings: keeping every reply stays within 0.05 of the best case, so open negotiations, not team size, break push. (b) The invitee double-promises even with every promise in view; only the promise list improves with load. (c) Society size, heavy spam: push finds no one, pull about 0.6 of the group at every size.
Figure 5. Inbox failures accumulate across agents. Group formation on email-Eu-core under heavy unwanted traffic, relative to unbounded attention. Solid: direct directory search. Dashed: forwarded through contacts. Paid mail first matches the control (not drawn); push finds no one; folders and batches lose far more when forwarded. Mean of three societies. Share of the target group found relative to unbounded attention, across networks of 50, 250, and 1005 agents. Direct search performs better than forwarded search for folder sorting and batch reading. Arrival-order reading finds no agents, while paid mail first matches unbounded attention.
agentssearchf=0.25f{=}0.250.50.50.750.75mean hop
50directory.28.46.761.0
 network.06.26.592.9
250directory.21.53.761.0
 network.02.10.403.2
1,005directory.22.42.731.0
 network.01.05.283.7
Table 3. Share of the target group found when a fraction ff of agents use paid mail first and the rest use arrival-order reading. Values are relative to full adoption ( f=1f=1 ), under heavy unwanted traffic. Mean of three societies. The last column gives the mean number of hops under full adoption.
Figure 6. No reading rule is best at every budget. 32 arrivals, 100 decisions per cell. (a) Target read. (b) Answer right. With 4 reads only the assistant choosing finds the target, at nearly five times the best case’s tokens; with 16, paid mail first matches the best case at a quarter of the assistant’s tokens. Gaps under 0.05 are noise. Two line charts against messages read out of 32 (4, 8 and 16) for newest first, paid mail first, closest match and the assistant chooses. (a) Share of decisions in which the target message was read: at four reads only the assistant choosing exceeds one half. At sixteen reads paid mail first reads it every time. (b) Share answered right: at sixteen reads paid mail first matches the best case.
  yes/no replypriced reply, “yes, up to $X”
reading rulereadstarget readrighttokensread: wanted / too expensiverightlimit righttokens
read it all (push)321.000.937401.00 / 1.000.910.82937
newest first40.090.525000.16 / 0.160.570.88500
newest first80.210.586300.26 / 0.120.631.00639
newest first160.530.727530.50 / 0.480.720.88833
paid mail first40.390.684340.44 / 0.360.680.82462
Table 4. Experiment 3. 32 arrivals, of which the agent reads 4, 8 or 16. 100 decisions per cell, gpt-5.6-terra. Yes/no reply: how often the target was read, how often the answer was right (an unread target counts as “no”), and tokens per decision (for the assistant, including the call to choose). Priced reply: how often wanted and too-expensive targets were read, how often the answer was right, and, for wanted targets read, how often the stated limit was right.
More in this topic

Multi-Agent Coordination

Multi-agent coordination studies how autonomous agents align actions, share information, and divide work to achieve individual or collective goals.

See all 520 papers

Explore similar work

CardsList
May 12, 2026

LLM-X: A Scalable Negotiation-Oriented Exchange for Communication Among Personal LLM Agents

We propose a personal-LLM exchange (LLM-X), a scalable negotiation-oriented environment that enables direct, structured communication across populations of personal agents (LLMs), each representing an individual user. Unlike existing tool-centric protocols that focus on agent-API interaction, LLM-X introduces a message bus and routing substrate for LLM-to-LLM coordination with guarantees around schema validity and policy enforcement. We contribute: (1) an architecture for LLM-X comprising federated gateways, topic-based routing, and policy enforcement; (2) a typed message protocol supporting capability negotiation and contract-net-style coordination; and (3) the first empirical evaluation of LLM-based multi-agent negotiation at scale. Experiments span 5, 9, and 12 agents, under distinct negotiation policies (Low, Medium, High), and across both short-run (minutes) and long-run (2h, 12h) load conditions. Results highlight clear policy-performance trade-offs: stricter policies improve robustness and fairness but increase latencies and message volume. Extended runs confirm that LLM-X remains stable under sustained load, with bounded latency drift.

Giuliano Lorenzoni, Paulo Alencar, Donald Cowan

University of Waterloo · University of Waterloo Waterloo, ON, Canada

Multi-Agent LLM SystemsMulti-Agent CoordinationMulti-Agent NegotiationAutomated NegotiationMulti-Agent Communication
AskPDF
Jun 30, 2026

From Signals to Structure: How Memory Architecture Drives Language Emergence in LLM Agents

How do two agents invent a shared language from scratch? In a Lewis signaling game, a sender and receiver must coordinate on a code using only their interaction history. We study five memory architectures across varying channel configurations with LLM agents and find that memory architecture matters more than channel capacity. Agents with a persistent private notebook benefit from surplus channel capacity and avoid the high-capacity collapse seen in stateless agents, achieving the most reliable coordination (0.867±0.0230.867 \pm 0.023 at capacity = 25). Stateless agents peak at moderate capacity and then degrade as the vocabulary grows beyond what a rolling context window can track The notebook externalizes learned conventions, freeing agents from having to re-derive codes each round. An information bottleneck-inspired argument predicts an optimal capacity equal to the number of objects. Instead, the bottleneck (capacity = 8) proves to be a fragility point, and surplus capacity is generally better. We show that channel capacity alone cannot predict coordination; memory architecture determines whether agents turn interaction history into stable conventions, and both dimensions are needed to understand how signals become language.

Yashar Talebirad, Eden Redman, Ali Parsaee +1

Alberta Machine Intelligence Institute, University of Alberta, Edmonton, Canada · Network for Applied Technology, Edmonton, Canada

Multi-Agent LLM SystemsMulti-Agent CoordinationMemory-Augmented AgentsEmergent Communication
AskPDF
Oct 12, 2026

Scaling Multi-Agent Intelligence with Substrate-Centric Coordination

Existing large language model (LLM) based multi-agent systems have been shown to scale poorly, and we identify three problems: reading burden that grows with the group, useful information diluted by shared work of unknown quality, and fragility to failed agents. We argue that the problems are largely due to agent-centric designs: the coordination structure is wired into fixed workflows, central coordinators, or peer-to-peer messaging, and recent blackboard-style methods that move the coordination into a shared medium relieve only the last problem. To close the gaps, we build ScaleMAS, where asynchronous agents interact with a shared datastore of linked messages via three operations: publishing messages with optional references to earlier ones that they build on, searching for messages by content, and visiting messages by address. Search returns at most kk messages, so an agent's read stays bounded at any group size; results are ranked by relevance and by how often they are cited, which we find to be an effective proxy for quality; and messages persist after their producers leave, so the group carries on when individual agents fail. Across four agentic tasks, ScaleMAS outperforms agent-centric and blackboard-style baselines at lower inference compute, continues to scale up to 128 agents, and tolerates losing agents midway.

Zhenting Qi, Zhuokai Zhao, Rulin Shao +7

FAIR at Meta · Harvard · Meta AI +1

Multi-Agent LLM SystemsMulti-Agent CoordinationMulti-Agent SystemsShared-Memory Multi-Agent Systems
AskPDF