PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Michael Jerge, Suman Jana

arXiv:2609.30017v1cs.LGcs.AI

TL;DR

Hierarchical bandits can exploit tree structure in LLM inference, but typically require a smoothness schedule in advance despite piecewise-smooth objectives. CANOPY learns where smoothness holds from cheap probes and targets expensive evaluations at violations. It improves matched-budget performance across routing, identification, search, caching, and trimming benchmarks.

  • Problem

    Hierarchical bandits typically require a smoothness schedule in advance, although objectives may be only piecewise smooth with sharp boundaries.

    Source: §1 · p. 1

  • Method

    CANOPY uses cheap random-path probes to certify local aggregation bias and directs expensive leaf evaluations toward cells where the certificate detects a smoothness violation.

    Source: §1 · p. 2

  • Results

    Across twelve open-source benchmarks, CANOPY improves matched-cost or matched-compute performance, including 2.9× top-10 recall on RouterEval’s 1000-model pool versus the strongest structure-blind baseline.

    Source: §1 · p. 2

  • Takeaways & Limitations

    CANOPY improves over structure-blind search when probes are cheap and violations are sparse, as reflected across twelve public benchmarks.

    Source: §6 · p. 10

    The advantage is bounded by task conditions: homogeneous regions, saturated tasks, unreachable optima, stationary workloads, or little prefix overlap can leave no advantage to exploit.

    Source: §4.2 · pp. 9–10

Abstract

from arXiv · show

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.

1 INTRODUCTION

LLM inference tasks often require choosing among more candidates than can be evaluated, even when shared computation gives them a natural tree structure. CANOPY learns where smoothness holds and directs expensive evaluations toward violations, improving matched-cost or matched-compute performance across twelve benchmarks.

1 INTRODUCTION

  • Hierarchical candidates share more computation and tend to behave more similarly, except at a small number of sharp boundaries.Exhaustive evaluation is often unaffordable because candidates may require a generation, test run, or served request.Source: §1 · p. 1
  • Standard hierarchical bandits require a smoothness schedule in advance, although real objectives may be only piecewise smooth and valuable leaves may lie near sharp boundaries.Assuming too much smoothness risks pruning promising regions; conservatism can forfeit hierarchical-search savings.Source: §1 · p. 1
  • The overview depicts cheap-probe spread compared with a Lipschitz floor, followed by pruning of the certified-smooth subtree.Its red line marks the boundary splitting a cell.Source: Figure 1 · p. 2
  • After a smoothness violation is encountered, targeted leaf-level sampling is unavoidable up to logarithmic factors for identifying the best leaf.The paper states this result as Proposition 2.Source: §1 · p. 2
  • CANOPY certifies aggregation bias from data and directs expensive leaf evaluations to regions where its local smoothness certificate fails.The framework casts routing, prefix caching, and test-time search as budgeted multi-fidelity tree optimization.Source: §1 · p. 2
  • Across twelve open-source benchmarks, CANOPY improves performance at matched cost or compute, including 2.9× top-10 recall on RouterEval’s 1000-model pool versus the strongest structure-blind baseline.The RouterEval tree bandit is better at every tested budget.Source: §1 · p. 2

2 BACKGROUND

Prior work studies hierarchical optimization, multi-fidelity observations, and fixed-budget best-arm identification. CANOPY combines cheap structural search where aggregation is reliable with leaf-level certification where it is not.

Hierarchical and X-armed bandits

  • Hierarchical bandits control the gap between a cell’s observed value and its best descendant using known smoothness, schedule-free methods, or a search over candidate schedules.Adaptation to unknown smoothness is impossible from leaf evaluations alone, while random-path probes reveal the distribution of leaf values within a cell.Source: §2 · p. 2

Multi-fidelity optimization and best-arm identification

  • Multi-fidelity optimization combines cheap biased observations with expensive accurate ones; in CANOPY’s tree setting, the one-sided fidelity bias is the best leaf’s excess over the subtree average.Internal-node probes return subtree averages and leaf evaluations provide unbiased observations.Source: §2 · pp. 2–3
  • CANOPY combines structural search in regions where aggregation is reliable with targeted leaf-level certification where it is not.The leaf-level problem is fixed-budget best-arm identification, whose rate depends on a problem-specific hardness quantity.Source: §2 · p. 3

