Pith. sign in

REVIEW 3 major objections 6 minor 42 references

Breaking through the classical Shannon entropy limit: A new frontier through logical semantics

T0 review · 3 major / 6 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A new theorem shows that when the receiver can perform logical deduction, the fundamental communication cost is controlled by a two-variable 'logical semantic entropy' rather than by classical symbol entropy.

desk verdict A well-written extended abstract for a companion paper: the model and the Lambda function are genuinely interesting, but the central theorem and all details live in [24], so the claim is unverifiable from this text alone. read the letter →

arxiv 2501.00612 v1 pith:SNG65FEH submitted 2024-12-31 cs.IT math.IT

Luis A. Lastras , Barry M. Trager , Jonathan Lenchner , Wojciech Szpankowski , Chai Wah Wu , Mark S. Squillante , Alexander Gray This is my paper · ORCID
classification cs.ITmath.IT MSC 94A1594A1703B05
keywords semanticinformationtheorylogicalentropydeductivereasoningkernelofalogicstatementsourcecodingwithsideShannonlossycompressioncommunicationcomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper tries to show that if a receiver can perform deductive reasoning, the communication cost needed to convey a logical statement is no longer governed by the classical entropy of the symbols, but by a new two-variable quantity called the logical semantic entropy. For a sender statement, a query, and receiver knowledge with normalized expected kernel sizes $p_s$, $p_q$, and $p_r$, the paper proves matching upper and lower bounds: the least possible average communication is $\Lambda(p_s, p_r - p_q)$, up to a small term that vanishes as the number of propositions grows. This matters because it gives a precise information-theoretic account of how semantics and deduction add value to transmitted bits, with practical codes showing savings that are integer multiples of classical compression. The same bound holds whether or not the sender knows the receiver's knowledge, a striking 'no need to know' property.

What carries the argument

The load-bearing object is the logical semantic entropy $\Lambda(a,b) = a\log_2\left(\frac{a+b}{a}\right) + b\log_2\left(\frac{a+b}{b}\right)$, a two-variable entropy-like function defined on normalized kernel sizes. It is paired with the kernel $\kappa(s)$, the set of truth assignments that satisfy a logic statement $s$; one statement entails another exactly when the first kernel is a subset of the second. The function $\Lambda$ plays the role that Shannon entropy plays in symbol compression: it serves as both the achievability rate and the converse bound, with the argument $p_r - p_q$ measuring the gap between receiver knowledge and query that the message must bridge.

What would settle it

To falsify Theorem 1, fix a small $m$ (say $m = 4$) and an i.i.d. kernel model with specified $p_s, p_q, p_r$, enumerate all possible protocols between Alice and Bob, and compare the minimal expected cost to $\Lambda(p_s, p_r - p_q)$; a gap larger than the stated $O(m/2^m)$ term in either direction would refute the matching bounds. A protocol that beats the lower bound for even one such distribution would also refute the theorem.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central claim is Theorem 1: for any distribution over $(S_m, Q_m, R_m)$ satisfying $S_m \vdash Q_m$ and $Q_m \vdash R_m$, with normalized expected kernel sizes $p_s, p_q, p_r$, when Alice knows $R_m$ there is a protocol whose normalized average communication cost is at most $\Lambda(p_s, p_r - p_q) + O(m/2^m)$, and under an i.i.d. model for how kernels are generated every protocol costs at least $\Lambda(p_s, p_r - p_q)$. When Alice does not know $R_m$, the same two-sided characterization holds in the case $Q_m = S_m$. The paper interprets this as showing that logical semantic entropy, not symbol entropy, is the right measure of communication for semantically equipped receivers.

Load-bearing premise

The whole bound rests on the assumption that the receiver's deductive engine is strongly sound and strongly complete, meaning Bob can in principle prove every logical consequence of what he knows; if real proof systems are incomplete or bounded in computation, the predicted communication savings can shrink or disappear.

Editorial extensions

