Cache-Aware Agent-Loop Cost (TurnCost)

Sources#

• Do Theorem Provers Need Theorem-Proving Agents? mini-Lean-agent: A Coding-Agent Baseline for Lean
• The Price Reversal Phenomenon: When Cheaper Reasoning Models Cost More
• TurnCost: Turns, Not Observations: Cache-Aware Loop Engineering for Coding Agents

Summary#

A coding agent's loop is append-only: every turn re-sends everything retained so far plus the newest tool output. Under prefix caching, almost all of that re-sent context is billed at the cached-read rate, and only the newest suffix pays full input price. TurnCost (Pramod Kumar & Raj Kumar Pandey, Penn State, arXiv 2610.15093, 2026-10-10, POVC '26 workshop at ASE 2026, empirical) takes that structure seriously and re-scores 600 published trajectories under it. It reaches four results:

1. Cache-unaware accounting is off by roughly 7×. 98.1–99.0% of input tokens are cache hits, so flat input pricing overstates loop cost by 6.5–7.8× per cell, mean 7.14×, under near-ideal caching.
2. The real constraint on using a cheaper model is the strong model's cached price, not its list price. A closed-form break-even follows, and it is about ten times tighter than list prices suggest.
3. Learned observation reduction ties deterministic truncation on cost, because real observations are small (median 118–286 tokens). The bulk sits on Tool-Output Pruning.
4. Turn count, not observation size, carries the cost variance: R² = 0.844 against 0.040.

The authors call the design of this iterative control loop "loop engineering": context management, model selection, compaction and termination. That is narrower than this wiki's Loop Engineering, which is the practitioner discipline of building the system that prompts the agent. The two meet at the same object, the loop, from the cost side and the workflow side.

The cost model#

Let C_t be the context sent at turn t, o_t the output, and r_t the observation appended after turn t. The loop appends only, so C_t = C_0 + Σ_{j<t}(o_j + r_j): a token added at turn j is paid for again on every later turn. Under prefix caching the cached share at turn t is h_t = C_t − r_{t−1}. Everything except the newest observation is a prefix the backend has already seen, and a radix-tree KV cache (SGLang) reuses it exactly. The same mechanism makes switching models expensive: a new backend shares no prefix with the old one and must prefill the whole context cold.

TurnCost reconstructs per-turn context from the message sequence, tokenizes with o200k_base, counts tool schemas (re-sent every request), and bills reasoning tokens as output without carrying them forward. It uses normalized prices: strong input = 1, cached read = 0.1, weak input = 0.05, summary ratio σ = 0.05. All three are swept.

What "98.6% cached" is and is not. It is a simulated share. It follows from the append-only structure under an ideal cache, not from provider-reported cache hits. The paper names what it leaves out: block-boundary rounding, TTL eviction, and loss of reuse when requests move between backends. Prompt-Cache Economics measures exactly those losses on a production API (ρ ≈ 0.83–0.89). TurnCost's sensitivity ladder is what connects the two numbers. The 7.1× inflation falls to 4.0× at 90% cache efficiency, 2.4× at 75% and 1.45× at 50%. The authors ask that 7.1× always be cited with that caveat.

Flat pricing gets worse as loops get longer#

The inflation rises steadily with trajectory length: 5.33× below 40 turns, then 6.10×, 6.93× and 7.44× across the middle strata, and 7.99× above 130 turns. The longest cell (qwen35/SWE-agent, median 134 turns) inflates most at 7.8×, and the shortest (minimax/OpenHands, 60) least at 6.5× (Figure 2, viewed). The ratio is bounded by the input/cached price ratio (10× at the default tariff) and approaches it as the cached prefix comes to dominate.

This is how the routing literature can report large savings. AgentRouter reports 71.8% cost reduction at 97.3% of frontier quality, but on 4–12-step LangGraph/CrewAI workflows priced from output-token rates only. SWE-Router uses flat per-inference pricing. MTRouter prices from a flat input/output table even though it discusses cache loss under model switching. Short trajectories sit at the far left of the inflation curve, where flat pricing is least wrong, and even there it is wrong by about 5×. AgentDiet does price cached input, and the critique does not apply to it. TRACE-Router reports no token-level cost model, so the paper makes no claim about it. The authors audited these five systems only, not the wider routing literature.

In-band swap vs out-of-band delegation#

