acceptodds
Under review as a conference paper at ICLR 2027

Harnessing LLMs as Agents: What Does It Cost?

Abstract

Language-model agents increasingly rely on harnesses that manage bounded context, persistent memory, tools, verification, and repeated execution, yet existing notions of model capability do not capture the computational resources these mechanisms consume. We study these costs through the *Language Model Agent Machine* (LAM), a resource-bounded model that fixes the underlying semantic model while explicitly accounting for harness-level resources. Our theory yields four main results: **Communication:** LAM execution is instancewise equivalent to red–blue pebbling under joint call–transfer budgets, characterizing the discrete resource frontier and transferring classical I/O lower bounds to context–memory traffic. **Access:** memory interfaces can change asymptotic cost, including a separation between random and non-speculative sequential access for pointer chasing and an exact frontier for single-stack FIFO access. **Recomputation:** bit-reversal DAGs require model calls with context capacity and persistent-memory capacity , quantifying when stored intermediate state avoids repeated semantic computation. **Reliability:** we derive tight stage-local sampling bounds, exact imperfect-verification costs, and a Young–Daly-type checkpoint law with a closed-form optimal verification interval. Controlled and held-out experiments on GPT-6 Astra compare these predictions with observed measurements, including checkpoint optima and a held-out policy-selection tournament conditioned on a programmatic segment check. Held-out chained MATH further illustrates the tradeoff between whole-task call granularity, logical input traffic, and reliability, while prescribed-schedule runs are reported separately as implementation checks. Together, these results provide a resource theory for the computational cost of language-model agent harnesses. Project page: https://anonymous1776research.github.io/LAM-ICLR2027/.

Primary area:
foundation or frontier models, including LLMs
Keywords:
language model agents, agentic systems, computational complexity, resource-bounded computation, external memory, memory access, communication complexity, reliability, verification, query complexity

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_kn2rOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

Language agent model (LAM) is an abstract model of an agent's harness that treats the model as a block box and is designed to study the harness controls: the model calls, the contents of context and external memory (including movements between the two), and tool calls. The paper aims to provide a resource theory of LLM agent harnesses, showing that by keeping the model capability fixed, the harness costs can be bound, compared, and optimized. The authors show an equivalence of harness execution with red-blue pebbling, the type of memory access changes asymptomatic cost, and a characterization of how storage is traded for model calls.

Critical strengths

(S1) Studying the harness in agent systems is an important and timely endeavor.

(S2) The proofs seem correct and careful (although several are fairly obvious — see W2 below).

Critical weaknesses

(W1) The language agent model seems to be heavily inspired by Andrej Karpathy's LLM OS from late 2023 and MemGPT. The paper does not add new architectural insight outside of the counters and theorems over those counters. However, the LAM seems to me like it counts the wrong things: its cost units are not the same units as that which agent systems are typically bill or timed in. There is no relationship with prefix caching, input/output/reasoning tokens, or latency. This leads me to wonder what concrete design decisions the LAM actually changes compared to actual deployed systems. What is an example of a result the theoretical model gives us that could not have been obtained through measurement alone?

(W2) I am not a theoretician, but several theorem appear either true by construction or fairly obvious. I do not mean the fancy theorems such as, e.g., 3 and 6 (which seem to be restatements of classical results in the LAM context), but even the first two theorems hardly feel like they prove anything. For example, theorem 1 argues that harness == red-blue pebbling, which basically derives trivially from the definition, while theorem 2 just leaves the algorithm zero freedom, which means the bound is necessarily the expected distance between consecutive cells on a random permutation. Please let me know if I am misreading the intent, but this seems fairly expected and unsurprising. I think the paper could avoid leaving readers with this impression by explaining what surprising results would interest a practitioner or change a design decision.

(W3) How does the model account for code that is model-generated that itself issues model calls (for example, CodeACT or recursive language model harnesses)? This design is more and more common in real systems, yet it does not seem to map cleanly to the proposed model. If I understand correctly, modeling this case as a tool would mean that nested calls would loop lose access to memory, whereas modeling it as controller logic would not work due to finiteness. What happens if the control flow is generated by the LLM itself?

(W4) Several pieces of related work in the space of context window and its relationship to memory/IO pages are uncited and should have been included in the related work survey. Mainen 2026, “The Library Theorem” and Rafique 2026, “ClawVM” come to mind. A quick search also turned up this paper Meyerson et al. 2025, “MAKER” which seems highly relevant. It seems a proper survey of the related work would likely show that the claims of presenting a “new resource theory” is too strong and should be revised.

