Cost Modeling for Long-Horizon Agentic Tasks
Agentic AI costs grow quadratically, not linearly, as tasks lengthen.
Cost modeling for agentic AI has a math problem, and it's not a rounding error. The standard way people budget for LLM spend, tokens times price, works fine for a single call. It falls apart the moment a system starts reasoning across steps, calling tools, checking its own outputs, and retrying when something goes wrong, because each of those actions triggers another model call, and agentic workflows have been shown to burn through five to thirty times more tokens than a single-pass request for comparable output. The unit that matters has quietly changed. The unit that matters is cost per trajectory, and trajectories don't behave like single calls. The unit that matters is cost per trajectory, and trajectories behave fundamentally differently from single calls.
How context re-billing compounds costs quadratically across agent steps
Every LLM call in an agent loop re-sends the full conversation history, and every provider bills for that history again, in full, every time. This is how the transformer context window works: the model has no memory between calls, so the entire prior exchange, tool outputs and reasoning traces included, gets stuffed back into the prompt and charged again. It's how the transformer context window works: the model has no memory between calls, so the entire prior exchange, tool outputs and reasoning traces included, gets stuffed back into the prompt and charged as input tokens.
Walk through what that does over a real session. The task starts at some baseline context size. Each step appends whatever the agent just did, a search result, a file diff, a chain of reasoning, an error message it's trying to recover from. The input token count for step two is bigger than step one. Step three is bigger still. By step ten, the agent is paying for everything that came before, stacked on top of the new material. It's paying, again, for everything that came before, stacked on top of the new material.
That's why a 20-step loop can eat more than ten times the tokens a naive per-step estimate would predict, a multiplier documented in agentic cost analysis. The cost of any given step is roughly proportional to the sum of everything that happened before it, which makes total cost grow superlinearly with step count, not linearly. In the worst case this behaves like O(N²): double the steps, and cost doesn't double, it roughly quadruples. Anyone budgeting for agent spend by multiplying "average cost per step" by "expected number of steps" is working from a model that's structurally wrong, not just imprecise.
The five formal cost components that make up a long-horizon task bill
A formal decomposition of long-horizon agent cost, laid out in arXiv:2604.11753, breaks total spend into distinct components rather than treating it as one blended number. Three of them carry most of the weight in practice.
Rollout cost covers the LLM inference itself: the incremental input tokens added at each step (excluding cached tokens, since caching repeated context is now standard practice in long-trajectory work) plus the full output tokens generated at each step. This is the component where the quadratic growth described above actually lives, and it's usually the largest line item on the bill.
Tool call cost is priced separately from inference, and it's easy to underweight because it never appears in token counters. Search calls and browse or visit calls have their own per-call rates, distinct from each other. Representative 2026 figures from the same decomposition put search calls at $0.50 per 1,000 queries and visit calls at $0.83 per 1,000. Tool call volume swings just as much as token volume does across a session; it is not a fixed per-task overhead, and treating it as one is a common modeling shortcut that undercounts real spend.
Aggregation cost is the smallest and most conditional of the three. For a simple pipeline, it's zero. Once a system runs parallel rollouts and uses an LLM to combine their outputs into one answer, aggregation cost appears, but for solution aggregation specifically, it's bounded by a single additional LLM call, which is a genuinely useful efficiency property when modeling worst-case spend for parallelized agent designs.
Why pre-task cost prediction is unreliable
Token usage is not just variable across runs of the same task, it's wildly so. Measured runs on identical tasks have shown up to a 30x spread in total token consumption, with the most expensive run on a given problem requiring roughly seven million more tokens than the cheapest run on that same problem. That's a distribution with a long tail, and the tail gets fatter as the task gets harder. That's a distribution with a long tail, and the tail gets fatter as the task gets harder.
The reason ties back to task complexity, and METR's time-horizon research gives the clearest evidence for it. Testing frontier agents across a range of tasks, mostly coding work with some general reasoning problems, spanning results from 2019 through 2025, METR found that the length of a task (measured as how long it takes a skilled human to complete it) correlates strongly with agent success rate, at an R² of 0.83. Frontier models today hit near-100% success on tasks a skilled human finishes in under about four minutes. Pushing the task out to something that takes a human more than roughly four hours drives success rates below 10%.
That reliability curve has a cost consequence that's easy to miss if you're only looking at pass or fail. Tasks sitting in the failure-prone zone fail expensively. They fail after the agent has explored several branches, retried, backtracked, and tried again. The runs most likely to fail are frequently the same runs most likely to have burned the most tokens getting there. Pre-task cost prediction, in other words, is least reliable exactly where the financial stakes are highest.
Where cost models fail in production
Theory is one thing. What actually happened at Uber is another.
Claude Code adoption across Uber's roughly 5,000-engineer organization climbed from 32% to 84% between December 2025 and March 2026. By April, the entire annual AI budget was gone, and monthly API costs had climbed into six figures. CTO Praveen Neppalli Naga said: "I'm back to the drawing board, because the budget I thought I would need is blown away already." The cost model had been built at pilot scale, on a handful of engineers using the tool occasionally. Nobody re-ran the numbers for 84% adoption with engineers running long agentic sessions all day, and the gap between pilot-scale assumption and production-scale reality is what emptied the budget.
A fintech company building a fraud-detection agent hit a different failure mode. In November 2025, the system cost about $5,000 a month running roughly 50 users. By January 2026, at around 500 users, the bill had tripled to $15,000 a month. At higher user counts, the unit economics inverted entirely, cost per user grew rather than shrank with scale, and the economics became untenable. The team's model had priced out cost per task once, correctly, but never modeled how concurrent load, shared context, and rising volume interact. Per-task cost is not a constant when hundreds of sessions are running at once.
The most stark example is a straightforward malfunction. Four agents built with LangChain entered an infinite loop and kept running for eleven days before anyone noticed. The bill came to $47,000. There was no per-session spend ceiling, no loop detection, and no anomaly monitoring in place, so nothing stopped the loop and nothing flagged it until the invoice arrived.
None of this is isolated. Deloitte has documented teams discovering monthly bills in the tens of millions of dollars traced back to agentic loops, and the industry has picked up the term "token tsunamis" for exactly this kind of runaway cost event. Enterprise agent deployments reportedly saw average quarter-on-quarter cost increases of 340% between Q4 2025 and Q1 2026. Different companies, different failure mechanisms, but the same root cause each time: a cost model built for one scale or one execution path, deployed into conditions the model never accounted for.
The modeling primitives practitioners need before a production agent runs
Fixing this starts before the agent ever runs in production, with four modeling primitives that replace the single-number estimate most teams still reach for.
Model step count as a distribution. Given the tail behavior documented above, a fixed "expected number of steps" throws away exactly the information that matters. Estimate the distribution using task complexity, proxied by expected human completion time as in the METR framework, and budget against the 90th percentile of that distribution rather than the median. The blowouts happen in the tail, so budgeting for the middle of the distribution guarantees the model will be wrong when it matters most.
Model the context accumulation curve explicitly. Input token count is a function of step number, and it needs to be modeled as one: account for the size of tool outputs and reasoning traces at each step, and calculate cumulative context cost directly rather than multiplying a single-step cost by the step count (the mistake that produces the quadratic surprise in the first place). Part of this exercise is identifying which context segments repeat across steps and qualify for caching, since excluding cached tokens from the billable count is one of the few levers that meaningfully softens the curve.
Model tool call volume and composition separately from inference cost. Search and visit calls carry different per-call rates, so lumping them into one "tool overhead" number hides real cost variance. Estimate call frequency per step, not as a flat session-level average, and at high step counts, treat tool cost as a first-class component alongside inference rather than an afterthought, since it can become material relative to LLM spend on long trajectories.
Assign model tiers deliberately. Not every step needs a frontier reasoning model; some can run on a smaller, cheaper execution model without loss of quality. The ratio of output cost to input cost runs around 4:1 at the median and considerably higher for premium reasoning models. Planning steps that generate long outputs are disproportionately expensive per token. A mixed-tier architecture needs each tier's contribution to total cost modeled on its own, not blended into one average rate.
Monitoring and controlling spend once agents are running in production
The primitives above help before launch, but the harder shift is the one that happens after: moving from predicting total task cost in advance to inspecting a trajectory's state mid-run and estimating what's left to spend, an approach reflected in emerging mid-trajectory cost estimation work. A prediction made before the first token is generated is a guess. A model that re-evaluates from the trajectory's actual state at step 12 has real information to work with, including exactly the kind of context-length and step-count data described earlier.
Instrumentation has to happen at the session level, and cumulative input tokens matter more here than output tokens, because that's where the quadratic growth first drives up total cost, and monitoring it at the session level gives the earliest warning of a runaway session. Tool call count by type deserves its own line, given how differently search and visit calls are priced.
Set a spend ceiling per session and enforce it automatically. The LangChain incident ran for eleven days specifically because no ceiling existed to stop it, and nothing flagged it until the invoice arrived. A hard cap doesn't require perfect cost prediction to be useful. It only requires that someone decided, in advance, what the maximum acceptable loss on a single session looks like, and built a system that enforces that number rather than trusting a forecast made before the agent took its first step.
