acceptodds
Under review as a conference paper at ICLR 2027

Frequencies Rank, Probabilities Allocate: Calibrated Draft Trees for Drafter-Free Speculative Decoding

Abstract

Drafter-free speculative decoding verifies trees of continuations retrieved from the prompt, the output so far, or a datastore, and allocates each tree by retrieval scores, such as n-gram frequencies, that rank candidates. We show that ranking is not enough: over all candidate trees, best-first allocation is invariant to a continuous, strictly increasing transformation of edge scores if and only if it is a power map; scores that order every set of siblings correctly can still lose a factor of K in expected accepted draft tokens; and errors of conditional acceptance probabilities along root paths bound the loss. Motivated by source- and depth-dependent miscalibration of retrieval frequencies on real traces, we introduce CalTree, a 29-parameter acceptance model fitted on annotation-free replays of the target's own generations, over retrieval and request-local evidence. On five targets from 1.5B to 32B parameters, it generates 2.6–6.5% more tokens per verification pass than SSSD on Spec-Bench and 4.5–24.5% more on code editing, at every tested budget and target. Source and depth discounts tuned for this metric at each budget on the same replays recover 24–53% of the Spec-Bench gain, and normalizing CalTree's probabilities over the retrieved siblings keeps their order but forfeits 1.3–5.0 points at the tested budgets. Scores fitted on chat transfer to code, and a Qwen2.5-7B scorer to four other targets, without refitting. In fixed-load SGLang benchmarks, CalTree-LR raises throughput over SSSD by 1.0–3.0% on Spec-Bench and 2.6–4.0% on code editing; full-workload outputs are not always token-identical to autoregressive decoding.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Speculative Decoding, Drafter-Free Decoding, Draft Trees, Calibration, LLM Inference Acceleration

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_gADsOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

CalTree separates sibling ranking from allocating a speculative tree’s node budget across branches and depths. A 29-parameter logistic model predicts conditional acceptance using retrieval and request features, and path probabilities guide tree construction. Experiments span five target models, with modest SGLang throughput gains over native SSSD.

Critical strengths
  1. The paper clearly motivates the distinction between sibling ranking and tree allocation.

  2. The lightweight model uses retrieval, repetition, and long-range-match features without target weights or hidden states, fitting the existing framework.

Critical weaknesses
  1. The advantage over simpler scoring is unclear. Tuned discounts recover 24–53% of CalTree-LR’s replay gains but are omitted from serving comparisons. CalTree-LR also raises tree-building time from 64–112 to 119–213 μs. End-to-end comparisons are needed.

  2. Output comparability is not fully established: only 83–90% and 89–94% of speculative outputs exactly match AR. Existing checks do not resolve full-workload quality or timing effects, which matter given the 1–3% throughput gains, though they do not imply sampling bias.

  3. Fixed-budget gains may not persist under tuned serving. SSSD’s adaptive draft size is disabled, budgets are set by concurrency, and some high-concurrency settings fail to beat AR.

Questions for authors
  1. How does CalTree compare with tuned discounts in SGLang, including all overhead?

  2. Can full-workload quality checks clarify output differences and timing effects?

  3. Do gains persist with tuned or adaptive budgets, and when is AR preferable?

3 comments
AuthorsOpenReview ↗

Response to Reviewer gADs (part 1 of 2)

Thank you for the clear questions; each led to a new experiment.

Q1, CalTree versus tuned discounts in SGLang, all overhead included. The discounts run inside SSSD's C++ tree builder, and every serving table reruns all methods alternating within the same runs. They are a strong control: seven source/depth factors searched for τ on the same replays CalTree learns from, separately at each budget D = 4 to 32 (Appendix D). In throughput:

WorkloadTuned discounts vs SSSDCalTree-LR vs SSSDCalTree-LR vs tuned discounts
CanItEdit, Qwen2.5-7B (Table 16)+1.3 to +2.2%+3.7 to +4.5%+1.5 to +3.1%, every run
CanItEdit, Llama-3.1-8B (Table 26)+0.7 to +1.2%+2.4 to +3.3%+1.2 to +2.6%, every run
HumanEval, Qwen2.5-7B and Llama-3.1-8B (Table 27)+0.1 to +1.4%+1.5 to +2.5%+0.9 to +1.5%, every run
Spec-Bench, Qwen2.5-7B (Table 3)+0.5 to +1.8%+1.0 to +3.1%+0.1 to +1.3%
Spec-Bench, Llama-3.1-8B (Table 3)+0.5 to +1.7%+0.5 to +2.0%−0.3 to +1.4%
  • Code editing and HumanEval. CalTree-LR is faster than the discounts in every run, on both targets.
  • Spec-Bench. The discounts recover a median 62% of CalTree-LR's serving gain over SSSD; CalTree-LR is ahead of them at 7 of 8 loads.
  • Cost. Tree building takes 43 to 80 µs with tuned discounts, 44 to 87 µs natively and 81 to 168 µs with CalTree-LR on one core. Table 19 splits the engine gain into tokens per step and time per step: on Spec-Bench CalTree-LR raises tokens per step by 2.3 to 3.6% and step time by 0.5 to 2.6%, so in every setting the step grows less than the tokens per step; the discounts change step time by −0.4 to +0.7%.

