Deciding When to Compile: Utility Accounting for Moving Tool Knowledge from Prompt to Weights

Language models that call software tools usually learn each tool by reading its documentation and a few usage examples placed in the prompt. This is flexible, since a tool released this morning works this afternoon. It is also expensive: every query pays attention cost over thousands of documentation tokens, and accuracy falls as the prompt grows. The opposite approach trains each tool into a small set of adapter weights and removes the documentation from the prompt. That is cheap per query but rigid, because a new tool cannot be used until someone trains its adapter, and a growing pile of adapters starts to interfere with one another. We propose treating the choice between these two representations as a decision made separately for each tool and revised over time. A tool starts in the prompt. It is compiled into weights only once the evidence shows that doing so pays for its training cost, its effect on accuracy, and the damage it does to other tools. It is demoted or dropped when that evidence reverses.

The idea comes from a 1980s finding in symbolic AI called the utility problem: systems that cached their past reasoning as reusable rules often got slower, because checking which rules applied cost more than the search the rules saved. The fix that worked was to count, for each rule, how often it is used, how much it saves, and how much it costs to apply, and then keep only rules whose net value was positive. Modern tool-using language models face the same accounting question in a new form. The "rule" is a tool's knowledge. It can be stored as prompt text, which costs tokens on every query, or as weights, which cost training and cause interference. Nobody currently decides between the two with an explicit, confidence-bounded utility estimate.

Core Claim

A system that keeps a running, statistically bounded estimate of each tool's net utility under both representations, and moves tools between "in-context," "compiled," and "evicted" accordingly, can recover most of the compute savings of full compilation while keeping the zero-delay flexibility of in-context use for new and rare tools. It should also beat the simple rule "compile whatever is used most." The last part of the claim carries the scientific weight. It only holds if call frequency and net utility often disagree. Two cases would produce such disagreement: popular tools whose schemas compile badly or collide with near-duplicate tools, and rarely used tools with enormous documentation. Testing whether those cases are common enough to matter is the core experiment.

Where This Sits

The classical work supplies the method. Quantitative Results Concerning the Utility of Explanation-Based Learning scored each learned rule as average savings times application frequency minus average match cost, and pruned rules with negative scores. Disabling that pruning caused a 65% slowdown in Blocksworld. A Statistical Approach to Solving the EBL Utility Problem (PALO) added Chernoff bounds, so that a change to the rule set is accepted only when it lowers expected cost with stated confidence. The same paper also warns about sample cost: tight tolerances needed over 20,000 samples, while coarse ones needed about 49. We use coarse, decision-relevant bounds for that reason. The Problem of Expensive Chunks and its Solution by Restricting Expressiveness showed that changing a rule's representation can bound its matching cost, at the price of needing more rules (142 versus 17 in their Grid task). Compilation into weights is the modern version of that trade.

On the modern side, ParaTool motivates the work and serves as the main competitor. It trains one low-rank adapter per tool, mixes adapters with a learned gate, and cuts compute by up to 92.22% on Stable ToolBench and 94.45% on BFCL-V2. It compiles every tool offline, however, so it cannot handle unseen tools and has no mechanism for pruning harmful adapters. Experience-Guided Behavior Adaptation for Large Language Models is the closest modern use of utility tracking. It keeps a Beta posterior over whether each stored piece of guidance leads to correct answers and selects guidance by Thompson sampling. Its utility counts only correctness and ignores token cost, and every selected item stays in the prompt as text. Our proposal differs in what it decides: not which text to insert, but which representation each piece of knowledge should live in. Train Once, Reuse Everywhere and Prompt-MII constrain the design. The first reports that attention routing cannot supply knowledge absent from the weights. The second reports that instruction compression was shown only for classification. Neither can stand in for tool-specific schemas, so we compile into adapters, as ParaTool does.

Research Program

Each tool $t$ is kept in one of three states. In the in-context state, retrieved documentation is inserted into the prompt. In the compiled state, the tool is represented by an adapter selected by a gate, as in ParaTool. In the evicted state, it is not used at all. For every tool, the system maintains running estimates of four quantities: call frequency $f_t$, success rate under each representation $a^{P}_t$ (prompt) and $a^{C}_t$ (compiled), and per-call compute $c^{P}_t$ and $c^{C}_t$. It also estimates an interference term $I_t$, defined as the drop in success on other tools' held-out probe queries after adding $t$'s adapter to the mixture. The net utility of compiling $t$, per unit of future traffic, is

$$U_t = f_t\left[\lambda\,(a^{C}_t - a^{P}_t) + (c^{P}_t - c^{C}_t)\right] - \frac{C^{\text{train}}_t}{H} - \lambda I_t .$$

Here $\lambda$ converts a unit of success rate into compute units, which makes it the operator's exchange rate between accuracy and cost. $C^{\text{train}}_t$ is the one-time cost of training the adapter, and $H$ is the amortization horizon in queries. This is Minton's formula with two terms added: the representation-dependent accuracy difference, and the interference cost that ParaTool leaves unmodeled.

