PaperlayerView exact revision on arXiv

Source-linked AI summary

TRACER: Trajectory-Aware Tool Retrieval for LLM Agents

Tanish Kher, Sarvesh DK, Abedelkadir Asi, Sparsha Chennarayapatna Sundaresh, Dezhi Hong

arXiv:2610.21267v1cs.CLcs.AIcs.IR

TL;DR

Large tool registries raise token costs, while description-based retrieval can confuse similar tools. TRACER retrieves candidates using tool-call history and contextual evidence, with a learned balance between them. It improves selection accuracy in most tested model-environment pairs and matches task success with fewer per-step tokens.

  • Problem

    Large registries increase context and token costs, and description-based retrieval can confuse semantically similar tools.

    Source: §1 · p. 1

  • Method

    TRACER indexes observed tool-call sequences in a trie and ranks next-call candidates using transition-specific usage memory and a learned per-state blend with contextual evidence.

    Source: §1 · p. 1

  • Results

    TRACER improves selection accuracy over full-registry selection in 21 of 24 model-environment pairs and matches task success with 61% fewer prompt tokens per step.

    Source: Contributions · p. 2

  • Takeaways & Limitations

    TRACER’s small candidate sets can improve specificity and call ordering while leaving the final tool choice to the model.

    Source: §1 · p. 1, Contributions · p. 2

    TRACER assumes successful runs have already been logged; with no usage history, it falls back to vector retrieval, whose accuracy is far lower.

    Source: Limitations · p. 9

Abstract

from arXiv · show

Modern agents select tools from registries, but exposing entire registries incurs high token costs and can impair selection as they grow. We present TRACER, a retrieval front-end that indexes observed tool-call sequences in a trie and ranks continuations using a learned blend of empirical and contextual priors. On a mixed retail-and-telecom $\tau^2$ environment, TRACER improves GPT-5.4's tool-selection accuracy by 4.7 points while reducing input tokens per step by 80%, exposing just 5 of 128 tools. In autonomous full-turn execution, it matches GPT-5.4's full-registry task success with 61% fewer input tokens per step. Across six environments and four models, TRACER improves tool-selection accuracy over full-registry selection in 21 of 24 model-environment pairs, with average gains of 6 to 10 points; the three exceptions trail by at most 2.2. We analyze failures in both regimes to identify directions for future work.

1 Introduction

TRACER treats tool retrieval as sequential prediction, using execution history and contextual evidence to present a small candidate set at each step. On the mixed retail-and-telecom environment, it improves GPT-5.4’s selection accuracy while reducing per-step tokens, with gains also reported across multiple environments and models.

1 Introduction

  • Tool retrieval is often treated as independent search, although calls already made constrain which tool should come next in a multi-turn sequence.Description-based retrieval can confuse semantically similar tools, and retrieval errors can propagate to downstream execution.Source: §1 · p. 1
  • On the mixed retail-and-telecom environment, GPT-5.4’s tool-selection accuracy rises from 57.2% to 61.9%, a 4.7-point gain, while prompt tokens per step fall 80%.Figure 1 reports selection accuracy at a fixed top-k budget of five tools.Source: Figure 1 · p. 1, §1 · p. 2
  • TRACER combines full-prefix conditioning, transition-specific usage memory, and a learned per-state blend in one state-conditioned retrieval front-end.It offers a small candidate set while leaving the final choice to the model.Source: §1 · pp. 1–2, Contributions · p. 2
  • The benchmark pools retail and telecom, adding synthetic APIs and trajectories to create 128 deliberately confusable tools with per-step ground truth.A blind human study judged the benchmark more human-like than the τ 2 originals.Source: Contributions · p. 2
  • 21 of 24 model-environment pairs show improved tool-selection accuracy over full-registry selection, while task success matches with 61% fewer prompt tokens per step.Per-step context falls by 55–90%.Source: Contributions · p. 2
  • TRACER sharpens tool specificity and call ordering by surfacing similar past trajectories, removing competitor tools the model otherwise would have selected.Source: Contributions · p. 2

2 Related Work

Prior retrieval methods improve matching or incorporate relationships among tools, but often do not condition choices on the full execution history. TRACER’s related-work distinction is to make retrieval dynamic at each prefix and learn how to weight its signals for the current state.

Matching requests to fixed tool representations

