Decoupling Readiness from Release: Tail-Aware Scheduling for Agentic LLM Workflows

Forum topic · 小凯 · 2026-09-13

Summary

Agentic LLM workflows interleave model turns with tool interactions, so end-to-end completion time depends not only on inference speed but also on when ready turns are released. Most runtimes eagerly release each turn upon readiness; under contention this accumulates released but unfinished work that can no longer be reordered, inflating tail latency. This paper (arXiv:2609.10964) proposes a tail-risk-aware turn release scheduling method that jointly decides which ready turn to release next and how much released-but-unfinished work to maintain. It uses a mean-Conditional Value-at-Risk (CVaR) objective to capture the evolving tail risk of unfinished workflows, incorporates online estimates of turn work when prioritizing ready turns, and adapts the released-work budget to observed queue pressure. Evaluated on real agent execution traces from software engineering tasks across multiple LLMs and arrival rates, the method matches eager release under light load and substantially reduces the P95 of workflow flow time under contention, achieving up to 3.50x speedup.

Paper Overview

Research areas: cs.AI, cs.SE
Authors: Bochao Feng, Jianjiang Li, Haojie Wang, Lin Qiao, Yinghui Li, Yukun Yan, Jidong Zhai
Published: 2026-09-13
arXiv: 2609.10964

Key Points

Agentic LLM workflows interleave model turns with tool interactions; end-to-end completion time depends on both inference speed and when ready turns are released.
Most runtimes release turns eagerly upon readiness. Under contention, this accumulates released-but-unfinished work that workflow-level policies can no longer reorder, increasing tail latency.
The proposed method is a tail-risk-aware turn release scheduler that jointly decides which ready turn to release next and how much released-but-unfinished work to maintain.
It uses a mean-Conditional Value-at-Risk (CVaR) objective to capture the evolving tail risk of unfinished workflows.
It incorporates online estimates of turn work when prioritizing ready turns and adapts the released-work budget to observed queue pressure.
Evaluated on real agent execution traces from software engineering tasks across multiple LLMs and workflow arrival rates.
Results: comparable to eager release under light load; substantially reduces P95 of workflow flow time under contention, with up to a $3.50\times$ speedup.

Abstract

Agentic LLM workflows consist of sequences of model turns interleaved with tool interactions, so their end-to-end completion time depends not only on inference speed but also on when ready turns are released. Most runtimes release each turn immediately upon readiness. Under contention, this eager release policy can accumulate released but unfinished work; once submitted, those turns can no longer be reordered by the workflow-level policy, increasing tail latency. We present a tail-risk-aware turn release scheduling method that jointly decides which ready turn to release next and how much released but unfinished work to maintain. The method uses a mean--Conditional Value-at-Risk (CVaR) objective to capture the evolving tail risk of unfinished workflows, incorporates online estimates of turn work when prioritizing ready turns, and adapts the released work budget to observed queue pressure. We evaluate the method using real agent execution traces from software engineering tasks across multiple LLMs and workflow arrival rates. The method performs comparably to eager release under light load and substantially reduces the P95 of workflow flow time under contention, achieving up to a

3.50\times

speedup.