Q2, full-workload quality and timing.

  • Agreement. Divergence from AR comes with any change to the tree. At batch size 8, tuned discounts agree with SSSD token for token on 87.9% (Qwen2.5-7B) and 92.7 to 93.2% (Llama-3.1-8B) of requests, and CalTree-LR on 87.1% and 91.2 to 91.6%. A different tree changes the FP16 arithmetic of verification, whatever the scoring rule. In the submitted runs, SSSD also disagreed with its own repeated runs on up to 6.1% of requests.
  • Amount of work. Divergent outputs barely change how much is generated: in the batch-size-8 Qwen2.5-7B runs (560 requests, submitted runs), median output tokens were 138,678 for CalTree-LR, 138,721 for AR and 139,749 for SSSD.
  • Task metrics (Table 15). CalTree-LR's GSM8K exact match (77.50%) and RAG answer hit (61.25% on Qwen2.5-7B, 65.00% on Llama-3.1-8B) equal AR's in every run. Translation BLEU differs from AR's by at most 0.14 (one Qwen2.5-7B request that flips at a near-tied logit, as it does in one of the three submitted SSSD runs) and summarization ROUGE-L by at most 0.08.
  • Functional correctness. On CanItEdit, each output's code was run against the benchmark's hidden tests in an isolated sandbox (submitted runs). AR, SSSD and CalTree-LR pass at the same rate in every run: 40.5% of 210 requests at batch size 8 and 32.9% of 70 at batch size 1. Where a method's output differs from AR's, it passes exactly as often as AR does on those requests. On HumanEval (Appendix Q), run the same way, all four methods pass the same share of problems in every run, except that at batch size 8 on Llama-3.1-8B, SSSD, the tuned discounts and CalTree-LR each pass one problem fewer than AR (69.5% vs 70.1%).
  • Equal-output timing. On the batch-size-1 requests where all methods match AR in all runs, CalTree-LR is faster than SSSD by 1.4% and 0.3% on Spec-Bench (Qwen2.5-7B, Llama-3.1-8B; +0.4% and −0.5% vs the tuned discounts) and by 3.8% and 2.3% on CanItEdit, where it is 1.5% and 1.1% faster than the tuned discounts. On HumanEval it is 1.7% and 2.1% faster than SSSD and 1.3% and 1.6% faster than the tuned discounts. Above batch size 1 the engine times one submission of the whole batch, so an output-matched comparison is not available there; we state this as a limitation.
AuthorsOpenReview ↗

Response to Reviewer gADs (part 2 of 2)

Q3, tuned or adaptive budgets, and when AR is preferable. The gains persist under both, on both targets (Appendices L and O).

  • Tuned budgets (Tables 17 and 23). Sweeping D = 4 to 32 at batch sizes 1 and 8, CalTree-LR is faster than SSSD at every budget: by 1.0 to 3.0% on Qwen2.5-7B and 1.0 to 3.4% on Llama-3.1-8B, where every run is faster than every run of SSSD.

  • Adaptive draft size (Tables 18 and 24). With SSSD's adaptive draft size enabled (tuned discounts then use the factors for the current budget), CalTree-LR is faster than SSSD at batch sizes 1 to 32, by 1.0 to 2.1% on Qwen2.5-7B and 1.1 to 2.8% on Llama-3.1-8B, and changes throughput by +0.2 to +0.8% and −0.2 to +1.9% relative to the tuned discounts.

  • Choosing the budget and the scores add up. SSSD's default budgets are too large at batch sizes 8 and 16:

    Target, batch sizeSSSD, default DSSSD, fastest DCalTree-LR at that D
    Qwen2.5-7B, 80.99x AR (D = 16)1.22x (D = 4)1.24x, 1.1% above tuned discounts
    Llama-3.1-8B, 81.05x (D = 16)1.20x (D = 8)1.23x, 1.1% above tuned discounts
    Qwen2.5-7B, 160.94x (D = 8)1.07x (D = 4)1.08x, 1.4% above SSSD
    Llama-3.1-8B, 160.97x (D = 8)1.04x (D = 4)1.06x, 1.6% above SSSD
  • When AR is preferable. At batch size 32 on our single-GPU setup, no budget from 2 to 4 reaches AR (at most 0.90x, Table 25), so AR is the better choice there. With single-token drafts (D = 2) CalTree-LR has almost nothing to allocate and is 0.1 to 1.4% slower than SSSD; at D = 3 it changes throughput by −0.1 to +0.9%.

The revised paper states this in Section 4.6 and the limitations: CalTree improves allocation within a budget and does not replace choosing the budget, and its gain adds to a well-chosen budget.

AuthorsOpenReview ↗

Follow-up for Reviewer gADs

Thank you again for the review. A short index of the experiments added for your three questions:

  • Q1, tuned discounts in SGLang with all overhead (Tables 3, 16, 19, 26, 27). On code editing and HumanEval CalTree-LR is faster than the tuned discounts in every run on both targets (by 1.2 to 3.1% and 0.9 to 1.5%); on chat, where the discounts are tuned, they recover a median 62% of its gain and CalTree-LR is ahead of them at 7 of 8 loads.
  • Q2, full-workload quality and timing (Table 15). CalTree-LR's GSM8K and RAG scores equal AR's in every run, CanItEdit hidden-test pass rates are identical, and HumanEval pass rates differ from AR's by at most one problem, alike for every speculative method; the tuned discounts diverge from SSSD as often as CalTree-LR does (87.9% vs 87.1% agreement); CalTree-LR's output token total at batch size 8 is within 0.03% of AR's.
  • Q3, tuned and adaptive budgets, and when AR is preferable (Tables 17, 18, 23 to 25). CalTree-LR is faster than SSSD at every budget from 4 to 32 and with adaptive draft sizes, on both targets. A smaller budget gives CalTree-LR 1.23x to 1.24x AR at batch size 8 and 1.06x to 1.08x at 16; at batch size 32 AR is faster.

