Iterative is an accelerator focused exclusively on Southeast Asia. Founded by cofounders of Decide.com (acquired by eBay), Iterative differentiates itself with partners, mentors, advisors, and investors who have all previously started, sold, and operated startups. Iterative's mission is to build the strongest and most supportive network in the region for early stage founders. For more details, see http://iterative.vc.

Iterative

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 4. Extensions to Iterative Parsing In this section, we move our focus to general parser-guided generation and start with a simple walk-through for a Python-like grammar provided as a CFG. Consider a vocabulary consisting of strings like "d" and "ef" that can be combined to produce Python-like syntax according to an implicit CFG, and assume that these strings are sequentially sampled and concatenated according to a process like Algorithm 1. Furthermore, consider a terminal symbol DEF in the CFG that corresponds to the string "def" and is given by the trivial regular expression def. Also, consider a NAME symbol given by the regular expression [^\W\d]\w* (e.g. Python identifiers). We want to sequentially parse strings sampled from the aforementioned vocabulary in a way that adheres the Python syntax. For example, the following could be one such sequence: ["d", "ef", " f", "oo(", "):", " ", "pass"]. All the elements of the sequence are by definition elements of the vocabulary. Concatenating the sequence produces "def foo(): pass", which is a valid sequence of tokens defining a function. In the situation we’re considering, we will have observed all the tokens up to a certain point and know nothing about the ones after that point. For instance, at the third observation in the example sequence, we have the concatenated string "def f". If we were to lex/parse this string a traditional approach would return the symbol sequence DEF NAME, which misidentifies the "f" as a complete NAME token. As we can see from the rest of the sequence, the correct NAME token will be "foo". In general, the next valid strings that can be sampled from the vocabulary are ones that either continue expanding/advancing the NAME currently starting with "f" (as the full sequence in our example does), and/or


