Scheduling Shared-Prefix Decoding with Unknown Output Lengths

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 $k$ simultaneous requests, this restriction causes an $\Omega (k)$ 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 $76/3$ 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 $1.43\times$ and $1.95\times$ 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.