Using massive data analysis of connected device firmware and software, Finite State provides transparency to device manufacturers and asset owners, enabling them to understand and mitigate their risks before they are compromised

Finite State

finitestate

Introduction Sooner or later every software engineer will come across a situation that requires some kind of text parsing. The text might contain information in semi-structured form that need to get parsed and saved into data structures. Different methods can be used to tackle the text parsing problem. One approach is to develop custom code using a line split approach and then parse the separate elements. Another one can be to use a built-in scanner library function available in many programming languages. If you are interested to dive deep into the topic you can find a , covering everything from regular expressions, grammars and lexers to parsing trees and algorithms. very detailed guide here Deterministic vs Non-deterministic, what's the difference? In this article, I compare two parsing methods with a focus on their performance. The first method uses for parsing and data extraction. You can find a regular expression engine in any programming language. Great examples of regular expression library capabilities are included in perl, python, php and java. regular expressions A regular expression can be modeled by a . FSMs are quite flexible and can be used for any task that has distinct states of processing or operation. In parsing text using regular expressions, a class of FSMs is of particular interest, the Non-deterministic FSM or as they are also known the , You can easily and then use the NDFA to parse the text input. Finite State Machine (FSM) Non-deterministic Finite Automata (NDFA) convert a regular expression into a NDFA Using an NDFA in practice usually means a lot of backtracking. The algorithm has to follow every possible transition from a state to another and when a possible path fails it goes back and continues with another path. In theory, there are methods available that convert a NDFA to a Deterministic Finite Automaton (DFA). This conversion can be quite tricky when your parser is designed using regular expressions. In this article, I opted for a DFA designed from scratch as the second method to parse the text and extract the data. This allowed me to compare the two methods, the NDFA and the DFA, in terms of performance. Case study - An .ini file parser To compare the two methods, the case study of an configuration file parser and reader was used. The input file can have configuration sections that are denoted in a single line using brackets and section names, for example: ini-like [sectionA] The section line can also have a comment part: [sectionA]          ; is a comment this Comments can also exist on their own in a line: ; line contains only comment this Each section can contain multiple lines with settings in a key-value fashion. The key name must be a string and the value can take various types. The supported types are string, integer, path, array and boolean. Some examples are given below: keyname1 = keyname2 = keyname3 = .ssh/file.conf                           
keyname4 = value1,value2,value3                           
keyname5 = "A string value" 35363262 /root/ true Each setting can have overrides that are loaded instead of the main value when the user enters the flag during loading. For example, you can have multiple values for key name config_path depending on the deployment system production, staging, testing: config_path<production> = lib/config/prod.cfg               
config_path<testing> = lib/config/prod.cfg               
config_path<staging> = lib/config/prod.cfg /var/ /var/ /var/ For a more comprehensive example of the accepted input, you can check the github repository containing the code used in this article. A sample input file can be found here. Non-deterministic parser using Regular Expressions Firstly, the regular expression parser was put in action and its performance measured. The graph detailing the NDFA that was created from the regular expression is shown in graph 1. This graph implies backtracking when a path fails until all possible paths in the graph from Start to End are exhausted. In each one of the nodes, a regular expression match is tried and if it succeeds the corresponding data is extracted if applicable. Comment node expects the following regular expression to match \s*;.* Section node has a data group and expects \s*\[([\\w_]+)\]\s* For a full definition of the regular expressions used in this NDFA you can check the class that implements it in the source code. Deterministic parser using Finite State Machine Next, a parser based on an FSM implementation was build and tested on the same input data. The FSM graph is shown in graph 2. In this case, transitions between states are deterministic and depend only on the current input character. There is no backtracking and each text line is processed character by character using the FSM. States that are tagged with the isFinal flag are valid terminal states. If the input text is fully processed while the FSM is in a final state, the parsing is completed successfully. The color legend shows the states extract different data types from the input text. For example, light-green state 3 extracts the group section name. For a full definition of the FSM and its implementation in Java you can check the . source code here Performance results So what are the results of the performance comparison between the two methods? To find out, a set of text parsing operations on a large synthetic file was done. The parsing was repeated multiple times for each method and the average time was measured. The resulting data from text parsing was put onto memory in HashMap. You can see the results of the comparison for different file sizes in graph 3. The blue line shows the parsing time of NDFA for different sizes of the input file. The green line shows the parsing time of DFA for the same input size. The input size is counted in total configuration lines and the x axis scale is logarithmic. The DFA scales well and approximates a O(logN) complexity, whereas NDFA approximates a O(N) complexity. At N = 2.4M lines DFA is 4-5x faster than NDFA. This makes DFA parser an excellent parser candidate when text parsing speed is important. Conclusion In this article, I have reviewed and compared the performance of different types of Finite Automata for the task of text parsing into a data structure in memory. A Non-Deterministic Finite Automaton based on Java's Regular Expression engine was and tested. built Next, a Deterministic Finite Automaton was using a custom-built Java code FSM implementation. The DFA was found at least 4 times faster than the NDFA and having logarithmic time complexity as the input size increases. You can find the . built full code implementation used in the article in my Github repository About the author currently works as a Senior Software Architect / Technical Lead at . He likes to design and implement large-scale distributed application backends and single-page web applications, embedded with Machine Learning (ML) components. From time to time he might also get his hands dirty with Infrastructure as Code (IaC) and DevOps tasks or mini IoT projects. Spiros Dimopoulos Behavioral Signals

High Performance Text Parsing Using Finite State Machines (FSM)

I’ve noticed that apps often embed ad-hoc , with information about the current status spread out throughout . I wrote a small helper for working with finite state machines in called . In this post, I’ll go into: Redux finite state machines reducers Redux redux-machine An example of a finite state machine and how to it with redux-machine implement Advantages to using redux-machine redux-machine Example This is a very simple example of a state machine for working with data fetching, which will help show how to use redux-machine: finite state machine for handling API call state in Redux In words: INIT is the initial status When the status is `INIT` and the action type is `FETCH_USERS`, the machine transitions to `IN_PROGRESS` status. When the status is `IN_PROGRESS` and the action type is `FETCH_USERS_RESPONSE` or `FETCH_USERS_FAIL`, the machine transitions to the `INIT` (initial) status. I use the term “status” instead of “state” to avoid confusion with “state” in the Redux sense. So and are statuses. INIT IN_PROGRESS Here’s how you can implement the state machine with redux-machine: state machine implemented with redux-machine The special part is the symbol, which transitions the reducer to a different status. When the status is , acts like . When the status is , acts like . become INIT fetchUsersReducer initReducer IN_PROGRESS fetchUsersReducer inProgressReducer Redux-machine keeps the current status in the store in a non-ad-hoc and explicit way. It stores the current status in the store with the STATUS key. For example, when the status is , the value of “STATUS” is “IN_PROGRESS.” IN_PROGRESS An app can have arbitrarily many reducers created with redux-machine, and these reducers can be nested. This is helpful because any non-trivial app will have state machines within state machines. For example, if the main flow of the app is: a simplified main flow for an app then the statuses in fetchUsers will only be relevant when the main app status is LOGGED_IN. Advantages of redux-machine redux-machine makes the current status explicit and keeps your state in the redux store. Keeping all state in the store is useful for: Debugging: the entire state is easily inspectable. redux-machine is also compatible with . time-travel debugging Communicating status to the user. For example, with a loading spinner when the request is active or a “logged in” indicator when the user is logged in. and are good at modeling user workflows, but store status outside of the redux store. redux-saga redux-observable Request for Feedback I haven’t used extensively yet, so would welcome feedback and suggestions. redux-machine

A Finite State Machine Helper for Redux

Authors:
(1) Albert Gu, Machine Learning Department, Carnegie Mellon University with Equal contribution (agu@cs.cmu.edu);
(2) Tri Dao, Department of Computer Science, Princeton University with Equal contribution (tri@tridao.me). Authors: Authors: (1) Albert Gu, Machine Learning Department, Carnegie Mellon University with Equal contribution (agu@cs.cmu.edu); (2) Tri Dao, Department of Computer Science, Princeton University with Equal contribution (tri@tridao.me). Table of Links Abstract and 1. Introduction Abstract and 1. Introduction 2 State Space Models 2 State Space Models 3 Selective State Space Models and 3.1 Motivation: Selection as a Means of Compression 3 Selective State Space Models and 3.1 Motivation: Selection as a Means of Compression 3.2 Improving SSMs with Selection 3.2 Improving SSMs with Selection 3.3 Efficient Implementation of Selective SSMs 3.3 Efficient Implementation of Selective SSMs 3.4 A Simplifed SSM Architecture 3.4 A Simplifed SSM Architecture 3.5 Properties of Selection Mechanisms 3.5 Properties of Selection Mechanisms 3.6 Additional Model Details 3.6 Additional Model Details 4 Empirical Evaluation and 4.1 Synthetic Tasks 4 Empirical Evaluation and 4.1 Synthetic Tasks 4.2 Language Modeling 4.2 Language Modeling 4.3 DNA Modeling 4.3 DNA Modeling 4.4 Audio Modeling and Generation 4.4 Audio Modeling and Generation 4.5 Speed and Memory Benchmarks 4.5 Speed and Memory Benchmarks 4.6 Model Ablations 4.6 Model Ablations 5 Discussion 5 Discussion 6 Conclusion, Acknowledgments and References 6 Conclusion, Acknowledgments and References A Discussion: Selection Mechanism A Discussion: Selection Mechanism B Related Work and B.1 S4 Variants and Derivatives B Related Work and B.1 S4 Variants and Derivatives B.2 SSM Architectures B.2 SSM Architectures B.3 Relationship to RNNs B.3 Relationship to RNNs B.4 Linear Attention and B.5 Long Context Models B.4 Linear Attention and B.5 Long Context Models C Mechanics of Selective SSMs C Mechanics of Selective SSMs D Hardware-aware Algorithm For Selective SSMs D Hardware-aware Algorithm For Selective SSMs E Experimental Details and Additional Results and E.1 Synthetic Tasks E Experimental Details and Additional Results and E.1 Synthetic Tasks E.2 Language Modeling E.2 Language Modeling E.3 DNA Modeling E.3 DNA Modeling E.4 Audio Details E.4 Audio Details E.5 Efficiency Benchmark E.5 Efficiency Benchmark 3 Selective State Space Models We motivate our selection mechanism using intuition from synthetic tasks (Section 3.1), then explain how to incorporate this mechanism into state space models (Section 3.2). The resulting time-varying SSMs cannot use convolutions, presenting a technical challenge of how to compute them efficiently. We overcome this with a hardware-aware algorithm that exploits the memory hierarchy on modern hardware (Section 3.3). We then describe a simple SSM architecture without attention or even MLP blocks (Section 3.4). Finally, we discuss some additional properties of selection mechanisms (Section 3.5). 3.1 Motivation: Selection as a Means of Compression We argue that a fundamental problem of sequence modeling is compressing context into a smaller state. In fact, we can view the tradeoffs of popular sequence models from this point of view. For example, attention is both effective and inefficient because it explicitly does not compress context at all. This can be seen from the fact that autoregressive inference requires explicitly storing the entire context (i.e. the KV cache), which directly causes the slow linear-time inference and quadratic-time training of Transformers. On the other hand, recurrent models are efficient because they have a finite state, implying constant-time inference and linear-time training. However, their effectiveness is limited by how well this state has compressed the context. To understand this principle, we focus on two running examples of synthetic tasks (Figure 2). • The Selective Copying task modifies the popular Copying task (Arjovsky, Shah, and Bengio 2016) by varying the position of the tokens to memorize. It requires content-aware reasoning to be able to memorize the relevant tokens (colored) and filter out the irrelevant ones (white). • The Induction Heads task is a well-known mechanism hypothesized to explain the majority of in-context learning abilities of LLMs (Olsson et al. 2022). It requires context-aware reasoning to know when to produce the correct output in the appropriate context (black). In summary, the efficiency vs. effectiveness tradeoff of sequence models is characterized by how well they compress their state: efficient models must have a small state, while effective models must have a state that contains all necessary information from the context. In turn, we propose that a fundamental principle for building sequence models is selectivity: or the context-aware ability to focus on or filter out inputs into a sequential state. In particular, a selection mechanism controls how information propagates or interacts along the sequence dimension (see Section 3.5 for more discussion). 3.2 Improving SSMs with Selection One method of incorporating a selection mechanism into models is by letting their parameters that affect interactions along the sequence (e.g. the recurrent dynamics of an RNN or the convolution kernel of a CNN) be input-dependent. This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv

Transformers Are Powerful, but Selective State Space Models Just Might Be Smarter

Can We Simulate Quantum Phenomena? The FPGA Coprocessor Experiment

Authors:
(1) Jongmin Lee, Department of Mathematical Science, Seoul National University;
(2) Ernest K. Ryu, Department of Mathematical Science, Seoul National University and Interdisciplinary Program in Artificial Intelligence, Seoul National University. Abstract and 1 Introduction 1.1 Notations and preliminaries 1.2 Prior works 2 Anchored Value Iteration 2.1 Accelerated rate for Bellman consistency operator 2.2 Accelerated rate for Bellman optimality opera 3 Convergence when y=1 4 Complexity lower bound 5 Approximate Anchored Value Iteration 6 Gauss–Seidel Anchored Value Iteration 7 Conclusion, Acknowledgments and Disclosure of Funding and References A Preliminaries B Omitted proofs in Section 2 C Omitted proofs in Section 3 D Omitted proofs in Section 4 E Omitted proofs in Section 5 F Omitted proofs in Section 6 G Broader Impacts H Limitations 3 Convergence when y=1 Undiscounted MDPs are not commonly studied in the DP and RL theory literature due to the following difficulties: Bellman consistency and optimality operators may not have fixed points, VI is a nonexpansive (not contractive) fixed-point iteration and may not convergence to a fixed point even if one exist, and the interpretation of a fixed point as the (optimal) value function becomes unclear when the fixed point is not unique. However, many modern deep RL setups actually do not use discounting, [2] and this empirical practice makes the theoretical analysis with γ = 1 relevant. In this section, we show that Anc-VI converges to fixed points of the Bellman consistency and optimality operators of undiscounted MDPs. While a full treatment of undiscounted MDPs is beyond the scope of this paper, we show that fixed points, if one exists, can be found, and we therefore argue that the inability to find fixed points should not be considered an obstacle in studying the γ = 1 setup. We first state our convergence result for finite state-action spaces. This paper is available on arxiv under CC BY 4.0 DEED license. [3] Well-definedness of T requires a σ-algebra on state and action spaces, expectation with respect to transition probability and policy to be well defined, boundedness and measurability of the output of Bellman operator, etc. Authors: (1) Jongmin Lee, Department of Mathematical Science, Seoul National University; (2) Ernest K. Ryu, Department of Mathematical Science, Seoul National University and Interdisciplinary Program in Artificial Intelligence, Seoul National University. Authors: Authors: (1) Jongmin Lee, Department of Mathematical Science, Seoul National University; (2) Ernest K. Ryu, Department of Mathematical Science, Seoul National University and Interdisciplinary Program in Artificial Intelligence, Seoul National University. Abstract and 1 Introduction Abstract and 1 Introduction 1.1 Notations and preliminaries 1.1 Notations and preliminaries 1.2 Prior works 1.2 Prior works 2 Anchored Value Iteration 2 Anchored Value Iteration 2.1 Accelerated rate for Bellman consistency operator 2.1 Accelerated rate for Bellman consistency operator 2.2 Accelerated rate for Bellman optimality opera 2.2 Accelerated rate for Bellman optimality opera 3 Convergence when y=1 3 Convergence when y=1 4 Complexity lower bound 4 Complexity lower bound 5 Approximate Anchored Value Iteration 5 Approximate Anchored Value Iteration 6 Gauss–Seidel Anchored Value Iteration 6 Gauss–Seidel Anchored Value Iteration 7 Conclusion, Acknowledgments and Disclosure of Funding and References 7 Conclusion, Acknowledgments and Disclosure of Funding and References A Preliminaries A Preliminaries B Omitted proofs in Section 2 B Omitted proofs in Section 2 C Omitted proofs in Section 3 C Omitted proofs in Section 3 D Omitted proofs in Section 4 D Omitted proofs in Section 4 E Omitted proofs in Section 5 E Omitted proofs in Section 5 F Omitted proofs in Section 6 F Omitted proofs in Section 6 G Broader Impacts G Broader Impacts H Limitations H Limitations 3 Convergence when y=1 Undiscounted MDPs are not commonly studied in the DP and RL theory literature due to the following difficulties: Bellman consistency and optimality operators may not have fixed points, VI is a nonexpansive (not contractive) fixed-point iteration and may not convergence to a fixed point even if one exist, and the interpretation of a fixed point as the (optimal) value function becomes unclear when the fixed point is not unique. However, many modern deep RL setups actually do not use discounting, [2] and this empirical practice makes the theoretical analysis with γ = 1 relevant. In this section, we show that Anc-VI converges to fixed points of the Bellman consistency and optimality operators of undiscounted MDPs. While a full treatment of undiscounted MDPs is beyond the scope of this paper, we show that fixed points, if one exists, can be found, and we therefore argue that the inability to find fixed points should not be considered an obstacle in studying the γ = 1 setup. We first state our convergence result for finite state-action spaces. This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv [3] Well-definedness of T requires a σ-algebra on state and action spaces, expectation with respect to transition probability and policy to be well defined, boundedness and measurability of the output of Bellman operator, etc.

Why Anc-VI is Crucial for Undiscounted Reinforcement Learning

