Rate-Distortion Theory for Deductive Sources under Closure Fidelity

arxiv: 2604.15698 · v3 · submitted 2026-04-17 · 💻 cs.IT · cs.LO· math.IT

Rate-Distortion Theory for Deductive Sources under Closure Fidelity

Jianfeng Xu This is my paper

Pith reviewed 2026-05-10 08:20 UTC · model grok-4.3

classification 💻 cs.IT cs.LOmath.IT

keywords rate-distortion theorydeductive sourcesclosure fidelityknowledge base compressionsource codingdeductive closureinference depthinformation theory

0 comments p. Extension

The pith

The minimum zero-distortion rate equals the source mass of the core times the entropy of the source conditioned on that core.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies lossy compression for sources made of logical statements inside a fixed proof system. Fidelity requires that the deductive closure of the reconstructed statements matches the original closure rather than matching symbols exactly. This setup decomposes any source into an irredundant core and redundant consequences that follow from it. The central result is that the lowest rate achieving zero distortion is exactly the probability mass of the core multiplied by the conditional entropy of the source given the core. When all allowed reconstructions lie inside the deductive closure, the entire rate-distortion function depends only on the core and the redundant statements become invisible to both rate and distortion.

Core claim

Under a natural disjointness condition on zero-distortion reconstruction sets, the minimum zero-distortion rate equals the source mass of the core times the entropy of the source conditioned on that core. For reconstruction alphabets contained in the deductive closure of the source knowledge base, the full rate-distortion function depends only on the core, so redundant states are invisible to both rate and distortion. When the decoder has a bounded inference-depth budget, an exact rate-depth-distortion characterization is obtained. Under an additional order-robustness assumption that identifies the chosen core with the order-free essential set, this characterization interpolates between古典符号逐

What carries the argument

The irredundant core of the deductive source, which is the minimal set of statements from which all others follow, under a fidelity criterion that preserves the deductive closure rather than individual symbols.

If this is right

The full rate-distortion function depends only on the core whenever reconstructions remain inside the deductive closure.
An exact rate-depth-distortion tradeoff exists when the decoder is restricted to a bounded number of inference steps.
Under order-robustness the tradeoff curve continuously connects symbolwise compression to fully deductive compression.
Redundant consequences generated by the proof system contribute nothing to either rate or distortion.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Shared inference rules between sender and receiver could allow transmission of only the core while the receiver reconstructs the rest.
The same decomposition might apply to other structured data such as databases or ontologies that admit closure operations.
Numerical experiments on small propositional theories could measure the gap between core-based rates and classical rates.

Load-bearing premise

The zero-distortion reconstruction sets are disjoint and the chosen core coincides with the order-free essential set.

What would settle it

A concrete finite statement source and proof system where the zero-distortion rate exceeds core mass times conditional entropy, or where adding redundant statements inside the closure changes the rate-distortion curve.

read the original abstract

We study lossy compression of a finite statement source generated in a fixed deductive environment. The source symbols are statements in a knowledge base endowed with a proof system, and reconstruction fidelity is measured by preservation of deductive closure rather than by symbolwise equality. This induces, once the proof system and canonical order are fixed, a decomposition of the source into an irredundant core and redundant stored consequences. Under a natural disjointness condition on zero-distortion reconstruction sets, we show that the minimum zero-distortion rate equals the source mass of the core times the entropy of the source conditioned on that core. For reconstruction alphabets contained in the deductive closure of the source knowledge base, we further prove that the full rate-distortion function depends only on the core, so redundant states are invisible to both rate and distortion. When the decoder is limited to a bounded inference-depth budget (a bounded number of iterations of the immediate-consequence operator), we obtain an exact rate-depth-distortion characterization. Under an additional order-robustness assumption identifying the chosen core with the order-free essential set, this characterization interpolates between classical symbolwise compression and unconstrained deductive compression. These results formulate deductive compression as a structured source-coding problem and quantify how shared inference structure changes the fundamental limits of communication.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper sets up rate-distortion for logical statements with closure fidelity and claims the rate depends only on an irredundant core, but the key factoring step rests on an unverified disjointness assumption.

