Historical Trace Coverage for Regression Selection in Stochastic Tool-Using Agents

Executive Summary

I investigated whether previous execution traces can safely identify which agent tasks need to be rerun after one tool implementation changes. The tempting rule is simple: if a task called the changed tool before, rerun it; otherwise, reuse its old result. This resembles dynamic regression-test selection, but an LLM agent can take different tool paths when the task and system are unchanged. A stored trace therefore records what happened once, not every tool the task may reach.

I ran a Phase 0 empirical study using four-trial public trajectories from the τ²-bench airline and telecom environments [1]. The study covered 50 airline tasks and 114 telecom tasks for each of two agents, Claude Opus 4.5 and GPT-5.2. Across the four identical trials, only 16.0% to 44.7% of tasks used exactly the same tool set, depending on model and domain. Between 22.4% and 35.3% of observed task-tool relationships appeared in only one to three of the four trials. Tool exposure was therefore meaningfully stochastic.

Using held-out trials, a selector based on one historical trace missed 4.5% to 10.0% of task-tool relationships later observed in the held-out runs. The risk was concentrated in a small number of optional lookup tools. For example, get_bills_for_customer had a 0.0% miss rate for Claude Opus 4.5 but 36.4% for GPT-5.2. Across 19 tools shared by both models, the mean absolute difference in miss rate was 10.7 percentage points. Tool risk was not a stable property that could be assigned once and reused across agents.

The proposed method contribution did not survive. A frequency-based selector using two traces improved Recall@10% over a one-trace identity baseline by only 0.8% to 9.0% relative. Taking the union of tools observed across repeated runs was usually worse under a fixed selection budget because it enlarged the candidate set without ranking it well. AgentAssay had also established that coverage from stored traces is a lower bound on achievable coverage [2]. I therefore could not honestly claim a new selector or a new problem class.

Main lesson. Historical traces are useful but incomplete evidence. The valuable result is the measurement of when and where trace-based selection misses dependencies, not a claim that I invented a better regression selector.

Figure 1. Percentage of tasks with identical tool sets across four trials for each model and domain. Tool exposure varies substantially even when the task and environment are unchanged.

Research Arc and Verification

Ideation and exploration

The initial idea was to adapt dynamic regression-test selection: reuse an old result when a task had not previously reached a changed tool. I first checked whether the proposed change class was real by inspecting source-history transitions in three Model Context Protocol reference servers. I then examined repeated public agent trajectories because a selector cannot be safe if a task's tool exposure is effectively fixed only in one observed run.

Understanding

The decisive question was not whether traces varied, but whether repeated traces produced a useful selection rule under a fixed budget. I therefore compared a one-trace identity baseline, two-trace union, two-trace frequency ranking, and random selection at the same 10% budget. The method claim would have survived only if frequency ranking made a substantial and reproducible improvement over the simple identity baseline.

Verification and red team

• The source-history claim was checked against concrete diffs rather than interface metadata alone.
• Historical and held-out trials were separated when measuring missed task-tool relationships, preventing the same run from both selecting and defining reachability.
• The selector was compared against random selection and the simpler one-trace identity baseline.
• I explicitly did not treat a missed tool exposure as proof of an outcome regression. No V0-to-V1 causal change experiment was run.
• Retail trajectories were excluded from the clean analysis because their outcome oracle relied heavily on an experimental language-model judge.

The record therefore supports a measurement of trace incompleteness and weak ranking headroom. It does not support a claim that historical traces cause downstream regressions or that frequency ranking is a useful general selector.

Motivation & Context

Tool-using agents are evaluated by running tasks that may involve multiple model turns, simulated users, stateful tool calls, environment execution, and outcome checking. When a single tool changes, rerunning the entire suite is the safest option, but it can be expensive.

Traditional dynamic regression-test selection often uses dependencies observed in previous executions. A test that did not touch changed code can sometimes be skipped. I wanted to know whether the same idea remains safe for an LLM agent, where the dependency between a task and a tool is partly chosen at runtime by a stochastic model.

The exact decision I studied was:

Input: task T, changed tool C, exact change ΔC, and old traces H_T
Output: RECHECK or REUSE

The dangerous error is REUSE when a new execution could reach the changed tool and produce an evaluation-relevant change.

This work connects to my broader interest in infrastructure for reliable production agents. The deeper systems question is how much operational evidence remains trustworthy after one component changes. This pilot tested one narrow evidence source: historical tool-call traces.

Hypotheses

H1: Contract-preserving tool changes are common enough to matter

Tool implementations often change while their name, description, and input schema remain fixed. Interface-only change datasets may miss this class.

