Multi-Step Reasoning in Large Language Models: A Survey

This post summarizes the survey "Towards LLM-based Multi-Step Reasoning" by Aske Plaat, Annie Wong, Suzan Verberne, et al. (Leiden University, Netherlands), available at arXiv:2407.11511v2.

1. Overview and Core Contributions

Despite revolutionary advances in NLP, LLMs struggle with complex, multi-step logical reasoning. Even grade-school math word problems — trivial for humans — remain challenging because LLMs generate text by predicting the next most likely token rather than performing strict symbolic reasoning.

A major response to this limitation is Chain-of-Thought (CoT) prompting (Wei et al., 2022), which guides models to produce explicit, step-by-step intermediate reasoning, yielding significant gains on math and logic benchmarks.

The survey's core contribution is a three-stage taxonomy for multi-step reasoning:

• Generate — how intermediate reasoning steps are produced, from hand-written prompts to auto-generated and external-knowledge-augmented prompting.
• Evaluate — verification and scoring of generated steps via self-critique, external tools, or independent models.
• Control — managing the reasoning process: choosing which step to advance, or backtracking and correcting errors.

This process-oriented framework goes beyond mere technique enumeration, providing a unified lens for comparing methods and a roadmap for reliable, interpretable LLM reasoning systems.

2. Key Methods: The Three-Stage Taxonomy

Stage 1: Step Generation

| Strategy | Strengths | Limitations | |---|---|---| | Hand-crafted prompts (e.g., "let's think step by step") | Intuitive, controllable | Poor generalization, labor-intensive | | External knowledge prompts (knowledge graphs, databases) | Higher accuracy and reliability | Complex retrieval and integration | | Model-auto-generated prompts (e.g., Auto-CoT) | Highly automated, generalizable | Requires substantial data and compute |

Stage 2: Step Evaluation

• Self-evaluation: the model reflects on its own steps via targeted prompts; limited by the model's own blind spots.
• Tool-based evaluation: deterministic tools (Python interpreters, calculators, logic solvers) provide highly reliable verification.
• External model verification: a separate model scores the main model's steps for more objectivity, at the cost of extra training data and compute.

Stage 3: Control of Reasoning Steps

• Greedy selection: pick the best-looking step at each stage — fast and simple, but myopic (local optimum ≠ global optimum).
• Ensemble strategies: self-consistency, path ensembling, and model ensembling — more robust but computationally expensive.
• Reinforcement learning and tree search: modeling reasoning as sequential decision-making using Monte Carlo Tree Search, PPO, A3C — powerful but very costly, with difficult reward design.

3. Benchmark Results and Findings

• GSM8K: a dataset of ~8,500 grade-school math word problems requiring 2–8 steps to solve. CoT methods deliver roughly a +39% performance improvement over direct-answer baselines.
• CoT variants have driven consistent gains across multiple math and logic benchmarks since 2022, demonstrating that prompt design can elicit deeper processing from LLMs.

4. Challenges and Future Directions

• Reducing the computational cost of search- and RL-based control.
• Improving self-evaluation to overcome model blind spots.
• Designing better reward functions for reinforcement-learning-based reasoning.
• Coordinating generation, evaluation, and control jointly rather than in isolation to improve reliability and interpretability.

5. Conclusion

By framing multi-step reasoning as an interplay of generation, evaluation, and control, this survey offers both a clear theoretical framework and a practical roadmap — advancing toward more reliable, explainable LLM reasoning systems.

Reference: Plaat, A., Wong, A., Verberne, S., et al. — arXiv:2407.11511v2