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

Anthony T. Nixon

cs.ITApr 10, 2026

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

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.

Figures & tables

Agent pair	Sender ( $A$ )	Receiver ( $B$ )	$R_{\mathrm{crit}}$ meaning	Instantiation
Human $\leftrightarrow$ AI	AI ( $m_{A}$ large)	Human ( $m_{H}$ small)	RLHF feedback floor	§ 9
Large $\to$ small model	$m_{\text{large}}$	$m_{\text{small}}$	Distillation loss floor	Cor. 35
Sensor $\to$ controller	$m_{\text{sensor}}$	$m_{\text{ctrl}}$	Comm. bandwidth floor	§ 4
Stepping-stone chain	$m_{1}>\cdots>m_{k}$	(compositional)	Traversal rate budget	Thm. 31
Equal agents	$m$	$m$	$R_{\mathrm{crit}}=0$ (no gap)	Lem. 39

Table 1: The framework applies universally to any pair of bounded agents. The critical rate

R_{\mathrm{crit}}

quantifies the structural communication cost of the capacity gap. Below

R_{\mathrm{crit}}

, intent-preserving communication is impossible regardless of protocol design.

Framework	What is given	What remains open	This paper’s role
Classical R-D / WZ	Source alphabet and fidelity criterion are specified by the modeler	No account of where heterogeneous agents’ semantic alphabets come from	Derives those alphabets from bounded interaction before applying coding theory
POMDP abstraction / quotienting	Capacity-dependent state abstractions	No communication theorem between mismatched abstractions	Turns quotient mismatch into a rate theorem with a structural floor
IB / task-oriented compression	Relevance variable and task objective are designer-chosen	No receiver-capacity side-information model	Uses receiver quotient classes as capacity-derived side information, not designer-chosen relevance
This work	Sender/receiver quotient alphabets are induced by capacity	Communication cost between mismatched semantic spaces	Identifies the structural floor and the one-way benchmark once the alphabets are derived

Table 2: Positioning relative to adjacent frameworks. The novelty is not the reuse of classical coding tools per se, but the derivation of agent-dependent semantic alphabets from bounded interaction and the resulting communication problem between them.

Panel of Figure 1 — Figure 1: Quotient partitions for two agents of different capacity. Solid blue boxes: $\mathcal{Q}_{A}$ -classes (finer). Dashed red boxes: $\mathcal{Q}_{B}$ -classes (coarser). Each $\mathcal{Q}_{B}$ -class merges multiple $\mathcal{Q}_{A}$ -classes. Below $R_{\mathrm{crit}}=\lceil\log 5-\log 2\rceil$ bits/step, $B$ cannot distinguish the merged subclasses—some of $A$ ’s intended actions are irrecoverable.

Symbol	Meaning
$M$ ; $\mathcal{S},\mathcal{A},\mathcal{O}$	POMDP; state, action, observation sets
$Q_{m,T}(M)$ ; $\mathcal{Q}_{A},\mathcal{Q}_{B}$	Quotient POMDP; quotient class sets for agents $A$ , $B$
$\Pi_{m,T}$	$m$ -node FSCs evaluated over horizon $T$
$\equiv_{m,T}$	Bounded indistinguishability (history equivalence under $\Pi_{m,T}$ )
$R_{\mathrm{crit}}$ , $R_{\mathrm{sem}}(\varepsilon)$	Critical rate, semantic rate-distortion function
$d_{\mathrm{intent}}$ , $D_{\mathrm{intent}}$	Per-history and expected intent distortion

Table 3: Core notation. See Sections 2 and 3 for formal definitions.

Form of $R_{\mathrm{crit}}$	Expression	Regime
Log-cardinality (worst-case)	$\log\|\mathcal{Q}_{A}\|-\log\|\mathcal{Q}_{B}\|$	Uniform quotient dist.
WZ lossless rate (i.i.d.)	$H(Q_{A}\mid Q_{B})$	i.i.d. source
Conditional entropy rate	$\bar{h}(Q_{A}\mid Q_{B})=h_{A}-h_{B}$	Stationary ergodic

Table 4: Hierarchy of critical-rate characterizations, from conservative (top) to sharp (bottom). The log-cardinality form is policy-independent; the entropy-rate form depends on the joint quotient dynamics. Numerical values for Chain5 appear in Appendix M .

Panel of Figure 2 — Figure 2: Left: Chain5 rate-distortion curves for $m_{A}\!=\!16$ , $m_{B}\in\{1,2,4,8\}$ . A sharp knee appears near $R_{\mathrm{crit}}\approx 1.4$ bits/step (dashed); distortion decays rapidly above it. Right: $R_{\min}$ vs. capacity gap (slope $\approx 1$ ), confirming Corollary 35 .

