Abstract: Large Reasoning Models (LRMs) such as OpenAI o1 and DeepSeek-R1 have shown excellent performance in reasoning tasks using long reasoning chains. However, this has also led to a significant increase of computational costs and the generation of verbose output, a phenomenon known as overthinking. The tendency to overthinking is often exacerbated by Reinforcement Learning (RL) algorithms such as GRPO/DAPO. In this paper, we propose BFS-PO, an RL algorithm which alleviates this problem using a Best-First Search exploration strategy. Specifically, BFS-PO looks for the shortest correct answer using a backtracking mechanism based on maximum entropy nodes. By generating progressively shorter responses during training, BFS-PO learns to produce concise reasoning chains. Using different benchmarks and base LRMs, we show that BFS-PO can simultaneously increase the LRM accuracy and shorten its answers.
Introduction
Modern Large Reasoning Models (LRMs) achieve high accuracy by "thinking" through problems using long Chains-of-Thought (CoT). However, this often leads to overthinking: the generation of thousands of redundant, verbose, or even erroneous tokens that waste compute and memory. Ironically, standard Reinforcement Learning (RL) algorithms like GRPO or DAPO can exacerbate this. Because these algorithms often use length-based normalization in their objective functions, they can inadvertently reward longer responses when a model is struggling to find a correct answer. BFS-PO (Best-First Search Policy Optimization) is designed to curb this behavior by identifying the shortest correct reasoning paths during training.
The BFS-PO Framework
The core innovation of BFS-PO is structuring training exploration as a Best-First Search on a tree rather than independent samples. The process consists of three main phases:
- Selection & Backtracking: Instead of just generating multiple independent answers, the algorithm identifies the "best" solution found so far (the shortest correct one). It then looks back through that reasoning chain to find "forking tokens"—points of high maximum entropy where the model had to make a difficult logical decision.
- Expansion: The model generates new branches specifically from these high-entropy nodes, attempting to find an even shorter path to the correct answer.
- Branch Advantage: Standard RL compares a sequence's reward to a global average. BFS-PO introduces a "branch advantage," comparing a specific path's reward to the average of other branches originating from the same decision point. This provides a much denser and more stable supervision signal.
By sharing "ancestor" tokens across different branches, BFS-PO can reuse KV caches during training, resulting in a 1.37x speedup compared to standard DAPO training. Crucially, BFS-PO does not require a costly external Process Reward Model (PRM); it only needs a final answer verifier.
Experimental Evaluation
The authors evaluated BFS-PO across several rigorous reasoning benchmarks, including GSM8K, MATH-500, and MMLU-STEM. To test generalization, out-of-distribution (OOD) testing was conducted on AIME’25 and MINERVA-MATH. The models used for testing included Llama-3.1-8B-Instruct, Qwen2.5-3B-Instruct, and Qwen2.5-7B-Instruct.
Results and Discussion
Across almost all tests, BFS-PO achieved a rare "win-win": it increased accuracy while simultaneously decreasing the average length of reasoning chains. In the AIME’25 competition math benchmark, BFS-PO outperformed DAPO by over 4 percentage points in accuracy while using significantly fewer tokens.
To measure this balance, the authors utilized the Accuracy Efficiency Score (AES), which rewards both correctness and conciseness. As shown in the results table, BFS-PO consistently achieved the highest AES compared to baselines like TokenSkip and Tree of Thoughts. Qualitative analysis further supports these findings; for example, on the GSM8K dataset, BFS-PO reduced reasoning from 277 tokens to 198 tokens by removing redundant explanations without losing logical integrity.
Conclusion and Limitations
BFS-PO demonstrates that brevity can be a signal for logic. By biasing exploration toward the shortest correct path, the model learns to eliminate textual filler and focus on critical logical trajectories. While the study focused on models up to 8B parameters, the computational cost of building search trees for 70B+ models remains a challenge for future work. Additionally, the method currently relies on objective verifiers (e.g., math or code), making its application to open-ended reasoning tasks a promising area for further research.
Summary updated