ReST-RL: Achieving Accurate Code Reasoning of LLMs with Optimized Self-Training and Decoding

Sining Zhoubian, Dan Zhang, Yuxiao Dong, Jie TangarXiv 2025 · DOI · arXiv

Introduction

Reinforcement Learning (RL) has emerged as a powerful tool for aligning Large Language Models (LLMs) with complex reasoning tasks. However, applying RL to code reasoning faces two primary challenges: insignificant reward variance in online methods like Group Relative Policy Optimization (GRPO) and the high cost of obtaining human-annotated data for Process Reward Models (PRMs). We introduce ReST-RL, a framework that overcomes these hurdles by combining Reinforced Self-Training (ReST) with a value-model-guided decoding strategy.

Methodology

The ReST-RL framework consists of two main components: a training phase (ReST-GRPO) and an inference-time decoding phase (VM-MCTS).

The ReST-RL Framework: Integrating ReST-GRPO for policy reinforcement and VM-MCTS for verified decoding.

ReST-GRPO: Policy Reinforcement

Standard GRPO often suffers from low reward variance, where multiple samples for a single prompt yield identical rewards, providing a weak learning signal. ReST-GRPO addresses this through:

  1. High-Value Prompt Filtering: Selecting prompts that exhibit high reward variance or contain at least one successful solution.
  2. Partial State Bootstrapping: Sampling intermediate reasoning steps from successful trajectories and using them as new starting points. This technique increases the density of positive signals and forces the model to learn from successful patterns.

VM-MCTS: Verified Decoding

To improve test-time performance without expensive human labels, we develop a Value Model (VM). Unlike PRMs that require step-level correctness labels, the VM estimates the expected future reward (value) of a partial state. We use MCTS to automatically generate value targets from model-generated data. During inference, this VM guides a search process to prune suboptimal paths and prioritize promising reasoning trajectories.

Experimental Results

We evaluated ReST-RL using a curated set of 6,945 coding prompts from BigCodeBench, DS-1000, and APPS. The framework was tested across several model families, including Qwen, DeepSeek, and Llama.

Performance Gains

ReST-RL consistently outperformed both base models and standard RL baselines. As shown in the table below, the iterative application of ReST-GRPO leads to substantial improvements across all benchmarks.

Performance comparison of ReST-RL against baselines across multiple models and coding benchmarks.

On the Qwen3-8B model, ReST-RL improved the average score from 0.503 to 0.689. Notably, ReST-GRPO achieved higher accuracy in fewer training steps compared to naive GRPO, demonstrating superior training efficiency.

Decoding Efficiency

The VM-MCTS strategy proved more robust than standard Outcome Reward Models (ORM). By providing precise signals at intermediate steps, it allows for more effective exploration within a fixed sampling budget, leading to higher accuracy growth rates.

Conclusion

ReST-RL provides a scalable and effective solution for enhancing the code reasoning capabilities of LLMs. By maximizing the utility of model-generated data through variance-aware filtering and MCTS-guided value estimation, it achieves significant performance gains without the need for human-annotated process labels. Future work will explore the generalizability of these techniques to other reasoning domains such as mathematics and logic.

Summary updated

BibTeX
@misc{zhoubian2025rest,
  author = {Sining Zhoubian and Dan Zhang and Yuxiao Dong and Jie Tang},
  title = {{ReST-RL: Achieving Accurate Code Reasoning of LLMs with Optimized Self-Training and Decoding}},
  year = {2025},
  eprint = {2508.19576},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.19576},
}
Figure