Figure 3: Shrinking-distortion regime illustration for the asymptotic one-way converse (Chain5, $(m_{A},m_{B})=(16,1)$ ). The orange curve shows the empirical minimum rate $R_{\min}$ achieving $D_{\mathrm{intent}}\leq\varepsilon_{T}$ with $\varepsilon_{T}=0.4/T$ ; the blue curve shows the log-cardinality reference $\log|Q_{A}|-\log|Q_{B}|$ . This figure is a regime-matching illustration for Theorem 20 . By contrast, Figure 2 remains a fixed- $\varepsilon$ illustration of the broader structural phase-transition theorem.

Figure 4: Phase transition at $|S|>100$ . Top: $m_{B}\!=\!1$ creates a capacity gap; distortion floor persists below $R_{\mathrm{crit}}=2$ bits/step. Bottom: $m_{B}\!=\!2$ closes the gap ( $|\mathcal{Q}_{A}|=|\mathcal{Q}_{B}|$ ). Domains: Chain100 ( $|S|\!=\!100$ ), Chain150 ( $|S|\!=\!150$ ), Chain200 ( $|S|\!=\!200$ ).

Figure 5: RockSample(4,4): phase transition and WZ benchmark. Left: $D_{\mathrm{intent}}$ vs. $R$ for $m_{A}\!=\!8$ , $m_{B}\in\{1,2,3\}$ ; the $m_{B}\!=\!1$ curve shows a clear knee at $R_{\mathrm{crit}}\!=\!3$ bits/step. Right: Blahut-Arimoto $R_{\mathrm{WZ}}(D)$ (black) vs. $R(D)$ (red) on the non-i.i.d. quotient source; $H(\mathcal{Q}_{A}|\mathcal{Q}_{B})=0.70$ bits/step.

Panel of Figure 6 — Figure 6: Left: RichGridWorld ( $T\!=\!2$ ); $m_{B}\!=\!1$ gap creates a distortion floor. Right: BalancedRand8 ( $T\!=\!4$ , refinement ratio $2.58$ ); inflection near $R_{\mathrm{crit}}\approx 1.63$ .

Figure 7: Wyner-Ziv benchmark curves under random vs. structured policies (Chain5, $m_{A}\!=\!16$ , $m_{B}\!=\!1$ ). Solid: $R_{\mathrm{WZ}}(D)$ with decoder side information; dashed: $R(D)$ without. Vertical lines mark the log-cardinality bound ( $1.43$ , gray), $H(\mathcal{Q}_{A}|\mathcal{Q}_{B})_{\mathrm{rand}}$ ( $0.29$ , blue), and $H(\mathcal{Q}_{A}|\mathcal{Q}_{B})_{\mathrm{struct}}$ ( $0.08$ , red). Structured vs. random at the same WZ benchmark level: $3.6\times$ reduction ( $0.08$ vs. $0.29$ ); structured vs. worst-case counting bound: $19\times$ ( $0.08$ vs. $1.43$ ).

Figure 8: IB-style encoder-only compression vs. the semantic WZ benchmark ( Proposition 29 ). The dashed curve ignores decoder side information $Q_{B}$ ; the solid curve exploits it. The exact theorem-level statement is the lower bound of Proposition 29 ; the lossless endpoints differ by $H(Q_{B})$ . (a) Structured policies: $31\times$ lossless gap. (b) Random policies: $21\times$ lossless gap.

Result	Status	Assumptions	Loc.
Value/proxy bounds	Proved	Lip. reward	§ 3
Capacity (i): threshold	Proved	Common-history coarsening + positive support on a merged class	App. H
Capacity (ii): exp. decay	Proved (i.i.d. one-way)	Common-history coarsening, intent meas., one-way, i.i.d. quotient source, Lip.	App. I
Shrinking-distortion converse	Proved (shrinking- $\varepsilon$ regime)	Common-history coarsening, intent meas., quot. reg., one-way	App. J
WZ converse (Prop. 25 (i))	Proved	Common-history coarsening, intent meas. + one-way	§ 7
WZ bridge (Prop. 25 (ii))	Proved (i.i.d.) / Argued (erg.)	Common-history coarsening, intent meas. + one-way	§ 7