3 THEORY

CANOPY models tree search through the gap between a cell’s best leaf and its average, then replaces assumed smoothness and uniform descent with data-based certification and discontinuity-guided sampling. Its guarantees recover the smooth rate without violations and add costs tied to discontinuities when they occur.

3.1 NOTATION AND PRELIMINARIES

  • Aggregation bias is the gap between a cell’s largest leaf mean and its subtree average; tree-Lipschitzness bounds it by a level-dependent spread on smooth cells.The piecewise model permits K discontinuities, where only the trivial bias bound of 1 remains; near-optimality dimension d describes the growth of ε-optimal cells.Source: §3.1 · p. 3
  • For the tree model, internal-node probes return noisy subtree averages at cost c_p, while noisy leaf evaluations cost c_l and the learner is charged by total cost.The objectives include regret minimization and fixed-budget top-k identification; the stated discussion focuses on k = 1.Source: §3.1 · p. 3

3.2 THE OPTIMISTIC TREE-BANDIT ALGORITHM

  • Optimistic descent selects the child with the largest B-value, using a bias bonus to upper-bound the best reachable leaf beyond the estimated subtree average.The standard optimistic tree bandit is modified for average-backup values; CANOPY replaces its assumed bias schedule and uniform descent.Source: §3.2 · p. 4

3.3 CERTIFYING SMOOTHNESS FROM DATA

  • Random-path probes support a certificate that upper-bounds aggregation bias using a log-sum-exp bound, deconvolved probe-noise MGF, and empirical-Bernstein confidence bounds.Gaussian probe noise is divided out using its known MGF; probes are truncated to a stated range, with a corresponding probability term in the guarantee.Source: §3.3 · p. 4
  • When within-cell spread exceeds the Lipschitz prediction by a constant factor, CANOPY flags the cell; one discontinuity can flag a cell at each level, yielding O(KD) flagged cells.The certificate is valid on every instance and tight on benign instances, while flagged cells receive a data-driven rather than tight Lipschitz bias bonus.Source: §3.3 · p. 5

3.4 GUARANTEES

  • Fixed-budget identification combines cheap structural search over smooth regions with expensive leaf certification in flagged regions, with detection guaranteed under a spread-margin assumption.Once a violation is encountered, targeted leaf-level sampling is unavoidable up to a logarithmic factor; cheap probes cannot identify the best leaf within a cell from its mean distribution alone.Source: §3.4 · pp. 5–6
  • With no discontinuities, identification complexity is the smooth structural-search cost; sparse violations add per-violation certification cost, while dense violations approach structure-blind complexity.The favorable comparison requires cheap probes relative to leaf evaluations and sparse violations.Source: §3.4 · p. 6
  • For regret, each suboptimal discontinuity contributes O(log n/∆v), dispersion caps jump cells at KD, and fixed K leaves the polynomial rate unchanged.The smooth-cell analysis remains the standard HOO analysis, and K = 0 recovers the clean Lipschitz rate.Source: §3.4 · p. 6

4 EXPERIMENTS

The experiments cover five downstream task families across twelve public benchmarks, with methods compared at matched metrics or budgets. Results favor CANOPY across identification, search, routing, caching, and trimming, while the scope summary identifies conditions where its advantage is absent or limited.

4.1 SETUP

  • Twelve public benchmarks cover five task families, selected to test distinct tree structures and pair cases where the theory’s preconditions plausibly hold or fail.The experiments include routing, caching, trimming, top-k identification, and test-time search.Source: §4 · p. 6, §4.1 · p. 7
  • Search and trimming use five models spanning capability levels; results compare matched budgets using each task family’s specified metric and baseline.Baselines include a structure-blind router, successive elimination, best-of-N, LRU/LFU, and fixed trim levels.Source: §4.1 · pp. 7–8

