PaperlayerView exact revision on arXiv

Source-linked AI summary

Duration Aware Scheduling for ASR Serving Under Workload Drift

Darshan Makwana, Yash Jogi, Harsh Kotta, Aayush Kubba

arXiv:2603.11273v1cs.LG

TL;DR

ASR serving commonly uses FCFS despite request-duration variability, which can increase queue delays when long requests block shorter ones. This paper integrates SJF and HRRN using audio duration as a processing-time proxy; SJF cuts median E2E latency up to 73%, while HRRN limits tail-latency degradation to 24%.

  • Problem

    FCFS scheduling in ASR serving ignores request-duration variability, allowing long requests to block shorter ones and increasing queue delays and latency.

  • Method

    The paper uses audio duration as a processing-time proxy and integrates SJF and HRRN duration-aware schedulers into vLLM.

  • Results

    SJF achieves up to 73% lower median E2E latency at high load, while HRRN bounds tail-latency degradation to at most 24%; gains persist under workload drift.

  • Takeaways & Limitations

    Duration-aware scheduling is a simple, deployment-ready lever for improving user-perceived latency in production ASR systems.

  • Takeaways & Limitations

    The duration estimator can overestimate output tokens for recordings with extended silence, motivating voice-activity-based duration estimation.

Abstract

from arXiv · show

Scheduling policies in large-scale Automatic Speech Recognition (ASR) serving pipelines play a key role in determining end-to-end (E2E) latency. Yet, widely used serving engines rely on first-come-first-served (FCFS) scheduling, which ignores variability in request duration and leads to head-of-line blocking under workload drift. We show that audio duration is an accurate proxy for job processing time in ASR models such as Whisper, and use this insight to enable duration-aware scheduling. We integrate two classical algorithms, Shortest Job First (SJF) and Highest Response Ratio Next (HRRN), into vLLM and evaluate them under realistic and drifted workloads. On LibriSpeech test-clean, compared to baseline, SJF reduces median E2E latency by up to $73\%$ at high load, but increases $90$th-percentile tail latency by up to $97\%$ due to starvation of long requests. HRRN addresses this trade-off: it reduces median E2E latency by up to $28\%$ while bounding tail-latency degradation to at most $24\%$. These gains persist under workload drift, with no throughput penalty and $<0.1$\,ms scheduling overhead per request.

1 INTRODUCTION

The paper addresses FCFS head-of-line blocking under heavy or variable ASR workloads by estimating job length from audio duration and applying duration-aware scheduling. Integrating SJF and HRRN into vLLM improves latency, while HRRN limits SJF’s tail-latency trade-off across evaluated workloads.

  • Motivation: FCFS can let long-running requests block shorter ones, increasing queue delays and average latency under heavy load or variable request distributions.End-to-end latency is critical for interactive ASR applications because noticeable delays can reduce usability and user satisfaction.
  • Approach: Audio duration is used as a proxy for job processing time to prioritize requests with SJF and HRRN.The two algorithms were integrated into vLLM and evaluated on LibriSpeech test-clean plus a synthetic uniform-duration workload to study robustness under workload drift.
  • Results: 73%: SJF reduces median end-to-end latency by up to 73% versus baseline at high workload on LibriSpeech.SJF also reduces median time to first token by up to 93% in the same setting.
  • Results: 24% versus 97%: HRRN bounds 90th-percentile tail-latency degradation to at most 24%, compared with 97% for SJF.On the synthetic split, SJF still achieves up to a 67% reduction in median end-to-end latency, indicating gains beyond natural LibriSpeech duration skew.

2 RELATED WORK