If any of your questions remains open, we would be glad to address it before the discussion closes, and we hope the new results can be reflected in your assessment.

Reviewer_gEuaOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

CalTree changes how a speculative decoder chooses which retrieved tokens to verify. It keeps SSSD's retrieval and verification rules [1]. A 29-parameter logistic model scores each candidate using retrieval counts, agreement between sources, and earlier matches in the request. Labels come from replaying the target model's own greedy outputs. Multiplying scores along a path gives the priority for adding its last token to the tree. The paper proves that only a common positive power preserves every tree under a continuous, strictly increasing change of edge scores. Correct sibling rankings can still lose a factor approaching the tree budget in expected accepted draft tokens. Across five target models and four budgets, CalTree-LR reports 2.6–6.5% more tokens per verification pass than native SSSD on Spec-Bench and 4.5–24.5% more on CanItEdit. These are replay results. The measured SGLang throughput gains are 1.0–3.0% on Spec-Bench and 2.6–4.0% on CanItEdit.

Critical strengths
  1. The main theorem answers a precise question. SuffixDecoding already multiplies frequency estimates along a path [2]. Theorem 1 shows which changes to those estimates leave every allocation unchanged. In Appendix A, a two-edge path with scores x,yx,y competes with a root edge of score zz. Moving zz toward xyxy from either side forces g(xy)=g(x)g(y)g(xy)=g(x)g(y). Continuity and strict increase then give g(p)=pαg(p)=p^\alpha, with α>0\alpha>0. The argument handles ties. It does not say that only a power map can work on one benchmark. Proposition 2 also checks out: nodes shared by both trees cancel, and expanding the difference of path products gives Eq. 3.

  2. The replay isolates a useful improvement. At a given prefix and budget, the methods see the same candidates. They must emit the same greedy text, but each method chooses its own round boundaries. One diagnostic explains why the extra features help: at depth three, a token with retrieval frequency ratio one is accepted 67–88% of the time when it comes from the request, versus 36–41% when it comes from the datastore (§4.2). Table 9 then shows a gain for CalTree-LR in all 20 model–budget settings. The finding is not just a lower calibration error.

Critical weaknesses
  1. Section 5 understates the closest prior result. It contrasts Goose's deep copy branch with CalTree's scoring of individual candidates. That describes Goose's default method, but Appendix D.10 and Table 16 of Goose v2 already test a best-first allocator that multiplies acceptance estimates along paths. One variant scores individual candidates from adjacency counts and match length [3]. UniSpec also scores cached n-grams, although it uses probabilities from earlier target-model passes [4]. I would credit CalTree for its richer request features, its use of replay labels, and its controlled study on SSSD. Scoring individual retrieved candidates is not itself the distinction. Table 2's retrieval-only ablation is useful, but the paper does not explain how closely it matches the Goose variant.

  2. The measured speed gain is over native SSSD, not over the simpler tuned rule on the same outputs. For Qwen2.5-7B at D=16D=16, tuned source/depth discounts gain 1.6% in tokens per pass, versus 3.3% for CalTree-LR (Table 5). Table 3 does not time the tuned rule. That omission matters because CalTree-LR takes 119–213 µs to build a tree, versus 64–112 µs for native SSSD (§4.6). Also, only 83–90% of the Qwen speculative outputs match ordinary greedy decoding token for token. On the 107 of 140 batch-one turns where all methods agree in all runs, CalTree-LR is still 1.8% faster than SSSD. I credit that result. It does not settle the comparison at higher loads or against tuned discounts. Appendix J is appropriately explicit about this limit.

References:

[1] Michele Marzollo et al. SSSD: Simply-Scalable Speculative Decoding

[2] Gabriele Oliaro, Zhihao Jia, Daniel Campos, and Aurick Qiao. SuffixDecoding: Extreme Speculative Decoding for Emerging AI Applications

[3] Tao Jin, Phuong Minh Nguyen, and Naoya Inoue. Goose: Anisotropic Speculation Trees for Training-Free Speculative Decoding

[4] Truong Dinh Do, Nguyen-Khang Le, and Le-Minh Nguyen. UniSpec: Training-Free Speculative Decoding for Robust LLM Acceleration Across Languages and Hardware

Questions for authors
  1. Which existing ablation comes closest to Goose's instance-based scorer [3]? In particular, which inputs or labels differ from the retrieval-only row in Table 2, and what part of the gain can that row isolate?
  2. What information is held fixed for every edge in Eq. 1? The chain rule applies to probabilities conditioned on the same request information and on the parent matching. Section 3 fits each edge from its own features. From the saved traces, do you have a check of predicted path products against whole-path matches on a common set of prefixes? Table 11 reports individual edges selected by each scorer, not paths.
  3. In the existing Qwen2.5-7B batch-eight runs, how often did CalTree-LR and native SSSD match each other token for token? What were their total output-token counts and elapsed times? Agreement with the autoregressive baseline alone does not answer this.
3 comments
AuthorsOpenReview ↗

Response to Reviewer gEua (part 1 of 2)

Thank you for the detailed reading, including the check of the proof in Appendix A.