Table 5: Proof status. “Proved” = complete proof in appendix. “Proved (i.i.d.) / Argued (erg.)” = exact for memoryless sources; ergodic case argued with explicit mixing-time bounds ( Remark 27 ). “Argued” = structured argument; gap acknowledged. The alignment upper bound is constructive rather than fully general, and the shrinking-distortion converse is theorem-level only in its stated asymptotic regime.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Claim surface	Formal status	Assumptions	What the experiments speak to
Structural phase transition; one-way constructive decay	Lower bound theorem-level; exponential decay theorem-level only in the i.i.d. one-way regime	Common-history coarsening for quotient comparison; positive support for impossibility; intent meas. + one-way + i.i.d. + Lip. for constructive decay	Chain5, RichGridWorld, BalancedRand8, and Chain100/150/200 probe where the empirical knees sit relative to the stated references; Chain5 is not read as validation of a sharp constructive exponent
Shrinking-distortion converse	Theorem-level, asymptotic only	Common-history coarsening, intent meas., one-way observability, quotient regularity, shrinking distortion $\varepsilon=O(1/T)$	A dedicated shrinking- $\varepsilon$ Chain5 sweep matches the converse regime; the fixed- $\varepsilon$ plots still illustrate the broader phase-transition shape rather than the converse itself
One-way WZ benchmark	Exact converse; i.i.d. operationally exact; ergodic long-run bridge argued	Common-history coarsening, intent meas. + one-way observability	Blahut-Arimoto curves and structured-policy comparisons validate benchmark sensitivity to visitation, not full ergodic FSC-level equality
Alignment applications	Lower bound theorem-backed; upper bound constructive; routing qualitative	Quotient model for the application; memoryless/codebook assumptions for the upper bound	Alignment-scaling plots support the structural trend; the LLM routing appendix is an analogy/case study, not a formal instantiation

Appendix

Table 6: Ledger separating theorem-level claims from benchmark-level and qualitative claims. The purpose is not to downplay the empirical section, but to prevent fixed-

\varepsilon

experiments and benchmark calculations from being mistaken for proof of stronger statements than the paper actually establishes.

Form of $R_{\mathrm{crit}}$	Expression	Regime	Depends on	Chain5
Log-cardinality	$\log\|\mathcal{Q}_{A}\|-\log\|\mathcal{Q}_{B}\|$	Worst-case	Quotient sizes only	1.43
Marginal entropy	$H(Q_{A})-H(Q_{B})$	i.i.d. source	Policy visitation	0.59
WZ lossless rate	$H(Q_{A}\mid Q_{B})$	i.i.d. (BA)	Source + coarsening	0.29 ‡
Cond. entropy rate	$\bar{h}(Q_{A}\mid Q_{B})$	Stationary ergodic	Joint dynamics	$0.024^{\dagger}$

Appendix

Table 7: Critical rate benchmark characterizations with Chain5 numerical values (

(m_{A}\!=\!16,\,m_{B}\!=\!1)

); see Table 4 for the condensed hierarchy. The WZ lossless rate

H(Q_{A}\mid Q_{B})

is computed via Blahut-Arimoto on visited quotient classes and is the most reliable numerical reference.

Figure 9: Semantic rate-distortion curves for the Tiger environment ( $T=4$ , $m_{A}=3$ , $m_{B}=1$ ).

Panel of Figure 10 — Figure 10: Left: Critical rate $R_{\mathrm{crit}}$ vs. quotient size gap across POMDP instances. Right: Semantic vs. classical coding ( $m_{A}\!=\!16,\;m_{B}\!=\!2$ ). Shaded band shows IQR over 10 seeds.

Figure 11: Quotient estimation convergence for Chain5 ( $T=4$ ). Each point is the median $|\mathcal{Q}_{m,T}|$ over 10 seeds; shaded bands indicate IQR. Estimates stabilize by $n_{\mathrm{FSC}}\approx 20$ .

Multi-Agent Communication

Multi-agent communication studies how autonomous agents exchange information to coordinate decisions, share knowledge, and act together under constraints.

See all 365 papers

Apr 10, 2026

Semantic Channel Theory: Deductive Compression and Structural Fidelity for Multi-Agent Communication

Shannon's information theory deliberately excludes message semantics. This paper develops a rigorous framework for semantic communication that integrates formal proof systems with Shannon-theoretic tools. We introduce an axiomatic information model comprising Lsem-definable state sets linked by computable enabling maps, and define the semantic channel as a composition of Markov kernels whose supports respect the enabling structure. A fixed proof system induces an irredundant semantic core and a derivation-depth stratification, enabling four distortion measures of increasing semantic depth: Hamming, closure, depth, and a parameterized composite. Six families of computable semantic channel invariants are defined and their inter-relationships established, including a data processing bound, a semantic Fano bound, and an ideal-channel collapse theorem. The central quantitative result is a deductive compression gain: under closure-based fidelity, the minimum block length is determined by the irredundant core size rather than the full knowledge-base size. We instantiate the framework for heterogeneous multi-agent communication, introducing an overlap decomposition that yields necessary and sufficient conditions for closure-reliable communication. A semantic bottleneck phenomenon is identified in broadcast settings: vocabulary mismatch imposes irreducible fidelity limitations even over noiseless carriers. All results are verified on an explicit Datalog instance.

