Making Preemption Productive in Long-Output LLM Serving
Organizations: National University of Singapore Singapore · Sea AI Lab Singapore
Abstract
Reasoning LLMs generate long outputs whose key--value (KV) caches occupy GPU memory for minutes. When memory fills, the server preempts requests, and a preempted request can repeatedly lose and recover its state while producing little new output. We call this behavior KV thrashing. In certain cases, existing systems leave more than a fifth of requests stalled for over a minute. Because preemption cannot be avoided without delaying admission, we ask how to make it productive. We present Stint, a serving system that preserves a preempted request's work, bounds how long it waits, and gives it fresh output after it returns. Stint stores fixed-length KV snapshots in a contiguity-first CPU pool with an exact-extent allocator, and moves them with fused K/V gather/scatter kernels and double buffering. Age-based readmission brings stalled requests back, and protection gives them a turn of fresh decoding before another preemption. Remaining-length estimates from decoding hidden states guide victim selection. On olympiad-math replays with Qwen3-32B on H200 GPUs, no request pauses for more than 50 seconds under Stint and p99 time per output token falls by 50.7% relative to recomputation in the same engine. The replay as a whole finishes 10.7% sooner (12.0% higher throughput), because the requests that baselines starve no longer finish last.
Figures & tables
| Model | Per token | 10,000 tokens |
|---|---|---|
| DeepSeek-R1 ( Guo et al., 2025 ) | 68.625 KiB | 0.654 GiB |
| Llama-3.1-405B ( Grattafiori et al., 2024 ) | 504 KiB | 4.807 GiB |
| Qwen3-32B ( Yang et al., 2025 ) | 256 KiB | 2.441 GiB |
| Llama-3.1-8B ( Grattafiori et al., 2024 ) | 128 KiB | 1.221 GiB |
| Metric | Recomp. | LMCache | HiCache | Stint |
|---|---|---|---|---|
| Throughput (tok/s) | 4,100 | 4,023 | 3,092 | 4,592 |
| Median TPOT (ms) | 38.2 | 39.5 | 49.7 | 40.9 |
| p99 TPOT (ms) | 104.5 | 107.1 | 93.8 | 51.5 |
| Pooled p99 ITL (ms) | 47.9 | 111.7 | 57.4 | 78.0 |
| Mean TTFT (ms) | 49.4 | 74.7 | 147.4 | 56.7 |
| p99 TTFT (ms) | 67.9 | 535.5 | 567.9 | 246.7 |
| Recomp. | LMCache | HiCache | Stint | |
| Median (s) | 0.24 | 0.62 | 2.31 | 29.9 |
| p99 (s) | 788 | 813 | 613 | 47.3 |
| Maximum (s) | 808 | 840 | 658 | 49.3 |
| Requests s | 23.2% | 23.3% | 21.2% | 0% |
| Requests s | 15.9% | 16.2% | 15.5% | 0% |
| Max. share of lifetime | 72.4% | – | – | 8.4% |
| Allocator | Tok/s | Fallbacks | Padding (%) |
|---|---|---|---|
| Uniform 8K | |||
| Mixed sizes | |||
| Exact extents | 4792 61 | 0 0 | 0 0 |
| Allocator | Tok/s | Fallbacks | Padding (%) |
|---|---|---|---|
| Uniform 8K | |||
| Mixed sizes | |||
| Exact extents | 3293 29 | 0 0 | 0 0 |
| MemCopy | Prepare+MemCopy | |||
| Method | D2H | H2D | D2H | H2D |
| HiCache cohort (host A) | ||||
| Stint | 3.680 | 3.231 | 4.243 | 3.961 |
| HiCache layer-first | 3.274 | 3.361 | 8.929 | 9.075 |
| HiCache page-first | 15.793 | 3.360 | 21.948 | 9.086 |
| Local-adapter cohort (host B) | ||||
| K/V kernels | Staging pairs | D2H | H2D |
|---|---|---|---|
| Separate | 1 | ||
| Fused | 1 | ||
| Separate | 2 | ||
| Fused | 2 |
| Mode | Tok/s | Wait (s) | Offloads | Gap s |
|---|---|---|---|---|
| Disabled | 475.43 | 45.11 | 71 | 22% |
| Age-only | 484.45 | 5.20 | 494 | 0% |
| Protected(Q=64) | 494.10 | 13.75 | 286 | 68% |
| Change | Workloads | Runs | Throughput (%) | Other effect |
|---|---|---|---|---|
| Exact extents vs. uniform 8K | AIME1000, LCB800 | 3 | , | AIME fallbacks |
| Fused K/V, two pairs vs. legacy | AIME300, LCB200 | 2 | , | p99 ITL , |
| Prediction enabled but unused | AIME1000, LCB880 | 3 | , | – |
| SRJF vs. physical-largest victims | AIME1000, LCB880 | 3 | , | p99 ITL , |
| Protected recovery (Q64) vs. none | LCB50, 2 pairs | 1 | , | mean decode batch , |
| Protected vs. age-only readmission | LCB50 | 1 | offloads |
Appendix figures & tables20 assets
Supplementary material from the paper’s appendix.
Appendix
| Arrival seed | Recompute | P0 | SRJF |
|---|---|---|---|
| 30 | 103 | 103 | 98 |
| 31 | 100 | 100 | 107 |
| 32 | 101 | 105 | 106 |
| Group | Mean TTFT | Mean TPOT | p99 TPOT | Mean dispatch- to-completion | p99 dispatch- to-completion |
|---|---|---|---|---|---|
| Training100 | |||||
| Training-unseen299 |
| Workload | System | Output tok/s | Mean arrival-to- first-output (s) | p99 TPOT (ms) | Memory guard peak (GiB) |
|---|---|---|---|---|---|
| AIME1000 | Recompute | 7,741.27 | 4.687 | 118.26 | 417.18 |
| FIFO64 recompute | 6,493.93 | 260.629 | 32.16 | 416.35 | |
| Stint | 7,701.16 | 0.074 | 76.86 | 1,446.90 | |
| LCB880 | Recompute | 5,007.50 | 0.084 | 225.14 | 451.33 |
| FIFO64 recompute | 4,703.59 | 225.188 | 39.99 | 451.01 | |
| Stint | 5,189.30 | 0.087 | 57.16 | 1,481.02 |
| Prepared | With preparation | |||
| Method | D2H | H2D | D2H | H2D |
| HiCache cohort: H200 host A, CUDA 12.8 | ||||
| Stint | ||||
| HiCache layer-first | ||||
| HiCache page-first | ||||
| Local-adapter cohort: H200 host B, CUDA 12.8 | ||||
| Model | Workload | MAE | RMSE | |||
|---|---|---|---|---|---|---|
| Stint | AIME300 | 300 | 3,471 | 4,604 | -0.14 | 0.34 |
| DSMN | AIME300 | 300 | 3,942 | 5,580 | -0.68 | 0.24 |
| LTR | AIME300 | 300 | 3,179 | 3,993 | 0.14 | 0.24 |
| S3 | AIME300 | 300 | 4,459 | 5,833 | -0.83 | 0.21 |
| PiA | AIME300 | 300 | 3,377 | 4,114 | 0.09 | 0.30 |
| Stint | LCB200 | 199 | 4,744 | 7,286 | 0.15 | 0.56 |
| Model | KiB/token | |||||
|---|---|---|---|---|---|---|
| Qwen3-32B | 64 | 5,120 | 25,600 | 8,192 | 1,024 | 256 |
| Llama-3.1-8B | 32 | 4,096 | 14,336 | 4,096 | 1,024 | 128 |
| Shift | Scored scope | Frozen MAE | Updated MAE | Change |
|---|---|---|---|---|
| AIME LCB | 494 requests/order | |||
| LCB AIME | 494 requests/order | |||
| AIME LCB | Final target phase | |||
| LCB AIME | Final target phase |
| Shift | Mode | Output tok/s | Mean TTFT | Mean TPOT | p99 TPOT |
|---|---|---|---|---|---|
| AIME LCB | Frozen | ||||
| AIME LCB | Original | ||||
| AIME LCB | Packed | ||||
| LCB AIME | Frozen | ||||
| LCB AIME | Original | ||||
| LCB AIME | Packed |
| Model | Mode | TPOT (ms) | Thpt | ||
|---|---|---|---|---|---|
| avg | p50 | p99 | (tok/s) | ||
| QWQ-32B | Recompute | 67.28 | 61.73 | 110.80 | 702.6 |
| Swap | 64.78 | 58.14 | 103.13 | 712.3 | |
| Llama-8B | Recompute | 55.93 | 57.42 | 142.91 | 3885.8 |
| Swap | 69.61 | 74.50 | 144.37 | 3161.1 | |
| Batch (blocks) | GPU CPU | CPU GPU |
|---|---|---|
| 1 | 1,068 | 1,103 |
| 4 | 2,625 | 2,590 |
| 16 | 3,681 | 3,623 |
| 64 | 4,112 | 3,490 |
| 256 | 4,237 | 3,496 |
| 512 | 4,252 | 3,496 |
| Policy | # Prepts. | TPOT (ms) | Thpt | ||
|---|---|---|---|---|---|
| avg | p50 | p99 | (tok/s) | ||
| LIFO (last) | 448 | 167.8 | 46.2 | 2,618.0 | 269.4 |
| Largest-first | 456 | 105.8 | 45.5 | 990.4 | 240.1 |
| Earliest | 446 | 126.9 | 45.9 | 2,024.7 | 242.5 |
| Random | 479 | 209.7 | 44.7 | 1,199.5 | 242.1 |
| Mode | TPOT (ms) | Thpt | Pre- | Tokens | ||
|---|---|---|---|---|---|---|
| avg | p50 | p99 | (tok/s) | empt. | preempt. | |
| Swap | 128.0 | 116.9 | 249.5 | 45.9 | 191 | 126,509 |
| Recompute | 170.5 | 149.9 | 680.7 | 46.6 | 202 | 101,311 |
| Workload | Observation | Output tok/s | p99 TPOT (ms) | p99 TTFT (ms) | Preemptions |
|---|---|---|---|---|---|
| AIME1000 | Original | 6,844.34 | 169.02 | 282.79 | 1,732 |
| Repaired follow-up | 7,378.17 | 159.10 | 483.08 | 1,801 | |
| LCB880 | Original | 5,159.31 | 173.51 | 277.42 | 1,103 |
| Repaired follow-up | 5,247.53 | 172.57 | 614.82 | 1,122 |
LLM Serving
Large language model serving studies how to deliver model responses with low latency, high throughput, and efficient use of compute and memory.
See all 249 papers