Goose v2 and UniSpec. You are right that Section 5 described only Goose's default construction.

  • Goose v2, Appendix D.10, already tests a best-first allocator that multiplies acceptance estimates along paths. It includes an instance-based variant that maps adjacency counts and match length to acceptance rates.
  • UniSpec scores cached n-grams by the target's probabilities from earlier forward passes and keeps the most confident nodes. It also sizes the draft per device, which is orthogonal to allocation within a budget.
  • Revised related work. It credits both and no longer presents scoring individual candidates as the distinction. Following your summary, it attributes CalTree's contribution to the richer request features, the replay labels for conditional acceptance, and the controlled study on SSSD.

Q1, the closest ablation to Goose's instance-based scorer. The retrieval-only row of Table 2 is logistic regression on the retrieval group alone, fitted on the same two-stage replay labels as CalTree. For each source, the group has an indicator, the log frequency ratio, the log parent support, the matched order and the number of matching orders. It also has depth and the number of sources.

Goose's instance-based scorer differs in three ways:

  • it maps the raw adjacency count, not the ratio, through a monotone function per source and match length;
  • it has no depth input;
  • it scores a token by its best source instead of pooling evidence across sources.

The row therefore cannot isolate Goose's functional form, so we reimplemented both of its Appendix D.10 allocators on SSSD's candidates (Appendix J, Table 14), fitted on the same labels and run in the same exact replay as Table 9. The instance-based one applies a weighted isotonic map per source and match length (1 to 4) to the log child count and takes the maximum over sources. The static one multiplies the parent's score by the acceptance rate of the candidate's rank within its source.

  • Result. Across five targets and D = 4 to 32, the instance-based variant changes τ by −2.2 to +0.6% relative to SSSD and the static one by −3.2 to +1.1%; both are below CalTree-LR (2.6 to 6.5%) in all 20 settings. On Qwen2.5-7B, the retrieval-only row gains 0.9 to 1.7% and tuned discounts 0.7 to 1.6%.
  • Why. Neither uses depth. The path-level check below gives the reason: without depth, both overstate shallow paths and understate deep ones (instance-based observed over predicted: 0.62 at depth 1, 2.00 at depth 4), so the trees come out too wide.
  • Caveat. Goose v2 does not give the functional forms. These are one reading of each variant on fixed candidates, not a reproduction of Goose's full system.

Q3, CalTree-LR versus SSSD at batch size 8 (Qwen2.5-7B, submitted runs).

  • Agreement. The two produced token-identical outputs on 87.1% of the 560 requests in each of the three paired runs. In those runs, SSSD matched itself on 93.9%.
  • Output tokens. Medians were 138,678 for LR, 139,749 for SSSD and 138,721 for AR.
  • Elapsed time. Medians were 270 s, 278 s and 275 s, so LR produced 2.4% more tokens per second than SSSD.
  • New runs. CalTree-LR again agrees with SSSD on 87.1%. Tuned discounts, which only rescale SSSD's scores, agree with it on 87.9%.
AuthorsOpenReview ↗

Response to Reviewer gEua (part 2 of 2)

Q2, what Eq. 1 conditions on, and a path-level check. Each factor of Eq. 1 conditions on the request at the round root (prompt and verified output) and on the parent path being matched.

  • Features. CalTree's features for an edge are functions of exactly this information: the retrieval results at the parent, request statistics over the verified prefix plus the drafted path, and the suffix-automaton state walked along that path.
  • Labels. Stage-2 labels are collected only for edges whose parent was accepted, which is the conditioning event of Eq. 1.
  • What the model does not guarantee is that its errors stay independent along a path, which is why your check is the right one.

We ran it on the same prefixes and paths for every scorer (Appendix I).

  • Prefixes. Every fourth position of all 560 Spec-Bench turns of Qwen2.5-7B, giving 35,003 prefixes.
  • Paths. At each prefix, SSSD's candidate tree is enumerated to depth 4 with no scorer involved. That gives 9.15M paths, identical for every scorer.
  • Prediction and label. Each path is scored by the product of a scorer's edge probabilities and labeled by whether the whole path equals the target's greedy continuation.

The table below covers paths with predicted probability at least 0.05, the ones an allocator can select. It is Table 11 in the revision; the edge-level calibration table you cite as Table 11 is now Table 12.

depth 1depth 2depth 3depth 4
CalTree-LR0.970.910.840.77
CalTree-GB0.990.980.970.95
SSSD (native scores)0.620.470.380.32

Entries are the observed match rate divided by the mean predicted path probability.

  • CalTree-LR. Its path products are close at depths 1 and 2 and become optimistic at depths 3 and 4. Its small conditional errors compound: over all paths, the depth-4 ratio of 0.86 is close to the product of its per-depth edge ratios.
  • CalTree-GB stays within 5%.
  • Native frequencies overstate deep paths about threefold.

The revision reports this and states the LR limitation. Two checks show the drift costs little in τ and is not a depth-specific bias we can tune away.

  • The depth exponents 1.1^(d−1) and 1.25^(d−1) shrink deep probabilities in the direction the drift calls for, and change LR's gain by −0.1 to +0.1 points (Table 13).
  • We refit a per-depth Platt map σ(a_d z + b_d) of LR's logit z on the fully enumerated candidate paths of the training replays, conditioning on the parent path being matched. The maps stay near the identity (a_d from 0.90 to 1.03, b_d from −0.08 to +0.12 over the five targets), leave the depth-4 observed-over-predicted ratio at 0.76, and change τ by at most 0.03 points (Appendix I). On its own training distribution LR is calibrated at every depth; on Spec-Bench its matched-parent edges are a few percent optimistic at every depth, and that small, near-uniform error compounds along the path. Goose's depth-free rates drift much faster.