There are two ways to use a cheaper model inside the loop. Once caching is priced, they run in opposite directions.

• In-band swapping runs a whole turn on the weak model with the full transcript. The weak model has no cache and pays a cold prefill on all of C_t. It saves money only when p_W^in < p_S^cache, not p_W^in < p_S^in. At the defaults (0.05 < 0.10) it does save: 14.7% at a 200-token threshold, 0.4% at 5,000. But it sits on a knife-edge. A weak model at 20% of the strong model's list price looks like an 80% saving under flat accounting and is a net loss once caching is counted. Profit and loss are a factor of two apart, and list prices give no warning.
• Out-of-band delegation hands the weak model only the observation and inserts a short result into the main transcript. The strong model's cache stays intact and the transcript is shortened permanently, so the saving recurs on every later turn.

Break-even (Eq. 3). Delegating an observation of r_j tokens at turn j into a summary of σr_j pays for itself when

T − j > [p_W^in (1 + e) + p_W^out σ] / [(1 − σ) p_S^cache] → p_W^in / p_S^cache (σ, e → 0)

where e is prompt overhead relative to r_j. Three things are absent from it, and each absence is informative. Observation size is absent: it sets how much a delegation saves, not whether it is worth doing. The strong model's list price is absent, because the comparison is against its cached price, typically a tenth of list. And a poor compressor (large σ) hurts through both numerator and denominator, so the penalty is worse than linear. Worked at $3.00 input / $0.30 cached / $0.15 weak, H = 0.5 turns. The list-price version gives 0.05, understating the threshold 10×.

The data do not follow the formula's optimism. At realistic price ratios Eq. 3 puts break-even under two remaining turns, yet delegation still loses money at conservative thresholds in the two minimax cells (Figure 3, viewed: about −1.5% and −4% at 5,000 tokens). Those are also the two cells with the shortest trajectories. The binding constraint is observation size. Large observations are rare and tend to arrive late, with too few turns left to amortize the call. "If delegation still fails to break even [at that horizon], the price gap is not the problem, and no amount of router tuning will fix it."

Turns carry the variance#

Across all 600 trajectories, on log-log scales:

Adding turn count to a model that already contains observation size raises R² by 0.905. The reverse adds 0.101. By turn-count decile, median turns rise 36 → 168 and median cost rises sevenfold (0.138 → 0.978), while median observation size falls from 655 to 334 tokens. The most expensive trajectories have the most turns and the smallest observations. Cost per turn is comparatively stable (median 0.005, CV 0.28), and cost per observation token less so (CV 0.36).

The authors are explicit that this is association, partly by construction: cost is a sum over turns, so some relationship with T is definitional. They identify two features that are not definitional. The exponent exceeds one (1.23): cost grows faster than turn count because each turn re-reads all earlier ones. And observation size predicts slightly negatively, so the two axes are not two views of one quantity. The positive claim is a pointer. Every technique examined (routing, learned reduction, truncation) acts on the axis carrying 4% of the explained variance, and nobody targets redundant turns directly. Removing a turn removes its cost and every later re-read of it. The authors do not claim turns can be removed at held task success. "Why an agent needs a hundred turns to fix one bug" is left open.

