CANOPY is a multi-fidelity tree bandit designed for LLM inference problems such as , prefix caching, and test-time search. It addresses the limitation of standard hierarchical bandits that require a pre-specified smoothness schedule. CANOPY uses cheap random-path probes to construct an online certificate of local aggregation bias, then directs expensive leaf evaluations only to regions where the certificate detects a smoothness violation. This approach learns where the smoothness assumption holds rather than assuming it globally.
Evaluated across twelve benchmarks, CANOPY consistently outperforms baselines at matched budgets. Notably, it achieves 2.9× higher top-10 recall on a 1000-model pool, 1.6× more SWE-bench Verified issues resolved compared to best-of-N, and 3.6× lower median time-to-first-token with prefix caching. The method also shows gains on MATH, GPQA-Diamond, and other tasks.
This is interesting because it eliminates the need to manually specify smoothness schedules, making hierarchical bandits more practical for real-world LLM serving systems. The technique of online certification of local smoothness from cheap probes is a novel contribution that could generalize to other tree-structured optimization problems.