Fallback Chain under a Deadline and Step Budget

Problem Statement

A production agent never has one way to answer a question - it has a chain: the fast cheap model, then the strong expensive one, then the cached stale answer, then a canned apology. What makes the chain safe is that it runs under two hard limits at once: a wall-clock deadline and a step budget. Without them, a chain of three flaky providers is just three ways to blow your latency SLO.

Background

The chain is tried in order. Before each attempt, both guards are checked:

1. Step budget. If the number of attempts already made equals max_steps, stop with status step_budget_exhausted.
2. Deadline. If elapsed + latency_ms for the next provider would exceed deadline_ms, do not attempt it - stop with status deadline_exceeded. The guard is predictive: you never start a call you already know cannot finish in time.

If both guards pass, the provider is attempted: it costs its full latency_ms and one step whether it succeeds or fails. A success ends the run with status ok. A failure moves to the next provider. Running off the end of the chain is status exhausted.

Your Task

Implement:

def execute_with_fallback(chain, outcomes, deadline_ms, max_steps):

• chain: ordered list of {"name": str, "latency_ms": int}.
• outcomes: dict of provider name -> "ok" or "error". A name missing from the dict counts as "error".

Return a dict with:

• status: "ok", "deadline_exceeded", "step_budget_exhausted" or "exhausted"
• provider: the winning provider's name, or "" when there is none
• elapsed_ms: total milliseconds consumed by attempts actually made
• steps: number of attempts actually made
• attempted: the provider names attempted, in order

Input/Output Format

Returns the five-key dict above. All the numbers are ints - nothing here is floating point.

Sample

chain = [{"name": "fast", "latency_ms": 100}, {"name": "strong", "latency_ms": 400}]
print(execute_with_fallback(chain, {"strong": "ok"}, 1000, 5)["provider"])   # strong
print(execute_with_fallback(chain, {"strong": "ok"}, 400, 5)["status"])      # deadline_exceeded

In the second call fast fails after 100ms, and 100 + 400 > 400, so strong is never started.