acceptodds
Withdrawn from ICLR 2027

CAPE: Coverage-Preserving Tool-Use Optimization for Agents

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Adapting a language agent’s tool program should preserve every deployment that its previous execution policy supports. Finding a better policy and establishing its optimality can require different amounts of computation. CAPE compiles native program effects into coverage-preserving policies with no model training. It separates the identities that must succeed by the deadline from the number that could succeed at an earlier prefix. These relaxed completion capacities provide upper bounds on progress and lower bounds on the call cost of partially covered policies. Verified native-effect symmetries share the capacity calculation while the policy search retains the required identities. The compiler keeps an executable incumbent and records whether optimality has been established. On 48 predefined operations from eight database tables with 64 native profiles, CAPE and full-state-symmetric AND/OR both achieve full completion in 2.396 calls and certify every operation. Mean planning CPU is 0.378 versus 0.771 seconds, with savings concentrated in the Employees operations. At 128 profiles CAPE certifies four more operations with additional computation. Larger native families, matched-initialization ablations and complete execution records characterize when the capacity bounds reduce search and when their computation costs more.

Primary area:
applications to robotics, autonomy, planning
Keywords:
Agent, Planning, Tool Use, Policy Synthesis

Reviews

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

The paper studies compilation of tool-use policies for a finite family of receivers whose identity is hidden at execution time but whose action effects can be calibrated offline. Starting from a supplied playbook, CAPE preserves every receiver configuration that the playbook completes, then lexicographically maximizes completion and minimizes execution calls within a fixed call budget. Its key mechanism builds executable policies from actions whose effects are known on their reached receiver scopes, while optimistic bounds guide acquisition of additional program and diagnostic effects. Selective two-call continuation bounds can stop acquisition early. Under deterministic, unchanged-state assumptions, the method preserves inherited coverage and certifies full-catalog optimality when lower and upper values meet.

Critical strengths
  • The motivation, method, and evaluation are closely aligned. Unknown receiver effects can make an optimistic policy impossible to execute, so preserving every initially supported receiver is a consequential requirement. Locally closed witnesses address this directly, and independent complete-model solutions and replay test the actual coverage and optimization objective. CAPE reaches the independently computed optimum in 502/504 executable compilations. Figure 2 further checks when diagnostics expand achievable completion, distinguishing CSV headroom from JSON cases where the full-catalog and program-only optima coincide. This provides evidence about both the problem and what the method solves.
  • The additional experiments test the proposed mechanisms beyond the main result. Eager exact, generic lazy, program-only, program-first, and protected lookahead are relevant alternatives. The full-row and no-tightening controls test local acquisition and continuation bounds, while the matched 2-by-3 AND/OR study separates acquisition order from bound-computation effort. These controls substantiate the scheduler benefit and expose conditions where tightening does not pay. The fourteen-deployment panel adds evidence that the compiler can be reused across proposal sources, without being essential to the core mechanism claim (Sections 4.2–4.5).
