Fork Where the Model Changes Its Mind: Belief-Shift Branching for Tree-Structured RLVR

Forum topic · 小凯 · 2026-09-13

Summary

This paper introduces belief-shift branching, a method for placing forks in tree-structured rollouts for critic-free reinforcement learning with verifiable rewards (RLVR). Tree rollouts provide step-level credit by comparing sibling outcomes, but each fork costs sampling budget, so fork placement largely determines how much signal step-level RL can gain. The authors formalize fork placement as locating pivots where a chain's expected outcome turns, and propose forking just before the step where the model's answer beliefs diverge most, read at candidate boundaries. Three supervision-free instantiations span access levels: a black-box probe, a logit-lens depth profile, and a learned activation direction. The probe costs about 1% of step compute on math and under 5% on code. Against Monte-Carlo value curves, the belief-shift signal ranks first in all eight model-benchmark panels, beating entropy, structural, and LLM-judge baselines. In RL across three model families, it leads every mathematics aggregate, achieving +2.6 aggregate and +2.9 on AIME 2026 on OLMo-3-7B over the strongest baseline, and sweeps all OLMo code results with +6.5 on LiveCodeBench-medium.

Paper Overview

Field: cs.AI
Authors: Bin Lei, Yu Li, Prafulla Kumar Choubey, Jiaxin Zhang, Becky Xiangyu Peng, Qinyuan Ye, Kartik Narayan, Caiwen Ding, Silvio Savarese, Chien-Sheng Wu
Published: 2026-09-13
arXiv: 2609.11061

Abstract (translated)

Tree-structured rollouts give critic-free reinforcement learning with verifiable rewards (RLVR) step-level credit: fork a chain at an intermediate point, and sibling outcome differences estimate step value. Each fork adds sampling cost, so realistic budgets typically allow only a few forks per chain. A fork placed where the outcome is already largely settled yields siblings that mostly agree and provide almost no credit signal; hence, for a given tree size, where forks are placed largely determines how much step-level RL can gain.

Most existing mainstream methods place forks by structure (fixed lengths, midpoints, delimiters) or by next-token entropy. This work formalizes fork placement as locating the *pivots* of the chain's value curve — the points where the expected outcome turns.

Method: Belief-Shift Branching

The proposed approach reads the model's answer belief at candidate boundaries and forks just before the step where consecutive beliefs diverge most. Three instantiations, none needing step-level supervision, span access levels:

1. A black-box probe 2. A logit-lens depth profile 3. A learned activation direction, fit offline and used only in validation before RL training

The signal only *places* forks; the probe costs about $1\%$ of step compute on mathematics and under $5\%$ on code when run inside the rollout engine.

Results

Validation: Against Monte-Carlo value curves, the belief-shift signal ranks first in each of the eight model×benchmark panels, ahead of entropy, structural, and LLM-judge baselines.
RL training: Across three model families and two domains, belief-shift forking leads every mathematics aggregate.
On OLMo-3-7B: $$+2.6$$ aggregate and $$+2.9$$ on AIME 2026 over the strongest baseline.
Sweeps every OLMo code column, by $$+6.5$$ on LiveCodeBench-medium.

---

*Auto-collected on 2026-09-13.*