# Syntax Error-Free and Generalizable Tool Use for LLMs via Finite-State
Decoding

Hongqiao Chen2∗ Lei Li3 William Yang Wang1

###### Abstract

Large language models (LLMs) have shown promising capabilities in using
external tools to solve complex problems. However, existing approaches involve
either fine-tuning on tool demonstrations, which does not generalize to new
tools without additional training, or providing tool documentation in context,
limiting the number of tools. Both approaches often generate syntactically
invalid tool calls. In this paper, we propose ToolDec, a finite-state machine-
guided decoding algorithm for tool-augmented LLMs. ToolDec eliminates tool-
related errors for any tool-augmented LLMs by ensuring valid tool names and
type-conforming arguments. Furthermore, ToolDec enables LLM to effectively
select tools using only the information contained in their names, with no need
for fine-tuning or in-context documentation. We evaluated multiple prior
methods and their ToolDec-enhanced versions on a variety of tasks involving
tools like math functions, knowledge graph relations, and complex real-world
RESTful APIs. Our experiments show that ToolDec reduces syntactic errors to
zero, consequently achieving significantly better performance and as much as a
2x speedup. We also show that ToolDec achieves superior generalization
performance on unseen tools, performing up to 8x better than the baselines
111We release our code and data at https://github.com/chenhongqiao/tooldec.

##  1 Introduction

Augmenting large language models (LLMs) with external tools (Mialon et al.,
2023) enables them to solve complex problems. Current LLMs can utilize
retrievers (Shen et al., 2023; Gupta & Kembhavi, 2022; Schick et al., 2023),
RESTful APIs (Qin et al., 2023; Song et al., 2023), program interpreters (Chen
et al., 2022; Gao et al., 2023), and various other tools. The performance of a
tool-augmented LLM depends on its ability to make three key decisions—when to
use a tool, which tool to use, and how to invoke a tool. Existing approaches
learn to make these decisions through fine-tuning or in-context learning.

However, these approaches still generate erroneous tool calls. For example,
in-context learning can easily generate non-existent tool names that are not
in the tool inventory because non-existent tools may also look plausible as
the next token (Song et al., 2023; Qin et al., 2023). Fine-tuned models,
though usually call tools by correct names, often pass invalid arguments to
the right tool functions (Hao et al., 2023), just as in-context learning does.
Furthermore, prior approaches do not generalize to unseen tools well. Fine-
tuning approaches need additional training data and further fine-tuning to
adopt new tools. In-context learning approaches require tool documentation in
the prompts.

To address these issues, we propose ToolDec, a decoding algorithm guided by a
finite-state machine (FSM) to ensure LLMs invoke tools properly. Our core
insight is to explicitly represent states during LLM decoding. Each state is
associated with a valid set of tokens corresponding to tool names and tool
arguments. ToolDec transitions from state to state as decoding progresses. At
each decoding step, ToolDec does not sample from the entire vocabulary of the
language model. Instead, it samples from a subset of tokens allowed by the
current state. The FSM that gives guidance to ToolDec is constructed from tool
documentation and API signature so that the machine precisely represents the
grammar of tool calls. In this way, ToolDec is able to always generate
syntactically correct tool calls. Figure 1 illustrates that an LLM enhanced by
ToolDec is able to generate the right function call multiply with precise
arguments (“3.14” and “123”) and therefore, it gets the correct result
returned by the tool. More examples comparing ToolDec and other tool LLMs can
be found in Appendix A.3.

Table 1: The comparison between the LLM tool use paradigms. Finite-state decoding is able to eliminate syntax errors, adopt new tools without new data and in-context documentation. Paradigm | Syntax Error-Free | Data-Free Generalization |  | No Tool Docs in Context
---
Fine-tuning | ✗ | ✗ | ✓
In-context learning | ✗ | ✓ | ✗
Finite-state decoding (ours) | ✓ | ✓ | ✓
Figure 1: LLMs using external tools. LLMs without tools cannot multiply, so
they just generate a probable next token. Tool-augmented LLMs can access
external tools like multiply, but they may call a non-existent tool like
product and pass invalid arguments like the string “pi”. Our proposed ToolDec
always generates tool calls without syntax errors.

Furthermore, ToolDec generalizes to new tools that never appeared before much
more efficiently. Unlike prior approaches which require fine-tuning or in-
context descriptions of new tools, ToolDec automatically constructs a finite-
state machine from a tool’s API signature (its name and argument types) and
adds it to the existing FSM. ToolDec is then able to call new tools without
fine-tuning or in-context demonstration. While pre-trained language models can
generate tool names when prompted to, they often hallucinate plausible tool
names that are not in the inventory. ToolDec does not do that. In Figure 1,
both product and multiply sound plausible for the scenario, but only multiply
is a given tool. Since ToolDec only calls existent tools, it won’t hallucinate
a plausible yet non-existent tool and can rely on the tool names to find the
right tool.

The contributions of this paper can be summarized as follows:

  * •

We propose ToolDec, a finite-state decoding algorithm to empower LLMs to use
tools properly. ToolDec enjoys two advantages: its generated tool calls are
guaranteed to be syntactically correct and it generalizes to unseen tools
efficiently.

  * •

