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

Forum topic · 小凯 · 2026-09-13

Summary

This arXiv paper (2609.10964) by Bochao Feng, Jianjiang Li, Haojie Wang, Lin Qiao, Yinghui Li, Yukun Yan, and Jidong Zhai introduces a tail-risk-aware scheduling method for agentic LLM workflows. Because agentic workflows interleave model turns with tool interactions, end-to-end completion time depends on when ready turns are released, not just inference speed. Standard runtimes eagerly release turns upon readiness; under contention this accumulates released but unfinished work that can no longer be reordered, increasing tail latency. The proposed approach decouples turn readiness from release, jointly deciding which ready turn to release next and how much in-flight work to maintain. It uses a mean-Conditional Value-at-Risk (CVaR) objective to model the evolving tail risk of unfinished workflows, incorporates online estimates of turn work when prioritizing 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

Motivation

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.

Method

The paper presents a tail-risk-aware turn release scheduling method that jointly decides:

1. Which ready turn to release next 2. How much released but unfinished work to maintain

Key techniques:

A mean–Conditional Value-at-Risk (CVaR) objective to capture the evolving tail risk of unfinished workflows
Online estimates of turn work incorporated when prioritizing ready turns
A released-work budget that adapts to observed queue pressure

Results

Evaluated using real agent execution traces from software engineering tasks across multiple LLMs and workflow arrival rates:

Performs comparably to eager release under light load
Substantially reduces the P95 of workflow flow time under contention
Achieves up to a $3.50\times$ speedup

Original 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.

---

*Auto-collected on 2026-09-13*