Critical weaknesses
  • The dataset varies source data more than the policy-search structures central to the motivation. The 64 requests come from eight sources and eight operations, but use two receiver families: 64 CSV and 88 JSON configurations, with call budgets C = 3/5. This is appropriate for a controlled demonstration, yet offers limited variation in receiver ambiguity, observation merging, action-catalog structure, and horizon, which determine whether the acquisition frontier is effective. The fourteen proposal deployments broaden proposal sources rather than independently broadening these native tool structures. The results therefore support the compiler on the tested interface families, with a narrower basis for general conclusions about its acquisition strategy. This is a limitation within the stated finite-receiver problem; arbitrary stochastic or stateful tools are not required to validate that problem.
  • The default selective-tightening policy has a conditional efficiency benefit that is not fully characterized. The paper appropriately exposes this in Table 2: for CSV at C = 3, always tightening is faster than selective tightening (10.177 versus 10.918 seconds), while at C = 5 selective and no-tightening CAPE have the same mean acquisition count. JSON supports the acquisition scheduler but gives little evidence of a separate tightening benefit. Thus, the observed average compilation gain does not establish that the full default combination is the best allocation of computation across workloads. Since compilation can require thousands of effect queries while execution sometimes saves less than one call per receiver, the practical significance also depends on query cost and playbook reuse. A characterization of these cost regimes would make the motivation-to-efficiency conclusion substantially stronger.
  • Writing quality: repeated defensive qualifications and overemphasis on the method's boundaries. The manuscript repeatedly restates its finite, calibratable receiver setting, unchanged-state failure semantics, and conditional certification guarantees across the introduction, Section 3.1, Proposition 1, and the evaluation. Phrases such as “finite, calibratable receiver family” and “failed calls leave the task state unchanged” are part of this repeated framing. The evaluation also repeatedly emphasizes common inputs, shared components, and the separation of compilation from validation. Although these conditions are relevant, their dispersed repetition gives the exposition a defensive tone and devotes excessive attention to preempting objections. The repeated qualifications can heighten doubts rather than settle them, creating an impression of protesting too much. Consolidating the assumptions and experimental controls would improve writing quality and allow the central acquisition idea to stand out more clearly. This weakens the clarity and economy of the exposition. This is the consequence of the author's excessive reliance on GPT writing, and the author should optimize these writing sections to make their paper statements more persuasive, thereby improving the quality of their writing.
Questions for authors
  • What features of receiver ambiguity and observation partitions distinguish workloads where CAPE outperforms matched AND/OR from those where it ties or loses? Do the existing measurements or analysis indicate how that distinction changes with receiver count and call budget?
  • Can the tightening decision be related to expected native queries avoided versus bound-computation cost? This would explain the opposite CSV outcomes at C = 3/5 and whether the selective default is justified beyond the tested strata.
  • Under the measured native-query and execution costs, how much playbook reuse is needed for CAPE to pay off relative to program-only or the protected initializer? This concerns the efficiency significance of the current method, rather than an extension to a different tool model.
Reviewer_mhKbOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper introduces CAPE, a train-free compilation framework that optimizes tool-use policies for agents facing finite, pre-calibratable receiver families (e.g., DuckDB CSV and pandas JSON parsing variants). By using local closure, optimistic bounds, and a two-step relaxation (T2T_2), CAPE builds decision-tree policies that minimize execution calls while preserving baseline coverage (R0R_0).

Critical strengths
  1. CAPE actually delivers on its promise. It locks down initial coverage so you never break what already works (R0⊆S(π)R_0 \subseteq S(\pi)), hitting the true optimum in 502 of 504 runs when checked against a full-model solver. The algorithm clearly works as advertised.
  2. The empirical setup is top-notch, with isolated runs, paired bootstrap intervals, and zero cherry-picking. The authors openly report their negative results (like CSV C=5C=5 gains crossing zero). Because they are so transparent, I can trust the numbers completely, which makes it clear the actual gains are modest and mostly limited to JSON compile time.
Critical weaknesses
  1. CAPE’s final policies are practically identical to a simple eager exact search—matching it on CSV and barely moving the needle on JSON (+0.14 pp). The only real win is saving a few seconds of offline compile time, and even that vanishes on CSV at C=5C=5. Since the authors skip comparisons against obvious practical alternatives—like a standard LLM retry loop or classical solvers like EC²—it feels less like a breakthrough in agent behavior and more like a slightly faster exact solver for a very niche setup.
  2. The whole framework relies on an ideal scenario: a finite, fully enumerable, deterministic group of receivers that you can pre-calibrate offline. The experiments stick strictly to tiny setups (64 DuckDB configs, 88 pandas configs, C≤5C \le 5), with no scaling tests as the state space grows. Plus, the 14-model panel doesn't prove much since most of them output the exact same code. It’s hard to buy the broad "tool-using agents" framing when the method is tethered to such a restricted, rigid environment.
