CANOPY uses random-path probes to certify smoothness violations online, improving routing, top-k identification, test-time search, caching, and prompt trimming at matched budgets

CANOPY frames several LLM inference problems, including model routing, prefix-cache management, prompt trimming, and test-time search, as optimization over a tree: every prefix is a node, its continuations form a subtree, internal nodes give cheap but biased estimates of a region's value, and leaf evaluations are expensive but accurate. Prior 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. This unified view and problem setting are stated explicitly in the abstract and motivate the method design.

CANOPY does not assume a global smoothness prior; it learns where the smoothness prior is valid by using cheap random-path probes to construct an online certificate of local aggregation bias, then directing expensive leaf evaluations toward cells where the certificate detects a smoothness violation. Relative to hierarchical bandits that need a pre-specified smoothness schedule, this turns smoothness from an input assumption into an object that can be checked online. The abstract describes the probes, the certificate, and the evaluation steering, but does not give the certificate's concrete form, thresholds, or probe budget allocation.

The authors 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. The guarantees place a weaker piecewise-smooth assumption into the analysis rather than holding only under global smoothness. The abstract states the form of the guarantees and their two limiting behaviors, but gives no constants, rate expressions, or proof techniques.

Across routing, top-k identification, test-time search, caching, and prompt trimming, CANOPY consistently improves matched-budget performance, including 2.9x higher top-10 recall on a 1000-model pool, 1.6x more SWE-bench Verified issues resolved than best-of-N, and 3.6x lower median time-to-first-token with prefix caching. These results span multiple downstream tasks rather than a single benchmark, indicating transferability across tree-structured inference optimization settings. The abstract reports matched-budget comparisons and three specific multipliers, but does not give baseline details, budget sizes, or statistical uncertainty for each task.

The result targets settings that model LLM inference problems as tree-structured multi-fidelity optimization: every prefix is a node, internal nodes are cheap and biased, leaves are expensive and accurate, and the objective is only piecewise smooth with optima possibly near sharp boundaries. It suits readers who must allocate cheap probes and expensive evaluations under a fixed budget, such as those working on model routing, top-k identification, test-time search, prefix-cache management, and prompt trimming. The theoretical guarantees apply where the additional cost is additive in the number of discontinuities, degenerating to the smooth-tree rate when no violations are present and to structure-blind search as violations become dense.

The abstract does not give the certificate's concrete form or decision thresholds, the budget allocation for random-path probes, the rate expressions and constants of the fixed-budget and regret guarantees, or the specific baseline settings, matched-budget sizes, and statistical uncertainty for each task. It also lists only three multiplier results without stating the model-pool size, number of issues, or hardware conditions under which they were measured. Readers who care about these details will need the body and experimental sections.