read the letter

The main new piece is treating deductive closure as the fidelity measure instead of symbol equality. Under that setup the paper derives that zero-distortion rate equals core mass times conditional entropy, and that the full rate-distortion curve depends only on the core once the reconstruction alphabet stays inside the deductive closure. It also gives an exact rate-depth-distortion trade-off when the decoder has a bounded inference budget and shows how the result sits between ordinary symbolwise coding and fully unconstrained deductive coding under an extra order-robustness assumption. Those statements are cleanly stated and the interpolation claim is a reasonable way to position the work inside existing rate-distortion theory. The framing itself is useful for anyone thinking about compression of knowledge bases or AI reasoning traces. The soft spot is the disjointness condition on zero-distortion reconstruction sets. The abstract calls it natural and says it lets the rate factor cleanly, yet supplies no check against standard proof systems such as resolution or Hilbert calculi. If closures overlap across distinct source statements the factoring step fails and the core no longer isolates the rate. The order-robustness assumption is likewise required for the core to be unique and for redundant statements to be invisible; without it the claims do not go through. Because the manuscript text was not supplied here, I cannot see the actual derivations or any concrete examples that would confirm the assumptions hold in practice. The paper is written for information theorists who already work on structured sources or logic-based compression. A reader who wants to see whether closure fidelity really changes fundamental limits will get value from the framework, but only after the assumptions are tested. It deserves a serious referee to examine the proofs and to ask for verification on at least one standard deductive system. I would send it to review rather than desk-reject.

Referee Report

3 major / 2 minor

Summary. The paper develops a rate-distortion framework for finite sources of logical statements in a fixed deductive system, with fidelity defined by preservation of deductive closure rather than symbol equality. It decomposes any such source into an irredundant core plus redundant consequences, proves that the zero-distortion rate equals core mass times conditional entropy under a disjointness condition on zero-distortion sets, shows that the full R(D) depends only on the core when the reconstruction alphabet lies inside the deductive closure, derives an exact rate-depth-distortion function for bounded inference depth, and obtains an interpolation between classical symbolwise coding and unconstrained deductive coding under an order-robustness assumption.

Significance. If the stated assumptions hold, the results supply the first information-theoretic characterization of how shared deductive structure alters fundamental compression limits, rendering redundant consequences invisible to both rate and distortion. The exact bounded-depth characterization and the interpolation result are concrete strengths that could guide practical deductive compression schemes.

major comments (3)

[Abstract and main zero-distortion theorem] The central zero-distortion rate claim (abstract and the theorem establishing R(0) = core mass × H(source|core)) rests on the disjointness condition that zero-distortion reconstruction sets are disjoint across distinct source symbols. The manuscript calls the condition 'natural' but supplies neither a verification that it holds for standard calculi (resolution, Hilbert-style, etc.) nor a proof that the core decomposition remains unique once the condition is imposed. This is load-bearing for the factoring result.
[Theorem on R(D) dependence on core and the interpolation result] The claim that the full rate-distortion function depends only on the core (and that redundant states are invisible) requires both the reconstruction alphabet to lie inside the deductive closure and the order-robustness assumption that identifies the chosen core with the order-free essential set. The manuscript does not demonstrate that order-robustness holds in typical deductive environments or quantify the sensitivity of the core to ordering when the assumption fails.
[Bounded-depth rate-depth-distortion theorem] The exact rate-depth-distortion characterization under a bounded inference-depth budget inherits the same disjointness requirement; if overlapping closures occur for any finite depth, the clean separation into core mass and conditional entropy no longer follows. The paper should state explicitly whether the bounded-depth result continues to hold without disjointness or provide a counter-example.

minor comments (2)

[Model and notation] Define 'source mass of the core' and the precise meaning of 'deductive closure' with a short example in the model section before the main theorems; readers outside logic may otherwise lose the thread.
[Introduction] The abstract states that the results 'formulate deductive compression as a structured source-coding problem'; a brief comparison table with classical rate-distortion and with existing logical compression literature would help situate the contribution.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Central claims rest on two domain assumptions stated in the abstract; no free parameters or invented entities are explicitly introduced in the provided text.