Falsification condition: fewer than 5% of behavior-changing commits in a representative tool-server history are contract-preserving implementation changes.

H2: Task-to-tool exposure is stochastic

Repeated executions of the same task will not always expose the same tool set.

Falsification condition: almost all tasks and task-tool pairs are stable across four repeated runs.

H3: More historical traces reduce unsafe misses

Increasing the historical evidence budget from one trace to two or four traces should reduce the chance of missing a reachable task-tool relationship.

H4: Frequency-aware evidence materially improves selection

A selector using how often a task reaches a tool should meaningfully outperform a one-trace identity baseline under the same selection budget.

Falsification condition: improvement is too small to survive sampling noise or justify the added executions.

H5: Tool-level risk is stable across agents

Optional or high-variance tools might have similar historical miss rates across models, allowing a reusable risk table.

Falsification condition: miss rates vary substantially between agents for the same tools.

Methods & Experiments

Experiment 1: Is the proposed change class real?

Hypothesis tested: H1.

I examined 4,161 commits from the source histories of the official Model Context Protocol reference servers fetch, git, and time. I classified 185 relevant transitions and separated behavior-changing commits from linting, typing, packaging, and dependency-only changes using a pre-stated conservative rule.

A change counted as contract-preserving when tool behavior changed but the exposed tool name, description, and input schema remained unchanged.

Success criterion: at least 5% of behavior-changing commits meet this definition.

Sanity check: I inspected concrete diffs rather than inferring behavior only from metadata. One verified example, commit 1ac3c1da, changed the returned git_diff text while preserving its exposed interface.

Experiment 2: How stable is tool exposure?

Hypotheses tested: H2 and H5.

For each task, I compared the set of tools called across four runs. I also constructed task-tool pairs and counted whether each pair appeared in one, two, three, or all four trials.

The main baseline was exact tool-set agreement. This is deliberately stricter than final task success: two executions can both succeed while using different tools.

Experiment 3: How often does historical coverage miss a reachable dependency?

Hypothesis tested: H3.

I used trials 1 and 2 as historical selector evidence and trials 3 and 4 as held-out reachability evidence. A historical miss occurred when a task-tool pair was absent from the selected historical traces but appeared in a held-out execution.

This design reduces circularity because the same run is not used both to select and to define the reachable set. It still provides only a lower bound: a pair absent from all four observed runs may remain reachable in an unobserved run.

I measured historical miss at one and two observed runs. Values reported for four runs were Jeffreys-posterior estimates, not direct measurements. Four available trials cannot both provide four historical observations and an independent held-out ground truth.

Experiment 4: Does repeated evidence produce a better selector?

Hypothesis tested: H4.

I compared four selectors at a 10% task budget:

The primary metric was pooled Recall@10% over candidate changed tools.

Success criterion: frequency evidence should provide a substantial, reproducible improvement over Identity R1.

Results

Contract-preserving changes were common

The change class passed the 5% existence gate. A metadata-only evolution benchmark would miss many of these changes because the exposed schema does not change.

Tool exposure varied across identical runs

An earlier pilot reported mean exact tool-set agreement of 0.248. The public-trajectory replication gives the claim provenance while also showing that stability depends strongly on model and domain.

One historical trace missed reachable task-tool relationships

The direct R=1 to R=2 comparison supports H3: a second historical trace reduced observed misses in all four settings. The estimated R=4 column is not directly comparable and should not be treated as a measured monotonic continuation.

Risk was concentrated but model-dependent

Across 19 shared tools, the mean absolute cross-model difference was 10.7 percentage points and the maximum was 36.4 points. H5 was not supported.

These are diagnostic high-variance examples, not random qualitative samples. The stored report did not preserve a random set of complete conversations, so I do not manufacture one here.

The proposed selector added little

Union R2 was at or below Identity R1 in three of four settings. Frequency R2 helped, but the improvement was small and inconsistent. H4 was not supported strongly enough for a method paper.

Figure 2. Recall@10% for one-trace identity and two-trace frequency selectors. Repeated traces did not create a strong ranking method under a tight budget.

Analysis: Why It Failed (or was inconclusive)

The original project aimed to justify a new change-aware selector. That contribution failed for five concrete reasons.

