Multi-agent communication & games · Verification & proof search / Open question
Which Model Should Search Next?
One model can create useful starting points while another refines them well. Their relative benefit depends on the node and the remaining budget, not only on global average score. Efficiency payoff: Allocate cheaper and more capable models by marginal search value per paid resource, including context growth and evaluation cost.
Seed catalog · Showing the bundled record.
Problem statement
Across independent search episodes, use generators with unknown shared kernels on observed answer types, root type , and known exact scores . Expanding a depth- node with generator costs positive integer units. With budget per episode, derive the minimax regret , where is the optimal kernel-informed search value under the same budget. Seek a polynomial-time algorithm or a computational obstruction.
Assumptions and scope
- Each episode starts with an empty answer tree and the same root generator family. Any previously generated node below depth H may be expanded again; all generated answers remain available. Knowledge of kernels may transfer between episodes, but answers themselves do not.
- Conditional on the selected generator and parent type, child draws are independent with the indicated fixed kernel. Prices include generation/prefill and exact evaluation; a_l, b_l and v_l are known nonnegative integers with a_l+v_l>=1. The budget is a hard sequential cost cap, not merely an expected call count.
- The oracle knows kernels, not future outcomes. Explicitly charge the learner's planning arithmetic and memory in S,K,H,C,N; solving an exponentially large tree-state dynamic program for free is not an efficient upper bound. Wall-clock batching and surrogate evaluators would change the model.
What would settle it?
A sublinear-in-N regret bound with explicit parameter dependence and polynomial computational cost, with a lower bound separating statistical and planning barriers. Report the best fixed-model baseline as well as the stronger dynamic oracle.
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
Appendix D of AB-MCTS already implements multi-generator search; Section 5 explicitly calls for costs beyond API counts. This finite-type repeated-episode formulation is an editorial specialization, not a source-stated minimax conjecture. Existing MCTS/pure-exploration results must be compared using final-best-answer value rather than cumulative sampled reward. 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.
- 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.
- 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.