BFS-PO: Best-First Search for Large Reasoning Models

Fiorenzo Parascandolo; Wenhui Tan; Enver Sangineto; Ruihua Song; Rita Cucchiara

cs.CLFeb 16, 2026

BFS-PO: Best-First Search for Large Reasoning Models

Authors: Fiorenzo Parascandolo, Wenhui Tan, Enver Sangineto, Ruihua Song, Rita Cucchiara

Organizations: Department of Engineering, University of Modena and Reggio Emilia, Italy. · Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China.

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.

Figures & tables

Panel of Figure 1 — Figure 1: A schematic comparison between GRPO/DAPO (a) and BFS-PO (b-d). In (a), the sampling mechanism of GRPO/DAPO is represented as a simple tree with only one forking node (the root node, conditioned on the question $q$ ). ✓ and ✗ represent correct and incorrect answers, respectively. In (b) and (d), the current best solution is selected, while in (c) new branches are added to the tree. For simplicity, in this figure we use $G=4$ .

Panel of Figure 2 — Figure 2: A schematic representation of the sub-tree $S(w_{n}^{b})$ .

Method	K	Branch Adv.	Len. Penalty	Acc. $\uparrow$	Avg. Len. $\downarrow$	AES $\uparrow$
Zero-shot	-	-	-	83.7	315	0.00
DAPO	0	-	✓	85.6	290	0.15
BFS-PO	1	✓	✓	85.9	286	0.17
BFS-PO	2	✓	✓	86.2	271	0.23
BFS-PO	3	✓	✓	86.2	269	0.24
w/o BFS	3	✓	✓	86.0	311	0.10

Table 1: Ablation experiments using GSM8K and Qwen2.5-3B-Instruct.

Model	Method	Acc. $\uparrow$	Avg. Len. $\downarrow$	AES $\uparrow$
Qwen2.5-3B-Instruct	Zero-shot	83.7	315	0.00
	SFT	83.4	319	-0.03
	TokenSkip	83.2	263	0.14
	DAPO	85.6	290	0.15
	BFS-PO	86.2	269	0.24
Llama-3.1-8B-Instruct	Zero-shot	86.2	213	0.00

Table 2: Experimental results with training on GSM8K.

Method	MATH			GSM8K			MMLU			AIME			MINERVA
Method	(in-domain)			(out-of-domain)			(out-of-domain)			(out-of-domain)			(out-of-domain)
	Acc. $\uparrow$	Avg. Len. $\downarrow$	AES $\uparrow$	Acc. $\uparrow$	Avg. Len. $\downarrow$	AES $\uparrow$	Acc. $\uparrow$	Avg. Len. $\downarrow$	AES $\uparrow$	Acc. $\uparrow$	Avg. Len. $\downarrow$	AES $\uparrow$	Acc. $\uparrow$	Avg. Len. $\downarrow$	AES $\uparrow$
Llama-3.1-8B-Instruct
Zero-shot	48.6	503	0.00	86.2	213	0.00	58.5	356	0.00	6.4	873	0.00	19.0	553	0.00
SFT	48.2	505	-0.05	86.0	214	-0.02	58.4	354	-0.01	-	-	-	-	-	-
TokenSkip	46.7	349	0.11	82.6	152	0.08	58.1	189	0.44	-	-	-	-	-	-

Table 3: Experimental results with training on MATH-500.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Llama-3.1-8B-Instruct
Methods	Ratio	GSM8K			MATH-500
Methods	Ratio	Acc. $\uparrow$	Avg. Len. $\downarrow$	AES $\uparrow$	Acc. $\uparrow$	Avg. Len. $\downarrow$	AES $\uparrow$
Zero-shot	-	86.2	213	0.00	48.6	503	0.00
TokenSkip	1.0	86.7	214	0.02	48.2	505	-0.05
	0.9	86.1	198	0.06	47.8	448	0.03
	0.8	84.3	170	0.09	47.3	399	0.07

