CAPE: Coverage-Preserving Tool-Use Optimization for Agents

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.