Verification & proof search · RL & post-training / Open question
Learning to Branch
Tree rollouts reuse expensive prefixes, but nominal leaf count can exaggerate the number of independent learning signals.
Seed catalog · Showing the bundled record.
Problem statement
In a depth- tree over an -symbol alphabet with terminal reward , estimate by adaptively branching shared prefixes. At total generated-token and verification cost , determine the minimum attainable and a scheme attaining it, with bounded policy scores and explicit dependence on shared-prefix covariance. Correct branch-selection bias before using the estimator in policy updates.
Assumptions and scope
- Specify the prefix sampling law and branch-selection rule, including any entropy or reward-dependent adaptation.
- Charge a shared prefix once and every generated suffix/verification at its declared cost; keep the target policy gradient fixed within an estimation round.
- State how selection is corrected so that adaptive branching does not silently change the estimated objective; then quantify error when that estimator drives successive updates.
What would settle it?
A covariance-aware estimator and adaptive branching rule with cost-normalized error bounds and a matching impossibility/comparison result for a stated tree class, followed by a justified policy-update consequence.
Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.
Status and evidence
DATPO supplies an empirical tree-search design, while VSR addresses state resampling. The remaining target is joint prefix-sharing covariance, selection correction and allocation guarantees. This is an editorial, source-motivated research target. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.
Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.
Sources and further reading
- Yu et al. — Difficulty-Adaptive Tree-Structured Policy Optimization ↗related algorithm · source checked 2026-11-19
Publisher abstract checked: sentence-entropy branching, adaptive difficulty and sibling-diversity advantages. Finite-budget empirical coverage gains do not imply independent-rollout statistics.
- Wang et al. — Variance-Optimal State Resampling for RLVR ↗partial theory · source checked 2026-11-19
Abstract checked: a fixed-policy variance-minimizing Neyman allocation is already derived. Online multi-step allocation and the cost of learning its changing inputs are separate targets.
- Cheng et al. — IsoCompute Playbook: Optimally Scaling Sampling Compute for LLM RL ↗empirical motivation · source checked 2026-11-19
ICML 2026 publisher abstract checked: allocation among rollouts, batch size and updates; optimal group size increases then saturates in the measured setups.