Questions for authors
  1. Outside of standard file-reader configs, in what real-world agent scenario is an API family fully pre-calibratable offline yet completely hidden at runtime? If this framework is really meant just for configuration-parsing problems, it’s better to state that explicitly.
  2. What happens if you compare CAPE to a basic ReAct agent that just tries the program, reads the error log, and retries with tweak options under the same call budget CC? If a standard retry loop gets similar success without needing offline compilation, that directly impacts how big of a contribution this is.
  3. How do compile time and certification scale as ∣H∣\vert{}H\vert{} hits the hundreds/thousands or CC goes up to 8? You mention exponential state-space growth, but don't test it. Showing that CAPE's speedup over eager exact search actually widens on bigger problems would make a much stronger case.
Reviewer_t7EtOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The work studies how a tool-using agent should submit an LLM-proposed data operation to a receiver whose input format is unknown at execution time. The authors frame this as compiling an adaptive decision tree of program attempts and diagnostic probes. The tree should maximize the number of configurations that succeed within C calls, then minimize total calls, while keeping every configuration that an initial trial-in-order policy already handles. Building this tree requires querying how each action behaves on each configuration, which is expensive. The proposed method, CAPE, avoids querying the full table. It acquires outcomes selectively, only when they are needed, maintains an executable policy together with an optimistic upper bound, and certifies optimality when the two meet.

Critical strengths
  1. In this setting, unknown outcomes affect not only whether a call succeeds but also which configurations can be told apart, so a standard optimistic plan may not be executable. The paper recognizes this and builds a relaxation that stays a valid upper bound in both respects.
  2. CAPE keeps an executable policy separate from its optimistic bound. As a result it can return a usable policy at any time, never loses coverage relative to the initial playbook, and can certify optimality when the bounds meet.
  3. An action only needs to be tested on the configurations that actually reach it, which avoids filling the full outcome table
  4. Experiments are cleanly controlled. Comparing against exact search with identical policy quality isolates the cost benefit. The shared-kernel comparison isolates the scheduler from the bounds and caches. Optimality is checked independently rather than relying on the method’s own certificates.
Critical weaknesses
  1. The work is very hard to follow from the beginning to the end. The abstract and introduction are close to unreadable. They rely on undefined coined terms: “receiver identity,” “inherited coverage contract,” “locally closed action effects,” “native witness,” “native observation partitions,” “compilation lifecycle,” “mechanism cohort,” “shared-kernel.” Likewise, the method section introduces many symbols in quick succession: S, M, D, G, Ḡ, d̄, B, U, F⁺, k, c,... and so on. A short running example in the main text would make the method accessible. Hence, it is almost impossible to assess the true value of the work in its current form.

  2. The method assumes a finite, enumerable receiver family that can be instantiated offline, deterministic outcomes, failures without side effects, and equal weighting of all configurations in the objective (Section 3.1, Eq. 1). In particular, it assumes that calibration can instantiate every configuration while the executing policy cannot observe which configuration it faces. If every configuration of the receiver can be instantiated for calibration, it is unclear why the deployed configuration cannot simply be queried or agreed upon. The paper does not provide a concrete deployment in which this combination holds, so the setting appears constructed for the method.

  3. The claims, especially the agent framing, are not matched by what the experiments show. For example, the paper is framed as tool-use optimization for agents, but the LLM’s only role is to produce one operation per request. Everything afterwards is deterministic, offline combinatorial search over a hand-constructed finite family of reader configurations. There is no comparison with how an LLM agent would actually handle an unknown interface, for instance by reading the error message and revising the format (ReAct-style). The only agent-like baseline is a fixed catalog-order trial policy.

Questions for authors
  • Can you give a concrete deployment where the receiver family is finite and can be instantiated offline, yet the actual configuration cannot be queried or fixed at execution time?
  • How does an LLM agent that reads the error message and revises the serialization compare with CAPE’s compiled policy in success and execution calls?

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

Related papers

Discussion (0)

Sign in to comment.