4.2 RESULTS

  • Across five task families, matched-budget results include 2–3× identification recall, 1.6× as many SWE-bench issues resolved, and 5.39 versus 3.02 blocks reused per request.Adaptive trimming also beats every fixed trim at matched tokens.Source: Table 1 · p. 7, §4.2 · p. 8
  • In τ-bench, the regional router beats the flat learner in 4 of 5 replicates, with mean success of 0.463 versus 0.323.The reported gap is +0.14 ± 0.27, and single replicates are noisy under terminal-reward credit assignment.Source: §4.2 · p. 8
  • At B=300, recall@10 is 0.253 versus 0.124, and at B=600 it is 0.370 versus 0.126; the advantage narrows to 1.3× at B=2400.Absolute recall remains modest for top-10 identification over 1000 models.Source: §4.2 · p. 9
  • Value-guided search gains +0.087 on MATH, +0.111 on GPQA, and +0.123 on SWE-bench; its gain shrinks with budget and appears only for capable models.On SWE-bench it resolves 1.6× as many issues as best-of-N, rising to 1.8–2.2× in significant tight-budget cells; probes follow the best continuation on 73% of pivotal MATH steps and all 18 pivotal SWE-bench steps.Source: §4.2 · p. 9
  • On a live vLLM server, prefix caching cuts median time-to-first-token 3.6×; on the Mooncake trace, the adaptive cache reuses 5.39 versus LRU’s 3.02 blocks per request at B=16.No prefix trim, including the adaptive method, recovers full-context F1 on LongBench.Source: §4.2 · p. 9
  • CANOPY’s advantage is bounded by its operating conditions: homogeneous regions, saturated tasks, unreachable optima, stationary workloads, or little prefix overlap may leave little or no gain.On MMLU, trimming beats only the verbose default; on the hardest SWE-bench tier, both arms remain near zero at small budgets.Source: §4.2 · pp. 9–10

5 RELATED WORK

Prior hierarchical bandits assume or search over smoothness schedules, while CANOPY uses probe feedback to certify local aggregation bias. Its approach targets sparse smoothness violations and treats several LLM inference and serving tasks as a shared tree-optimization problem.

5 RELATED WORK

  • HOO assumes a known smoothness schedule, POO searches candidate schedules, and adaptation to unknown smoothness from leaf evaluations alone is impossible.Random-path probes supply additional information about the distribution of leaf values within a cell.Source: §5 · p. 10
  • Unlike dispersion-based optimization of piecewise-smooth objectives, CANOPY detects cells where smoothness predictions fail and directs expensive leaf evaluations there.A lower bound shows this targeted leaf-level cost is unavoidable up to logarithmic factors.Source: §5 · p. 10
  • Routing, prefix caching, test-time search, and prompt trimming can be treated as instances of one cost-budgeted multi-fidelity tree optimization problem.These applications expose hierarchical structure through model groups, shared token prefixes, partial generations, or related compressed contexts.Source: §5 · p. 10

6 DISCUSSION

CANOPY treats several LLM inference and serving tasks as budgeted tree-bandit problems, certifying aggregation bias from data and targeting expensive evaluations where smoothness predictions fail. The appendix details the certificate’s probe assumptions, concentration treatment, and mechanization scope.

6 DISCUSSION

  • CANOPY improves over structure-blind search when probes are cheap and smoothness violations are sparse, across the paper’s twelve public benchmarks.The discussion identifies routing, prefix-cache management, prompt trimming, top-k identification, and test-time search as instances of the same tree-bandit structure.Source: §6 · p. 10

A CONCENTRATION AND SELF-CERTIFICATION

  • The certificate seeks a high-probability upper bound on aggregation bias, defined as the best leaf mean in a cell minus its subtree average, using random-path probes.Each probe samples a leaf uniformly from the node’s leaves and observes its noisy reward.Source: A CONCENTRATION AND SELF-CERTIFICATION · p. 14, §A.1 · p. 14
  • The Lean development mechanizes Theorems 1–3 and the light-tail rate, while using empirical-Bernstein, successive-rejects, and HOO results as named hypotheses where invoked.The full-theorem algebra is also checked symbolically and on 20k randomized exact instances.Source: A CONCENTRATION AND SELF-CERTIFICATION · p. 14
  • The Bernstein step truncates at z=3 over [−zσ, 1 + zσ], with an approximately 0.27% per-probe Gaussian escape probability; increasing z widens the Bernstein range.The escape term enters the theorem’s coverage bound after a union bound over probes.Source: A CONCENTRATION AND SELF-CERTIFICATION · p. 14

A.1 SETUP AND ASSUMPTIONS

  • The certificate assumes independent Gaussian noise, because exact knowledge of its moment-generating function permits deconvolution in the required upper-bound direction.Extending the argument to general sub-Gaussian noise is left to future work.Source: §A.1 · p. 14

