acceptodds
Under review as a conference paper at ICLR 2027

Scheduling Shared-Prefix Decoding with Unknown Output Lengths

14 views

Abstract

Requests sharing a prompt prefix can reuse its key–value (KV) cache. A scheduler must decide which requests to run within a fixed memory budget before knowing their output lengths. We show that individual prompt lengths and generation progress cannot distinguish shared prefixes from disjoint prompts. Such a policy must count the shared prefix separately for each request to respect the memory budget for every compatible prompt layout. On a family of simultaneous requests, this restriction causes an increase in total completion time relative to an optimal schedule. For simultaneous requests whose prompts consist of one shared prefix kept in memory, subtracting its footprint leaves only generated tokens to schedule. This reduction preserves feasible schedules and completion times. With staggered starts and doubling attempt lengths, the Geometric Slicing Algorithm achieves a competitive ratio for total completion time on this budget. The guarantee holds for unknown output lengths in a model where interrupted requests restart from the beginning. We also examine when an existing serving engine can use cached prefixes to admit more requests. In TGI, making prefixes available immediately after prefill yields and makespan speedups on constructed and natural-language request bursts, respectively, under constrained memory. Controls show that the benefit decreases as requests arrive farther apart; native-engine comparisons identify settings where existing scheduling already captures the shared-memory benefit.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
non-clairvoyant scheduling, competitive ratio, KV-cache memory management, prefix sharing, LLM serving systems, Best-of-N and tree decoding, admission control

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_3bJSOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper investigates the scheduler for shared-prefix decoding with unknown output lengths. The authors provide a coverage-GSA method and achieve a 76/3 competitive ratio under specific assumptions. The authors gain a makespan improvement in TGI by making prefixes available immediately.

Critical strengths

The idea is clear and strong through prefix sharing. The authors provide theoretical proof of the competitive ratio.

Critical weaknesses

The results are too limited and strongly depend on arrivals, known prefix, and serving method.

Questions for authors

Is it possible that the method can be used on other inference software such as vLLM? Can you show related results?

1 comment

Thank you for suggesting the vLLM comparison. We implemented the original staggered schedule in vLLM and compared it with native scheduling under a common KV pool and public output cap. In the eager long-first batch, the original schedule reduces mean completion time from 25.5025.50 to 24.2224.22 s, with lower throughput than native. Our reply to etLJ Q2 gives the full comparison.

Starting at slice 3232 and handing the unfinished tail to native vLLM gives the following results on short-heavy batches.

SettingReduction in mean completion timeChange in makespan
Eager, long-first61.5%61.5\%+21.0%+21.0\%
Eager, mixed order45.6%45.6\%+3.9%+3.9\%
CUDA Graph enabled, long-first60.2%60.2\%+19.4%+19.4\%
Batch-invariant kernels, mixed order45.1%45.1\%+4.9%+4.9\%

Sharing is identified from the prompts and cache metadata. The vLLM tests vary request order within simultaneous batches. To examine arrival spacing, Figure 2(b) spreads the same 1616 TGI requests over 00, 22, 55 and 2020 seconds. The earlier-publication makespan gain tapers from 1.93×1.93\times to 1.17×1.17\times, 1.10×1.10\times and 1.03×1.03\times as overlap falls.

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

This paper studies LLM inference scheduling with shared-prefix KV caching and unknown output lengths. It shows that additive memory accounting can incur an Ω(k) loss in total completion time, and reduces the single-shared-prefix setting to an existing scheduling problem by subtracting the shared prefix from the memory budget. Building on the Geometric Slicing Algorithm (GSA), the authors establish a tighter 76/3 competitive ratio and evaluate prefix-aware admission using TGI, vLLM, and real serving traces.

Critical strengths

The paper addresses a well-motivated scheduling problem. The Ω(k) lower bound clearly illustrates the cost of ignoring shared KV memory, while the residual-memory reduction is simple and elegant. The tighter competitive analysis is a useful theoretical contribution. The paper also includes system-level experiments and several controls that help identify when prefix-aware admission is beneficial.