Relating tools to one another

  • TGR smooths embeddings toward dependencies and ProTIP subtracts embeddings of already chosen tools, but neither conditions each choice on the ordered calls and turns that came before.TGR pools dependencies across prefixes; ProTIP does not retain the order of prior calls.Source: §2 · p. 2

Conditioning on execution

  • ToolNet uses last-call successors and bigram counts, while AutoTool adds two-call history and a fixed α=0.5 similarity blend; TRACER instead learns per-state signal weights.The reported learned-balance gains are 0.9 to 7.6 points; AutoTool’s description-based comparison is 21 points worse on API-Bank in the ablation.Source: §2 · p. 2

3 Method

TRACER treats tool retrieval as sequential prediction, using the current turn’s call prefix and conversation context to rank a small set of next-tool candidates. Its trie combines empirical transition frequencies with contextual similarity through a learned per-step blend, with vector-search fallback for specified out-of-distribution cases.

3.1 Problem definition and notation

  • TRACER asks how successful historical trajectories can identify k ≪ |R| candidates containing the gold next tool while reducing per-step token cost.The current turn’s issued calls define the prefix used for selection.Source: §3.1 · p. 3

3.2 Overview

  • At each step, TRACER locates the current prefix in a trajectory trie, scores its child tools using empirical and contextual priors, then presents the top k for the model to choose from.The model, not the front-end, makes the final tool choice.Source: §3.2 · p. 3

3.3 Trie construction

  • Each observed trajectory prefix becomes a trie node, whose children are tools observed immediately after that prefix.Each edge stores a transition probability and a mean-pooled embedding of contexts in which that transition occurred.Source: §3.3 · p. 3

3.4 The empirical prior P(t)

  • The empirical prior scores child tools by their normalized transition frequency from the current node, favoring paths more often taken in training.A smoothing constant gives candidates with no observed transition from the state a finite score.Source: §3.4 · p. 3

3.5 The contextual prior L(t)

  • The contextual prior compares the current step-context embedding with each child edge’s stored context memory, then rectifies and normalizes similarities across the children.If every similarity is non-positive, the resulting distribution is uniform.Source: §3.5 · pp. 3–4

3.6 Blending them: the learned scoring rule

  • A learned per-step rule blends the contextual and empirical log-signals, with learned weight and temperature, to rank child tools for top-k retrieval.The blend weight and temperature are produced from a five-dimensional state feature vector.Source: §3.6 · p. 4

3.7 Confidence gate and out-of-distribution fallback

  • When the trie has no candidates for a state or its score distribution is flat, TRACER replaces trie candidates with the top k tools from full-registry vector search.The flat-distribution gate uses τ = 0.20.Source: §3.7 · p. 4

4 Data and Experimental Setup

The evaluation uses six environments spanning mixed retail and telecom, banking, cross-domain APIs, and a smaller homogeneous benchmark. It draws on curated benchmark trajectories, adds validated synthetic data for the mixed benchmark, and tests two execution regimes across model and retrieval configurations.

4.1 Benchmarks

  • The primary Mixed Tau2 R&T benchmark combines real graded retail and telecom trajectories with vetted synthetic ones; the suite also includes Tau3 Banking, BFCL v3, and API-Bank.The benchmarks vary in domain and scale, from roughly 700 interconnected banking documents to a smaller, homogeneous API-Bank reference.Source: §4.1 · p. 4

4.2 Data sourcing

  • For the τ benchmarks, the authors retain successful simulations and tool-call turns, reduce each task to one canonical decision point, and use API-Bank and BFCL v3 whole.Mixed Tau2 R&T additionally includes synthetic trajectories.Source: §4.2 · pp. 4–5

4.3 Synthetic generation and validation for Mixed Tau2 R&T

  • Synthetic APIs and trajectories expand the mixed benchmark because real trajectories alone leave too few plausible alternatives; additions pass validity, non-substitutability, API-disjointness, and non-cloning gates.A blind human study selected the synthetic trajectory as human-authored in 40 of 59 decided pairs (67.8%).Source: §4.3 · p. 5

4.4 Execution regimes

  • Teacher-forcing feeds the gold call forward to isolate front-end selection, whereas free-running carries the agent’s own calls and reasoning forward, allowing errors to compound.Free-running episodes end when the grader confirms completion or after 20 steps.Source: §4.4 · p. 5

