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.