The tuned rule versus CalTree on the same outputs. We agree this comparison was missing; it is now in every serving table. The discounts are refined for τ separately at each budget on the same replays CalTree learns from (Appendix D).

  • Full Spec-Bench runs. At SSSD's default budgets the discounts recover a median 62% of CalTree-LR's gain over SSSD, and CalTree-LR is ahead of them at 7 of 8 loads (all 8 in the later rerun, Table 22).
  • Output-matched requests. On the batch-size-1 Spec-Bench turns where all methods match AR in every run, CalTree-LR's margin over the discounts is +0.4% on Qwen2.5-7B (107 of 140 turns) and −0.5% on Llama-3.1-8B (113 of 140), and over SSSD +1.4% and +0.3%. On the matched CanItEdit requests it is +1.5% over the discounts and +3.8% over SSSD on Qwen2.5-7B (61 of 70), and +1.1% and +2.3% on Llama-3.1-8B (64 of 70). On the matched HumanEval problems it is +1.3% (Qwen2.5-7B, 72 of 82) and +1.6% (Llama-3.1-8B, 75 of 82) over the discounts.
  • Full code-editing and HumanEval runs. CalTree-LR is faster than the discounts in every run on both targets, by 1.5 to 3.1% (Qwen2.5-7B) and 1.2 to 2.6% (Llama-3.1-8B), Tables 16 and 26; on HumanEval by 0.9 to 1.5%, also in every run (Table 27).

So on chat CalTree-LR's margin over the discounts is small, and on code editing and HumanEval it is clear on full and on output-matched workloads.

AuthorsOpenReview ↗

Follow-up for Reviewer gEua

Thank you again for the careful review, including the check of the proof. A short index of the additions for your questions:

  • Goose v2 and UniSpec (Section 5, Appendix J, Table 14). Related work credits both. Goose v2's two Appendix D.10 allocators, reimplemented on SSSD's candidates, are below CalTree-LR in all 20 settings (−3.2 to +1.1% and −2.2 to +0.6% vs 2.6 to 6.5%); neither uses depth.
  • Eq. 1 and a path-level check (Appendix I, Table 11). 9.15M paths at 35,003 common prefixes, plus a per-depth recalibration that changes τ by at most 0.03 points.
  • Agreement at batch size 8 (Table 15). CalTree-LR agrees with SSSD on 87.1% of requests, the tuned discounts on 87.9%.
  • The tuned rule on the same outputs (Tables 3, 16, 26, 27). On output-matched chat turns CalTree-LR is within half a percent of the tuned discounts (+0.4% and −0.5%); on code editing it is faster than them in every run on both targets, and by 1.5% and 1.1% on the output-matched requests; HumanEval shows the same (1.3% and 1.6% on its output-matched problems).

We are happy to clarify anything that remains before the discussion closes.

Reviewer_LJXGOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work proposes CalTree, a lightweight acceptance predictor for drafter-free speculative decoding trees that re-ranks proposed tokens based on 29 parameters that are fit to replayed target generations. The method improves the draft token acceptance rank compared to the baselines and achieves modest throughput gains.

Critical strengths
  • Good experimental design, with 5 target models and diverse datasets. Comparisons include multiple seeds, domain transfer experiments, and feature ablations which build confidence in method.
  • Useful calibration observations regarding how acceptance differs as a function of source and depth irrespective of retrieval frequencies.
  • Consistent improvements in acceptance length.
Critical weaknesses
  • Modest throughput gains: Despite the better acceptance rate, the overhead of the CalTree model appears to negate most of the benefits, yielding only a modest throughput gain of a few percentage points. Increasing concurrency while shrinking tree follows SSSD, but it would be more illustrative to demonstrate the effect of changing the tree size at fixed concurrency to best understand the overhead of CalTree.
  • Technical contributions are marginal: Source-dependent reliability was recognized by existing heuristics such as SSSD and SPECTRA. Theorem 1 is a useful motivation but a relatively modest extension to a classical result.
Questions for authors
  • Tuned source/depth discounts recover 25-50% of CalTree’s acceptance length improvements but are not compared against CalTree in the serving throughput analysis. Please add the tuned discount setting to the throughput analysis to establish the value of CalTree’s more sophisticated, but costly, predictions.
5 comments
AuthorsOpenReview ↗

Response to Reviewer LJXG (part 1 of 2)

Thank you for the review and for the two concrete requests; we ran both.

Tuned discounts in the throughput analysis. They now run in every serving table, inside SSSD's C++ tree builder and timed in the same runs, in alternating order, as every other method. The control is strong: seven source/depth factors searched directly for τ on the same replays CalTree learns from, separately at each budget D = 4 to 32 (Appendix D), at native build cost (43 to 80 µs vs 44 to 87 µs native and 81 to 168 µs for CalTree-LR on one core).

  • Chat (Spec-Bench, Table 3). Here the discounts recover a median 62% of CalTree-LR's gain over SSSD. CalTree-LR still raises SSSD's throughput by 1.0 to 3.1% on Qwen2.5-7B and 0.5 to 2.0% on Llama-3.1-8B (ahead in 23 of 24 paired runs), against 0.5 to 1.8% for the discounts, and is ahead of the discounts at 7 of 8 loads (−0.3 to +1.4%; all 8 in the later rerun, Table 22).
  • Code editing (CanItEdit, Tables 16 and 26). Without retuning, CalTree-LR is faster than the chat-tuned discounts in every run on both targets: by 1.5 to 3.1% on Qwen2.5-7B and 1.2 to 2.6% on Llama-3.1-8B. On HumanEval (Table 27) it is 0.9 to 1.5% faster than them, also in every run on both targets. In replay the discounts change τ on code editing by −1.5 to +4.0% (below SSSD in 5 of 20 settings) while CalTree-LR gains 4.5 to 24.5%.