A.2 FORMAL PROOF OF THEOREM 1

The proof certifies aggregation bias from random-path probes, then uses that certificate to separate smooth structural search from expensive leaf certification in jump cells. Its fixed-budget guarantee depends on detecting violations and succeeds when the stated detectability margin holds.

A.2 FORMAL PROOF OF THEOREM 1

  • With probability at least 1−δ−2nΦ̄(z), the certificate inequality holds simultaneously over the finite grid Λ of positive λ values, under bounded leaf means and Gaussian noise.The probes are truncated to [−zσ, 1+zσ] to control the probability of leaving the range.Source: §A.2 · pp. 14–15
  • The certificate bounds aggregation bias by combining a soft-maximum bound, Gaussian-noise deconvolution, and empirical concentration of probe statistics.The proof uses an empirical-Bernstein upper bound for the exponential probe moment and a lower-confidence bound for the subtree mean.Source: §A.2 · p. 15
  • A separate confidence slice estimates the subtree mean; allocating δ across the grid and mean bounds yields coverage for one node, and allocating δv across probed nodes extends it to a set.The range-event failure probabilities also accumulate across nodes.Source: §A.2 · p. 15

B.1 COMPLEXITY DEFINITIONS

  • The structural complexity c0 measures cheap-probe search over certified-resolution cells that survive sound pruning, using their subtree averages and deflated gaps.The implementation uses coarse descent followed by a race over surviving cells.Source: §B.1 · p. 16
  • The leaf-certification complexity hk measures the cost of identifying the best leaf within jump cell Ck using expensive evaluations.The edge-targeted complexity combines structural search with localized certifications.Source: §B.1 · p. 16

B.2 FORMAL PROOF OF THEOREM 2 (MAIN TEXT)

  • The fixed-budget guarantee bounds misidentification by detection failure plus a term that decreases exponentially with budget and depends on explored nodes.For a complete b-ary tree with N leaves, the explored-node factor is O(N).Source: §B.2 · pp. 16–17
  • The algorithm separates detection, structural search, and leaf certification; its detector flags violations without false flags and requires a positive margin to avoid missed violations.When each violation exceeds the smoothness floor by γ, the stated detection sample size is O(log(KD/δdet)/γ²).Source: §B.2 · pp. 16–17
  • Off the flagged set, sound pruning preserves the optimal branch and search reduces to fixed-budget identification among certified cells; flagged jump cells require expensive leaf-level identification.The budget is allocated between smooth search and certification to balance their error probabilities.Source: §B.2 · p. 17

B.3 PROOF OF THE PARTIAL LOWER BOUND (PROPOSITION 2)

The lower-bound construction makes cheap probes uninformative about which leaf is optimal inside a jump cell. It therefore reduces identification to a leaf-only problem and establishes necessity only for the certification component.

B.3 PROOF OF THE PARTIAL LOWER BOUND (PROPOSITION 2)

  • The hard instance permutes a fixed gap profile among m leaves in a jump cell while keeping all outside means below the cell’s worst leaf.The instances share the same multiset of means inside the cell.Source: §B.3 · pp. 17–18
  • Cheap internal-node probes have the same distribution across permutations, so they provide no information about the optimal leaf’s identity.This holds for both subtree-average probes and random-path samples.Source: §B.3 · p. 18
  • Conditioning on cheap observations reduces any budget-B algorithm to leaf-only identification with at most ⌊B/cℓ⌋ evaluations in the jump cell.Evaluations outside the cell are constants and carry no information about the permutation.Source: §B.3 · p. 18
  • When B is at most c cℓh/log m, some permutation of the gap profile yields constant error, making the certification term necessary up to a log m factor.The bound does not establish necessity of the structural component c0, which is negligible in this constructed family.Source: §B.3 · p. 18

C REGRET ANALYSIS IN THE PIECEWISE-LIPSCHITZ REGIME

Inflating the optimism bonus only on detected discontinuity cells decomposes regret into the smooth rate plus an additive penalty for discontinuities. Tree-dispersion bounds how many cells can straddle those discontinuities.

