# Don't throw away your value model! Generating more preferable text with Value-Guided Monte-Carlo Tree Search decoding

arXiv: https://arxiv.org/abs/2309.15028 · HTML: https://mlsanity.com/paper/2309.15028/

## Key facts

- Cited by 60 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning.
- Builds on 36 of its 51 references that are in the map.
- First posted on arXiv 26 Sep 2023.

## Placed in

- LLM reasoning / [Reinforcement learning for reasoning](https://mlsanity.com/lr/reinforcement-learning-for-reasoning/)

## Builds on (most cited first, 30 of 36)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [PIQA: Reasoning about Physical Commonsense in Natural Language](https://mlsanity.com/paper/1911.11641/) (2019)
- [Fine-Tuning Language Models from Human Preferences](https://mlsanity.com/paper/1909.08593/) (2019)
- [CommonsenseQA: A Question Answering Challenge Targeting Commonsense Knowledge](https://mlsanity.com/paper/1811.00937/) (2018)
- [RealToxicityPrompts: Evaluating Neural Toxic Degeneration in Language Models](https://mlsanity.com/paper/2009.11462/) (2020)
- [Solving math word problems with process- and outcome-based feedback](https://mlsanity.com/paper/2211.14275/) (2022)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [Plug and Play Language Models: A Simple Approach to Controlled Text Generation](https://mlsanity.com/paper/1912.02164/) (2019)
- [UnifiedQA: Crossing Format Boundaries With a Single QA System](https://mlsanity.com/paper/2005.00700/) (2020)
- [SLiC-HF: Sequence Likelihood Calibration with Human Feedback](https://mlsanity.com/paper/2305.10425/) (2023)
- [Fine-Grained Human Feedback Gives Better Rewards for Language Model Training](https://mlsanity.com/paper/2306.01693/) (2023)
- [GeDi: Generative Discriminator Guided Sequence Generation](https://mlsanity.com/paper/2009.06367/) (2020)
- [QASC: A Dataset for Question Answering via Sentence Composition](https://mlsanity.com/paper/1910.11473/) (2019)
- [Quark: Controllable Text Generation with Reinforced Unlearning](https://mlsanity.com/paper/2205.13636/) (2022)
- [Making Large Language Models Better Reasoners with Step-Aware Verifier](https://mlsanity.com/paper/2206.02336/) (2022)
- [Large Language Models as Commonsense Knowledge for Large-Scale Task Planning](https://mlsanity.com/paper/2305.14078/) (2023)
- [Generated Knowledge Prompting for Commonsense Reasoning](https://mlsanity.com/paper/2110.08387/) (2021)
- [NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics](https://mlsanity.com/paper/2112.08726/) (2021)
- [NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints](https://mlsanity.com/paper/2010.12884/) (2020)

## Built on by (most cited first, 30 of 60)

- [s1: Simple test-time scaling](https://mlsanity.com/paper/2501.19393/) (2025)
- [From System 1 to System 2: A Survey of Reasoning Large Language Models](https://mlsanity.com/paper/2502.17419/) (2025)
- [Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models](https://mlsanity.com/paper/2408.00724/) (2024)
- [LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning](https://mlsanity.com/paper/2410.02884/) (2024)
- [Everything of Thoughts: Defying the Law of Penrose Triangle for Thought Generation](https://mlsanity.com/paper/2311.04254/) (2023)
- [Learning How Hard to Think: Input-Adaptive Allocation of LM Computation](https://mlsanity.com/paper/2410.04707/) (2024)
- [ReasonFlux: Hierarchical LLM Reasoning via Scaling Thought Templates](https://mlsanity.com/paper/2502.06772/) (2025)
- [TreeBoN: Enhancing Inference-Time Alignment with Speculative Tree-Search and Best-of-N Sampling](https://mlsanity.com/paper/2410.16033/) (2024)
- [Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2504.12501/) (2025)
- [Offline Reinforcement Learning for LLM Multi-Step Reasoning](https://mlsanity.com/paper/2412.16145/) (2024)
- [Scaling of Search and Learning: A Roadmap to Reproduce o1 from Reinforcement Learning Perspective](https://mlsanity.com/paper/2412.14135/) (2024)
- [KCTS: Knowledge-Constrained Tree Search Decoding with Token-Level Hallucination Detection](https://mlsanity.com/paper/2310.09044/) (2023)
- [Large Language Models for Planning: A Comprehensive and Systematic Survey](https://mlsanity.com/paper/2505.19683/) (2025)
- [Harnessing the Reasoning Economy: A Survey of Efficient Reasoning for Large Language Models](https://mlsanity.com/paper/2503.24377/) (2025)
- [Self-Explore: Enhancing Mathematical Reasoning in Language Models with Fine-grained Rewards](https://mlsanity.com/paper/2404.10346/) (2024)
- [A Survey on Personalized and Pluralistic Preference Alignment in Large Language Models](https://mlsanity.com/paper/2504.07070/) (2025)
- [AdaptiveStep: Automatically Dividing Reasoning Step through Model Confidence](https://mlsanity.com/paper/2502.13943/) (2025)
- [To Backtrack or Not to Backtrack: When Sequential Search Limits Model Reasoning](https://mlsanity.com/paper/2504.07052/) (2025)
- [Sample, Don't Search: Rethinking Test-Time Alignment for Language Models](https://mlsanity.com/paper/2504.03790/) (2025)
- [Revisiting Multi-Agent Debate as Test-Time Scaling: A Systematic Study of Conditional Effectiveness](https://mlsanity.com/paper/2505.22960/) (2025)
- [Generative AI Act II: Test Time Scaling Drives Cognition Engineering](https://mlsanity.com/paper/2504.13828/) (2025)
- [Every Rollout Counts: Optimal Resource Allocation for Efficient Test-Time Scaling](https://mlsanity.com/paper/2506.15707/) (2025)
- [Putting the Value Back in RL: Better Test-Time Scaling by Unifying LLM Reasoners With Verifiers](https://mlsanity.com/paper/2505.04842/) (2025)
- [Value-Guided Search for Efficient Chain-of-Thought Reasoning](https://mlsanity.com/paper/2505.17373/) (2025)
- [CoAT: Chain-of-Associated-Thoughts Framework for Enhancing Large Language Models Reasoning](https://mlsanity.com/paper/2502.02390/) (2025)
- [On the Query Complexity of Verifier-Assisted Language Generation](https://mlsanity.com/paper/2502.12123/) (2025)
- [First Finish Search: Efficient Test-Time Scaling in Large Language Models](https://mlsanity.com/paper/2505.18149/) (2025)
- [Interactive Reasoning: Visualizing and Controlling Chain-of-Thought Reasoning in Large Language Models](https://mlsanity.com/paper/2506.23678/) (2025)
- [A Probabilistic Inference Scaling Theory for LLM Self-Correction](https://mlsanity.com/paper/2508.16456/) (2025)
- [Do Not Waste Your Rollouts: Recycling Search Experience for Efficient Test-Time Scaling](https://mlsanity.com/paper/2601.21684/) (2026)

## Abstract (arXiv)

Inference-time search algorithms such as Monte-Carlo Tree Search (MCTS) may seem unnecessary when generating natural language text based on state-of-the-art reinforcement learning such as Proximal Policy Optimization (PPO). In this paper, we demonstrate that it is possible to get extra mileage out of PPO by integrating MCTS on top. The key idea is not to throw out the value network, a byproduct of PPO training for evaluating partial output sequences, when decoding text out of the policy network. More concretely, we present a novel value-guided decoding algorithm called PPO-MCTS, which can integrate the value network from PPO to work closely with the policy network during inference-time generation. Compared to prior approaches based on MCTS for controlled text generation, the key strength of our approach is to reduce the fundamental mismatch of the scoring mechanisms of the partial outputs between training and test. Evaluation on four text generation tasks demonstrate that PPO-MCTS greatly improves the preferability of generated text compared to the standard practice of using only the PPO policy. Our results demonstrate the promise of search algorithms even on top of the aligned language models from PPO, and the under-explored benefit of the value network.