(W5) The paper is fairly hard to approach. Terminology is consistent but sentences are overly verbose and technically-loaded. Here is an example among many, appearing on page 2: "Using value provenance, we quotient block occurrences by computational origin and prove an instancewise, resource- reserving correspondence: for every L-realisable DAG, memory- nitialized vertex-granular LAM evaluations and red–blue pebblings have exactly the same feasible call–transfer budgets.” You have managed to pack 8 or 9 technical terms to say what you could have said in plain English: if a model call computes one step of the task, the harness run is a red-blue pebble game.

(Minor) The appendix is EXCESSIVELY long for such a paper. I am honestly not sure most of it adds much value.

Questions for authors

Please see my review for the details.

(Q1) What is an example of a result LAM gives us that could not have been obtained through measurement alone?

(Q2) How do you deal with code that the model generates which itself calls the model?

(Q3) Please compare LAM with missing related work, in particular Mainen and Meyerson et al.

6 comments
AuthorsOpenReview ↗

Response to Reviewer kn2r (part 1/6)

We thank you for recognizing the importance of studying harness costs and for the careful comments on our proofs, scope, and presentation. We have revised the paper to address these concerns.

W1. Architectural precedents, deployment costs, and design choices.

  1. About architectural precedents. LAM is a theoretical framework that establishes resource bounds and achievable tradeoffs for agent-harness execution. Its contribution lies in lower bounds, matching constructions, and explicit conditions for optimal execution. Karpathy’s LLM OS discussion and MemGPT provide architectural context for managed memory and context. LAM supplies a mathematical basis for analyzing such designs: how many model calls and memory transfers are necessary, when persistence avoids recomputation, and how verification changes reliability cost. This complements work on model capability by characterizing the resources required to realize that capability through a harness. The revised Section 2 further discusses the relationship to MemGPT and related inference abstractions.

  2. About token costs, prefix caching, and latency. We clarified both the theoretical counting convention and the treatment of caching in Section 4. The revised text states: “Prefix caching reuses computation but leaves logical input unchanged.” It then specifies the scope: “Our main theoretical results count logical traffic; the communication experiment in Section 8 additionally evaluates the effect of exact-prefix caching.” These statements distinguish the full input supplied to the model from the prefix computation that caching can reuse. LAM provides a theoretical basis for predicting and explaining harness costs across deployments. A measured bill describes one execution under one serving configuration. Our resource laws establish how costs scale with task size, context, persistence, and verification, and provide lower bounds across the execution classes covered by the theorems. Deployment-specific prices and calibrated error rates then turn these laws into cost predictions and policy choices. For example, our checkpoint-policy experiment fixes its prediction before evaluation: under the implemented segment-check interface, the selected four-step rollback policy has a forecast weighted cost of 25.2 and a measured cost of 25.2. This tests a prospective prediction, beyond reporting the cost of a completed run.

    Prefix caching refines this prediction by changing the cost of repeated input processing. Our communication evaluation (see revised Section 8, “Communication”) quantifies its effect: the replay-to-dependency-only ratio changes from 7.14× in logical input to 1.72× in estimated prefill on the synthetic chain, and from 11× to 3.05× on development MATH. These results explain why a large logical-traffic reduction can produce a smaller deployment benefit. Combining the resource laws with cache behavior, serving prices, and measured reliability supports concrete harness choices: whether to replay or route state, retain or recompute results, and verify frequently or recover over longer segments. The theoretical contribution is therefore both predictive and explanatory: it identifies unavoidable costs and guides the search for better cost–reliability tradeoffs across harness designs.

  3. About guidance for practical harness design. LAM supports a concrete selection procedure: specify the application's budget and reliability requirement, compare feasible policies, and select the lowest-cost policy that meets the requirement. On development tasks, measure model and verifier error rates, token costs, and cache behavior. Use these measurements with the resource laws to compare routing, storage, and verification/recovery policies. Fix the selected policy before held-out evaluation. Our checkpoint experiment follows this procedure: the calibration-derived rule selects a four-transition rollback interval, which is also the cheapest certified policy on the held-out chains under the implemented segment-check interface. Its measured weighted cost of 25.2 matches the frozen forecast. The execution-granularity experiment provides a second concrete design lesson: select grouping and verification together. The added Figure 3 shows that verified four-step calls achieve 96% success at 3,200 tokens per chain, compared with 92% at 3,600 tokens for unverified one-step calls. Verified eight-step calls retain 92% success at 2,700 tokens, a 25% cost reduction. Thus, a designer can reduce cost by grouping steps while using verification to recover reliability. The resource laws organize the candidate choices, and task-specific measurements determine which configuration meets the application objective.

AuthorsOpenReview ↗

Response to Reviewer kn2r (part 2/6)

W2. Classical foundations and the content of the results.

