Plan Cost Estimation Failure
Issue
An agent estimates the time, money, compute, or API-call cost a plan will require before executing it, but the estimate is badly wrong — often by an order of magnitude — because the estimation step relies on a shallow heuristic (counting plan steps, or a flat per-step assumption) rather than reasoning about the actual work each step entails. Downstream systems that make decisions based on that estimate (budget approval, scheduling, user-facing time expectations) are then working from a number that bears little relation to reality.
Frequency: Common
Symptoms
- Actual execution cost or duration exceeding the pre-execution estimate by a large multiple
- Estimates that scale linearly with plan step count regardless of what each step actually does
- Budget or time-box approvals granted based on the estimate, then breached partway through execution
- Estimates that don’t account for steps with data-dependent cost (e.g. “process all matching records,” where the count is unknown until execution)
- Wide variance between estimated and actual cost correlating specifically with steps involving loops, external API calls, or unbounded search
Root Cause
Cost estimation for a plan generated by an LLM is typically done by the same or a similar shallow reasoning process that generated the plan itself, without access to real historical execution data for similar steps. It commonly defaults to treating each step as roughly equal cost, or extrapolating from a single example, because the planner has no visibility into data-dependent factors that only become known during execution — how many records match a filter, how many pages a search will need to traverse, how many retries an unreliable API will require. Without a feedback loop from actual past executions of similar steps back into the estimation logic, the estimate is essentially a guess dressed up as a number, and it never improves because it’s never compared against ground truth after the fact.
Example
A data-migration agent is asked to "clean and reformat all customer
records in the legacy database" and estimates the task at 15 minutes,
based on treating it as a single "transform records" step similar in
estimated cost to other single steps in its plan.
The estimate doesn't account for:
- The actual record count (1.4 million, not sampled or checked before
estimating)
- Each record requiring 2 external API calls to a data-enrichment
service for address validation (rate-limited to 10 req/sec)
- A retry rate of roughly 8% on the enrichment API under load
Actual cost: 1.4M records x 2 calls = 2.8M calls, at a sustained 10
req/sec ceiling, plus retry overhead, works out to roughly 80+ hours of
wall-clock time -- not 15 minutes. The task was approved for a 30-minute
maintenance window based on the estimate, was still running when the
window closed, and had to be interrupted mid-migration, leaving a subset
of records only partially reformatted.
Statistics
| Finding | Context |
|---|---|
| Plan cost estimates generated without reference to per-step historical execution data are estimated to be off by 5-10x or more on tasks involving data-dependent loops | Typical range observed in agent execution retrospectives |
| Estimation accuracy is reported to improve substantially when the planner has access to actual cost/duration data from prior executions of similar step types | Reported range across teams that added historical-cost lookup to planning |
| Tasks with unbounded or unknown-cardinality inputs (e.g. “all matching records”) show disproportionately higher estimate-to-actual variance than tasks with fixed, known inputs | Estimated from comparison of estimate accuracy across task types |
Mitigations
- Cardinality checks before estimation: For any step whose cost scales with a data volume (record counts, page counts, search result counts), require a cheap preliminary check of that volume before finalizing the cost estimate, rather than assuming a fixed or average size.
- Historical cost lookup: Maintain a running log of actual cost/duration per step type and use it to inform new estimates, rather than generating each estimate from first-principles reasoning with no ground truth.
- Confidence intervals over point estimates: Produce cost estimates as a range with explicit uncertainty (e.g. “15-90 minutes depending on record count”) rather than a single number, so downstream approval processes can account for the uncertainty rather than treating the estimate as precise.
- Mid-execution re-estimation: Re-forecast remaining cost partway through execution once actual per-unit cost is observable (e.g. after the first 1,000 of 1.4M records), and surface a revised estimate before continuing rather than only estimating once up front.
- Post-execution estimate-vs-actual tracking: Systematically compare every estimate against its actual outcome and feed the delta back into the estimation model, closing the loop that’s otherwise absent.
Production Signals
Key Metrics
| Metric | Description | Alert Threshold |
|---|---|---|
| estimate_actual_variance_ratio | Ratio of actual to estimated cost/duration across completed tasks | Alert if median > 2x or < 0.5x |
| unbounded_input_estimate_rate | Fraction of plans with data-dependent steps that proceed to execution without a preliminary cardinality check | Alert if > 20% |
| budget_breach_after_approval_rate | Fraction of tasks that exceed their pre-approved budget/time-box after being approved based on the estimate | Alert if > 10% |
Alerts
| Alert | Condition | Severity | Response |
|---|---|---|---|
| Estimate grossly exceeded mid-execution | Actual cost/duration on-track to exceed the original estimate by a large multiple before task completion | High | Pause execution, re-estimate, seek re-approval if over budget threshold |
| Unbounded step proceeding without cardinality check | A step whose cost scales with data volume begins execution with no preliminary size check logged | Medium | Flag for planning-process review |
Related Patterns
- Plan Optimization Pathological - both stem from the planner’s cost model not matching real-world cost, one producing bad estimates and the other producing bad optimization targets
- Plan Hallucination Detection Failure - an estimate built on a hallucinated step inherits that step’s fabricated (and therefore meaningless) cost figure
- Plan Parallelization Error - inaccurate per-step cost estimates commonly feed into incorrect parallelization decisions, since parallelizability judgments often rely on assumed step cost