4.5 Algorithms

  • The comparisons include full-registry LLM-ONLY, context-vector retrieval, fixed-blend TRACER, and TRACER+G, which adds a small global set of high-prefix-entropy tools.TRACER-fixed isolates the learned blend by fixing it while keeping the rest of TRACER unchanged.Source: §4.5 · p. 5

4.6 Models, metrics, and protocol

  • Four models are evaluated with tool-selection accuracy and context-injection cost under teacher-forcing, and task success rate with that cost under free-running.Teacher-forcing uses five-fold cross-validation; free-running is run on Mixed Tau2 sizes for GPT-5.4 and GPT-5.4-mini.Source: §4.6 · p. 5

5 Results and Discussion

TRACER improves teacher-forced tool selection while reducing context, and can match full-registry task success in free-running execution. Results vary by setting, with out-of-trie steps and generic tools limiting gains in some cases.

5.1 Selection accuracy (Teacher-Forcing)

  • On Mixed Tau2 R&T (Large), TRACER beats the full registry for three of four models using 5 of 128 tools, including a 4.7-point gain for GPT-5.4.On Tau3 Banking, the full registry beats every trie variant for GPT-5.4 and Grok-4, while TRACER+G recovers the benchmark outright for the other two models.Source: §5.1 · p. 6

5.2 Context-injection cost

  • Figure 3 compares accuracy and context cost across budgets; on Mixed Tau2 R&T (Large), TRACER injects 2.8k tokens per step versus 14.2k for the full registry, an 80% reduction.Savings range from 31% on Tau3 Banking to 90% on BFCL v3; as the Mixed Tau2 pool grows, the reduction rises from 55% to 80%.Source: Figure 3 · p. 6, §5.2 · p. 6

5.3 End-to-end task success (free-running)

  • On GPT-5.4, TRACER reaches +0.1 points on Large at 23% of the registry, but falls below LLM-ONLY at 8 of 12 budgets and parity occurs only at the largest.Free-running results also show that recall matters more under compounding errors; early misses can move execution to unseen prefixes and trigger vector-search fallback.Source: §5.3 · p. 7

5.4 Why the gains happen

  • TRACER reduces generic-hub errors on the five order-management APIs: the trap rate falls from 36.4% with LLM-ONLY to 16.4%.For prepaid return labels, the contextual prior ranked the destructive return-initiation tool ninth, keeping it out of the candidate set while the model chose the precision tool.Source: §5.4 · p. 7
  • In banking, the trie withholds the sensitive write until its required unlock call, while edge memory matches the conversation to the unlock transition.The illustrated Tau3 Banking case uses GPT-5.4 with k=10.Source: Figure 4 · p. 7, §5.4 · p. 8

5.5 When the global set is needed

  • TRACER+G recovers 5.8 points on Tau3 Banking, where generic tools dominate, but adds distractors and underperforms TRACER on the τ2 mixes and BFCL v3.Depending on the model, its Tau3 Banking result lands between 3.0 points below and 4.0 points above LLM-ONLY.Source: §5.5 · p. 8

5.6 Ablations

  • On API-Bank with GPT-5.4-mini, the description-only Trie-Bayesian variant scores 21 points below TRACER-fixed, while the contextual prior moves performance from below to above LLM-ONLY.This ablation contrasts contextual edge embeddings with static tool-description similarity under the same trie and fixed blend.Source: §5.6 · p. 8
  • The learned blend averages w=0.019 on Mixed Tau2 R&T (Large), while a last-two-call trie gains 1.5–2.9 points in two settings, within one standard deviation.The shorter key also reduces out-of-trie steps to 9.6% from 12.4%; these results leave key depth as a parameter for future testing.Source: §5.6 · p. 8

6 Conclusion and Future Work

TRACER combines full-prefix history, transition-specific context, and learned weighting to improve selection while reducing token use. Its fixed budget and global set remain candidates for adaptation, and out-of-trie steps motivate a full-registry fallback.