Authors:
(1) Albert Gu, Machine Learning Department, Carnegie Mellon University and with equal contribution;
(2) Tri Dao, Department of Computer Science, Princeton University and with equal contribution. Table of Links Abstract and 1 Introduction 2 State Space Models 3 Selective State Space Models and 3.1 Motivation: Selection as a Means of Compression 3.2 Improving SSMs with Selection 3.3 Efficient Implementation of Selective SSMs 3.4 A Simplified SSM Architecture 3.5 Properties of Selection Mechanisms 3.6 Additional Model Details 4 Empirical Evaluation and 4.1 Synthetic Tasks 4.2 Language Modeling 4.3 DNA Modeling 4.4 Audio Modeling and Generation 4.5 Speed and Memory Benchmarks 4.6 Model Ablations 5 Discussion 6 Conclusion and References A Discussion: Selection Mechanism B Related Work C Mechanics of Selective SSMs D Hardware-aware Algorithm For Selective SSMs E Experimental Details and Additional Results 3 Selective State Space Models We motivate our selection mechanism using intuition from synthetic tasks (Section 3.1), then explain how to incorporate this mechanism into state space models (Section 3.2). The resulting time-varying SSMs cannot use convolutions, presenting a technical challenge of how to compute them efficiently. We overcome this with a hardware-aware algorithm that exploits the memory hierarchy on modern hardware (Section 3.3). We then describe a simple SSM architecture without attention or even MLP blocks (Section 3.4). Finally, we discuss some additional properties of selection mechanisms (Section 3.5). 3.1 Motivation: Selection as a Means of Compression We argue that a fundamental problem of sequence modeling is compressing context into a smaller state. In fact, we can view the tradeoffs of popular sequence models from this point of view. For example, attention is both effective and inefficient because it explicitly does not compress context at all. This can be seen from the fact that autoregressive inference requires explicitly storing the entire context (i.e. the KV cache), which directly causes the slow linear-time inference and quadratic-time training of Transformers. On the other hand, recurrent models are efficient because they have a finite state, implying constant-time inference and linear-time training. However, their effectiveness is limited by how well this state has compressed the context. To understand this principle, we focus on two running examples of synthetic tasks (Figure 2). • The Selective Copying task modifies the popular Copying task (Arjovsky, Shah, and Bengio 2016) by varying the position of the tokens to memorize. It requires content-aware reasoning to be able to memorize the relevant tokens (colored) and filter out the irrelevant ones (white). • The Induction Heads task is a well-known mechanism hypothesized to explain the majority of in-context learning abilities of LLMs (Olsson et al. 2022). It requires context-aware reasoning to know when to produce the correct output in the appropriate context (black). In summary, the efficiency vs. effectiveness tradeoff of sequence models is characterized by how well they compress their state: efficient models must have a small state, while effective models must have a state that contains all necessary information from the context. In turn, we propose that a fundamental principle for building sequence models is selectivity: or the context-aware ability to focus on or filter out inputs into a sequential state. In particular, a selection mechanism controls how information propagates or interacts along the sequence dimension (see Section 3.5 for more discussion). This paper is available on arxiv under CC BY 4.0 DEED license. Authors: (1) Albert Gu, Machine Learning Department, Carnegie Mellon University and with equal contribution; (2) Tri Dao, Department of Computer Science, Princeton University and with equal contribution. Authors: Authors: (1) Albert Gu, Machine Learning Department, Carnegie Mellon University and with equal contribution; (2) Tri Dao, Department of Computer Science, Princeton University and with equal contribution. Table of Links Abstract and 1 Introduction Abstract and 1 Introduction 2 State Space Models 2 State Space Models 3 Selective State Space Models and 3.1 Motivation: Selection as a Means of Compression 3 Selective State Space Models and 3.1 Motivation: Selection as a Means of Compression 3.2 Improving SSMs with Selection 3.2 Improving SSMs with Selection 3.3 Efficient Implementation of Selective SSMs 3.3 Efficient Implementation of Selective SSMs 3.4 A Simplified SSM Architecture 3.4 A Simplified SSM Architecture 3.5 Properties of Selection Mechanisms 3.5 Properties of Selection Mechanisms 3.6 Additional Model Details 3.6 Additional Model Details 4 Empirical Evaluation and 4.1 Synthetic Tasks 4 Empirical Evaluation and 4.1 Synthetic Tasks 4.2 Language Modeling 4.2 Language Modeling 4.3 DNA Modeling 4.3 DNA Modeling 4.4 Audio Modeling and Generation 4.4 Audio Modeling and Generation 4.5 Speed and Memory Benchmarks 4.5 Speed and Memory Benchmarks 4.6 Model Ablations 4.6 Model Ablations 5 Discussion 5 Discussion 6 Conclusion and References 6 Conclusion and References A Discussion: Selection Mechanism A Discussion: Selection Mechanism B Related Work B Related Work C Mechanics of Selective SSMs C Mechanics of Selective SSMs D Hardware-aware Algorithm For Selective SSMs D Hardware-aware Algorithm For Selective SSMs E Experimental Details and Additional Results E Experimental Details and Additional Results 3 Selective State Space Models We motivate our selection mechanism using intuition from synthetic tasks (Section 3.1), then explain how to incorporate this mechanism into state space models (Section 3.2). The resulting time-varying SSMs cannot use convolutions, presenting a technical challenge of how to compute them efficiently. We overcome this with a hardware-aware algorithm that exploits the memory hierarchy on modern hardware (Section 3.3). We then describe a simple SSM architecture without attention or even MLP blocks (Section 3.4). Finally, we discuss some additional properties of selection mechanisms (Section 3.5). 3.1 Motivation: Selection as a Means of Compression We argue that a fundamental problem of sequence modeling is compressing context into a smaller state. In fact, we can view the tradeoffs of popular sequence models from this point of view. For example, attention is both effective and inefficient because it explicitly does not compress context at all. This can be seen from the fact that autoregressive inference requires explicitly storing the entire context (i.e. the KV cache), which directly causes the slow linear-time inference and quadratic-time training of Transformers. On the other hand, recurrent models are efficient because they have a finite state, implying constant-time inference and linear-time training. However, their effectiveness is limited by how well this state has compressed the context. To understand this principle, we focus on two running examples of synthetic tasks (Figure 2). • The Selective Copying task modifies the popular Copying task (Arjovsky, Shah, and Bengio 2016) by varying the position of the tokens to memorize. It requires content-aware reasoning to be able to memorize the relevant tokens (colored) and filter out the irrelevant ones (white). • The Induction Heads task is a well-known mechanism hypothesized to explain the majority of in-context learning abilities of LLMs (Olsson et al. 2022). It requires context-aware reasoning to know when to produce the correct output in the appropriate context (black). In summary, the efficiency vs. effectiveness tradeoff of sequence models is characterized by how well they compress their state: efficient models must have a small state, while effective models must have a state that contains all necessary information from the context. In turn, we propose that a fundamental principle for building sequence models is selectivity: or the context-aware ability to focus on or filter out inputs into a sequential state. In particular, a selection mechanism controls how information propagates or interacts along the sequence dimension (see Section 3.5 for more discussion). This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv

Why Compressing Information Helps AI Work Better

Taming LLMs with Langchain + Langgraph

Exploring Drone Dynamics: Stability and Force Generation in Multimedia Design

Authors:
(1) Kexun Zhang, UC Santa Barbara and Equal contribution;
(2) Hongqiao Chen, Northwood High School and Equal contribution;
(3) Lei Li, Carnegie Mellon University;
(4) William Yang Wang,UC Santa Barbara. Table of Links Abstract and Intro
Related Work
ToolDec: LLM Tool Use via Finite-State Decoding
Experiment: ToolDec Eliminates Syntax Errors
Experiment: ToolDec Enables Generalizable Tool Selection
Conclusion and References
Appendix 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. This paper is available on arxiv under CC 4.0 DEED license. Authors: (1) Kexun Zhang, UC Santa Barbara and Equal contribution; (2) Hongqiao Chen, Northwood High School and Equal contribution; (3) Lei Li, Carnegie Mellon University; (4) William Yang Wang,UC Santa Barbara. Authors: Authors: (1) Kexun Zhang, UC Santa Barbara and Equal contribution; (2) Hongqiao Chen, Northwood High School and Equal contribution; (3) Lei Li, Carnegie Mellon University; (4) William Yang Wang,UC Santa Barbara. Table of Links Abstract and Intro Related Work ToolDec: LLM Tool Use via Finite-State Decoding Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Enables Generalizable Tool Selection Conclusion and References Appendix Abstract and Intro Abstract and Intro Related Work Related Work ToolDec: LLM Tool Use via Finite-State Decoding ToolDec: LLM Tool Use via Finite-State Decoding Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Enables Generalizable Tool Selection Experiment: ToolDec Enables Generalizable Tool Selection Conclusion and References Conclusion and References Appendix Appendix 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. Fine-tuning language models to use tools. 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. In-context learning for tool use. 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. Constrained decoding and finite-state machines. This paper is available on arxiv under CC 4.0 DEED license. This paper is available on arxiv under CC 4.0 DEED license. available on arxiv

Syntax Error-Free and Generalizable Tool Use for LLMs: Related Work

LLM-এর জন্য সিনট্যাক্স ত্রুটি-মুক্ত এবং সাধারণীকরণযোগ্য টুল ব্যবহার: সম্পর্কিত কাজ

Syntaxfehlerfreier und verallgemeinerbarer Tooleinsatz für LLMs: Verwandte Arbeiten

Uso de herramientas generalizables y sin errores de sintaxis para LLM: trabajo relacionado

Utilisation d'outils de syntaxe sans erreur et généralisables pour les LLM : travaux connexes

एलएलएम के लिए वाक्यविन्यास त्रुटि-मुक्त और सामान्यीकरण योग्य उपकरण का उपयोग: संबंधित कार्य

LLM における構文エラーのない一般化可能なツールの使用: 関連研究

LLM을 위한 구문 오류가 없고 일반화 가능한 도구 사용: 관련 작업

Uso de ferramenta generalizável e livre de erros de sintaxe para LLMs: trabalho relacionado

Использование без синтаксических ошибок и обобщенного инструмента для программ LLM: сопутствующие работы

Yüksek Lisans'lar için Sözdizimi Hatasız ve Genelleştirilebilir Araç Kullanımı: İlgili Çalışma

Sử dụng công cụ không có lỗi và có thể khái quát hóa cho LLM: Công việc liên quan

语法无错误且可推广的法学硕士 (LLM) 工具使用：相关工作

Authors:
(1) Kexun Zhang, UC Santa Barbara and Equal contribution;
(2) Hongqiao Chen, Northwood High School and Equal contribution;
(3) Lei Li, Carnegie Mellon University;
(4) William Yang Wang,UC Santa Barbara. Table of Links Abstract and Intro
Related Work
ToolDec: LLM Tool Use via Finite-State Decoding
Experiment: ToolDec Eliminates Syntax Errors
Experiment: ToolDec Enables Generalizable Tool Selection
Conclusion and References
Appendix 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 TOOLDEC is guided by a finite-state machine (FSM). An FSM is a 5-tuple (S, V, g, s0, R), consisting of a finite state set S, an alphabet V , a transition function g : S ×V → S, an initial state s0 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 ‘’. 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, ·) is defined. These 3.2 CONSTRUCTING FSMS THAT GUARANTEE SYNTACTICALLY CORRECT TOOL CALLS 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. 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. This paper is available on arxiv under CC 4.0 DEED license. Authors: (1) Kexun Zhang, UC Santa Barbara and Equal contribution; (2) Hongqiao Chen, Northwood High School and Equal contribution; (3) Lei Li, Carnegie Mellon University; (4) William Yang Wang,UC Santa Barbara. Authors: Authors: (1) Kexun Zhang, UC Santa Barbara and Equal contribution; (2) Hongqiao Chen, Northwood High School and Equal contribution; (3) Lei Li, Carnegie Mellon University; (4) William Yang Wang,UC Santa Barbara. Table of Links Abstract and Intro Related Work ToolDec: LLM Tool Use via Finite-State Decoding Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Enables Generalizable Tool Selection Conclusion and References Appendix Abstract and Intro Abstract and Intro Related Work Related Work ToolDec: LLM Tool Use via Finite-State Decoding ToolDec: LLM Tool Use via Finite-State Decoding Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Enables Generalizable Tool Selection Experiment: ToolDec Enables Generalizable Tool Selection Conclusion and References Conclusion and References Appendix Appendix 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. • Switching Modes. • Generating Tool Names. At the beginning of a tool call, only generate correct existent tool names from a pre-defined list of tools. • Generating Tool Names. • Passing Arguments. Only pass type-conforming arguments to the tool. • Passing Arguments. 3.1 FINITE-STATE DECODING TOOLDEC is guided by a finite-state machine (FSM). An FSM is a 5-tuple (S, V, g, s0, R), consisting of a finite state set S, an alphabet V , a transition function g : S ×V → S, an initial state s0 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 ‘’. 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, ·) is defined. These 3.2 CONSTRUCTING FSMS THAT GUARANTEE SYNTACTICALLY CORRECT TOOL CALLS 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. 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. Generating Syntactically Valid Tool Arguments. This paper is available on arxiv under CC 4.0 DEED license. This paper is available on arxiv under CC 4.0 DEED license. available on arxiv