If this is right

  • If the theorem holds, the minimum communication cost in a deductive setting is exactly $\Lambda(p_s, p_r - p_q)$ for a wide class of distributions, so the classical entropy lower bound is not fundamental once deduction is available.
  • The same limit applies whether or not the sender knows the receiver's knowledge, mirroring side-information coding but now in a lossy, semantics-based setting.
  • Sending the query can cost less than sending either the query or the sender's full knowledge, while still enabling the receiver to prove more than the query asks for.
  • When sender and receiver disagree, the ultimate cost becomes $\Lambda(p_s, 1 - p_r - p_s)$; as the receiver's belief approaches the sender's knowledge, correcting misinformation becomes arbitrarily more expensive than informing ignorance.
  • The result extends beyond propositional logic to first-order logic over finite models, so the framework applies to richer deductive systems.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If deductive completeness is weakened to resource-bounded proof search, the predicted $\Lambda$ rate will undershoot actual cost; quantifying that gap is a natural next step.
  • The 'less is more' effect suggests a privacy trade-off: the most efficient way to let the receiver prove a target query may also let the receiver prove unintended consequences, something security protocols should account for.
  • The hashing-based scheme for the case where the sender does not know the receiver's knowledge can be read as a distributed reasoning protocol, and may extend to multi-party settings where several receivers hold different background facts.
  • A direct empirical test would compare measured communication cost of the proposed protocol against $\Lambda$ for small $m$ across random distributions, checking that the gap matches the stated $O(m/2^m)$ term.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The manuscript proposes a framework for semantic communication in which Alice and Bob are equipped with a logic-based deductive engine. Alice's knowledge S_m, the query Q_m, and Bob's knowledge R_m are modeled as random logic statements over m propositional variables, with expected normalized kernel sizes p_s, p_q, p_r. Theorem 1 claims that, under entailment conditions S_m ⊢ Q_m and Q_m ⊢ R_m, an algorithm exists whose normalized expected communication cost is at most Λ(p_s, p_r - p_q) + O(m/2^m) when Alice knows R_m, with a matching lower bound under an additional 'i.i.d.' constraint, and that the same limit holds when Alice does not know R_m in the case Q_m = S_m. The paper also reports practical codes in Figure 2, discusses a 'less is more' phenomenon, and compares the cost of correcting misinformation with ignorance. The central theorem is stated without proof, and all definitions, derivations, and empirical code details are deferred to the companion paper [24].

Significance. If the claimed results are correct, they would provide a rigorous Shannon-style account of the communication advantage of deductive inference, with a nontrivial formula Λ and a Slepian-Wolf-like 'no need to know' phenomenon. The conceptual contribution is interesting and the paper is well positioned relative to Carnap-Bar-Hillel, rate-distortion theory, and Slepian-Wolf/Wyner-Ziv coding. However, the submission as it stands is a research announcement: Theorem 1 is not proved in this manuscript, the 'i.i.d.' model is not defined, and the practical codes are described only by reference to [24]. No code, data, or error analysis is provided, so the central mathematical and empirical claims cannot be independently verified.

major comments (3)
  1. [Overview of results (Theorem 1)] Theorem 1 is the paper's central result, yet it is stated with no proof or derivation. The text immediately defers the upper-bound architecture to [24], states that 'Precise definitions' of the lower-bound model are in [24], and later says the argument for optimality is 'fully addressed in (24)'. Because the hypotheses, the O(m/2^m) term, and the lower-bound model are not defined or established in this manuscript, the claimed communication limits are unverifiable from the submission.
  2. [Empirical validation (Figure 2)] The 'empirical validation' in Figure 2 cannot be audited: the practical semantic codes are 'fully described in (24)', the competing classic-compression baseline relies on a decision-tree representation 'explained in (24)', and no code, data, or error analysis is included. The claimed integer-multiple gains over classical compression therefore rest entirely on external material that is not part of this submission.
  3. [The price of misinformation] The claimed misinformation limit Λ(p_s, 1-p_r-p_s) is stated without derivation and is not covered by Theorem 1, which assumes S_m ⊢ Q_m and Q_m ⊢ R_m. The subsequent 'price of misinformation' ratio and its divergence as p_r → p_s depend on this unproved limit, so the conclusion is not supported by the material in this paper.