The measured exponent sharpens the "quadratic replay" framing used elsewhere in the wiki (Orchestration Sets Token Economics, Context Lifecycle Management's O(n²) full-append case). Token volume in an append-only loop does grow as O(n²) when per-turn additions are constant. Cache-aware cost over 36–168 turns grows as roughly T^1.23 in this corpus, because every re-read is billed at a tenth of the input price and per-turn additions are not constant. Both statements hold, and they describe different quantities.

Implications the paper draws#

1. Price the cache before optimizing anything. For workloads like these, a saving tuned against list price underdelivers in production by roughly the inflation factor.
2. Use Eq. 3 as a deployment rule. Delegate only when remaining turns exceed p_W^in / p_S^cache.
3. Always compare against a truncation baseline. A method that does not beat deleting the observation is buying quality, not cost, and has to be justified on quality.

Where it sits in the wiki#

• It corroborates the harness-side cost model with trajectory data, but only by simulation. Writer's p_eff = p_in(1 − h(1 − κ)) (Orchestration Sets Token Economics) claims h is set by how the orchestration layer assembles context. TurnCost finds h ≈ 0.98–0.99 for an append-only loop across two open scaffolds, against Writer's single identical-prefix call at 99.9%. Neither is a billed measurement. CAPC's measured ρ ≈ 0.85 is.
• It explains the minimal-harness cost inversion without measuring it. Minimal Harness for Autonomous ML Engineering (Malena)'s single 24h session costs ~6× a thread-resetting harness, "almost all of it cache reads," priced at an assumed 0.1×. TurnCost uses the same 0.1× default, so it cannot confirm that price. What it adds is the structural premise (a never-reset append-only loop is ~98–99% cache-eligible) and the turn-count exponent. The sensitivity ladder also bears on the direction of error, as set out on that page.
• It does not explain Harness Tax: Coding-Agent Cost Multiplies Across Harnesses While Success Barely Moves's gap, and the two fit together. Arena.ai's cleanest pair (Fable 5, Pi vs Claude Code) averages 15.4 vs 15.3 turns at ~2× the cost. Turn count is held fixed there, so the harness tax is a per-turn cost difference: Claude Code's first-call context is over 10× Pi's. TurnCost's decomposition runs within a scaffold-model cell, where cost per turn is comparatively stable (CV 0.28) and turn count varies. Read together, turn count sets cost within a harness, and the size of the re-sent prefix sets it across harnesses at matched turns. Under cache-aware pricing that prefix is billed mostly at the cached rate, so its dollar weight depends on accounting that Arena says matters ("total spending also depends on caching") but does not itemize. At ~15 turns, these rollouts sit where TurnCost finds flat pricing least wrong.

Limitations worth carrying#

• Corpus provenance. nvidia/Open-SWE-Traces was assembled as distillation data and excludes trajectories that hit the iteration limit or were prematurely terminated, plus empty-patch and test-altering runs. This biases the 7.1× conservative (inflation grows with length, and the longest runs are gone). It biases the observation-size tail in an unbounded, adverse direction: an agent re-reading a huge log until it exhausts its budget is exactly what was filtered out.
• Sampling. 150 trajectories per cell, taken as the first rows in file order without shuffling. That is deterministic and reproducible, but it is not a random sample.
• Open-weight models only (Qwen3.5-122B-A10B, Minimax-M2.5) on two open scaffolds (OpenHands, SWE-agent). Frontier proprietary agents may behave differently.
• Tokenizer mismatch. o200k_base is used throughout rather than each model's native tokenizer, so absolute counts may be off by 10–20%.
• Quality is not measured. The truncation/delegation parity is about cost only. AgentDiet's 60% vs 58% pass rate is the only quality evidence cited.
• Cache model is ideal-by-construction. No TTL, block rounding or backend migration. The authors say method comparisons are robust to this and magnitudes are not.

Connections#

• Listed-Price Reversal: the same mechanism across proprietary model pairs. A Shapley attribution of cost gaps on Terminal-Bench 2.0, Cybench and GAIA puts them on turn count and replayed history, with cost super-linear in turns and cheaper-listed models exhausting the message budget more often. It is attribution on benchmark rollouts, not a cache-aware re-scoring, so it does not test the 7.1× figure
• Tool-Catalog Context Cost: the fixed per-call overhead this page's turn-count result makes secondary on long loops. A resident tool catalog is that overhead's largest single component, and moving it off the prefix pays most on short, numerous tasks
• Prompt-Cache Economics: the measured-cache counterpart. CAPC bills a real API and finds ρ ≈ 0.83–0.89. TurnCost simulates an ideal cache over real trajectories and gives the ladder that converts one into the other's inflation factor
• Tool-Output Pruning: the observation-size distribution that bounds every pruner, the editor-echo finding, and truncation/delegation cost parity
• Context Lifecycle Management: the O(n²) full-append cost case, priced with caching that its source dropped by assumption
• Orchestration Sets Token Economics: the same p_eff model reached from the harness side. The guided-truncation result also supports its "reject with guidance, don't silently truncate" offload rule
• Minimal Harness for Autonomous ML Engineering (Malena): the long-session cost inversion, which uses the same assumed 0.1× cache price
• Harness Tax: Coding-Agent Cost Multiplies Across Harnesses While Success Barely Moves: the across-harness complement. At matched turn counts the tax there is per-turn prefix size, while here, within one harness, turn count carries the cost
• Client-Side Agent Optimization: step-level routing priced correctly. The in-band swap break-even is the cache-stickiness term its routing predecessors treat as a static per-model price
• Cost-per-Task Over Cost-per-Token: per-token price as a function of cache state and remaining turns rather than a constant
• Loop Engineering: same name, adjacent meaning. Here it is the cost-side design of the agent's control loop rather than the practitioner's goal loop
• Read-Time Memory Curation (JitMem) — an executor-only token count of the kind this page warns about. JitMem's 50–56% input-token saving over write-time memory leaves out the curator's own per-task call, which reads three full raw trajectories

Open Questions#

• Can redundant turns be removed at held task success? The paper shows turn count carries 84% of log-cost variance, while every published technique targets the 4% axis. No source in the corpus intervenes on turn count directly in a coding agent and reports both cost and resolve rate. The falsifiable form: a turn-reduction policy (a batched-tool-call prompt, a stop rule, a plan-first step) A/B'd on one scaffold and one model, reporting cache-aware cost and pass rate.
• What is the billed cache-read share of a long coding-agent trajectory on a production API? TurnCost's 98.1–99.0% is simulated under an ideal cache, while Prompt-Cache Economics measures ρ ≈ 0.85 at production prefix sizes. If the billed share is near 85%, TurnCost's own ladder puts the flat-pricing error at roughly 3× rather than 7×. Partially answered 2026-10-15 by Do Theorem Provers Need Theorem-Proving Agents? mini-Lean-agent: A Coding-Agent Baseline for Lean (empirical): a mini-SWE-agent loop on Gemini 3.8 Flash through Google AI Studio reports 91.5% of input tokens as cached (69.69M of 76.16M) over 1,091 calls on 12 Lean problems, about 90 calls per trajectory. That falls between the ~85% production measurement and TurnCost's simulated 98–99%. It is one model, short trajectories in a non-SWE task, and the paper does not say whether caching was implicit or explicit. A Lean-tooled harness on the same model caches only 8.7%, so the share is a property of the harness's prompt shape as much as of the provider.
• Does the small-observation distribution (median 118–286 tokens, editor echo the largest per-turn bulk) hold for frontier proprietary agents and for the iteration-limit trajectories the corpus filtered out? The excluded runs are exactly where a heavy log tail would live.

Sources#

• The Price Reversal Phenomenon: When Cheaper Reasoning Models Cost More — Chen, Zhang, He, Stoica, Zaharia & Zou, arXiv 2603.23971 v2 (2026-05-28), empirical: Figure 3 and Appendix E (turns and replayed history drive agentic cost gaps, super-linear in turns). Full treatment and parse warnings at Listed-Price Reversal
• TurnCost: Turns, Not Observations: Cache-Aware Loop Engineering for Coding Agents — Pramod Kumar & Raj Kumar Pandey (The Pennsylvania State University), TurnCost: Turns, Not Observations: Cache-Aware Loop Engineering for Coding Agents, arXiv 2610.15093, 2026-10-10, POVC '26 (1st International Workshop on PromptOps and Vibe Coding, co-located with ASE 2026, Munich; DOI 10.1145/3843779.3844635), 8pp, empirical. No COI: the authors evaluate no product of their own, and TurnCost is an open re-scoring tool (Zenodo 10.5281/zenodo.22216661). Cited: §2.2 and the "scope of our accounting claim" paragraph (which routing papers are cache-unaware); §3 Eqs. 1–3 and the worked example; §4 corpus, reconstruction and default prices; §5.1–5.8; §6; §7. Note that the cost figures are re-scored, not billed: the corpus ships conversations, not token accounting, and the cache share is simulated. Parse notes: Tables 1 and 2 were reconciled against pdftotext -layout on the local PDF and match cell for cell, and their medians, p90s, maxima and mean edit/read sizes agree with the §5.1–5.2 prose. Figures 2 (flat vs cache-aware per cell) and 3 (saving vs delegation threshold) were viewed. The per-cell negative savings (about −1.5% and −4%) are read off Figure 3 and approximate. The affiliation block is welded into a fragment of §1's prose, and that is cosmetic.
• Do Theorem Provers Need Theorem-Proving Agents? mini-Lean-agent: A Coding-Agent Baseline for Lean — Ortega et al. (Princeton / Rutgers), arXiv 2610.17331, 2026-10-12, empirical. Cited for Table 4's provider-recorded cached-input share (91.5% for a bash-only loop vs 8.7% for a module-per-call harness, Gemini 3.8 Flash)