Semantic Rate-Distortion Theory: Deductive Compression and Closure Fidelity

Jianfeng Xu

cs.ITApr 13, 2026

Semantic Rate-Distortion Theory: Deductive Compression and Closure Fidelity

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 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.

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)

Quantity	Recv. 2	Recv. 2 ′	Recv. 3
$\|A_{-}^{ij}\|$	1	0	0
$\|S_{+,n}^{ij}\|$	1	0	0
$\rho_{\text{Atom}}$	3/4	1	1
$\mathsf{F}_{\text{Cn}}$	$3/7$	1	1

TABLE II: 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}$	4	4	4
I. Source	$\mathsf{D_{d}}$	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.900	0	0.911

TABLE III: Semantic channel invariants for the Datalog instance in Example 5.1 .

Criterion	$(1,2)$	$(1,2^{\prime})$	$(1,3)$
Hamming $n^{*}_{H}$	N/A †	1.183	N/A †
Closure $n^{*}_{\text{Cn}}$	$\nexists$ ‡	0.789	0.789
Ratio	—	2/3	—
† $S_{-}^{ij}\neq\varnothing$ (Hamming reconstruction undefined). ‡ $A_{-}^{ij}\neq\varnothing$ , so $\mathsf{F}_{\text{Cn}}<1$ by Corollary 5.3 .

TABLE IV: Minimum blocklength estimates (

\epsilon\to 0

$\|\mathcal{V}\|$	$p$	$\|\mathcal{F}\|$	$\|\mathrm{Cl}\|$	$\gamma_{\mathrm{amp}}$	$d$
50	0.060	188	2 727	14.5	10
200	0.040	1 705	45 105	26.5	5
500	0.020	5 179	268 679	51.9	5
1 000	0.012	12 305	1 050 305	85.4	5
2 000	0.006	24 304	4 118 304	169.4	6

TABLE V: Deductive amplification across knowledge-base scales.

\gamma_{\mathrm{amp}}=|\mathrm{Cl}|/|\mathcal{F}|

$\mu$ (%)	$\|J\|$	$\|S_{O}\|$	$\rho_{\mathrm{comp}}$	$\rho_{\mathrm{ent}}$	$\Lambda_{1}$
0	0	1 705	1.000	1.000	1.00
10	4 340	6 045	0.855	0.241	1.17
20	8 680	10 385	0.805	0.132	1.24
30	13 020	14 725	0.775	0.090	1.29
50	21 700	23 405	0.740	0.054	1.35
80	34 720	36 425	0.709	0.033	1.41

TABLE VI: Deductive compression gain for the 200-location supply-chain knowledge base with materialized shortcuts.

|A|=|\mathcal{F}_{\mathrm{base}}|=1{,}705

throughout;

P_{O}

uniform on

S_{O}

$\|\mathcal{V}\|$	$\|A\|$	$\|S_{O}\|$	$\rho_{\mathrm{comp}}$	$\rho_{\mathrm{ent}}$	$d_{\max}$
50	188	949	0.764	0.151	10
200	1 705	14 725	0.775	0.090	5
500	5 179	84 229	0.754	0.046	5
1 000	12 305	323 705	0.742	0.028	5
2 000	24 304	1 252 504	0.719	0.014	6

TABLE VII: Deductive compression at

\mu=0.3

across scales.

Rate-Distortion Theory

Rate-distortion theory studies the minimum information needed to represent data at a chosen level of distortion.

See all 28 papers

Semantic Channel Theory: Deductive Compression and Structural Fidelity for Multi-Agent Communication
Apr 10, 2026Jianfeng XuSemantic Communication Information-Theoretic Lower Bounds
Koguan School of Law, China Institute for Smart Justice, School of Computer Science, Shanghai Jiao Tong University, Shanghai 200030, China
On the Rate-Distortion-Complexity Tradeoff for Semantic Communication
Feb 16, 2026Jingxuan Chai, Yong Xiao, Guangming ShiSemantic Communication Rate-Distortion Theory
the School of Artificial Intelligence at the Xidian University, Shaanxi 710071, China · the School of Electronic Information and Communications at the Huazhong University of Science and Technology, Wuhan 430074, China · the Pengcheng Laboratory, Shenzhen, Guangdong 518055, China +2
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

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

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

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

Open paper AskPDF arXiv

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.

Abstract

Rate-Distortion Theory

Explore similar work

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

On the Rate-Distortion-Complexity Tradeoff for Semantic Communication

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