← All AI/ML open problems

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.

OpenEditorially scopedSpecified modelCompiled 2026-11-20

Seed catalog · Showing the bundled record.

Problem statement

Consider depth-HH answer trees with observed types s∈[S]s\in[S], exact scores r(s)∈[0,1]r(s)\in[0,1], a root generator P0P_0 and refinement kernels PsP_s. Each expansion independently samples a new child from its parent's kernel; nonzero probabilities are at least pmin⁡p_{\min} and some score-one type is reachable within depth HH. For the Beta AB-MCTS-A rule with prior Beta⁡(1/2,1/2)\operatorname{Beta}(1/2,1/2), determine NA(δ)=min⁡{B:Pr⁡(max⁡v∈TBr(sv)<1)≤δ}N_A(\delta)=\min\{B:\Pr(\max_{v\in T_B}r(s_v)<1)\leq\delta\}. Bound its overhead relative to the optimal kernel-informed search, in S,H,pmin⁡,δS,H,p_{\min},\delta.

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

  1. 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.

  2. 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.

  3. 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.