Many LLM inference problems, including model routing, prefix-cache management, prompt trimming, and test-time search, can be viewed as optimization over a tree. This structure arises naturally from autoregressive generation: every prefix defines a node, and its continuations form a subtree below it. Internal nodes of the tree provide cheap but biased estimates of a region's value, while leaf evaluations are expensive but accurate. Hierarchical bandit methods can exploit this structure, but typically require a specific smoothness schedule to be specified in advance, even though real objectives are often only piecewise smooth and their optima may lie near sharp boundaries. We introduce CANOPY, a multi-fidelity tree bandit that learns where the smoothness prior is valid rather than assuming it globally. CANOPY uses cheap random-path probes to construct an online certificate of local aggregation bias, then directs expensive leaf evaluations toward cells where the certificate detects a smoothness violation. We prove fixed-budget and regret guarantees whose additional cost is additive in the number of discontinuities, recovering the smooth-tree rate when no violations are present and approaching structure-blind search as violations become dense. Across routing, top-k identification, test-time search, caching, and prompt trimming, CANOPY consistently improves matched-budget performance, including 2.9× higher top-10 recall on a 1000-model pool, 1.6× more SWE-bench Verified issues resolved than best-of-N, and 3.6× lower median time-to-first-token with prefix caching.
Figures & tables
Benchmark
Ours
Best baseline
Δ
selection
MMLU routing ( 6 models) quality @ cost
.977 @ .254
.943 @ .363 (flat)
+.034
τ -bench retail ( 5×80 tasks) success, 5-replicate mean
.463 ± .156
.323 ± .213 (flat)
+.14 (4/5)
Top- k id. ( 1000 models), B=600 recall@ 10
.370 ± .018
.126 ± .013 (s.e.)
2.9×
search
MATH ( 300 , Llama-70B) accuracy
.617
.530
+.087[+.04,+.14]
GPQA-Diamond (Llama-70B) accuracy
.424
.313
+.111[+.04,+.19]
SWE-bench Verified ( 261 ) resolved
.318
.195
+.123[+.08,+.17]
Table 1: Headline results at matched metric. In every row green marks the better and red the worse of ours against the baseline. Search rows report the paired same-item Δ with 95% confidence intervals. The τ -bench row compares the two learned routers. Oracle references, per-benchmark detail, and confidence intervals are in Appendix E .
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Policy
Final regret
Assumed L (too tight, L=0.05 )
4076
Assumed L (too loose, L=3.0 )
3424
Oracle-tuned fixed L=0.8
3127
Estimated L (ours)
3029
Appendix
Table 2: Lipschitz-constant ablation: final regret for mis-specified fixed L , the oracle-tuned fixed L , and the data-driven estimator (ours).
Policy
Regret
Avg. quality
Rel. cost/query
Hierarchical (ours)
472 ± 3
0.977 ± 0.001
0.254 ± 0.002
Flat (structure-blind)
878 ± 8
0.943 ± 0.001
0.363 ± 0.006
Best single (oracle ref.)
831 ± 8
0.936 ± 0.001
0.316 ± 0.000
Highest-quality (oracle ref.)
843 ± 4
0.969 ± 0.001
0.432 ± 0.000
Per-prompt oracle
0 ± 0
1.000 ± 0.000
0.067 ± 0.001
Appendix
Table 3: Routing detail. Top: routing over six real Bedrock models on MMLU, with 8 subjects as regions and a horizon of 6 k. Only the hierarchical and flat policies learn online. The rest are computed from the ground truth and pay no exploration cost. Middle: τ -bench retail, the online contextual UCB router (regional) against the structure-blind flat learner and the fixed models. Bottom: the seed-variance study, 5 independent replicates of the two learned routers over the same 80 tasks, of which replicate 1 is the main run above.
Cost budget
150
300
600
1200
2400
Hierarchical (ours)
0.124 ± 0.013
0.253 ± 0.016
0.370 ± 0.018
0.464 ± 0.014
0.563 ± 0.014
Successive elimination
0.103 ± 0.014
0.124 ± 0.014
0.126 ± 0.013
0.307 ± 0.012
0.421 ± 0.014
Uniform
0.103 ± 0.014
0.124 ± 0.014
0.126 ± 0.013
0.303 ± 0.012
0.428 ± 0.013
Appendix
Table 4: Top- 10 identification on the RouterEval 1000 -model pool: mean recall@ 10 ( ± SEM over 20 seeds and 9 evaluation splits) as the cost budget grows. The probe/leaf cost ratio is 0.05 , and the hierarchical method’s cost includes the certificate pre-pass.
Budget (calls)
best-of-N resolved [95% CI]
value-guided resolved [95% CI]
Δ (paired) [95% CI]
9
0.195 [0.15, 0.25]
0.318 [0.26, 0.38]
+0.123 [+0.08, +0.17]
Appendix
Table 5: Repository-level code: value-guided patch search vs. best-of-N at matched compute on SWE-bench Verified ( 261 issues, “ 15 min– 1 hour” tier, claude-sonnet-4.5). Resolved rate is the official criterion, and Δ is the paired same-issue gap with a 95% bootstrap CI over issues.
Model
best-of-N [95% CI]
value-guided [95% CI]
Δ [95% CI]
mistral-large
0.084 [0.05, 0.12]
0.140 [0.10, 0.18]
+0.057 [+0.01, +0.10]
sonnet45
0.503 [0.45, 0.56]
0.837 [0.79, 0.88]
+0.333 [+0.28, +0.39]
llama8b
0.537 [0.48, 0.59]
0.390 [0.34, 0.45]
−0.147 [-0.21, -0.09]
llama3-1-70b
0.540 [0.48, 0.59]
0.607 [0.55, 0.66]
+0.067 [+0.02, +0.12]
nova-pro
0.623 [0.57, 0.68]
0.753 [0.70, 0.80]
+0.130 [+0.08, +0.18]
Appendix
Table 6: Test-time search, value-guided against best-of-N at matched compute, with 95% bootstrap confidence intervals, Δ the paired same-item gap, and bold where the interval excludes zero. Capability ladder: five models on MATH and GPQA-Diamond, with GSM8K as the near-saturated control. The gain is largest for capable but unsaturated models and vanishes or reverses for the weakest, which is the unreachable regime. Mistral-Large’s low absolute MATH accuracy reflects answer-format non-compliance rather than reasoning ability. Repository-level code: the SWE-bench model × budget sweep over 78 – 80 Verified “ 15 min– 1 hour” issues per cell, with instances whose evaluation harness errored dropped from both arms. Code synthesis: the HumanEval and MBPP nulls for Llama-3.1-70B. The public-test cheap probe is weak and both benchmarks are near-saturated, a limit fixed before the results were seen.
Quantity
Value
Cheap-vs-true node value (Spearman ρ )
0.485
Cheap-vs-true node value (Pearson r )
0.427
Edge-following hit rate, all steps (chance 0.33)
0.940
Edge-following hit rate, pivotal steps only
0.734 [0.64, 0.82] ( n =109)
Mean true value lost per step (edge gap)
0.025
Pivotal-step fraction
τ=0.25 : 11%; τ=0.5 : 6%; τ=0.75 : 4%
Appendix
Table 7: The value function as almost tree- K -Lipschitz, measured in the wild: cheap-vs-true node-value correlation (the tree-Lipschitz backbone) and the count of pivotal steps K (violations). Top: MATH partial traces (cheap self-consistency probe). Bottom: the real-code analog on SWE-bench Verified ( 60 issues and 540 candidate patches, cheap FAIL_TO_PASS test probe vs. the official resolved criterion). The empirical counterpart of the synthetic violation-family task (Appendix D ).
Policy
Stationary (B=64)
After shift (B=16)
LRU
4.74
3.02
LFU
5.92
5.39
Adaptive (ours)
5.89
5.39
Offline-optimal (static)
5.92
5.39
Appendix
Table 8: Caching and systems detail. Mooncake: prefix-cache management on the real tool-agent production trace of 20 k requests, measured in blocks reused per request. Adaptive matches the offline optimum and beats the engine-default LRU, most at tight budgets. Live vLLM: automatic prefix caching on against off, reporting TTFT, latency, throughput, and prefix-cache hit rate on a shared-prefix workload with the built-in LRU eviction. Eviction policies: realized TTFT saved in milliseconds on the GPU-calibrated shared-prefix workload, stationary and post-shift. Adaptive beats the engine-default LRU throughout and dominates after the shift.
As pretraining scaling laws approach saturation, Test-Time Scaling (TTS) has emerged as an important direction for improving reasoning by allocating inference-time compute to a fixed model prior. Viewed at a high level, TTS reframes inference as search over a space of partial reasoning states. While Chain-of-Thought (CoT) exposes intermediate steps, common instantiations rely on single-trajectory decoding, limiting recovery from early errors and exploration. This survey systematizes recent progress in tree-search-based reasoning, viewing inference as instance-specific optimization rather than decoding. We trace the evolution from uninformed search to Monte Carlo Tree Search (MCTS), highlighting how sampling-based control supports principled exploration-exploitation trade-offs. To unify a fragmented literature, we introduce a Unified Design Space spanning search topology, evaluation signals, and control dynamics, and advocate a standardized compute-reporting abstraction to make compute-accuracy trade-offs explicit and comparable.
Jiaqi Wei, Xiang Zhang, Yuejin Yang +10
1Zhejiang University · 2Shanghai AI Laboratory · 4Fudan University +3
The rapid development of large language models, each with distinct capabilities and inference costs, raises a practical deployment question: given an incoming request, which model should handle it? We present OrcaRouter, a production-oriented LLM router that combines a LinUCB-based contextual bandit over lexical and sentence-embedding features with a hybrid offline-online learning protocol. Offline, OrcaRouter obtains full-information feedback by evaluating each candidate model on a curated set of routing prompts, yielding a reward matrix used to fit one ridge regressor per arm. At deployment time, it initializes from these parameters and can optionally continue learning from bandit feedback, updating only the selected model's arm after observing its reward. At the time of our RouterArena submission (May 20, 2026), OrcaRouter-Adaptive ranked second on the public RouterArena leaderboard with an arena score of 72.08, achieving 75.54% accuracy at a cost of USD 1.00 per 1,000 queries.
Large language models (LLMs) achieve impressive performance across multiple domains, but using the most capable model for every query is prohibitive at scale. LLM routing exploits diversity in model capability and cost by assigning each query to a suitable model to balance utility and budget. Current methods have two limitations: (i) they either use heuristics that do not always enforce the budget constraint or impose a fixed per-query budget that cannot adapt across the workload and leads to suboptimal performance; (ii) they require supervised learning on a dense dataset with statistics for every query-model pair, which is expensive to collect. To address these challenges, we formulate LLM routing as a constrained contextual multi-armed bandit problem and introduce WISERouter (WR for short), a framework that supports offline learning from historical interactions as well as online learning with exploration. We further prove that WR-Online achieves a sublinear regret bound of O(T) over a time horizon T. Empirical results on RouterBench and SWE-Bench demonstrate that (i) WR-Offline surpasses existing baselines in performance under a fixed budget and adheres more closely to budget constraints, and (ii) WR-Online achieves comparable performance to the baselines, while using substantially less exploration data.