ToolSpec: Accelerating Tool Calling via Schema-Aware and Retrieval-Augmented Speculative Decoding

Heming Xia; Yongqi Li; Cunxiao Du; Mingbo Song; Wenjie Li

cs.CLApr 15, 2026

ToolSpec: Accelerating Tool Calling via Schema-Aware and Retrieval-Augmented Speculative Decoding

Authors: Heming Xia, Yongqi Li, Cunxiao Du, Mingbo Song, Wenjie Li

Organizations: Department of Computing, The Hong Kong Polytechnic University · Peking University

Abstract

Tool calling has greatly expanded the practical utility of large language models (LLMs) by enabling them to interact with external applications. As LLM capabilities advance, effective tool use increasingly involves multi-step, multi-turn interactions to solve complex tasks. However, the resulting growth in tool interactions incurs substantial latency, posing a key challenge for real-time LLM serving. Through empirical analysis, we find that tool-calling traces are highly structured, conform to constrained schemas, and often exhibit recurring invocation patterns. Motivated by this, we propose ToolSpec, a schema-aware, retrieval-augmented speculative decoding method for accelerating tool calling. ToolSpec exploits predefined tool schemas to generate accurate drafts, using a finite-state machine to alternate between deterministic schema token filling and speculative generation for variable fields. In addition, ToolSpec retrieves similar historical tool invocations and reuses them as drafts to further improve efficiency. ToolSpec presents a plug-and-play solution that can be seamlessly integrated into existing LLM workflows. Experiments across multiple benchmarks demonstrate that ToolSpec achieves up to a 4.2x speedup, substantially outperforming existing training-free speculative decoding methods.

Figures & tables

Figure 1: Illustration of ToolSpec , which accelerates tool-calling generation via two innovations: 1) schema-aware drafting , where predefined tool schemas serve as faithful drafts and enable parallel verification of constrained variables (e.g., tool names ); and 2) retrieval-augmented speculation , retrieving and reusing similar historical tool invocations as high-quality drafts.

Figure 2: Latency breakdown of the Qwen2.5-Instruct model series on ToolBench ( Qin et al., 2024b ) . Tool execution latency remains essentially constant, whereas tool-calling generation latency increases with model scale, reaching up to

\bf 96\%

of the end-to-end latency.

Figure 3: A tool-calling trace from API-Bank ( Li et al., 2023 ) , with different fields highlighted in color.

Models	API-Bank	ToolAlpaca
Llama-3.1-8B-Instruct	$100.0\%$	$100.0\%$
Llama-3.2-3B-Instruct	$99.5\%$	$93.4\%$
Qwen2.5-14B-Instruct	$99.7\%$	$100.0\%$
Qwen2.5-7B-Instruct	$100.0\%$	$100.0\%$

Table 1: Format adherence of different models.

Datasets	#Tools	#Instances	Avg. Tool Rep.
API-Bank	2138	5221	10.95
ToolAlpaca	426	3938	4.82
BFCLv2	739	2251	9.01

Table 2: Statistics of tool-calling benchmarks.

Figure 4: Illustration of state transitions in ToolSpec . Once tool calling is triggered by <tool_call> , the FSM enters the tool-name state

q_{t}

, and then alternates between the parameter-name state

q_{p}

and parameter-value state

q_{v}

until the tool call is completed.

Figure 5: Illustration of tool-calling generation with ToolSpec . To accelerate structural tool calling, ToolSpec integrates two complementary drafting strategies: (a) schema-aware drafting , where a finite-state machine guides highly accurate drafting within the predefined tool schema; and (b) retrieval-augmented speculation , which reuses historical generation patterns as high-quality drafts to speed up recurrent tool calls.