6 Conclusion and Future Work

  • TRACER improves selection accuracy over full-registry selection in 21 of 24 model-environment pairs while cutting per-step tokens by 80% on the primary testbed.Its cost tracks the budget rather than the registry.Source: §6 · p. 8
  • The budget k and global set are fixed despite varying by domain and model, and free-running prefixes roughly triple the share of steps outside the trie.The authors note that the method did not carry gains at most GPT-5.4 budgets.Source: §6 · p. 8
  • Presenting the full registry only on out-of-trie steps would make coverage exact and lift selection accuracy there by 38 points on average while retaining 84% of the token reduction.The authors say this would likely translate to higher task success.Source: §6 · p. 9

Limitations

The limitations concern cold-start dependence, an untuned trie depth, grader-controlled episode endings, and selection accuracy's reliance on one recorded tool order.

Limitations

  • A registry without logged successful runs has no trie to consult, so every step falls to a less accurate vector fallback.The authors say the method assumes deployment after successful runs have been logged; fixed-size corpora cannot show how quickly the trie becomes useful.Source: Limitations · p. 9
  • The full current-turn prefix is used as the trie key, but that depth was not tuned and a shorter key is not obviously worse.The authors identify trie depth as a parameter that may not be optimal.Source: Limitations · p. 9
  • Free-running episodes end when the grader confirms completion or at 20 steps, so task success does not measure whether an agent knows when to stop.It measures whether the front-end supplies tools needed to reach the goal.Source: Limitations · p. 9
  • Selection accuracy scores against one recorded ordering, so a valid alternative tool order can count as wrong.Accept-sets and free-running task success bound this distortion.Source: Limitations · p. 9

A.1 Benchmark statistics

The appendix includes a benchmark-statistics table, but the supplied passage does not report its values.

A.1 Benchmark statistics

  • Table 7 is identified as reporting benchmark statistics, with no statistics specified in the supplied passage.Source: Table 7 · p. 11

A.2 Trajectory provenance

The appendix identifies separate provenance tables for retail and telecom turns and describes the domain and model breakdown.

A.2 Trajectory provenance

  • The breakdown covers retail and telecom turns by model and reports the share of each model’s steps with a teacher-forced reasoning trace.Retail turns are real τ 2 trajectories; telecom turns are synthetic derivations credited to the model whose scraped submission seeded them.Source: §A.2 · p. 11
  • Retail turn provenance is presented in Table 8.Source: Table 8 · p. 11
  • Telecom turn provenance is presented in Table 9, whose caption identifies in-house turns as “Authored.”Source: Table 9 · p. 11

A.3 Curation battery prompts

The curation battery uses topic-agnostic LLM-judge rubrics to screen Mixed Tau2 R&T and BFCL v3. The reported screening differs by benchmark: a full gate battery for Mixed Tau2 R&T and C10 alone for BFCL v3.

A.3 Curation battery prompts

  • Each curation gate uses a topic-agnostic rubric scored by an LLM judge.Source: §A.3 · p. 11
  • Mixed Tau2 R&T was screened with C1–C7 and C10, with all gates blocking except diagnostic C3 and policy-level C6.Per-gate rates are reported in Table 10.Source: §A.3 · p. 11, Table 10 · p. 11
  • BFCL v3 was screened with C10 alone using a three-sample majority vote over 731 turns; 702 turns (96.0%) had a unique gold tool and no combining-induced substitutes.Source: §A.3 · p. 11

A.4 Reproduced prompts

This appendix documents TRACER’s prompts, evaluation protocols, weight-head design and diagnostics, qualitative behavior, and limitations, alongside how trajectories, policy documents, and the free-running environment were constructed. It also reports banking accuracy patterns, clarifies the out-of-trie coverage measure, provides budget sweeps, and describes AI-assistant use and result verification.

A.4 Reproduced prompts

  • The C3 prompt judges dialogue language rather than topic or masked tool details, while the regular-split protocol uses broadened retail and telecom policy documents routed by domain.The reproduced retail policy excerpt covers authentication, escalation, and order operations; the telecom document is its broadened counterpart.Source: §A.4 · p. 12

A.5 Example synthetic trajectories

  • In the blind pair, both the reviewer and C3 judge chose the lower conversation as human-authored, while synthetic turns preserve a more natural register than the genuine benchmark side.The three reviewers received C3’s criteria, rated confidence, and were not told beforehand that the task was a research study.Source: §A.5 · p. 14, Figure 5 · p. 14, §A.6 · p. 14

