Berkeley's coarsening trick finds near-optimal communication protocols in polynomial time

A new paper from UC Berkeley researchers Mark Bedaywi, Scott Emmons, Nika Haghtalab, and Stuart Russell tackles a core problem in collaborative AI: how many bits do agents need to communicate to make good joint decisions, and can those protocols be computed efficiently? Their answer, published on arXiv (2608.05327), is both surprising and practical. They show that for any communication game with n possible observations and m actions, there exists an algorithm that runs in polynomial time (poly(n,m,1/ε)) and produces a protocol achieving near-optimal utility (α−ε). The protocol uses at most 2^O(CCα(G))/ε² bits, where CCα(G) is the minimum bits any protocol—even a computationally unbounded one—would need to hit utility α. This exp(CCα) dependence is tight: unless P=NP, no polynomial-time algorithm can find truly optimal protocols with fewer than 2^(CCα−2) bits.

The key technical innovation is a strengthened version of the Frieze–Kannan weak regularity lemma, which lets them construct a simplified coarsened game Ĝ where each agent's observation space is collapsed into constant-size partitions. This coarsening preserves behavior on all short protocols, making it the engine behind their efficient algorithm. Crucially, their approach requires no structural assumptions like informational substitutes or weak learnability—which they prove actually imply CCα(G)=O(1), making those prior conditions far more restrictive than necessary. This means for any game with a short high-utility protocol, the algorithm can find one efficiently, opening the door to designing practical coordination protocols for multi-agent systems, from robot swarms to LLM-based agents, without hand-crafted communication strategies.