The reviewer writes "I am not a theoretician". We appreciate your perspective and thoughtful questions. As researchers in the theory of LLMs and agents, we aim to make our results clear and useful to practitioners.

Our core novelty is introducing a unified resource theory for LLM agent harnesses, covering four aspects: (i) communication between context and memory, (ii) memory-access interfaces, (iii) persistence–recomputation tradeoffs, and (iv) reliability through sampling, verification, and recovery.

Our contributions go beyond these classical foundations. We use classical pebbling, time--space tradeoffs, sequential-testing tools, and checkpointing laws as starting points, but derive new harness-level results that account for model calls, active context, persistent memory, correctness feedback, and rollback. Concretely, we characterize joint call--communication costs, separate persistence from active context in recomputation, prove a tight no-feedback sampling law for multi-step execution, and derive joint verification--rollback policies that can outperform either mechanism alone.

The revised Table 1 makes these distinctions explicit. We further provide a comparison table to classical works, and we also list how we have revised the paper to better reflect our novelty.

AuthorsOpenReview ↗

Response to Reviewer kn2r (part 3/6)

Table A. Classical foundations, our novelties and revisions

Classical foundationWhat we inheritWhat is novel in our paperHow we have revised the paper
Hong & Kung (1981)The red–blue pebble model and classical input/output lower bounds.We derive optimal call and transfer costs on a grid, showing that minimum model-call complexity and optimal-order memory communication can be achieved simultaneously. See Section 4.We rewrote Section 4 to separate classical results from our contributions: (a) shortened the pebbling background, (b) simplified the correspondence theorem, (c) replaced the abstract Pareto-frontier emphasis with a concrete joint call–communication result, and (d) moved the sequential input-traffic result into the main text with a clearer explanation of its harness-level significance.
Lengauer & Tarjan (1982)The classical bit-reversal time–space tradeoff.In Section 6, we separate active context from persistent memory and show how persistence can eliminate repeated model calls without enlarging the context window. On the bit-reversal DAG, the optimal call cost is N=Θ(n2/(C+S)+n)N=\Theta(n^2/(C+S)+n), and a matching harness achieves this bound with only O(n)O(n) memory transfers.We rewrote Section 6 to make the distinction from the classical result explicit: (a) motivated recomputation as a harness-level problem, (b) explained the bit-reversal construction and why it creates delayed reuse, (c) separated active context from persistent memory, and (d) added a concrete interpretation showing how storing intermediate results avoids repeated model calls while still requiring retrieval into context.
Wald (1947); Bretagnolle & Huber (1979)Classical sequential-testing tools for lower-bounding the samples needed to distinguish two distributions.In the Reliability section (Section 7), we prove that without correctness feedback, reliable multi-step execution necessarily incurs a logarithmic sampling overhead. On a hidden-tree task where a wrong transition produces no later warning, even adaptive sampling requires Θ(nγ−2log⁡(n/δ))\Theta(n\gamma^{-2}\log(n/\delta)) model calls, and plurality matches this order.We rewrote the sampling analysis to make the contribution explicit: (a) motivated the no-feedback setting as a harness-level problem, (b) explained why hidden-tree errors cannot be detected later, (c) emphasized that the lower bound allows adaptive stopping, and (d) connected the lower and upper bounds into a tight end-to-end model-call law.
Young (1974); Daly (2006); Aupy et al. (2013)Classical checkpointing tradeoffs between checking overhead and repeated work, including square-root checkpoint scaling and silent-error verification.Beyond the classical checkpointing law, we jointly optimize local verification and segment rollback. We derive the exact combined cost and show that an interior hybrid can be strictly cheaper than either local verification or checkpointing alone; our extensions also incorporate transfer cost and non-independent error hazards.We revised Section 7's discussion to explicitly credit the classical square-root law and distinguish it from our new joint verification–rollback optimization, transfer-priced policy, and conditional-hazard extension.

Reviewer_3LMQOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces the Language Model Agent Machine (LAM) to study harness-level resource costs while fixing the underlying semantic model. It derives results on communication, memory access, recomputation, verification, and checkpointing, supported by controlled experiments and held-out evaluations.

Critical strengths
  1. LAM provides a unified resource model for comparing harness designs while fixing the underlying semantic model.
  2. The lower bounds and constructive schedules give useful foundations for understanding communication, memory access, and persistence–recomputation tradeoffs.
  3. The reliability analysis carefully accounts for verification and checkpointing costs, with held-out evaluations comparing frozen predictions against measurements.
Critical weaknesses
  1. The communication and recomputation results concern vertex-granular evaluations, leaving limited guidance on choosing between stepwise execution and whole-task calls.
  2. The checkpoint-policy tournament is conditional on a programmatic segment-check interface, limiting evidence about the cost of verification in other agent tasks.