Syntax Error-Free and Generalizable Tool Use for LLMs: ToolDec

LLM-এর জন্য সিনট্যাক্স ত্রুটি-মুক্ত এবং সাধারণীকরণযোগ্য টুল ব্যবহার: টুলডেক

Syntaxfehlerfreier und verallgemeinerbarer Tooleinsatz für LLMs: ToolDec

Uso de herramientas generalizables y sin errores de sintaxis para LLM: ToolDec

Utilisation d'outils de syntaxe sans erreur et généralisables pour les LLM : ToolDec

LLM के लिए वाक्यविन्यास त्रुटि-रहित और सामान्यीकृत उपकरण उपयोग: ToolDec

LLM 向けの構文エラーのない一般化可能なツールの使用: ToolDec

LLM을 위한 구문 오류가 없고 일반화 가능한 도구 사용: ToolDec

Uso de ferramenta generalizável e livre de erros de sintaxe para LLMs: ToolDec

Синтаксис без ошибок и универсальное использование инструмента для LLM: ToolDec

Yüksek Lisans'lar için Sözdizimi Hatasız ve Genelleştirilebilir Araç Kullanımı: ToolDec

Sử dụng công cụ không có lỗi và có thể khái quát hóa cho LLM: ToolDec

语法无错误且可推广的法学硕士 (LLM) 工具使用：ToolDec

Authors:
(1) Kexun Zhang, UC Santa Barbara and Equal contribution;
(2) Hongqiao Chen, Northwood High School and Equal contribution;
(3) Lei Li, Carnegie Mellon University;
(4) William Yang Wang,UC Santa Barbara. Table of Links Abstract and Intro
Related Work
ToolDec: LLM Tool Use via Finite-State Decoding
Experiment: ToolDec Eliminates Syntax Errors
Experiment: ToolDec Enables Generalizable Tool Selection
Conclusion and References
Appendix 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 Figure 5a, 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 Figure 5b. 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. 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. This paper is available on arxiv under CC 4.0 DEED license. Authors: (1) Kexun Zhang, UC Santa Barbara and Equal contribution; (2) Hongqiao Chen, Northwood High School and Equal contribution; (3) Lei Li, Carnegie Mellon University; (4) William Yang Wang,UC Santa Barbara. Authors: Authors: (1) Kexun Zhang, UC Santa Barbara and Equal contribution; (2) Hongqiao Chen, Northwood High School and Equal contribution; (3) Lei Li, Carnegie Mellon University; (4) William Yang Wang,UC Santa Barbara. Table of Links Abstract and Intro Related Work ToolDec: LLM Tool Use via Finite-State Decoding Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Enables Generalizable Tool Selection Conclusion and References Appendix Abstract and Intro Abstract and Intro Related Work Related Work ToolDec: LLM Tool Use via Finite-State Decoding ToolDec: LLM Tool Use via Finite-State Decoding Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Enables Generalizable Tool Selection Experiment: ToolDec Enables Generalizable Tool Selection Conclusion and References Conclusion and References Appendix Appendix 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 Math Functions. 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. Benchmark on Knowledge Graph Relations. 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. Benchmark on APIs for Real-World Web Services. 5.3 EXPERIMENT RESULTS Generalization to Unseen Math Functions. In Figure 5a, 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 Math Functions. Generalization to Unseen Knowledge Graph Functions. We present our results on KAMEL in Figure 5b. 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. Generalization to Unseen Knowledge Graph Functions. 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. Generalization to Unseen Web Services. 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. This paper is available on arxiv under CC 4.0 DEED license. This paper is available on arxiv under CC 4.0 DEED license. available on arxiv

Syntax Error-Free and Generalizable Tool Use for LLMs: ToolDec Enables Generalizable Tool Selection

সিনট্যাক্স ত্রুটি-মুক্ত এবং LLM-এর জন্য সাধারণীকরণযোগ্য টুল ব্যবহার: ToolDec সাধারণীকরণযোগ্য টুল নির্বাচন সক্ষম করে

Syntaxfehlerfreier und verallgemeinerbarer Werkzeugeinsatz für LLMs: ToolDec ermöglicht verallgemeinerbare Werkzeugauswahl

Uso de herramientas generalizables y sin errores de sintaxis para LLM: ToolDec permite la selección de herramientas generalizables

Utilisation d'outils de syntaxe sans erreur et généralisables pour les LLM : ToolDec permet la sélection d'outils généralisables

LLM के लिए वाक्यविन्यास त्रुटि-रहित और सामान्यीकरण योग्य टूल का उपयोग: ToolDec सामान्यीकरण योग्य टूल चयन को सक्षम करता है

LLM 向けの構文エラーのない一般化可能なツールの使用: ToolDec により一般化可能なツール選択が可能

LLM을 위한 구문 오류가 없고 일반화 가능한 도구 사용: ToolDec을 통해 일반화 가능한 도구 선택 가능

Uso de ferramenta generalizável e livre de erros de sintaxe para LLMs: ToolDec permite seleção de ferramenta generalizável

Без синтаксических ошибок и универсальное использование инструментов для LLM: ToolDec обеспечивает универсальный выбор инструментов

Yüksek Lisans'lar için Sözdizimi Hatasız ve Genelleştirilebilir Araç Kullanımı: ToolDec Genelleştirilebilir Araç Seçimini Etkinleştirir

Sử dụng công cụ không có lỗi và có thể khái quát hóa cho LLM: ToolDec cho phép lựa chọn công cụ có thể khái quát hóa

语法无错误且可通用的 LLM 工具使用：ToolDec 支持通用工具选择

Authors:
(1) Kexun Zhang, UC Santa Barbara and Equal contribution;
(2) Hongqiao Chen, Northwood High School and Equal contribution;
(3) Lei Li, Carnegie Mellon University;
(4) William Yang Wang,UC Santa Barbara. Table of Links Abstract and Intro
Related Work
ToolDec: LLM Tool Use via Finite-State Decoding
Experiment: ToolDec Eliminates Syntax Errors
Experiment: ToolDec Enables Generalizable Tool Selection
Conclusion and References
Appendix 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. 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 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. The high tool error rate of the baselines suggests that even after instruction finetuning, 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. 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. This paper is available on arxiv under CC 4.0 DEED license. Authors: (1) Kexun Zhang, UC Santa Barbara and Equal contribution; (2) Hongqiao Chen, Northwood High School and Equal contribution; (3) Lei Li, Carnegie Mellon University; (4) William Yang Wang,UC Santa Barbara. Authors: Authors: (1) Kexun Zhang, UC Santa Barbara and Equal contribution; (2) Hongqiao Chen, Northwood High School and Equal contribution; (3) Lei Li, Carnegie Mellon University; (4) William Yang Wang,UC Santa Barbara. Table of Links Abstract and Intro Related Work ToolDec: LLM Tool Use via Finite-State Decoding Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Enables Generalizable Tool Selection Conclusion and References Appendix Abstract and Intro Abstract and Intro Related Work Related Work ToolDec: LLM Tool Use via Finite-State Decoding ToolDec: LLM Tool Use via Finite-State Decoding Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Enables Generalizable Tool Selection Experiment: ToolDec Enables Generalizable Tool Selection Conclusion and References Conclusion and References Appendix Appendix 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 (Qin et al., 2023). 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. ToolEval, Pass Rate Win Rate Tool Error Rate 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. ToolkenGPT (Hao et al., 2023). 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”. ToolLLM+TOOLDEC. 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. ToolkenGPT+TOOLDEC. 4.3 EXPERIMENTAL RESULTS 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. TOOLDEC enhances in-context learning tool LLMs. The high tool error rate of the baselines suggests that even after instruction finetuning, 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. 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. TOOLDEC enhances fine-tuning tool LLMs. This paper is available on arxiv under CC 4.0 DEED license. This paper is available on arxiv under CC 4.0 DEED license. available on arxiv

Syntax Error-Free and Generalizable Tool Use for LLMs: ToolDec Eliminates Syntax Errors

LLM-এর জন্য সিনট্যাক্স ত্রুটি-মুক্ত এবং সাধারণীকরণযোগ্য টুল ব্যবহার: টুলডেক সিনট্যাক্স ত্রুটি দূর করে

Syntaxfehlerfreier und verallgemeinerbarer Tool-Einsatz für LLMs: ToolDec eliminiert Syntaxfehler

Uso de herramientas generalizables y sin errores de sintaxis para LLM: ToolDec elimina los errores de sintaxis

Utilisation d'un outil sans erreur de syntaxe et généralisable pour les LLM : ToolDec élimine les erreurs de syntaxe

एलएलएम के लिए वाक्यविन्यास त्रुटि-मुक्त और सामान्यीकृत उपकरण का उपयोग: टूलडेक वाक्यविन्यास त्रुटियों को समाप्त करता है

LLM 向けの構文エラーのない汎用ツールの使用: ToolDec は構文エラーを排除します

LLM을 위한 구문 오류가 없고 일반화 가능한 도구 사용: ToolDec은 구문 오류를 제거합니다.

Uso de ferramenta generalizável e livre de erros de sintaxe para LLMs: ToolDec elimina erros de sintaxe

Синтаксические ошибки и универсальное использование инструмента для LLM: ToolDec устраняет синтаксические ошибки

LLM'ler için Sözdizimi Hatasız ve Genelleştirilebilir Araç Kullanımı: ToolDec, Sözdizimi Hatalarını Ortadan Kaldırır

