Semantic Rate-Distortion for Bounded Multi-Agent Communication: Capacity-Derived Semantic Spaces and the Communication Cost of Alignment
Summary: arXiv:2604.09521v1 Announce Type: cross
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 Qm,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 Rcrit 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.
Key Contributions
- Structural Phase-Transition Theorem: We prove a fixed-ε structural phase-transition theorem whose lower bound is fully general on the common-history quotient comparison.
- 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.
- Asymptotic One-Way Converse: Derived in the shrinking-distortion regime ε = O(1/T), proved from the message stream and decoder side information.
- Alignment Traversal Bounds: Enabling compositional communication through intermediate capacity levels.
Experimental Findings
Experiments conducted on eight POMDP environments, including RockSample(4,4), illustrate the phase transition. A structured-policy benchmark demonstrates that the one-way rate can drop by up to 19 times relative to the counting bound. Additionally, a shrinking-distortion sweep aligns with the regime of the asymptotic converse, providing a deeper understanding of how agents with differing capacities can communicate effectively.
Conclusion
This study underscores the importance of understanding the communication dynamics between heterogeneous agents in multi-agent systems. By establishing a capacity-derived semantic space and illustrating the critical rates for effective communication, we pave the way for future research aimed at optimizing multi-agent interactions and enhancing the efficiency of information exchange.