Critical weaknesses
  1. Limited novelty over prior work. The core GSA algorithm, including geometric retries and staggered scheduling, was introduced by Feng et al. [1]. Shared-prefix scheduling has also been explored in Preble [2], Dexter et al. [3], and BatchLLM [4]. In the main setting, Coverage-GSA essentially subtracts the shared prefix from the memory budget and applies the existing GSA. While the new theoretical bounds are valuable, the algorithmic contribution appears incremental, and the distinction from prior work deserves clearer justification.

  2. Insufficient empirical validation of Coverage-GSA. The main TGI speedups (1.43× and 1.95×) come from earlier prefix publication rather than Coverage-GSA itself. Native vLLM already performs close to static coverage admission, while the separate cohort-GSA experiments show substantial overhead from repeated attempts. The paper lacks a direct end-to-end evaluation of the theoretically analyzed staggered Coverage-GSA against strong existing schedulers.

  3. Restrictive assumptions and limited practical applicability. The strongest 76/3 guarantee assumes a single resident shared prefix, no private prompt suffixes, and kill-and-restart execution. Real serving workloads often involve partial prefix sharing, dynamic cache management, and streaming outputs. Restarting requests also introduces redundant computation and potential issues with already delivered tokens. These limitations make the practical implications of the theoretical guarantee less clear.

References

[1] Feng et al., Competitive Non-Clairvoyant KV-Cache Scheduling for LLM Inference. arXiv:2601.22996, 2026. https://arxiv.org/abs/2601.22996

[2] Srivatsa et al., Preble: Efficient Distributed Prompt Scheduling for LLM Serving. ICLR 2025. https://proceedings.iclr.cc/paper_files/paper/2025/hash/5bc342f48de8264779952fac378f96dc-Abstract-Conference.html

[3] Dexter et al., LLM Query Scheduling with Prefix Reuse and Latency Constraints. NeurIPS 2025. https://proceedings.nips.cc/paper_files/paper/2025/hash/878bbdf6227315995c207561211ddb53-Abstract-Conference.html

[4] Zheng et al., BatchLLM: Optimizing Large Batched LLM Inference with Global Prefix Sharing and Throughput-oriented Token Batching. MLSys 2026. https://proceedings.mlsys.org/paper_files/paper/2026/hash/5b7ae1758452854dee4e962207d38304-Abstract-Conference.html

Questions for authors
  1. Beyond the new theoretical bounds, what is the main algorithmic contribution of Coverage-GSA compared with applying the original GSA [1] after subtracting the shared prefix? How does this work differ from existing prefix-aware scheduling approaches [2–4]?

  2. Can the authors evaluate the staggered Coverage-GSA analyzed in Theorem 22 directly against native vLLM or other strong prefix-aware schedulers under matched conditions? Wall-clock latency, throughput, and redundant generation costs would be particularly useful.

  3. Since earlier prefix publication affects both admission and prefill reuse, can the authors isolate their respective contributions to the reported TGI speedups?

  4. How does kill-and-restart translate to practical inference, especially stochastic decoding and streaming APIs? How are generation consistency and previously delivered tokens handled when a request restarts?

3 comments

Thank you for asking what Coverage-GSA adds to GSA and for suggesting a direct test of the staggered schedule.

Q1. Contribution and related work

Coverage-GSA applies Feng et al.'s GSA [1] with its original geometric retries and staggered starts. For one resident shared prefix of size WW and no private prompt suffixes, we run GSA with zero prompt length on R=M−WR=M-W. Theorem 6 proves that this transformation preserves both feasible schedules and the optimum under shared KV memory.

A shared and a disjoint layout can present the same per-request lengths and generation progress. A scheduler that sees only these quantities and must be safe in both layouts can incur an Ω(k)\Omega(k) loss against the shared-memory optimum, even with exact output lengths (Lemma 3 and Theorem 4). With sharing information, our analysis of the residual schedule gives a 76/376/3 bound at finite widths, including width one, for simultaneous requests with no private prompt suffixes and Lmax⁡≤RL_{\max}\le R at growth factor two (Theorem 22).

Preble [2] balances prefix reuse and load across GPUs. Dexter et al. [3] study query ordering under time-to-first-token constraints. BatchLLM [4] groups requests and forms token batches to improve throughput. We ask how shared memory changes feasible decode schedules and what guarantee is possible when output lengths are unknown. This setting captures batches from same-context sampling and parallel continuations.

Q2. Direct evaluation against native vLLM

We implemented the original staggered schedule at αg=2\alpha_g=2 in vLLM, accounting for physical page rounding. We also tested two changes. The first starts at slice 3232. The second hands unfinished requests to native scheduling as fresh attempts at a phase boundary once at least 75%75\% of the batch has completed.

The table uses Qwen3-8B on an A100-40GB, with 6464 simultaneous requests, a resident 20482048-token prefix and a common 144144-page KV pool. All policies receive the same public output cap of 256256. The scheduler learns the stopping lengths through execution. In this eager, long-first batch, eight requests generate 256256 tokens and the other 5656 generate 3232. We report the geometric mean of the three per-seed medians, with three repetitions per seed.

PolicyMean completion (s)p95 (s)Makespan (s)Useful tokens/sDiscarded output tokens
Native vLLM25.5030.4130.74124.940
Original Coverage-SPS24.2286.56113.2333.913,776
Slice 3232 + native handoff9.8327.2737.19103.25256

