Parametric retrieval enables LLMs to retrieve tools implicitly by assigning each API a unique virtual token and training the model to generate it via constrained beam search. Toolsense shows that this regime has two critical drawbacks: it destroys parametric tool knowledge during training, and its beam-search decoding is too slow for real-time deployment. We introduce TRACE (Tool Retrieval via Augmented Chain-of-thought and Enterprise rules), a two-stage curriculum that resolves this dissociation. Stage 1 reuses the multi-format memorization SFT from ToolSense to seed tool knowledge with LoRA. Stage 2 is our core contribution: the model is trained to emit a thinking trace before producing a JSON list of tool tokens, using two data sources -- RRB pairs from ToolSense and queries synthesized to target business rules curated by domain experts -- both augmented with reasoning traces. This training objective preserves Stage 1 MCQ and QA probing accuracy while enabling single-beam greedy decoding at production latency. Evaluated on a combined enterprise catalog of 8,300+ tools across two enterprise product lines, TRACE training for Stage 2 not only preserves but improves tool understanding: MCQ accuracy gains +3.2 pp and QA probing gains +9 pp over Stage 1. On retrieval, TRACE achieves ~86% recall on Domain A and ~60% on Domain B -- compared to embedding baseline performance of ~27% & ~52% -- both with single-beam greedy decoding, making it directly deployable at production latency.
Figures & tables
Figure 1: Methodology for Generating Data Dtrain for Stage 2 Trace training
Axis
Levels
F (format)
a flat, b bare-hier, c wrapped-hier
M (Stage 1)
∅ none, m memo, mr reasoning memo
R (Stage 2)
∅ none, n non-reasoning, r reasoning, r+R reasoning + rules
Table 1: Configuration grid.
Figure 2: In-distribution probing. MCQ ts (left) and QA ts (right) accuracy across the four Stage-2 modes.
Domain A
Domain B
Method ( F,M,R )
R@1
R@10
R@1
R@10
text-embedding-3-large
13.74
27.48
27.59
52.71
ToolGen (c,m,n)
45.0
87.0
35.8
78.0
Trace -R (c,m,r)
40.5
74.0
46.3
79.7
Trace (c,m,r+R)
48.9
86.3
36.6
77.2
Table 2: Fair retrieval comparison between non-reasoning & reasoning variants under 10-beam constrained decoded inference. F=c for all variants.
Domain A
Domain B
Method ( F,M,R )
R@1
R@gen
R@1
R@gen
Trace -R (c,m,r)
32.1
53.4
56.1
67.5
Trace (c,m,r+R)
51.1
85.5
43.1
60.2
Table 3: Comparison of reasoning retrieval variants under no constrained decoding and single beam with JSON list of tool tokens as output. F=c for all variants.
Figure 3: Stage 2 Rule-grounded Pareto sweep on F=a , M=m and R=r+R where we vary the number of queries per rule.
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Latency comparison of Trace (c,m,r+R(12−rep)) on two inference models using vLLM on a single H200, 100 Domain-A PRB queries (log axes).
F
M
R
MCQ ts -A
MCQ ts -B
QA ts -A
QA ts -B
MCQ expert
a
m
∅
52.3 [47.0, 57.7]
50.2 [45.5, 55.5]
80.0 [74.5, 85.5]
67.8 [62.7, 72.2]
63.4
m
n
27.3 [22.7, 32.7]
29.8 [25.2, 34.2]
51.5 [44.5, 58.5]
52.5 [47.5, 57.0]
34.8
m
n → r
65.0 [60.0, 70.7]
71.5 [67.2, 76.0]
76.5 [71.0, 82.0]
80.0 [76.0, 83.8]
49.8
m
r
68.7 [63.7, 73.7]
70.0 [65.5, 74.5]
87.5 [83.0, 91.5]
85.5 [82.0, 88.8]
59.5
b
m
∅
43.3 [37.3, 49.0]
37.2 [32.8, 42.0]
61.5 [54.5, 67.5]
55.8 [50.7, 60.8]
58.6
m
n
28.3 [23.3, 33.3]
27.0 [22.5, 31.8]
45.5 [38.5, 52.5]
43.0 [38.2, 48.0]
30.0
Appendix
Table 4: Token-format sweep. Probing accuracy across the three token formats and four Stage-2 modes, all with non-reasoning Stage-1 ( M=m ). Non-reasoning retrieval ( R=n ) collapses every probe across all formats; reasoning retrieval ( R=r ) recovers it. Bolting reasoning onto a non-reasoning checkpoint ( R=n→r ) only partially recovers MCQ accuracy and fails entirely for F∈{b,c} .
F
M
R
MCQ ts -A
MCQ ts -B
MCQ expert
a
∅
r
74.0 [69.0, 78.7]
81.8 [78.0, 85.2]
67.8
a
m
r
68.7 [63.7, 73.7]
70.0 [65.5, 74.5]
59.5
a
mr
r
62.3 [57.0, 68.0]
73.5 [69.0, 77.5]
65.2
b
m
r
46.3 [41.0, 52.0]
44.0 [39.2, 48.8]
50.9
b
mr
r
62.0 [56.3, 67.3]
71.5 [67.0, 76.0]
63.2
c
m
r
57.7 [52.3, 63.0]
67.8 [63.2, 72.2]
61.5
Appendix
Table 5: Stage-1 ablation under reasoning retrieval. Holding R=r fixed, we vary M∈{∅,m,mr} to isolate Stage-1’s contribution. The (a,∅,r) row is the no-Stage-1 ablation: it recovers MCQ expert to within 1 pp of the base model, but has the lowest retrieval. Reasoning Stage-1 ( M=mr ) outperforms non-reasoning Stage-1 ( M=m ) on MCQ expert for every F .
F
M
R
MCQ ts -A
MCQ ts -B
MCQ expert
a
m
r
68.7 [63.7, 73.7]
70.0 [65.5, 74.5]
59.5
a
m
r + R (3q)
66.7 [61.3, 72.0]
62.5 [57.7, 67.2]
59.2
a
m
r + R (6q)
68.0 [63.0, 73.7]
66.2 [61.7, 70.8]
58.1
a
m
r + R (9q)
66.3 [61.0, 71.7]
62.0 [57.5, 67.0]
57.9
a
m
r + R ( app )
62.3 [56.3, 67.7]
66.8 [61.8, 71.5]
—
a
m
r + R ( rep )
65.7 [60.3, 71.0]
63.0 [58.2, 68.0]
56.2
Appendix
Table 6: Rule-grounded scaling. Probing accuracy along the rule-data axis. Rows above the rule entries reproduce the no-rules baseline (F,m,r) for direct comparison. Held-out MCQ expert falls monotonically with rule-data volume; in-distribution probes are stable.
Domain A
Domain B
F
M
R
R@1
R@5
R@10
R@1
R@5
R@10
Non-reasoning retrieval baselines
a
m
n
39.7 [31.3, 48.1]
80.9 [74.0, 87.8]
91.6 [86.3, 96.2]
31.7 [23.6, 40.7]
69.9 [61.8, 77.2]
80.5 [73.2, 87.0]
b
m
n
44.3 [35.9, 52.7]
80.2 [73.3, 86.3]
86.3 [80.2, 91.6]
40.7 [31.7, 49.6]
70.7 [63.4, 77.2]
79.7 [73.2, 86.2]
c
m
n
45.0 [36.6, 54.2]
80.9 [74.0, 87.0]
87.0 [80.9, 92.4]
35.8 [27.6, 43.9]
73.2 [65.9, 80.5]
78.0 [70.7, 85.4]
Trace -class re-evaluations under constrained decoding (suffix ∗ )
Appendix
Table 7: Constrained-decoded retrieval (R@1, R@5, R@10). Includes the non-reasoning retrieval baselines (⋅,m,n) across all three token formats and the apple-to-apple re-evaluations (suffix ∗ ) of two Trace -class reasoning checkpoints.
Domain A
Domain B
F
M
R
R@1
R@gen
R@1
R@gen
Non-reasoning then reasoning (M=m,R=n→r)
a
m
n → r
44.3 [35.9, 53.4]
58.0 [49.6, 66.4]
44.7 [35.8, 53.7]
52.0 [43.1, 61.0]
b
m
n → r
48.9 [40.5, 57.3]
61.8 [53.4, 69.5]
56.9 [48.0, 65.9]
63.4 [54.5, 71.5]
c
m
n → r
34.4 [26.7, 42.7]
45.0 [36.6, 53.4]
48.0 [39.0, 56.9]
54.5 [45.5, 63.4]
Reasoning retrieval, no rules (M=m,R=r)
Appendix
Table 8: Single-beam reasoning retrieval (R@1, R@gen). Each row is a checkpoint evaluated by letting the model commit to its own answer set; R@gen is recall over the generated set. Sections group runs by (M,R) .
Figure 5: Rule grounding corrects ambiguous tool routing. Without rule grounding (left), the model reasons plausibly but selects the wrong tool because it lacks the domain routing constraint. After rule grounding (right), the reasoning trace explicitly cites the business rule, producing the correct retrieval.
No. of Choices
No. of Questions
2
58
3
74
4
301
5
21
Total
454
Appendix
Table 9: Distribution of answer choices in the MCQ expert dataset.
Domain A
Domain B
Rules
20
103
Avg. confusables
4.2
2.8
Avg. length (words)
∼ 180
∼ 120
Appendix
Table 10: Business rule catalog statistics.
Method
Domain A R@gen
Domain B R@gen
Hybrid (no rules)
67.2
54.5
Hybrid (with rules)
66.4
56.1
Trace (c,m,r+R)
85.5
60.2
Appendix
Table 11: Hybrid retrieval + LLM reranker vs. Trace on PRB.
Benchmark
Rule cited (%)
Correct retrieval (%)
PRB A
82.4
71.2
PRB B
79.5
75.3
Appendix
Table 12: Human labelling study: when the ground-truth query requires a business rule, how often does Trace correctly cite it, and what is the corresponding retrieval accuracy.
Metric
Domain A
Domain B
Avg ∣A^(q)∣
2.63
2.01
Precision
34.8
35.1
Recall (R@gen)
85.5
60.2
F1
48.6
42.4
Off-vocabulary rate (%)
1.04
1.96
Appendix
Table 13: Extended retrieval metrics for Trace (c,m,r+R) under single-beam greedy decoding on PRB.
Large language models deployed as agents over large tool catalogs face a critical tool-retrieval bottleneck. As embedding-based retrieval approaches rely on compact encoders that may under-capture specialized tool semantics, parametric tool retrieval addresses this by encoding each tool as a virtual token appended to the LLM vocabulary, fine-tuned in two stages (memorization then retrieval SFT) to use the LLM as a retriever, achieving strong performance on standard ToolBench retrieval benchmarks. Yet these benchmarks use verbose, fully-specified queries, and their evaluation applies constrained decoding that restricts outputs to valid token paths, neither reveals whether the model actually understands its tools. We introduce ToolSense, an open-source LLM-powered diagnostic framework that takes any tool catalog as input and automatically generates three benchmarks: a Realistic Retrieval Benchmark (RRB) with queries at three ambiguity tiers, an MCQ probing benchmark, and a QA probing benchmark. Applying ToolSense to ToolBench (~47k tools) and evaluating five parametric model training configurations reveals a knowledge-retrieval dissociation: on RRB queries, several configurations collapse by ~50-64 percentage points compared to fully-specified ToolBench benchmarks, falling below the embedding-model baseline. Additionally, despite strong retrieval performance, some models score near-random on factual probes, suggesting a knowledge-retrieval dissociation. We open-source the ToolSense framework and the ToolBench diagnostic benchmarks at https://github.com/SAP/toolsense.
Ashutosh Hathidara, Sai Shruthi Sistla, Sebastian Schreiber +1
While most efforts to improve LLM-based tool-using agents focus on the agent itself - through larger models, better prompting, or fine-tuning - agent performance increasingly plateaus due to the quality of the tool interfaces these agents consume. Tool descriptions are often written for human developers and tolerate ambiguity that agents cannot resolve, particularly as the number of candidate tools grows. Existing approaches to improving tool interfaces (1) require re-running a multi-stage per-tool pipeline - synthesizing queries, executing an agent to collect trajectories, annotating trajectories, and prompting a strong LLM multiple times - for every API that enters the catalog, and (2) typically optimize each tool independently, limiting scalability and generalization to unseen tools. We propose Trace-Free+, a curriculum learning framework that progressively transfers supervision from trace-rich settings to trace-free deployment, encouraging the model to internalize reusable patterns of what makes a tool description effective. To support this approach, we construct a large-scale dataset of high-quality tool interfaces derived from real-world APIs through a principled data synthesis workflow. Experiments on widely adopted benchmarks show that Trace-Free+ improves robustness as tool catalogs scale to 150+ candidates - in scaling experiments, reducing accuracy degradation by 29.23% and improving average query-level success by 60.89% on StableToolBench - generalizes across domains without retraining, and provides complementary gains on top of agent fine-tuning.
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 τ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.