TL;DR
Large Language Models (LLMs) struggle with multi-step reasoning, often losing focus and generating redundant or incorrect information. This paper introduces "Stepwise Informativeness Search," a novel tree-search framework that guides LLMs to proactively reference underutilized prior steps and minimize redundancy, significantly improving reasoning accuracy and efficiency.
What Problem Does This Paper Address?
LLMs have shown impressive reasoning capabilities through techniques like Chain-of-Thought (CoT) prompting. However, for complex, multi-step reasoning tasks, LLMs tend to "lose focus" in the middle of long chains of thought. This leads to several issues:
- Underutilization of prior information: Intermediate conclusions from earlier steps are often overlooked, even if they are crucial for later deductions.
- Redundant rationales: The model might repeat the same conclusions or generate steps that don't add new information.
- Unreliable and incorrect answers: The combination of these issues can lead to logical errors and ultimately, incorrect final answers.
This problem is particularly pronounced in smaller LLMs, but even larger models can suffer from these "reasoning loops" and inefficiencies. The paper aims to address this by making LLM reasoning more structured, focused, and efficient.
Methods
The core contribution is the Stepwise Informativeness Search framework, an inference-time tree search algorithm designed to improve LLM reasoning. It builds upon standard stepwise beam search but incorporates two key heuristics:
- Grounding-Guided Selection: This heuristic prioritizes reasoning steps that actively reference "underutilized" prior steps. Underutilized steps are identified by their low reference frequency in previous steps, suggesting they hold untapped potential. The method leverages LLM attention scores to assess how well a new step grounds itself on these underutilized conclusions.
- Novelty-Guided Selection: This heuristic aims to reduce redundancy by ranking candidates based on the novelty of their intermediate conclusions compared to previous steps. A trigram-based similarity measure is used to filter out highly similar conclusions.
Additionally, the paper introduces a Self-Grounding Strategy. This strategy explicitly prompts LLMs to reference relevant prior steps or the input query as premises before each deduction, using a structured format like "[Step-i] From <source>, <deduction>." This helps anchor the reasoning process and prevent focus on irrelevant or distracting information.
The framework integrates these heuristics into a scoring function that combines cumulative likelihood with grounding and novelty scores.
Datasets
The paper evaluates its approach on several standard multi-step reasoning and commonsense reasoning datasets:
- Deductive Reasoning:
- FOLIO (Han et al., 2022)
- ProofWriter (Tafjord et al., 2020)
- Mixed Reasoning:
- MMLU-Pro (Wang et al., 2024c)
- GPQA-Diamond (Rein et al., 2023)
- Commonsense Reasoning:
- ARC Challenge (Clark et al., 2018)
Key Insights and Ideas
- Underutilized steps are valuable: The paper empirically shows that grounding reasoning on previously underutilized steps significantly improves accuracy, even for complex tasks. This highlights that LLMs don't always leverage all available information effectively.
- Attention is a good proxy for grounding: LLMs naturally assign higher attention to grounded contexts. This observation is leveraged to measure how well a new reasoning step connects to prior information.
- Novelty prevents redundancy: Explicitly encouraging novel conclusions in reasoning steps is crucial for avoiding repetitive and less informative rationales.
- Self-grounding provides structure: The structured prompting for self-grounding helps LLMs maintain logical coherence and focus by explicitly linking each deduction to its premises.
- Efficiency gains: The proposed method achieves better accuracy with fewer tokens and reduced inference time compared to many baseline methods, making it more practical.
Key Results
- Improved Accuracy: The Stepwise Informativeness Search framework consistently outperforms baseline methods (including Few-shot CoT, Self-Consistency, Tree-of-Thought, and various beam search variants) across multiple datasets and LLMs (Llama3.2-3B-Instruct, Llama3-8B-Instruct, Phi-4, Qwen2.5-7B-Instruct, DeepSeek-R1-Distill-Llama-8B). For instance, on Llama3-8B-Instruct, the method achieved up to 49.46% accuracy, a notable improvement over baselines.
- Reduced Redundancy: The method significantly reduces redundant steps, as evidenced by a substantial decrease in the average count of overlapping conclusions.
- Efficiency: The approach generates shorter rationales (fewer tokens) and achieves faster inference times compared to other stepwise beam search methods, while maintaining comparable memory usage. For example, on the FOLIO dataset, the informativeness search reduced token usage by nearly 4x compared to standard stepwise beam search.
- Effectiveness on Smaller Models: The method shows particularly substantial improvements on smaller LLMs like Llama3.2-3B-Instruct, suggesting its effectiveness in enhancing reasoning for less capable models.
Limitations and Future Work
- Computational Constraints: The current experiments were conducted with limited search space (beam size 3, sample size 2) and LLM backbones up to 14B parameters. Future work could explore larger search spaces and more powerful LLMs to unlock further potential.
- Integration with Other Methods: The framework currently relies on standard cumulative likelihood for its base scoring. Future research could explore integrating the informativeness heuristics with other scoring mechanisms, such as self-evaluation, process reward models, or other tree-search algorithms like MCTS.
- Embedding-based Similarity: While trigram-based similarity was effective, the paper notes that lightweight embedding-based measures could further enhance semantic fidelity and merit exploration for novelty and information gain calculations.
- Long-Thinking Models: The paper suggests that the approach can be extended to long-thinking models that explore multiple alternative solutions or perform verification, by applying in-block novelty-guided selection within reasoning blocks.
Summary updated