Sử dụng công cụ không có lỗi và có thể khái quát hóa cho LLM: ToolDec Loại bỏ lỗi cú pháp

语法无错误且可推广的法学硕士 (LLM) 工具使用：ToolDec 可消除语法错误

Authors:
(1) Kexun Zhang, UC Santa Barbara and Equal contribution;
(2) Hongqiao Chen, Northwood High School and Equal contribution;
(3) Lei Li, Carnegie Mellon University;
(4) William Yang Wang,UC Santa Barbara. Table of Links Abstract and Intro
Related Work
ToolDec: LLM Tool Use via Finite-State Decoding
Experiment: ToolDec Eliminates Syntax Errors
Experiment: ToolDec Enables Generalizable Tool Selection
Conclusion and References
Appendix A. APPENDIX A.1 PSEUDO-CODE OF THE DECODING ALGORITHM A.2 GENERALIZING TOOLKENGPT TO UNSEEN NEW TOOLS 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. A.4 EXAMPLES OF KAMEL RELATIONS This paper is available on arxiv under CC 4.0 DEED license. Authors: (1) Kexun Zhang, UC Santa Barbara and Equal contribution; (2) Hongqiao Chen, Northwood High School and Equal contribution; (3) Lei Li, Carnegie Mellon University; (4) William Yang Wang,UC Santa Barbara. Authors: Authors: (1) Kexun Zhang, UC Santa Barbara and Equal contribution; (2) Hongqiao Chen, Northwood High School and Equal contribution; (3) Lei Li, Carnegie Mellon University; (4) William Yang Wang,UC Santa Barbara. Table of Links Abstract and Intro Related Work ToolDec: LLM Tool Use via Finite-State Decoding Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Enables Generalizable Tool Selection Conclusion and References Appendix Abstract and Intro Abstract and Intro Related Work Related Work ToolDec: LLM Tool Use via Finite-State Decoding ToolDec: LLM Tool Use via Finite-State Decoding Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Enables Generalizable Tool Selection Experiment: ToolDec Enables Generalizable Tool Selection Conclusion and References Conclusion and References Appendix Appendix A. APPENDIX A.1 PSEUDO-CODE OF THE DECODING ALGORITHM A.2 GENERALIZING TOOLKENGPT TO UNSEEN NEW TOOLS 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. A.4 EXAMPLES OF KAMEL RELATIONS This paper is available on arxiv under CC 4.0 DEED license. This paper is available on arxiv under CC 4.0 DEED license. available on arxiv

Syntax Error-Free and Generalizable Tool Use for LLMs: Appendix

LLM-এর জন্য সিনট্যাক্স ত্রুটি-মুক্ত এবং সাধারণীকরণযোগ্য টুল ব্যবহার: পরিশিষ্ট

Syntaxfehlerfreier und verallgemeinerbarer Werkzeugeinsatz für LLMs: Anhang

Uso de herramientas generalizables y sin errores de sintaxis para LLM: Apéndice

Utilisation d'un outil de syntaxe sans erreur et généralisable pour les LLM : Annexe

एलएलएम के लिए वाक्यविन्यास त्रुटि-रहित और सामान्यीकरण योग्य उपकरण का उपयोग: परिशिष्ट

LLM のための構文エラーのない一般化可能なツールの使用: 付録

LLM을 위한 구문 오류가 없고 일반화 가능한 도구 사용: 부록

Uso de ferramenta generalizável e livre de erros de sintaxe para LLMs: Apêndice

Использование без синтаксических ошибок и универсального инструмента для программ LLM: Приложение

Yüksek Lisans için Sözdizimi Hatasız ve Genelleştirilebilir Araç Kullanımı: Ek

Sử dụng công cụ không có lỗi và có thể khái quát hóa cho LLM: Phụ lục

语法无错误且可推广的法学硕士 (LLM) 工具使用：附录

Authors:
(1) Kexun Zhang, UC Santa Barbara and Equal contribution;
(2) Hongqiao Chen, Northwood High School and Equal contribution;
(3) Lei Li, Carnegie Mellon University;
(4) William Yang Wang,UC Santa Barbara. Table of Links Abstract and Intro
Related Work
ToolDec: LLM Tool Use via Finite-State Decoding
Experiment: ToolDec Eliminates Syntax Errors
Experiment: ToolDec Enables Generalizable Tool Selection
Conclusion and References
Appendix 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 [1] 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. 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. This paper is available on arxiv under CC 4.0 DEED license. [1] We release our code and data at https://github.com/chenhongqiao/tooldec. Authors: (1) Kexun Zhang, UC Santa Barbara and Equal contribution; (2) Hongqiao Chen, Northwood High School and Equal contribution; (3) Lei Li, Carnegie Mellon University; (4) William Yang Wang,UC Santa Barbara. Authors: Authors: (1) Kexun Zhang, UC Santa Barbara and Equal contribution; (2) Hongqiao Chen, Northwood High School and Equal contribution; (3) Lei Li, Carnegie Mellon University; (4) William Yang Wang,UC Santa Barbara. Table of Links Abstract and Intro Related Work ToolDec: LLM Tool Use via Finite-State Decoding Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Enables Generalizable Tool Selection Conclusion and References Appendix Abstract and Intro Abstract and Intro Related Work Related Work ToolDec: LLM Tool Use via Finite-State Decoding ToolDec: LLM Tool Use via Finite-State Decoding Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Enables Generalizable Tool Selection Experiment: ToolDec Enables Generalizable Tool Selection Conclusion and References Conclusion and References Appendix Appendix 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 [1] 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. 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. This paper is available on arxiv under CC 4.0 DEED license. This paper is available on arxiv under CC 4.0 DEED license. available on arxiv [1] We release our code and data at https://github.com/chenhongqiao/tooldec.

Syntax Error-Free and Generalizable Tool Use for LLMs: Abstract and Intro

LLM-এর জন্য সিনট্যাক্স ত্রুটি-মুক্ত এবং সাধারণীকরণযোগ্য টুল ব্যবহার: বিমূর্ত এবং ভূমিকা

Syntaxfehlerfreier und generalisierbarer Tooleinsatz für LL.M.: Abstract und Intro

Uso de herramientas generalizables y sin errores de sintaxis para LLM: resumen e introducción

Utilisation d'un outil de syntaxe sans erreur et généralisable pour les LLM : résumé et introduction

एलएलएम के लिए वाक्यविन्यास त्रुटि-रहित और सामान्यीकरण योग्य उपकरण का उपयोग: सार और परिचय

LLM のための構文エラーのない一般化可能なツールの使用: 概要と概要

LLM을 위한 구문 오류가 없고 일반화 가능한 도구 사용: 초록 및 소개

Uso de ferramenta generalizável e livre de erros de sintaxe para LLMs: Resumo e introdução

Синтаксическое безошибочное и обобщенное использование инструментов для студентов LLM: Аннотация и введение

LLM'ler için Sözdizimi Hatasız ve Genelleştirilebilir Araç Kullanımı: Özet ve Giriş

Sử dụng công cụ không có lỗi và có thể khái quát hóa cho LLM: Tóm tắt và giới thiệu

语法无错误且可推广的法学硕士 (LLM) 工具使用：摘要和简介

Authors:
(1) Kexun Zhang, UC Santa Barbara and Equal contribution;
(2) Hongqiao Chen, Northwood High School and Equal contribution;
(3) Lei Li, Carnegie Mellon University;
(4) William Yang Wang,UC Santa Barbara. Table of Links Abstract and Intro
Related Work
ToolDec: LLM Tool Use via Finite-State Decoding
Experiment: ToolDec Eliminates Syntax Errors
Experiment: ToolDec Enables Generalizable Tool Selection
Conclusion and References
Appendix 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 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. 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. 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. 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. 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. Edward Fredkin. Trie memory. Communications of the ACM, 3(9):490–499, 1960. 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. Tanmay Gupta and Aniruddha Kembhavi. Visual programming: Compositional visual reasoning without training. ArXiv, abs/2211.11559, 2022. 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. 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. 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. Jan-Christoph Kalo and Leandra Fichtel. Kamel : Knowledge analysis with multitoken entities in language models. Automated Knowledge Base Construction, 2022. 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. 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. 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. Gregoire Mialon, Roberto Dess ´ `ı, Maria Lomeli, Christoforos Nalmpantis, Ram Pasunuru, Roberta Raileanu, Baptiste Roziere, Timo Schick, Jane Dwivedi-Yu, Asli Celikyilmaz, et al. Augmented ` language models: a survey. arXiv preprint arXiv:2302.07842, 2023. 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. 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. 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. Aaron Parisi, Yao Zhao, and Noah Fiedel. Talm: Tool augmented language models. arXiv preprint arXiv:2205.12255, 2022. 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. 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. 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. 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. 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. Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothee´ Lacroix, Baptiste Roziere, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Ar- ` mand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models, 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. 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. This paper is available on arxiv under CC 4.0 DEED license. Authors: (1) Kexun Zhang, UC Santa Barbara and Equal contribution; (2) Hongqiao Chen, Northwood High School and Equal contribution; (3) Lei Li, Carnegie Mellon University; (4) William Yang Wang,UC Santa Barbara. Authors: Authors: (1) Kexun Zhang, UC Santa Barbara and Equal contribution; (2) Hongqiao Chen, Northwood High School and Equal contribution; (3) Lei Li, Carnegie Mellon University; (4) William Yang Wang,UC Santa Barbara. Table of Links Abstract and Intro Related Work ToolDec: LLM Tool Use via Finite-State Decoding Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Enables Generalizable Tool Selection Conclusion and References Appendix Abstract and Intro Abstract and Intro Related Work Related Work ToolDec: LLM Tool Use via Finite-State Decoding ToolDec: LLM Tool Use via Finite-State Decoding Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Enables Generalizable Tool Selection Experiment: ToolDec Enables Generalizable Tool Selection Conclusion and References Conclusion and References Appendix Appendix 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 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. 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. 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. 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. 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. Edward Fredkin. Trie memory. Communications of the ACM, 3(9):490–499, 1960. 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. Tanmay Gupta and Aniruddha Kembhavi. Visual programming: Compositional visual reasoning without training. ArXiv, abs/2211.11559, 2022. 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. 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. 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. Jan-Christoph Kalo and Leandra Fichtel. Kamel : Knowledge analysis with multitoken entities in language models. Automated Knowledge Base Construction, 2022. 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. 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. 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. Gregoire Mialon, Roberto Dess ´ `ı, Maria Lomeli, Christoforos Nalmpantis, Ram Pasunuru, Roberta Raileanu, Baptiste Roziere, Timo Schick, Jane Dwivedi-Yu, Asli Celikyilmaz, et al. Augmented ` language models: a survey. arXiv preprint arXiv:2302.07842, 2023. 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. 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. 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. Aaron Parisi, Yao Zhao, and Noah Fiedel. Talm: Tool augmented language models. arXiv preprint arXiv:2205.12255, 2022. 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. 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. 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. 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. 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. Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothee´ Lacroix, Baptiste Roziere, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Ar- ` mand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models, 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. 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. This paper is available on arxiv under CC 4.0 DEED license. This paper is available on arxiv under CC 4.0 DEED license. available on arxiv

