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

Stories, News & Mentions about FINITESTATE

Categories

Trending Topics

Stories, News & Mentions about FINITESTATE

Finitestate’s Stories on HackerNoon

Categories

Trending Topics