Analysis of Semantic Communication for Logic-based Hypothesis Deduction

Ahmet Faruk Saz, Siheng Xiong, and Faramarz Fekri · 2025

Read Analysis of Semantic Communication for Logic-based Hypothesis Deduction by Ahmet Faruk Saz, Siheng Xiong, and Faramarz Fekri (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-21755.txt.

Introduction

Ahmet Faruk Saz, Siheng Xiong, and Faramarz Fekri analyze how to send just enough evidence for a receiver to pick the right hypothesis, in this 2025 paper. The receiver holds several guesses about the state of the world, stated in first-order logic. The sender has partial evidence but not the ground truth, and a tight budget for messages.

The goal is framed as matching the sender's belief spread at the receiver's end. Math shortcuts turn that goal into a resource allocation problem with a water-filling style answer. The authors prove the answer is best possible despite the problem's awkward shape. Message plans for one round and many rounds follow. Tests beat random and earlier selection methods.

Catalog record

CREATORAhmet Faruk Saz, Siheng Xiong, and Faramarz Fekri
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-21755

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Analysis of Semantic Communication for Logic-based Hypothesis Deduction Thanks: This work is supported by National Science Foundation under award ID MLWiNS-2003002 and a Gift from Intel Co. Ahmet Faruk Saz, Siheng Xiong, and Faramarz Fekri Abstract This work presents an analysis of semantic communication in the context of First-Order Logic (FOL)-based deduction. Specifically, the receiver holds a set of hypotheses about the State of the World (SotW), while the transmitter has incomplete evidence about the true SotW but lacks access to the ground truth. The transmitter aims to communicate limited information to help the receiver identify the hypothesis most consistent with true SotW. We formulate the objective as approximating the posterior distribution at the transmitter to the receiver. Using Stirling’s approximation, this reduces to a constrained, finite-horizon resource allocation problem. Applying the Karush-Kuhn-Tucker conditions yields a truncated water-filling solution. Despite the problem’s non-convexity, symmetry and permutation invariance ensure global optimality. Based on this, we design message selection strategies, both for single- and multi- round communication, and model the receiver’s inference as an m m -ary Bayesian hypothesis testing problem. Under the Maximum A Posteriori (MAP) rule, our communication strategy achieves optimal performance within budget constraints. We further analyze convergence rates and validate the theoretical findings through experiments, demonstrating reduced error over random selection and prior methods. I Introduction Semantic communication redefines data transmission by prioritizing meaning over raw data, offering critical benefits for intelligent services and next-generation networks like 6G. Previous works have explored semantic compression techniques [ 1 ] , knowledge-enhanced transmission strategies [ 2 ] , and semantic-aware resource allocation. These efforts have shown the promise of semantic communication for improving efficiency and robustness across diverse intelligent systems and communication environments. While these works largely emphasize semantic compression and transmission optimization, our focus shifts to a distinct but complementary problem: logical deduction of hypotheses under resource constraints. In many real-world scenarios—such as distributed sensing or privacy-sensitive environments—the transmitter lacks knowledge of the receiver’s precise goal. Consequently, the challenge becomes transmitting the most semantically content-informative message possible. This framework has the potential to empower a variety of applications involving logical deduction: drones in search-and-rescue operations can share logical summaries of their local observations [ 3 ] ; wearable health monitors can transmit structured symptom patterns to support remote diagnostics [ 4 ] ; autonomous vehicles can communicate compact causal cues like “reduced traction ahead” [ 4 ] ; and legal or educational systems can tailor logic-based explanations to user intent [ 5 ] . This paper builds on prior work that introduced a First-Order Logic (FOL)-based semantic communication framework for deductive inference. Drawing from the foundational ideas of Carnap [ 6 ] and Hintikka [ 7 ] , we treated FOL as a formal language for representing and transmitting structured knowledge. While classical semantic systems were computationally intractable, our earlier work [ 8 , 9 , 10 ] addressed scalability by framing communication as a boolean-satisfiability model selection problem. Using model counting, we developed a bit-efficient, task-agnostic transmission strategy that enabled logical inference at the receiver, even when the transmitter lacked access to the downstream task. In this paper, we take our efforts a step further and formalize semantic communication as a posterior distribution alignment problem over a logical space structured by First-Order Logic (FOL). The world is represented using a hierarchy of constituents, attributive constituents, and Q-sentences, and uncertainty is quantified via inductive logical probability over these structures. The transmitter, observing partial evidence about the true state, aims to select messages that maximize semantic informativeness—quantified via Carnap’s cont-information—without access to the receiver’s hypothesis set. We show that optimal message selection reduces to minimizing the KL divergence between transmitter and receiver posteriors over constituents, which in turn becomes a constrained resource allocation problem over observed attributive constituents. To make the analysis tractable, we apply Stirling’s approximation and exploit the symmetry of the resulting objective, deriving a globally optimal solution using a truncated water-filling algorithm. We extend this framework to multi-round communication, showing that repeated optimal allocations converge to an ideal posterior configuration under cumulative constraints. This formulation enables principled message selection under realistic communication budgets and, under the Bayesian MAP criterion at the receiver, minimizes error in hypothesis deduction. We derive the convergence rate for the multi-round setup and show that the algorithm converges linearly. Finally, we validate our theoretical findings on a custom deduction dataset, demonstrating superior performance in hypothesis selection compared to prior work, greedy selection, and random baselines. The contribution of this paper is twofold. First, it introduces a formal connection between semantic communication and logical inference by framing message transmission as the problem of posterior distribution alignment between transmitter and receiver in a First-Order Logic framework. This perspective distinguishes the present work from prior approaches that emphasize semantic compression or task-specific heuristics, and provides a principled way to quantify semantic informativeness through Carnap’s cont-information and distributional divergence. Second, we develop and analyze a resource allocation formulation of this problem, showing that the optimal message composition follows a truncated water-filling solution. We establish that this strategy achieves global optimality in the relaxed setting and extend it to multi-round communication, where convergence properties are derived. Simulation results confirm that aligning posterior distributions yields significant improvements in hypothesis deduction accuracy compared to prior semantic communication strategies. Together, these contributions advance semantic communication beyond compression-oriented formulations and provide a theoretically grounded approach for logic-based deductive reasoning under communication constraints. In the next section, we introduce FOL representation of the world and problem setup. II Related Work Semantic and goal-oriented communication systems, inspired by Weaver’s Level B notion, focus on transmitting meaning rather than symbols. DeepSC and DeepJSCC [ 11 , 12 ] pioneered autoencoder-based designs, while other works introduced task-oriented training [ 13 , 14 ] and functional compression [ 15 ] . These methods achieve notable gains in efficiency but often rely on black training or static task definitions. Beyond end-to-end learning, neuro-symbolic and graph-based approaches aim to combine logical reasoning with semantic transmission. Prior work [ 16 , 17 , 18 , 19 , 20 ] has shown that these methods strengthen semantic understanding by capturing structured meaning, making them promising foundations for communication systems. RuleTaker and ProofWriter [ 21 , 22 ] demonstrated transformer-based reasoning, while recent studies integrate knowledge graphs and large models [ 23 , 24 ] to encode structured semantics. Vector quantization [ 25 ] and generative models [ 26 ] further extend semantic communication by aligning semantic tokens with modulation schemes or reconstructing content via shared AI models. Our work differs in that it does not rely on neural compression or task-specific encoders. Instead, we adopt a symbolic and probabilistic formalism grounded in First-Order Logic and inductive probabilities tailored to logical inference. This allows us to frame semantic communication for hypothesis deduction as a posterior distribution alignment problem, derive a globally optimal truncated water-filling allocation, and establish convergence guarantees. Thus, our contributions provide a theoretical complement to learning-driven and application-specific approaches in semantic communication. III Background on FOL, Inductive Probabilities, and Semantic Information III-A Representing the State of the World via First-Order Logic We begin by illustrating how the state of the world can be represented using First-Order Logic (FOL). Consider an

Read the complete text