Canopy improves multi-level search in language model tasks

Canopy: Exploiting Piecewise Smooth Tree Priors for Multi-Fidelity Bandits

Machine LearningArtificial Intelligence

Summary

Many problems in using large language models can be thought of as searching a big tree where some parts are cheap to explore but less accurate, and other parts are expensive but precise. The authors noticed that previous methods assumed the tree's smoothness everywhere, which isn't true for real data that can suddenly change. They created Canopy, a method that learns which parts of the tree are smooth and focuses expensive checks where this assumption breaks down. This approach performs better on tasks like model selection, caching, and prompt shortening, saving time and improving results.

What this means in practice

  • For machine learning engineers: Optimize model routing and test-time search more efficiently by focusing expensive evaluations where the underlying objective changes sharply.
  • For data infrastructure teams: Reduce latency in language model deployments by improving prefix cache management and prompt trimming with better multi-fidelity tree search.

Authors

Michael Jerge, Suman Jana

Abstract

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\times$ higher top-10 recall on a 1000-model pool, $1.6\times$ more SWE-bench Verified issues resolved than best-of-$N$, and $3.6\times$ lower median time-to-first-token with prefix caching.