Pith. sign in

REVIEW 3 major objections 6 minor 7 cited by

AdaServe: Accelerating Multi-SLO LLM Serving with SLO-Customized Speculative Decoding

T0 review · 3 major / 6 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2501.12162 v2 pith:MFS6ILLF submitted 2025-01-21 cs.CL cs.AIcs.DCcs.LG

Zikun Li , Zhuofu Chen , Remi Delacourt , Gabriele Oliaro , Zeyu Wang , Qinghan Chen , Shuhuai Lin , April Yang
show 6 more authors
Zhihao Zhang Zhuoming Chen Sean Lai Xinhao Cheng Xupeng Miao Zhihao Jia
This is my paper · ORCID
classification cs.CLcs.AIcs.DCcs.LG
keywords multi-SLOservingspeculativedecodingdrafttokentreeTPOTSLOgoodputLLMsystemsbeamsearchadaptivespeculation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

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.

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 (3)
  1. [Section 4.2, Eq. (7); Algorithm 2] 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.
  2. [Section 4.2, Theorem 4.1] 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.
  3. [Appendix C] 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.
minor comments (6)
  1. [Algorithms 1 and 2] 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'.
  2. [Section 6.1] 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.
  3. [Section 5.2, Eqs. (8)–(9)] 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.
  4. [Section 6] 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.
  5. [Section 4.2, Eq. (7) and Theorem 3.1] 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.
  6. [Throughout] 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.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the SLO-tree optimization is derived from an independently defined objective and greedy arguments; the draft-logit surrogate and in-house SLO calibration are stated assumptions or evaluation choices, not derivation-equivalent inputs.

full rationale

The paper's central derivation, from the objective E[acc(T)] = sum_v f(v) (Theorem 3.1, Eq. 4) through the SLO constraint (Eqs. 2-5) and the greedy token-tree construction (Algorithm 1), does not reduce to its own inputs. Theorem 3.1 is a definitional identity combining path-acceptance probabilities with linearity of expectation, and Algorithm 1's optimality is argued internally in Appendix C using the fact that greedy selection of the largest f(v) nodes maximizes the cumulative sum under a cardinality budget, with connectivity following from the monotonicity of f(v) along tree paths (Appendix B). The practical Algorithm 2 replaces f(v) with draft-model logits (Eq. 7); this is an explicit, uncalibrated surrogate assumption (Section 4.2, Challenge 1), not a fitted parameter, nor an equation that forces the reported SLO violation or goodput numbers. If the surrogate is miscalibrated, the deployed scheduler may optimize the wrong objective, but that is a correctness/robustness limitation, not a circular derivation. The evaluation compares against external baselines on shared workloads and SLO targets; the Cat-1 SLO is set from a measured near-zero-load baseline latency (Section 6.1), which is testbed self-referential but does not make the relative comparison a tautology. The grid-searched constants c1 and c2 in Eqs. (8)-(9) are tuning choices with no demonstrated encoding of the outcome metric. Self-citations ([9], [32], [37]) supply background identities and standard tree verification, but the central optimality proof and the empirical comparison do not depend on an unverified self-citation. The manuscript omits a proof of Theorem 4.1 (Section 4.2), which weakens the theoretical claim but is a missing-support/correctness issue, not a circular step. Overall: no derivation-equivalent-to-input circularity; score 2 reflects minor non-load-bearing self-citations and self-referential evaluation choices rather than a circular argument.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

AdaServe rests on standard linearity-of-expectation results and on the domain assumption that draft-model logits mirror LLM acceptance behavior. Several engineering constants (c1, c2, n_max, depth/width bounds) are hand-tuned or grid-searched and do not transfer automatically to other workloads or GPUs. No new physical entities are postulated.

free parameters (5)
  • c1 (depth controller) = not reported
    Grid-searched constant in Equation (8); scales the depth policy and affects speculation cost and goodput.
  • c2 (width controller) = not reported
    Grid-searched constant in Equation (9); scales the beam width policy.
  • n_max (per-request token cap) = not reported
    Upper bound on tokens added during SLO-customized selection (Algorithm 2); chosen by hand to prevent budget monopolization.
  • D_max, D_min, W_max bounds = not reported
    Predefined bounds for tree depth and width in Equations (8)-(9); author-chosen.
  • Budget B / B1 / B2 = determined by hardware profiling
    Token budget per iteration from roofline profiling; affects all allocations but is a measured system constant.