We empirically verify ToolDec’s superior performance compared to prior strong
baselines on four diverse datasets from different domains. Our extensive
experiments show ToolDec eliminates all syntax errors and hallucinated tool
names, resulting in better accuracy and as much as 50% less inference time.
Our results also indicate that ToolDec is more than 8x better than baselines
on mathematical reasoning with 9 unseen tools and 7x better than knowledge
question answering with 204 unseen tools.

##  2 Related Work

Fine-tuning language models to use tools. Language models can be fine-tuned to
use tools with data that contain interleaving text and tool use. Earlier
studies make language models use a single tool like a retrieval module
(Borgeaud et al., 2022; Guu et al., 2020) or a search engine (Nakano et al.,
2021) by fine-tuning. Recent advances in tool-augmented language models that
use multiple tools (Schick et al., 2023; Parisi et al., 2022) also fine-tune
language models to use tools including QA models, translation models,
calculators, and search engines. ToolkenGPT (Hao et al., 2023) proposes to use
several special tokens to represent tools and only tunes the embeddings of the
tokens so that new tool adoption can be more efficient. However, fine-tuning
approaches for tool use still need new data and extra fine-tuning to adapt a
model to new tools. We list the differences between finite-state decoding and
the previous two paradigms in Table 1.

In-context learning for tool use. Language models can learn from in-context
examples (Brown et al., 2020) and follow instructions (Ouyang et al., 2022).
This makes it possible to simply put the descriptions of tools in the prompt
and ask language models to use them. Recent works have used this possibility
to use neural models (Shen et al., 2023), RESTful APIs (Qin et al., 2023; Song
et al., 2023), program interpreters (Chen et al., 2022; Gao et al., 2023) and
many other tools to solve problems. In-context learning does not need extra
model tuning to use new tools. However, the description and documentation of
new tools still need to be in the prompt, which increases computation cost and
limits the context budget for the model to actually reason about the task.

Constrained decoding and finite-state machines. Previous constrained decoding
methods mainly focus on lexical constraints (Anderson et al., 2017). They
reduce the large search space of lexically constrained decoding with finite-
state machines (Anderson et al., 2017), grouping together similar candidates
(Hokamp & Liu, 2017), and better search algorithms (Miao et al., 2019; Lu et
al., 2021; 2022). However, lexical constraints are not expressive enough to
regulate tool calls. While finite-state machines have to be weighted and
probabilistic to deal with the soft constraints in natural language (Eisner,
2002; Rastogi et al., 2016), the constraints for syntactic tool calls are hard
constraints that are much easier for FSMs. Therefore, we propose ToolDec to
meet the syntactic constraints of a valid tool call.

##  3 ToolDec: LLM Tool Use via Finite-State Decoding

A syntactically correct tool call needs to refer to an existent tool name and
pass type-conforming arguments. Motivated by the fact that it is
straightforward to verify the syntax of a tool call using a finite-state
machine (FSM), we propose ToolDec, a constrained decoding algorithm guided by
an FSM. During each decoding step, the model samples from a subset of the
vocabulary that only contains syntactically correct tokens. The FSM that
specifies the token subsets can be constructed from the tool documentation.
For example, in Figure 2, an FSM is constructed for functions add, exp, square
and sqrt. Table 2 shows how ToolDec answers the question “the side of a square
is 5, what’s its area?” using the FSM. With the guidance from the FSM, ToolDec
achieves the following goals:

  * •

Switching Modes. Switch between “text mode” when the model is free to generate
any text and “tool mode” when the model can only generate valid tool calls.

  * •

Generating Tool Names. At the beginning of a tool call, only generate correct
existent tool names from a pre-defined list of tools.

  * •

Passing Arguments. Only pass type-conforming arguments to the tool.

###  3.1 Finite-State Decoding

Figure 2: A finite-state machine for ToolDec constructed for math functions
add, exp, square, sqrt that take integers as arguments. The names of the tools
are represented with a trie structure. “IntFSM” is a submodule that parses
integers.

ToolDec is guided by a finite-state machine (FSM). An FSM is a 5-tuple
$(S,V,g,s_{0},R)$, consisting of a finite state set $S$, an alphabet $V$, a
transition function $g:S\times V\rightarrow S$, an initial state $s_{0}$ and a
set of accepting states $R$. In our case, $S$ and $g$ are constructed from the
tool signature. $V$ is the token vocabulary of the language model. $R$
corresponds to pre-defined tokens that can determine the LM has completed the
task, like ‘<EOS>’.