Models	Methods	API-Bank			ToolAlpaca			BFCLv2			Overall Speedup
Models	Methods	#MAT	Tokens/s	Speedup	#MAT	Tokens/s	Speedup	#MAT	Tokens/s	Speedup	Overall Speedup
Qwen2.5-7B -Instruct	Vanilla	1.00	32.76	1.00 $\times$	1.00	32.72	1.00 $\times$	1.00	32.73	1.00 $\times$	1.00 $\times$
	PLD	2.37	64.56	1.97 $\times$	2.10	60.75	1.86 $\times$	2.24	62.52	1.91 $\times$	1.91 $\times$
	TR	3.09	78.95	2.41 $\times$	2.87	71.28	2.18 $\times$	2.89	73.64	2.25 $\times$	2.28 $\times$
	SAMD	3.60	83.96	2.56 $\times$	2.62	63.57	1.94 $\times$	2.92	70.70	2.16 $\times$	2.22 $\times$
	ToolSpec	4.90	129.40	3.95 $\times$	4.55	113.54	3.47 $\times$	4.73	117.17	3.58 $\times$	3.67 $\times$

Table 3: Comparison of inference efficiency between ToolSpec and prior plug-and-play methods. We report the mean number of accepted tokens (#MAT), average decoding speed (tokens/s), and wall-clock speedup relative to vanilla autoregressive decoding. The best results are shown in boldface , and the second-best results are underlined . ∗ The Eagle series, a training-required SD method, is included for reference only.

Figure 6: Speedup comparison between ToolSpec and prior plug-and-play methods on ToolBench.

Figure 7: Distribution of accepted token lengths in the first two decoding steps using LLaMA-3.1-8B-Instruct on API-Bank. Green triangles represent mean values, and black diamonds denote outliers.

Figure 8: Mean number of accepted tokens (#MAT) and speedups for repeated tool calls. Results are obtained using LLaMA-3.1-8B-Instruct on API-Bank.

Figure 9: Distribution of accepted token lengths using LLaMA-3.1-8B-Instruct on API-Bank. Values exceeding 17 are truncated for clearer visualization.

Methods	#MAT	Tokens/s	Speedup
Vanilla	1.00	28.21	1.00 $\times$
ToolSpec	5.80	125.59	4.45 $\times$
w/o SAD	5.58	118.99	4.22 $\times$
w/o RAS	4.29	94.53	3.35 $\times$
w/o both	3.62	76.00	2.69 $\times$

Table 4: Ablation study of ToolSpec modules. “ SAD ” and “ RAS ” denote schema-aware drafting and retrieval-augmented speculation, respectively. Results are obtained with LLaMA-3.1-8B-Instruct on API-Bank.

Figure 10: Format adherence of different models in tool-calling generation. Results are obtained on API-Bank.

Figure 11: Time allocation for each operation when LLMs respond to a query. Results are obtained using LLaMA-3.1-8B-Instruct on API-Bank.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Models	Methods	API-Bank	ToolAlpaca
Qwen2.5-7B	Vanilla	54.94	58.94
Qwen2.5-7B	ToolSpec	54.94	58.94
Qwen2.5-14B	Vanilla	54.61	58.94
Qwen2.5-14B	ToolSpec	54.61	59.60
LLaMA-3.1-8B	Vanilla	59.30	48.34
LLaMA-3.1-8B	ToolSpec	59.30	48.34

Appendix

Table 5: Performance comparison between ToolSpec and vanilla autoregressive decoding across different models on two widely used tool-use benchmarks.

Continuations	#MAT	Tokens/s	Speedup
$\{16,8,4,4\}$	5.52	115.07	4.08 $\times$
$\{32,16,8,8\}$	5.75	124.77	4.42 $\times$
$\{64,32,16,8\}$	5.77	122.60	4.35 $\times$
$\{16,16,16,16\}$	5.60	117.95	4.18 $\times$

Appendix

Table 6: Speedup of ToolSpec under different continuation lengths. Results are obtained with LLaMA-3.1-8B-Instruct on API-Bank.

$k$	#MAT	Tokens/s	Speedup
$1$	5.13	113.18	4.01 $\times$
$5$	5.56	119.70	4.24 $\times$
$10$	5.75	124.77	4.42 $\times$
$15$	5.69	123.22	4.37 $\times$

Appendix

Table 7: Speedup of ToolSpec with different retrieval parameter values

k

. Results are obtained with LLaMA-3.1-8B-Instruct on API-Bank.

Models	#MAT	Tokens/s	Speedup
Vanilla	1.00	17.23	1.00 $\times$
PLD	1.91	28.24	1.64 $\times$
TR	2.90	30.30	1.76 $\times$
SAMD	2.99	30.73	1.78 $\times$
ToolSpec	4.72	52.42	3.04 $\times$

Appendix

Table 8: Speedup of ToolSpec and prior plug-and-play methods using Qwen2.5-32B-Instruct on API-Bank. The best results are shown in boldface , and the second-best results are underlined .

Figure 12: Relative speedup improvement of ToolSpec over the previous best method. Results are obtained using the Qwen series on API-Bank.

Figure 13: Case study of ToolSpec with similar user queries on API-Bank using LLaMA-3.1-8B-Instruct.

Figure 14: Case study of ToolSpec under different tool-argument values using LLaMA-3.1-8B-Instruct.

LLM Inference Acceleration

LLM inference acceleration develops algorithms and systems that reduce language-model latency, memory use, and serving cost while preserving output quality.

See all 1,084 papers

SchemaFill: Efficient LLM Tool Calling via Slot-Parallel Speculative Decoding
Oct 5, 2026Zhi-Kai Chen, Song-Yan Li, De-Chuan Zhan +1Speculative Decoding LLM Inference Acceleration
School of Artificial Intelligence, Nanjing University, China · National Key Laboratory for Novel Software Technology, Nanjing University, China · Nanjing University, China
OoO-Spec: Out-of-Order Semantic Speculation for Fast Tool Calling
Aug 1, 2026Zhiheng Zhang, Mujie Xu, Feiyu Sun +1Speculative Decoding LLM Inference Acceleration
The University of Tokyo · Peking University · Nanjing University
Try, Check and Retry: A Divide-and-Conquer Framework for Boosting Long-context Tool-Calling Performance of LLMs
Mar 12, 2026Kunfeng Chen, Qihuang Zhong, Juhua Liu +2LLM Tool Use
School of Computer Science, National Engineering Research Center for Multimedia Software, Institute of Artificial Intelligence and Hubei Key Laboratory of Multimedia and Network Communication Engineering, Wuhan University, China · Nanyang Technological University, Singapore

Oct 5, 2026J/K move · Enter open · S save

SchemaFill: Efficient LLM Tool Calling via Slot-Parallel Speculative Decoding

Zhi-Kai Chen, Song-Yan Li, De-Chuan Zhan, Han-Jia Ye

School of Artificial Intelligence, Nanjing University, China · National Key Laboratory for Novel Software Technology, Nanjing University, China · Nanjing University, China

Speculative Decoding LLM Inference Acceleration LLM Tool Use Tool Use LLM Agent Tool Generation

Open paper AskPDF arXiv

LLM agents interact with external systems by generating structured tool calls. Given a user request, conversational context, and a catalog of tool schemas, a tool-calling model must select tools and generate their arguments, potentially producing multiple calls in a single response. Standard autoregressive decoding generates these calls token by token, incurring substantial latency for requests involving multiple calls or many argument fields. The explicit argument structure offers opportunities for parallel generation, but later argument values may depend on preceding fields and calls, so independently generated values can differ from the target model's output. We present SchemaFill, a framework for efficient LLM tool calling through slot-parallel speculative decoding. SchemaFill generates future slot values concurrently as candidates, without requiring advance knowledge of the actual call sequence or argument values. Candidates spanning multiple fields and calls are concatenated for verification by the target model under the actual output prefix. Only verified tokens are committed, and the target supplies corrections when candidates disagree. This applies target verification while exploiting parallelism across slots and calls. On Glaive and BFCL, SchemaFill achieves up to a 4.05

\times

improvement in end-to-end throughput over autoregressive decoding. Code is available at https://github.com/Czzzk/SchemaFill.

Abstract

LLM Inference Acceleration

Explore similar work

SchemaFill: Efficient LLM Tool Calling via Slot-Parallel Speculative Decoding

OoO-Spec: Out-of-Order Semantic Speculation for Fast Tool Calling

Try, Check and Retry: A Divide-and-Conquer Framework for Boosting Long-context Tool-Calling Performance of LLMs