Jianfeng Xu

Koguan School of Law, China Institute for Smart Justice, School of Computer Science, Shanghai Jiao Tong University, Shanghai 200030, China

Semantic Communication Information-Theoretic Lower Bounds Multi-Agent Communication

Ask PDF

Sep 28, 2026

Emergence, Not Bandwidth: Physical Coupling and the Limits of Learned Multi-Agent Communication

Rate-limited multi-agent teams raise three questions the emergent-communication literature has answered only empirically: what an optimal message should encode, what compression costs over a horizon, and when a learned protocol is unique enough for a teammate to read. We answer them for rate-limited Dec-POMDPs, then measure how far reinforcement learning falls short of the optimum. Our theorems fix what is achievable independently of any learner, so a gap between an engineered and a learned sender at the same bit budget is an optimization fact, not an information-theoretic one. We instantiate this on three MuJoCo arenas spanning zero, partial and rigid physical coupling, charging every condition exactly 2 bits per decision, and create the discriminating regime by closing a physical side channel within one arena, holding bodies, task and reward fixed. Communication value is governed by coupling: under rigid coupling through a shared object, no channel beats silence (+0.001 +/- 0.001, p = 0.982, n = 25), since proprioception already carries that information; without coupling, every condition solves the task; under partial coupling, the engineered 2-bit sender reaches an interquartile mean of 1.000 but the learned one reaches 0.482, indistinguishable from silence (p = 0.400, n = 25). With a shared alphabet, bandwidth cannot explain the gap. Warm-starting from an engineered receiver localizes the failure: the same channel reaches 0.857 versus 0.562 cold-started (p < 0.001), so it is neither representational nor one of maintenance; reinforcement learning fails to discover the protocol. Cross-play shows learned protocols are individually meaningful but mutually unintelligible: self-play 0.980 collapses to 0.144 across seeds, and our best constructed alignment leaves at least 77% of that gap. All headline results use 25 seeds per arena and seven published baselines at matched rate.

Mihir Chauhan, Aniket Bera

IDEAS Lab, Department of Computer Science Purdue University

Sequential MARL Partially Observable Markov Decision Processes Multi-Agent Communication Cooperative MARL Emergent Communication

Ask PDF

Apr 13, 2026

Semantic Rate-Distortion Theory: Deductive Compression and Closure Fidelity

Shannon's rate-distortion theory treats source symbols as unstructured labels. When the source is a knowledge base equipped with a logical proof system, a natural fidelity criterion is closure fidelity: a reconstruction is acceptable if it preserves the deductive closure of the original. This paper develops a rate-distortion theory under this criterion. Central to the theory is the irredundant core-a canonical generating set extracted by a fixed-order deletion procedure, from which the full deductive closure can be rederived. We prove that the zero-distortion semantic rate equals a quantity that is strictly below the classical entropy rate whenever the knowledge base contains redundant states. More generally, the full semantic rate-distortion function depends only on the core; redundant states are invisible to both rate and distortion. We derive a semantic source-channel separation theorem showing a semantic leverage phenomenon: under closure fidelity, the required source rate is reduced by an asymptotic leverage factor greater than one, allowing the same knowledge base to be communicated with proportionally fewer channel uses-not by violating Shannon capacity, but because redundant states become free. We also prove a strengthened Fano inequality that exploits core structure. For heterogeneous multi-agent communication, an overlap decomposition gives necessary and sufficient conditions for closure-reliable transmission and identifies a semantic bottleneck in broadcast settings that persists even over noiseless channels. All results are verified on Datalog instances with up to 24,000 base facts.

Jianfeng Xu

Koguan School of Law, China Institute for Smart Justice, School of Computer Science, Shanghai Jiao Tong University, Shanghai 200030, China.

Rate-Distortion Theory

Ask PDF

Abstract

Multi-Agent Communication

Explore similar work

Semantic Channel Theory: Deductive Compression and Structural Fidelity for Multi-Agent Communication

Emergence, Not Bandwidth: Physical Coupling and the Limits of Learned Multi-Agent Communication

Semantic Rate-Distortion Theory: Deductive Compression and Closure Fidelity