What happens when information theory accounts for reasoning?

IBM Research scientists, including Luis Lastras, Jonathan Lenchner, Barry Trager, Mark Squillante, Chai Wah Wu, Ronald Fagin, and collaborators Wojciech Szpankowski and Alexander Gray, published a paper in the Proceedings of the National Academy of Sciences (PNAS) proposing a new information theory framework that accounts for reasoning, introducing a quantity called 'logical semantic entropy' to define communication limits when receivers can deduce additional facts. The framework extends Claude Shannon's 1948 sender-receiver model by giving the receiver reasoning capability, and includes a 'No Need to Know' result showing that the fundamental communication limit remains essentially unchanged even when the sender doesn't know what the receiver already knows.

What happens when information theory accounts for reasoning? Imagine a cataclysm wipes out humanity's scientific knowledge. Hard drives, the internet, books, movies — all about to be lost. But before everything is gone, you have the chance to leave a single sentence for future generations. What would you write? Physicist Richard Feynman once answered that hypothetical saying he would tell the future of humanity that all things are made of atoms. He believed that from that one sentence, an enormous amount of scientific knowledge could eventually be reconstructed. Feynman’s sentence is so valuable not because of the number of words or symbols it contains, rather everything a future scientist could infer from it. For nearly 80 years, the field of information theory has largely focused on transmitting information efficiently, rather than accounting for what people can deduce from that information. A new paper published https://www.pnas.org/doi/10.1073/pnas.2525600123 in the Proceedings of the National Academy of Sciences PNAS by IBM Research scientists Luis Lastras, Jonathan Lenchner, Barry Trager, Mark Squillante, Chai Wah Wu, Ronald Fagin, and collaborators Wojciech Szpankowski and Alexander Gray, proposes a new way of thinking about communication. It’s one that explicitly accounts for reasoning. Shannon's simplification In 1948, American scientist Claude Shannon transformed communications with a remarkably powerful idea. He realized that you could separate the meaning of a message from the problem of transmitting it efficiently. That abstraction led to modern information theory. Whether the message is a photograph, a phone call, a scientific paper, this blog, or the training data for a large language model, Shannon's framework focuses on how information can be represented, compressed, and transmitted reliably. The approach proved successful because communication networks don't need to understand what they're carrying. The internet doesn't care whether a packet contains a life-saving medical diagnosis or a picture of a cat. It simply moves the bits. Yet the humans at either end of a communication instinctively recognize that not all bits are equally valuable. A single bit generated by a faulty sensor may be worthless; a single bit from a reliable collision-avoidance system telling an autonomous vehicle to brake could be enormously valuable. The difference lies in what can be inferred from that information. Bringing reasoning into the model Lastras and his collaborators asked what would happen if communication systems explicitly accounted for logical deduction. Their framework extends Shannon's classic sender-receiver model https://en.wikipedia.org/wiki/Shannon%E2%80%93Weaver model by giving the receiver a reasoning capability. Rather than measuring only the information that is transmitted directly, the model also considers the additional knowledge that can be derived from what was received. The central insight the team arrived at is that communication becomes more efficient when reasoning is allowed. Instead of transmitting every fact individually, a sender can provide information that enables a receiver to infer many additional facts. In other words, the value of a message depends not only on what it says, but also on what it allows someone to conclude. To capture this mathematically, the researchers derived a new quantity, called ‘logical semantic entropy,’ which defines the fundamental communication limits in the presence of reasoning capabilities. A trio of theories The team’s framework produced several results that challenge conventional intuition. One finding, which the researchers call the "No Need to Know" result, examines what happens when a sender doesn't know exactly what a receiver already knows. Surprisingly, they found that the fundamental communication limit remains essentially unchanged. This is unexpected because their communication inherently drops details unnecessary for logical deduction using lossy compression — a setting where knowing what the recipient already understands usually helps save data. A second finding led to what they named the "Less Is More" paradox. They borrowed two fictional characters commonly used in cryptography theory, Alice and Bob https://en.wikipedia.org/wiki/Alice and Bob . If Alice wants Bob to learn only a particular subset of her knowledge while using as few bits as possible, the most efficient strategy can end up teaching Bob more than intended. By using broad, pre-set shorthand patterns to solve multiple scenarios at once, Alice dramatically cuts down on the total data sent. However, because these patterns cover extra ground, sharing one necessarily reveals more background context to Bob than necessary, creating a potential security risk. The researchers also explored a model for correcting mistaken beliefs. Their analysis suggests that the communication cost of correcting incorrect information can become dramatically larger than the cost of filling a simple knowledge gap. By mathematically modeling communication when a receiver holds beliefs that directly contradict the sender's facts, the researchers calculated the extra data cost required to correct someone who is wrong versus informing someone who is just unaware of the facts. They found that as the receiver becomes more specific and strongly opinionated in their incorrect beliefs, the relative cost to guide them back to the truth grows to infinity. From side project to a larger conversation For Lastras, the project wasn't a short-term initiative. The work began as a personal research effort pursued largely in the background with a small team. Over several years, he devoted time each week to exploring a question that had remained unresolved since the early days of information theory. That small team slowly grew as collaborators helped reach deeper into the field of mathematical logic to explore the topic in greater depth. Modern AI systems increasingly depend not only on processing information, but also on reasoning over it. While Shannon's original framework remains the foundation of digital communication, Lastras and team argue that future intelligent systems may benefit from a richer theory that accounts for what can be inferred from information — not simply how efficiently that information can be transmitted. In that sense, the paper extends a conversation that began in 1948 and asks a new question for the age of intelligent systems: What if communication theory measured not just the data sent, but the background knowledge required to make sense of it? Related posts - ReleaseMike Murphy Introducing the first sub-1 nanometer node chip — the smallest, most powerful chip technology in the world /blog/sub-1nm-node-chips NewsMike Murphy Building AI more like software /blog/granite-libraries-project-switch ReleaseMike Murphy Renowned mathematician Subhash Khot joins IBM Research /blog/subhash-khot-ibm NewsMike Murphy- Algorithms Mathematical Sciences /topics/mathematical-sciences Quantum Algorithms /quantum-computing