Deadline-Aware Adaptive Prefill Chunking for Efficient Large Language Model Serving

• URL: http://arxiv.org/abs/2609.07883v1
• Date: Mon, 07 Sep 2026 18:47:57 GMT
• Title: Deadline-Aware Adaptive Prefill Chunking for Efficient Large Language Model Serving
• Abstract summary: Continuous improves large language model (LLM) serving throughput, but long prompt prefills can delay decode iterations and violate inter-token latency objectives.<n>We introduce SLOWeave, an online scheduling method that selects the largest prefill chunk predicted to finish before the earliest active decode deadline.<n>We prove that, whenever a decode-only iteration is feasible and the cost iteration is accurate, SLOWeave maximizes immediate prefill progress among decisions that preserve every active request's next-token deadline.
• Score: 11.307452536192125
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Continuous batching improves large language model (LLM) serving throughput, but long prompt prefills can delay decode iterations and violate inter-token latency objectives. Chunked prefill mitigates this interference, yet its chunk size is normally fixed: small chunks protect decode latency but repeatedly pay launch overhead, while large chunks improve prefill efficiency but create latency spikes. We introduce SLOWeave, an online scheduling method that selects the largest prefill chunk predicted to finish before the earliest active decode deadline. The decision requires no workload-specific chunk-size tuning and is computed by a logarithmic-time search over a monotone iteration-cost model. We prove that, whenever a decode-only iteration is feasible and the cost predictor is accurate, SLOWeave maximizes immediate prefill progress among decisions that preserve every active request's next-token deadline. We evaluate the method in a reproducible event-driven simulator and an iteration-level GPU runtime across chat, mixed-context, long-context, and bursty workloads. Under a 25ms time-per-output-token objective, SLOWeave improves goodput over the strongest fixed-chunk baseline by 39% on mixed requests and 38% on long-context requests. Under a stricter 10ms objective, the gains rise to 3.3$\times$ and 2.4$\times$, respectively. These results isolate adaptive chunk sizing as a useful serving primitive and provide an implementation-ready controller for integration with iteration-level LLM runtimes.

Related papers

• $\nabla$-Reasoner: LLM Reasoning via Test-Time Gradient Descent in Latent Space [71.23672814629448]
  $nabla$-Reasoner is an iterative generation framework that integrates differentiable optimization over token logits into the decoding loop.<n>$nabla$-Reasoner achieves over 20% accuracy improvement on a challenging mathematical reasoning benchmark.
  arXiv  Detail & Related papers  (2026-03-05T08:42:54Z)
• FlowPrefill: Decoupling Preemption from Prefill Scheduling Granularity to Mitigate Head-of-Line Blocking in LLM Serving [13.856291757420012]
  Long-running requests monopolize resources and delay higher-priority ones, leading to widespread time-to-first-token (TTFT) service level violations.<n>We propose FlowPrefill, a TTFT-goodput-optimized serving system that balances execution granularity against scheduling overheads.<n>We show that FlowPrefill improves maximum goodput by up to 5.6$times$ compared to state-of-the-art systems.
  arXiv  Detail & Related papers  (2026-02-18T16:57:45Z)
• dParallel: Learnable Parallel Decoding for dLLMs [77.24184219948337]
  Diffusion large language models (dLLMs) offer parallel token prediction and lower inference latency.<n>Existing open-source models still require nearly token-length decoding steps to ensure performance.<n>We introduce dParallel, a simple and effective method that unlocks the inherent parallelism of dLLMs for fast sampling.
  arXiv  Detail & Related papers  (2025-09-30T16:32:52Z)
• Intra-request branch orchestration for efficient LLM reasoning [52.68946975865865]
  Large Language Models (LLMs) increasingly rely on inference-time reasoning algorithms to improve accuracy on complex tasks.<n>Prior work has largely focused on reducing token usage, often at the expense of accuracy, while overlooking other latency factors.<n>We present DUCHESS, an LLM serving system that reduces cost and latency without sacrificing accuracy through intra-request branch orchestration guided by predictions.
  arXiv  Detail & Related papers  (2025-09-29T15:52:08Z)