axioms (2)

domain assumption natural disjointness condition on zero-distortion reconstruction sets
Invoked to obtain the minimum zero-distortion rate formula.
domain assumption order-robustness assumption identifying the chosen core with the order-free essential set
Used to interpolate between classical symbolwise compression and unconstrained deductive compression.

pith-pipeline@v0.9.0 · 5518 in / 1258 out tokens · 51570 ms · 2026-05-10T08:20:03.810100+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

31 extracted references · 1 canonical work pages

[1]

A mathematical theory of communication,

C. E. Shannon, “A mathematical theory of communication,”Bell System Technical Journal, vol. 27, no. 3, pp. 379–423, 1948

1948
[2]

T. M. Cover and J. A. Thomas,Elements of Information Theory, 2nd ed. John Wiley & Sons, 2006

2006
[3]

Csisz ´ar and J

I. Csisz ´ar and J. K ¨orner,Information theory: coding theorems for discrete memoryless systems. Cambridge University Press, 2011

2011
[4]

An outline of a theory of semantic information,

R. Carnap and Y . Bar-Hillel, “An outline of a theory of semantic information,” Research Laboratory of Electronics, MIT, Tech. Rep. Technical Report 247, 1952

1952
[5]

Beyond transmitting bits: Context, semantics, and task-oriented communications,

D. G ¨und¨uz, Z. Qin, I. E. Aguerri, H. S. Dhillon, Z. Yang, A. Yener, K. K. Wong, and C.-B. Chae, “Beyond transmitting bits: Context, semantics, and task-oriented communications,”IEEE Journal on Selected Areas in Communications, vol. 41, no. 1, pp. 5–41, 2022

2022
[6]

An indirect rate-distortion characterization for semantic sources: General model and the case of gaussian observation,

J. Liu, S. Shao, W. Zhang, and H. V . Poor, “An indirect rate-distortion characterization for semantic sources: General model and the case of gaussian observation,” inIEEE Transactions on Communications, vol. 70, no. 9, 2022, pp. 5946–5959

2022
[7]

A mathematical theory of semantic communication,

K. Niu and P. Zhang, “A mathematical theory of semantic communication,”Journal on Communications, vol. 45, no. 6, pp. 7–59, 2024

2024
[8]

Semantic rate-distortion theory with applications,

Y .-Q. Zhao, Z.-M. Ma, G. Y . Li, S. Yuan, T. Ye, and C. Zhou, “Semantic rate-distortion theory with applications,”arXiv preprint arXiv:2509.10061, 2025

work page arXiv 2025
[9]

Extended blahut-arimoto algorithm for semantic rate-distortion function,

Y . Han, Y . Liu, Y . Sun, K. Niu, N. Ma, S. Cui, and P. Zhang, “Extended blahut-arimoto algorithm for semantic rate-distortion function,” Entropy, vol. 27, no. 6, p. 651, 2025

2025
[10]

A theory for semantic channel coding with many-to-one source,

S. Ma, C. Zhang, H. Qi, H. Li, Y . Bi, G. Shi, and N. Al-Dhahir, “A theory for semantic channel coding with many-to-one source,” IEEE Transactions on Cognitive Communications and Networking, 2025

2025
[11]

Noiseless coding of correlated information sources,

D. SLEPIAN and J. K. WOLF, “Noiseless coding of correlated information sources,”IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 19, no. 4, p. 471, 1973

1973
[12]

The rate-distortion function for source coding with side information at the decoder,

A. D. Wyner and J. Ziv, “The rate-distortion function for source coding with side information at the decoder,”IEEE Trans. Inform. Theory, vol. 22, no. 1, pp. 1–10, 1976

1976
[13]

Coding for computing,

A. Orlitsky and J. R. Roche, “Coding for computing,”IEEE Transactions on Information Theory, vol. 47, no. 3, pp. 903–917, 2001

2001
[14]

The zero error capacity of a noisy channel,

C. Shannon, “The zero error capacity of a noisy channel,”IRE Transactions on Information Theory, vol. 2, no. 3, pp. 8–19, 1956. 27

