Timeout Budget Split Across Sequential Steps

mediumPROReliability & Failure HandlingAI AgentsAI Agents 1

Problem Statement

An agent plan runs steps sequentially under one overall timeout. Assign each step a per-step timeout proportional to its expected cost, but never below a floor, and report whether the plan fits.

Background

Given a total budget and per-step expected costs costs, the naive split gives step i a share budget * costs[i] / sum(costs). To avoid starving cheap steps, each allocation is raised to at least floor seconds. Because flooring can push the sum over budget, the plan is feasible only if sum(max(share_i, floor)) <= budget. Report each allocation (rounded to 4 decimals) and feasibility.

Your Task

def split_timeout(costs, budget, floor):

Return a dict {"allocations": [...], "feasible": bool}, allocations rounded to 4 decimals.

Input Format

costs (list of positive floats), budget (float), floor (float).

Output Format

A dict with "allocations" (list of floats) and "feasible" (bool).

Sample

print(split_timeout([1.0, 3.0], 8.0, 0.5))

Output:

{'allocations': [2.0, 6.0], 'feasible': True}

Example

Input

print(split_timeout([1.0, 3.0], 8.0, 0.5))

Output

{'allocations': [2.0, 6.0], 'feasible': True}

Reasoning

Calculate the total expected cost to determine proportional weights: $\text{total} = 1.0 + 3.0 = 4.0$ .
Compute the raw proportional share for each step using the formula $\text{share}_i = \text{budget} \times \frac{\text{cost}_i}{\text{total}}$ $share_{i} = budget \times \frac{cost _{i}}{total}$ :
- Step 1: $8.0 \times \frac{1.0}{4.0} = 2.0$
- Step 2: $8.0 \times \frac{3.0}{4.0} = 6.0$
Apply the minimum floor constraint by taking the maximum of the raw share and the floor value ( $0.5$ $0.5$ ):
- Step 1: $\max(2.0, 0.5) = 2.0$
- Step 2: $\max(6.0, 0.5) = 6.0$
Check feasibility by summing the final allocations and comparing to the budget: $2.0 + 6.0 = 8.0$ , which is $\le 8.0$ , so the plan is feasible.
The final output is {'allocations': [2.0, 6.0], 'feasible': True}

Constraints

Share is budget * costs[i] / sum(costs), then raised to floor.
feasible is sum(allocations) <= budget (use a small tolerance).
Round allocations to 4 decimals; costs is non-empty with positive sum.

Learn this in

Multi-Agent Coordination & Failure ModesAgent Engineering Study Plan Production: Observability, Benchmarks, Runtimes & Eval-Driven DevelopmentAgent Engineering Study Plan Workflow Patterns & LangGraph Stateful GraphsAgent 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 resource allocation under constraints, a core concept in systems design and AI agent planning. When an agent executes a sequence of steps (e.g., API calls, tool invocations), each step consumes time. A global timeout budget must be distributed across steps so that no single step monopolizes the entire window, yet no step is starved of the minimum time it needs to complete.

The allocation strategy here is proportional allocation with a floor constraint. Without the floor, step $i$ would receive $\text{share}_i = \text{budget} \times \frac{\text{costs}[i]}{\sum \text{costs}}$ . This ensures that steps with higher expected costs get more time. However, if a step has a very small cost relative to others, its proportional share might be unreasonably small (e.g., 0.01 seconds), making it impossible to complete. The floor guarantees a minimum allocation: $\text{alloc}_i = \max(\text{share}_i, \text{floor})$ .

The critical insight is that applying the floor can violate the budget constraint. If many steps hit the floor, the sum of allocations may exceed the total budget. In that case, the plan is infeasible—the agent cannot guarantee all steps will complete within the timeout. Feasibility is thus a binary check: does $\sum \text{alloc}_i \leq \text{budget}$ ?

2. Algorithm Approach

This is a deterministic allocation with feasibility check problem. The approach is:

Compute the proportional share for each step based on its cost relative to total cost.
Apply the floor constraint by taking the maximum of the share and the floor value.
Sum all allocations and compare against the budget to determine feasibility.
Return the rounded allocations and the feasibility flag.

No iterative adjustment or optimization is needed—the allocation rule is fixed, and feasibility is a simple comparison.

3. Step-by-Step Strategy

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.