Prior serving systems and scheduling methods largely target text-based LLM inference, where job length must be predicted or approximated and engines default to FCFS. This work differs by using audio duration, known at ASR request arrival and strongly correlated with processing time, as the job-length signal.

  • LLM serving systems: Modern inference engines including Orca and vLLM, along with Sarathi-Serve, DistServe, and Splitwise, default to FCFS scheduling.These systems introduced iteration-level scheduling, paged KV-cache management, chunked prefill, or prefill/decode disaggregation.
  • Scheduling for LLM inference: LLM-serving schedulers use token-based queues, predicted output lengths, quality-of-experience objectives, or token-granularity scheduling.FastServe uses skip-join MLFQ; Fu et al. approximate SJF using a ranking model and report up to 2.8× lower latency on chatbot workloads.
  • Output length prediction: Prior output-length methods use classifiers, self-prediction, semantic features, or proxy models, and incur non-trivial overhead.These methods support KV-cache sizing or scheduling through predicted or approximated sequence lengths.
  • Size-based scheduling: Classical size-based scheduling prioritizes shorter jobs, while prior systems exploit known file sizes or deterministic DNN execution times.SRPT has been shown to reduce mean response time in web servers with limited unfairness under heavy-tailed workloads.
  • Key distinction: Unlike text-based LLM inference, ASR provides audio duration at request arrival, and duration correlates strongly with processing time.Text-based systems require auxiliary models, prompting, or heuristic features because output length is fundamentally unpredictable.

3 METHODOLOGY

The methodology uses audio duration as a relative estimate of ASR job processing time, then applies duration-aware SJF and HRRN scheduling. SJF favors short jobs but can starve long requests, while HRRN combines waiting time with estimated duration to balance these priorities.

  • Processing-Time Estimation: Whisper decoding time grows approximately linearly with generated output tokens, while encoding time is near-constant per 30-second segment.Overall processing time is therefore dominated by decoding and output-token count.
  • Processing-Time Estimation: Audio duration reliably estimates processing time because it strongly correlates with generated token count, and scheduling requires only relative job ordering.The correlation is empirically analyzed on LibriSpeech test-clean and FLEURS using whisper-large-v3.
  • Shortest Job First (SJF): SJF prioritizes shorter incoming jobs to minimize average waiting time, using a min-heap with O(log n) insertion and deletion cost.Earlier arrivals break ties among jobs with equal duration.
  • Shortest Job First (SJF): SJF can starve long jobs when short requests continuously arrive, delaying long requests indefinitely.This is the central limitation addressed by HRRN.
  • Highest Response Ratio Next (HRRN): HRRN orders jobs by response ratio, combining waiting time and estimated job duration to favor shorter jobs while gradually increasing priority for requests that wait longer.Audio duration is used directly as estimated job time because only relative ordering is required.

4 EXPERIMENTS

Experiments evaluate SJF and HRRN against FCFS across original and synthetic LibriSpeech workloads under varying request rates. SJF provides larger median-latency gains but incurs substantial tail penalties, while HRRN offers a more balanced trade-off without throughput loss or meaningful scheduling overhead.

  • Evaluation methodology: P50 and P90 E2EL capture typical and tail user experience, respectively, across request-rate conditions.E2EL includes queuing, prefill, and decode; TTFT is also evaluated as a responsiveness metric.
  • Original LibriSpeech: At 10 req/s, SJF reduces P50 and P90 E2EL by 6% and 8%, while HRRN reduces both metrics by 8% versus FCFS.All policies perform similarly at lower load because queues rarely form.
  • Original LibriSpeech: At 17 req/s, SJF reduces P50 E2EL by 23% but increases P90 E2EL by 5%, whereas HRRN changes these metrics by -10% and +9%.HRRN sacrifices some median-latency improvement by gradually promoting long-waiting jobs.
  • Original LibriSpeech: At 23 req/s, SJF reduces P50 E2EL by 66% but increases P90 E2EL by 138%, while HRRN reduces P50 by 23% and limits P90 degradation to 32%.These results show HRRN providing a practical middle ground under heavy load.
  • Synthetic split: At 25 req/s on the synthetic split, SJF reduces P50 E2EL by 67%, while its P90 E2EL inflation is 29% versus 97% on LibriSpeech.At 20 req/s, SJF’s P90 inflation is 57% versus 79%; HRRN’s penalty at 25 req/s is 14% versus 24%.
  • Throughput and overhead: All three policies achieve identical request throughput on both datasets, with scheduling adding less than 0.1 ms per request.The overhead is negligible relative to the approximately 60–100 ms processing time for one ASR decoder step.