1956
[15]

Fredman–koml´os bounds and information theory,

J. K ¨orner, “Fredman–koml´os bounds and information theory,”SIAM Journal on Algebraic Discrete Methods, vol. 7, no. 4, pp. 560–570, 1986

1986
[16]

The zero-error side information problem and chromatic numbers (corresp.),

H. Witsenhausen, “The zero-error side information problem and chromatic numbers (corresp.),”IEEE Transactions on Information Theory, vol. 22, no. 5, pp. 592–593, 1976

1976
[17]

Source coding and graph entropies,

N. Alon and A. Orlitsky, “Source coding and graph entropies,”IEEE Transactions on Information Theory, vol. 42, no. 5, pp. 1329–1339, 1996

1996
[18]

The semantics of predicate logic as a programming language,

M. H. Van Emden and R. A. Kowalski, “The semantics of predicate logic as a programming language,”Journal of the ACM (JACM), vol. 23, no. 4, pp. 733–742, 1976

1976
[19]

What you always wanted to know about Datalog (and never dared to ask),

S. Ceri, G. Gottlob, and L. Tanca, “What you always wanted to know about Datalog (and never dared to ask),”IEEE Transactions on Knowledge and Data Engineering, vol. 1, no. 1, pp. 146–166, 1989

1989
[20]

Abiteboul, R

S. Abiteboul, R. Hull, and V . Vianu,Foundations of Databases. Addison-Wesley, 1995

1995
[21]

Complexity and expressive power of logic programming,

E. Dantsin, T. Eiter, G. Gottlob, and A. V oronkov, “Complexity and expressive power of logic programming,”ACM Computing Surveys (CSUR), vol. 33, no. 3, pp. 374–425, 2001

2001
[22]

Datalog reasoning over compressed RDF knowledge bases,

P. Hu, J. Urbani, B. Motik, and I. Horrocks, “Datalog reasoning over compressed RDF knowledge bases,” inProceedings of the 28th ACM International Conference on Information and Knowledge Management (CIKM), 2019, pp. 2065–2068

2019
[23]

Maintenance of materialized views: Problems, techniques, and applications,

A. Gupta and I. S. Mumick, “Maintenance of materialized views: Problems, techniques, and applications,”IEEE Data Engineering Bulletin, vol. 18, no. 2, pp. 3–18, 1995

1995
[24]

Gupta, I

A. Gupta, I. S. Mumicket al.,Materialized views: techniques, implementations, and applications. MIT press Cambridge, MA, 1998

1998
[25]

Rate-distortion-perception tradeoff based on the conditional-distribution perception measure,

S. Salehkalaiabar, J. Chen, A. Khisti, and W. Yu, “Rate-distortion-perception tradeoff based on the conditional-distribution perception measure,”IEEE Transactions on Information Theory, vol. 70, no. 12, pp. 8432–8454, 2024

2024
[26]

Hodges,Model theory

W. Hodges,Model theory. Cambridge university press, 1993

1993
[27]

On the resemblance and containment of documents,

A. Z. Broder, “On the resemblance and containment of documents,” inProceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No. 97TB100171). IEEE, 1997, pp. 21–29

1997
[28]

A proof of the triangle inequality for the tanimoto distance,

A. H. Lipkus, “A proof of the triangle inequality for the tanimoto distance,”Journal of Mathematical Chemistry, vol. 26, no. 1, pp. 263–265, 1999

1999
[29]

Asymptotic equipartition property for a markov source having ambiguous alphabet,

T. Tasn ´adi and P. Vrana, “Asymptotic equipartition property for a markov source having ambiguous alphabet,”IEEE Transactions on Information Theory, vol. 69, no. 11, pp. 6897–6908, 2023

2023
[30]

Coding theorems for a discrete source with a fidelity criterion,

C. E. Shannonet al., “Coding theorems for a discrete source with a fidelity criterion,”IRE Nat. Conv. Rec, vol. 4, no. 142-163, p. 1, 1959

1959
[31]

Optimizing queries with materialized views,

