What is it about?

Not every bit of information is created equal. A reliable heart rate sensor can help a doctor deduce the right course of action, while a stream of random bits from a faulty one helps no one. Shannon's theory deliberately sets meaning aside, a choice that makes modular communication systems possible. By its measure, though, the random stream is the costlier one to transmit. The question at the heart of this paper: can communication become more efficient if the goal shifts from recovering a message exactly to being able to deduce all, or some, of the facts a sender knows? The answer is yes. Building on Shannon's information theory, we derive simple expressions for the new fundamental limits. They rest on a quantity we call logical semantic entropy, which measures the cost of describing the essentials so that the receiver can deduce what it needs. We also show practical schemes that, while not yet reaching these limits in general, come much closer to them than conventional approaches, which need two to four times the minimum number of bits.

Featured Image

Why is it important?

Computers don't just receive information; they act on it. More and more, the receiver is an autonomous system that draws its own conclusions from what it's told, whether that's an AI agent, a medical device or a car. How to make that communication efficient is a foundational question in the engineering of these systems. Our article doesn't solve this in full generality: it works with propositional and first-order logic over a finite set of possibilities, which is far from the expressive power of real software. But it is a concrete step forward. It gives crisp, closed-form expressions for a range of setups, and some of the conclusions are surprising. For example, in our setup the sender can be almost as efficient without knowing what the receiver already knows as it would be if it did. When the receiver needs only some of the sender's facts, the best strategy sends something that lets the receiver deduce more than it asked for, yet costs fewer bits than sending only the requested facts. Other results confirm, and put numbers on, what intuition suggests: correcting a receiver who believes something false can cost far more than informing one who simply doesn't know, and the gap grows without limit as the receiver becomes more certain of its false belief. Turning these results into gains in real systems will take more work along the path this article opens.

Perspectives

This article is the result of a long-term collaboration that started with a fascinating question: how much information is contained in a logic statement? Over 2-3 years, it turned into a learning experience in which experts in information theory and mathematical logic taught each other a great deal, and gradually distilled their insights to the point where they were ready for publication. For me, it was a personally rewarding experience. One of the key tools we used, rate distortion theory, was the focus of my PhD work under the late information theorist Toby Berger, who wrote the classic textbook on the subject. I often thought of him during this work, and I hope that continuing to develop this important branch of information theory honors his memory.

Luis Lastras
IBM Research

Read the Original

This page is a summary of: Fundamental limits incorporating logical reasoning into Shannon’s information theory, Proceedings of the National Academy of Sciences, August 2026, Proceedings of the National Academy of Sciences,
DOI: 10.1073/pnas.2525600123.
You can read the full text:

Read

Resources

Contributors

The following have contributed to this page