A Deadline That Propagates Through Every Tool Call in a Run

The header should carry the number of milliseconds remaining, not a wall clock instant. This is not a stylistic choice; it is the same decision gRPC made for its own deadline propagation. Because a deadline is a point in time, forwarding it unchanged between servers is problematic when their clocks are not synchronized, so gRPC converts the deadline into a timeout with the elapsed time already deducted (gRPC deadlines guide). The wire format is the remaining duration.

A practitioner asking whether to propagate absolute deadlines anyway, on the argument that NTP keeps clocks within a few milliseconds, got the practical answer when designing the workaround: the standard mechanism is relative precisely so nobody has to reason about skew (grpc-java issue 11966). Your agent and your tools may run in different regions, on different container runtimes, or on a laptop with a sleeping clock. A millisecond count is invariant to all of that.

The unit matters too. Milliseconds keep the arithmetic integral and avoid floating point drift in logs. If you want a second header for humans, make it derived and never authoritative.

The propagation logic belongs in one place: a wrapper that sits between the model's tool decision and the actual HTTP or RPC call. It reads the run's absolute end time from the execution context, computes the difference against the clock, and writes the header. Because it recomputes each time, the value can only fall.

import time

HEADER = "X-Run-Deadline-Ms"
MIN_USEFUL_MS = 150  # below this, networking alone likely eats the budget

class RunContext:
    def __init__(self, end_time_monotonic: float):
        self.end_time = end_time_monotonic

    def remaining_ms(self) -> int:
        return max(0, int((self.end_time - time.monotonic()) * 1000))

def call_tool(client, run: RunContext, name: str, payload: dict):
    remaining = run.remaining_ms()
    if remaining < MIN_USEFUL_MS:
        raise BudgetExhausted(name, remaining)
    resp = client.post(
        f"/tools/{name}",
        json=payload,
        headers={HEADER: str(remaining)},
        timeout=remaining / 1000,
    )
    resp.raise_for_status()
    return resp.json()

Two details are load-bearing. First, time.monotonic() is used rather than wall clock time, so a clock adjustment mid-run cannot inflate the budget. Second, the client-side transport timeout is set from the same number as the header, so the header never claims more time than the client is willing to wait. That consistency is what stops a tool from working past the point where anyone is listening.

If the agent makes several tool calls in parallel for one step, compute the header once for the batch rather than per call, otherwise calls started later in the fan-out get a slightly smaller budget than their siblings for no reason. For sequential calls, recompute every time.

The tool is the only party that knows how long it usually takes. A search index, a PDF renderer, and a payment authorization have completely different duration distributions, and the tail is what matters. Averages hide exactly the requests that hurt: a service averaging 100 ms can still have a meaningful share of requests taking seconds, and the slow tail clusters around connection pool exhaustion, garbage collection pauses, and slow dependencies (Redis). Gating on an average would let the agent start work that the tail will overrun.

So the server checks the header against a percentile of its own recent durations, not a mean. The p99 latency definition is simple: 99 percent of requests finish within that value, and only the top 1 percent take longer (Aerospike). If the remaining budget is smaller than your p99 duration, refusing is honest.

P99_LOOKALIKE_MS = 1400  # read from your own latency histogram, not a guess

def require_budget(request):
    raw = request.headers.get("X-Run-Deadline-Ms")
    if raw is None:
        raise Refused(400, "missing_deadline", "X-Run-Deadline-Ms is required")
    remaining = int(raw)
    if remaining < P99_LOOKALIKE_MS:
        raise Refused(449, "insufficient_budget",
                      f"need {P99_LOOKALIKE_MS} ms, got {remaining}")
    return remaining

The refusal should be a distinct, typed signal, not a generic 500. A 4xx-family response with a machine-readable code lets the agent branch: try the cheap fallback, skip the step, or tell the user the run cannot complete. It also keeps the refusal out of your error budget, because it is a correct outcome rather than a failure. Compare this with how APIs expose pressure already: Monday's rate limit docs return named error codes like COMPLEXITY_BUDGET_EXHAUSTED so callers can react specifically rather than parsing prose (monday.com rate limits). Deadline refusal deserves the same treatment.

One subtlety: the p99 you compare against must be per tool and per input class. A tool that renders a single page and a tool that renders a 400-page batch should not share a threshold. If you only have a global number, treat it as a floor and add per-tool overrides where you have measured them.

The hard case is a tool that calls another tool. An agent calls a "research" tool, which calls a search API, which calls an embeddings service. Each hop must shrink the budget, and none may grow it.

The rule is the same one gRPC applies inside a single call chain: a downstream service cannot extend a deadline set by the caller, and when the deadline expires, cancellation propagates to in-flight calls (oneuptime gRPC deadlines). Implement it as an invariant rather than a convention:

