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

• URL: http://arxiv.org/abs/2609.11061v1
• Date: Thu, 10 Sep 2026 04:06:45 GMT
• Title: Fork Where the Model Changes Its Mind: Belief-Shift Branching for Tree-Structured Reinforcement Learning
• Abstract summary: We formalize fork placement as locating the emphss of the chain's value curve, where the expected outcome turns.<n>Three instantiations, none needing step-level supervision, span access levels: a black-box probe, a logit-lens depth profile, and a learned activation direction.
• Score: 62.24941741019998
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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, such as fixed lengths, midpoints, and delimiters, or by next-token entropy. We formalize fork placement as locating the \emph{pivots} of the chain's value curve, where the expected outcome turns. We propose \emph{belief-shift branching}: read the model's answer belief at candidate boundaries and fork just before the step where consecutive beliefs diverge most. Three instantiations, none needing step-level supervision, span access levels: a black-box probe, a logit-lens depth profile, and a learned activation direction, which is fit offline and therefore used only in the validation before RL training. The signal only \emph{places} forks, and the probe costs about $1\%$ of step compute on mathematics and under $5\%$ on code when it runs inside the rollout engine. In that validation, against Monte-Carlo value curves, a belief-shift signal ranks first in each of the eight model$\times$benchmark panels, ahead of entropy, structural, and LLM-judge baselines. In RL across three model families and two domains, belief-shift forking leads every mathematics aggregate, on OLMo-3-7B by $+2.6$ aggregate and $+2.9$ on AIME 2026 over the strongest baseline, and sweeps every OLMo code column, by $+6.5$ on LiveCodeBench-medium.

Related papers

• Scalable Quantum Machine Learning: Trainability, Expressivity and Efficiency [0.5076419064097732]
  We propose a unitary brick-wall: a $k$-particle fermionic architecture for nearest-neighbor hardware.<n>The brick-wall has dynamical Lie algebra $mathfraku(n)$ and directly parametrizes $U(n)$ via Givens rotations.<n>It achieves similar hardness guarantees at $8klog n$ evaluations per gradient step, the same factor $3n/(8k)$ reduction.
  arXiv  Detail & Related papers  (2026-07-27T05:23:32Z)
• Directional Curvature from Armijo Backtracking: A Low-Cost Sharpness Probe and a Calibration-Free Learning-Rate Safeguard for Adam [0.16283634001181238]
  We observe that a single Armijo backtracking line search already carries this information at the cost of a few forward passes.<n>Used once at initialisation, this measurement yields a learning-rate cap that makes Adam robust to a too-large initial learning rate.
  arXiv  Detail & Related papers  (2026-07-04T19:49:01Z)
• Dead-Direction Signatures: A Cheap Spectral Reading of Singular Complexity [5.67642958049511]
  Singular learning theory characterises the complexity of a deep network through the geometry of its loss singularities.<n>We introduce DeadDirection Signatures (DDS), a family of cheap closed-form spectral readings of singular structure.<n>Each reads a network's activation matrix or per-sample-gradient FisherGram at a chosen layer, replacing the posterior chain spectral linear algebra.
  arXiv  Detail & Related papers  (2026-06-19T06:49:09Z)
• Read the Trace, Steer the Path: Trajectory-Aware Reinforcement Learning for Diffusion Language Models [26.87342465042021]
  We introduce CAPR (Cached-Amortized Path Refinement), a dLLM-RL algorithm that summarizes the denoising trace into a compact path state.<n>It reduces rollout-generation cost to roughly 0.75x that of flat rollouts and 0.6x that of tree rollouts.<n>Across 4x4 Sudoku, Countdown, GSM8K, and Math500, it matches the strongest tree-structured baseline at less than one third of the per-step compute.
  arXiv  Detail & Related papers  (2026-06-03T03:22:54Z)
• Verifier-Free RL for LLMs via Intrinsic Gradient-Norm Reward [69.99652051809737]
  In this work, we propose Verifier-free Intrinsic Gradient-Norm Reward (VIGOR)<n>VIGOR is a simple reward that uses only the policy model itself.<n>It exhibits cross-domain transfer to code benchmarks when trained only on math data.
  arXiv  Detail & Related papers  (2026-05-11T03:15:37Z)
• The Spectral Edge Thesis: A Mathematical Framework for Intra-Signal Phase Transitions in Neural Network Training [0.0]
  We show that phase transitions in neural network training are controlled by the spectral gap of the rolling-window Gram matrix of parameter updates.<n>Adiabatic parameter $mathcalA = |G|_F / (, g2)$ controls circuit stability: $mathcalA ll 1$ (plateau), $mathcalA sim 1$ (phase transition), $mathcalA gg 1$ (forgetting)
  arXiv  Detail & Related papers  (2026-03-30T20:10:22Z)
• Divine Benevolence is an $x^2$: GLUs scale asymptotically faster than MLPs [51.56484100374058]
  Scaling laws can be understood from ground-up numerical analysis.<n>GLU variants now dominate frontier LLMs and similar outer-product architectures are prevalent in ranking models.<n>We show that GLUs have piecewise quadratic functional forms that are sufficient to exhibit quadratic order of approximation.<n>This opens the possibility of architecture design from first principles numerical theory to unlock superior scaling in large models.
  arXiv  Detail & Related papers  (2026-02-16T06:19:58Z)
• Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
  We present a novel characterization of rank, grounded in the well-known Transformer architecture.<n>We show that the rank of a function $f$ corresponds to the minimum number of emphChain of Thought steps required by a single-layer Transformer.<n>We also introduce the notion of the multi-head rank that captures multi-head single-layer transformers, and perform the analysis of PAC-learnability of the classes of functions with bounded multi-head rank.
  arXiv  Detail & Related papers  (2025-01-22T16:30:58Z)
• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  We study reinforcement learning with linear function approximation, unknown transition, and adversarial losses. We propose a new algorithm that attains an $widetildeO(dsqrtHS3K + sqrtHSAK)$ regret with high probability.
  arXiv  Detail & Related papers  (2024-03-07T15:03:50Z)
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model [50.38446482252857]
  Two-player zero-sum Markov games are arguably the most basic setting in multi-agent reinforcement learning. We develop a learning algorithm that learns an $varepsilon$-approximate Markov NE policy using $$ widetildeObigg. We derive a refined regret bound for FTRL that makes explicit the role of variance-type quantities.
  arXiv  Detail & Related papers  (2022-08-22T17:24:55Z)
• High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation [89.21686761957383]
  We study the first gradient descent step on the first-layer parameters $boldsymbolW$ in a two-layer network. Our results demonstrate that even one step can lead to a considerable advantage over random features.
  arXiv  Detail & Related papers  (2022-05-03T12:09:59Z)
• A Theoretical Understanding of Gradient Bias in Meta-Reinforcement Learning [16.824515577815696]
  Gradient-based Meta-RL (GMRL) refers to methods that maintain two-level optimisation procedures. We show that existing meta-gradient estimators adopted by GMRL are actually text-bfbiased. We conduct experiments on Iterated Prisoner's Dilemma and Atari games to show how other methods such as off-policy learning and low-bias estimator can help fix the gradient bias for GMRL algorithms in general.
  arXiv  Detail & Related papers  (2021-12-31T11:56:40Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  We revisit offline reinforcement learning on episodic time-homogeneous Markov Decision Processes with $S$ states, $A$ actions and planning horizon $H$. We obtain the first set of nearly $H$-free sample complexity bounds for evaluation and planning using the empirical MDPs.
  arXiv  Detail & Related papers  (2021-03-25T18:52:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.