Enhancing the reasoning capabilities of language models (LMs) remains a key challenge, especially for tasks that require complex, multistep decision-making where existing Chain-of-Thought (CoT) approaches struggle with consistency and verification.In this paper, we propose a novel reasoning framework, referred to as Structure-aware Planning with an Accurate World Model (SWAP), that integrates structured knowledge representation with learned planning.Unlike prior methods that rely purely on natural language reasoning, SWAP leverages entailment graphs to encode structured dependencies and enable symbolic verification of intermediate steps.To systematically construct and update the graph, SWAP employs a policy model to propose candidate expansions and a world model to predict structural updates.To improve accuracy, the world model generates multiple alternative updates, and a discriminator re-ranks them based on plausibility.To encourage diverse exploration, we introduce Diversity-based Modelling (DM), which samples candidates from the remaining probability mass after removing previously sampled candidates from the original policy distribution.Additionally, SWAP improves the discrimination accuracy through Contrastive Ranking (CR), which directly compares candidates within prompts and incorporates metaknowledge to improve ranking quality.We evaluate SWAP across diverse reasoning-intensive benchmarks including math reasoning, logical reasoning, and coding tasks.Extensive experiments demonstrate that SWAP significantly improves upon the base models and consistently outperforms existing reasoning methods 1 .

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-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.

Longxuan Yu, Delin Chen, Siheng Xiong, Qingyang Wu, Dawei Li, Zhikai Chen, Xiaoze Liu, Liangming Pan. Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2025.

In this paper, we address the problem of lossy semantic communication to reduce uncertainty about the State of the World (SotW) for deductive tasks in point to point communication. A key challenge is transmitting the maximum semantic information with minimal overhead suitable for down-stream applications. Our solution involves maximizing semantic content information within a constrained bit budget, where SotW is described using First-Order Logic, and content informativeness is measured by the usefulness of the transmitted information in reducing the uncertainty of the SotW perceived by the receiver. Calculating content information requires computing inductive logical probabilities of state descriptions; however, naive approaches are infeasible due to the massive size of the state space. To address this, our algorithm draws inspiration from state-of-the-art model counters and employs tree search-based model counting to reduce the computational burden. These algorithmic model counters, designed to count the number of models that satisfy a Boolean equation, efficiently estimate the number of world states that validate the observed evidence. Empirical validation using the FOLIO and custom deduction datasets demonstrate that our algorithm reduces uncertainty and improves task performance with fewer bits compared to baselines.

Conventional embedding-based models approach event time prediction in temporal knowledge graphs (TKGs) as a ranking problem. However, they often fall short in capturing essential temporal relationships such as order and distance. In this paper, we propose TEILP, a logical reasoning framework that naturaly integrates such temporal elements into knowledge graph predictions. We first convert TKGs into a temporal event knowledge graph (TEKG) which has a more explicit representation of time in term of nodes of the graph. The TEKG equips us to develop a differentiable random walk approach to time prediction. Finally, we introduce conditional probability density functions, associated with the logical rules involving the query interval, using which we arrive at the time prediction. We compare TEILP with state-of-the-art methods on five benchmark datasets. We show that our model achieves a significant improvement over baselines while providing interpretable explanations. In particular, we consider several scenarios where training samples are limited, event types are imbalanced, and forecasting the time of future events based on only past events is desired. In all these cases, TEILP outperforms state-of-the-art methods in terms of robustness.

While large language models (LLMs) have demonstrated remarkable reasoning capabilities, they are not without their flaws and inaccuracies.Recent studies have introduced various methods to mitigate these limitations.Temporal reasoning (TR), in particular, presents a significant challenge for LLMs due to its reliance on diverse temporal concepts and intricate temporal logic.In this paper, we propose TG-LLM, a novel framework towards languagebased TR.Instead of reasoning over the original context, we adopt a latent representation, temporal graph (TG) that enhances the learning of TR.A synthetic dataset (TGQA), which is fully controllable and requires minimal supervision, is constructed for fine-tuning LLMs on this text-to-TG translation task.We confirmed in experiments that the capability of TG translation learned on our dataset can be transferred to other TR tasks and benchmarks.On top of that, we teach LLM to perform deliberate reasoning over the TGs via Chain-of-Thought (CoT) bootstrapping and graph data augmentation.We observed that those strategies, which maintain a balance between usefulness and diversity, bring more reliable CoTs and final results than the vanilla CoT distillation. 1 * Equal contribution. 1 Code and data are available at https://github.com/ xiongsiheng/TG-LLM.Once upon a time in the quaint town of Weston, a baby boy named John Thompson was brought into the world in the year 1921.Growing up, he had a vibrant spirit and an adventurous soul.…Step 1: Text-to-Temporal Graph Translation True or false: event (John Thompson owned Pearl Network) was longer in duration than event (Sophia Parker was married to John Thompson) ?The duration for each event can be calculated as follows:(John Thompson owned Pearl Network) starts at 1942, ends at 1967

Advancements in logical reasoning, utilizing LLMs to convert natural language into logical symbolism, combined with the use of external theorem provers, have repositioned the symbolic approach as a central point of interest. The main challenge within this paradigm lies in the LLMs’ capability to accurately translate natural language (NL) statements into first-order-logic (FOL) expressions. Although LLMs have shown notable success, there remains a gap in understanding the limitations and challenges they encounter in NL-FOL translation. This is primarily due to the absence of datasets and evaluation test beds at the required fine-grained level. We present MALLS, a dataset of 28K diverse and verified sentence-level NL-FOL pairs collected from GPT4. We utilize a combined strategy of FOL rule parsing, human annotation, and automatic filtering to ensure quality. We also present LogicLLaMA, a LLaMA2-7B/13B fine-tuned on MALLS for NL-FOL translation, which can be used standalone or to correct previously generated rules by GPT3.5 after being further fine-tuned via a novel reinforcement learning with human feedback (RLHF) framework. We benchmark a wide range of LLMs on MALLS and previous datasets, highlighting weaknesses in them in NL-FOL translation and demonstrating the advantages of MALLS. We also show that LogicLLaMA achieves GPT4-level performance and can generalize to other datasets. Project repo is available at https://github.com/gblackout/LogicLLaMA