minor comments (6)
  1. [Mathematical setup] The symbol ⊢ is used both for semantic entailment and for provability ('can be inferred from'), but no formal consequence relation or proof system is defined; the paper should clarify whether it is using semantic entailment, syntactic provability, or both.
  2. [Overview of results (Theorem 1)] The phrase 'normalized average cost in total bits exchanged' is ambiguous: if the cost is normalized by m, the formula for Λ in Eq. (1) gives a quantity in bits and the meaning of the O(m/2^m) correction term needs further explanation.
  3. [Mathematical setup] The phrase 'strongly sound and exhibits a type of strong completeness' is never defined; for propositional logic the authors could simply state that the logic is sound and complete, which would make the assumption precise.
  4. [Overview of results] There is a typo: 'This results holds more generally beyond Propositional Logic' should read 'This result holds more generally beyond Propositional Logic'.
  5. [Figure 2] The caption of Figure 2(a) does not specify the units of the reported gains; the text refers to a 'Shannon bound' only in the context of Figure 2(b), so the reader cannot tell whether the two panels are measured on the same scale.
  6. [References] Reference [24] is load-bearing for the proof, the definitions, and the empirical results, but the manuscript does not state whether [24] is published, under review, or available as a preprint; this status is essential for a referee to evaluate the dependency.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: central coding bounds are substantive; proof is deferred to same-author companion, a verifiability gap rather than a circular reduction.

full rationale

The claimed result (Theorem 1) is a genuinely substantive coding statement: for distributions satisfying S_m⊢Q_m⊢R_m, it asserts an upper bound Λ(p_s,p_r−p_q)+O(m/2^m) and a matching lower bound under an i.i.d. constraint. The function Λ is defined in Eq. (1) as a scaled conditional entropy, independently of the communication protocol, and p_s,p_q,p_r are model parameters describing expected normalized kernel sizes; the bounds are not identities forced by these definitions. No parameter is fitted to data and then renamed a prediction; the practical codes in Figure 2 are implementations compared against Λ, not the source of Λ. The manuscript's derivation chain is, however, incomplete: the proof of Theorem 1 and the precise i.i.d. model are explicitly deferred to the same-author companion [24] ('Arguing why and how these techniques result in such an optimal systems is beyond the scope of this paper and fully addressed in (24)'; 'The precise definitions can be found in (24)'). This makes the central claim unverifiable from the submitted text and gives the self-citation a structural, proof-locating role. But deferring a proof to a longer companion paper is a completeness/verifiability issue, not a circular reduction: the manuscript nowhere defines Λ in terms of the communication cost, nor equates the claimed bound with its inputs by construction. The 'less is more' and misinformation formulas are stated as consequences of the same external theorem, not as re-definitions of the conclusion. Therefore no significant circularity is found, with the caveat that the paper is not self-contained.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on logical soundness and completeness, the entailment model S entails Q entails R, and a uniform i.i.d. kernel model for lower bounds. These are domain assumptions. There are no fitted parameters and no invented entities; Lambda is a defined function, not a hidden degree of freedom.

assumptions (4)
  • domain assumption The underlying logic is strongly sound and exhibits a type of strong completeness
    The theorem relies on the receiver being able to prove all logical entailments. Stated in the Mathematical setup section: results hold for logic that is strongly sound and exhibits a type of strong completeness.
  • domain assumption The random statements satisfy entailment conditions S_m entails Q_m and Q_m entails R_m
    This structural correlation between Alice's and Bob's knowledge is assumed throughout and is stated in the Correlated world observations section. If it fails, the clean kernel size picture does not hold.
  • domain assumption For lower bounds, kernel elements are drawn i.i.d. from a subsuming kernel
    Theorem 1 states this under an additional i.i.d. constraint. This uniformity condition is not justified for real logic statements and is needed for the lower bound, so it is a substantive assumption.
  • domain assumption Expected normalized kernel sizes p_s, p_q, p_r are sufficient summary statistics of the joint distribution
    The bounds are phrased purely in terms of these expectations, implying that the internal geometry of kernels beyond size is irrelevant. This is assumed rather than proved in this text.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Breaking through the classical Shannon entropy limit: A new frontier through logical semantics." pith.science (2026). https://pith.science/paper/SNG65FEH