5 LIMITATIONS AND FUTURE WORK

The duration-aware estimator can overestimate output tokens for recordings with extended silence and may lose accuracy across languages with different tokenization densities. Future work includes VAD preprocessing and adaptive estimation or dynamic policy switching based on live workload signals.

  • Silence sensitivity: Extended silence can cause the duration-based estimator to overestimate output tokens because silent regions produce no transcription tokens.VAD preprocessing could compute d from speech-active segments instead of raw file duration.
  • Adaptive κ: A fixed κ across requests may limit estimation accuracy in multilingual deployments with language-dependent tokenization densities.An adaptive κ is proposed as a future direction.
  • Dynamic policy switching: Production systems could dynamically switch among FCFS, SJF, and HRRN using queue depth, tail-latency percentiles, and starvation indicators.The experiments evaluated each scheduling policy in isolation rather than switching policies at runtime.

6 CONCLUSION

The paper shows that FCFS is limited by variable request durations in ASR serving, while audio duration provides a reliable zero-overhead proxy for job length. Integrating SJF and HRRN into vLLM improves latency on LibriSpeech under high load and workload drift, with HRRN limiting tail-latency degradation.

  • 6 CONCLUSION: Audio duration is a reliable, zero-overhead proxy for job length in encoder–decoder ASR models such as Whisper.This addresses FCFS limitations when request durations vary.
  • 6 CONCLUSION: Up to 73% lower median E2E latency is observed after integrating SJF and HRRN into vLLM on LibriSpeech at high load.The result is reported relative to the FCFS-based serving baseline.
  • 6 CONCLUSION: Up to 93% lower median TTFT is observed on LibriSpeech at high load after integrating SJF and HRRN into vLLM.This is another latency improvement reported for the integrated duration-aware schedulers.
  • 6 CONCLUSION: HRRN bounds tail-latency degradation to at most 24%, while the latency improvements persist under workload drift.The conclusion specifically identifies HRRN as controlling the tail-latency trade-off.

A APPENDIX · A.1 TIME TO FIRST TOKEN ANALYSIS

The appendix analyzes time to first token (TTFT) as a complementary measure that isolates scheduling-driven queue wait before decoding. Across LibriSpeech and synthetic workloads, SJF substantially reduces median TTFT, while HRRN limits P90 degradation relative to SJF.

  • A.1 TIME TO FIRST TOKEN ANALYSIS: TTFT isolates the scheduling decision’s direct impact on queue wait because it measures delay before decoding begins.It complements end-to-end latency by focusing on pre-decoding delay.
  • A.1 TIME TO FIRST TOKEN ANALYSIS: At 20–25 req/s, SJF reduces P50 TTFT by up to 93%, from 4273 ms under FCFS to 296 ms.This demonstrates reduced queueing delay for most requests under heavy load.
  • A.1 TIME TO FIRST TOKEN ANALYSIS: Even at P90, SJF maintains sub-second TTFT up to 15 req/s on LibriSpeech.The result shows that SJF’s queueing benefit extends beyond median requests at moderate load.
  • A.1 TIME TO FIRST TOKEN ANALYSIS: At 25 req/s, HRRN achieves −33% P50 TTFT while limiting P90 TTFT degradation relative to SJF.The corresponding percentage changes are shown in Figure 9.
  • A.1 TIME TO FIRST TOKEN ANALYSIS: On the synthetic split, SJF achieves an 84% P50 TTFT reduction at 25 req/s.This confirms that TTFT improvements are driven by queue reordering rather than exploiting large duration gaps.
  • A.1 TIME TO FIRST TOKEN ANALYSIS: Percentage changes for the synthetic split are reported in Figure 11.The figure accompanies the 25 req/s TTFT result.

A.2 BURST WORKLOAD ANALYSIS