1. The core theoretical warning was already known. AgentAssay had already formalized stored trace coverage as a lower bound and stated that candidate-version regression testing is not trace-first compatible in general.
2. The proposed improvement was too small. Frequency evidence improved Recall@10% by only 0.8% to 9.0% relative. This is not convincing headroom for a new method without a much larger study.
3. Repeated coverage and budgeted ranking are different objectives. Unioning more traces reduces the chance of missing a dependency, but it also expands the selected set. Under a small budget, that can dilute the ranking and reduce recall.
4. No V0 to V1 causal experiment was run. The study measured exposure misses, not actual post-change reward regressions. A missed tool exposure does not necessarily change the final outcome. The changed branch may not be triggered, the tool difference may be harmless, or the agent may recover.
5. The outcome oracle was not uniformly trustworthy. Retail depended heavily on an experimental language-model judge. Twenty telecom tasks used ACTION as part of their reward basis, effectively treating one assumed action trajectory as uniquely correct. A cleaner objective pool contained 50 airline tasks and 94 telecom tasks.

Several alternative explanations remain. Variation may come partly from the simulated user rather than only the agent. The results may change with decoding settings or different model releases. Optional lookup tools may appear risky because their use is weakly constrained by the task wording, not because of a general property of lookup tools.

The negative result is still informative. It shows that adding more historical traces is not equivalent to producing a useful priority order, and that an observed path should not be treated as the task's specification.

Key Insight

Tasks and outcomes matter more than tool ordering

A tool-call sequence is one realization of an agent's behavior, not necessarily the task's correct answer. Two agents may call tools in different orders and still produce the same correct database state and required communication. Conversely, two traces may have similar tool sequences but produce different final states.

This became concrete during the oracle audit:

• Airline tasks could be evaluated through communication and database state.
• Ninety-four telecom tasks could be evaluated through environment assertions.
• Twenty telecom tasks also used an assumed action sequence, which risks penalizing valid alternative paths.
• Retail relied on an experimental natural-language judge and was not suitable for the clean first study.

The important distinction is therefore:

Task identity defines what must be achieved.
Outcome checks determine whether it was achieved.
Tool traces reveal one path taken to achieve it.

Some behaviors were close to deterministic: several tools had a 0% one-trace miss rate in both agents. Others were stochastic and highly model-dependent. The correct research object is not "the agent has one stable tool order." It is the distribution of possible paths for a task and whether a component change can alter an evaluated outcome.

What I Learned & Research Skill Demonstrated

• I converted a vague claim about agent stochasticity into measurable task-tool exposure and held-out miss rates.
• I distinguished a dependency observation from an outcome oracle.
• I used held-out trials to reduce circularity between selection evidence and ground truth.
• I audited the benchmark's reward basis instead of assuming every task had an objective oracle.
• I tested a proposed method against the strongest simple baseline and accepted that the improvement was too small.
• I corrected my own planning assumptions, including an overly pessimistic bound and an unsuitable mutation target.
• I learned to separate a useful empirical characterization from a novel method contribution.

Open Questions & Future Directions

1. Propagation to outcomes: When a historical trace misses exposure to a changed tool branch, how often does the miss produce a measurable reward or state regression?
2. Controlled V1 mutations: Apply realistic implementation-only changes to high-variance tools such as get_data_usage and evaluate repeated V0 and V1 outcomes on the 144-task objective pool.
3. Source of stochasticity: Separate variation caused by the agent from variation caused by the simulated user.
4. Path equivalence: Develop an outcome-preserving way to group distinct tool paths without treating one order as uniquely correct.
5. Deployment evidence: Test whether production traces show the same concentration of risk in optional tools.

The original power calculation suggested 13 repetitions per arm for detecting a pass-rate drop of 0.50 from a 0.90 baseline with one-sided Fisher testing, alpha 0.05, and power 0.80. Smaller effects become expensive: 30 repetitions for a 0.30 drop, 56 for 0.20, and 89 for 0.15. These numbers should be recomputed after the exact V1 mutation and baseline pass rate are fixed.

Appendix

Definitions

Source artifacts recorded in the Phase 0 report

• bound.md and bound.json: analytic bounds, exact Fisher power, and simulated selector surfaces
• change_class.md and mining_official.json: MCP source-history mining
• system.md and system_manifest.json: benchmark freeze, task counts, tool inventory, and oracle analysis
• exposure.json: per-task per-tool counts across four trials
• select_eval.json: held-out miss and Recall@K results

References

1. V. Barres, H. Dong, S. Ray, X. Si, and K. Narasimhan, “τ²-Bench: Evaluating Conversational Agents in a Dual-Control Environment,” arXiv:2506.07982, 2025. Online. Available: https://arxiv.org/abs/2506.07982
2. V. P. Bhardwaj, “AgentAssay: Token-Efficient Regression Testing for Non-Deterministic AI Agent Workflows,” arXiv:2603.02601, 2026. Online. Available: https://arxiv.org/abs/2603.02601