@misc{pith2026250100612,
  author       = {Pith},
  title        = {Pith review of: Breaking through the classical Shannon entropy limit: A new frontier through logical semantics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SNG65FEH}},
  note         = {Machine review of arXiv:2501.00612}
}
read the original abstract

Information theory has provided foundations for the theories of several application areas critical for modern society, including communications, computer storage, and AI. A key aspect of Shannon's 1948 theory is a sharp lower bound on the number of bits needed to encode and communicate a string of symbols. When he introduced the theory, Shannon famously excluded any notion of semantics behind the symbols being communicated. This semantics-free notion went on to have massive impact on communication and computing technologies, even as multiple proposals for reintroducing semantics in a theory of information were being made, notably one where Carnap and Bar-Hillel used logic and reasoning to capture semantics. In this paper we present, for the first time, a Shannon-style analysis of a communication system equipped with a deductive reasoning capability, implemented using logical inference. We use some of the most important techniques developed in information theory to demonstrate significant and sometimes surprising gains in communication efficiency availed to us through such capability, demonstrated also through practical codes. We thus argue that proposals for a semantic information theory should include the power of deductive reasoning to magnify the value of transmitted bits as we strive to fully unlock the inherent potential of semantics.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

42 extracted references · 34 canonical work pages

  1. [24]

    L. A. Lastras, et al., Towards a Unification of Logic and Information Theory (2024), https: //arxiv.org/abs/2301.10414

    work page Pith review arXiv 2024

  2. [1]

    Feynman, R

    R. Feynman, R. Leighton, M. Sands, E. Hafner, The Feynman Lectures on Physics; Vol. I (Addison-Wesley) (1965)

    work page 1965

  3. [2]

    C. E. Shannon, A Mathematical Theory of Communication. Bell System Technical Journal27, 379–423, 623–656 (1948)

    work page 1948

  4. [3]

    Szpankowski, A

    W. Szpankowski, A. Grama, Frontiers of Science Information: Shannon Meets Turing. IEEE Computer (51), 32–42 (2018)

    work page 2018

  5. [4]

    Bar-Hillel, R

    Y. Bar-Hillel, R. Carnap, Semantic information. The British J. Philosophy of Science 4, 147– 157 (1953)

    work page 1953

  6. [5]

    Shannon, The lattice theory of information

    C. Shannon, The lattice theory of information. Transactions of the IRE Professional Group on Information Theory 1 (1), 105–107 (1953), doi:10.1109/TIT.1953.1188572

    work page arXiv 1953

  7. [6]

    Floridi, Outline of a Theory of Strongly Semantic Information

    L. Floridi, Outline of a Theory of Strongly Semantic Information. Minds and Machines 14 (2004), doi:10.1023/B:MIND.0000021684.50925.c9

    work page arXiv 2004

  8. [7]

    Devlin, Logic and Information (Cambridge University Press) (1991)

    K. Devlin, Logic and Information (Cambridge University Press) (1991)

    work page 1991

