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

Jianfeng Xu

cs.LOApr 10, 2026

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

Authors: Jianfeng Xu

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

Abstract

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.

Figures & tables

Symbol	Meaning
$S_{O}^{(i)}$	Knowledge base (semantic state set) of agent $i$
$A^{(i)},\;J^{(i)}$	Irredundant core and stored shortcuts of agent $i$
$S_{\cap}^{ij}$	Common states: $S_{O}^{(i)}\cap S_{O}^{(j)}$
$S_{-}^{ij}$	Lost states: $S_{O}^{(i)}\setminus S_{O}^{(j)}$ $(\,=S_{O}^{-})$
$S_{+}^{ij}$	Surplus states: $S_{O}^{(j)}\setminus S_{O}^{(i)}$ $(\,=S_{O}^{+})$
$A_{\cap}^{ij}$	Preserved sender core: $A^{(i)}\cap S_{O}^{(j)}$

TABLE I: Notation summary for Section V . All quantities are defined relative to a fixed sender–receiver pair

(i,j)

Family	Invariant	Overlap expression / constraint
I. Source struct.	$\mathsf{A}$	$\|A^{(i)}\|$ (sender core size)
I. Source struct.	$\mathsf{D_{d}}$	$\max_{q\in S_{O}^{(i)}}\text{Dd}(q\mid A^{(i)})$
II. Set-level (KB only)	$\rho_{\text{Atom}}$	$(\|A^{(i)}\|-\|A_{-}^{ij}\|)/\|A^{(i)}\|$ ( 5.10 )
II. Set-level (KB only)	$\mathsf{F}_{\text{Cn}}$	$=1$ iff (F1)+(F2) (Prop. 5.3 )
III. Noise-pair (+kernel)	$\Phi_{\text{Atom}}$	$=0$ if $A_{-}^{ij}\neq\varnothing$ ; else $\min_{a}\kappa_{\mathrm{sem}}^{ij}(a\mid a)$
III. Noise-pair (+kernel)	$\Psi_{+}$	$=0$ if $S_{+}^{ij}=\varnothing$ ; else $\max_{s_{o}}\sum_{\hat{s}_{o}\in S_{+}^{ij}}\kappa_{\mathrm{sem}}^{ij}(\hat{s}_{o}\mid s_{o})$

TABLE II: Semantic channel invariants expressed in the overlap language of Definition 5.4 . “KB only” indicates dependence on the knowledge-base pair alone; “+kernel” indicates additional dependence on the channel kernel

\kappa_{\mathrm{sem}}^{ij}

Stratum	New elements
$T^{0}$	$\mathit{Edge}(a,b)$ , $\mathit{Edge}(a,c)$ , $\mathit{Edge}(b,c)$ , $\mathit{Edge}(c,d)$
$T^{1}\!\setminus\!T^{0}$	$\mathit{Path}(a,b)$ , $\mathit{Path}(a,c)$ , $\mathit{Path}(b,c)$ , $\mathit{Path}(c,d)$
$T^{2}\!\setminus\!T^{1}$	$\mathit{Path}(a,d)$ , $\mathit{Path}(b,d)$

TABLE III: Stratum decomposition of

T_{\mathsf{PS}}

-iteration from

A^{(1)}

Quantity	Recv. 2	Recv. 2 ′	Recv. 3
$\|S_{\cap}^{ij}\|$	7	8	4
$\|S_{-}^{ij}\|$	1	0	4
$\|S_{+}^{ij}\|$	2	1	2
$\|A_{\cap}^{ij}\|$	3	4	4
$\|A_{-}^{ij}\|$	1	0	0
$\|S_{+,d}^{ij}\|$	1	1	2

TABLE IV: Overlap decomposition and set-level invariants for sender agent 1 paired with each receiver.