So on chat, where the discounts are tuned separately at each budget, CalTree-LR's margin over them is small (1.1% at the fastest batch-size-8 budgets); the value of the learned scores is that one unchanged model keeps its gain when the workload changes, which a per-workload, per-budget search does not.

Tree size at fixed concurrency, and does the overhead negate the gain? We swept D = 4, 8, 16 and 32 at batch sizes 1 and 8 on both targets (Tables 17 and 23).

  • Every budget. CalTree-LR is faster than SSSD at every budget: by 1.0 to 3.0% on Qwen2.5-7B and 1.0 to 3.4% on Llama-3.1-8B, where every run is faster than every run of SSSD.
  • Budget and scores add up. At batch size 8 SSSD's default D = 16 runs at 0.99x and 1.05x AR. The fastest budget (D = 4 and D = 8) runs at 1.22x and 1.20x, and CalTree-LR at that budget at 1.24x and 1.23x, 1.1% ahead of the tuned discounts on both targets.
  • Where the time goes (Table 19). Throughput relative to SSSD is the change in tokens per step divided by the change in step time. On Spec-Bench CalTree-LR raises tokens per step by 2.3 to 3.6% and step time by 0.5 to 2.6%; on CanItEdit by 3.6 to 5.9% and −0.1 to +1.4%. In every setting the step grows less than the tokens per step, so the scoring cost reduces the gain but does not erase it. At batch size 1 a step takes 18.2 ms and CalTree-LR lengthens it by 1.3%.

Richer scorers (Appendix N). We also tested whether a more accurate scorer pays off once its cost is cut. A 30-tree CalTree-GB, selected on held-out replays before any test run and evaluated with a faster, bitwise-identical tree evaluation, raises the engine's τ over CalTree-LR by 0.3 to 1.0% but is level with it in throughput (−0.6 to +1.2%, Table 22); the 300-tree model is slightly behind (−2.3 to −0.1%). CalTree-LR remains the method we serve.

AuthorsOpenReview ↗

Response to Reviewer LJXG (part 2 of 2)

Technical contribution. We agree that SSSD and SPECTRA already treat sources as unequally reliable. SSSD scales request-local frequencies by 0.6 and discounts depth. SPECTRA serves its internal guesses before external retrieval because it measured them to be accepted more often. Both are fixed rules, and their scores remain frequencies.

