Tail-Aware Scheduling Improves Agentic LLM Workflow Latency

Summary

Agentic LLM workflows alternate model turns with tool interactions, making completion time depend on when ready turns are released as well as inference speed. The paper argues that the common eager-release policy can build up released but unfinished work under contention; after submission, that work cannot be reordered at the workflow level, which can worsen tail latency. It introduces a tail-risk-aware scheduler that jointly selects the next ready turn and controls how much released unfinished work is allowed. The method uses a mean-CVaR objective to represent the changing tail risk of unfinished workflows, online estimates of turn work to prioritize ready turns, and an adaptive released-work budget based on queue pressure. Evaluation on real software-engineering agent traces spans multiple LLMs and workflow arrival rates. Under light load, the method performs comparably to eager release, while under contention it substantially lowers P95 workflow flow time, with a reported speedup of up to 3.50x.