Rate-Distortion Theory for Deductive Sources under Closure Fidelity

Jianfeng Xu

arxiv: 2604.15698 · v4 · pith:4UJ7UZKEnew · 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

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 shared proof system, and reconstruction fidelity is measured by preservation of deductive closure rather than by symbolwise equality. Fixing the proof system and a canonical scan order yields a decomposition of the source alphabet into an irredundant core and redundant stored consequences. At zero distortion, each core symbol induces a set of distortion-free reconstructions. In the nonconfusable (disjoint-core) regime, 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. In the general confusable-core regime, we characterise the exact zero-distortion rate via a hypergraph-entropy quantity induced by jointly realisable core subsets, with a reduction to Korner-style graph entropy under a natural pairwise realisability condition. 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. Finally, 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 characterisation. Under an additional order-robustness assumption identifying the chosen core with the order-free essential set, this characterisation interpolates between classical symbolwise compression and unconstrained deductive compression.

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

Rate-Distortion Theory for Deductive Sources under Closure Fidelity

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)