{"id":"4f53d02e-bf85-4008-8f94-f52368a30aa3","arxiv_id":"2501.12162","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"AdaServe customizes speculative decoding per request to satisfy heterogeneous per-token latency SLOs, claiming up to 4.3x fewer violations and 1.9x higher goodput than baselines.","lead":"AdaServe is a serving system that gives each large language model request its own decoding-speed target, using speculative decoding to meet different latency requirements in the same batch. It reports up to 4.3 times fewer missed latency targets and up to 1.9 times higher goodput than existing serving systems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Draft-logit surrogate for path acceptance probabilities is unvalidated; if biased, SLO-customized selection and the claimed optimality do not transfer to the deployed system.","rationale":"The paper's central claim is that AdaServe achieves its SLO and goodput gains by constructing per-request draft token trees that maximize expected accepted tokens under a hardware budget and per-request TPOT constraints. The optimization objective and the SLO-feasibility checks in Algorithm 2 both rely on f(v), the true path acceptance probability. Since the true f(v) is unavailable, Eq (7) substitutes a product of draft-model probabilities. This substitution is the critical bridge from the clean formulation in Section 3 to the implemented system. If the surrogate is inaccurate or miscalibrated, the selected trees are not the ones that maximize expected accepted tokens, and the theoretical optimality of Algorithm 1 and the coverage guarantee of Theorem 4.1 do not apply to the deployed Algorithm 2. The paper cites prior work on distillation and on using draft logits in other systems, but it provides no direct evidence that the cumulative sum of draft-logit products is a reliable predictor of SLO attainment on the evaluated workloads. This is the least secure link in the causal chain from formulation to empirical result. I agree with the reader's identification of this as the weakest assumption. Other issues, such as missing comparisons against SpecServe and SLOS-Serve, the absence of error bars, and the unproven Theorem 4.1, are real but secondary: they affect the breadth and precision of the empirical claims, whereas the surrogate assumption affects whether the mechanism described in the central claim is actually realized. A focused calibration and sensitivity study would settle the concern; if the surrogate is shown to be accurate on the tested workloads, the conditional acceptance can be upgraded. I therefore keep the reader's CONDITIONAL verdict unchanged.","tokens_in":23262,"tokens_out":21707,"duration_ms":228497,"concrete_test":"On a held-out portion of the evaluation trace, instrument AdaServe to record for every node v in every candidate tree both the draft-model surrogate (Eq 7) and the empirical verification frequency f_hat(v) over repeated runs, or compute the true acceptance probabilities from the target LLM's logits. Compute the Spearman rank correlation and a reliability diagram of the surrogate against f_hat. Then re-run the end-to-end evaluation with a selection variant that ranks and thresholds using f_hat instead of Eq (7). If the SLO-attainment or goodput curves shift by more than 5% relative, the surrogate is load-bearing for the headline claims; if they are unchanged, the approximation is adequate and the concern is settled.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Equation (7) replaces the true path acceptance probability f(v) with the product of draft-model logits, and Algorithm 2 uses this surrogate in two places: (i) ranking nodes for SLO-customized and throughput-optimized selection, and (ii) the stopping condition in lines 12-15, where cumulative surrogate probability must reach A_cap(r). Neither the ranking nor the cumulative threshold is calibrated against the LLM's actual acceptance distribution. In speculative sampling, the token acceptance probability is min(1, p_target/p_draft), not p_draft; with a miscalibrated draft model the surrogate can be systematically above the true f(v), causing the scheduler to believe an SLO is being met when it is not. The paper provides no error analysis, no calibration study, and no sensitivity experiments for this approximation. Since the central claim states that AdaServe reduces SLO violations by constructing token trees that maximize expected accepted tokens subject to TPOT constraints, an unvalidated surrogate leaves open the possibility that the deployed system is maximizing the wrong objective and that the reported SLO and goodput gains are specific to the two model families and workloads tested, not to the proposed mechanism.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"AdaServe is an LLM serving system that uses speculative decoding with per-request, SLO-customized draft token trees to serve requests with heterogeneous TPOT (time-per-output-token) requirements. The paper formulates multi-SLO serving as maximizing the expected number of accepted tokens subject to a hardware token budget and per-request TPOT constraints (Section 3, Eqs. (1)–(6)), and proposes a greedy algorithm (Algorithm 1) claimed optimal when the path acceptance probabilities f(v) are known. Since f(v) is unavailable at tree-construction time, AdaServe approximates it by the product of draft-model conditional probabilities (Eq. (7)), decouples speculation from selection, and implements a speculate–select–verify pipeline (Algorithm 2): beam search builds candidate trees; SLO-customized selection adds tokens until each request's TPOT target is met; throughput-optimized selection spends the remaining budget; the LLM verifies all chosen trees in parallel. Tree depth and width are adapted to system load (Eqs. (8)–(9)). Evaluations against vLLM, Sarathi-Serve, and vLLM with static speculative decoding on Llama-3.1-70B and Qwen2.5-32B over real-trace and synthetic workloads report up to 4.3× fewer SLO violations and up to 1.9× higher goodput.","tokens_in":23317,"tokens_out":23387,"duration_ms":233050,"significance":"The problem is timely and important: multi-SLO serving is poorly addressed by uniform continuous batching, and the paper's combination of decoupled speculation and selection, SLO-tailored per-request tree construction, and adaptive depth/width control is a sensible and novel mechanism. I credit the authors with complete pseudocode for both algorithms, a reasonably broad evaluation (two model families of 32B/70B, a real request trace, a bursty synthetic workload, and ablations of acceptance rate and latency breakdown), and an honest acknowledgement of concurrent SLO-aware speculative-decoding work. The reported gains — up to 4.3× fewer violations and 1.9× higher goodput over vLLM with static speculative decoding — are consistent in direction across Figures 8–14. If the claims hold, this is a solid systems contribution. However, the significance is currently capped by three gaps: Theorem 4.1 is asserted without proof, the Eq. (7) surrogate that drives all SLO-satisfaction decisions is unvalidated, and the Appendix C optimality proof is informal.","major_comments":[{"comment":"The surrogate in Eq. (7) is load-bearing and unvalidated. The paper replaces the LLM path-acceptance probability f(v) of Theorem 3.1 with the product of the draft model's conditional probabilities, and Algorithm 2 uses this surrogate both to rank nodes (lines 13 and 19) and to decide SLO satisfaction (lines 12–15, comparing cumulative surrogate mass against A_cap(r)). Under the standard speculative-sampling verification scheme, the marginal probability that a draft node u is accepted is min(p_target(u), p_draft(u)) (under greedy verification it is the indicator of agreement with the target's argmax), not p_draft(u); the product of draft probabilities is therefore an upper bound on the true acceptance probability whenever the draft is not perfectly aligned with the target. If the draft is overconfident, Eq. (5) can appear satisfied while the true expected accepted tokens fall short, so the scheduler can believe an SLO is being met when it is not; consequently, the optimality guarantee of Algorithm 1 and the coverage guarantee of Theorem 4.1 do not transfer to the deployed system. The paper's distillation argument does not directly apply to the evaluated draft models (Llama-3.2-1B and Qwen2.5-0.5B are general instruct models, not SD-distilled drafts). I request (i) a calibration study relating the Eq. (7) surrogate to empirically measured acceptance frequencies on the evaluated workloads, (ii) an ablation that replaces the surrogate with target-model logits obtained from the previous iteration's verification, and (iii) an explicit restatement of the theoretical claims as holding with respect to the surrogate.","section":"Section 4.2, Eq. (7); Algorithm 2"},{"comment":"Theorem 4.1 is stated without proof, and none of Appendices A–C contains it. The theorem is load-bearing: it justifies replacing Algorithm 1's interleaved node selection with a fixed-depth beam search, and the subsequent bound D_opt ≤ B − n is used to argue that beam-search speculation overhead is small. The claim is not obviously true in the multi-request case, because Step 1 of Algorithm 1 inserts SLO-mandated nodes that need not be among the globally highest-probability nodes, and a beam search with width B could in principle prune such nodes' ancestors. Please provide a complete proof of Theorem 4.1 (and of its generalization to all requests), or, if the statement requires additional assumptions (e.g., on the budget relative to the number of SLO-forced nodes), state them explicitly.","section":"Section 4.2, Theorem 4.1"},{"comment":"The optimality proof of Algorithm 1 is informal in a way that a referee cannot fully verify. Lemma C.1 asserts that the greedy set of n−1 nodes is the best subset of that size 'by definition', but the exchange argument is not written out; Lemma C.2 is correctly stated but likewise needs a formal swap-based proof. Part 2 of the proof is prose: it does not rigorously show that any feasible solution must allocate at least N_i tokens to every request i (which Step 1 of Algorithm 1 does by construction, using the minimal N_i from Lemma C.1), nor that the global greedy allocation of the remaining budget is optimal over all feasible budget distributions across requests. The claimed result appears correct under the stated assumptions, but the proof should be rewritten as a formal exchange argument.","section":"Appendix C"}],"minor_comments":[{"comment":"The budget loops use 'while B ≥ 0' (Algorithm 1, line 16; Algorithm 2, lines 12 and 18) after B is decremented for every added node (and for roots at Algorithm 2, line 7). With B = 0 the loop body executes once more and B becomes −1, so the budget can be exceeded by one token; the conditions should be 'B > 0'.","section":"Algorithms 1 and 2"},{"comment":"The zero-load baseline latency that defines the Cat-1 SLO (1.2× baseline) is not tied to a specific configuration; please specify whether the baseline is measured on the same systems (with or without speculative decoding) and how it is kept comparable across AdaServe and the baselines, since the 1.2× target is a relative threshold.","section":"Section 6.1"},{"comment":"The argument order of the clip function (upper, lower, value) is unconventional; it should be stated explicitly in the text. In addition, the grid search for c1 and c2 should report the objective and the validation data used, so that the adaptive policy is reproducible and not tuned on the reported evaluation traces.","section":"Section 5.2, Eqs. (8)–(9)"},{"comment":"Figures 8–15 do not report the number of independent runs or variance. Since the request traces are generated by sampling categories and requests, please report means over at least three seeds (or state that each plotted trace is a single deterministic run). Relatedly, the abstract's headline numbers (up to 4.3× and 1.9×) should point to the exact figure and operating point where they are realized, since the rasterized curves are not easy to read precisely.","section":"Section 6"},{"comment":"Please state explicitly the verification protocol (speculative sampling with min(1, p_target/p_draft) acceptance, or greedy argmax acceptance) under which Theorem 3.1's decomposition E[acc(T)] = Σ_{v∈T} f(v) holds; this also determines what the Eq. (7) surrogate is approximating and would make the calibration study requested in Major Comment 1 well-defined.","section":"Section 4.2, Eq. (7) and Theorem 3.1"},{"comment":"There are several typos and wording slips: 'wich' (§6.2), 'operator' (§4.2, 'to operator more efficiently'), 'recourses' (§4.3), 'iteartion' (§5.2), 'requiremer' (§4.3), and the inconsistent use of 'unattained requests' vs. 'SLO violations'. I recommend a careful proofread.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The practical contribution is real and the empirical story is coherent; my recommendation of major revision is driven by the gap between the theoretical narrative and the deployed mechanism. The highest-risk point is the Eq. (7) surrogate: Algorithm 1's optimality and Theorem 4.1's coverage apply to the known-f setting, while the deployed Algorithm 2 is driven by an unvalidated proxy whose bias can only degrade SLO attainment. A calibration study plus an alternative-surrogate ablation would settle this. I do not regard the lack of comparison with the concurrent SpecServe and SLOs-Serve as a defect given publication timing, and the paper's 'to our knowledge' framing is appropriate. If the authors provide the missing proof of Theorem 4.1 and the empirical validation of the surrogate, I would be comfortable with acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear [Colleague],\n\nYou should know about AdaServe: it's a serious LLM serving paper that tackles a real problem—meeting heterogeneous latency SLOs in one batch—and it does something genuinely new. Instead of treating all requests uniformly, it allocates draft token-tree nodes across requests under a hardware budget and per-request TPOT constraints, and it decouples speculation from selection so the draft model isn't the bottleneck. The constrained optimization formulation (Section 3) is clean, and the adaptive depth/width control is sensible. The evaluation covers two model families, several workloads, and a real trace; the gains over vLLM and vLLM-Spec are directionally convincing.\n\nNow the soft spots, in proportion. The headline numbers (4.3x fewer violations, 1.9x goodput) rest on a few things that are under-supported. Theorem 4.1, which guarantees the beam-search candidate tree covers the optimal tree, is stated without proof; the argument is plausible but not rigorous in the text. The evaluation has no error bars, and it doesn't compare against two concurrent SLO-aware systems (SpecServe, SLOS-Serve) that the paper itself cites—that weakens the 'first' framing and leaves the exact margin over the closest competitors unknown. SLO attainment is measured with average per-token latency, not tail latency, which can flatter a system. And the grid-searched constants c1/c2 aren't reported, which hurts reproducibility.\n\nThe bigger conceptual concern is also the one the authors hand-wave the most: Equation (7) uses the draft model's logit product as a surrogate for the LLM's path acceptance probability. In real speculative sampling, acceptance is min(1, p_target/p_draft), not p_draft. The paper cites prior work and distillation as justification, but there's no calibration study or sensitivity analysis. If the surrogate is systematically biased, the SLO-customized selection could be chasing the wrong objective. I don't think this sinks the paper—the ranking of nodes by draft probability is probably correlated with true acceptance well enough to explain the empirical wins—but it's a real gap that a referee should push on.\n\nWho is this for? People building production LLM serving systems, and researchers working on speculative decoding or SLO-aware scheduling. It deserves a serious referee; the missing proof, missing baseline comparisons, and unvalidated surrogate are fixable in revision. I'd send it to review rather than desk reject.\n\nRecommendation: engage with it. Ask for the proof of Theorem 4.1, the SpecServe/SLOS-Serve comparison, and a calibration or sensitivity experiment for the draft-logit surrogate.","headline":"A genuinely new idea—per-request token-tree allocation for multi-SLO speculative decoding—with convincing but under-validated empirics; deserves review, needs a proof for Theorem 4.1 and an honest look at the draft-logit surrogate.","tokens_in":24082,"tokens_out":3947,"would_cite":true,"duration_ms":34956,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"AdaServe argues that multi-SLO LLM serving should be cast as constrained optimization over per-request speculation trees, reducing SLO violations by up to 4.3x.","keywords":["multi-SLO serving","speculative decoding","draft token tree","TPOT SLO","goodput","LLM serving systems","beam search","adaptive speculation"],"falsifier":"Measure, on the paper's own workloads, the rank correlation between the draft model's path-probability estimates and the large model's actual acceptance decisions per node. If that correlation is near zero or negative on high-traffic traces, AdaServe's selection would be near-random and its SLO-attainment advantage over fixed-speculation baselines should disappear; conversely, if the advantage persists even with a deliberately miscalibrated draft model, the logit-surrogate premise is not doing the load-bearing work.","tokens_in":22902,"feed_emoji":"⚡","tokens_out":5686,"duration_ms":53700,"temperature":0.7,"pith_summary":"This paper argues that the reason existing LLM serving systems fail under mixed latency requirements is that they treat all requests identically, batching tokens uniformly and giving every request the same per-token latency. AdaServe instead treats each request's latency target as a constraint and uses speculative decoding, generating several candidate tokens at once with a small draft model and verifying them in parallel with the large model, as a dial to control decoding speed per request. The claim is that by constructing, for every request, a tree of speculative tokens chosen to just meet that request's time-per-output-token SLO and then spending any leftover compute budget on the globally most promising tokens, a server can satisfy more SLOs and produce more useful tokens. On workloads mixing coding, chatbot, and summarization requests, AdaServe reports up to 4.3x fewer SLO violations and up to 1.9x higher goodput than the best baselines.","feed_headline":"SLO-customized speculation cuts LLM SLO violations 4.3x","feed_subtitle":"Per-request draft token trees tuned to each latency goal keep more requests on target while lifting goodput up to 1.9x.","key_machinery":"The load-bearing object is the draft token tree together with the path-probability sum identity $E[\\mathrm{acc}(T)] = \\sum_{v \\in T} f(v)$, where $f(v)$ is the probability the LLM accepts the token sequence from the root to node $v$. This identity converts the two goals, meet each request's TPOT SLO and maximize total accepted tokens, into a shared currency: every node added to a tree contributes its path probability either to a request's SLO constraint or to global throughput. The greedy selection algorithm (Algorithm 1) is optimal because $f(v)$ is strictly decreasing along any root-to-leaf path, so the highest-probability node is always a parent already selected, keeping the chosen set a connected tree; Theorem 4.1 then justifies replacing interleaved single-token draft decoding with a parallel beam search of depth $D_{\\mathrm{opt}}$ and width $B$. Around this core AdaServe builds a speculate-select-verify pipeline: the draft model proposes candidate trees by beam search, an SLO-customized selection assigns tokens to requests in order of how far behind their SLO they are, a throughput-optimized selection spends the remaining budget on the globally top nodes, and the LLM verifies all trees in parallel.","core_discovery":"The central discovery is that the expected number of tokens a speculative-decoding verification accepts from a draft tree decomposes as the sum over the tree's nodes of each node's path probability, $E[\\mathrm{acc}(T)] = \\sum_{v \\in T} f(v)$ (Theorem 3.1), which turns SLO-aware token-tree construction into a budgeted selection problem: pick nodes with the largest path probabilities subject to a hardware token budget and to each request's requirement on expected accepted tokens. Under the assumption that path probabilities are known, a greedy algorithm that first spends tokens to meet each request's SLO threshold and then spends the remainder on the globally highest-probability nodes is provably optimal (Algorithm 1, Appendix C). The practical system removes that assumption by using the draft model's logits as surrogates for path probabilities, decouples speculation from selection so the draft model runs in parallel beam search rather than one node at a time, and bounds the loss with Theorem 4.1: the optimal tree is contained in a beam-search candidate tree of depth equal to the optimal tree's depth and beam width equal to the budget. The paper reports SLO violation reductions up to 4.3x and goodput improvements up to 1.9x versus continuous-batching and static speculative-decoding baselines.","pith_inferences":["The logit-surrogate assumption suggests a calibration check the paper does not implement: serving systems could monitor the rank correlation between draft logits and observed acceptance rates and fall back to more conservative speculation when it degrades.","The path-probability currency could extend to other resource dimensions, such as KV-cache memory or prefill-decode co-scheduling, where each speculative token also has a cost and a similar greedy allocation would apply.","Because the formulation is hardware-agnostic, the same SLO-customized selection could be applied to heterogeneous GPU pools or disaggregated serving, where the token budget $B$ varies from iteration to iteration.","A testable prediction follows: as the draft model is made weaker or more domain-mismatched, AdaServe's advantage over fixed-speculation baselines should shrink and eventually invert, since selection quality degrades toward random."],"forward_implications":["If correct, LLM serving systems can meet heterogeneous latency SLOs without sacrificing throughput, by modulating per-request speculation aggressiveness instead of constraining batch size.","For any fixed token budget and SLO thresholds, spending tokens first on SLO-critical nodes and then on the highest-probability nodes is the best possible allocation; no other node-selection policy beats it under the same assumptions.","Theorem 4.1 implies speculation cost stays near $D_{\\mathrm{opt}}$ draft steps rather than $B-n$, making SLO-aware tree-based serving practical, and the adaptive depth/width policy keeps that cost bounded under load changes.","The decomposition identity gives serving systems a common objective, the sum of path probabilities, that any multi-request speculative-decoding policy can optimize.","The speculate-select-verify pipeline separates the small model's work from the large model's work so that CPU-side selection overhead stays minimal, measured at about 0.3-0.4% of serving time."],"supporting_citations":[{"why":"Supplies the tree-based verification and hardware-aware tree sizing that AdaServe's token-tree construction extends to multi-SLO settings.","marker":"[9]"},{"why":"The draft-model beam search and logit-based acceptance estimates that AdaServe adopts for approximating path probabilities.","marker":"[24]"},{"why":"Introduces tree-based speculative inference and verification, the decoding mechanism AdaServe customizes per request.","marker":"[32]"},{"why":"The vLLM serving system with PagedAttention, the primary continuous-batching baseline AdaServe is compared against.","marker":"[22]"},{"why":"Sarathi-Serve, the chunked-prefill baseline that AdaServe must beat in the multi-SLO regime.","marker":"[1]"},{"why":"The speculative-decoding acceptance scheme that underlies the definition of path acceptance probability f(v).","marker":"[23]"},{"why":"Shows draft models can be aligned with the target LLM, supporting the logit-surrogate assumption of Equation (7).","marker":"[25]"},{"why":"Distillation aligns draft and target logits, cited as evidence that draft logits are accurate surrogates for f(v).","marker":"[58]"},{"why":"DistServe, the source of the multi-category SLO workload settings and goodput metric used in evaluation.","marker":"[57]"}],"fun_headline_variants":["SLO-customized token trees cut violations 4.3x","Per-request speculation trees lift goodput 1.9x","AdaServe tailors draft tokens to each latency SLO","Speculate-select-verify adapts to multi-SLO workloads","Bounded greedy tree selection slashes SLO violations"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole optimization assumes the draft model's token probabilities (its logits) are accurate stand-ins for the probability that the large model will accept each token; if that approximation is wrong, the trees AdaServe builds are optimized for the wrong numbers and the optimality guarantees do not carry over to the real system.","fun_headline_variants_meta":{"raw":{"variants":["SLO-customized token trees cut violations 4.3x","Per-request speculation trees lift goodput 1.9x","AdaServe tailors draft tokens to each latency SLO","Speculate-select-verify adapts to multi-SLO workloads","Bounded greedy tree selection slashes SLO violations"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001071,"raw_usage":{"total_tokens":4523,"prompt_tokens":1019,"completion_tokens":3504,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":635,"completion_tokens_details":{"reasoning_tokens":3418}},"tokens_in":635,"tokens_out":3504,"duration_ms":25575,"temperature":1.0,"reasoning_tokens":3418,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T17:27:18.822813+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Measure, on the paper's own workloads, the rank correlation between the draft model's path-probability estimates and the large model's actual acceptance decisions per node. If that correlation is near zero or negative on high-traffic traces, AdaServe's selection would be near-random and its SLO-attainment advantage over fixed-speculation baselines should disappear; conversely, if the advantage persists even with a deliberately miscalibrated draft model, the logit-surrogate premise is not doing the load-bearing work.","supporting_citations":[{"cited_title":"Specinfer: Accelerating large language model serving with tree-based speculative inference and verification","cited_arxiv_id":null,"evidence_quote":"Introduces tree-based speculative inference and verification, the decoding mechanism AdaServe customizes per request."},{"cited_title":"vllm: Easy, fast, and cheap llm serving with pagedattention","cited_arxiv_id":null,"evidence_quote":"The vLLM serving system with PagedAttention, the primary continuous-batching baseline AdaServe is compared against."},{"cited_title":"Eagle: Speculative sampling requires rethinking feature uncertainty, 2024","cited_arxiv_id":null,"evidence_quote":"Shows draft models can be aligned with the target LLM, supporting the logit-surrogate assumption of Equation (7)."}],"review_version":1}