C REGRET ANALYSIS IN THE PIECEWISE-LIPSCHITZ REGIME

  • Inflating the optimism bonus only on detected discontinuity cells yields the smooth regret rate plus an additive penalty in the number of discontinuities.The result concerns the optimistic tree bandit on a piecewise-Lipschitz objective.Source: C REGRET ANALYSIS IN THE… · p. 19

C.1 THE TREE-DISPERSION CONDITION

  • A function is piecewise tree-Lipschitz with K discontinuities when at most K boundary points exist and every cell containing none is tree-Lipschitz.Tree-Lipschitz behavior is defined with respect to the tree metric.Source: §C.1 · p. 19
  • At each level at most K cells straddle discontinuities, so across depth D the tree has at most KD jump cells.Source: §C.1 · p. 19

C.2 FORMAL PROOF OF THEOREM 3

The regret proof partitions cells into smooth and jump sets, applying the classical smooth-tree analysis to one and charging a discontinuity penalty to the other. For fixed K, the jump contribution does not change the learning rate, and K=0 recovers the Lipschitz rate.

C.2 FORMAL PROOF OF THEOREM 3

  • Theorem 6 bounds regret conditioned on detecting the O(KD) jump cells, assuming piecewise tree-Lipschitz regions and near-optimality dimension d.The jump-cell contribution depends on the smallest positive gap Δmin.Source: §C.2 · p. 19
  • The proof partitions all nodes into smooth and jump cells, then divides cumulative regret according to the type of cell selected.Regret is measured against the committed cell’s value, matching expected sampled-leaf regret.Source: §C.2 · p. 19
  • On smooth cells the aggregation bias follows spread(l)=Lρ^l, so standard HOO analysis controls regret through near-optimality dimension d.Source: §C.2 · pp. 19–20
  • On jump cells the algorithm inflates the bias bonus to an empirical worst-case bound, keeping the optimistic index valid despite violations of the smoothness schedule.The bound applies a UCB argument per suboptimal jump cell; an optimal-containing jump cell has zero gap and contributes no regret.Source: §C.2 · p. 20
  • Summing jump-cell regret uses the tree-dispersion bound of at most KD cells and yields the discontinuity penalty in the combined regret decomposition.Source: §C.2 · p. 20
  • For fixed K, discontinuities change constants and a log n factor rather than the learning rate; K=0 recovers the clean Lipschitz rate.Source: §C.2 · p. 20

D SYNTHETIC VALIDATION OF THE MULTI-FIDELITY MACHINERY

Controlled synthetic studies sweep probe cost, memory, smoothness, and discontinuity count to test CANOPY’s multi-fidelity machinery. Results show when tree structure helps, how data-driven adaptation performs, and how it behaves as violations proliferate.

Top-k identification

  • At budget 1500, the beam variant reaches 0.84 recall against 0.57 for successive elimination when probes are cheap; the sound variant reaches 0.62 against 0.57.The beam’s focusing drives the empirical advantage; the sound variant is a certified never-worse floor.Source: D SYNTHETIC VALIDATION OF THE… · p. 21, Figure 3 · p. 22

Finite-state compression

  • On an infinite-depth arity-3 tree, the memory-bounded rule explores near 70 nodes as the tree grows from 121 to nearly 800,000 nodes, with regret between 663 and 1702.This is the discrete witness of depth-independent memory in Proposition 1.Source: D SYNTHETIC VALIDATION OF THE… · p. 21

Regret versus memory

Estimating the smoothness

Graceful degradation in the violation count

  • As discontinuities increase, the detect-and-relax hybrid degrades smoothly from near-perfect top-1 accuracy toward the structure-blind floor while dominating both alternatives.The fixed-budget study uses branching 4, depth 5, budget 400, and cp/cℓ = 0.05.Source: D SYNTHETIC VALIDATION OF THE… · p. 21, Figure 6 · p. 23

From the rate to the data

  • On a tree-Lipschitz value function, average regret decays toward zero with horizon, with measured cumulative-regret exponent α ≈ 0.77 < 1 and estimated near-optimality dimension d̂ ≈ 0.For RouterBench routing values, the category tree explains about 31% of per-prompt value variance and the benchmark-family tree explains about 53% of region-value variance; remaining within-region variation is per-prompt noise.Source: D SYNTHETIC VALIDATION OF THE… · pp. 21–22, Figure 7 · p. 24

E ADDITIONAL EXPERIMENTAL RESULTS

