Patient.
schedule the workflow, not the token
a reliability-budgeted scheduler for agentic LLM workflows · Hannah B. Pasandi, UC Berkeley Sky Computing Lab
in plain terms

When an agent works on a task, nobody is waiting on the next token; the human waits on the finished workflow, minutes later. Patient gives the gateway an explicit budget for the bytes agents spend proving their answers right, verification, retries, judging, and spends that budget deliberately instead of treating it as waste.

the idea

Latency is the wrong axis for agent workflows

Serving stacks optimize time-to-first-token and per-request latency, but agent workflows complete in minutes and the person waits on the final answer, not on any token. The unit the scheduler optimizes and the unit the user experiences have diverged. Worse, the traffic that looks most expendable, retries, verifier calls, judge calls, is the application enforcing correctness.

Wrong clock. Shaving the next token barely moves a workflow whose completion time sits around a minute and above. Reliability spend, unnamed. Verification and retry bytes are correctness spend, but no scheduler sees them as a quantity to manage.
the budget

Name the correctness spend, in bytes

The reliability budget is the maximum number of bytes the network will spend on verification, retry, and judge calls before a workflow completes or is declared failed. It is declared by the application per workflow and enforced by the gateway.

Bytes, not calls. One long-context verifier call can cost more than ten short generator calls; bytes are what the gateway can meter and what composes across stages. Two headers. The whole contract is X-Workflow-Id and X-Reliability-Budget on requests the gateway already sees.
three rules

Three rules at the gateway, one guarantee

agent workflow stages + verifiers Patient gateway 1 · budget guard: never exceed B 2 · blocking verifiers first 3 · version-pinned, load-aware routing generators verifiers reliable completion
Rule 1, budget guard. Decline any stage that would exceed the declared budget; degrade loudly and escalate per contract, never silently. Rule 2, dependency priority. Schedule blocking verifiers first: a late verifier strands the next generator behind budget exhaustion. Rule 3, version-pinned routing. Shortest queue, but keep a retry on the model version the verifier actually judged.

Applied in order at each decision, the rules carry a (1+ε) competitive bound on reliable completion against an offline oracle, under stated assumptions. When the budget is mis-sized, Patient degrades to the budget guard rather than losing the guarantee silently.

evaluation

4,000 workflows, three benchmarks, five schedulers

On a calibrated emulation of 4,000 workflows across SWE-bench, WebArena, and BFCL, Patient raises reliable completion over default routing, join-the-shortest-queue, an ABR-style controller, and Niyama-Sarathi, with the widest margin on SWE-bench, the most verification-heavy workload, at comparable completion time. Software-engineering workflows spend close to half their bytes on verification, which is exactly the spend Patient manages.

status

Patient is in revision (R2) at SoCC '26. Implementation is about 700 lines of Go as an MCP gateway plug-in; the contract is two HTTP headers, no kernel or serving-engine changes.

in the stack

Patient is the scheduling primitive of AgenticStack

In the AgenticStack agenda, Single-Call Fallacy sets the unit of accounting (the plan), Patient spends a reliability budget at the gateway, and Confine measures where to spend it: per-mode reliability on the signal the router consumes.

Retries and verifier calls are not waste to suppress; they are the application enforcing correctness. Give them a budget and spend it deliberately.

← back to AgenticStack