S. Chaudhuri, R. Krishnamurthy, S. Potamianos, and K. Shim, “Optimizing queries with materialized views,” inIEEE International Conference on Data Engineering, 1995, pp. 190–200

1995

[1] [1]

A mathematical theory of communication,

C. E. Shannon, “A mathematical theory of communication,”Bell System Technical Journal, vol. 27, no. 3, pp. 379–423, 1948

1948

[2] [2]

T. M. Cover and J. A. Thomas,Elements of Information Theory, 2nd ed. John Wiley & Sons, 2006

2006

[3] [3]

Csisz ´ar and J

I. Csisz ´ar and J. K ¨orner,Information theory: coding theorems for discrete memoryless systems. Cambridge University Press, 2011

2011

[4] [4]

An outline of a theory of semantic information,

R. Carnap and Y . Bar-Hillel, “An outline of a theory of semantic information,” Research Laboratory of Electronics, MIT, Tech. Rep. Technical Report 247, 1952

1952

[5] [5]

Beyond transmitting bits: Context, semantics, and task-oriented communications,

D. G ¨und¨uz, Z. Qin, I. E. Aguerri, H. S. Dhillon, Z. Yang, A. Yener, K. K. Wong, and C.-B. Chae, “Beyond transmitting bits: Context, semantics, and task-oriented communications,”IEEE Journal on Selected Areas in Communications, vol. 41, no. 1, pp. 5–41, 2022

2022

[6] [6]

An indirect rate-distortion characterization for semantic sources: General model and the case of gaussian observation,

J. Liu, S. Shao, W. Zhang, and H. V . Poor, “An indirect rate-distortion characterization for semantic sources: General model and the case of gaussian observation,” inIEEE Transactions on Communications, vol. 70, no. 9, 2022, pp. 5946–5959

2022

[7] [7]

A mathematical theory of semantic communication,

K. Niu and P. Zhang, “A mathematical theory of semantic communication,”Journal on Communications, vol. 45, no. 6, pp. 7–59, 2024

2024

[8] [8]

Semantic rate-distortion theory with applications,

Y .-Q. Zhao, Z.-M. Ma, G. Y . Li, S. Yuan, T. Ye, and C. Zhou, “Semantic rate-distortion theory with applications,”arXiv preprint arXiv:2509.10061, 2025

work page arXiv 2025

[9] [9]

Extended blahut-arimoto algorithm for semantic rate-distortion function,

Y . Han, Y . Liu, Y . Sun, K. Niu, N. Ma, S. Cui, and P. Zhang, “Extended blahut-arimoto algorithm for semantic rate-distortion function,” Entropy, vol. 27, no. 6, p. 651, 2025

2025

[10] [10]

A theory for semantic channel coding with many-to-one source,

S. Ma, C. Zhang, H. Qi, H. Li, Y . Bi, G. Shi, and N. Al-Dhahir, “A theory for semantic channel coding with many-to-one source,” IEEE Transactions on Cognitive Communications and Networking, 2025

2025

[11] [11]

Noiseless coding of correlated information sources,

D. SLEPIAN and J. K. WOLF, “Noiseless coding of correlated information sources,”IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 19, no. 4, p. 471, 1973

1973

[12] [12]

The rate-distortion function for source coding with side information at the decoder,

A. D. Wyner and J. Ziv, “The rate-distortion function for source coding with side information at the decoder,”IEEE Trans. Inform. Theory, vol. 22, no. 1, pp. 1–10, 1976

1976

[13] [13]

Coding for computing,

A. Orlitsky and J. R. Roche, “Coding for computing,”IEEE Transactions on Information Theory, vol. 47, no. 3, pp. 903–917, 2001

2001

[14] [14]

The zero error capacity of a noisy channel,

C. Shannon, “The zero error capacity of a noisy channel,”IRE Transactions on Information Theory, vol. 2, no. 3, pp. 8–19, 1956. 27

1956

[15] [15]

Fredman–koml´os bounds and information theory,

J. K ¨orner, “Fredman–koml´os bounds and information theory,”SIAM Journal on Algebraic Discrete Methods, vol. 7, no. 4, pp. 560–570, 1986