assumptions (5)
  • standard math E[acc(T)] = sum_{v in T} f(v) (Theorem 3.1)
    Decomposition of expected accepted tokens; the paper cites prior work [9,24], and Appendix A sketches the same linearity of expectation.
  • domain assumption Draft model logits approximate LLM acceptance probabilities (Equation (7))
    All practical token selection uses M_q products instead of true f(v); supported by distillation literature but not guaranteed for a given draft/base pair.
  • domain assumption Hardware processing power can be captured by a profiled token budget B
    The system sets a fixed per-iteration verification budget from a roofline model (Section 3, footnote 1); real GPU occupancy varies with sequence lengths and kernel shapes.
  • domain assumption TPOT constraints can be relaxed to expectations over accepted tokens (Equation (3))
    Replaces the realized random variable acc(T_i) with its expectation, ignoring variance; a request could still miss its SLO when actual acceptance is below expectation.
  • standard math f(parent) > f(child) for every node (Appendix B)
    Used to prove connectivity of greedy selections; holds for any proper probability distribution over token sequences.

how reviews work

0 comments
Cite this review

Pith. "Pith review of AdaServe: Accelerating Multi-SLO LLM Serving with SLO-Customized Speculative Decoding." pith.science (2026). https://pith.science/paper/MFS6ILLF

@misc{pith2026250112162,
  author       = {Pith},
  title        = {Pith review of: AdaServe: Accelerating Multi-SLO LLM Serving with SLO-Customized Speculative Decoding},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MFS6ILLF}},
  note         = {Machine review of arXiv:2501.12162}
}
abstract

Modern large language model (LLM) applications exhibit diverse service-level objectives (SLOs), from low-latency requirements in interactive coding assistants to more relaxed constraints in data wrangling tasks. Existing LLM serving systems, which rely on uniform batching and scheduling strategies, often fail to meet these heterogeneous SLOs concurrently. We present AdaServe, the first LLM serving system designed to support efficient multi-SLO serving through SLO-customized speculative decoding. AdaServe formulates multi-SLO serving as a constrained optimization problem and introduces a hardware-aware algorithm that constructs a speculation tree tailored to each request's latency target. It features a speculate-select-verify pipeline that enables fine-grained control over decoding speed while maximizing system throughput. AdaServe further adapts to workload variation by dynamically adjusting speculation parameters. Evaluations across diverse workloads show that AdaServe reduces SLO violations by up to 4.3$\times$ and improves goodput by up to 1.9$\times$ compared to the best performing baselines, highlighting its effectiveness in multi-SLO serving.

Figures

Figures reproduced from arXiv: 2501.12162 by the authors.