The appendix reports additional experiments across routing, top-k identification, test-time search, caching, and prompt trimming, with outcomes varying by budget, task difficulty, and available quality headroom. Its evidence includes both favorable comparisons and settings where gains narrow or disappear.

E.1 ROUTING

  • On six Bedrock models across eight MMLU subjects, the regional router reaches near-oracle quality at the lowest cost of any realizable policy and beats the flat learner and strongest fixed model.Only the hierarchical and flat policies learn online; the other policies use ground truth and pay no exploration cost.Source: §E.1 · p. 25, Table 3 · p. 27
  • The regional τ-bench learner beats the flat learner in 4 of 5 replicates, with mean success 0.463 ± 0.156 versus 0.323 ± 0.213, but the strongest fixed policy reaches 0.600.The authors characterize this as directional evidence: the learned routers’ advantage is cost-adjusted, not absolute.Source: §E.1 · p. 25, Figure 9 · p. 26, Table 3 · p. 27

E.2 TOP-k IDENTIFICATION

  • 2.9× recall at B=600 narrows to 1.3× at B=2400 on RouterEval’s 1000-model pool, with successive elimination staying within one standard error of uniform sampling.The hierarchical advantage is largest at low-to-mid budgets as structure-blind baselines catch up.Source: §E.2 · p. 25, Figure 8 · p. 26

E.3 TEST-TIME SEARCH

  • In the pre-registered hardest-tier SWE-bench Verified run, both arms resolved 2/42 issues at B=6; at B=9, value-guided search resolved 3/42 versus 2/42 for best-of-N.The directional hypothesis failed, and both arms were near floor; the authors attribute the lack of guidance opportunity to issues being beyond the model’s reach at that budget.Source: §E.3 · p. 25

E.5 PROMPT TRIMMING

  • Prompt trimming spans little headroom on MMLU, a real quality-token tradeoff on LongBench, and strict dominance on BBH.On LongBench, retrieval-scored chunk selection improves every fixed trim by +0.10 to +0.13 F1 at tight budgets and moves the adaptive point to 0.407 F1 at 2,701 tokens.Source: §E.5 · p. 26, Figure 12 · p. 28, Table 9 · p. 31

CAPABILITY LADDER; GSM8K (near-saturated control)

REPOSITORY-LEVEL CODE

  • The repository-level code sweep covers 78–80 SWE-bench Verified issues per model-budget cell; HumanEval and MBPP show nulls for Llama-3.1-70B with a weak public-test probe and near-saturated benchmarks.Instances with evaluation-harness errors were dropped from both arms in the code sweep.Source: Table 5 · p. 27, Table 6 · p. 29

E.4 PREFIX CACHING AND SYSTEMS

  • On a 20k-request production trace, adaptive caching matches the offline optimum and beats engine-default LRU, especially at tight budgets; after a popularity shift, it adapts fastest and dominates LRU.On live vLLM, increasing the KV-cache budget lowers median TTFT and raises prefix-cache hit rate.Source: Figure 11 · p. 28, Figure 12 · p. 28, Table 8 · p. 31

F FUTURE WORK

The paper argues that its approach extends beyond tree-structured problems when an objective has a suitable metric and regional values are weighted averages. It sketches extensions to metric-space and embedding hierarchies, DAGs, and sparse attention for long-context reinforcement learning.

F FUTURE WORK

  • The method’s core ingredients are a metric under which the objective is smooth and an aggregation map that averages points in a region, rather than a tree specifically.The paper says the optimistic engine, data-driven smoothness certificate, and discontinuity-guided sampling carry over when those ingredients hold.Source: F FUTURE WORK · p. 32
  • For general metric spaces, a hierarchical cover can replace the dyadic tree while preserving the near-optimality-dimension analysis and leaving the within-cell certificate unchanged.For language-model embeddings, the paper proposes spherical caps under the angular metric, replacing the sparse and brittle token-prefix tree for routing.Source: F FUTURE WORK · p. 32
  • With weighted subset averages, the noise-deconvolved certificate is unchanged, extending the framework to directed acyclic and lattice-structured index sets.The paper also sketches sparse attention as a hierarchical bandit over context blocks, while leaving the temporal-smoothness lemma and importance-ratio bound for future work.Source: F FUTURE WORK · p. 32
Loading 2609.30017v1…