1986

[16] [16]

The zero-error side information problem and chromatic numbers (corresp.),

H. Witsenhausen, “The zero-error side information problem and chromatic numbers (corresp.),”IEEE Transactions on Information Theory, vol. 22, no. 5, pp. 592–593, 1976

1976

[17] [17]

Source coding and graph entropies,

N. Alon and A. Orlitsky, “Source coding and graph entropies,”IEEE Transactions on Information Theory, vol. 42, no. 5, pp. 1329–1339, 1996

1996

[18] [18]

The semantics of predicate logic as a programming language,

M. H. Van Emden and R. A. Kowalski, “The semantics of predicate logic as a programming language,”Journal of the ACM (JACM), vol. 23, no. 4, pp. 733–742, 1976

1976

[19] [19]

What you always wanted to know about Datalog (and never dared to ask),

S. Ceri, G. Gottlob, and L. Tanca, “What you always wanted to know about Datalog (and never dared to ask),”IEEE Transactions on Knowledge and Data Engineering, vol. 1, no. 1, pp. 146–166, 1989

1989

[20] [20]

Abiteboul, R

S. Abiteboul, R. Hull, and V . Vianu,Foundations of Databases. Addison-Wesley, 1995

1995

[21] [21]

Complexity and expressive power of logic programming,

E. Dantsin, T. Eiter, G. Gottlob, and A. V oronkov, “Complexity and expressive power of logic programming,”ACM Computing Surveys (CSUR), vol. 33, no. 3, pp. 374–425, 2001

2001

[22] [22]

Datalog reasoning over compressed RDF knowledge bases,

P. Hu, J. Urbani, B. Motik, and I. Horrocks, “Datalog reasoning over compressed RDF knowledge bases,” inProceedings of the 28th ACM International Conference on Information and Knowledge Management (CIKM), 2019, pp. 2065–2068

2019

[23] [23]

Maintenance of materialized views: Problems, techniques, and applications,

A. Gupta and I. S. Mumick, “Maintenance of materialized views: Problems, techniques, and applications,”IEEE Data Engineering Bulletin, vol. 18, no. 2, pp. 3–18, 1995

1995

[24] [24]

Gupta, I

A. Gupta, I. S. Mumicket al.,Materialized views: techniques, implementations, and applications. MIT press Cambridge, MA, 1998

1998

[25] [25]

Rate-distortion-perception tradeoff based on the conditional-distribution perception measure,

S. Salehkalaiabar, J. Chen, A. Khisti, and W. Yu, “Rate-distortion-perception tradeoff based on the conditional-distribution perception measure,”IEEE Transactions on Information Theory, vol. 70, no. 12, pp. 8432–8454, 2024

2024

[26] [26]

Hodges,Model theory

W. Hodges,Model theory. Cambridge university press, 1993

1993

[27] [27]

On the resemblance and containment of documents,

A. Z. Broder, “On the resemblance and containment of documents,” inProceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No. 97TB100171). IEEE, 1997, pp. 21–29

1997

[28] [28]

A proof of the triangle inequality for the tanimoto distance,

A. H. Lipkus, “A proof of the triangle inequality for the tanimoto distance,”Journal of Mathematical Chemistry, vol. 26, no. 1, pp. 263–265, 1999

1999

[29] [29]

Asymptotic equipartition property for a markov source having ambiguous alphabet,

T. Tasn ´adi and P. Vrana, “Asymptotic equipartition property for a markov source having ambiguous alphabet,”IEEE Transactions on Information Theory, vol. 69, no. 11, pp. 6897–6908, 2023

2023

[30] [30]

Coding theorems for a discrete source with a fidelity criterion,

C. E. Shannonet al., “Coding theorems for a discrete source with a fidelity criterion,”IRE Nat. Conv. Rec, vol. 4, no. 142-163, p. 1, 1959

1959

[31] [31]

Optimizing queries with materialized views,

S. Chaudhuri, R. Krishnamurthy, S. Potamianos, and K. Shim, “Optimizing queries with materialized views,” inIEEE International Conference on Data Engineering, 1995, pp. 190–200

1995