Fallback Chain under a Deadline and Step Budget

mediumPROReliability & Failure HandlingAI AgentsAI Agents 1

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:

Step budget. If the number of attempts already made equals max_steps, stop with status step_budget_exhausted.
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.

Example

Input

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

Output

strong
deadline_exceeded

Reasoning

With a 1000ms deadline, fast is attempted (100ms, fails since it is absent from outcomes), then strong is attempted and succeeds at 500ms total. With a 400ms deadline, fast still costs 100ms, but 100 + 400 = 500 > 400, so the predictive guard blocks strong before it starts.

Constraints

0 <= len(chain) <= 50; latency_ms >= 0; deadline_ms >= 0; max_steps >= 0
Both guards are checked before each attempt, step budget first
The deadline guard is predictive: elapsed + latency_ms > deadline_ms blocks the attempt
A failed attempt still costs its full latency and one step
A provider missing from outcomes is treated as "error"
provider is "" for every non-ok status

Learn this in

The Agent Loop & ReAct FoundationsAgent Engineering Study Plan Multi-Agent Coordination & Failure ModesAgent Engineering Study Plan Multi-Agent Frameworks: AutoGen, CrewAI, OpenAI Agents SDK, Claude Agent SDKAgent Engineering Study Plan Specialized Agents: Computer Use & VoiceAgent Engineering Study Plan

More from AI Agents 1

Cheapest Cache TTL Meeting a Freshness SLAhard Bootstrap Confidence Interval Width for Eval Accuracymedium Route to the Cheapest Model Meeting Qualitymedium pass@k Estimatormedium Savings from a Semantic Cachemedium

Concept primerPREVIEW

1. Background Knowledge

This problem models a fallback chain pattern commonly used in distributed systems and AI agent orchestration to ensure reliability under strict Service Level Objectives (SLOs). In production environments, relying on a single provider is risky; if the primary service fails or is too slow, the system degrades gracefully by attempting secondary, tertiary, or cached options. The core challenge here is managing two distinct resource constraints simultaneously: latency (wall-clock time) and computational steps (number of API calls or attempts).

The concept of a predictive deadline guard is critical. Unlike a simple timeout that interrupts a running process, this guard prevents the initiation of a task if it is mathematically impossible for the task to complete before the deadline. This requires calculating elapsed_ms + latency_ms before the attempt. If this sum exceeds deadline_ms, the system must abort immediately with a deadline_exceeded status, rather than wasting resources on a doomed attempt. This distinction ensures that the elapsed_ms reported reflects only the time spent on completed or started attempts, not hypothetical ones.

Additionally, the problem introduces a step budget, which limits the total number of fallback attempts regardless of time. This prevents infinite loops or excessive costs in scenarios where providers fail repeatedly. The interaction between these two constraints creates a state machine where each transition depends on the current state (elapsed_ms, steps) and the properties of the next provider in the chain. Understanding how to track state mutations (incrementing steps, adding latency) and checking termination conditions at each step is fundamental to solving this.

2. Algorithm Approach

The appropriate algorithmic pattern for this problem is a linear iteration with early termination. Since the fallback chain is ordered and must be tried sequentially, a simple for loop over the chain list is sufficient. The algorithm maintains a running state consisting of elapsed_ms, steps, and a list of attempted providers.

At each iteration, before executing the current provider, the algorithm must perform two guard checks:

Step Budget Check: Verify if steps has reached max_steps. If so, terminate with step_budget_exhausted.
Deadline Check: Verify if elapsed_ms + current_provider.latency_ms exceeds deadline_ms. If so, terminate with deadline_exceeded.

If both guards pass, the provider is "attempted." This involves incrementing steps, adding latency_ms to elapsed_ms, and recording the provider name. Then, the outcomes dictionary is consulted to determine if the attempt succeeded ("ok") or failed ("error" or missing key). A success terminates the loop with status ok. A failure continues to the next iteration. If the loop completes without success or early termination, the status is exhausted.

3. Step-by-Step Strategy

Initialize State Variables:

elapsed_ms = 0
steps = 0
attempted = []
status = "exhausted" (default if the chain runs out)
provider = "" (default if no success)

Iterate Through the Chain:

Loop through each item in the chain list.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.