• Adaptively Robust LLM Inference Optimization under Prediction Uncertainty [9.541681114575812]
  We study the problem of optimizing Large Language Model (LLM) inference scheduling to minimize total latency.<n>A key challenge in LLM inference scheduling is that while the prompt length is known upon arrival, the output length, which critically impacts memory usage and processing time, is unknown.<n>We propose algorithms that leverage machine learning to predict output lengths, assuming the prediction provides an interval classification (min-max range) for each request.
  arXiv  Detail & Related papers  (2025-08-20T08:55:26Z)
• OverFill: Two-Stage Models for Efficient Language Model Decoding [68.68408155020568]
  Large language models (LLMs) excel across diverse tasks but face significant deployment challenges due to high inference costs.<n>We propose OverFill, which decouples prefill and decode stages to optimize accuracy-efficiency tradeoffs.<n>Our 3B-to-1B OverFill configuration outperforms 1B pruned models by 83.2%, while the 8B-to-3B configuration improves over 3B pruned models by 79.2% on average.
  arXiv  Detail & Related papers  (2025-08-11T20:07:34Z)
• LLM Serving Optimization with Variable Prefill and Decode Lengths [6.937936394246354]
  We study the problem of serving LLM (Large Language Model) requests where each request has heterogeneous prefill and decode lengths.<n>We show that this problem is NP-hard due to the interplay of placement constraints, precedence relationships, and linearly increasing memory usage.<n>We propose a novel algorithm based on a new selection metric that efficiently forms batches over time.
  arXiv  Detail & Related papers  (2025-08-08T08:54:21Z)
• $\texttt{SPECS}$: Faster Test-Time Scaling through Speculative Drafts [55.231201692232894]
  $textttSPECS$ is a latency-aware test-time scaling method inspired by speculative decoding.<n>Our results show that $textttSPECS$matches or surpasses beam search accuracy while reducing latency by up to $sim$19.1%.
  arXiv  Detail & Related papers  (2025-06-15T05:50:05Z)
• Training Long-Context LLMs Efficiently via Chunk-wise Optimization [60.05884946552877]
  We present textitSequential Chunk-wise Optimization (SeCO), a memory-efficient training paradigm that partitions lengthy inputs into manageable chunks.<n>We also introduce textitSparse Chunk-wise Optimization (SpaCO), which reduces computational overhead by selectively propagating gradients to specific chunks.<n>SpaCO decouples the computational cost of backpropagation from the context length, enabling training time to gradually converge to inference time as sequences become longer.
  arXiv  Detail & Related papers  (2025-05-22T14:11:34Z)
• Squeezed Attention: Accelerating Long Context Length LLM Inference [61.787865959140994]
  We propose Squeezed Attention to accelerate applications where a large portion of the input context is fixed.<n>During inference, we compare query tokens from the user input with the centroids to predict which keys from the fixed context are semantically relevant.<n>We also present a hierarchical version of our algorithm which can reduce the complexity of attention from linear to logarithmic with respect to the fixed context length.
  arXiv  Detail & Related papers  (2024-11-14T18:54:19Z)
• Medha: Efficiently Serving Multi-Million Context Length LLM Inference Requests Without Approximations [8.725115559974999]
  We show that existing work for long context inference is largely based on techniques from long context training.<n>This leads to inefficient resource utilization, server fragmentation, and head-of-line (HOL) blocking.<n>We present Medha, an end-to-end system for efficient long-context inference.
  arXiv  Detail & Related papers  (2024-09-25T18:21:05Z)
• MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention [36.49445805074941]
  MInference (Milliontokens Inference) is a sparse calculation method designed to accelerate pre-filling of long-sequence processing. We demonstrate that MInference effectively reduces inference latency by up to 10x for pre-filling on an A100, while maintaining accuracy.
  arXiv  Detail & Related papers  (2024-07-02T17:59:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.