Questions for authors
  1. How could LAM guide the choice of execution granularity?
  2. How should C, S, and Q_{blk} map to an actual harness when only a subset of X is passed to each model call?
4 comments
AuthorsOpenReview ↗

Response to Reviewer 3LMQ (part 1/4)

We thank the reviewer for the careful reading and for recognizing the main strengths of our work, including LAM as a unified resource model for comparing harness designs under a fixed semantic model, the value of our lower bounds and constructive schedules for communication, memory access, and persistence--recomputation tradeoffs, and the care taken in our reliability analysis and held-out evaluation of verification and checkpointing costs. We also appreciate the reviewer’s constructive questions on execution granularity and the mapping from the abstract resource parameters to practical harness implementations. We address both points below and have revised the paper accordingly.

W1. Guidance on execution granularity.

LAM guides this choice by treating the grouping of semantic steps into model calls as a harness design decision. Whole-task Direct and fully stepwise execution are two endpoints; intermediate groupings are also allowed.

We have added an execution-granularity experiment to Section 8, reported in Figure 3. It compares six group sizes with and without boundary verification. Each model call executes a group of consecutive logical steps and returns its endpoint. Boundary verification checks that endpoint and retries rejected groups. The table below reports measured success rates and total token costs, including solver, verifier, and retry tokens.

Table. Execution granularity, verification, and token cost–success tradeoffs

Logical steps per callVerificationToken cost per chainChain success
1None3,61492%
1Boundary6,85399%
2None2,84390%
2Boundary4,36998%
4None2,31086%
4Boundary3,28596%
8None2,06180%
8Boundary2,71192%
16None1,85274%
16Boundary2,21985%
32None1,72968%
32Boundary1,90875%
AuthorsOpenReview ↗

Response to Reviewer 3LMQ (part 2/4)

Larger groups reduce token cost but lower success under both policies. Boundary verification improves success at every grouping, with an additional token cost. Selecting grouping and verification jointly can improve both metrics: four-step calls with verification achieve 96% success at 3,200 tokens per chain, compared with 92% at 3,600 tokens for unverified one-step calls. Eight-step calls with verification also match the latter's 92% success at only 2,700 tokens per chain, a 25% cost reduction. These comparisons make execution granularity a concrete harness design choice across intermediate groupings as well as the two endpoints.

Concretely:

  1. Different groupings induce different resource costs. Grouping more steps into one call reduces call count and hides internal dependencies from the harness, which can reduce communication. Finer execution exposes more intermediate states for memory, reuse, verification, and rollback.

  2. LAM can compare intermediate granularities, not only the two extremes. For example, a 16-step task could use one 16-step call, sixteen 1-step calls, four 4-step calls, or a nonuniform partition that exposes only selected intermediate states. Each choice induces different resource costs and opportunities for verification. In the revised Section 8, Figure 3 reports measured costs and success rates across six group sizes, with and without boundary verification. This verifier checks each returned endpoint and retries rejected groups.

  3. The best granularity therefore depends on the target objective and verification policy. If model calls and communication dominate, coarser execution may be preferable. If intermediate verification, reuse, or recovery is valuable, exposing more boundaries can be worth the additional cost. The new experiment shows why these choices should be made jointly: verification increases cost at a fixed grouping, but larger groups with verification can be both cheaper and more reliable than smaller groups without verification.

Section 8 provides held-out MATH measurements at the two endpoints: Direct uses 1,311 input tokens per chain with 64/70 chains correct at every link, while dependency-only execution with verification uses 3,217 input tokens with 70/70 chains correct at every link. We revised the execution-granularity discussion and added the intermediate-grouping illustration to explain how grouping and verification jointly shape the cost–success tradeoff. The practical guidance is to compare these choices together using LAM's resource accounting and measured reliability under the application's objective.

AuthorsOpenReview ↗

Response to Reviewer 3LMQ (part 3/4)