The original schedule improves mean completion time by 5.0%5.0\% in this setting. It also reduces mean completion time by 79.5%79.5\% against additive SPS and 10.1%10.1\% against cohort GSA in a separate matched comparison. In the ablation, starting at slice 3232 reduces the short-request mean from 15.7115.71 to 7.267.26 s. Handoff alone reduces the long-request mean from 83.6783.67 to 36.0636.06 s. Together they cut explicit restarts from 344344 to 88.

The combined variant reduces mean completion time by 61.5%61.5\% in eager long-first order, 45.6%45.6\% in eager mixed order and 60.2%60.2\% in graph-enabled long-first order. Makespan increases by 21.0%21.0\%, 3.9%3.9\% and 19.4%19.4\%, respectively. These tests use short-heavy batches. Across these settings, the original schedule improves mean completion time over native in eager long-first order. The 76/376/3 guarantee applies to the original staggered schedule in the token model.

Q3. Admission versus prefill reuse

Earlier prefix publication changes both admission and prefill reuse in TGI. The reported 1.43×1.43\times and 1.95×1.95\times makespan gains measure their joint effect. Under loose capacity, earlier publication gives a 1.12×1.12\times gain with the same admission waves, illustrating the prefill-reuse contribution in that setting.

In vLLM, we independently vary the accounting rule and prefix-cache reads on eight requests with a common 11521152-page pool. The table gives mean completion time in seconds, using three seeds and three repetitions per seed.

AccountingReuse onReuse off
Coverage3.1289.195
Additive8.71613.573

In this vLLM control, coverage reduces mean completion time by 64.1%64.1\% with reuse and 32.3%32.3\% without it. Enabling reuse reduces mean completion time by 66.0%66.0\% under coverage and 35.8%35.8\% under additive. Within each accounting rule, the schedule stays fixed and prefill input falls from 90,11290{,}112 to 704704 tokens.

Q4. Restarting sampled and streamed outputs

In our SPS benchmarks, an interrupted attempt discards its partial output and restarts from the prompt. A non-streaming service can buffer attempt output until completion. For streaming, the recovery path keeps the token IDs already sent, rebuilds private KV from those IDs, and continues after the committed prefix.

We tested greedy and sampled decoding (T=0.6T=0.6) on eight prompts and three seeds. With batch-invariant kernels, each of three recovery modes (same-batch restart, serial restart and token-retaining recomputation) matches all 4848 uninterrupted outputs per test. In the EOS-enabled test, the stop reasons also match. With ordinary kernels, token-retaining recovery preserves the delivered prefix in all tested cases, and the continuation can differ. In a separate batch-invariant mixed-order performance test, the combined scheduling variant matches all 576576 native outputs token for token and reduces mean completion time by 45.1%45.1\%.

The 76/376/3 analysis assumes one resident shared prefix and no private prompt suffixes. For known private suffix lengths with qi+Li≤Rq_i+L_i\le R, the residual budget charges each suffix individually and Theorem 9 transfers the corresponding positive-prompt guarantees. General overlapping paths require set-dependent memory accounting (Proposition 8), and cache eviction changes which KV blocks are resident.

Thank you for the detailed response and additional experiments. The direct vLLM comparison, accounting/reuse ablation, and clarification of the restart mechanism help address several concerns from my initial review. I appreciate the authors' efforts and have decided to raise my rating.

I still have some concerns about the gap between the theoretical guarantee and the empirical results. The original schedule shows limited gains over native vLLM, while the stronger results come from a modified variant without the same theoretical guarantee, evaluated on a limited set of constructed workloads.

As this is not my primary area of expertise, I would defer to the AC's judgment and the assessments of reviewers with more expertise in this area.

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

The paper studies KV-memory scheduling for requests with shared prefixes and unknown output lengths. For policies that observe only prompt lengths and generation progress and must remain memory-safe for every compatible layout, the authors show that a long shared prefix can cause an Ω(k) loss in total completion time. In the model with a single resident shared prefix and no private prompt suffixes, subtracting the prefix memory reduces the problem to zero-prompt scheduling. Separate system experiments examine earlier prefix publication in TGI, coverage admission, and retry overhead, showing that the benefits depend on arrival overlap and whether the native scheduler already accounts for sharing.

Critical strengths

1.The theoretical results are matched to their assumptions throughout. The paper gives an information-restricted lower bound, an exact residual-budget reduction for a shared prefix, and a self-contained competitive-ratio proof for the zero-prompt case. It also distinguishes peak reservation from per-tick feasibility and supplies counterexamples for short prefixes, intermediate budgets, online flow time, and general tries, which keeps the scope of each result clear.