Figure 1
Figure 1. Existing systems cannot efficiently support multi￾SLO LLM serving. Sarathi-Serve [1] introduces chunked-prefill, where lengthy prefill requests are partitioned into smaller chunks to expe￾dite the Time-to-First-Token (TTFT). FastServe [51] employs a preemptive scheduling method to mitigate latency issues caused by long sequences. VTC [44] ensures fair schedul￾ing by tracking the tokens processed for each service and… view at source ↗
Figure 3
Figure 3. Speculative decoding accelerates LLM inference. (b) A draft token tree Prompt: Describe the structure of an atom. LLM output: An atom consists of three … (a) A draft sequence 𝑡! (An) 𝑡" (atom) 𝑡# (is) 𝑡$ (the) 𝑡% (basic) ✅ ✅ ❌ 𝑡& (unit) 𝑡' (consists) ✅ ✅ ✅ ✅ ❌ 𝑡! (An) 𝑡" (atom) 𝑡# (is) 𝑡% (consists) 𝑡$ (the) 𝑡& (of) 𝑡' (three) ❌LLM rejects ✅LLM accepts 𝑡( (atom.) 𝑡( (atom.) Draft token Correct token Root token [PIT… view at source ↗
Figure 4
Figure 4. Draft sequence and draft token tree. are then verified in parallel using the full LLM in a single verification iteration [5, 14, 25, 32]. As illustrated in [PITH_FULL_IMAGE:figures/full_fig_p003_4.png] view at source ↗
Figures from the paper (10 more)
Figure 5
Figure 5. Figure 5: SLO-customized speculative decoding. In this example, there are two requests in the batch. The budget is 8. In the speculation step, both requests construct a candidate token tree with 3 steps of speculator decoding and beam search where the beam width 𝑤 = 2. During th…
Figure 6
Figure 6. Figure 6: Overview of AdaServe. When many requests are active, the average token budget per request decreases, limiting the viable depth and width of each token tree. In such cases, large 𝑑 and 𝑤 values generate excessive speculative tokens that are likely to be discarded, leadi…
Figure 7
Figure 7. Figure 7: Request frequency of the real-world trace. Workloads. We evaluate AdaServe using a mixture of requests from different applications, each with distinct SLO requirements, following prior work [57]. We consider re￾quests from three categories, as summarized in [PITH_FULL…
Figure 8
Figure 8. Figure 8: SLO attainment w.r.t. RPS. 2.6 2.8 3.0 3.2 3.4 3.6 3.8 4.0 4.2 4.4 4.6 4.8 RPS (requests/s) 200 400 600 800 Goodput (tokens/s) Llama-3.1-70B-Instruct 2.4 2.6 2.8 3.0 3.2 3.4 3.6 3.8 4.0 4.2 RPS (requests/s) 200 400 600 800 Qwen2.5-32B-Instruct [PITH_FULL_IMAGE:figures…
Figure 9
Figure 9. Figure 9: Goodput w.r.t. RPS. 30 50 70 90 Urgent Requests (%) 20 40 60 80 100 SLO Attainment (%) Llama-3.1-70B-Instruct 30 50 70 90 Urgent Requests (%) 200 400 600 800 Goodput (tokens/s) Llama-3.1-70B-Instruct 30 50 70 90 Urgent Requests (%) 20 40 60 80 100 SLO Attainment (%) Qw…
Figure 10
Figure 10. Figure 10: SLO attainment and goodput w.r.t. urgent request proportion. 1.6 1.4 1.2 1.0 0.8 0.6 SLO Scale 20 40 60 80 100 SLO Attainment (%) Llama-3.1-70B-Instruct 1.6 1.4 1.2 1.0 0.8 0.6 SLO Scale 200 400 600 800 Goodput (tokens/s) Llama-3.1-70B-Instruct 1.6 1.4 1.2 1.0 0.8 0.6…
Figure 11
Figure 11. Figure 11: SLO attainment and goodput w.r.t. SLO scale. Metrics. We use SLO attainment and goodput as our pri￾mary metrics. SLO attainment is the percentage of requests in a workload that meet their SLO. Specifically, a request is considered to fulfill its SLO if its average per…
Figure 15
Figure 15. Figure 15: Latency breakdown of AdaServe. models—compared to the overall serving time. These results demonstrate that SLO-customized speculative decoding im￾poses negligible overhead and is well-suited for integration into speculative decoding-based serving systems. 7 Related Wo…
Figure 13
Figure 13. Figure 13: Request arrival pattern of the synthetic trace. AdaServe Sarathi-serve vLLM vLLM-spec (4) vLLM-spec (6) vLLM-spec (8) 0 20 40 60 80 100 SLO Attainment (%) 83.6 65.6 52.6 51.6 47.8 38.4 Llama3-70B AdaServe Sarathi-Serve vLLM vLLM-Spec (4) vLLM-Spec (6) vLLM-Spec (8) 0 …
Figure 14
Figure 14. Figure 14: SLO attainment under the synthetic trace. conservative approach to reduce verification overhead. In contrast, vLLM-Spec employs a static speculation strategy, resulting in a constant average acceptance rate regardless of RPS. However, as shown in [PITH_FULL_IMAGE:fig…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 7 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. DeltaServe: Host-Agnostic Co-Serving of Inference and Fine-Tuning for LLMs

    cs.DC 2026-07 conditional novelty 6.0 of 10

    DeltaServe co-serves LoRA fine-tuning with LLM inference on existing engines (vLLM, SGLang, S-LoRA) through host-agnostic hooks and an SLO-aware scheduler, achieving 2.9x the fine-tuning throughput of LLMStation at 10...

  2. MineDraft: A Framework for Batch Parallel Speculative Decoding

    cs.CL 2026-02 conditional novelty 6.0 of 10

    MineDraft speeds up speculative decoding by keeping two request batches — drafting one batch while verifying the other — gaining up to ~40% per-GPU throughput at moderate draft lengths.

  3. Utility-Driven Speculative Decoding for Mixture-of-Experts

    cs.DC 2025-06 conditional novelty 6.0 of 10

    Cascade is a utility-driven speculation manager that makes speculative decoding practical for MoE LLMs by disabling it when expert-activation cost exceeds token gain and hill-climbing to the best speculation length.

  4. IC-Cache: Efficient Large Language Model Serving via In-context Caching

    cs.LG 2025-01 conditional novelty 6.0 of 10

    IC-Cache reuses historical large-model responses as in-context examples so small models can handle a larger share of serving traffic without losing quality, improving throughput and latency.

  5. SpecRouter: Adaptive Routing for Multi-Level Speculative Decoding in Large Language Models

    cs.LG 2025-05 reject novelty 5.0 of 10

    SpecRouter dynamically schedules chains of draft and verifier models for multi-level speculative decoding, adding a mask-based rollback mechanism for key-value caches.

  6. Streaming, Fast and Slow: Cognitive Load-Aware Streaming for Efficient LLM Serving

    cs.HC 2025-04 conditional novelty 5.0 of 10

    Content-aware pacing of LLM streams, driven by readability or an LLM self-score, can cut simulated compute use by up to 16.8 percent at a 95 percent streaming-reading alignment target.

  7. Collaborative Inference and Learning between Edge SLMs and Cloud LLMs: A Survey of Algorithms, Execution, and Open Challenges

    cs.DC 2025-07 conditional novelty 4.0 of 10

    A survey that builds a taxonomy of edge-cloud LLM-SLM collaboration for inference and training, claiming to be the first to unify both phases.

Reference graph

Works this paper leans on

70 extracted references · 38 canonical work pages · cited by 7 Pith papers

  1. [1]

    Taming throughput-latency tradeoff in llm inference with sarathi-serve

    Amey Agrawal, Nitin Kedia, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S Gulavani, Alexey Tumanov, and Ramachandran Ramjee. Taming throughput-latency tradeoff in llm inference with sarathi-serve. arXiv preprint arXiv:2403.02310, 2024

    arXiv 2024

  2. [2]

    Claude 3.5

    Anthropic. Claude 3.5. https://www.anthropic.com/news/claude-3-5- sonnet. (Accessed on 10/11/2024)

    work page 2024

  3. [3]

    Longbench: A bilingual, multitask benchmark for long context under- standing

    Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhid- ian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, et al. Longbench: A bilingual, multitask benchmark for long context under- standing. arXiv preprint arXiv:2308.14508, 2023

    arXiv 2023

  4. [4]

    How many words do we read per minute? a review and meta-analysis of reading rate

    Marc Brysbaert. How many words do we read per minute? a review and meta-analysis of reading rate. Journal of memory and language , 109:104047, 2019

    work page 2019

  5. [5]

    Medusa: Simple llm inference ac- celeration framework with multiple decoding heads

    Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, Jason D Lee, Deming Chen, and Tri Dao. Medusa: Simple llm inference ac- celeration framework with multiple decoding heads. arXiv preprint arXiv:2401.10774, 2024

    arXiv 2024

  6. [6]

    Accelerating large lan- guage model decoding with speculative sampling

    Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Jean-Baptiste Lespiau, Laurent Sifre, and John Jumper. Accelerating large lan- guage model decoding with speculative sampling. arXiv preprint arXiv:2302.01318, 2023

    arXiv 2023

  7. [7]

    Evaluating large language models trained on code

    Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374, 2021

    arXiv 2021

  8. [8]

    Slos-serve: Optimized serving of multi-slo llms

    Siyuan Chen, Zhipeng Jia, Samira Khan, Arvind Krishnamurthy, and Phillip B Gibbons. Slos-serve: Optimized serving of multi-slo llms. arXiv preprint arXiv:2504.08784, 2025

    arXiv 2025

Show all 70 references
  1. [9]

    Sequoia: Scalable, robust, and hardware-aware speculative decoding

    Zhuoming Chen, Avner May, Ruslan Svirschevski, Yuhsun Huang, Max Ryabinin, Zhihao Jia, and Beidi Chen. Sequoia: Scalable, robust, and hardware-aware speculative decoding. arXiv preprint arXiv:2402.12374, 2024

    2024 arXiv

  2. [10]

    How github copilot serves 400 million completion requests a day, 2025

    David Cheney. How github copilot serves 400 million completion requests a day, 2025

    2025

  3. [11]

    Gonzalez, Ion Stoica, and Eric P

    Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E. Gonzalez, Ion Stoica, and Eric P. Xing. Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality, March 2023

    2023

  4. [12]

    Towards next-generation intelligent assistants leveraging llm techniques

    Xin Luna Dong, Seungwhan Moon, Yifan Ethan Xu, Kshitiz Malik, and Zhou Yu. Towards next-generation intelligent assistants leveraging llm techniques. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , pages 5792–5793, 2023

    2023

  5. [13]

    The llama 3 herd of models

    Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Ka- dian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024

    2024 arXiv

  6. [14]

    Break the se- quential dependency of llm inference using lookahead decoding

    Yichao Fu, Peter Bailis, Ion Stoica, and Hao Zhang. Break the se- quential dependency of llm inference using lookahead decoding. In Forty-first International Conference on Machine Learning

  7. [15]

    Gemini pro

    Google DeepMind. Gemini pro. https://deepmind.google/ technologies/gemini/pro/. (Accessed on 10/11/2024)

    2024

  8. [16]

    Getting started with cuda graphs, September 2019

    Alan Gray. Getting started with cuda graphs, September 2019

    2019

  9. [17]

    Deepseek-r1: Incentivizing reasoning capability in llms via reinforce- ment learning

    Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-r1: Incentivizing reasoning capability in llms via reinforce- ment learning. arXiv preprint arXiv:2501.12948, 2025

    2025 arXiv

  10. [18]

    Deepspeed-fastgen: High-throughput text generation for llms via mii and deepspeed- inference

    Connor Holmes, Masahiro Tanaka, Michael Wyatt, Ammar Ahmad Awan, Jeff Rasley, Samyam Rajbhandari, Reza Yazdani Aminabadi, Heyang Qin, Arash Bakhtiari, Lev Kurilenko, et al. Deepspeed-fastgen: High-throughput text generation for llms via mii and deepspeed- inference. arXiv prep...

    2024 arXiv

  11. [19]

    Specserve: Efficient and slo-aware large language model serving with adaptive speculative decoding

    Kaiyu Huang, Hao Wu, Zhubo Shi, Han Zou, Minchen Yu, and Qingjiang Shi. Specserve: Efficient and slo-aware large language model serving with adaptive speculative decoding. arXiv preprint arXiv:2503.05096, 2025

    2025

  12. [20]

    Openai o1 system card

    Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El- Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, et al. Openai o1 system card. arXiv preprint arXiv:2412.16720, 2024

    2024 arXiv

  13. [21]

    Beyond data and model par- allelism for deep neural networks

    Zhihao Jia, Matei Zaharia, and Alex Aiken. Beyond data and model par- allelism for deep neural networks. In Proceedings of the 2nd Conference on Systems and Machine Learning , SysML’19, 2019. Zikun Li, Zhuofu Chen, Remi Delacourt, Gabriele Oliaro, Zeyu Wang, Qinghan Chen, Shuh...

    2019

  14. [22]

    vllm: Easy, fast, and cheap llm serving with pagedattention

    Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Yu, Joseph E Gonzalez, Hao Zhang, and Ion Stoica. vllm: Easy, fast, and cheap llm serving with pagedattention. See https://vllm.ai/ (accessed 9 August 2023) , 2023

    2023

  15. [23]

    Fast inference from transformers via speculative decoding

    Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. arXiv preprint arXiv:2211.17192, 2022

    2022 arXiv

  16. [24]

    Eagle-2: Faster inference of language models with dynamic draft trees

    Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. Eagle-2: Faster inference of language models with dynamic draft trees. arXiv preprint arXiv:2406.16858, 2024

    2024 arXiv

  17. [25]

    Eagle: Speculative sampling requires rethinking feature uncertainty, 2024

    Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. Eagle: Speculative sampling requires rethinking feature uncertainty, 2024

    2024

  18. [26]

    Eagle- 3: Scaling up inference acceleration of large language models via training-time test, 2025

    Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. Eagle- 3: Scaling up inference acceleration of large language models via training-time test, 2025

    2025

  19. [27]

    Competition-level code generation with alphacode

    Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrit- twieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. Competition-level code generation with alphacode. Science, 378(6624):1092–1097, 2022

    2022

  20. [28]

    {AlpaServe}: Statistical multiplexing with model parallelism for deep learning serving

    Zhuohan Li, Lianmin Zheng, Yinmin Zhong, Vincent Liu, Ying Sheng, Xin Jin, Yanping Huang, Zhifeng Chen, Hao Zhang, Joseph E Gonzalez, et al. {AlpaServe}: Statistical multiplexing with model parallelism for deep learning serving. In 17th USENIX Symposium on Operating Systems De...

    2023

  21. [29]

    Andes: Defining and enhancing quality- of-experience in llm-based text streaming services

    Jiachen Liu, Zhiyu Wu, Jae-Won Chung, Fan Lai, Myungjin Lee, and Mosharaf Chowdhury. Andes: Defining and enhancing quality- of-experience in llm-based text streaming services. arXiv preprint arXiv:2404.16283, 2024

    2024 arXiv

  22. [30]

    Optimizing speculative decoding for serving large language models using goodput, 2024

    Xiaoxuan Liu, Cade Daniel, Langxiang Hu, Woosuk Kwon, Zhuohan Li, Xiangxi Mo, Alvin Cheung, Zhijie Deng, Ion Stoica, and Hao Zhang. Optimizing speculative decoding for serving large language models using goodput, 2024

    2024

  23. [31]

    Helix: Serving large language models over heterogeneous gpus and network via max-flow

    Yixuan Mei, Yonghao Zhuang, Xupeng Miao, Juncheng Yang, Zhi- hao Jia, and Rashmi Vinayak. Helix: Serving large language models over heterogeneous gpus and network via max-flow. arXiv preprint arXiv:2406.01566, 2024

    2024 arXiv

  24. [32]

    Specinfer: Accelerating large language model serving with tree-based speculative inference and verification

    Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Zhengxin Zhang, Rae Ying Yee Wong, Alan Zhu, Lijie Yang, Xiaoxiang Shi, et al. Specinfer: Accelerating large language model serving with tree-based speculative inference and verification. In Proceedings of th...

    2024

  25. [33]

    Mlperf inference: Datacenter, 2025

    MLCommons. Mlperf inference: Datacenter, 2025

    2025

  26. [34]

    Mlperf inference v5.0 advances language model capa- bilities for genai, 2025

    MLCommons. Mlperf inference v5.0 advances language model capa- bilities for genai, 2025

    2025

  27. [35]

    Can foundation models wrangle your data? arXiv preprint arXiv:2205.09911, 2022

    Avanika Narayan, Ines Chami, Laurel Orr, Simran Arora, and Christo- pher Ré. Can foundation models wrangle your data? arXiv preprint arXiv:2205.09911, 2022

    2022 arXiv

  28. [36]

    Tensorrt-llm

    NVIDIA. Tensorrt-llm. https://nvidia.github.io/TensorRT-LLM/index. html. (Accessed on 10/11/2024)

    2024

  29. [37]

    Suf- fixdecoding: A model-free approach to speeding up large language model inference, 2024

    Gabriele Oliaro, Zhihao Jia, Daniel Campos, and Aurick Qiao. Suf- fixdecoding: A model-free approach to speeding up large language model inference, 2024

    2024

  30. [38]

    OpenAI. Gpt-4o. https://openai.com/index/hello-gpt-4o/. (Accessed on 10/11/2024)

    2024

  31. [39]

    Splitwise: Efficient gen- erative llm inference using phase splitting

    Pratyush Patel, Esha Choukse, Chaojie Zhang, Aashaka Shah, Íñigo Goiri, Saeed Maleki, and Ricardo Bianchini. Splitwise: Efficient gen- erative llm inference using phase splitting. In 2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA) , pages 118–...

    2024

  32. [40]

    Mooncake: Kimi’s kvcache-centric architecture for llm serving

    Ruoyu Qin, Zheming Li, Weiran He, Mingxing Zhang, Yongwei Wu, Weimin Zheng, and Xinran Xu. Mooncake: Kimi’s kvcache-centric architecture for llm serving. arXiv preprint arXiv:2407.00079, 2024

    2024 arXiv

  33. [41]

    So much to read, so little time: How do we read, and can speed reading help? Psychological Science in the Public Interest, 17(1):4–34, 2016

    Keith Rayner, Elizabeth R Schotter, Michael EJ Masson, Mary C Potter, and Rebecca Treiman. So much to read, so little time: How do we read, and can speed reading help? Psychological Science in the Public Interest, 17(1):4–34, 2016

    2016

  34. [42]

    Mlperf inference benchmark

    Vijay Janapa Reddi, Christine Cheng, David Kanter, Peter Mattson, Guenther Schmuelling, Carole-Jean Wu, Brian Anderson, Maximilien Breughe, Mark Charlebois, William Chou, et al. Mlperf inference benchmark. In 2020 ACM/IEEE 47th Annual International Symposium on Computer Archit...

    2020

  35. [43]

    Code llama: Open foundation models for code

    Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Romain Sauvestre, Tal Remez, et al. Code llama: Open foundation models for code. arXiv preprint arXiv:2308.12950, 2023

    2023 arXiv

  36. [44]

    Fairness in serv- ing large language models

    Ying Sheng, Shiyi Cao, Dacheng Li, Banghua Zhu, Zhuohan Li, Danyang Zhuo, Joseph E Gonzalez, and Ion Stoica. Fairness in serv- ing large language models. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24) , pages 965–988, 2024

    2024

  37. [45]

    Fu, Zhiqiang Xie, Beidi Chen, Clark Barrett, Joseph E

    Ying Sheng, Lianmin Zheng, Binhang Yuan, Zhuohan Li, Max Ryabinin, Daniel Y. Fu, Zhiqiang Xie, Beidi Chen, Clark Barrett, Joseph E. Gonzalez, Percy Liang, Christopher Ré, Ion Stoica, and Ce Zhang. Flexgen: High-throughput generative inference of large language models with a si...

    2023

  38. [46]

    Dynamollm: Designing llm inference clusters for perfor- mance and energy efficiency

    Jovan Stojkovic, Chaojie Zhang, Íñigo Goiri, Josep Torrellas, and Esha Choukse. Dynamollm: Designing llm inference clusters for perfor- mance and energy efficiency. arXiv preprint arXiv:2408.00741, 2024

    2024

  39. [47]

    Spectr: Fast speculative decoding via optimal transport

    Ziteng Sun, Ananda Theertha Suresh, Jae Hun Ro, Ahmad Beirami, Himanshu Jain, and Felix Yu. Spectr: Fast speculative decoding via optimal transport. Advances in Neural Information Processing Systems , 36, 2024

    2024

  40. [48]

    Ml-enhanced code completion improves developer productivity, 2022

    Maxim Tabachnyk and Stoyan Nikolov. Ml-enhanced code completion improves developer productivity, 2022

    2022

  41. [49]

    Hashimoto

    Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. Stanford alpaca: An instruction-following llama model. https://github.com/ tatsu-lab/stanford_alpaca, 2023

    2023

  42. [50]

    Gptvoicetasker: Llm-powered virtual assistant for smartphone

    Minh Duc Vu, Han Wang, Zhuang Li, Jieshan Chen, Shengdong Zhao, Zhenchang Xing, and Chunyang Chen. Gptvoicetasker: Llm-powered virtual assistant for smartphone. arXiv preprint arXiv:2401.14268, 2024

    2024 arXiv

  43. [51]

    Fast dis- tributed inference serving for large language models

    Bingyang Wu, Yinmin Zhong, Zili Zhang, Shengyu Liu, Fangyue Liu, Yuanhang Sun, Gang Huang, Xuanzhe Liu, and Xin Jin. Fast dis- tributed inference serving for large language models. arXiv preprint arXiv:2305.05920, 2023

    2023 arXiv

  44. [52]

    Spec- ulative decoding: Lossless speedup of autoregressive translation

    Heming Xia, Tao Ge, Si-Qing Chen, Furu Wei, and Zhifang Sui. Spec- ulative decoding: Lossless speedup of autoregressive translation

  45. [53]

    An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, et al. Qwen2. 5 technical report. arXiv preprint arXiv:2412.15115, 2024

    2024 arXiv

  46. [54]

    Accelerating self-attentions for llm serving with flash- infer, February 2024

    Zihao Ye, Lequn Chen, Ruihang Lai, Yilong Zhao, Size Zheng, Junru Shao, Bohan Hou, Hongyi Jin, Yifei Zuo, Liangsheng Yin, Tianqi Chen, and Luis Ceze. Accelerating self-attentions for llm serving with flash- infer, February 2024

    2024

  47. [55]

    Orca: A distributed serving system for Transformer- Based generative models

    Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, and Byung-Gon Chun. Orca: A distributed serving system for Transformer- Based generative models. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22), pages 521–538, Carlsbad, CA, July 2022...

    2022

  48. [56]

    Efficiently programming large language models using sglang

    Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Jeff Huang, Chuyue Sun, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E Gonzalez, et al. Efficiently programming large language models using sglang. arXiv preprint arXiv:2312.07104, 2023

    2023 arXiv

  49. [57]

    Distserve: Disaggregating prefill and decoding for goodput-optimized large language model serving

    Yinmin Zhong, Shengyu Liu, Junda Chen, Jianbo Hu, Yibo Zhu, Xu- anzhe Liu, Xin Jin, and Hao Zhang. Distserve: Disaggregating prefill and decoding for goodput-optimized large language model serving. arXiv preprint arXiv:2401.09670, 2024. AdaServe: SLO-Customized LLM Serving wit...

    2024 arXiv

  50. [58]

    Distillspec: Improving speculative decoding via knowledge distillation

    Yongchao Zhou, Kaifeng Lyu, Ankit Singh Rawat, Aditya Krishna Menon, Afshin Rostamizadeh, Sanjiv Kumar, Jean-François Kagy, and Rishabh Agarwal. Distillspec: Improving speculative decoding via knowledge distillation. arXiv preprint arXiv:2310.08461, 2023. Zikun Li, Zhuofu Chen...

    arXiv

  51. [59]

    Base Case: The root node is selected first because it has the highest value (𝑓(𝑟𝑜𝑜𝑡) = 1 > 𝑓(𝑣) for all other nodes𝑣)

  52. [60]

    For a node 𝑣 at step𝑛, the al- gorithm ensures that 𝑝𝑎𝑟𝑒𝑛𝑡(𝑣) is selected before 𝑣, 𝑓(𝑝𝑎𝑟𝑒𝑛𝑡(𝑣)) > 𝑓(𝑣)

    Inductive Step: Assume that at step𝑛− 1, the selected nodes are connected. For a node 𝑣 at step𝑛, the al- gorithm ensures that 𝑝𝑎𝑟𝑒𝑛𝑡(𝑣) is selected before 𝑣, 𝑓(𝑝𝑎𝑟𝑒𝑛𝑡(𝑣)) > 𝑓(𝑣). Thus,𝑣 is connected to the se- lected nodes. By induction, all selected nodes form a valid, conne...

  53. [61]

    If Algorithm 1 returns INVALID, no feasible solution exists

  54. [62]

    Preliminaries and Notation: • For each request𝑟𝑖, we have a token tree𝑇𝑖𝑛𝑓(𝑟𝑖)

    If a feasible solution exists, the solution returned by Algorithm 1 is optimal. Preliminaries and Notation: • For each request𝑟𝑖, we have a token tree𝑇𝑖𝑛𝑓(𝑟𝑖). • Each node𝑣 in𝑇𝑖𝑛𝑓(𝑟𝑖) is associated with a path prob- ability𝑓(𝑣). • The goal for each request𝑟𝑖 is to achieve a ta...

  55. [63]

    The algorithm attempts to meet𝐴(𝑟𝑖) by repeatedly choosing the highest𝑓(𝑣) node from𝑇𝑖𝑛𝑓(𝑟𝑖) not yet chosen by any request, until𝐴(𝑟𝑖) is reached or the budget𝐵 is exhausted

  56. [64]

    By Lemma C.1, the minimal number of tokens needed to achieve𝐴(𝑟𝑖) is𝑁𝑖

    If at some step 𝑖, the algorithm cannot find enough tokens to achieve 𝐴(𝑟𝑖) (i.e., it runs out of budget before𝐴(𝑟𝑖) is met), it returns INVALID. By Lemma C.1, the minimal number of tokens needed to achieve𝐴(𝑟𝑖) is𝑁𝑖. If the algorithm fails at request 𝑖, it means it has alread...

  57. [65]

    Note that𝑀𝑖(𝑆)≥ 𝑁𝑖 for the solution𝑆 returned by the algorithm, where 𝑀𝑖(𝑆) is the number of tokens allocated to𝑟𝑖 in𝑆

    Define𝑁𝑖 as the minimal number of tokens required to achieve𝐴(𝑟𝑖) for each request𝑟𝑖. Note that𝑀𝑖(𝑆)≥ 𝑁𝑖 for the solution𝑆 returned by the algorithm, where 𝑀𝑖(𝑆) is the number of tokens allocated to𝑟𝑖 in𝑆. The same holds for any other feasible solution𝑆′:𝑀𝑖(𝑆′)≥ 𝑁𝑖

  58. [66]

    Being “better” might mean it uses fewer tokens or achieves a higher sum of𝑓(𝑣) for the given budget

    Suppose there exists a valid solution𝑆′ that is better than𝑆. Being “better” might mean it uses fewer tokens or achieves a higher sum of𝑓(𝑣) for the given budget. Consider how𝑆′ distributes tokens among requests: there must be some difference in the number of tokens allocated ...

  59. [67]

    For any single token tree𝑇𝑖𝑛𝑓(𝑟𝑖) and a given number of tokens𝑀𝑖, by Lemma C.2, the greedy choice of𝑀𝑖 nodes yields the maximum possible sum of𝑓(𝑣) for that budget on 𝑟𝑖

    Fix a particular distribution of the budget across the requests. For any single token tree𝑇𝑖𝑛𝑓(𝑟𝑖) and a given number of tokens𝑀𝑖, by Lemma C.2, the greedy choice of𝑀𝑖 nodes yields the maximum possible sum of𝑓(𝑣) for that budget on 𝑟𝑖. Thus, if 𝑆′ differs from𝑆, but assigns th...

  60. [68]

    Hence, any improvement in one request’s allocation in𝑆′ would require changing the budget distribution among requests. However, after ensuring the mini- mal quotas𝑁𝑖 for each request (which both𝑆 and any feasible𝑆′ must respect), the second step of the algo- rithm in𝑆 distribu...

  61. [69]

    If Algorithm 1 returns INVALID, no feasible solution can exist, since the minimal required tokens to meet the SLOs of the first𝑖 requests already exceed𝐵

  62. [70]

    Any other solution that meets all SLOs cannot be strictly better, due to the maximality properties of the greedy selections both per-request and globally

    If a feasible solution exists, the solution returned by Algorithm 1 must be optimal. Any other solution that meets all SLOs cannot be strictly better, due to the maximality properties of the greedy selections both per-request and globally. Thus, Algorithm 1 is correct and optimal. □

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.