W2. Programmatic verification in the checkpoint experiment.

  1. The programmatic verifier isolates the checkpointing tradeoff: how often should the harness check progress when checking has a known cost? The checkpoint law assumes perfect segment verification. We therefore hold verifier correctness fixed and vary its stipulated price across 1, 4, and 16 solver-call equivalents. This tests the balance between frequent checking and the repeated work caused by rolling back longer segments.

  2. The predicted policy choices agree with the held-out measurements. Predictions are fixed before evaluation. At the three verifier prices, the predicted and measured cost-minimizing checkpoint intervals coincide at 4, 8, and 16 transitions, respectively. In the separate policy tournament, all arms are evaluated on the same 100 held-out chains. The calibration-derived rule selects a four-transition rollback interval, which is also the cheapest certified policy on the held-out data: it has 1/100 failures and a reported weighted cost of 25.2, matching the reported forecast. This tournament tests policy selection under the implemented segment-check interface, whose affine-composition work is performed outside the priced semantic execution.

  3. The revised Section 7 explicitly separates imperfect local checking from perfect segment checking. Its Imperfect Local Verification theorem accounts for false acceptance, false rejection, and retry cost. The main text also includes candidate-dependent verifier behavior. For checkpointing, the Conditional-hazard Checkpoint Envelope allows transition errors to depend on the preceding execution and rollback history, without independence within or across attempts, while retaining a perfect segment verifier. The joint policy combines imperfect local checks with perfect segment verification and rollback.

  4. The practical guidance is to price the available checking interface and choose the checking and recovery schedule accordingly. The controlled experiment tests this choice when segment checks are perfect; the imperfect-local-verification analysis separately quantifies how verifier errors change accepted-error probability and retry cost.


Q1. How could LAM guide the choice of execution granularity?

We have added an experiment across six execution granularities, with and without boundary verification, reported in Figure 3. LAM treats execution granularity as a harness design choice with measurable resource consequences. A designer can compare alternative groupings of the same task along four dimensions:

  1. Model calls and input traffic: grouping more logical steps into each call can reduce call count and communication.
  2. Intermediate-state access: smaller groups expose more states that can be selectively routed or stored.
  3. Recomputation: exposed intermediate results can be persisted and reused rather than regenerated.
  4. Verification and recovery: each exposed boundary provides an opportunity to check progress and retry rejected work.

The choice depends on the application's budget and required success rate. First, test several group sizes on development tasks. For each size, compare execution with and without boundary verification. Measure success and count all token costs, including checks and retries. Then choose the cheapest option that meets the required success rate. Using the measured success rates in Figure 3, a 90% requirement would select verified eight-step calls at 2,700 tokens per chain. A 98% requirement would select verified two-step calls at 4,300 tokens. If the application instead has a fixed budget, choose the option with the highest success rate within that budget. For example, a 2,200-token budget would select verified sixteen-step calls, with a measured success rate of 85%. Finally, fix the chosen policy and test it on held-out tasks. LAM accounts for resource costs. Task-specific measurements establish success rates. Together, they guide the choice of grouping and verification.

The held-out MATH measurements provide complementary evidence at the endpoints: Direct uses 1,311 input tokens per chain with 64/70 all-link correctness, while dependency-only execution with verification uses 3,217 input tokens with 70/70 all-link correctness. Together, these comparisons explain where exposing intermediate states is worth the additional cost and how intermediate groupings can balance execution overhead with verification and recovery.

AuthorsOpenReview ↗

Response to Reviewer 3LMQ (part 4/4)

Q2. How should CC, SS, and QblkQ_{\mathrm{blk}} map to an actual harness when only a subset of XX is passed to each model call?

The revised Section 3 states that a model call selects its arguments from XX, while other resident blocks are not passed to it. Section 4 now clarifies that only selected arguments contribute to model-facing input traffic. The mapping is:

  1. CC — active semantic capacity. This bounds all blocks resident in XX, including controller block registers. A block occupies capacity even when the next call does not use it. A model call selects at most C−1C-1 argument blocks, leaving a slot for its output.

  2. SS — persistent semantic capacity. This bounds blocks retained in MM outside XX. A stored block must be retrieved into XX before a call can use it. Retrieval preserves the persistent copy.

  3. QblkQ_{\mathrm{blk}} — memory transfers. Loading a block from MM into XX, or storing a block from XX into MM, contributes one transfer. Passing an already-resident block to a call creates no additional transfer.

  4. TinT_{\mathrm{in}} and ToutT_{\mathrm{out}} — model-facing traffic. These count symbols supplied to and returned by model calls. Only selected arguments contribute to a call's input traffic.

For example, suppose XX has four slots and holds three blocks. A call selects two blocks and places its output in the remaining slot. All three resident blocks occupy active capacity, but only the selected two contribute to that call's input traffic. No memory transfer is needed for this call.

Section 4 also now states that prefix caching reuses computation but leaves logical input unchanged. The existing communication evaluation separately considers exact-prefix caching. On the deepest synthetic setting, the replay-to-dependency-only ratio is 7.14× for logical input and 1.72× for estimated prefill. On development MATH, the corresponding ratios are 11× and 3.05×. These are traffic ratios, not dollar-cost ratios. These clarifications distinguish resident state, memory transfers, per-call input, and the computation reused through prefix caching.