Family	Invariant	Pair $(1,2)$	Pair $(1,2^{\prime})$	Pair $(1,3)$
I. Source	$\mathsf{A}(\mathcal{I}^{(1)})$	4	4	4
I. Source	$\mathsf{D_{d}}(\mathcal{I}^{(1)})$	2	2	2
II. Set-level	$\rho_{\text{Atom}}$	0.750	1.000	1.000
II. Set-level	$\mathsf{F}_{\text{Cn}}$	0.429	1.000	1.000
III. Noise-pair	$\Phi_{\text{Atom}}$	0	0.900	0.900
III. Noise-pair	$\Psi_{+}$	0	0	0.911

TABLE V: Semantic channel invariants for the Datalog instance of Example 5.1 . Carrier channel:

q

-ary symmetric,

q=10

p=0.1

. Source distribution:

P_{O}

uniform on

S_{O}^{(1)}

. Encoding: fixed deterministic injection

f:S_{O}^{(1)}\to\{0,\ldots,9\}

; decoding: deterministic nearest-element rule (see text).

Criterion	Pair $(1,2)$	Pair $(1,2^{\prime})$	Pair $(1,3)$
Hamming $n^{*}_{H}$	N/A †	1.183	N/A †
Closure $n^{*}_{\text{Cn}}$	$\nexists$ ‡	0.789	0.789
Ratio $n^{}_{\text{Cn}}/n^{}_{H}$	—	0.667	—
† Hamming reconstruction impossible: $S_{-}^{ij}\neq\varnothing$ . ‡ $\mathsf{F}_{\text{Cn}}<1$ : closure reliability unachievable (Corollary 5.3 ).

TABLE VI: Minimum blocklength estimates (

q=10

p=0.1

\epsilon\to 0

). All values are asymptotic:

n^{*}_{H}\approx\log|S_{O}^{(1)}|/C(W)

n^{*}_{\text{Cn}}\approx\log|A^{(1)}|/C(W)

Semantic Communication

Semantic communication sends meaning- or task-relevant information so receivers can act without reconstructing every transmitted bit or signal.

See all 100 papers

Semantic Rate-Distortion Theory: Deductive Compression and Closure Fidelity
Apr 13, 2026Jianfeng XuRate-Distortion Theory
Koguan School of Law, China Institute for Smart Justice, School of Computer Science, Shanghai Jiao Tong University, Shanghai 200030, China.
Semantic Rate-Distortion for Bounded Multi-Agent Communication: Capacity-Derived Semantic Spaces and the Communication Cost of Alignment
Apr 10, 2026Anthony T. NixonMulti-Agent Communication Task-Oriented Semantic Communication
Towards High Semantic Fidelity: Hyperdimensional Symbolic Messages in Multi-Agent Communication
Oct 16, 2026Shoucheng Song, Chang Yao, Hao Wu +3Semantic Communication Multi-Agent Communication
School of Computer Science & Technology, Beijing Jiaotong University, Beijing, China · Beijing Key Laboratory of Traffic Data Mining and Embodied Intelligence, Beijing, China · Institute of Artificial Intelligence of China Telecom (TeleAI), Beijing, China

Apr 13, 2026J/K move · Enter open · S save

Semantic Rate-Distortion Theory: Deductive Compression and Closure Fidelity

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

Open paper AskPDF arXiv

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.

Quantity	Recv. 2	Recv. 2 ′	Recv. 3
$\|S_{\cap}^{ij}\|$	7	8	4
$\|S_{-}^{ij}\|$	1	0	4
$\|S_{+}^{ij}\|$	2	1	2
$\|A_{\cap}^{ij}\|$	3	4	4
$\|A_{-}^{ij}\|$	1	0	0
$\|S_{+,d}^{ij}\|$	1	1	2

Abstract

Semantic Communication

Explore similar work

Semantic Rate-Distortion Theory: Deductive Compression and Closure Fidelity

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

Towards High Semantic Fidelity: Hyperdimensional Symbolic Messages in Multi-Agent Communication