Show all 42 references
  1. [8]

    Bao, et al

    J. Bao, et al. , Towards a theory of semantic communication, in IEEE Network Science Workshop (IEEE Computer Society, Los Alamitos, CA, USA) (2011), pp. 110–117, doi: 10.1109/NSW.2011.6004632, https://doi.ieeecomputersociety.org/10.1109/NSW. 2011.6004632

    2011

  2. [9]

    Bao, et al., Towards a theory of semantic communication, in Extended Technical Report (2011), https://apps.dtic.mil/sti/tr/pdf/ADA544137.pdf

    J. Bao, et al., Towards a theory of semantic communication, in Extended Technical Report (2011), https://apps.dtic.mil/sti/tr/pdf/ADA544137.pdf

    2011

  3. [10]

    J. Liu, W. Zhang, H. V. Poor, A Rate-Distortion Framework for Characterizing Semantic Information, in IEEE International Symposium on Information Theory (2021)

    2021

  4. [11]

    J. Liu, S. Shao, W. Zhang, H. V. Poor, An Indirect Rate-Distortion Characterization for Se- mantic Sources: General Model and the Case of Gaussian Observation. IEEE Transactions on Communications 70 (9), 5946–5959 (2022), doi:10.1109/TCOMM.2022.3194978. 14

    2022

  5. [12]

    Y. Shao, Q. Cao, D. G¨ und¨ uz, A Theory of Semantic Communication. IEEE Transactions on Mobile Computing 23, 12211–12228 (2022), https://api.semanticscholar.org/ CorpusID:254247048

    2022

  6. [13]

    Guo, et al., Semantic Compression with Side Information: A Rate-Distortion Perspective (2022)

    T. Guo, et al., Semantic Compression with Side Information: A Rate-Distortion Perspective (2022)

    2022

  7. [14]

    P. A. Stavrou, M. Kountouris, The Role of Fidelity in Goal-Oriented Semantic Communication: A Rate Distortion Approach.IEEE Transactions on Communications71 (7), 3918–3931 (2023), doi:10.1109/TCOMM.2023.3274122

    2023

  8. [15]

    G¨ und¨ uz,et al., Beyond Transmitting Bits: Context, Semantics, and Task-Oriented Com- munications

    D. G¨ und¨ uz,et al., Beyond Transmitting Bits: Context, Semantics, and Task-Oriented Com- munications. IEEE Journal on Selected Areas in Communications 41 (1), 5–41 (2023), doi: 10.1109/JSAC.2022.3223408

    2023

  9. [16]

    K. Niu, P. Zhang, A Mathematical Theory of Semantic Communication (2024), https:// arxiv.org/abs/2401.13387

    2024 arXiv

  10. [17]

    H. Yu, J. A. Evans, L. R. Varshney, Information lattice learning. J. Artif. Intell. Res. 77, 971–1019 (2023)

    2023

  11. [18]

    H. Yu, L. R. Varshney, Semantic Compression with Information Lattice Learning. 2024 IEEE International Symposium on Information Theory Workshops (ISIT-W)pp. 1–6 (2024), https: //api.semanticscholar.org/CorpusID:268889753

    2024

  12. [19]

    C. E. Shannon, Coding Theorems for a Discrete Source With a Fidelity Criterion, in Claude E. Shannon: Collected Papers (Wiley-IEEE Press), pp. 325–350 (1993), doi: 10.1109/9780470544242.ch21

    1993 doi

  13. [20]

    T. Berger, Rate Distortion Theory: A Mathematical Basis for Data Compression, Prentice-Hall electrical engineering series (Prentice-Hall) (1971), https://books.google.com/books? id=-HV1QgAACAAJ

    1971

  14. [21]

    Barwise, Model Theoretic Logics: Concepts and Aims, inModel Theoretic Logics, J

    J. Barwise, Model Theoretic Logics: Concepts and Aims, inModel Theoretic Logics, J. Barwise, S. Feferman, Eds. (Cambridge University Press), pp. 1–24 (1985). 15

    1985

  15. [22]

    Slepian, J

    D. Slepian, J. Wolf, Noiseless coding of correlated information sources. IEEE Transactions on Information Theory 19 (4), 471–480 (1973), doi:10.1109/TIT.1973.1055037

    1973

  16. [23]

    Wyner, J

    A. Wyner, J. Ziv, The rate-distortion function for source coding with side information at the decoder. IEEE Transactions on Information Theory 22 (1), 1–10 (1976), doi:10.1109/TIT. 1976.1055508

    1976

  17. [25]

    A. C.-C. Yao, Some complexity questions related to distributive computing(Preliminary Re- port), STOC ’79 (Association for Computing Machinery, New York, NY, USA) (1979), p. 209–213, doi:10.1145/800135.804414, https://doi.org/10.1145/800135.804414

    1979

  18. [26]

    Cover, Enumerative source encoding

    T. Cover, Enumerative source encoding. IEEE Transactions on Information Theory 19 (1), 73–77 (1973), doi:10.1109/TIT.1973.1054929

    1973

  19. [27]

    Elias, Universal codeword sets and representations of the integers

    P. Elias, Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory 21 (2), 194–203 (1975), doi:10.1109/TIT.1975.1055349

    1975

  20. [28]

    Breitbart, H

    Y. Breitbart, H. Hunt, D. Rosenkrantz, On the size of binary decision diagrams repre- senting Boolean functions. Theoretical Computer Science 145 (1), 45–69 (1995), doi:https: //doi.org/10.1016/0304-3975(94)00181-H, https://www.sciencedirect.com/science/ article/pii/030439759400181H

    1995

  21. [29]

    Mehta, V

    D. Mehta, V. Raghavan, Decision tree approximations of Boolean functions.Theoretical Com- puter Science 270 (1), 609–623 (2002), doi:https://doi.org/10.1016/S0304-3975(01)00011-1, https://www.sciencedirect.com/science/article/pii/S0304397501000111

    2002 doi

  22. [30]

    O’Donnell, M

    R. O’Donnell, M. Saks, O. Schramm, R. Servedio, Every decision tree has an influential variable, in 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05) (2005), pp. 31–39, doi:10.1109/SFCS.2005.34

    2005 doi

  23. [31]

    Zamir, The rate loss in the Wyner-Ziv problem

    R. Zamir, The rate loss in the Wyner-Ziv problem. IEEE Transactions on Information Theory 42 (6), 2073–2084 (1996), doi:10.1109/18.556597. 16

    1996 doi

  24. [32]

    A. Orlitsky, Interactive communication: balanced distributions, correlated files, and average- case complexity, inProceedings 32nd Annual Symposium of Foundations of Computer Science (1991), pp. 228–238, doi:10.1109/SFCS.1991.185373

    1991

  25. [33]

    R. E. Blahut, Algebraic codes for data transmission(Cambridge University Press) (2003)

    2003

  26. [34]

    Richardson, R

    T. Richardson, R. Urbanke, Modern Coding Theory (Cambridge University Press) (2008)

    2008

  27. [35]

    D. J. MacKay, Information Theory, Inference, and Learning Algorithms(Cambridge University Press) (2003)

    2003

  28. [36]

    Immerman, Descriptive Complexity (Springer, New York USA) (1999)

    N. Immerman, Descriptive Complexity (Springer, New York USA) (1999)

    1999

  29. [37]

    Fagin, J

    R. Fagin, J. Y. Hailpern, Y. Moses, M. Vardi,Reasoning about Knowledge(MIT Press) (2004)

    2004

  30. [38]

    V ¨a¨an¨anen, Second-order and Higher-order Logic, in The Stanford Encyclopedia of Philosophy , E

    J. V ¨a¨an¨anen, Second-order and Higher-order Logic, in The Stanford Encyclopedia of Philosophy , E. N. Zalta, Ed. (Metaphysics Research Lab, Stanford University), Fall 2021 ed. (2021), https://plato.stanford.edu/archives/fall2021/entries/ logic-higher-order/

    2021

  31. [39]

    N. J. Nilsson, Probabilistic logic. Artificial Intelligence 28 (1), 71–87 (1986)

    1986

  32. [40]

    Cozman, Credal networks

    F. Cozman, Credal networks. Artificial Intelligence 120 (2), 199–233 (2000)

    2000

  33. [41]

    Fagin, R

    R. Fagin, R. Riegel, A. Gray, Foundations of Reasoning with Uncertainty via Real-valued Logics. Proceedings of the National Academy of Sciences 121 (21) (2024)

    2024

  34. [42]

    Grunwald, P

    P. Grunwald, P. Vitanyi, Shannon Information and Kolmogorov Complexity (2004), https: //arxiv.org/abs/cs/0410002. Acknowledgments The authors acknowledge helpful conversations with the following individuals: Ron Fagin, Phokion Kolaitis, Jason Rute, Kush Varshney and Mark Wegma...

    2004 arXiv

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.