Syntax Error-Free and Generalizable Tool Use for LLMs: Conclusion and References

এলএলএম-এর জন্য সিনট্যাক্স ত্রুটি-মুক্ত এবং সাধারণীকরণযোগ্য টুল ব্যবহার: উপসংহার এবং রেফারেন্স

Syntaxfehlerfreier und generalisierbarer Tooleinsatz für LL.M.: Fazit und Referenzen

Uso de herramientas generalizables y sin errores de sintaxis para LLM: conclusiones y referencias

Utilisation d'outils de syntaxe sans erreur et généralisables pour les LLM : conclusion et références

एलएलएम के लिए वाक्यविन्यास त्रुटि-मुक्त और सामान्यीकरण योग्य उपकरण का उपयोग: निष्कर्ष और संदर्भ

LLM における構文エラーのない一般化可能なツールの使用: 結論と参考文献

LLM을 위한 구문 오류가 없고 일반화 가능한 도구 사용: 결론 및 참조

Uso de ferramenta generalizável e livre de erros de sintaxe para LLMs: conclusão e referências

Использование без синтаксических ошибок и обобщения инструментов для программ LLM: выводы и ссылки

Yüksek Lisans'lar için Sözdizimi Hatasız ve Genelleştirilebilir Araç Kullanımı: Sonuç ve Referanslar

Sử dụng công cụ không có lỗi và có thể khái quát hóa cho LLM: Kết luận và tài liệu tham khảo

语法无错误且可推广的法学硕士工具使用：结论和参考文献

Author:
(1) Brandon T. Willard, Normal Computing;
(2) R´emi Louf, Normal Computing. Table of Links Abstract and Intro
LLM Sampling and Guided Generation
Iterative FSM Processing and Indexing
Extensions to Iterative Parsing
Discussion, References and Acknowledgments Abstract In this article we show how the problem of neural text generation can be constructively reformulated in terms of transitions between the states of a finite-state machine. This framework leads to an efficient approach to guiding text generation with regular expressions and context-free grammars by allowing the construction of an index over a language model’s vocabulary. The approach is model agnostic, allows one to enforce domain-specific knowledge and constraints, and enables the construction of reliable interfaces by guaranteeing the structure of the generated text. It adds little overhead to the token sequence generation process and significantly outperforms existing solutions. An implementation is provided in the open source Python library Outlines [Louf and Willard]. 1. Introduction We are concerned with the problem of generating sequences of tokens from a large language model (LLM) [Vaswani et al., 2017, Radford et al., 2019] that conform to regular expressions or context-free grammars (CFGs). This kind of guided LLM generation is used to make LLM model output usable under rigid formatting requirements that are either hard or costly to capture through fine-tuning alone [Beurer-Kellner et al., 2023, Scholak et al., 2021, Poesia et al., 2022a, Rabinovich et al., 2017, Weng, 2021, Dong et al., 2023, Poesia et al., 2022b, Geng et al., 2023, Wang et al., 2023]. Such features have recently been generalized in prompting libraries and interfaces [Microsoft, 2023, Beurer-Kellner et al., 2023, Rickard, 2023a,b], but their applicability can be limited by their scaling costs. Most implementations of guided generation bias the score values used to determine the probabilities of the tokens in an LLM’s vocabulary. A common and sufficient approach involves repeated evaluations over the entire vocabulary in order to determine which tokens are valid–according to the constraints and previously sampled tokens–and setting the probabilities of invalid tokens to zero. This approach entails a fixed O(N) cost for each token generated, where N is the size of the LLM’s vocabulary. We propose an approach that uses the finite state machine (FSM) formulation of regular expressions to both arbitrarily start and stop guided generation and allow the construction of an index with which the set of nonzero-probability tokens can be obtained efficiently at each step. The result is an algorithm that costs O(1) on average. For the regular expression case, our approach shares the most similarity with Kuchnik et al. [2023], which uses a transducer formulation to obtain FSMs defined over a language model’s vocabulary, and these FSMs contain much of the same information and scaling benefits as the indices described here. Our approach does not require the complete transducer abstraction and can be used to more easily extend existing, efficient regular expression libraries without modifying the underlying automatons and their implementations. More importantly, our indexing approach can also be extended to CFGs and LALR(1) parsers to allow for efficient guided generation according to popular data formats and programming languages (e.g. JSON, Python, SQL, etc.). The transition to parsing is made by way of augmentations to traditional LALR(1) parser components and operations, making it–again–an approach that can be used to extend existing parser implementations. This paper is available on arxiv under CC 4.0 license. Author: (1) Brandon T. Willard, Normal Computing; (2) R´emi Louf, Normal Computing. Author: Author: (1) Brandon T. Willard, Normal Computing; (2) R´emi Louf, Normal Computing. Table of Links Abstract and Intro LLM Sampling and Guided Generation Iterative FSM Processing and Indexing Extensions to Iterative Parsing Discussion, References and Acknowledgments Abstract and Intro Abstract and Intro LLM Sampling and Guided Generation LLM Sampling and Guided Generation Iterative FSM Processing and Indexing Iterative FSM Processing and Indexing Extensions to Iterative Parsing Extensions to Iterative Parsing Discussion, References and Acknowledgments Discussion, References and Acknowledgments Abstract In this article we show how the problem of neural text generation can be constructively reformulated in terms of transitions between the states of a finite-state machine. This framework leads to an efficient approach to guiding text generation with regular expressions and context-free grammars by allowing the construction of an index over a language model’s vocabulary. The approach is model agnostic, allows one to enforce domain-specific knowledge and constraints, and enables the construction of reliable interfaces by guaranteeing the structure of the generated text. It adds little overhead to the token sequence generation process and significantly outperforms existing solutions. An implementation is provided in the open source Python library Outlines [Louf and Willard]. 1. Introduction We are concerned with the problem of generating sequences of tokens from a large language model (LLM) [Vaswani et al., 2017, Radford et al., 2019] that conform to regular expressions or context-free grammars (CFGs). This kind of guided LLM generation is used to make LLM model output usable under rigid formatting requirements that are either hard or costly to capture through fine-tuning alone [Beurer-Kellner et al., 2023, Scholak et al., 2021, Poesia et al., 2022a, Rabinovich et al., 2017, Weng, 2021, Dong et al., 2023, Poesia et al., 2022b, Geng et al., 2023, Wang et al., 2023]. Such features have recently been generalized in prompting libraries and interfaces [Microsoft, 2023, Beurer-Kellner et al., 2023, Rickard, 2023a,b], but their applicability can be limited by their scaling costs. Most implementations of guided generation bias the score values used to determine the probabilities of the tokens in an LLM’s vocabulary. A common and sufficient approach involves repeated evaluations over the entire vocabulary in order to determine which tokens are valid–according to the constraints and previously sampled tokens–and setting the probabilities of invalid tokens to zero. This approach entails a fixed O(N) cost for each token generated, where N is the size of the LLM’s vocabulary. We propose an approach that uses the finite state machine (FSM) formulation of regular expressions to both arbitrarily start and stop guided generation and allow the construction of an index with which the set of nonzero-probability tokens can be obtained efficiently at each step. The result is an algorithm that costs O(1) on average. For the regular expression case, our approach shares the most similarity with Kuchnik et al. [2023], which uses a transducer formulation to obtain FSMs defined over a language model’s vocabulary, and these FSMs contain much of the same information and scaling benefits as the indices described here. Our approach does not require the complete transducer abstraction and can be used to more easily extend existing, efficient regular expression libraries without modifying the underlying automatons and their implementations. More importantly, our indexing approach can also be extended to CFGs and LALR(1) parsers to allow for efficient guided generation according to popular data formats and programming languages (e.g. JSON, Python, SQL, etc.). The transition to parsing is made by way of augmentations to traditional LALR(1) parser components and operations, making it–again–an approach that can be used to extend existing parser implementations. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

Efficient Guided Generation for Large Language Models: Abstract and Intro

বড় ভাষার মডেলের জন্য দক্ষ নির্দেশিত প্রজন্ম: বিমূর্ত এবং ভূমিকা

Effiziente geführte Generierung für große Sprachmodelle: Zusammenfassung und Einführung

Generación guiada eficiente para modelos de lenguaje grandes: resumen e introducción

Génération guidée efficace pour les grands modèles de langage : résumé et introduction

बड़े भाषा मॉडल के लिए कुशल निर्देशित पीढ़ी: सार और परिचय

大規模言語モデルの効率的なガイド付き生成: 概要と導入

대규모 언어 모델을 위한 효율적인 생성 안내: 초록 및 소개

Geração guiada eficiente para grandes modelos de linguagem: resumo e introdução

Эффективная управляемая генерация для больших языковых моделей: Аннотация и введение

Büyük Dil Modelleri için Verimli Kılavuzlu Oluşturma: Özet ve Giriş

Tạo hướng dẫn hiệu quả cho các mô hình ngôn ngữ lớn: Tóm tắt và giới thiệu

大型语言模型的高效引导生成：摘要和简介