Appendix

Table 4: Extended comparison with TokenSkip using Llama-3.1-8B-Instruct (in-domain experiments).

Llama-3.1-8B-Instruct
Methods	Ratio	GSM8K (out-of-distribution)			MMLU-STEM (out-of-distribution)
Methods	Ratio	Acc. $\uparrow$	Avg. Len. $\downarrow$	AES $\uparrow$	Acc. $\uparrow$	Avg. Len. $\downarrow$	AES $\uparrow$
Zero-shot	-	86.2	213	0.00	58.5	356	0.00
TokenSkip	1.0	86.0	214	-0.02	58.4	354	0.00
	0.9	84.9	202	-0.02	59.4	327	0.16
	0.8	83.7	175	0.03	59.3	286	0.27

Appendix

Table 5: Extended comparison with TokenSkip using Llama-3.1-8B-Instruct (out-of-domain experiments).

Model	Methods	Ratio	Acc. $\uparrow$	Avg. Len. $\downarrow$	AES $\uparrow$
Qwen2.5-3B-Instruct	Zero-shot	-	83.7	315	0.00
	TokenSkip	1.0	83.4	319	-0.03
		0.9	83.2	263	0.13
		0.8	81.6	251	0.08
		0.7	80.1	233	0.04
		0.6	77.3	200	-0.02

Appendix

Table 6: Extended comparison with TokenSkip on GSM8K with Qwen2.5-Instruct models (in-domain experiments).

Explore similar work

Efficiently Learning To Reason or Not to Reason: Root-token Policy Optimization for Adaptive Thinking
Oct 13, 2026Taehyeon Kim, Hyunsoo Lee, Youngsoo Jang +1Efficient Language Model Reasoning Large Reasoning Models
LG AI Research · UNIST · University of Illinois Chicago
GraphPO: Graph-based Policy Optimization for Reasoning Models
Jun 17, 2026Yuliang Zhan, Xinyu Tang, Jian Li +7Reinforcement Learning LLM Reasoning with Graphs
Gaoling School of Artificial Intelligence, Renmin University of China · Ant Group
Efficient Reasoning via Constrained Optimization in Latent Space
Sep 28, 2026Zhinan Hou, Xingchen Li, Keyou YouOverthinking in Language Models Efficient Language Model Reasoning
Tsinghua University

Oct 13, 2026J/K move · Enter open · S save

Efficiently Learning To Reason or Not to Reason: Root-token Policy Optimization for Adaptive Thinking

Taehyeon Kim, Hyunsoo Lee, Youngsoo Jang, Moontae Lee

LG AI Research · UNIST · University of Illinois Chicago

Efficient Language Model Reasoning Large Reasoning Models Overthinking in Language Models RL for Language Model Reasoning

Open paper AskPDF arXiv

Large reasoning models (LRMs) achieve strong performance by externalizing explicit reasoning traces before producing the answer, yet suffer from overthinking challenge that allocates uniformly heavy computation to queries of varying difficulty. While proprietary models mitigate this via opaque routing, open-source LRMs still lack an efficient mechanism to internalize adaptive reasoning due to both expensive training cost and limited disclosure of training recipes. In response, we introduce RPO (Root-token Policy Optimization), a framework that enables LRMs to self-determine when to reason by training only the initial root token (e.g., whether to invoke the <think> tag) via group relative reward and group-wise advantages. By focusing on this pivotal branching point, RPO drastically reduces training overhead and VRAM usage. Across multiple model families and scales, RPO learns difficulty-aware adaptive thinking at just ~2% of the training compute of prior adaptive-reasoning methods.

Abstract

Explore similar work

Efficiently Learning To Reason or Not to Reason: Root-token Policy Optimization for Adaptive Thinking

GraphPO: Graph-based Policy Optimization for Reasoning Models

Efficient Reasoning via Constrained Optimization in Latent Space