Overall, we revised the paper to make LAM's practical guidance clearer. Section 8 now includes Figure 3, a new experiment across six execution granularities with and without boundary verification. Its measured costs and success rates show how grouping and verification jointly affect performance. Sections 3 and 4 clarify how resident state, memory transfers, and per-call traffic are counted, and distinguish logical input from computation reused through prefix caching. Section 7 distinguishes imperfect, candidate-dependent local verification from perfect segment verification. We also explain that the programmatic-verifier experiment tests the checkpoint law under a controlled checking interface.

We hope these revisions address the reviewer’s concerns about execution granularity and the practical interpretation of the resource model. If these clarifications resolve your concerns, we would greatly appreciate it if you would consider increasing your score accordingly.

Reviewer_cQjCOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper builds a formal model of the cost of running an LLM inside an agent harness. The LLM is treated as a black box that turns input chunks into output chunks, while the harness has a bounded context and memory and may not compute content itself. Within this model the paper proves cost tradeoffs for moving data between context and memory (shown equivalent to the classic red–blue pebble game), for random versus sequential memory access, for storing intermediate results versus recomputing them, and for verification and checkpointing. Small experiments on GPT-6 Astra check some of the predictions.

Critical strengths

An interesting framing connecting agent harnesses to classical I/O complexity, treating the context window as fast memory and external storage as slow memory.

The experiments are limited but the authors are clear about what they show.

Critical weaknesses

Novelty is limited. Most results are classical ones (Hong–Kung pebbling, Lengauer–Tarjan, Young–Daly checkpointing, standard sampling bounds) restated in agent terms, with the translation itself as the main new part. The link to real agents is also weak. The theory assumes each call does one small step on toy tasks such as bit-reversal graphs and tape or stack memory, with independent errors. The paper’s own MATH result shows a single call doing many steps uses fewer tokens, which falls outside the model, and its data shows errors vary by state. Finally, the experiments mostly confirm arithmetic: token savings follow from counting, the checkpoint test uses a perfect programmatic verifier, and accuracy differences on 70 MATH chains are small.

Questions for authors

Which proof steps are new beyond translating classical results? Can the framework account for a single call doing many steps, which is the main lever real harnesses use? Is there a non-obvious harness design choice the theory predicts that holds on a realistic agent task?

7 comments
AuthorsOpenReview ↗

Response to Reviewer cQjC (Part 1/6)

We thank you for appreciating our framing which connects agent harnesses to classical I/O complexity.

W1. Differences from classical results.

Our core novelty is introducing a unified resource theory for LLM agent harnesses, covering four aspects: (i) communication between context and memory, (ii) memory-access interfaces, (iii) persistence–recomputation tradeoffs, and (iv) reliability through sampling, verification, and recovery.

Our contributions go beyond these classical foundations. We use classical pebbling, time--space tradeoffs, sequential-testing tools, and checkpointing laws as starting points, but derive new harness-level results that account for model calls, active context, persistent memory, correctness feedback, and rollback. Concretely, we characterize joint call--communication costs, separate persistence from active context in recomputation, prove a tight no-feedback sampling law for multi-step execution, and derive joint verification--rollback policies that can outperform either mechanism alone.

We summarized key novelties from classical literature in the following table, and we also list how we have revised the paper to better reflect our novelty.

Table A. Classical foundations, our novelties and revisions

Classical foundationWhat we inheritWhat is novel in our paperHow we have revised the paper
Hong & Kung (1981)The red–blue pebble model and classical input/output lower bounds.We derive optimal call and transfer costs on a grid, showing that minimum model-call complexity and optimal-order memory communication can be achieved simultaneously. See Section 4.We rewrote Section 4 to separate classical results from our contributions: (a) shortened the pebbling background, (b) simplified the correspondence theorem, (c) replaced the abstract Pareto-frontier emphasis with a concrete joint call–communication result, and (d) moved the sequential input-traffic result into the main text with a clearer explanation of its harness-level significance.
Lengauer & Tarjan (1982)The classical bit-reversal time–space tradeoff.In Section 6, we separate active context from persistent memory and show how persistence can eliminate repeated model calls without enlarging the context window. On the bit-reversal DAG, the optimal call cost is N=Θ(n2/(C+S)+n)N=\Theta(n^2/(C+S)+n), and a matching harness achieves this bound with only O(n)O(n) memory transfers.We rewrote Section 6 to make the distinction from the classical result explicit: (a) motivated recomputation as a harness-level problem, (b) explained the bit-reversal construction and why it creates delayed reuse, (c) separated active context from persistent memory, and (d) added a concrete interpretation showing how storing intermediate results avoids repeated model calls while still requiring retrieval into context.
Wald (1947); Bretagnolle & Huber (1979)Classical sequential-testing tools for lower-bounding the samples needed to distinguish two distributions.In the Reliability section (Section 7), we prove that without correctness feedback, reliable multi-step execution necessarily incurs a logarithmic sampling overhead. On a hidden-tree task where a wrong transition produces no later warning, even adaptive sampling requires Θ(nγ−2log⁡(n/δ))\Theta(n\gamma^{-2}\log(n/\delta)) model calls, and plurality matches this order.We rewrote the sampling analysis to make the contribution explicit: (a) motivated the no-feedback setting as a harness-level problem, (b) explained why hidden-tree errors cannot be detected later, (c) emphasized that the lower bound allows adaptive stopping, and (d) connected the lower and upper bounds into a tight end-to-end model-call law.
Young (1974); Daly (2006); Aupy et al. (2013)Classical checkpointing tradeoffs between checking overhead and repeated work, including square-root checkpoint scaling and silent-error verification.Beyond the classical checkpointing law, we jointly optimize local verification and segment rollback. We derive the exact combined cost and show that an interior hybrid can be strictly cheaper than either local verification or checkpointing alone; our extensions also incorporate transfer cost and non-independent error hazards.We revised Section 7's discussion to explicitly credit the classical square-root law and distinguish it from our new joint verification–rollback optimization, transfer-priced policy, and conditional-hazard extension.
AuthorsOpenReview ↗