Table 2: How ToolDec uses the FSM in Figure 2 to answer the question “the side of a square is 5, what’s its area?”. At each time step, the state in the machine corresponds to a set of valid next tokens. We zero out all other tokens and re-normalize the next token distribution, forcing the LLM to only sample valid tokens. Step | Generated Text | Current State $g$ | Valid Next Tokens | Next Token | Next State
---|---|---|---|---|---
$t$ | Its | $s_{0}$ | whole vocab. | ‘area’ | $s_{0}$
$t+1$ | Its area | $s_{0}$ | whole vocab. | ‘is’ | $s_{0}$
$t+2$ | Its area is | $s_{0}$ | whole vocab. | ‘<T>’ | $s_{1}$
$t+3$ | Its area is <T> | $s_{1}$ | ‘add’, ‘exp’, ‘sq’ | ‘sq’ | $s_{4}$
$t+4$ | Its area is <T>sq | $s_{4}$ | ‘uare’, ‘rt’ | ‘uare’ | $s_{5}$
$t+5$ | Its area is <T>square | $s_{5}$ | ‘(’ | ‘(’ | $s_{10}$
$t+6$ | Its area is <T>square( | $s_{10}$ | ‘+’,‘-’,‘1’-‘9’ | ‘5’ | $s_{12}$
$t+7$ | Its area is <T>square(5 | $s_{12}$ | ‘0’-‘9’, ‘)’ | ‘)’ | $s_{10}$
$t+8$ | Its area is <T>square(5) | $s_{10}$ | whole vocab. | - | -

At each decoding step $t$, ToolDec maintains a current state $s$. It can only
generate the tokens permitted by the FSM, i.e. the tokens for which
$g(s,\cdot)$ is defined. These permitted tokens are a subset of $V$ and we
denote them as $V_{s}$. After generating one token $a$, ToolDec transits to
another state $g(s,a)$ specified by the FSM transition function. The permitted
tokens for each state can be the full vocabulary, or a valid subset
corresponding to tool names and argument types. At each step $t$, we do not
directly sample from the next token distribution $P(x_{t}|x_{1..t-1})$
calculated by the LLM. Instead, we zero out the probabilities of invalid
tokens for which the transition function is undefined, and normalize the
probabilities,

$\tilde{P}(x_{t}=a|x_{1..t-1},s)=\left\\{\begin{aligned}
&\tfrac{P(x_{t}=a|x_{1..t-1})}{\sum_{a^{\prime}\in
V_{s}}P(x_{t}=a^{\prime}|x_{1..t-1})},\ &g(s,a)\text{ is defined},\\\
&0,&\text{otherwise}\end{aligned}\right..$

The next token $a$ is then sampled from the modified distribution
$\tilde{P}(x_{t}|x_{1..t-1},s)$. With the next token, we move on to the next
decoding step and transition the current state $s$ to the next state $g(s,a)$.
The pseudo-code of this algorithm is listed in Appendix A.1.

###  3.2 Constructing FSMs that Guarantee Syntactically Correct Tool Calls

Switching Modes. We use two states in the FSM to represent whether the
language model is in text mode or tool mode. The text mode is denoted by the
initial state $s_{0}$, during which the model is free to generate any token in
its vocabulary, i.e. $V_{s_{0}}=V$. The tool mode is denoted by state $s_{1}$.
The model needs to output the special token <T> to switch from text mode to
tool mode. Starting at $s_{1}$ is a smaller FSM that describes the grammar of
tool calls. Note that ToolDec can be applied to models with different mode-
switching schemes. For some models like ToolkenGPT (Hao et al., 2023) and
toolformer (Schick et al., 2023), when to use a tool is decided by the model
itself using special tokens, just like in Table 2. For others like ToolLLM
(Qin et al., 2023), the planning is done explicitly using an external planner
similar to that in ReAct (Yao et al., 2023). For those models, ToolDec
switches between $s_{0}$ and $s_{1}$ according to the external planner.

Generating Tool Names. Once the model is at state $s_{1}$, the next step would
be to generate a new tool call. To generate a correct tool call, the model
needs to output the correct name for the tool and a correct list of arguments.
If every tool had a single-token name, we could simply define $V_{s_{1}}$ as
the set of tool names. However, that is not the case for most tools. Many
tools have long names that need multiple tokens to represent. For example, the
tool square in Figure 2 consists of two tokens— ‘sq’ and ‘uare’. Therefore, we
need to construct an FSM for multi-token tool names.

We use a trie (Fredkin, 1960) to construct the FSM for tool names. In Figure
2, the trie for tool names consists of states
$\\{s_{1},s_{2},s_{3},s_{4},s_{5},s_{6}\\}$. A trie is a rooted tree in which
each edge represents a token. A node in the tree represents a string that’s
the concatenation of the path from the root to this node. In our example,
$s_{4}$ represents the string “sq” and $s_{5}$ represents the string “square”.
All nodes in a trie represent a set of strings. We construct a trie for the
valid tool names and make $s_{1}$ the root of this trie.

To construct a trie, we insert all the strings into it one by one. Inserting a
string into a trie means going from the root down the path made by the string
and creating new nodes when the next step in the path does not exist. For
example, we show how two more tools names, exp10 and expand can be added to
the trie in Figure 3.

Figure 3: Inserting two more tool names exp10 and expand into the trie. They
are represented by the two blue states $s_{7}$ and $s_{8}$.

Note that the construction of trie depends on one assumption: no two tools
have the same name. While this is a reasonable assumption to make, there could
be exceptions in real applications. In that case, we could rewrite the tool
names to include more details to disambiguate them. Rewriting abstract and
hard-to-understand tool names can also make it easier for the language model
to select them by name.

Generating Syntactically Valid Tool Arguments. Tool arguments have specified
types. Like arguments in a program, they need to follow certain grammar rules.
These rules can be specified by finite-state machines. For example, the
“IntFSM” in Figure 2 depicts a finite-state machine that only accepts integer
literals. For all arguments of a tool, we chain their corresponding FSMs
together and use the last state corresponding to the tool name as the initial
state of this FSM chain. Note that in practice, it’s not necessary to
explicitly construct this FSM. Any grammar checker that tells the set of valid
next tokens suffice.

##  4 Experiment I: ToolDec Eliminates Syntax Errors

In this section, we show that ToolDec can eliminate syntax errors while
generating tool calls. We select two recent baselines, ToolLLM and ToolkenGPT,
representative of the in-context learning and the fine-tuning paradigm, to
showcase ToolDec’s ability. Since the tool-use settings for the two baselines
are different and cannot be applied to one another, we test ToolDec’s
performance separately for the two baselines using the benchmarks from the
original papers. Through extensive experiments, we show that ToolDec can
completely eliminate syntactic errors, resulting in better accuracy and
shorter inference time.

###  4.1 Baselines and Benchmarks

ToolLLM (Qin et al., 2023). ToolLLM is an in-context learning approach to
tool-augmented language models. It utilizes an instruction-tuned LLaMA-7B
model (Touvron et al., 2023) to use tools. Given the natural language
instruction of a tool-dependent task, an API retriever first retrieves a small
subset of relevant functions. Textual description and schema of these relevant
functions are made available in the context. Then, ToolLLM goes through a
multi-step reasoning process using the functions to produce a final answer.

ToolLLM is evaluated on ToolEval, a dataset proposed in the same paper.
ToolEval contains tasks that involve a massive set (10,000+) of publicly
available REST APIs. We use the most difficult subsets of ToolEval to evaluate
our method—I2-Category and I3-Instruction. They contain tasks that need
complex and unseen tools from multiple categories (such as geolocation,
date/time, and others) to solve. On average, an I2-Category task needs 6.76
tools and an I3-Category task needs 8.24 tools. ToolEval has two main metrics:
Pass Rate measures the percentage of tasks for which the model reaches an
answer within a certain amount of reasoning steps. Win Rate utilizes an
automatic evaluator powered by an LLM following a pre-defined set of criteria
for a better path. It compares the quality and correctness of the baseline
answers to the reference answer produced by ChatGPT. Qin et al. (2023) finds
that the automatic evaluator has a high correlation of 75.8% with human
annotators. Other than these two metrics, we also measure Tool Error Rate, the
proportion of tasks that have at least one tool-related error.

ToolkenGPT (Hao et al., 2023). ToolkenGPT is a fine-tuning approach to tool
use. ToolkenGPT represents each tool as a special token and optimizes only the
embedding of the tool tokens for tool use. During inference, ToolkenGPT
invokes a tool once the corresponding special token is predicted. During a
tool call, it passes arguments by learning from in-context demonstrations.
ToolkenGPT uses LLaMA-33B (Touvron et al., 2023) as its base model.

We evaluated ToolDec’s performance on FuncQAmulti(Hao et al., 2023). This
dataset tests LLMs’ ability in numerical reasoning tasks with 68 math
problems. Then, LLMs are required to produce a numerical answer using a few of
the 13 arithmetic operations as tools (e.g. multiply, power, lcm). The
accuracy is determined by measuring the percentage of problems for which a
correct answer is produced, with a 0.1% error tolerance. On average, a problem
in FuncQAmulti requires 2.78 tool calls to solve. Following Hao et al. (2023),
we report results of other baselines, including ChatGPT without tools, LLaMA
with chain-of-thought and tools, LLaMA with ReAct and tools.

###  4.2 Integrating ToolDec with the Base Models

ToolLLM+ToolDec. Following Qin et al. (2023), we use ReAct (Yao et al., 2023)
to plan the tool calls of ToolLLM. This conforms to the second case of mode
switching in Section 3.2. There are three parts in the FSM for ToolLLM. First,
a format FSM that enforces the “Thought, Action, Action Input” syntax of
ReAct. After decoding “Action:”, this FSM transitions to the beginning state
of the function name FSM, which guarantees that a decoded function name is
always valid. We also constructed a JSON-based function argument FSM. We
allowed LLMs to reason for 5 steps before it must call the finish action to be
considered “pass”.

ToolkenGPT+ToolDec. Since ToolkenGPT uses special tokens to call tools,
ToolDec is only applied to guarantee the syntax of arguments. In this
experiment, our FSM guarantees that every argument is a valid number, and
arguments are separated by commas. It also guarantees that the actual number
of arguments passed to a function is exactly the number needed by it. We
compared ToolDec to two variants of the baseline in Hao et al. (2023), one
with backtrace and one without. Backtrace tries to avoid failed tool calls by
allowing the LLM to go back and try the next probable token, in place of the
failed tool call. To evaluate ToolDec, we report the average inference time
per problem and tool error rates in addition to accuracy.

###  4.3 Experimental Results

Table 3: Results on ToolEval. ToolDec-enhanced ToolLLM outperformed baselines ToolLLM in all metrics. ToolDec eliminated all tool errors and was even able to beat ChatGPT slightly. | I2-Category | I3-Instruction
---|---|---
| Pass ↑ | Win ↑ | Tool Error ↓ | Pass ↑ | Win ↑ | Tool Error ↓
ChatGPT | 39.0% | - | 8.0% | 29.0% | - | 7.0%
ToolLLM | 32.0% | 44.0% | 39.0% | 18.0% | 44.0% | 47.0%
ToolLLM + Fuzzy Matching | 38.0% | 48.0% | 19.0% | 23.0% | 49.0% | 23.0%
ToolLLM + ToolDec (ours) | 42.0% | 55.0% | 0.0% | 34.0% | 60.0% | 0.0%

ToolDec enhances in-context learning tool LLMs. Table 3 shows ToolDec’s
performance on ToolEval. ToolDec achieved 55% win rate on I2-Category and 60%
win rate on I3-instruction. As a drop-in replacement of the original decoding
algorithm, ToolDec eliminated all three types of tool-related errors and
achieved the best win rate and pass rate, even beating ChatGPT.

Figure 4: Error rates of the three types of tool-related errors relative to
the total number of tool calls. ToolDec reduced all three tool-related errors
to zero.

The high tool error rate of the baselines suggests that even after instruction
fine-tuning, ToolLLM still lacks the ability of accurately invoke external
tools from the tool documentation. This inability is more exposed when there
is a large variety of tools available, as in I3-Instruction. Furthermore,
these errors significantly impacted the model’s ability to complete tasks.

We present the error rates of each error type on two benchmarks in Figure 4.
For ToolLLMs, name error, i.e. calling a non-existent tool, was the most
common syntactic error in a tool call. ToolDec completely eliminated all three
errors.

With function name hallucination being the most prevalent tool-related error,
a slightly better baseline was to mitigate it with fuzzy matching by suffix.
We present the results of the baseline with fuzzy matching as ToolLLM + Fuzzy
Matching, and without as ToolLLM. This mitigation increased pass rate but had
little impact on win rate, as evident in Table 3, because wrong APIs could
often be chosen when a model was unable to precisely call the tool it wanted.
Overall, our experiments on ToolLLM demonstrate that ToolDec is highly
effective on in-context learning LLMs. Through the next baseline, ToolkenGPT,
we show that ToolDec is also beneficial to fine-tuned tool LLMs.

Table 4: Results on FuncQAmulti. ToolkenGPT combined with ToolDec eliminated all tool errors. Compared to ToolkenGPT without backtrace, ToolDec was better in both accuracy and inference time. Compared to ToolkenGPT with backtrace, ToolDec achieved a comparable accuracy with only half the time. | Accuracy ↑ | Time ↓ | Tool Error ↓
---|---|---|---
0-shot ChatGPT w/o tools | 9% | - | -
LLaMA w/ tools + CoT | 3% | - | -
LLaMA w/ tools + ReAct | 6% | - | -
ToolkenGPT | 10.3% | 7.76s | 27.9%
ToolkenGPT + Backtrace | 14.7% | 10.39s | 0.0%
ToolkenGPT + ToolDec (ours) | 13.2% | 5.95s | 0.0%

ToolDec enhances fine-tuning tool LLMs. Table 4 shows the results on
FuncQAmulti. Although ToolkenGPT eliminates the possibility of calling non-
existent tool names by fine-tuning a special token embedding, it can still
suffer from other syntactic errors, which is demonstrated by the 27.9% tool
error rate. As a drop-in replacement, ToolDec increased ToolkenGPT’s accuracy
while being much faster in inference. Although ToolkenGPT + backtrace achieved
slightly better accuracy than ToolDec, it used 2x more time to try different
tools. Note that since ToolDec eliminated all tool errors, there were no
failed tool calls for backtrace to retry. The results underscore tool-related
errors’ relevancy and ToolDec’s applicability to both recent in-context
learning and fine-tuning tool-augmented LLMs.

##  5 Experiment II: ToolDec Enables Generalizable Tool Selection

In Experiment II, we show how ToolDec generalizes to unseen tools without
additional training data and tool documentation. We compare ToolDec with two
strong baselines—ToolkenGPT (Hao et al., 2023) as a representative fine-tuning
approach, and RestGPT (Song et al., 2023) as a representative in-context
learning approach. We conducted experiments on three benchmarks—FuncQA (Hao et
al., 2023) and KAMEL (Kalo & Fichtel, 2022), and RestBench (Song et al.,
2023). These benchmarks require diverse tool sets from very different domains,
including math reasoning, knowledge question answering and real-world web
services. In all three domains, our results show that ToolDec is able to
efficiently generalize to new tools without fine-tuning on extra data.

###  5.1 Fine-Tuning Baseline: ToolkenGPT

ToolkenGPT is a fine-tuning approach to tool use that learns a special token
for every tool. To generalize to new tools, ToolkenGPT still needs additional
data and extra fine-tuning involving the use of new tools. We demonstrate that
ToolDec, once fine-tuned on a given set of seen tools, doesn’t need additional
data and further fine-tuning to adopt unseen tools. We compare ToolDec and the
baselines by tuning them on the same subset of tools, denoted as “seen tools”,
and then evaluate their performance on “unseen tools”.

To guarantee a fair comparison, We mimic ToolkenGPT’s planning method to solve
the “when to use tools” problem. Specifically, we fine-tune the embedding of a
single special token <T> to represent all tools, reducing the size of extra
vocabulary to 1. Once <T> is generated, a tool call begins. We prompt LLM to
generate a tool name. The generation of this tool name is guided by an FSM
constructed from a list of all available tools. This tool name is then plugged
back into the context to start the generation of arguments. We show an example
of this process in Appendix A.2.

We selected a small subset of “seen tools” out of all available tools and
tuned the embedding only with demonstrations of the tools in the selected
subset. We fine-tuned the baseline using the same subset. Then, we evaluated
our method and the baselines on tasks that involve unseen tools in the subset
to demonstrate ToolDec’s generalization ability.

Benchmark on Math Functions. We use FuncQA multi-hop questions to evaluate our
method. Tools in FuncQA, such as permutate, gcd, power are mathematical
functions that strictly limits on their arguments to be numbers in certain
ranges. We select 4 out of 13 tools as the seen subset to tune the baseline
and evaluate different approaches on the remaining 9 unseen tools.

Benchmark on Knowledge Graph Relations. To further investigate ToolDec’s
generalizability on a larger set of tools, we also evaluate on KAMEL (Kalo &
Fichtel, 2022), a question-answering dataset containing a total of 234
knowledge relations that resemble the characteristics of APIs (e.g.
number_of_children). More examples can be found in Appendix A.4. The tools in
KAMEL are many more than those in FuncQA. They are also more complex and
diverse because the number of arguments to their tools varies from 1 to 3, and
their types include strings, locations, dates, numbers and other ad-hoc types.
We select 30 out of 234 tools as the seen subset and evaluate on 4 different
evaluation sets, with 30, 60, 100, and 234 tools, respectively. Following Hao
et al. (2023), we use prompting, few-shot, and zero-shot as extra baselines.
(1) Prompting relies on the internal knowledge of LLM, since no tool was
provided. (2) Few-shot demonstrates tool use through few-shot examples. (3)
Zero-shot provides descriptions of all available tools in context. Since the
KAMEL’s training and evaluation dataset share the same question template for
every tool, which is often not true in real-world settings, we compare ToolDec
only to ToolkenGPT trained on the synthetic dataset proposed by the original
study. We use the accuracy of tool calls as a metric, which is determined by
the proportion of responses that invoke the correct knowledge relation.

###  5.2 In-Context Learning Baseline: RestGPT

RestGPT (Song et al., 2023) is an in-context learning approach that learns
tool use from in-context tool documentation. We demonstrate the generalization
ability of ToolDec-enhanced RestGPT by showing that RestGPT with ToolDec can
achieve better accuracy without in-context documentation than the RestGPT
baseline with documentation. Since ToolDec needs access to the next token
distribution, we use Vicuna-based (Zheng et al., 2023) RestGPT as the
baseline. For our method, we remove all tool documentation from the prompt,
leaving only the instructions for reasoning.

Benchmark on APIs for Real-World Web Services. We evaluate on RestBench (Song
et al., 2023). It consists of tasks in real-world scenarios including TMDB, a
website for movie information, and Spotify, an online music player. These
tasks directly come from real-user instructions and require multiple tools in
the form of RESTful APIs to solve. RESTful APIs are the de facto standard for
web services (Li et al., 2016) that use HTTP methods to manipulate resources.
The ground truth solutions are annotated by humans in the form of tool call
chains. We evaluate our method and the baseline on TMDB, which consists of 55
RESTful APIs. Since HTTP methods such as GET and POST have a format different
from the tool call, tool arguments format of ToolDec. We rewrote these APIs to
follow this format. We use the correct path rate (CP%) proposed by the
original paper as the metric to measure accuracy. Correct path rate is the
proportion of model outputs that contain the correct tool call path annotated
by humans.

###  5.3 Experiment Results

Generalization to Unseen Math Functions. In 5(a), we present the results on
FuncQA. While ToolkenGPT and ToolDec achieved similar accuracies on tasks that
involved only seen tools, ToolkenGPT failed to generalize to unseen tools,
resulting in a significant performance drop. On the other hand, ToolDec was
able to maintain a comparable accuracy even on unseen tools and achieve 8x
better accuracy on multi-hop problems, underscoring its generalizability.
Consequently, ToolDec significantly outperformed ToolkenGPT on total accuracy.

Generalization to Unseen Knowledge Graph Functions. We present our results on
KAMEL in 5(b). As the number of available tools increased, the two ICL methods
suffered from the context length limit (Hao et al., 2023) and experienced a
significant drop in accuracy. ToolkenGPT, fine-tuned on the first 30 tools,
was also unable to generalize to more tools. Prompting kept a stable low
accuracy because it did not rely on in-context tool documentation. On the
other hand, ToolDec was able to maintain its accuracy even when the amount of
unseen tools reached 204.

Table 5: Results on RestBench. The baseline needs a much longer prompt with in-context tool documentation to learn tool use, while our method does not. Yet, our method still has a much higher correct path ratio (CP%) than the baseline. | CP% $\uparrow$ | Prompt Size $\downarrow$
---|---|---
RestGPT with In-Context Documentation | 15.0% | 1974
RestGPT + ToolDec w/o Documentation | 23.0% | 880

(a) FuncQA

(b) KAMEL

Figure 5: Results on KAMEL and FuncQA. As the number of unseen tools
increased, all baselines experienced a significant performance drop. But
ToolDec kept a similar high performance though it had only seen a small subset
(30 out of 234 on KAMEL and 4 out of 13 on FuncQA) of tools.

Generalization to Unseen Web Services. The results on RestBench are reported
in Table 5. ToolDec enabled the model to use web-service APIs without in-
context documentation, reducing the prompt size from 1974 tokens to only 880
tokens. Nevertheless, ToolDec still significantly outperformed the baseline in
terms of correctness indicated by correct path ratio (CP%), raising it by 8
points. These results suggest that ToolDec can also improve the
generalizability of in-context learning tool use in real-world web
applications.

Results from all three settings indicate that not only does ToolDec help fine-
tuning tool LLMs generalize without extra training data, it also helps in-
context learning tool LLMs generalize without in-context documentation. This
capability of ToolDec has been proven in three different domains.

##  6 Conclusion

This paper presents ToolDec, a novel decoding algorithm designed to enhance
Large Language Models (LLMs) by integrating external tools and ensuring their
invocation is syntax-error-free. ToolDec, guided by a finite-state machine
constructed from tool documentation and API signatures, accurately represents
the grammar of tool calls, addressing prevalent issues like erroneous tool
calls and poor generalization to unseen tools in existing models.

Experiments demonstrate that ToolDec eliminates tool-related syntax errors,
improves accuracy, and saves inference time across various benchmarks. It also
exhibits the ability to generalize to unseen tools in multiple domains without
additional fine-tuning data. The advancements by ToolDec open avenues for
research in developing more sophisticated models adaptable to a wider range of
tools and applications without additional training data, leading to more
versatile and robust LLMs capable of solving a broader spectrum of complex
problems.

The success of ToolDec in eliminating syntax errors can inspire research
focusing on semantic accuracy and contextual relevance of tool calls. This can
lead to models that invoke, understand, and leverage tools more effectively,
enhancing LLMs’ overall problem-solving capabilities.

## References

  * Anderson et al. (2017) Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould.  Guided open vocabulary image captioning with constrained beam search.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pp. 936–945, Copenhagen, Denmark, September 2017\. Association for Computational Linguistics.  doi: 10.18653/v1/D17-1098.  URL https://aclanthology.org/D17-1098.
  * Borgeaud et al. (2022) Sebastian Borgeaud, Arthur Mensch, Jordan Hoffmann, Trevor Cai, Eliza Rutherford, Katie Millican, George Bm Van Den Driessche, Jean-Baptiste Lespiau, Bogdan Damoc, Aidan Clark, et al.  Improving language models by retrieving from trillions of tokens.  In _International conference on machine learning_ , pp. 2206–2240. PMLR, 2022.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Chen et al. (2022) Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W Cohen.  Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks.  _arXiv e-prints_ , pp. arXiv–2211, 2022.
  * Eisner (2002) Jason Eisner.  Parameter estimation for probabilistic finite-state transducers.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pp. 1–8, 2002.
  * Fredkin (1960) Edward Fredkin.  Trie memory.  _Communications of the ACM_ , 3(9):490–499, 1960\.
  * Gao et al. (2023) Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig.  Pal: Program-aided language models.  In _International Conference on Machine Learning_ , pp. 10764–10799. PMLR, 2023.
  * Gupta & Kembhavi (2022) Tanmay Gupta and Aniruddha Kembhavi.  Visual programming: Compositional visual reasoning without training.  _ArXiv_ , abs/2211.11559, 2022.
  * Guu et al. (2020) Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Mingwei Chang.  Retrieval augmented language model pre-training.  In _International conference on machine learning_ , pp. 3929–3938. PMLR, 2020.
  * Hao et al. (2023) Shibo Hao, Tianyang Liu, Zhen Wang, and Zhiting Hu.  Toolkengpt: Augmenting frozen language models with massive tools via tool embeddings.  _arXiv preprint arXiv:2305.11554_ , 2023.
  * Hokamp & Liu (2017) Chris Hokamp and Qun Liu.  Lexically constrained decoding for sequence generation using grid beam search.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 1535–1546, Vancouver, Canada, July 2017. Association for Computational Linguistics.  doi: 10.18653/v1/P17-1141.  URL https://aclanthology.org/P17-1141.
  * Kalo & Fichtel (2022) Jan-Christoph Kalo and Leandra Fichtel.  Kamel : Knowledge analysis with multitoken entities in language models.  _Automated Knowledge Base Construction_ , 2022.
  * Li et al. (2016) Li Li, Wu Chou, Wei Zhou, and Min Luo.  Design patterns and extensibility of rest api for networking applications.  _IEEE Transactions on Network and Service Management_ , 13(1):154–167, 2016.
  * Lu et al. (2021) Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi.  Neurologic decoding:(un) supervised neural text generation with predicate logic constraints.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pp. 4288–4299, 2021.
  * Lu et al. (2022) Ximing Lu, Sean Welleck, Peter West, Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ronan Le Bras, Lianhui Qin, Youngjae Yu, Rowan Zellers, et al.  Neurologic a* esque decoding: Constrained text generation with lookahead heuristics.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pp. 780–799, 2022.
  * Mialon et al. (2023) Grégoire Mialon, Roberto Dessì, Maria Lomeli, Christoforos Nalmpantis, Ram Pasunuru, Roberta Raileanu, Baptiste Rozière, Timo Schick, Jane Dwivedi-Yu, Asli Celikyilmaz, et al.  Augmented language models: a survey.  _arXiv preprint arXiv:2302.07842_ , 2023.
  * Miao et al. (2019) Ning Miao, Hao Zhou, Lili Mou, Rui Yan, and Lei Li.  Cgmh: Constrained sentence generation by metropolis-hastings sampling.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pp. 6834–6842, 2019.
  * Nakano et al. (2021) Reiichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christopher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, et al.  Webgpt: Browser-assisted question-answering with human feedback.  _arXiv preprint arXiv:2112.09332_ , 2021.
  * Ouyang et al. (2022) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al.  Training language models to follow instructions with human feedback.  _Advances in Neural Information Processing Systems_ , 35:27730–27744, 2022.
  * Parisi et al. (2022) Aaron Parisi, Yao Zhao, and Noah Fiedel.  Talm: Tool augmented language models.  _arXiv preprint arXiv:2205.12255_ , 2022.
  * Qin et al. (2023) Yujia Qin, Shihao Liang, Yining Ye, Kunlun Zhu, Lan Yan, Yaxi Lu, Yankai Lin, Xin Cong, Xiangru Tang, Bill Qian, et al.  Toolllm: Facilitating large language models to master 16000+ real-world apis.  _arXiv preprint arXiv:2307.16789_ , 2023.
  * Rastogi et al. (2016) Pushpendre Rastogi, Ryan Cotterell, and Jason Eisner.  Weighting finite-state transductions with neural context.  In _Proceedings of the 2016 conference of the North American chapter of the Association for Computational Linguistics: human language technologies_ , pp. 623–633, 2016.
  * Schick et al. (2023) Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom.  Toolformer: Language models can teach themselves to use tools.  _arXiv preprint arXiv:2302.04761_ , 2023.
  * Shen et al. (2023) Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang.  Hugginggpt: Solving ai tasks with chatgpt and its friends in hugging face, 2023.
  * Song et al. (2023) Yifan Song, Weimin Xiong, Dawei Zhu, Wenhao Wu, Han Qian, Mingbo Song, Hailiang Huang, Cheng Li, Ke Wang, Rong Yao, Ye Tian, and Sujian Li.  Restgpt: Connecting large language models with real-world restful apis, 2023.
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample.  Llama: Open and efficient foundation language models, 2023.
  * Yao et al. (2023) Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao.  React: Synergizing reasoning and acting in language models, 2023.
  * Zheng et al. (2023) Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric. P Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica.  Judging llm-as-a-judge with mt-bench and chatbot arena, 2023.

##  Appendix A Appendix

###  A.1 Pseudo-Code of the Decoding Algorithm

Algorithm 1 Finite-State Machine Guided Decoding for Language Models

A DFSM defined by $(S,V,g,s_{0},R)$;

A language model $M$ that produces the distribution of the next token given a
prefix string;

An initial string of tokens $x_{1..k}$, which represents the prompt from the
user.

A string of tokens.

$s\leftarrow s_{0}$

while $s\not\in F$ do

$V_{s}\leftarrow\\{a|a\in V\land g(s,a)\text{ is defined}\\}$

$P(x_{k+1}|x_{1..k})\leftarrow M(x_{1..k})$

$\tilde{P}(x=a|x_{1..k},s)\leftarrow\left\\{\begin{aligned}
&\tfrac{P(x=a|x_{1..k})}{\sum_{a^{\prime}\in V_{s}}P(x=a^{\prime}|x_{1..k})},\
&a\in V_{s}\\\ &0,&\text{otherwise}\end{aligned}\right.$

$x\sim\tilde{P}(x|x_{1..k},s)$

$x_{k+1}\leftarrow x$

$k\leftarrow k+1$

$s\leftarrow g(s,x)$

end while

return $x_{1..k}$

###  A.2 Generalizing ToolkenGPT to Unseen New Tools

Figure 6: Once a tool call begins, ToolDec injects a special prompt (blue
text) into context to generate the tool name.

###  A.3 Examples of ToolDec Eliminating Tool-related Errors

In this section, we show examples of ToolDec preventing tool-related errors on
various baselines. Baselines are displayed in the left column and ToolDec is
showed on the right.

Figure 7: ToolDec can prevent function name error, function argument error,
and invalid ReAct syntax on ToolLLM. Figure 8: ToolDec can eliminate the
common tool-related errors for fine-tuned models.

###  A.4 Examples of KAMEL Relations

Relation Name | Description
---|---
broadcasted_places(station) | gets the places where a radio station is broadcasted to
main_topics(title) | gets the main topics of a book or magazine
competition_disciplines(name) | gets the disciplines a person is competing in
team_membership(name) | gets the list of teams a person was a member
location(name) | gets the country where a location is located
creative_work_type(title) | gets the type or format of a creative work
membership(name) | gets the groups or organizations a person was a member
employer(name) | gets the employers of a person
floors_above_ground(name) | gets the number of floors above the ground of a building
workplaces(name) | gets the workplaces of a person
start_year(title) | gets the year when a TV show or a movie started airing
positions_played(name) | gets the positions played by a sports player
number_of_participants(event_name) | gets the number of participants in a sporting event
taxon_rank(species_name) | gets the taxonomic rank of a given species name
Table 6: Examples of KAMEL Relations