2.The system section retains unfavorable results and attributes gains conservatively. The TGI experiments report the overall gain while stating that the intervention affects both admission and prefill reuse, rather than presenting it as an independently identified admission-only speedup; controls with loose capacity, varying arrival gaps, native vLLM, and a physical pool equal to M are reported alongside. The selected-group replay further reports that GSA is slower than a static coverage policy that knows the realized output lengths, and identifies this as an oracle comparison.

Critical weaknesses

1.The paper does not establish a constant competitive ratio for general shared-prefix structures. The core reduction and the 76/3 constant apply to a single resident prefix with no private suffixes. In the extensions, the IGD bound on dynamic disjoint star forests is O(Gβ log Lmax), varying with the number of groups G and the ratio of residual budgets β = Rmax/Rmin across groups; the group-count-independent 4-competitive ratio for BPGS holds under a sufficient condition that the shared prefixes together with all stage reservations fit within the budget, while the mutually exclusive case falls back to the same group-dependent IGD bound, and mixed packing and depth-three overlap are explicitly left open by the authors.

2.The online extension guarantees total completion time, not response time. Theorem 38 gives a constant competitive ratio for online total completion time, while the instance family in Proposition 40 shows an unbounded total-flow ratio for Epoch-GSA. The Scope paragraph explicitly distinguishes the two objectives. However, response time is usually what matters in serving, so the online result provides limited support for latency-sensitive deployment.

Questions for authors

1.The replay submits each selected group together with its common prefix resident. Which additional assumptions of the competitive guarantees do these workloads satisfy? In particular, how do the presence or absence of private prompt suffixes and the restart-on-interruption execution semantics correspond to the actual request structure and engine behavior in the replay? Separately, the 76/3 ratio is obtained for the staggered variant at growth factor exactly 2, whereas the live variant uses a tuned growth factor, Figure 3(c) is labeled cohort GSA, and the TGI experiment changes when prefixes are published; if resources permit, a systems comparison of that variant against native scheduling under matched information constraints might be helpful. .

2.Beyond Proposition 40's adversarial example, do the existing online checks indicate when batching delays dominate total flow? Please present those observations separately from the total-completion-time guarantee.

1 comment

Thank you for drawing attention to the replay assumptions and asking when online batching delays dominate.

Q1. Replay assumptions and direct comparison

The Mooncake replay submits each selected group together after warming its common prefix. It preserves the trace's prefix structure and recorded lengths, including private prompt suffixes. The selection rule W+∑i(qi+Li)≤0.85MW+\sum_i(q_i+L_i)\le 0.85M ensures that each private suffix plus its realized output fits within RR. Static admission receives the realized lengths. Cohort GSA in Figure 3(c) discovers completion by running attempts and resubmits unfinished requests from their original prompts. The live GSA experiments use a growth factor of about 1.771.77. The TGI experiment changes when the cache exposes a prefix to admission.

Our new vLLM comparison uses simultaneous requests with identical complete prompts, a resident prefix and hidden stopping lengths. It runs staggered SPS at growth factor two and accounts for KV page rounding. A separate run executes the exact token-model schedule with additional pages to accommodate rounding. In the eager long-first comparison with the same physical KV pool, the original staggered schedule reduces mean completion time from 25.5025.50 to 24.2224.22 s. Our reply to etLJ Q2 gives the runtime costs and the engineering ablations.

For private suffixes with qi+Li≤Rq_i+L_i\le R, Theorem 9 transfers the corresponding positive-prompt guarantees. For disjoint groups, IGD gives O(Gβlog⁡Lmax⁡)O(G\beta\log L_{\max}). BPGS gives a group-independent bound of 44 when the prefixes and maximum phase reservations fit together (Theorem 49). Mixed packing and depth-three overlap remain open.

Q2. When batching delay dominates response time

We measured waiting in the cohort Epoch-GSA CPU model on the same 100100 workloads at two capacities. Each workload has 3232 requests, lengths sampled uniformly from [1,64][1,64] and release times sampled uniformly from [0,512][0,512].

Residual budgetMean response (ticks)Wait outside batch (ticks)Wait within batch (ticks)
R=64R=64818.1685.68599.13
R=2048R=2048131.4047.370

At R=64R=64, waiting for a turn within the current batch accounts for 73.23%73.23\% of response time. At R=2048R=2048, all requests fit simultaneously even at their maximum lengths, and within-batch waiting disappears. Requests that arrive during an ongoing batch can still wait for it to drain. That outside-batch delay accounts for 36.05%36.05\% of response time. This experiment measures response time. Theorem 38 bounds online total completion time.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.