Compilation happens when a Hoeffding lower confidence bound on $U_t$ is positive. Demotion back to the prompt happens when the upper bound becomes negative. Eviction happens when even the in-context utility, $f_t \lambda a^{P}_t - f_t c^{P}_t$, is confidently negative, for example for tools whose presence misleads the model.

Two practical pieces make this workable. First, $a^{C}_t$ is unknown before training. We estimate it with a cheap proxy: a small adapter trained for a few steps on synthetic calls generated from the documentation, evaluated on a handful of probes. The quality of this proxy is itself something we will measure. Second, $I_t$ is measured on a fixed probe set of already-compiled tools that share an embedding neighborhood with $t$, which keeps its cost bounded.

Baselines

The naive reference point is pure in-context retrieval. Each query retrieves the top-k tool documents by embedding similarity and inserts them, with no compilation. It sets the flexibility ceiling for new tools and the compute floor we must beat. It is run with the same base model, the same retriever, and a k tuned on a held-out window.

The strongest existing method is ParaTool (ParaTool). Its reported advantage over strong in-context baselines is a 9.71% relative pass-rate improvement on Stable ToolBench and a 4.22% improvement on BFCL-V2, with FLOP reductions of up to 92.22% and 94.45%. No absolute pass rate for ParaTool is reported on Lacuna, so we will reproduce it rather than quote one. We run it in two forms. The oracle-offline form compiles every tool in advance with access to the full tool set. It is not deployable in a streaming world, but it upper-bounds per-query efficiency. The periodic-retrain form recompiles every tool seen so far every fixed number of queries, with a total training compute budget equal to what our method spends. Our method beats ParaTool if it matches periodic-retrain ParaTool's cumulative pass rate at lower total compute (training plus inference), and clearly exceeds it on newly arrived tools.

The key ablation is frequency-only promotion. It keeps the same three states, adapters, and budget, but compiles the most frequently called tools up to a capacity limit, like a popularity cache. This isolates whether the utility terms (accuracy difference, interference, token savings) add anything over counting calls. A second ablation drops the confidence bound and uses point estimates, to test whether the PALO-style caution prevents costly compile-then-demote thrashing.

Why not just…?

Why not just compile every tool, as ParaTool does? In a static benchmark this is hard to beat, and our oracle-offline baseline concedes that. In a stream, every new tool is unusable until retraining, and the adapter mixture keeps growing. ParaTool itself reports no mechanism for pruning, and its authors list overlapping tools as a source of gating interference. The streaming experiment measures both costs directly: success on tools within their first N calls, and the success of old tools as the mixture grows.

Why not just add a length penalty to the bandit of Experience-Guided Behavior Adaptation? That fixes the missing cost term but still pays tokens on every call for every useful tool, so compute scales with traffic rather than with the number of distinct tools. We include this cost-aware bandit, with all tools kept in context, as an additional baseline. If it matches our cumulative compute, the compilation step is unnecessary. That would be an informative negative result.

Why not just compile whatever is called most often? This is the real threat. If popularity and utility rank tools almost identically, frequency-only promotion is simpler and equally good. We will report the rank correlation between $f_t$ and $U_t$ across tools, and inspect the disagreements. If the benefit over frequency-only promotion is within noise, we will report that the utility accounting reduces to a popularity cache in this domain, and narrow the claim to the eviction and demotion decisions.

Why not just compress documentation into a short instruction, as Prompt-MII does? Its 12.8x token reduction was shown on classification, where the task is a decision rule. Tool calls need exact argument schemas, which paraphrase tends to lose. We test a compressed-documentation variant as a fourth representation option. If it wins on some tools, the utility accounting can simply select it for those tools.

Proposed Experiments

We build streaming versions of Stable ToolBench (2,098 tools) and BFCL-V2 (2,034 tools). Tools arrive in batches, and query popularity follows a Zipf-like distribution whose head drifts over time. Drift matters because PALO's guarantees assume a fixed distribution, and demotion is our answer to that assumption failing. Metrics are pass rate or accuracy per time window, cumulative compute including all adapter training, success on each tool within its first 50 calls, and success of old tools on probe queries as the compiled set grows. We sweep $\lambda$ to trace an accuracy–compute frontier for each method, and compare frontiers rather than single points.

Three checks decide the claim. First, on the compute-versus-pass-rate frontier, our method must dominate both pure in-context retrieval and periodic-retrain ParaTool at matched total budget. Second, it must beat frequency-only promotion specifically on the subset of tools where $f_t$ and $U_t$ disagree, and we report how large that subset is. Third, the cheap proxy for $a^{C}_t$ must predict the fully trained adapter's success well enough, at a rank correlation we set in advance, that compile decisions are rarely reversed. If the proxy fails, the method degenerates into trial-and-error compilation, and we would report that as the binding limitation.

As a secondary test of generality, we apply the same three-state accounting to the guidance library of Experience-Guided Behavior Adaptation on MMLU-Pro physics and chemistry. There, frequently selected guidance clusters are distilled into a single adapter. We ask whether the accuracy gains that paper reports (up to 26.1% absolute for Haiku 4.5 in Chemistry) survive when the guidance is moved out of the prompt.