Author:
(1) Brandon T. Willard, Normal Computing;
(2) R´emi Louf, Normal Computing. Table of Links Abstract and Intro
LLM Sampling and Guided Generation
Iterative FSM Processing and Indexing
Extensions to Iterative Parsing
Discussion, References and Acknowledgments 3. Iterative FSM Processing and Indexing To be precise, we consider regular expressions in 5-tuple finite automaton form [Sipser, 1996, Definition 1.5]: Definition 1 (Finite Automaton). A finite automaton, or finite-state machine, is given by (Q, Σ, δ, q0, F), where Q is a finite set of states, Σ a finite alphabet, δ : Q × Σ → Q the transition function, q0 ∈ Q the start state, and F ⊆ Q the set of accept states. The characters comprising the strings in V are drawn from Σ: i.e. V ⊂ P(Σ). Throughout, the FSM states, Q, will be represented by integer values for simplicity. Example 1. We illustrate the FSM sampling process in Figure 1 for the regular expression ([0-9]*)?\.?[0-9]*, which can be used to generate floatingpoint numbers. For simplicity, let the vocabulary, V, consist of only the strings: "A", ".", "42", ".2", and "1". When the generation begins, the FSM is in state 0, so our algorithm masks the string "A", since it would not be accepted by the FSM. We can only sample ".", "42", ".2", and "1" in this case. If we sample ".2", we advance the FSM to state 3. In this case, only "42" and "1" are valid completions, so we mask the other values before sampling. If we sample "1" instead, we advance the FSM to state 1, in which case ".", ".42", ".2", and "1" are valid completions and the mask remains unchanged. Looping through the vocabulary to determine the valid next tokens is still the biggest issue. For that, we pre-process the vocabulary using the regular expression’s FSM and build an index. The important part is that we consider starting in every viable FSM state, because the strings in the vocabulary could match arbitrary parts of a regular expression, and those parts are implicitly the FSM states. A procedure for producing matches starting at any point in the FSM is given in Algorithm 3. The result is a list of sub-sequences detailing the states through which the FSM would traverses when accepting the provided string. By matching the starting states of these sub-sequences to the last FSM state arrived at in a single step of the loop in Algorithm 2, we can efficiently index the vocabulary with a map, σ : Q → P(V), connecting FSM states and sets of elements of the vocabulary that will be accepted by the FSM in those states. Algorithm 4 describes the construction of σ. Using a hash-map for σ can make the m step in Algorithm 2 cost only O(1) on average. Furthermore, since σ is constructed outside of the token sampling procedure, its run-time cost is effectively irrelevant, although it theoretically requires memory equal to the number of states in the FSM (i.e. |Q|). Fortunately, for non-pathological combinations of regular expressions and vocabularies, not every string in the vocabulary will be accepted by the FSM, and not every FSM state will be represented by a string in V. 3.1 Examples In this section we use GPT2-medium (355M parameters) to illustrate how regular expression guided generation works in practice. We use the library Outlines to generate them: Listing 3.1 – continued Listing 3.3 – continued 3.2 Comparison with current methods To illustrate the efficiency of the indexing approach described here, and implemented in Outlines, we perform a simple comparison with the Guidance library. As of this writing, the Guidance library uses partial regular expression matching–applied from the start of the sampled sequence each time–and must iterate over the LLM’s vocabulary (N = 50, 257) on each step. The Guidance code and prompt used for this comparison are as follows: Listing 3.4 – continued The corresponding Outlines code is as follows: Listing 3.5 – continued The value of max_tokens is varied and the timings are recorded with timeit for a single loop and single repeat value (i.e. only one sample is collected for each value of max_tokens). The results are plotted in Section 3.2. Barring any configuration oversights that might be creating a large runtime discrepancy, the observed scaling in the maximum number of sampled tokens is striking and is indicative of the growing computational problem implied by the approach. This paper is available on arxiv under CC 4.0 license. Author: (1) Brandon T. Willard, Normal Computing; (2) R´emi Louf, Normal Computing. Author: Author: (1) Brandon T. Willard, Normal Computing; (2) R´emi Louf, Normal Computing. Table of Links Abstract and Intro LLM Sampling and Guided Generation Iterative FSM Processing and Indexing Extensions to Iterative Parsing Discussion, References and Acknowledgments Abstract and Intro Abstract and Intro LLM Sampling and Guided Generation LLM Sampling and Guided Generation Iterative FSM Processing and Indexing Iterative FSM Processing and Indexing Extensions to Iterative Parsing Extensions to Iterative Parsing Discussion, References and Acknowledgments Discussion, References and Acknowledgments 3. Iterative FSM Processing and Indexing To be precise, we consider regular expressions in 5-tuple finite automaton form [Sipser, 1996, Definition 1.5]: Definition 1 (Finite Automaton). A finite automaton, or finite-state machine, is given by (Q, Σ, δ, q0, F), where Q is a finite set of states, Σ a finite alphabet, δ : Q × Σ → Q the transition function, q0 ∈ Q the start state, and F ⊆ Q the set of accept states. Definition 1 A finite automaton, or finite-state machine, is given by (Q, Σ, δ, q0, F), where Q is a finite set of states, Σ a finite alphabet, δ : Q × Σ → Q the transition function, q0 ∈ Q the start state, and F ⊆ Q the set of accept states. The characters comprising the strings in V are drawn from Σ: i.e. V ⊂ P(Σ). Throughout, the FSM states, Q, will be represented by integer values for simplicity. Example 1. We illustrate the FSM sampling process in Figure 1 for the regular expression ([0-9]*)?\.?[0-9]*, which can be used to generate floatingpoint numbers. For simplicity, let the vocabulary, V, consist of only the strings: "A", ".", "42", ".2", and "1". Example 1. We illustrate the FSM sampling process in Figure 1 for the regular expression ([0-9]*)?\.?[0-9]*, which can be used to generate floatingpoint numbers. For simplicity, let the vocabulary, V, consist of only the strings: "A", ".", "42", ".2", and "1". When the generation begins, the FSM is in state 0, so our algorithm masks the string "A", since it would not be accepted by the FSM. We can only sample ".", "42", ".2", and "1" in this case. When the generation begins, the FSM is in state 0, so our algorithm masks the string "A", since it would not be accepted by the FSM. We can only sample ".", "42", ".2", and "1" in this case. If we sample ".2", we advance the FSM to state 3. In this case, only "42" and "1" are valid completions, so we mask the other values before sampling. If we sample "1" instead, we advance the FSM to state 1, in which case ".", ".42", ".2", and "1" are valid completions and the mask remains unchanged. If we sample ".2", we advance the FSM to state 3. In this case, only "42" and "1" are valid completions, so we mask the other values before sampling. If we sample "1" instead, we advance the FSM to state 1, in which case ".", ".42", ".2", and "1" are valid completions and the mask remains unchanged. Looping through the vocabulary to determine the valid next tokens is still the biggest issue. For that, we pre-process the vocabulary using the regular expression’s FSM and build an index. The important part is that we consider starting in every viable FSM state, because the strings in the vocabulary could match arbitrary parts of a regular expression, and those parts are implicitly the FSM states. A procedure for producing matches starting at any point in the FSM is given in Algorithm 3. The result is a list of sub-sequences detailing the states through which the FSM would traverses when accepting the provided string. By matching the starting states of these sub-sequences to the last FSM state arrived at in a single step of the loop in Algorithm 2, we can efficiently index the vocabulary with a map, σ : Q → P(V), connecting FSM states and sets of elements of the vocabulary that will be accepted by the FSM in those states. Algorithm 4 describes the construction of σ. Using a hash-map for σ can make the m step in Algorithm 2 cost only O(1) on average. Furthermore, since σ is constructed outside of the token sampling procedure, its run-time cost is effectively irrelevant, although it theoretically requires memory equal to the number of states in the FSM (i.e. |Q|). Fortunately, for non-pathological combinations of regular expressions and vocabularies, not every string in the vocabulary will be accepted by the FSM, and not every FSM state will be represented by a string in V. 3.1 Examples In this section we use GPT2-medium (355M parameters) to illustrate how regular expression guided generation works in practice. We use the library Outlines to generate them: Listing 3.1 – continued Listing 3.3 – continued 3.2 Comparison with current methods To illustrate the efficiency of the indexing approach described here, and implemented in Outlines, we perform a simple comparison with the Guidance library. As of this writing, the Guidance library uses partial regular expression matching–applied from the start of the sampled sequence each time–and must iterate over the LLM’s vocabulary (N = 50, 257) on each step. The Guidance code and prompt used for this comparison are as follows: Listing 3.4 – continued The corresponding Outlines code is as follows: Listing 3.5 – continued The value of max_tokens is varied and the timings are recorded with timeit for a single loop and single repeat value (i.e. only one sample is collected for each value of max_tokens). The results are plotted in Section 3.2. Barring any configuration oversights that might be creating a large runtime discrepancy, the observed scaling in the maximum number of sampled tokens is striking and is indicative of the growing computational problem implied by the approach. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

Efficient Guided Generation for Large Language Models: Iterative FSM Processing and Indexing

বৃহৎ ভাষার মডেলের জন্য দক্ষ নির্দেশিত প্রজন্ম: পুনরাবৃত্তিমূলক FSM প্রক্রিয়াকরণ এবং সূচীকরণ

Effiziente geführte Generierung für große Sprachmodelle: Iterative FSM-Verarbeitung und Indizierung

Generación guiada eficiente para modelos de lenguaje grandes: indexación y procesamiento FSM iterativo

Génération guidée efficace pour les grands modèles de langage : traitement et indexation itératifs FSM

बड़े भाषा मॉडल के लिए कुशल निर्देशित पीढ़ी: पुनरावृत्त FSM प्रसंस्करण और अनुक्रमण

大規模言語モデルの効率的なガイド付き生成: 反復的な FSM 処理とインデックス作成

대규모 언어 모델을 위한 효율적인 생성 유도: 반복적인 FSM 처리 및 인덱싱

Geração guiada eficiente para modelos de linguagem grande: processamento e indexação FSM iterativo

Эффективная управляемая генерация для больших языковых моделей: итеративная обработка и индексирование конечного автомата

