Verification & proof search · RL foundations / Open question
When Should Search Go Wider?
Sakana's GEN node makes fresh candidates compete with continued refinement. A theory must account for how refinement changes the score distributions being backed up. Efficiency payoff: Identify when adaptive branching saves inference calls, and when misleading intermediate scores cause an avoidable search overhead.
Seed catalog · Showing the bundled record.
Problem statement
Consider depth- answer trees with observed types , exact scores , a root generator and refinement kernels . Each expansion independently samples a new child from its parent's kernel; nonzero probabilities are at least and some score-one type is reachable within depth . For the Beta AB-MCTS-A rule with prior , determine . Bound its overhead relative to the optimal kernel-informed search, in .
Assumptions and scope
- Use Algorithm 1, Section 3.4 and Appendix A.4.2 of the linked version: GEN/CONT aggregation, fractional score updates alpha+=r and beta+=1-r, and independent Beta draws at selection. At depth H suppress expansion and selection of exhausted subtrees; use a fixed index rule for ties.
- Root resampling and refinement both cost one generation plus one exact evaluation. There is no extra rollout: each generated answer is evaluated directly. Repeated types remain separate tree nodes, as in answer-tree search; all random generations are conditionally independent given their parent type.
- The comparison policy knows the transition kernels but not future samples, and pays for the same expansions. Define its N_star(delta) by maximizing success at each fixed budget. Hidden-test error, mixed-model MCMC cost and noisy evaluations are separate extensions.
What would settle it?
Finite-budget upper bounds and matching bad instances for N_A or N_A/N_star, with explicit depth and rare-transition dependence. Determine whether the source rule has an unavoidable exponential overhead and whether a stated modification removes it; generic MCTS consistency is insufficient.
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
AB-MCTS supplies algorithms and empirical comparisons, including progressive widening, but not this guarantee. BRUE and VarDE already provide other tree-search guarantees. The finite-type benchmark and ratio are editorial choices; their precise novelty needs a dedicated best-arm/MDP audit. The source's Bayesian vocabulary does not make adaptive subtree scores stationary observations from a correct posterior model. This is an editorial, source-motivated research target. The preliminary review through 2026-11-20 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
- Inoue et al. — Wider or Deeper? Scaling LLM Inference-Time Compute with Adaptive Branching Tree Search ↗related algorithm · source checked 2026-11-20
Full HTML Sections 3–5 and Appendices A, C.10 and D checked: GEN/CONT selection, mixed-model and aggregation variants, empirical multi-model search. Finer real-world costs and final-answer selection are explicit directions. No finite-budget optimality theorem is supplied; candidate coverage is not selected-answer accuracy.
- Feldman and Domshlak — Simple Regret Optimization in Online Planning for Markov Decision Processes ↗partial theory · source checked 2026-11-20
Primary search abstract checked: BRUE gives exponential simple-regret/error decay in finite-MDP planning. Generic MCTS convergence is already studied; this does not analyze AB-MCTS's adaptive GEN/CONT backups.
- Luong et al. — Variance Driven Exploration: A Provable and Efficient Methodology for Pure Exploration in Highly Stochastic Environments ↗partial theory · source checked 2026-11-20
Primary search abstract checked: variance-aware allocation, MCTS and best-policy guarantees already exist. The finite-budget maximum-over-generated-answers objective and unbounded branching require an explicit comparison.