Deliberate Reasoning for LLMs as Structure-aware Planning with Accurate World Model

Siheng Xiong, Ali Payani, Yuan Yang, Faramarz Fekri

TL;DR

This paper introduces SWAP, a novel framework that enhances Large Language Models' (LLMs) reasoning abilities by combining structured planning with an accurate world model. SWAP uses entailment graphs for symbolic verification and novel techniques like Diversity-based Modelling and Contrastive Ranking to improve planning and discrimination, significantly outperforming existing methods on complex reasoning tasks.

What Problem Does This Paper Address?

LLMs have shown impressive capabilities, but complex, multi-step reasoning tasks, especially those requiring verification and consistency, remain a challenge. Existing methods like Chain-of-Thought (CoT) often struggle with these aspects due to their reliance on natural language alone and a lack of robust verification mechanisms, leading to hallucinations and errors. While formal methods offer verification, they often lack the flexibility needed for diverse reasoning tasks. This paper aims to bridge this gap by proposing a semi-formal reasoning framework that integrates structured knowledge representation with learned planning, enabling symbolic verification of intermediate steps while maintaining flexibility.

Methods

SWAP introduces a novel reasoning framework that conceptualizes multi-step reasoning as the construction of entailment graphs. These graphs explicitly represent how premises lead to intermediate conclusions, allowing for symbolic verification. The framework comprises:

  • Policy Model: Proposes candidate expansions (actions) for the entailment graph.
  • World Model: Predicts structural updates to the graph, essentially simulating future states. To improve accuracy, it generates multiple alternative updates, which are then re-ranked by a discriminator.
  • Diversity-based Modelling (DM): Encourages exploration by sampling candidates from the remaining probability mass after excluding previously sampled ones, promoting diverse reasoning paths.
  • Contrastive Ranking (CR): Enhances discrimination accuracy by directly comparing candidate options within prompts and incorporating meta-knowledge to improve ranking quality.

The entire process is framed as a Markov Decision Process (MDP), where states are represented by the current graph and actions are graph expansions.

Datasets

The paper evaluates SWAP on several established benchmarks:

  • Math Reasoning: GSM8K, MATH500
  • Logical Reasoning: FOLIO, ReClor
  • Coding: HumanEval, MBPP

No new benchmarks were introduced.

Key Insights and Ideas

  • Entailment Graphs for Verification: Representing reasoning as entailment graph construction provides a structured way to encode dependencies and enable symbolic verification, a crucial step beyond pure natural language reasoning.
  • World Model as a Key Component: The accuracy of the world model is paramount, directly impacting the effectiveness of the planning process. SWAP's approach of generating multiple updates and using a discriminator for re-ranking is a novel way to improve world model reliability.
  • Addressing Planning Bottlenecks: The paper identifies and addresses two critical issues in planning-based reasoning: generation diversity (solved by DM) and discrimination accuracy (solved by CR). This targeted approach is key to SWAP's success.
  • Semi-Formal Reasoning is Powerful: SWAP demonstrates that a blend of structured representation (entailment graphs) and learned planning can achieve strong reasoning capabilities without resorting to fully formal systems, offering a practical middle ground.

Key Results

SWAP consistently outperforms existing reasoning methods across diverse benchmarks.

  • On LLaMA3-8B-Instruct, SWAP achieved 92.6% on GSM8K, 43.2% on MATH500, and 79.2% on FOLIO, significantly outperforming baselines like CoT, ToT, and RAP.
  • On Mistral-7B-Instruct, SWAP achieved 83.2% on GSM8K, 28.0% on MATH500, and 71.2% on FOLIO, again showing substantial improvements.
  • The paper highlights that SWAP's structured approach and planning mechanism are particularly effective for higher-difficulty problems.
  • Ablation studies confirm that each component of SWAP (structure-awareness, world model, DM, CR) contributes positively to overall performance.

Limitations and Future Work

  • Computational Cost: Planning-based methods, including SWAP, can be resource-intensive due to generating and comparing multiple candidate options. Future work could focus on optimizing this procedure, exploring trade-offs between accuracy and efficiency, and developing adaptive strategies based on task difficulty.
  • Dynamic Adjustment: Developing adaptive strategies that dynamically adjust the number of candidates based on task difficulty or model confidence is suggested.
  • Lightweight Discriminators: Exploring lightweight model architectures for discriminators could improve efficiency.
  • Reinforcement Learning: Future work could explore reinforcement learning to enable dynamic interaction between the policy and world models.
  • Tool Integration: Integrating external tools could further enhance LLM capabilities.
  • Self-Correction: Teaching models to self-identify and correct mistakes is proposed as a promising direction for improving robustness.

Summary updated

Abstract

Enhancing the reasoning capabilities of language models (LMs) remains a key challenge, especially for tasks that require complex, multi-step 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 meta-knowledge 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.
BibTeX
@inproceedings{xiong2025deliberate,
  author = {Siheng Xiong and Ali Payani and Yuan Yang and Faramarz Fekri},
  title = {{Deliberate Reasoning for LLMs as Structure-aware Planning with Accurate World Model}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2025},
}
Figure