Response to Reviewer cQjC (Part 2/6)

W2. Connection to real-agent execution.

The reviewer writes that “the theory assumes each call does one small step” and that the MATH Direct result “falls outside the model,” while also noting that “errors vary by state.” We agree that execution granularity and state-dependent errors are important in real agents, and our framework already accounts for both. The MATH result illustrates execution granularity as a resource choice, while our reliability analysis includes heterogeneous and history-dependent error models beyond the independent case.

First, the statement that our theory assumes “each call does one small step” does not accurately describe the scope of the paper. Several parts of the paper do not rely on this assumption at all. (i) The general LAM framework in Section 3 does not require one model call to correspond to one elementary task step; the vertex-granular restriction is introduced later for specific results. (ii) The memory-access results in Section 5 do not depend on model-call granularity: the pointer-chasing results analyze memory-access operations, while the single-stack result uses no model or tool calls at all. (iii) The Reliability analysis in Section 7 is formulated over semantic state transitions, but a transition is not required to be an elementary reasoning step; a call may implement an arbitrarily complex fixed semantic transition. (iv) The experiments in Section 8 explicitly include a Direct condition in which one model call performs the entire multi-step MATH chain. Thus, one-call-one-step is not a global assumption of LAM; it is an explicit restriction used only for particular stepwise results, such as the Communication results in Section 4 and the Recomputation result in Section 6.

Second, the claim that our theory relies on independent, homogeneous errors is incorrect as a characterization of our reliability analysis. Independence is used for particular closed-form results in Section 7, but we analyze several more general settings. Specifically, (i) our local-verification analysis in Section 7 explicitly allows candidate-dependent verifier behavior, where different correct and incorrect candidates can have different acceptance probabilities; the resulting accepted-error and retry-cost formulas remain valid after replacing fixed verifier rates by the corresponding candidate-dependent quantities. (ii) More importantly, our Conditional-hazard checkpoint envelope in Section 7 allows the transition error probability to depend on the entire preceding execution and rollback history. It requires only bounds on the conditional error hazard and explicitly makes no independence assumption within or between rollback attempts. (iii) Our experiments in Section 8 directly measure substantial variation in error rates across chain states and report that a pooled homogeneous i.i.d. model does not describe the observed sampling data. Thus, fixed-ε\varepsilon and independence assumptions are used to obtain exact baseline formulas, rather than imposed as universal assumptions of the framework.

Third, we have added an execution-granularity experiment to Section 8, reported in Figure 3. It compares six group sizes with and without boundary verification. Each model call executes a group of consecutive logical steps and returns its endpoint, allowing the harness to choose which intermediate states become available for routing, storage, and verification. The measured results show that larger groups reduce token cost but lower success. Boundary verification checks each returned endpoint and retries rejected groups. The measured results support choosing grouping and verification jointly: a larger verified group can be both cheaper and more reliable than a smaller unverified group. The held-out MATH results complement this experiment, with verified stepwise execution achieving 70/7070/70 all-link correctness versus 64/7064/70 for whole-chain Direct. Together, these comparisons make execution granularity a concrete harness design choice, spanning intermediate groupings as well as whole-task and fully stepwise execution.

Figure 3 and Table B report the 32-step MATH granularity experiment using GPT-6 Astra, with 100 chains per configuration. The six group sizes range from one step per call to the entire 32-step chain:

AuthorsOpenReview ↗

Response to Reviewer cQjC (Part 3/6)