A.6 Human study protocol

  • Three unpaid institutional colleagues reviewed fictional dialogue, were debriefed afterward, and consented to use of their judgments; the protocol collected no demographics and had no ethics-board review.Pairs rated “not sure” were excluded from the 59.Source: §A.6 · p. 14

A.9 Feature selection and weight-head ablations

  • The PCA-5 and tanh MLP heads stay within 0.3 points of the hand-picked linear head, which beats constant w=0.5 by 18 points.The five-feature head spans prior confidence, edge-memory evidence, and context scale; its parameters are fit with Adam over 500 epochs using cross-fit folds.Source: §A.8 · p. 15, Table 12 · p. 16, §A.9 · p. 16

A.10 What the head learns

  • Tables 13 and 14 report learned blend weights by environment and logistic-head coefficients by registry size, respectively; TRACER and TRACER+G fits coincide within 0.006 on every feature.Small w means the contextual prior carries the ranking, and the table reports fold means and standard deviations.Source: §A.10 · p. 16, Table 14 · p. 16, Table 13 · p. 16

A.11 Trie key depth

  • The last-2 trie key and full current-turn prefix are indistinguishable on covered steps; their difference is coverage rather than ranking.The last-2 index keys on the two most recent calls, while edge memories still mean-pool the whole conversation and the learned blend is unchanged.Source: §A.11 · pp. 16–17, Table 15 · p. 17

A.12 Qualitative examples

  • In the retail example, LLM-ONLY performs an irreversible return as a prerequisite, but the trie excludes that tool because no observed transition leads to it from the current state.The customer asked only for a prepaid return label.Source: §A.12 · p. 17, Figure 7 · p. 17

A.13 Compute, software, and artifacts

  • TRACER’s retrieval failures can hide needed tools, and its trie inherits observed-trajectory biases that may underserve rare legitimate sequences; Table 16 describes out-of-trie frequency and selection degradation.The confidence gate and out-of-trie fallback bound the retrieval-failure risk.Source: §A.13 · p. 17, §A.14 · p. 17, Table 16 · p. 18

A.14 Out-of-trie coverage

  • At k=10, the out-of-trie figure reports the share of steps without a matching prefix node, with parentheses showing selection accuracy on those steps minus overall accuracy in Table 2, in points.The figure’s large value is the unmatched-step share; the parenthetical value is the accuracy difference.Source: §A.14 · p. 18

A.15 Constructing the free-running environment

  • The free-running environment reuses shipped executable benchmarks and builds executors, state stores, and graders for synthetic tools, with both tracks using the same per-turn reference.A shared grader is routed per example; missing database arguments return a sentinel so logs retain where failure began.Source: §A.15 · p. 18

A.16 Banking accuracy by tool type

  • Banking accuracy was given back on read, write, verification, and routing calls; a wrong banking tool can skip a prerequisite rather than waste a call.A gated-unlock call is the unlock:X call required before a sensitive tool X.Source: §A.16 · p. 18
  • Gated-unlock calls gained +0.098 (0.148 →0.246), shell/grep filesystem calls +0.069, and knowledge-base retrievals +0.054, but banking accuracy fell −0.023 overall.The comparison is TRACER+G − LLM-ONLY; banking gains concentrate on tool types where the correct call is not obvious.Source: Table 17 · p. 18, §A.16 · p. 18

A.17 Full budget sweeps

  • The appendix supplies full teacher-forcing tool-selection accuracy sweeps for Mixed Tau2 R & T, Tau3 Banking, API-Bank, and BFCL v3.The tables report across-fold standard deviations; Tau3 Banking runs to k=10 and API-Bank to k=5.Source: Table 18 · p. 19, Table 19 · p. 19
  • Full context-injection-cost sweeps cover teacher-forcing and free-running settings, alongside free-running task-success results.The cost tables report reduction against LLM-ONLY and mean prompt tokens per decision step; free-running cost differs by serving model.Source: §A.17 · pp. 18, 20, Table 20 · p. 20, Table 21 · p. 20

A.18 Use of AI assistants

  • The authors report that they designed and verified the experimental design, results, and reported numbers, while AI assistants supported software development, text editing, formatting, and two appendix sections.The evaluated models, frozen embedder, and LLM judges are described as method components rather than writing assistance.Source: §A.18 · p. 21

Related papers

Loading 2610.21267v1…