Under an instantaneous burst of 500 ASR requests, duration-aware scheduling still improves latency, though less than under sustained overload. HRRN provides the strongest and most consistent gains while avoiding SJF’s starvation risk, without materially affecting per-token decoding throughput.

  • Burst workload setup: 500 requests arrive simultaneously, creating a worst-case queue with no inter-arrival gaps for scheduler triage.The burst workload uses request rate = ∞ to model sudden production traffic spikes.
  • Burst workload setup: The burst experiment runs whisper-large-v3 on an A100 40 GB over the 500-utterance LibriSpeech test-clean split.Each policy processes the full split as a single burst.
  • Latency results: −9.6% P50 TTFT and −10.7% P50 E2EL are achieved by HRRN, compared with −2.1% P50 TTFT and −3.7% P50 E2EL for SJF versus FCFS.The smaller gains reflect a queue that drains monotonically after all requests arrive.
  • Throughput impact: < 8% variation in TPOT and ITL shows that scheduling overhead does not impair per-token decoding throughput at maximum queue depth.The setting contains 500 concurrent requests.
  • Policy comparison: HRRN consistently outperforms FCFS and SJF because accumulated wait time raises long-waiting requests’ response ratios, preventing starvation.The burst findings identify HRRN as preferable for unpredictable traffic patterns.

A.3 WHISPER-MEDIUM MODEL SCALING

Whisper-Medium reproduces the scheduling findings observed for Whisper-Large-v3 while saturating at a higher throughput because of its smaller model footprint. SJF favors shorter requests and lowers P25 latency, whereas HRRN mitigates the high-load P90 tail cost without retuning.

  • Scaling behavior: Whisper-Medium saturates at ∼21 req/s versus ∼18 req/s for Large-v3, shifting congestion and scheduling pressure to higher absolute rates.The comparison uses the same A100 GPU, LibriSpeech test-clean inputs, Poisson arrivals, and 500 completed requests per rate.
  • Policy behavior: Across 15–25 req/s, SJF achieves the lowest P25 E2EL, while HRRN occupies the middle position in policy ranking.SJF’s advantage reflects benefits for the majority of shorter requests.
  • Policy behavior: At high load, P90 latency reproduces the starvation trade-off, confirming that median-vs-tail tension is structural to priority scheduling rather than model-specific.The same tail cost appears in Whisper-Medium as in Large-v3 findings.
  • Generalization: The proposed policies transfer directly to Whisper-Medium without re-tuning, preserving large P50 gains with a bounded tail cost controlled by HRRN.This qualitative behavior holds across model scales.

A.4 IMPLEMENTATION DETAILS

The implementation integrates duration-aware SJF and HRRN scheduling into vLLM by estimating output tokens from waveform duration and routing that estimate through existing request metadata. It provides objective-specific queueing and preemption logic with selectable policies and no serialization-format changes.

  • Configuration: The policies are integrated into vLLM’s v1 engine through five modified files and approximately 250 lines of code, selected with a single CLI flag.The available options are --scheduling-policy sjf and --scheduling-policy hrrn, with no other configuration changes required.
  • Output token estimation: Waveform duration is converted into estimated output tokens before mel spectrogram extraction and stored in SamplingParams.extra_args.The estimate uses duration_s = len(audio_data) / sample_rate and estimated_output = max(1, int(duration_s * kappa)).
  • Request class: The Request class reads estimated output tokens from extra args, falling back to max tokens when the field is absent.The estimate propagates through SamplingParams.extra_args without modifying the request serialization format.
  • Queue implementations: SJF orders requests by estimated output tokens, arrival time, and request ID using a min-heap, while HRRN recomputes response ratios at each pop.SJF insertion and removal achieve O(log n), whereas HRRN selection costs O(n).
  • Preemption logic: Under memory pressure, SJF evicts the longest job and HRRN evicts the least urgent request according to their respective priority objectives.SJF uses the largest estimated job length, while HRRN uses the lowest current response ratio.
Loading 2603.11273v1…