What the paper contributes, and what the new results support, is the following.

  1. Theory. Theorem 1 shows that best-first allocation over path products is invariant only to power maps of the edge scores. Any rescaling of sources or depths therefore changes the trees, and by Proposition 2 the loss of those trees is bounded by how far the rescaled path scores are from acceptance probabilities. The experiments test this directly:

    • power maps of CalTree's probabilities reproduce every verification pass;
    • sibling normalization keeps every order but loses 1.3 to 5.0 points;
    • Proposition 2 bounds the loss by the conditional-probability errors along root paths.
  2. A larger gain that survives a change of workload. Per-budget tuned discounts are the strongest source-and-depth rule we found. On Spec-Bench they recover a median 62% of CalTree's serving gain and 24 to 53% of its replay gain. We tested transfer both ways:

    • Across targets, the discounts carry over as well as CalTree: a Qwen2.5-7B fit used unchanged on four other targets changes the gain by at most 0.7 points, against at most 0.2 for CalTree.
    • Across workloads, they keep much less. Fitted on chat, the discounts change τ by −1.5 to +4.0% on code editing (a median 18% of CalTree's gain, negative in 5 of 20 settings) and −0.3 to +1.7% on HumanEval (median 28%), while CalTree's chat-fitted scores gain 4.5 to 24.5% and 1.9 to 5.7%. In serving, CalTree-LR is faster than the discounts in every run on both targets, on code editing and on HumanEval (Tables 16, 26 and 27).

    The distinction is not that one transfers and the other does not; it is that CalTree's estimated probabilities give a larger, more workload-robust gain. The theory says why conditional acceptance probabilities are the right target for the scores; that estimating them carries across workloads is what the experiments show.

  3. Composing retrieval sources (Appendix M, Table 20; replay τ, Qwen2.5-7B, D = 8 / 16). When prompt lookup and token recycling add candidates to SSSD's pool, a per-source, per-depth calibration of the retrieval frequencies refitted on each pool (Iso) goes from +0.8 / +1.1% over native SSSD to −0.8 / −0.3% (−3.7 / −3.5% with warm-started token recycling alone), while CalTree-LR refitted the same way goes from +3.8 / +3.3% to +4.1 / +4.6% (+4.1 / +4.7%). Conditional acceptance probabilities put every source on one scale.

  4. The controlled study on SSSD's candidates separates allocation from retrieval. It now includes Goose v2's two allocators (Appendix J) and a path-level calibration check (Appendix I).

Theorem 1 builds on the classical characterization of multiplicative functions, as the paper says. Its role here is to rule out non-power reweightings as free choices.

The revised contribution list says this plainly and no longer presents source-dependent reliability as new, and Section 4.6 and the limitations report how much of the serving gain the tuned discounts recover on chat.

AuthorsOpenReview ↗

Follow-up for Reviewer LJXG

Thank you again for the review. A short index of how the revision answers your points:

  • Tuned discounts in the throughput analysis (Tables 3, 16, 26, 27). They now run in every serving experiment, tuned for τ separately at each budget on the same replays. On chat they recover a median 62% of CalTree-LR's gain and CalTree-LR is ahead of them at 7 of 8 loads; on code editing (by 1.5 to 3.1% and 1.2 to 2.6%) and on HumanEval (by 0.9 to 1.5%) CalTree-LR is faster than them in every run on both targets.
  • Tree size at fixed concurrency (Tables 17, 23). On both targets CalTree-LR is faster than SSSD at every budget from 4 to 32 at batch sizes 1 and 8 (by 1.0 to 3.0% and 1.0 to 3.4%). At the fastest batch-size-8 budget it reaches 1.24x and 1.23x AR, 1.1% ahead of the tuned discounts.
  • Overhead (Table 19). Scoring lengthens a step by 0.5 to 2.6% on Spec-Bench while raising tokens per step by 2.3 to 3.6%; in every setting the step grows less than the tokens per step.
  • Richer scorers (Appendix N, Table 22). With a faster, bitwise-identical tree evaluation, a 30-tree CalTree-GB is level with CalTree-LR in serving (−0.6 to +1.2%), so CalTree-LR stays the method we serve.
  • Contribution (part 2 of our response). Theorem 1 and Proposition 2 say why conditional acceptance probabilities are the right target for the scores, the experiments show that estimating them keeps the gain across workloads, and Table 20 shows them composing new retrieval sources in replay where a refitted frequency calibration loses ground.

If anything remains unconvincing, we would be glad to address it before the discussion closes, and we hope the new results can be reflected in your assessment.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General response (to all reviewers)

We thank the reviewers for careful and specific reviews. All three asked for the same missing comparison: tuned source/depth discounts in the serving engine, with all overhead included. We implemented it inside SSSD's C++ tree builder and reran every serving experiment with all methods alternating within the same runs.

The control. The tuned discounts are a strong baseline rather than a fixed heuristic: seven source/depth factors searched directly for τ on the same target replays CalTree learns from, refined separately at each budget D = 4, 8, 16 and 32 (Appendix D). They only rescale SSSD's scores, so they build trees at native cost (43 to 80 µs vs 44 to 87 µs native; CalTree-LR 81 to 168 µs on one core). CalTree-LR is one 29-parameter model fitted by log-loss and used unchanged at every budget.

Serving in SGLangTuned disc. vs SSSDCalTree-LR vs SSSDCalTree-LR vs tuned disc.
CanItEdit, Qwen2.5-7B (Table 16)+1.3 to +2.2%+3.7 to +4.5%+1.5 to +3.1%, every run
CanItEdit, Llama-3.1-8B (Table 26)+0.7 to +1.2%+2.4 to +3.3%+1.2 to +2.6%, every run
HumanEval, Qwen2.5-7B and Llama-3.1-8B (Table 27)+0.1 to +1.4%+1.5 to +2.5%+0.9 to +1.5%, every run
Spec-Bench, Qwen2.5-7B, default budgets (Table 3)+0.5 to +1.8%+1.0 to +3.1%+0.1 to +1.3%
Spec-Bench, Llama-3.1-8B, default budgets (Table 3)+0.5 to +1.7%+0.5 to +2.0%−0.3 to +1.4%
Spec-Bench, batch size 8, fastest budget, Qwen2.5-7B / Llama-3.1-8B (D = 4 / 8; Tables 17, 23)+0.4% / +1.4%+1.5% / +2.5%+1.1% / +1.1%
  • Chat (Spec-Bench). On the workload they are tuned on, the discounts recover a median 62% of CalTree-LR's gain over SSSD at the default budgets. CalTree-LR is still ahead of them at 7 of 8 loads (all 8 in the later rerun, Table 22) and ahead of SSSD in 23 of 24 paired runs. Choosing the budget and choosing the scores add up: at batch size 8, SSSD's default D = 16 runs at 0.99x and 1.05x AR, the fastest budget (D = 4 and D = 8) at 1.22x and 1.20x, and CalTree-LR at that budget at 1.24x and 1.23x.
  • Code (CanItEdit and HumanEval). With no retuning, CalTree-LR is faster than the chat-tuned discounts in every run on both targets, on code editing and on HumanEval. In replay the same discounts change τ on CanItEdit by −1.5 to +4.0% (below SSSD in 5 of 20 settings), while CalTree-LR's chat-fitted scores gain 4.5 to 24.5%.
  • Why the gap opens off chat. By Theorem 1, best-first allocation is invariant only to power maps of edge scores, so any source/depth rescaling changes the trees, and by Proposition 2 their loss is bounded by how far the path scores are from acceptance probabilities. The discounts find a rescaling by search on one workload; CalTree estimates the probabilities from request-level evidence, and in our experiments its scores stay useful when the workload changes. Across targets both transfer (−0.2 to +0.2 points for CalTree, at most 0.7 for the discounts); across workloads the discounts keep a median 18% of CalTree's replay gain on code editing and 28% on HumanEval, against 37% on Spec-Bench.

Other additions.

  • Overhead (LJXG, Table 19). On Spec-Bench CalTree-LR raises tokens per step by 2.3 to 3.6% and step time by 0.5 to 2.6%; in every setting the step grows less than the tokens per step.
  • Tree size at fixed concurrency and adaptive draft size (LJXG, gADs; Tables 17, 18, 23, 24). On both targets CalTree-LR is faster than SSSD at every budget from 4 to 32 at batch sizes 1 and 8 (1.0 to 3.0% and 1.0 to 3.4%) and with SSSD's adaptive draft size at batch sizes 1 to 32 (1.0 to 2.1% and 1.1 to 2.8%).
  • When AR is preferable (gADs, Table 25). At batch size 16, D = 4 restores a speedup (CalTree-LR 1.06 to 1.08x AR); at batch size 32 no budget from 2 to 4 reaches AR.
  • Output quality (gEua, gADs; Table 15). Tuned discounts agree with SSSD on 87.9% of requests at batch size 8 (Qwen2.5-7B), CalTree-LR on 87.1%: divergence comes with any change of the tree. CalTree-LR's GSM8K and RAG scores equal AR's in every run, and CanItEdit hidden-test pass rates are identical for AR, SSSD and CalTree-LR. On HumanEval all methods pass the same share of problems in every run, except that at batch size 8 on Llama-3.1-8B, SSSD, the tuned discounts and CalTree-LR each pass one problem fewer than AR (69.5% vs 70.1%).
  • Goose v2 Appendix D.10 (gEua; Appendix J, Table 14). Both allocators, reimplemented on SSSD's candidates, are below CalTree-LR in all 20 settings (−3.2 to +1.1% and −2.2 to +0.6% vs 2.6 to 6.5%); a path-level check over 9.15M paths (Appendix I) shows that without depth they overstate shallow paths and understate deep ones.
  • Related work now credits Goose v2 Appendix D.10, UniSpec and SPECTRA.
AuthorsOpenReview ↗

Summary of changes in the revised PDF (to all reviewers)

The revision uses the additional page for the main text and adds six appendix sections (J, L, N, O, P and Q); the title is unchanged. New or changed text is shown in blue. Added after the initial rebuttal: Appendices O, P and Q and the serving result in Appendix N (Table 22). Changes by location:

  • Introduction and abstract. The contribution list is rewritten to state what is new, with a separate Generalization item that leads on the learned scorer's transfer across targets and from chat to code, and to report serving results relative to tuned discounts. Two definitions are corrected: drafter-free methods train no draft model, and K counts draft tokens (non-root nodes). The abstract and conclusion are reworded to foreground that transfer; the abstract also reports the serving comparison with tuned discounts, on Spec-Bench and on code editing for both served targets.

  • Section 4.4. One sentence reports Goose v2's instance-based scorer on SSSD's candidates (details in Appendix J).

  • Section 4.6 and Table 3. All six methods, now including tuned discounts, are rerun in the same C++ tree builder with alternating order. The section reports same-machine build times, paired-run results, the margin over tuned discounts, code editing on both targets, and pointers to the fixed-concurrency, adaptive and HumanEval results (Appendices L, O and Q).

  • Section 5. Related work now covers SPECTRA, Goose v2 Appendix D.10 and UniSpec.

  • Limitations. On chat workloads, tuned discounts recover much of the serving gain. With SSSD's default budgets, tree speculation is at or below AR at batch sizes 16 to 32; a smaller budget restores a speedup at batch size 16 but not at 32 (Appendix O).

  • Appendix I. Adds path-level calibration on common prefixes (new Table 11), including a per-depth recalibration of CalTree-LR that does not remove the depth drift, and Goose's static rates.

  • Appendix J (new). Goose v2's two allocators from its Appendix D.10, static (rank-based) and instance-based, on SSSD's candidates (new Table 14).

  • Appendix K (formerly J). Adds output quality and agreement on the new runs (new Table 15) and CanItEdit hidden-test pass rates. Table 16 (formerly 13) is rerun with tuned discounts, with equal-output latency relative to them.

  • Appendix L (new). Tree budget at fixed concurrency (new Table 17), SSSD's adaptive draft size (new Table 18), and a decomposition of the engine gain into tokens per verification step and time per step (new Table 19).

  • Appendix N (new). A cheaper learned scorer: a 30-tree CalTree-GB selected on held-out replays before any test run, with its test results and same-core build times (new Table 21), a faster evaluation of tree ensembles in the C++ builder that leaves every score and tree unchanged, and both learned scorers served in SGLang with that evaluation, all methods rerun together (new Table 22). Section 4.6 points to it.

  • Appendix O (new). Tree budget at fixed concurrency and SSSD's adaptive draft size on Llama-3.1-8B (new Tables 23 and 24), and budgets below SSSD's default at batch sizes 16 and 32 for both targets (new Table 25). Appendix L points to it.

  • Appendix P (new). CanItEdit served on Llama-3.1-8B (new Table 26), as Table 16 does for Qwen2.5-7B, including equal-output latency.

  • Appendix Q (new). HumanEval served on both targets with every method (new Table 27), with equal-output latency and sandboxed test pass rates.

  • Appendix E and the discount control. Adds that the tuned discounts transfer across targets as well as CalTree does, but keep less of its gain off the chat workload they were tuned on.

  • Final corrections (18 Nov). The introduction's serving ranges now cover both served targets (they previously gave Qwen2.5-7B's code-editing range), the abstract states the Spec-Bench serving result as 23 of 24 paired runs rather than "every tested load", the conclusion no longer says "no new training", and Appendix O notes that CalTree-LR and SSSD are level on Llama-3.1-8B at batch size 32.

Renumbering: Tables 1 to 10 are unchanged. Former Tables 11, 12, 13 and 14 are now Tables 12, 13, 16 and 20; Tables 11, 14, 15, 17, 18, 19, 21, 22, 23, 24, 25, 26 and 27 are new. Former Appendices J and K are now Appendices K and M.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.