Semantic Rate-Distortion for Bounded Multi-Agent Communication: Capacity-Derived Semantic Spaces and the Communication Cost of Alignment
2026-04-10 • Information Theory
Information TheoryArtificial Intelligence
AI summaryⓘ
The authors study how two agents with different computing abilities understand and communicate about the same environment differently by creating their own simplified versions (semantic alphabets). They show there's a precise point where effective communication becomes impossible if the information rate is too low, based on how their simplified views mismatch. Their work mathematically defines and proves this communication boundary and provides ways to optimize information exchange depending on each agent's capacity. They also test their theories on multiple examples, confirming that communication efficiency can greatly improve when accounting for these capacity differences.
POMDPsemantic alphabetbounded agentquotient spacephase transitionWyner-Ziv codingside informationmemoryless sourceergodicitydistortion rate
Authors
Anthony T. Nixon
Abstract
When two agents of different computational capacities interact with the same environment, they need not compress a common semantic alphabet differently; they can induce different semantic alphabets altogether. We show that the quotient POMDP $Q_{m,T}(M)$ - the unique coarsest abstraction consistent with an agent's capacity - serves as a capacity-derived semantic space for any bounded agent, and that communication between heterogeneous agents exhibits a sharp structural phase transition. Below a critical rate $R_{\text{crit}}$ determined by the quotient mismatch, intent-preserving communication is structurally impossible. In the supported one-way memoryless regime, classical side-information coding then yields exponential decay above the induced benchmark. Classical coding theorems tell you the rate once the source alphabet is fixed; our contribution is to derive that alphabet from bounded interaction itself. Concretely, we prove: (1) a fixed-$\varepsilon$ structural phase-transition theorem whose lower bound is fully general on the common-history quotient comparison; (2) a one-way Wyner-Ziv benchmark identification on quotient alphabets, with exact converse, exact operational equality for memoryless quotient sources, and an ergodic long-run bridge via explicit mixing bounds; (3) an asymptotic one-way converse in the shrinking-distortion regime $\varepsilon = O(1/T)$, proved from the message stream and decoder side information; and (4) alignment traversal bounds enabling compositional communication through intermediate capacity levels. Experiments on eight POMDP environments (including RockSample(4,4)) illustrate the phase transition, a structured-policy benchmark shows the one-way rate can drop by up to $19\times$ relative to the counting bound, and a shrinking-distortion sweep matches the regime of the asymptotic converse.