Table B. Execution granularity, verification, and token cost–success tradeoffs

Logical steps per callVerificationToken cost per chainChain success
1None3,61492%
1Boundary6,85399%
2None2,84390%
2Boundary4,36998%
4None2,31086%
4Boundary3,28596%
8None2,06180%
8Boundary2,71192%
16None1,85274%
16Boundary2,21985%
32None1,72968%
32Boundary1,90875%

Larger groups reduce token cost but lower success under both policies. Boundary verification improves success at every grouping, with an additional token cost. Selecting grouping and verification jointly can improve both metrics: four-step calls with verification achieve 96% success at 3,200 tokens per chain, compared with 92% at 3,600 tokens for unverified one-step calls. Eight-step calls with verification also match the latter's 92% success at only 2,700 tokens per chain, a 25% cost reduction.

Furthermore, to make these distinctions explicit in the revision, we clarified in Section 7 that the fixed-ε\varepsilon and independence assumptions are not universal, added the candidate-dependent verification case to the main text, and moved the Conditional-hazard checkpoint envelope into the main paper to cover history-dependent errors without independence within or across rollback attempts.

Comments on the paper

3 comments
AuthorsOpenReview ↗

Rebuttal Summary — Please Take a Look at Our Responses and Provide Feedback

Dear AC and reviewers,

We thank the reviewers for their careful reading and constructive questions.

Our contributions establish a mathematical basis for understanding how harness design changes the computational cost of realizing a fixed model capability. LAM separates the underlying semantic model from the resources used to execute it, making it possible to compare harnesses with the same capability but different execution costs. We characterize resource requirements and achievable tradeoffs across communication, memory access, recomputation, and reliability. Lower bounds identify costs that every execution in the stated class must pay, while matching constructions show how those bounds can be attained. Together, these results explain when changes to context management, persistent storage, memory interfaces, and verification can improve execution efficiency, and provide a theoretical basis for practical harness design.

Our core novelty is introducing a unified resource theory for LLM agent harnesses, covering four aspects: (i) communication between context and memory, (ii) memory-access interfaces, (iii) persistence–recomputation tradeoffs, and (iv) reliability through sampling, verification, and recovery. Beyond their classical foundations, our results characterize joint call–communication budgets, distinguish active context from persistent storage, establish tight sampling costs for irreversible decisions, and identify when combining verification with rollback reduces cost.

We have revised the paper to clarify its contributions beyond classical results and strengthen its connection to practical harness design.

  1. We make the theoretical novelty explicit. The revised Introduction and Table 1 distinguish the classical foundations from our joint call–communication results, persistence–recomputation tradeoffs, tight sampling bounds, and combined verification–rollback analysis.

  2. We add a measured execution-granularity experiment in Section 8, Figure 3. It evaluates six group sizes on 32-step MATH chains, with and without boundary verification, using 100 chains per configuration. Verified four-step calls achieve 96% success at 3,285 tokens per chain, compared with 92% at 3,614 tokens for unverified one-step calls. The results demonstrate why grouping and verification should be selected jointly.

  3. We clarify the framework's scope and deployment interpretation. The revision explains which results require vertex-granular execution, how the reliability analysis accommodates candidate-dependent verification and history-dependent errors, and how logical traffic relates to prefix caching and deployment costs. We also simplify the presentation and shorten the appendix.

The revised main paper is now 10 pages, with expanded explanations of the theoretical contributions, practical interpretations, and experimental results. Revisions are marked in dark blue. Our responses for each reviewer identify the relevant sections and explain the changes in detail.

We would greatly appreciate the reviewers' feedback on these revisions and additional results during the discussion period. Please let us know whether they address your concerns or whether any points need further clarification; we would welcome the opportunity to respond.

Best regards,

The Authors

Dear Reviewers,

As the author–reviewer discussion period is approaching its end, we would like to kindly follow up on our detailed rebuttal and revised manuscript.

We have made substantial revisions to address your concerns, including new experiments, clearer explanations of our theoretical contributions, and improved presentation. We would greatly appreciate your feedback on whether these revisions have addressed your main concerns.

If any questions or concerns remain, we would be more than happy to provide further clarification before the discussion period closes.

Thank you again for your time and consideration.

Best regards,

The Authors

Dear Reviewers,

We have taken your reviews seriously and put considerable effort into addressing every concern, including revising the paper and conducting additional experiments.

We understand that everyone is busy, but we would really appreciate a response from your side as well. Even a brief update on whether our rebuttal has changed your assessment would be very helpful.

We believe that a fair review process requires a two-way discussion, where authors have the opportunity to address concerns and reviewers consider their responses. We sincerely hope our efforts and revisions can receive a fair evaluation before the discussion period closes.

Best regards,

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.