anything that begins with "("–i.e. an LPAR symbol with regular expression (–and proceeds to specify a valid argument signature. In the first case, the "f" can be seen as a partially matched NAME symbol in Python, and–recalling that its regular expression is [^\W\d]\w*–we can say that it matches both sub-patterns (i.e. [^\W\d] and \w*) in the regular expression. Our use of FSMs formalize the notion of sub-patterns by way of an FSM’s states. In this case, the regex for NAME can be represented by an FSM, M, with three states: 0 (i.e. the initial state q0), 1 (i.e. [^\W\d]), and 2 (i.e. \w*), where 1, 2 ∈ F. Using Algorithm 3, we would obtain the FSM state sequences (0, 1), (1, 2), (2, 2) for "f" and the FSM, M, corresponding to the NAME symbol. These FSM sequences for "f" tell us that matching can start for this vocabulary string in the states 0, 1, or 2, and it can end in states 1 or 2. According to case 1. above, parsing can be continued–for the NAME symbol–after previously ending in states 1 or 2. According to case 2., the next string could also start with or contain an LPAR, implying that M would have terminated, which it can given that 1 and 2 are final states in M at which the parsing would have stopped after reading "f". M terminating also indicates that a NAME symbol was completed, and that a transition to a state accepting LPAR was allowed by the grammar. In this illustration, the next valid vocabulary strings are at least "d", "ef", "pass", " ", "oo(", because all of those strings would expand the partially matched NAME, and the last one would also progress the parse state to one that reads an LPAR. The remaining string, "):", from the subset of the vocabulary we’ve considered would result in a sequence with invalid syntax. In relation to the FSM indexing approach, this means that Algorithm 4 would map FSM states 0, 1, and 2 to the subset "d", "ef", "pass", " ", "oo(" for the symbol NAME and its FSM, M. This illustration omits the underlying parser states that determine which grammar symbols and transitions are allowed. We use pushdown automata (PDA) as a means to extend the FSM approach and address the remaining details. 4.1 Pushdown Automata Formulation We define pushdown automata using the following 6-tuple representation [Sipser, 1996, Definition 2.13]: In order to construct an indexing approach for a PDA-driven parser, we need to use the connection between a CFG’s symbols–via a corresponding PDA’s alphabet–and the lexing and scanning steps that produce the symbols read by a PDA. More specifically, parsers are supported by lexers and scanners that identify symbols from a sequence of character inputs, as we implicitly illustrated in Section 4. Ordered lists of terminal symbols can be constructed for each parse/PDA state based on the symbol and stack transitions allowed by the map δ in each state. This means that we can construct an FSM for each parse state that is the union of each FSM corresponding to a terminal symbols read by the state. A scanning step will then identify a set of possible terminal symbols V ⊂ Σ for the characters read since the last fully identified symbol in the parsing process. For example, in the initial state q0 of a PDA for the Pythonlike CFG in Section 4, scanning and lexing the string "de" will result in V = {DEF, NAME}: i.e. DEF for any vocabulary string completing the string "def"–followed by a string not also read by the NAME FSM (e.g. "def ")– and NAME for any other strings read by its FSM (e.g. "default"). Note that steps of the scanner–and sampling steps of the LLM–will eventually reduce the set V until a single terminal symbol v ∈ V is determined. By applying Algorithm 3 to each string in V using the combined FSMs for each parse state, we can determine parser configurations that consist of the PDA states, the corresponding FSM states, and the potential terminal symbols. By analogy with the steps in Algorithm 3, we can use the pre-image of the PDA’s transition map to determine PDA stack values that will read the PDA states q ∈ Q and terminal symbol sets V of a parser configuration: The stack values provided by this map are needed in order to find paths– if any–through the PDA that allow successful, complete parses of each string in V starting from their possible parser configurations. For parser state and terminal combinations that correspond to REDUCE operations of an LALR(1) parser, these parser configurations will consist of more than just the topof-stack values in Γ; they will consist of sub-stacks corresponding to all valid prefixes for the REDUCE operations entailed by a vocabulary string. Ultimately, each parser configuration that permits a complete parse of a vocabulary string is added as an entry in the index for the PDA, and, in this case, the index will need to be a trie data structure in order to allow queries against the parser’s stack values. 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 4. Extensions to Iterative Parsing In this section, we move our focus to general parser-guided generation and start with a simple walk-through for a Python-like grammar provided as a CFG. Consider a vocabulary consisting of strings like "d" and "ef" that can be combined to produce Python-like syntax according to an implicit CFG, and assume that these strings are sequentially sampled and concatenated according to a process like Algorithm 1. Furthermore, consider a terminal symbol DEF in the CFG that corresponds to the string "def" and is given by the trivial regular expression def. Also, consider a NAME symbol given by the regular expression [^\W\d]\w* (e.g. Python identifiers). We want to sequentially parse strings sampled from the aforementioned vocabulary in a way that adheres the Python syntax. For example, the following could be one such sequence: ["d", "ef", " f", "oo(", "):", " ", "pass"]. All the elements of the sequence are by definition elements of the vocabulary. Concatenating the sequence produces "def foo(): pass", which is a valid sequence of tokens defining a function. In the situation we’re considering, we will have observed all the tokens up to a certain point and know nothing about the ones after that point. For instance, at the third observation in the example sequence, we have the concatenated string "def f". If we were to lex/parse this string a traditional approach would return the symbol sequence DEF NAME, which misidentifies the "f" as a complete NAME token. As we can see from the rest of the sequence, the correct NAME token will be "foo". In general, the next valid strings that can be sampled from the vocabulary are ones that either continue expanding/advancing the NAME currently starting with "f" (as the full sequence in our example does), and/or anything that begins with "("–i.e. an LPAR symbol with regular expression (–and proceeds to specify a valid argument signature. continue expanding/advancing the NAME currently starting with "f" (as the full sequence in our example does), and/or continue expanding/advancing the NAME currently starting with "f" (as the full sequence in our example does), and/or anything that begins with "("–i.e. an LPAR symbol with regular expression (–and proceeds to specify a valid argument signature. anything that begins with "("–i.e. an LPAR symbol with regular expression (–and proceeds to specify a valid argument signature. In the first case, the "f" can be seen as a partially matched NAME symbol in Python, and–recalling that its regular expression is [^\W\d]\w*–we can say that it matches both sub-patterns (i.e. [^\W\d] and \w*) in the regular expression. Our use of FSMs formalize the notion of sub-patterns by way of an FSM’s states. In this case, the regex for NAME can be represented by an FSM, M, with three states: 0 (i.e. the initial state q0), 1 (i.e. [^\W\d]), and 2 (i.e. \w*), where 1, 2 ∈ F. Using Algorithm 3, we would obtain the FSM state sequences (0, 1), (1, 2), (2, 2) for "f" and the FSM, M, corresponding to the NAME symbol. These FSM sequences for "f" tell us that matching can start for this vocabulary string in the states 0, 1, or 2, and it can end in states 1 or 2. According to case 1. above, parsing can be continued–for the NAME symbol–after previously ending in states 1 or 2. According to case 2., the next string could also start with or contain an LPAR, implying that M would have terminated, which it can given that 1 and 2 are final states in M at which the parsing would have stopped after reading "f". M terminating also indicates that a NAME symbol was completed, and that a transition to a state accepting LPAR was allowed by the grammar. In this illustration, the next valid vocabulary strings are at least "d", "ef", "pass", " ", "oo(", because all of those strings would expand the partially matched NAME, and the last one would also progress the parse state to one that reads an LPAR. The remaining string, "):", from the subset of the vocabulary we’ve considered would result in a sequence with invalid syntax. In relation to the FSM indexing approach, this means that Algorithm 4 would map FSM states 0, 1, and 2 to the subset "d", "ef", "pass", " ", "oo(" for the symbol NAME and its FSM, M. This illustration omits the underlying parser states that determine which grammar symbols and transitions are allowed. We use pushdown automata (PDA) as a means to extend the FSM approach and address the remaining details. 4.1 Pushdown Automata Formulation We define pushdown automata using the following 6-tuple representation [Sipser, 1996, Definition 2.13]: In order to construct an indexing approach for a PDA-driven parser, we need to use the connection between a CFG’s symbols–via a corresponding PDA’s alphabet–and the lexing and scanning steps that produce the symbols read by a PDA. More specifically, parsers are supported by lexers and scanners that identify symbols from a sequence of character inputs, as we implicitly illustrated in Section 4. Ordered lists of terminal symbols can be constructed for each parse/PDA state based on the symbol and stack transitions allowed by the map δ in each state. This means that we can construct an FSM for each parse state that is the union of each FSM corresponding to a terminal symbols read by the state. A scanning step will then identify a set of possible terminal symbols V ⊂ Σ for the characters read since the last fully identified symbol in the parsing process. For example, in the initial state q0 of a PDA for the Pythonlike CFG in Section 4, scanning and lexing the string "de" will result in V = {DEF, NAME}: i.e. DEF for any vocabulary string completing the string "def"–followed by a string not also read by the NAME FSM (e.g. "def ")– and NAME for any other strings read by its FSM (e.g. "default"). Note that steps of the scanner–and sampling steps of the LLM–will eventually reduce the set V until a single terminal symbol v ∈ V is determined. By applying Algorithm 3 to each string in V using the combined FSMs for each parse state, we can determine parser configurations that consist of the PDA states, the corresponding FSM states, and the potential terminal symbols. By analogy with the steps in Algorithm 3, we can use the pre-image of the PDA’s transition map to determine PDA stack values that will read the PDA states q ∈ Q and terminal symbol sets V of a parser configuration: The stack values provided by this map are needed in order to find paths– if any–through the PDA that allow successful, complete parses of each string in V starting from their possible parser configurations. For parser state and terminal combinations that correspond to REDUCE operations of an LALR(1) parser, these parser configurations will consist of more than just the topof-stack values in Γ; they will consist of sub-stacks corresponding to all valid prefixes for the REDUCE operations entailed by a vocabulary string. Ultimately, each parser configuration that permits a complete parse of a vocabulary string is added as an entry in the index for the PDA, and, in this case, the index will need to be a trie data structure in order to allow queries against the parser’s stack values. 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: Extensions to Iterative Parsing

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

Effiziente geführte Generierung für große Sprachmodelle: Erweiterungen zum iterativen Parsing

Generación guiada eficiente para modelos de lenguaje grandes: extensiones al análisis iterativo

Génération guidée efficace pour les grands modèles de langage : extensions à l'analyse itérative

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

大規模言語モデルの効率的なガイド付き生成: 反復解析の拡張

대규모 언어 모델을 위한 효율적인 유도 생성: 반복 구문 분석 확장

Geração guiada eficiente para grandes modelos de linguagem: extensões para análise iterativa

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

Büyük Dil Modelleri için Verimli Kılavuzlu Oluşturma: Yinelemeli Ayrıştırmanın Uzantıları

Tạo hướng dẫn hiệu quả cho các mô hình ngôn ngữ lớn: Phần mở rộng cho phân tích cú pháp lặp

大型语言模型的高效引导生成：迭代解析的扩展

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 处理和索引

Engineers, whether they’re data, software, or DevOps, often strive to build or design the perfect solution. They tend to focus predominantly on technical aspects, sometimes overlooking business outcomes. This is a common oversight. However, our main goal is to develop a product that addresses a business problem, not necessarily to create a flawless solution. Therefore, we need to continually revise our design to ensure we’re on the right track. Incremental design results in a working system at the end of implementation. On the other hand, iterative design produces a functioning system at the end of each iteration. Notable examples of iterative design are presented in the picture, created by Henrik Kniberg. Sounds good? In the realm of data engineering, consider the task of building a data pipeline. This pipeline needs to ingest data from a source, transform it, load it into a destination, and provide data access. To build the right solution, we need to address several questions: What is the source (technology, format, etc.)? How much data do we need to ingest (overall, regularly)? What is the destination (technology, format, etc.)? What are the business expectations from the pipeline (SLA, availability, latency, etc.)? The first three questions are technical, while the fourth is business-oriented. The answers to these will guide our technical decisions. Based on business priorities and level of expertise, we might hear responses such as: We need fresh data daily. Fresh data should be available during working hours. Assuming we have a relational database as a source system and a data platform (data warehouse, data lake, lakehouse, etc.) as a target, we can start designing our pipeline. Our initial solution might be a batch pipeline that runs daily and loads data into our data platform. But with past experience in data ingestion with lower latency, or if we’ve used Change Data Capture (CDC), we might suggest a pipeline that ingests data with lower latency (hourly or near real-time). However, implementing a streaming pipeline requires several tasks: Enabling CDC on the source database, which may require: Changes on the source database, involving DBAs Choosing, configuring, and installing CDC software, involving DevOp 2. Defining a target system for CDC data (file system, object storage, message broker). 3. Writing a streaming pipeline that ingests CDC data to our data platform (to a raw layer). 4. Writing a streaming pipeline that transforms data and incrementally loads it to the next layers. 5. Covering all components with monitoring, alerting, logging, etc. Depending on the company’s size and existing technologies, implementing such a solution could take several weeks to months. To avoid building a solution that might not be needed, we should build our system incrementally and iteratively. Here is a possible approach: Phase 1: Implement a batch pipeline that ingests data from the source database and loads it to our data platform (to a raw layer). Depending on the amount of data, this could be a full load or a partial load based on certain criteria. Implement a batch pipeline that reads only actual data from a raw layer and does truncate inserts to further layers. This approach saves us from dealing with updates, deletes, and merge operations, allowing faster implementation. Cover all components with monitoring, alerting, logging, etc. Phase 2: Implement incremental data processing from the raw layer to further layers, which can reduce processing time and infrastructure costs. Phase 3: Enable CDC on the source database. Define a target system for CDC data (file system, object storage, message broker). Implement a streaming pipeline that ingests CDC data into our data platform and processes it incrementally to further layers. Cover all components with monitoring, alerting, logging, etc. At each phase, we have a working system that solves a business problem, allowing the business to benefit from our implementation. We can stop at any phase or continue to implement more features as per business needs.

System Design: An Iterative and Incremental Approach

Authors: (1) Nathan Lambert, Allen Institute for AI; (2) Roberto Calandra, TU Dresden. Table of Links Abstract & Introduction Related Work Background Understanding Objective Mismatch Discussions Conclusion Acknowledgments, and References 5 Discussions The iterative deployment form of RLHF where reward models are retrained based on user data, which induces a second feedback loop, is shown in Fig. 4. Schulman (2023) discusses how this is used in ChatGPT to mitigate issues such as evasiveness, verbosity, and other unexpected, undesirable qualities. Designing in this framework introduces further complexity onto engineering objectives, but allows iterative mitigation of mismatch. This style of iterative RL deployment has been understood as exogenous feedback (Gilbert, Dean, Zick, & Lambert, 2022) and can have societal implications. Iterative deployment of RLHF There is some literature in this space, but expanding related works to the scale of use of modern LLMs will be difficult. For example, Suhr and Artzi (2022) shows theoretical results on outer-loop optimization of instruction-tuned models. The modifications made to the RL optimization of RLHF cast it as a contextual bandits problem, where an agent takes one action and the dynamics are abstracted into one trajectory-reward pairing. Work in this area has investigated the potential of integrating partial, skewed, or noisy human feedback into the optimization process (Nguyen, Daumé III, & Boyd-Graber, 2017). Contextual bandits The subarea of dueling bandits has further specified the problem that is closely aligned with RLHF, but in primarily theoretical work with much smaller models, datasets, and tasks. Yue, Broder, Kleinberg, and Joachims (2012) explains this space in work showing theoretical bounds: “In contrast to conventional approaches that require the absolute reward of the chosen strategy to be quantifiable and observable, our setting assumes only that (noisy) binary feedback about the relative reward of two chosen strategies is available. This type of relative feedback is particularly appropriate in applications where absolute rewards have no natural scale or are difficult to measure... but where pairwise comparisons are easy to make.” This, while closely related to RLHF, will require substantial experimentation to be applicable. Others have built on this into work directly learning from human preferences (Sekhari, Sridharan, Sun, & Wu, 2023) or from implicit human feedback (Maghakian et al., 2022). This paper is under CC 4.0 license. available on arxiv

The Iterative Deployment of RLHF in Language Models

In the realm of problem-solving, various techniques and strategies are employed to achieve desired outcomes. Three prominent methods are often utilized: the iterative approach, the recursive approach, and the derivative approach. Each approach has its unique characteristics, advantages, and disadvantages, making it essential to understand when and how to employ each one. In this article, we will explore these three problem-solving methods and offer insights into when to use each, highlighting which approach might be better suited for a given situation. Iterative Approach The iterative approach is a straightforward and linear method of problem-solving. It involves breaking a complex problem into smaller, more manageable sub-problems and solving them sequentially. Each sub-problem's solution is often used to build upon the next. It is widely favored for its simplicity and efficiency in solving problems. Advantages of the Iterative Approach: Simplicity: Iteration is easy to understand and implement. Efficiency: It is often faster for solving problems with well-defined sequential steps. Memory efficiency: Typically requires less memory compared to recursive methods. When to Use the Iterative Approach: Problems that can be divided into smaller, independent sub-problems. When memory usage is a concern. Iterative algorithms are useful for optimization problems and numerical computations. Recursive Approach The recursive approach is a technique that involves solving a problem by breaking it down into smaller instances of the same problem. It's a conceptually elegant method but can be more complex to implement than iteration. Recursive functions call themselves with modified inputs, which eventually lead to a base case where the recursion stops. Advantages of the Recursive Approach: Elegance: It is suitable for problems with inherently recursive structures. Clarity: Sometimes, the recursive approach can result in clearer, more intuitive code. When to Use the Recursive Approach: Problems that exhibit a recursive structure, such as tree traversal, fractals, or certain mathematical sequences. When a clear and concise solution is more critical than performance. Be cautious of stack overflow errors when using recursion on large datasets or deep levels of recursion. Derivative Approach The derivative approach is quite distinct from the iterative and recursive methods. It involves finding the rate of change of a problem or its derivative. This is a common technique in calculus, where derivatives describe the slope or rate of change of a function at a given point. The derivative approach is primarily used for solving problems involving rates of change, optimization, and predicting future behavior based on historical data. Advantages of the Derivative Approach: Precise: It provides a precise measure of how a function is changing at a given point. Widely applicable: Derivatives are fundamental in various fields, such as physics, economics, and engineering. When to Use the Derivative Approach: Problems that involve rates of change, optimization, or prediction. Complex systems where small changes can lead to significant consequences. Choosing the Right Approach Selecting the appropriate problem-solving approach depends on the specific problem at hand, its characteristics, and the context in which it needs to be solved. There is no one-size-fits-all solution. To make an informed choice, consider the following factors: Problem Structure: Determine whether the problem has a clear iterative, recursive, or derivative structure. This will often guide your choice. Performance Requirements: If speed is of the essence, an iterative approach is typically faster. For elegance and clarity, recursion might be preferred. Problem Domain: Derivative methods are well-suited for solving problems related to rates of change, while iterative and recursive methods are more general-purpose. Resources: Consider the available resources, including memory and computational power, which can influence the choice of approach. In Summary Iterative, recursive, and derivative approaches are three essential problem-solving methods, each with its own strengths and weaknesses. The choice of method should be based on the nature of the problem, performance requirements, and the specific context in which the solution is needed. Being proficient in all three approaches allows a problem solver to select the most appropriate tool for the task at hand, increasing the chances of success in tackling a wide range of challenges.

Iterative vs Recursive vs Derivative Approaches

and are two well known foundational open source instruments for building infrastructure. They are very different by nature and application scenarios but also have lots similarities and intersections. I’m going to skip philosophical aspects and show practical example of the two technologies can augment each other. Kubernetes Terraform What is Common? and span infrastructure, applications and services. Multipurpose Provide and hide complexity of underlying infrastructure. abstraction and enable hybrid cloud development. Cloud agnostic allow to focus on the end result, bypassing interim steps programming. Desired state and Development Experience Terraform Configurations vs Kubernetes Manifests At the lowest level, working with both tools assumes writing DSL manifests in / or , verifying and submiting them for execution with or cli tools. While this approach is good for ad-hock tasks or as a “quickstart”, it lacks iterative deployment, stacks lifecycle management and 3rd party automation reuse. YAML HCL JSON terraform kubectl Modules and Helm packages The above limitation is partially addressed by using and with public for terraform. For Kubernetes, it’s improved by using with numerous . However, development on this level, assumes spending lot’s of manual efford in order to get things done and enable continuous deployment. workspaces modules registry helm charts available Out of the box CI/CD That’s the most interesting part, where terraform ecosystem is missing a lot comparing to kubernetes and you need to make your hands dirty to get basic CI/CD. opensource Some examples: is critical since you need to communicate with different cloud platform APIs and you cannot keep sensitive data in the code. While enabled in Kubernetes by design via encrypted secrets, and , you spend some valuable time integrating into your CI for terraform. Managing Secretes vault integration service catalog Out of the box continuous development for dev and prod. Simply saying, terraform is missing “Day 0" tools similar to , , or even , which implement typical development flows and form a basement of you pipelines. automated workflow skaffold draft gitkube metaparticle What if we could use Kubernetes tools for Terraform? Apart from levereging the largest and biggest ecosystem, we could unify tooling and development experience for the both, hence, minimize maintenance efforts. Prototype I have created draft pack, which illustrates the above and automates terraform development using skaffold, helm and has built-in , integrations. Essentially, each Terraform change results into an upgrade of helm release and it can be easily integrated with . Packer Vault Jenkins X Jenkins X Terraform pipeline reference architecture Quickstart Prerequesites: installed draft, skaffold, helm, kubernetes Clone repository and install draft pack: git clone cd infrapackcd tests/ && make addpack https://github.com/odzhu/infrapack.git Run Packer and Terraform build and deploy against sample code using skaffold make test Under the hood, it will: Create temp dir and copy sample terraform and packer code the. Execure draft create and enreaching the code with helm charts. Build and deploy. NAME:   infrapackLAST DEPLOYED: Wed May 30 18:58:11 2018NAMESPACE: defaultSTATUS: DEPLOYED RESOURCES:==> v1/ServiceAccountNAME                 SECRETS  AGEinfrapack-infrapack  1        0s ==> v1/RoleNAME                    AGEstate-writer-infrapack  0s ==> v1/RoleBindingNAME                    AGEstate-writer-infrapack  0s ==> v1/JobNAME                  DESIRED  SUCCESSFUL  AGEinfrapack-infrapack1  1        0           0s ==> v1/Pod(related)NAME                        READY  STATUS   RESTARTS  AGEinfrapack-infrapack1-97r8t  0/1    Pending  0         0s ==> v1/SecretNAME             TYPE    DATA  AGEstate-infrapack  Opaque  1     0s ==> v1/ConfigMapNAME                DATA  AGEscripts-infrapack1  3     0s Deploy complete in 585.116428ms0 tests$ helm listNAME      REVISION UPDATED                  STATUS   CHART      NAMESPACEinfrapack 1        Wed May 30 18:58:11 2018 DEPLOYED hcl-v0.1.0 default Switch to temp dir and start skaffold. cd /tmp/sandbox/ && skaffold dev The environment is ready for sandboxing, any code change will be automatically applied and you can inspect helm release for the details!

Iterative Terraform Development with Skaffold and Kubernetes

Table of Links Abstract and 1 Introduction Abstract and 1 Introduction 2 Survey with Industry Professionals 2 Survey with Industry Professionals 3 RQ1: Real-World use cases that necessitate output constraints 3 RQ1: Real-World use cases that necessitate output constraints 4 RQ2: Benefits of Applying Constraints to LLM Outputs and 4.1 Increasing Prompt-based development Efficiency 4 RQ2: Benefits of Applying Constraints to LLM Outputs and 4.1 Increasing Prompt-based development Efficiency 4.2 Integrating with Downstream Processes and Workflows 4.2 Integrating with Downstream Processes and Workflows 4.3 Satisfying UI and Product Requirements and 4.4 Improving User Experience, Trust, and Adoption 4.3 Satisfying UI and Product Requirements and 4.4 Improving User Experience, Trust, and Adoption 5 How to Articulate output constraints to LLMS and 5.1 The case for GUI: A Quick, Reliable, and Flexible Way of Prototyping Constraints 5 How to Articulate output constraints to LLMS and 5.1 The case for GUI: A Quick, Reliable, and Flexible Way of Prototyping Constraints 5.2 The Case for NL: More Intuitive and Expressive for Complex Constraints 5.2 The Case for NL: More Intuitive and Expressive for Complex Constraints 6 The Constraint maker Tool and 6.1 Iterative Design and User Feedback 6 The Constraint maker Tool and 6.1 Iterative Design and User Feedback 7 Conclusion and References 7 Conclusion and References A. The Survey Instrument A. The Survey Instrument 5.2 The Case for NL: More Intuitive and Expressive for Complex Constraints Respondents found natural language easier for specifying complex constraints than GUIs, especially for extended background contexts or numerous choices that wouldn’t reasonably fit into a GUI. Natural language was also preferred for expressing vague, nuanced, or open-ended constraints, like “don’t include offensive words” or “respond in a cheerful manner.” At a high level, respondents emphasized that natural language provides a more natural, familiar, and expressive way to communicate (potentially multiple) complex constraints, and, “trying to figure out how to use a GUI might be more tedious.” “don’t include offensive words” “respond in a cheerful manner.” “trying to figure out how to use a GUI might be more tedious.” Additionally, some respondents noted that, despite their preference for using GUIs to define constraints from time to time, they ultimately have to use natural language prompts due to API limitations. Moreover, some wished to reference “external resources” in constraints that are not feasible to directly include in prompts (e.g., “a large database / vocabulary”). These suggest that a dedicated “output-constraints” API field for specifying constraints could be advantageous, potentially through the use of a formal language or notation. “external resources” “a large database / vocabulary” This paper is available on arxiv under CC BY-NC-SA 4.0 DEED license. This paper is available on arxiv under CC BY-NC-SA 4.0 DEED license. available on arxiv Authors:
(1) Michael Xieyang Liu, Google Research, Pittsburgh, PA, USA (lxieyang@google.com);
(2) Frederick Liu, Google Research, Seattle, Washington, USA (frederickliu@google.com);
(3) Alexander J. Fiannaca, Google Research, Seattle, Washington, USA (afiannaca@google.com);
(4) Terry Koo, Google, Indiana, USA (terrykoo@google.com);
(5) Lucas Dixon, Google Research, Paris, France (ldixon@google.com);
(6) Michael Terry, Google Research, Cambridge, Massachusetts, USA (michaelterry@google.com);
(7) Carrie J. Cai, Google Research, Mountain View, California, USA (cjcai@google.com). Authors: Authors: (1) Michael Xieyang Liu, Google Research, Pittsburgh, PA, USA (lxieyang@google.com); (2) Frederick Liu, Google Research, Seattle, Washington, USA (frederickliu@google.com); (3) Alexander J. Fiannaca, Google Research, Seattle, Washington, USA (afiannaca@google.com); (4) Terry Koo, Google, Indiana, USA (terrykoo@google.com); (5) Lucas Dixon, Google Research, Paris, France (ldixon@google.com); (6) Michael Terry, Google Research, Cambridge, Massachusetts, USA (michaelterry@google.com); (7) Carrie J. Cai, Google Research, Mountain View, California, USA (cjcai@google.com).

The Case for NL: More Intuitive and Expressive for Complex Constraints

Table of Links Abstract and 1 Introduction Abstract and 1 Introduction 2 Survey with Industry Professionals 2 Survey with Industry Professionals 3 RQ1: Real-World use cases that necessitate output constraints 3 RQ1: Real-World use cases that necessitate output constraints 4 RQ2: Benefits of Applying Constraints to LLM Outputs and 4.1 Increasing Prompt-based development Efficiency 4 RQ2: Benefits of Applying Constraints to LLM Outputs and 4.1 Increasing Prompt-based development Efficiency 4.2 Integrating with Downstream Processes and Workflows 4.2 Integrating with Downstream Processes and Workflows 4.3 Satisfying UI and Product Requirements and 4.4 Improving User Experience, Trust, and Adoption 4.3 Satisfying UI and Product Requirements and 4.4 Improving User Experience, Trust, and Adoption 5 How to Articulate output constraints to LLMS and 5.1 The case for GUI: A Quick, Reliable, and Flexible Way of Prototyping Constraints 5 How to Articulate output constraints to LLMS and 5.1 The case for GUI: A Quick, Reliable, and Flexible Way of Prototyping Constraints 5.2 The Case for NL: More Intuitive and Expressive for Complex Constraints 5.2 The Case for NL: More Intuitive and Expressive for Complex Constraints 6 The Constraint maker Tool and 6.1 Iterative Design and User Feedback 6 The Constraint maker Tool and 6.1 Iterative Design and User Feedback 7 Conclusion and References 7 Conclusion and References A. The Survey Instrument A. The Survey Instrument 5 HOW TO ARTICULATE OUTPUT CONSTRAINTS TO LLMS Fig. 1 shows distributions of respondents’ preferences towards specifying output constraints either through GUI or natural language. An overarching observation is that respondents preferred using GUI to specify low-level constraints and natural language to express high-level constraints. We discuss their detailed rationale below: GUI to specify low-level constraints natural language to express high-level constraints 5.1 The case for GUI: A Quick, Reliable, and Flexible Way of Prototyping Constraints First and foremost, respondents considered GUIs particularly effective for defining “hard requirements,” providing more reliable results, and reducing ambiguity compared to natural language instructions. For example, one argued that choosing “boolean” as the output type via a GUI felt much more likely to be “honoured” compared to “typ[ing] that I want a Yes / No response [...] in a prompt.” Another claimed that “flagging a ‘JSON’ button” provides a much better user experience than “typing ‘output as JSON’ across multiple prompts.” In addition, respondents preferred using GUI when the intended constraint is “objective” and “quantifiable”, such as “use only items x,y,z,” or “a JSON with certain fields specified.” Moreover, respondents found GUI to be more flexible for rapid prototyping and experimentation (e.g., “when I want to play around with different numbers, moving a slider around seems easier than typing”). Finally, for novice LLM users, the range of choices afforded by a GUI constraint can help clarify the model’s capabilities and limitations, “making the model seems less like a black box.” One respondent drew from their experience working with text-to-image models to underscore this point: “by seeing “Illustration” as a possible output style [among others like “Photo realistic” or “Cartoon”], I became aware of [the model’s] capabilities.” “boolean” “honoured” “typ[ing] that I want a Yes / No response [...] in a prompt.” “flagging a ‘JSON’ button” “typing ‘output as JSON’ across multiple prompts.” “objective” and “quantifiable” “use only items x,y,z,” “a JSON with certain fields specified.” “when I want to play around with different numbers, moving a slider around seems easier than typing”). “by seeing “Illustration” as a possible output style [among others like “Photo realistic” or “Cartoon”], I became aware of [the model’s] capabilities.” This paper is available on arxiv under CC BY-NC-SA 4.0 DEED license. This paper is available on arxiv under CC BY-NC-SA 4.0 DEED license. available on arxiv Authors:
(1) Michael Xieyang Liu, Google Research, Pittsburgh, PA, USA (lxieyang@google.com);
(2) Frederick Liu, Google Research, Seattle, Washington, USA (frederickliu@google.com);
(3) Alexander J. Fiannaca, Google Research, Seattle, Washington, USA (afiannaca@google.com);
(4) Terry Koo, Google, Indiana, USA (terrykoo@google.com);
(5) Lucas Dixon, Google Research, Paris, France (ldixon@google.com);
(6) Michael Terry, Google Research, Cambridge, Massachusetts, USA (michaelterry@google.com);
(7) Carrie J. Cai, Google Research, Mountain View, California, USA (cjcai@google.com). Authors: Authors: (1) Michael Xieyang Liu, Google Research, Pittsburgh, PA, USA (lxieyang@google.com); (2) Frederick Liu, Google Research, Seattle, Washington, USA (frederickliu@google.com); (3) Alexander J. Fiannaca, Google Research, Seattle, Washington, USA (afiannaca@google.com); (4) Terry Koo, Google, Indiana, USA (terrykoo@google.com); (5) Lucas Dixon, Google Research, Paris, France (ldixon@google.com); (6) Michael Terry, Google Research, Cambridge, Massachusetts, USA (michaelterry@google.com); (7) Carrie J. Cai, Google Research, Mountain View, California, USA (cjcai@google.com).

ITERATIVE

iterative.vc

51-200 employees

Since 2018

COMPANY RANKING

ITERATIVE

EVERGREEN INDEX #7021

Representing this company? Click here to claim and customize this page!

Iterative WIKI

Apply to get your Tech Company News Page live on HackerNoon.com today!

ITERATIVE

iterative.vc

51-200 employees

Since 2018

COMPANY RANKING

ITERATIVE

EVERGREEN INDEX #7021

RELATED COMPANIESRANK

STORIES ABOUT ITERATIVE

Representing this company? Click here to claim and customize this page!

Iterative WIKI

Apply to get your Tech Company News Page live on HackerNoon.com today!