# Semantic Rate-Distortion for Bounded Multi-Agent Communication: Capacity-Derived Semantic Spaces and the Communication Cost of Alignment

arXiv: https://arxiv.org/abs/2604.09521 · HTML: https://mlsanity.com/paper/2604.09521/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 50 references that are in the map.
- First posted on arXiv 10 Apr 2026.

## Builds on (most cited first, 14 of 14)

- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Language Models (Mostly) Know What They Know](https://mlsanity.com/paper/2207.05221/) (2022)
- [MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark](https://mlsanity.com/paper/2406.01574/) (2024)
- [RouteLLM: Learning to Route LLMs with Preference Data](https://mlsanity.com/paper/2406.18665/) (2024)
- [Deep Learning Enabled Semantic Communication Systems](https://mlsanity.com/paper/2006.10685/) (2020)
- [The Complexity of Decentralized Control of Markov Decision Processes](https://mlsanity.com/paper/1301.3836/) (2013)
- [Multi-Agent Cooperation and the Emergence of (Natural) Language](https://mlsanity.com/paper/1612.07182/) (2016)
- [Beyond Transmitting Bits: Context, Semantics, and Task-Oriented Communications](https://mlsanity.com/paper/2207.09353/) (2022)
- [Semantics-Empowered Communication for Networked Intelligent Systems](https://mlsanity.com/paper/2007.11579/) (2020)
- [Biases for Emergent Communication in Multi-agent Reinforcement Learning](https://mlsanity.com/paper/1912.05676/) (2019)
- [On the Information Bottleneck Problems: Models, Connections, Applications and Information Theoretic Views](https://mlsanity.com/paper/2002.00008/) (2020)
- [The Myhill-Nerode Theorem for Bounded Interaction: Canonical Abstractions via Agent-Bounded Indistinguishability](https://mlsanity.com/paper/2603.21399/) (2026)

## Abstract (arXiv)

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. 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× relative to the counting bound, and a shrinking-distortion sweep matches the regime of the asymptotic converse.