Büyük Dil Modelleri için Verimli Kılavuzlu Oluşturma: Yinelemeli FSM İşleme ve Dizin Oluşturma

Tạo hướng dẫn hiệu quả cho các mô hình ngôn ngữ lớn: Lập chỉ mục và xử lý FSM lặp

大型语言模型的高效引导生成：迭代 FSM 处理和索引

This paper is under CC 4.0 license. available on arxiv Authors: (1) Zhe Liu, State Key Laboratory of Intelligent Game, Beijing, China Institute of Software Chinese Academy of Sciences, Beijing, China; University of Chinese Academy of Sciences, Beijing, China; (2) Chunyang Chen, Monash University, Melbourne, Australia; (3) Junjie Wang, State Key Laboratory of Intelligent Game, Beijing, China Institute of Software Chinese Academy of Sciences, Beijing, China; University of Chinese Academy of Sciences, Beijing, China & Corresponding author; (4) Mengzhuo Chen, State Key Laboratory of Intelligent Game, Beijing, China Institute of Software Chinese Academy of Sciences, Beijing, China; University of Chinese Academy of Sciences, Beijing, China; (5) Boyu Wu, State Key Laboratory of Intelligent Game, Beijing, China Institute of Software Chinese Academy of Sciences, Beijing, China; University of Chinese Academy of Sciences, Beijing, China; (6) Zhilin Tian, State Key Laboratory of Intelligent Game, Beijing, China Institute of Software Chinese Academy of Sciences, Beijing, China; University of Chinese Academy of Sciences, Beijing, China; (7) Yuekai Huang, State Key Laboratory of Intelligent Game, Beijing, China Institute of Software Chinese Academy of Sciences, Beijing, China; University of Chinese Academy of Sciences, Beijing, China; (8) Jun Hu, State Key Laboratory of Intelligent Game, Beijing, China Institute of Software Chinese Academy of Sciences, Beijing, China; University of Chinese Academy of Sciences, Beijing, China; (9) Qing Wang, State Key Laboratory of Intelligent Game, Beijing, China Institute of Software Chinese Academy of Sciences, Beijing, China; University of Chinese Academy of Sciences, Beijing, China & Corresponding author. Table of Links Abstract and Introduction Motivational Study and Background Approach Experiment Design Results and Analysis Discussion and Threats to Validity Related Work Conclusion and References 5 RESULTS AND ANALYSIS 5.1 Bugs Detection Performance (RQ1) Table 2 presents the bug detection performance of InputBlaster. With the unusual inputs generated by InputBlaster, the bug detection rate is 0.78 (within 30 minutes), indicating 78 (28/36) of the bugs can be detected. In addition, the bugs can be detected with an average of 13.52 attempts, and the average bug detection time is 9.64 minutes, which is acceptable. This indicates the effectiveness of our approach in generating unusual inputs for testing the app, and facilitating the uncovering of bugs related to input widgets. Figure 5 demonstrates examples of InputBlaster’s generated unusual inputs and the inputs that truly trigger the crash. We can see that our proposed approach can generate quite diversified inputs which mutate the valid input from different aspects, e.g., for the price in the first example which should be a non-negative value, the generated unusual inputs range from negative values and decimals to various kinds of character strings. Furthermore, it is good at capturing the contextual semantic information of the input widgets and their associated constraints, and generating the violations accordingly. For example, for the minimum and maximum price in the first example, it generates the unusual inputs with the minimum larger than the maximum, and successfully triggers the crash. We further analyze the bugs that could not be detected by our approach. A common feature is that they need to be triggered under specific settings, e.g., only under the user-defined setting, the input can trigger the crash, in the environment we tested, it may not have been possible to trigger a crash due to the lack of user-defined settings in advance. We have manually compared the unusual inputs generated by our approach with the ones in the issue reports. We find in all cases, InputBlaster can generate the satisfied buggy inputs within 30 attempts and 30 minutes, which further indicates its effectiveness. Table 2 also shows the performance comparison with the baselines. We can see that our proposed InputBlaster is much better than the baselines, i.e., 136% (0.78 vs. 0.33) higher in bug detection rate (within 30 minutes) compared with the best baseline Text Exerciser. This further indicates the advantages of our approach. Nevertheless, the Text Exerciser can only utilize the dynamic hints in input generation which covers a small portion of all situations, i.e., a large number of input widgets do not involve such feedback. Performance comparison with baselines. Without our elaborate design, the raw ChatGPT demonstrates poor performance, which further indicates the necessity of our approach. In addition, the string analysis methods, which are designed specifically for string constraints, would fail to work for mobile apps. In addition, since the input widgets of mobile apps are more diversified (as shown in Section 2.1.2) compared with the string, the heuristic analysis or finite-state automata techniques in the string analysis methods might be ineffective for our task. The baselines for automated GUI testing or valid text input generation are even worse, since their main focus is to increase the coverage through generating valid inputs. This further implies the value of our approach for targeting this unexplored task. 5.2 Ablation Study (RQ2) Table 3 shows the performance of InputBlaster and its 2 variants respectively removing the first and third module. In detail, for InputBlaster w/o valid Input (i.e., without Module 1), we provide the information related to the input widgets (as Table 1 P1) to the LLM in Module 2 and set other information from Module 1 as “null”. For InputBlaster w/o enrich Examples (i.e., without Module 3), we set the examples from Module 3 as “null” when querying the LLM. Note that, since Module 2 is for generating the unusual inputs which is indispensable for this task, hence we do not experiment with this variant. 5.2.1 Contribution of Modules. We can see that InputBlaster’s bug detection performance is much higher than all other variants, indicating the necessity of the designed modules and the advantage of our approach. Compared with InputBlaster, InputBlaster w/o validInput results in the largest performance decline, i.e., 50% drop (0.39 vs. 0.78) in bug detection rate within 30 minutes. This further indicates that the generated valid inputs and inferred constraints in Module 1 can help LLM understand what the correct input looks like and generate the violated ones. also undergoes a big performance decrease, i.e., 32% (0.53 vs. 0.78) in bug detection rate within 30 minutes, and the average testing time increases by 109% (9.64 vs. 20.15). This might be because without the examples, the LLM would spend more time understanding user intention and criteria for what kinds of answers are wanted. InputBlaster w/o enrichExamples Table 4 further demonstrates the performance of InputBlaster and its 5 variants. We remove each sub-module of the InputBlaster in Figure 3 separately, 5.2.2 Contribution of Sub-modules. i.e., inferred constraint, mutation rule, text execution feedback, test generator and retrieved examples of buggy input. For removing the test generator, we directly let the LLM generate the unusual inputs, and for removing retrieved examples, we use the random selection method. For other variants, we set the removed content as “null”. The experimental results demonstrate that removing any of the sub-modules would result in a noticeable performance decline, indicating the necessity and effectiveness of the designed sub modules. Removing the mutation rules (InputBlaster w/o-mutateRule) have the greatest impact on the performance, reducing the bug detection rate by 50% (0.36 vs. 0.72 within 30 attempts). Remember that, InputBlaster first lets the LLM to generate the mutation rules (how to mutate the valid inputs), then asks it to produce the test generator following the mutation rule. With the generated mutation rules serving as the reasoning chain, the unusual input generation can be more effective, which further proves the usefulness of our design. We also notice that, when removing the test generator (InputBlaster w/o-generator), the bug detection rate does not drop much (0.72 vs. 0.61) when considering 30 attempts, yet it declines a lot (0.78 vs. 0.36) when considering 30 minutes of testing time. This is because our proposed approach lets the LLM produce the test generator which can yield a batch of unusual inputs. This means interacting with the LLM once can generate multiple outcomes. However, if asking the LLM to directly generates unusual inputs (i.e., InputBlaster w/o-generator), it requires interacting with LLM frequently, and could be quite inefficient. This further demonstrates we formulate the problem as producing the test generator task is efficient and valuable. In addition, randomly selecting the examples (InputBlaster w/oretriExample) would also largely influence the performance, and decrease the bug detection rate by 22% (0.56 vs. 0.72 within 30 attempts). This indicates that by providing similar examples, the LLM can quickly think out what should the unusual inputs look like. Nevertheless, we can see that, compared with the variant without enriched examples in prompt (Table 3), the randomly selected examples do take effect (0.47 vs 0.56 in bug detection rate within 30 attempts), which further indicates the demonstration can facilitate the LLM in producing the required output. Table 5 demonstrates the performance under the different number of examples provided in the prompt. 5.2.3 Influence of Different Number of Examples. We can see that the number of detected bugs increases with more examples, reaching the highest bug detection rate with 5 examples. And after that, the performance would gradually decrease even increasing the examples. This indicates that too few or too many examples would both damage the performance, because of the tiny information or the noise in the provided examples. 5.3 Usefulness Evaluation (RQ3) Table 6 shows all bugs spotted by Ape integrated with our InputBlaster, and more detailed information on detected bugs can be seen in our website. For the 131 apps, InputBlaster detects 43 bugs in 32 apps, of which 37 are newly-detected bugs. Furthermore, these new bugs are not detected by the Ape without InputBlaster. We submit these 37 bugs to the development team, and 28 of them have been fixed/confirmed so far (21 fixed and 7 confirmed), while the remaining are still pending (none of them is rejected). This further indicates the effectiveness and usefulness of our proposed InputBlaster in bug detection. When confirming and fixing the bugs, some Android app developers express thanks such as “Very nice! You find an invalid input we thought was too insignificant to cause crashes.”(i.e., Ipsos). Furthermore, some developers also express their thought about the buggy text input “Handling different inputs can be tricky, and I admit we couldn’t test for every possible scenario. It has given me a fresh appreciation for the complexity of user inputs and the potential bugs they can introduce. ”(i.e., DRBUs). Some developers also present valuable suggestions to facilitate the further improvement of InputBlaster. For example, some of them hope that we can find the patterns of these bugs and design repair methods.

Leveraging LLMs for Generation of Unusual Text Inputs in Mobile App Tests: Results and Analysis

Stories, News & Mentions about FINITESTATE

Finitestate’s Stories on HackerNoon