• On entry, read the header and immediately subtract your own measured start-up cost.
• Before every outbound call, recompute the remaining budget from your own monotonic clock and forward it.
• Never send a value larger than the one you received, even if your local estimate says you have more time.
• If the arithmetic yields a value below your own minimum, stop and return the refusal upward.

That third rule is what makes the contract test in the next section possible: it gives you a property to assert. It also prevents a common bug where a tool with a generous internal timeout resets the budget for its children because it forgot where the number came from.

Worked example with numbers. A run starts with 5,000 ms. The agent's planning step takes 600 ms, so the first tool call carries 4,400. That tool spends 250 ms of its own setup and then calls a nested search, so it forwards 4,150. The search tool measures that its p99 is 3,900 ms, which fits, so it runs and returns at 3,000 ms, leaving 1,150. The agent's next tool call carries 1,150. That tool's p99 is 1,400, so it refuses with insufficient_budget and reports 1,150. The agent skips it and finishes the run with 800 ms to spare. Every number in that trace came from a clock subtraction, and none of it required the machines to agree on what time it is.

The property you want to test is monotonic non-increase across the whole fan-out, plus correct refusal at the boundary. Write it against the middleware and a stub tool server, not against the real model, so it runs in milliseconds.

def test_deadline_contract():
    run = RunContext(end_time_monotonic=time.monotonic() + 2.0)
    seen = []

    def record(headers):
        seen.append(int(headers["X-Run-Deadline-Ms"]))
        return {"ok": True}

    call_tool(StubClient(record), run, "first", {})
    time.sleep(0.2)
    call_tool(StubClient(record), run, "second", {})

    assert seen, "header was never sent"
    assert all(b <= a for a, b in zip(seen, seen[1:])), seen

Three assertions carry the weight:

1. Header presence. The stub records every request and the test fails if any lacks X-Run-Deadline-Ms. This catches the client path that bypassed middleware, which is the usual regression.
2. Monotonic non-increase. Sorted pairwise comparison over the recorded values. Equality is allowed when two calls happen in the same millisecond; growth never is.
3. Refusal below the minimum. Configure the stub to require 1,000 ms, give the run 500 ms, and assert the typed insufficient_budget error. Assert the status code and the code string, not the message text.

Add a fourth test that is easy to forget: a nested case. Have the stub tool itself call a second stub and assert the grandchild's header is less than or equal to the parent's. That is where propagation bugs hide, because the outer middleware is correct while the inner call re-reads a configuration value.

Run these in CI on every change to the tool wrapper. They are cheap, deterministic, and they encode the decision rule the rest of the system depends on.

The minimum is the number below which a call is pure waste. It should reflect the fastest possible useful answer from that tool: connection setup plus the smallest meaningful unit of work. A search over a small index might be genuinely useful at 200 ms; a document conversion is not useful at any budget, because a half-converted file is worse than none.

Derive it from two inputs you already have. First, your own p95 or p99 duration from a latency histogram; percentiles describe the shape of the distribution, which is why serious performance reporting leads with p95 and p99 rather than the mean (qaskills.sh). Second, the false-timeout rate the product can tolerate, which is the method AWS recommends for picking internal call timeouts: choose an acceptable rate of false timeouts and read the latency value off the distribution at that percentile (System Design Academy).

Note the last row. For anything with an externally visible side effect, the deadline check is not enough on its own; the retry needs an idempotency key so a timeout followed by a retry cannot charge twice (System Design Academy). The budget decides whether to start; the idempotency key decides whether it is safe to try again.

Header recomputed from wall clock. Symptoms: budgets that grow between calls after an NTP correction, and refusals that appear and disappear on a schedule. Fix: monotonic clock only.

Budget reset at a nested hop. Symptoms: deep tool chains run past the run deadline and the agent gets a success after it has already given up. Fix: the nested contract test, plus a rule that no hop may forward a larger value than it received.

Refusal returned as a 500. Symptoms: refusal spikes show up in error-rate dashboards and page someone, and the agent retries a call that is guaranteed to fail again. Fix: distinct status and code, excluded from error budgets.

Minimum set from the average. Symptoms: roughly half of admitted calls time out at the transport layer under load. Fix: set the minimum from a high percentile.

Timeout and budget disagree. Symptoms: the client gives up before the header says the budget is spent, so the tool keeps working on a result nobody will read. This is the zombie request pattern, where downstream services burn CPU on a result that will never be seen (dev.to). Fix: derive the transport timeout from the same number you put in the header.

Blocking long tool calls makes all of these worse, because a stalled call holds the execution thread and stalling turns into timeouts, missed responses, and duplicated retries (NHI Management Group). If a tool genuinely needs minutes, hand it off and have it report back with a task identifier rather than keeping the run open with a shrinking budget.

If your runs span several model providers, keeping the budget logic identical across them is easier when the call path is uniform. Quanta Inference exposes text, image, video, audio and embedding models through one OpenAI-compatible API, which means one middleware layer and one header convention covers every tool that wraps a model call (Quanta Intelligence).