Iterative

iterative

Authors:
(1) Corby Rosset, Microsoft Research and Correspondence to corbyrosset@microsoft.com;
(2) Ching-An Cheng, Microsoft Research;
(3) Arindam Mitra, Microsoft Research;
(4) Michael Santacroce, Microsoft Research;
(5) Ahmed Awadallah, Microsoft Research and Correspondence to hassanam@microsoft.com;
(6) Tengyang Xie, Microsoft Research and Correspondence to tengyangxie@microsoft.com. Table of Links Abstract and 1 Introduction 2 Preliminaries 2.1 RLHF Based on Reward Models 2.2 RLHF with General Preferences 3 Direct Nash Optimization and 3.1 Derivation of Algorithm 1 3.2 Theoretical Analysis 4 Practical Algorithm – Iterative Contrastive Self-Improvement 5 Experiments and 5.1 Experimental Setup 5.2 Results and Analysis 6 Related Work 7 Conclusion and References Appendix A Extension to Regularized Preferences B Detailed Proofs C Additional Experimental Details 6 Related Work We divide the space of related work into whether or not the techniques use SFT or contrastive losses, in offline or online update settings. Online RLHF algorithms: RLHF innovated how to align language models with human preferences (Christiano et al., 2017; Stiennon et al., 2020), but it is unstable to train and memory-intensive, requiring all three of the parameterized policy model, reward model, and advantage model to be on device for training. Reward-model Augmented SFT: Since the introduction of RLHF, several emergent techniques apply reward models in various ways, such as to filter training data or rank responses. Reward rAnked Finetuning (RAFT) (Dong et al., 2023) and RRHF (Yuan et al., 2023b) offer the conceptually simplest solution for offline preference learning, which is to sample multiple outputs from a policy, rank them with a reward model, and then finetune on the best sampled output using SFT. This resembles the iterative behavior-cloning technique DAgger (Ross et al., 2011). Offline Contrastive Preference Learning: There exist several loss functions for contrastive preference learning, first introduced in the offline setting, namely Direct Preference Optimization (Rafailov et al., 2023, DPO) and Calibrated Sequence Likelihood Estimation a.k.a. SLiC (Zhao et al., 2023). Azar et al. (2023) make it clear that point-wise reward estimates are no substitute for pair-wise preferences, and that a policy can easily overfit to deterministic preferences without proper regularization. They derive a more general objective for RLHF, IPO, to directly optimize offline preference probabilities. Statistical Rejection Sampling Optimization (RSO) generates multiple samples from an initial model, ranks them to create training pairs, and optimizes them under a unified framework encompassing DPO and SLiC (Liu et al., 2024b). Inspired by the learning-to-rank literature, Listwise preference optimization (LIPO) extends pair-wise preference learning to list-wise (Liu et al., 2024a). Preference Ranking Optimization (PRO) also learns towards list-wise preferences (Song et al., 2024). The KTO algorithm takes a different approach from DPO and does not assume that a pair of good-vs-bad outputs for the same input exist, but rather a pool of good outputs and a pool of bad outputs for any inputs exist and optimizes an “unpaired” loss (Ethayarajh et al., 2024). Iterative Reward-based Finetuning: Reinforced Self-Training (ReST) is one of the first methods to explore iterative self-improving training strategies framed as a two-stage “Grow” step that samples from the current policy, and a “Improve” step that uses a reward model to filter ever-higher quality samples that are then used to improve the policy with offline RL (Gulcehre et al., 2023). A follow-up work explores the use of AI feedback rather than reward ranking (Singh et al., 2023). On-policy Contrastive Learning: Self-Rewarding Language Models (Yuan et al., 2024) is in practice very similar to DNO. They study the benefits of batched iteratively training on preferences derived from a recent policy’s sampled outputs, but in their work, they use the policy itself as the annotator, which starts off being able to provide only weak preference signals. Self-Play Fine-Tuning (Chen et al., 2024) a.k.a SPIN and Adversarial Preference Optimization a.k.a APO (Cheng et al., 2023) are both iterative LLM training techniques that are compatible with contrastive losses, but they make a very limiting assumption that the teacher is better than the student (without regard to any annotator feedback). The Cringe Loss (Adolphs et al., 2022) is a token-level loss function that contrasts the correct next token with a hard-negative token from the vocabulary that has high logit weight but still incorrect. The Pairwise Cringe Loss (Xu et al., 2023b) applies the cringe loss to an iterative self-improving style of training. On-Policy General Preference Optimization: Wang et al. (2023) consider finding the von Neumann winner of general preferences via multi-agent RL from the theoretical perspective. Nash-MD optimizes a policy towards the Nash equilibrium of a generalized preference model using policy gradients, showing that by sampling from a mixture of policies, one can converge to the Nash equilibrium in the last iteration (Munos et al., 2023). Self-play Preference Optimization (SPO) is another online two-player mini-max game that converges to a Nash equilibrium with no-regret guarantees (Swamy et al., 2024). However, these techniques are not as data efficient as contrastive losses and are difficult to implement faithfully without cumbersome two-timescale updates (Munos et al., 2023). A concurrent improvement, IPO-MD, mitigates these difficulties by using purely on-policy IPO updates and is empirically evaluated on an article summarization task (Calandriello et al., 2024). Guo et al. (2024) also propose to eliminate rewards in online AI-feedback (OAIF) by using another LLM to annotate which of two online-sampled outputs from the current policy is preferred. However, all the above studies only consider training pairs constructed between self-play “student vs student” samples, and between student and initial πref. That is, there is no concept of a more powerful “teacher” to compare against in their training pairs. We showed in Table 2 that omitting these “student vs teacher” preferences may hinder performance. This paper is available on arxiv under CC BY 4.0 DEED license. Authors: (1) Corby Rosset, Microsoft Research and Correspondence to corbyrosset@microsoft.com; (2) Ching-An Cheng, Microsoft Research; (3) Arindam Mitra, Microsoft Research; (4) Michael Santacroce, Microsoft Research; (5) Ahmed Awadallah, Microsoft Research and Correspondence to hassanam@microsoft.com; (6) Tengyang Xie, Microsoft Research and Correspondence to tengyangxie@microsoft.com. Authors: Authors: (1) Corby Rosset, Microsoft Research and Correspondence to corbyrosset@microsoft.com; (2) Ching-An Cheng, Microsoft Research; (3) Arindam Mitra, Microsoft Research; (4) Michael Santacroce, Microsoft Research; (5) Ahmed Awadallah, Microsoft Research and Correspondence to hassanam@microsoft.com; (6) Tengyang Xie, Microsoft Research and Correspondence to tengyangxie@microsoft.com. Table of Links Abstract and 1 Introduction Abstract and 1 Introduction 2 Preliminaries 2 Preliminaries 2.1 RLHF Based on Reward Models 2.1 RLHF Based on Reward Models 2.2 RLHF with General Preferences 2.2 RLHF with General Preferences 3 Direct Nash Optimization and 3.1 Derivation of Algorithm 1 3 Direct Nash Optimization and 3.1 Derivation of Algorithm 1 3.2 Theoretical Analysis 3.2 Theoretical Analysis 4 Practical Algorithm – Iterative Contrastive Self-Improvement 4 Practical Algorithm – Iterative Contrastive Self-Improvement 5 Experiments and 5.1 Experimental Setup 5 Experiments and 5.1 Experimental Setup 5.2 Results and Analysis 5.2 Results and Analysis 6 Related Work 6 Related Work 7 Conclusion and References 7 Conclusion and References Appendix Appendix A Extension to Regularized Preferences A Extension to Regularized Preferences B Detailed Proofs B Detailed Proofs C Additional Experimental Details C Additional Experimental Details 6 Related Work We divide the space of related work into whether or not the techniques use SFT or contrastive losses, in offline or online update settings. Online RLHF algorithms: RLHF innovated how to align language models with human preferences (Christiano et al., 2017; Stiennon et al., 2020), but it is unstable to train and memory-intensive, requiring all three of the parameterized policy model, reward model, and advantage model to be on device for training. Online RLHF algorithms: Reward-model Augmented SFT: Since the introduction of RLHF, several emergent techniques apply reward models in various ways, such as to filter training data or rank responses. Reward rAnked Finetuning (RAFT) (Dong et al., 2023) and RRHF (Yuan et al., 2023b) offer the conceptually simplest solution for offline preference learning, which is to sample multiple outputs from a policy, rank them with a reward model, and then finetune on the best sampled output using SFT. This resembles the iterative behavior-cloning technique DAgger (Ross et al., 2011). Reward-model Augmented SFT: Offline Contrastive Preference Learning: There exist several loss functions for contrastive preference learning, first introduced in the offline setting, namely Direct Preference Optimization (Rafailov et al., 2023, DPO) and Calibrated Sequence Likelihood Estimation a.k.a. SLiC (Zhao et al., 2023). Azar et al. (2023) make it clear that point-wise reward estimates are no substitute for pair-wise preferences, and that a policy can easily overfit to deterministic preferences without proper regularization. They derive a more general objective for RLHF, IPO, to directly optimize offline preference probabilities. Offline Contrastive Preference Learning: Statistical Rejection Sampling Optimization (RSO) generates multiple samples from an initial model, ranks them to create training pairs, and optimizes them under a unified framework encompassing DPO and SLiC (Liu et al., 2024b). Inspired by the learning-to-rank literature, Listwise preference optimization (LIPO) extends pair-wise preference learning to list-wise (Liu et al., 2024a). Preference Ranking Optimization (PRO) also learns towards list-wise preferences (Song et al., 2024). The KTO algorithm takes a different approach from DPO and does not assume that a pair of good-vs-bad outputs for the same input exist, but rather a pool of good outputs and a pool of bad outputs for any inputs exist and optimizes an “unpaired” loss (Ethayarajh et al., 2024). Iterative Reward-based Finetuning: Reinforced Self-Training (ReST) is one of the first methods to explore iterative self-improving training strategies framed as a two-stage “Grow” step that samples from the current policy, and a “Improve” step that uses a reward model to filter ever-higher quality samples that are then used to improve the policy with offline RL (Gulcehre et al., 2023). A follow-up work explores the use of AI feedback rather than reward ranking (Singh et al., 2023). Iterative Reward-based Finetuning: On-policy Contrastive Learning: Self-Rewarding Language Models (Yuan et al., 2024) is in practice very similar to DNO. They study the benefits of batched iteratively training on preferences derived from a recent policy’s sampled outputs, but in their work, they use the policy itself as the annotator, which starts off being able to provide only weak preference signals. Self-Play Fine-Tuning (Chen et al., 2024) a.k.a SPIN and Adversarial Preference Optimization a.k.a APO (Cheng et al., 2023) are both iterative LLM training techniques that are compatible with contrastive losses, but they make a very limiting assumption that the teacher is better than the student (without regard to any annotator feedback). On-policy Contrastive Learning: The Cringe Loss (Adolphs et al., 2022) is a token-level loss function that contrasts the correct next token with a hard-negative token from the vocabulary that has high logit weight but still incorrect. The Pairwise Cringe Loss (Xu et al., 2023b) applies the cringe loss to an iterative self-improving style of training. On-Policy General Preference Optimization: Wang et al. (2023) consider finding the von Neumann winner of general preferences via multi-agent RL from the theoretical perspective. Nash-MD optimizes a policy towards the Nash equilibrium of a generalized preference model using policy gradients, showing that by sampling from a mixture of policies, one can converge to the Nash equilibrium in the last iteration (Munos et al., 2023). Self-play Preference Optimization (SPO) is another online two-player mini-max game that converges to a Nash equilibrium with no-regret guarantees (Swamy et al., 2024). However, these techniques are not as data efficient as contrastive losses and are difficult to implement faithfully without cumbersome two-timescale updates (Munos et al., 2023). A concurrent improvement, IPO-MD, mitigates these difficulties by using purely on-policy IPO updates and is empirically evaluated on an article summarization task (Calandriello et al., 2024). Guo et al. (2024) also propose to eliminate rewards in online AI-feedback (OAIF) by using another LLM to annotate which of two online-sampled outputs from the current policy is preferred. However, all the above studies only consider training pairs constructed between self-play “student vs student” samples, and between student and initial πref. That is, there is no concept of a more powerful “teacher” to compare against in their training pairs. We showed in Table 2 that omitting these “student vs teacher” preferences may hinder performance. On-Policy General Preference Optimization: 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

Exploring Cutting-Edge Approaches to Iterative LLM Fine Tuning

Table of Links Abstract and 1. Introduction Abstract and 1. Introduction 2 Data 2.1 Data Sources 2.1 Data Sources 2.2 SS and SI Categories 2.2 SS and SI Categories 3 Methods 3.1 Lexicon Creation and Expansion 3.1 Lexicon Creation and Expansion 3.2 Annotations 3.2 Annotations 3.3 System Description 3.3 System Description 4 Results 4.1 Demographics and 4.2 System Performance 4.1 Demographics and 4.2 System Performance 5 Discussion 5 Discussion 5.1 Limitations 5.1 Limitations 6 Conclusion, Reproducibility, Funding, Acknowledgments, Author Contributions, and References 6 Conclusion, Reproducibility, Funding, Acknowledgments, Author Contributions, and References SUPPLEMENTARY SUPPLEMENTARY Guidelines for Annotating Social Support and Social Isolation in Clinical Notes Guidelines for Annotating Social Support and Social Isolation in Clinical Notes Other Supervised Models Other Supervised Models 3 METHODS 3.1 Lexicon Creation and Expansion The computational approaches to any NLP tasks require annotated lexicons and gold standard data [2]. We collected lexicons for fine-grained categories of SS and SI using an iterative method that included manual chart reviews and semi-automatic methods. 3.1.1 Manual Chart Review 3.1.1 Manual Chart Review Zhu et al. [26] developed a lexicon for identifying SI from clinical notes of patients with prostate cancer in the context of recovery support. Initially, this lexicon, which included 24 terms, was selected; however, it yielded relatively fewer clinical notes at MSHS and WCM compared to the published report. A list of terms for each category was created and extensively reviewed by the study team which included clinical psychiatrists and psychologists. We manually reviewed 50 notes at each site to find SS and SI keywords to enrich the existing lexicons. 3.1.2 Semi-automatic Method 3.1.2 Semi-automatic Method The lexicons from manual chart review as above were enhanced using word embeddings. First, the manually generated lexicons were vectorized using word2vec [39] and Equation 1. 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 † https://radimrehurek.com/gensim/ Authors:
(1) Braja Gopal Patra, Weill Cornell Medicine, New York, NY, USA and co-first authors;
(2) Lauren A. Lepow, Icahn School of Medicine at Mount Sinai, New York, NY, USA and co-first authors;
(3) Praneet Kasi Reddy Jagadeesh Kumar. Weill Cornell Medicine, New York, NY, USA;
(4) Veer Vekaria, Weill Cornell Medicine, New York, NY, USA;
(5) Mohit Manoj Sharma, Weill Cornell Medicine, New York, NY, USA;
(6) Prakash Adekkanattu, Weill Cornell Medicine, New York, NY, USA;
(7) Brian Fennessy, Icahn School of Medicine at Mount Sinai, New York, NY, USA;
(8) Gavin Hynes, Icahn School of Medicine at Mount Sinai, New York, NY, USA;
(9) Isotta Landi, Icahn School of Medicine at Mount Sinai, New York, NY, USA;
(10) Jorge A. Sanchez-Ruiz, Mayo Clinic, Rochester, MN, USA;
(11) Euijung Ryu, Mayo Clinic, Rochester, MN, USA;
(12) Joanna M. Biernacka, Mayo Clinic, Rochester, MN, USA;
(13) Girish N. Nadkarni, Icahn School of Medicine at Mount Sinai, New York, NY, USA;
(14) Ardesheer Talati, Columbia University Vagelos College of Physicians and Surgeons, New York, NY, USA and New York State Psychiatric Institute, New York, NY, USA;
(15) Myrna Weissman, Columbia University Vagelos College of Physicians and Surgeons, New York, NY, USA and New York State Psychiatric Institute, New York, NY, USA;
(16) Mark Olfson, Columbia University Vagelos College of Physicians and Surgeons, New York, NY, USA, New York State Psychiatric Institute, New York, NY, USA, and Columbia University Irving Medical Center, New York, NY, USA;
(17) J. John Mann, Columbia University Irving Medical Center, New York, NY, USA;
(18) Alexander W. Charney, Icahn School of Medicine at Mount Sinai, New York, NY, USA;
(19) Jyotishman Pathak, Weill Cornell Medicine, New York, NY, USA. Authors: Authors: (1) Braja Gopal Patra, Weill Cornell Medicine, New York, NY, USA and co-first authors; (2) Lauren A. Lepow, Icahn School of Medicine at Mount Sinai, New York, NY, USA and co-first authors; (3) Praneet Kasi Reddy Jagadeesh Kumar. Weill Cornell Medicine, New York, NY, USA; (4) Veer Vekaria, Weill Cornell Medicine, New York, NY, USA; (5) Mohit Manoj Sharma, Weill Cornell Medicine, New York, NY, USA; (6) Prakash Adekkanattu, Weill Cornell Medicine, New York, NY, USA; (7) Brian Fennessy, Icahn School of Medicine at Mount Sinai, New York, NY, USA; (8) Gavin Hynes, Icahn School of Medicine at Mount Sinai, New York, NY, USA; (9) Isotta Landi, Icahn School of Medicine at Mount Sinai, New York, NY, USA; (10) Jorge A. Sanchez-Ruiz, Mayo Clinic, Rochester, MN, USA; (11) Euijung Ryu, Mayo Clinic, Rochester, MN, USA; (12) Joanna M. Biernacka, Mayo Clinic, Rochester, MN, USA; (13) Girish N. Nadkarni, Icahn School of Medicine at Mount Sinai, New York, NY, USA; (14) Ardesheer Talati, Columbia University Vagelos College of Physicians and Surgeons, New York, NY, USA and New York State Psychiatric Institute, New York, NY, USA; (15) Myrna Weissman, Columbia University Vagelos College of Physicians and Surgeons, New York, NY, USA and New York State Psychiatric Institute, New York, NY, USA; (16) Mark Olfson, Columbia University Vagelos College of Physicians and Surgeons, New York, NY, USA, New York State Psychiatric Institute, New York, NY, USA, and Columbia University Irving Medical Center, New York, NY, USA; (17) J. John Mann, Columbia University Irving Medical Center, New York, NY, USA; (18) Alexander W. Charney, Icahn School of Medicine at Mount Sinai, New York, NY, USA; (19) Jyotishman Pathak, Weill Cornell Medicine, New York, NY, USA.

How We Collected Lexicons for Fine-Grained Categories of SS and SI Using an Iterative Method

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

Authors:
(1) Corby Rosset, Microsoft Research and Correspondence to corbyrosset@microsoft.com;
(2) Ching-An Cheng, Microsoft Research;
(3) Arindam Mitra, Microsoft Research;
(4) Michael Santacroce, Microsoft Research;
(5) Ahmed Awadallah, Microsoft Research and Correspondence to hassanam@microsoft.com;
(6) Tengyang Xie, Microsoft Research and Correspondence to tengyangxie@microsoft.com. Table of Links Abstract and 1 Introduction 2 Preliminaries 2.1 RLHF Based on Reward Models 2.2 RLHF with General Preferences 3 Direct Nash Optimization and 3.1 Derivation of Algorithm 1 3.2 Theoretical Analysis 4 Practical Algorithm – Iterative Contrastive Self-Improvement 5 Experiments and 5.1 Experimental Setup 5.2 Results and Analysis 6 Related Work 7 Conclusion and References Appendix A Extension to Regularized Preferences B Detailed Proofs C Additional Experimental Details 5 Experiments Algorithm 2 is chosen for its efficiency and simplicity from an implementation standpoint (in this section, we will use DNO to denote Algorithm 2 or DNO-Prct for simplicity). Once the input dataset {xi ∈ X } is chosen, each iteration of DNO proceeds in three phrases: sampling outputs from the current policy, annotating outputs for preference pair generation, and then training the next policy with the new training pairs. Iteration 0 is defined to start by sampling from the initial SFT model to produce training data for iteration 1. 5.1 Experimental Setup Every experiment except one in this study solely uses UltraFeedback. The exception is one “scaled up” experiment with about 10x more data sourced from a mixture of datasets aggregated including Anthropic HH (Bai et al., 2022a), UltraChat (Ding et al., 2023), MetaMathQA (Yu et al., 2023), EvolInstruct (Xu et al., 2023a), UltraFeedback (Cui et al., 2023) and Orca-2 (Mitra et al., 2023). Note that we only use the input prompts for these datasets and collect a GPT-4-Turbo responses for all 600k of these input prompts. Sampling from the Policy: At the end of training, we sample 5 outputs from the resulting student policy using top p sampling with p = 0.95 and temperature 0.7. Several works have shown the benefit of sampling and comparing multiple diverse outputs from the policy (Yuan et al., 2023a; Mitra et al., 2024; Liu et al., 2024b; Dong et al., 2023; Wang et al., 2022). We implement a simple defect detection system which flags any sample that has a high amount of repeated n-grams as automatic negative. Preference Annotation: We use GPT-4-Turbo “as a judge” to label preferences among the 5 policy samples and 1 gold sample (which is also GPT-4-Turbo) as shown in Figure 3. This prompt contains a few minor modifications from the that used in (Yuan et al., 2024). It implements an additive scoring framework on a 6-point scale where a score of 6 represents the highest quality answer according to certain dimensions like “correctness”, “expert knowledge”, “conciseness” etc. By following this rubric, GPT-4 acting as an annotator represents a best-effort general preference model because it compares multiple candidate responses side-by-side in the context window, and stratifies them along meaningful dimensions of quality. Training Pair Construction: Adhering to Line 6 in Algorithm 2 implies that not all pairs are suitable for training. Firstly, we must enforce the positives to be high quality in an absolute sense, and secondly, the negatives are directionally worse by a large margin. On the 6 point annotation scale, only samples that score a 5 or 6 are allowed to be positives. From the positives that meet this criteria, if any, we then construct all pairs such that the negative is at least 2 points lower. If the positive happens to be from the student, we relax this constraint to 1 point margin since the GPT-4-Turbo teacher outputs rarely receive a score less than 5 (as shown by the average teacher score in Table 2). Additionally, we are motivated to preserve the preference behavior from previous iterations so that new policies do not inadvertently regress to past bad behavior. To enforce this, we incorporate an exponentially decaying proportion of prior iterations’ training pairs into the current iteration, i.e. we sample at most 30% of training pairs from iteration t − 1, 15% from t − 2, and so on. We do not re-inference outputs for those inputs from the most recent policy. Recall that previous iterations’ inputs are non-overlapping with the splits for other iterations. Training: To prevent overfitting, we train our batched on-policy methods for at most one epoch on newly constructed pairs. Our effective batch size is fixed to 64 for all experiments. Our learning rate, beta, and alpha are found with brief hyperparameter searches. For most experiments, the learning rate is 5E-5, beta is either 0.1 or 0.05, and alpha is 0.005. We found that at higher iterations, the learning rate needs to be lowered. In SFT (supervised fine-tuning) experiments, our learning rate is 5E-6 and we mask out loss for the inputs. We use the open-source TRL library’s implementation to run our experiments. Evaluation: Our primary goal is to train a policy that is comparable to the most powerful state-of-the-art langauge models. Hence, AlpacaEval 2.0 (Dubois et al., 2023) is an appropriate benchmark because it computes win-rate against GPT-4-Turbo in a head-to-head fashion on a dataset of 805 input prompts that is shown to correlate with human preferences (0.93 spearman correlation with Chatbot Arena). While it is known that auto-eval methods also correlate with spurious features such as length, a new version of AlpacaEval 2.0 corrects for this with a length-controlled win-rate that has an even higher spearman correlation (0.98) with Chatbot Arena [4]. We also evaluate on MT-Bench (Zheng et al., 2023) which allows the llm-as-a-judge to first explain its reasoning before providing a scalar score on 1-10 for the candidate response to a bank of 80 questions. One crucial difference between AlpacaEval 2.0 and MT Bench is that the former asks GPT-4-Turbo to predict which of two side-by-side responses humans would prefer, weighted by the logits to represent its uncertainty, whereas MT-Bench asks the model to first generate a justification and then output a score on 1-10, but it neither defines the ratings (e.g. how a 7 is different than a 5) nor accounts for uncertainty in the logits of the score. We also evaluate on the OpenLLM leaderboard (Beeching et al., 2023), which measures reasoning ability on downstream NLP tasks like coding and question answering by evaluating the accuracy of the multiple choice answer option with the highest logit. Since our training data is primarily instruction-following and not trained to output just the sole answer option, this benchmark is not the primary target of this study; nonetheless, DNO on instruction tuning tasks ought to show no regression on reasoning tasks. This paper is available on arxiv under CC BY 4.0 DEED license. [4] https://github.com/tatsu-lab/alpaca_eval Authors: (1) Corby Rosset, Microsoft Research and Correspondence to corbyrosset@microsoft.com; (2) Ching-An Cheng, Microsoft Research; (3) Arindam Mitra, Microsoft Research; (4) Michael Santacroce, Microsoft Research; (5) Ahmed Awadallah, Microsoft Research and Correspondence to hassanam@microsoft.com; (6) Tengyang Xie, Microsoft Research and Correspondence to tengyangxie@microsoft.com. Authors: Authors: (1) Corby Rosset, Microsoft Research and Correspondence to corbyrosset@microsoft.com; (2) Ching-An Cheng, Microsoft Research; (3) Arindam Mitra, Microsoft Research; (4) Michael Santacroce, Microsoft Research; (5) Ahmed Awadallah, Microsoft Research and Correspondence to hassanam@microsoft.com; (6) Tengyang Xie, Microsoft Research and Correspondence to tengyangxie@microsoft.com. Table of Links Abstract and 1 Introduction Abstract and 1 Introduction 2 Preliminaries 2 Preliminaries 2.1 RLHF Based on Reward Models 2.1 RLHF Based on Reward Models 2.2 RLHF with General Preferences 2.2 RLHF with General Preferences 3 Direct Nash Optimization and 3.1 Derivation of Algorithm 1 3 Direct Nash Optimization and 3.1 Derivation of Algorithm 1 3.2 Theoretical Analysis 3.2 Theoretical Analysis 4 Practical Algorithm – Iterative Contrastive Self-Improvement 4 Practical Algorithm – Iterative Contrastive Self-Improvement 5 Experiments and 5.1 Experimental Setup 5 Experiments and 5.1 Experimental Setup 5.2 Results and Analysis 5.2 Results and Analysis 6 Related Work 6 Related Work 7 Conclusion and References 7 Conclusion and References Appendix Appendix A Extension to Regularized Preferences A Extension to Regularized Preferences B Detailed Proofs B Detailed Proofs C Additional Experimental Details C Additional Experimental Details 5 Experiments Algorithm 2 is chosen for its efficiency and simplicity from an implementation standpoint (in this section, we will use DNO to denote Algorithm 2 or DNO-Prct for simplicity). Once the input dataset {xi ∈ X } is chosen, each iteration of DNO proceeds in three phrases: sampling outputs from the current policy, annotating outputs for preference pair generation, and then training the next policy with the new training pairs. Iteration 0 is defined to start by sampling from the initial SFT model to produce training data for iteration 1. 5.1 Experimental Setup Every experiment except one in this study solely uses UltraFeedback. The exception is one “scaled up” experiment with about 10x more data sourced from a mixture of datasets aggregated including Anthropic HH (Bai et al., 2022a), UltraChat (Ding et al., 2023), MetaMathQA (Yu et al., 2023), EvolInstruct (Xu et al., 2023a), UltraFeedback (Cui et al., 2023) and Orca-2 (Mitra et al., 2023). Note that we only use the input prompts for these datasets and collect a GPT-4-Turbo responses for all 600k of these input prompts. Sampling from the Policy: At the end of training, we sample 5 outputs from the resulting student policy using top p sampling with p = 0.95 and temperature 0.7. Several works have shown the benefit of sampling and comparing multiple diverse outputs from the policy (Yuan et al., 2023a; Mitra et al., 2024; Liu et al., 2024b; Dong et al., 2023; Wang et al., 2022). We implement a simple defect detection system which flags any sample that has a high amount of repeated n-grams as automatic negative. Sampling from the Policy: Preference Annotation: We use GPT-4-Turbo “as a judge” to label preferences among the 5 policy samples and 1 gold sample (which is also GPT-4-Turbo) as shown in Figure 3. This prompt contains a few minor modifications from the that used in (Yuan et al., 2024). It implements an additive scoring framework on a 6-point scale where a score of 6 represents the highest quality answer according to certain dimensions like “correctness”, “expert knowledge”, “conciseness” etc. By following this rubric, GPT-4 acting as an annotator represents a best-effort general preference model because it compares multiple candidate responses side-by-side in the context window, and stratifies them along meaningful dimensions of quality. Preference Annotation: Training Pair Construction: Adhering to Line 6 in Algorithm 2 implies that not all pairs are suitable for training. Firstly, we must enforce the positives to be high quality in an absolute sense, and secondly, the negatives are directionally worse by a large margin. On the 6 point annotation scale, only samples that score a 5 or 6 are allowed to be positives. From the positives that meet this criteria, if any, we then construct all pairs such that the negative is at least 2 points lower. If the positive happens to be from the student, we relax this constraint to 1 point margin since the GPT-4-Turbo teacher outputs rarely receive a score less than 5 (as shown by the average teacher score in Table 2). Training Pair Construction: Additionally, we are motivated to preserve the preference behavior from previous iterations so that new policies do not inadvertently regress to past bad behavior. To enforce this, we incorporate an exponentially decaying proportion of prior iterations’ training pairs into the current iteration, i.e. we sample at most 30% of training pairs from iteration t − 1, 15% from t − 2, and so on. We do not re-inference outputs for those inputs from the most recent policy. Recall that previous iterations’ inputs are non-overlapping with the splits for other iterations. Training : To prevent overfitting, we train our batched on-policy methods for at most one epoch on newly constructed pairs. Our effective batch size is fixed to 64 for all experiments. Our learning rate, beta, and alpha are found with brief hyperparameter searches. For most experiments, the learning rate is 5E-5, beta is either 0.1 or 0.05, and alpha is 0.005. We found that at higher iterations, the learning rate needs to be lowered. In SFT (supervised fine-tuning) experiments, our learning rate is 5E-6 and we mask out loss for the inputs. We use the open-source TRL library’s implementation to run our experiments. Training Evaluation : Our primary goal is to train a policy that is comparable to the most powerful state-of-the-art langauge models. Hence, AlpacaEval 2.0 (Dubois et al., 2023) is an appropriate benchmark because it computes win-rate against GPT-4-Turbo in a head-to-head fashion on a dataset of 805 input prompts that is shown to correlate with human preferences (0.93 spearman correlation with Chatbot Arena). While it is known that auto-eval methods also correlate with spurious features such as length, a new version of AlpacaEval 2.0 corrects for this with a length-controlled win-rate Evaluation that has an even higher spearman correlation (0.98) with Chatbot Arena [4]. We also evaluate on MT-Bench (Zheng et al., 2023) which allows the llm-as-a-judge to first explain its reasoning before providing a scalar score on 1-10 for the candidate response to a bank of 80 questions. One crucial difference between AlpacaEval 2.0 and MT Bench is that the former asks GPT-4-Turbo to predict which of two side-by-side responses humans would prefer, weighted by the logits to represent its uncertainty, whereas MT-Bench asks the model to first generate a justification and then output a score on 1-10, but it neither defines the ratings (e.g. how a 7 is different than a 5) nor accounts for uncertainty in the logits of the score. We also evaluate on the OpenLLM leaderboard (Beeching et al., 2023), which measures reasoning ability on downstream NLP tasks like coding and question answering by evaluating the accuracy of the multiple choice answer option with the highest logit. Since our training data is primarily instruction-following and not trained to output just the sole answer option, this benchmark is not the primary target of this study; nonetheless, DNO on instruction tuning tasks ought to show no regression on reasoning tasks. 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 [4] https://github.com/tatsu-lab/alpaca_eval

AI That Trains Itself? Here's How it Works

Authors:
(1) Corby Rosset, Microsoft Research and Correspondence to corbyrosset@microsoft.com;
(2) Ching-An Cheng, Microsoft Research;
(3) Arindam Mitra, Microsoft Research;
(4) Michael Santacroce, Microsoft Research;
(5) Ahmed Awadallah, Microsoft Research and Correspondence to hassanam@microsoft.com;
(6) Tengyang Xie, Microsoft Research and Correspondence to tengyangxie@microsoft.com. Table of Links Abstract and 1 Introduction 2 Preliminaries 2.1 RLHF Based on Reward Models 2.2 RLHF with General Preferences 3 Direct Nash Optimization and 3.1 Derivation of Algorithm 1 3.2 Theoretical Analysis 4 Practical Algorithm – Iterative Contrastive Self-Improvement 5 Experiments and 5.1 Experimental Setup 5.2 Results and Analysis 6 Related Work 7 Conclusion and References Appendix A Extension to Regularized Preferences B Detailed Proofs C Additional Experimental Details 4 Practical Algorithm – Iterative Contrastive Self-Improvement In this section, we shift our focus to the algorithmic design of the practically scalable version of DNO, following the principles discussed in the last section. A primary challenge encountered in the implementation of the conceptual algorithm DNO (Algorithm 1) stems from the necessity to compute the expectation with respect to the preference function P under the current policy πt. Perhaps surprisingly, as we will show, all we need is a properly implemented iterative DPO-like contrastive learning algorithm. We present our the practical implementation of DNO in Algorithm 2 (DNO-Prct), which is a batched on-policy algorithm that conducts self-improvement iteratively via contrastive learning. One key consideration in our algorithmic design is that we only need to implicitly use the reward function rt. This comes from the specifically designed on-policy sampling, data filtering, and pair construction. While these specific design choices make DNO-Prct seem similar to simply performing DPO iteratively, there are significant reasons for these design decisions, as we will discuss below. Relationship between DNO-Prct and DPO. The reader may discern that DNO-Prct (Algorithm 2)—the practical implementation of DNO—can be described as an iterative version of the DPO algorithm. Such similarity is by design, intended to harness the simplicity and effectiveness of DPO (Rafailov et al., 2023) and build on empirical advancements from recent work that applies DPO iteratively (e.g., Yuan et al., 2024; Tran et al., 2024). Our experiments point to the importance of several design choices which help accommodate the general preferences, such as rankings derived from pair-wise win rates. More interestingly, our findings point to a surprising connection—that “a meticulously designed iterative DPO algorithm” could approach the Nash equilibrium of any given general preferences. Our general algorithmic framework—DNO (Algorithm 1)—is broader and fundamentally different from iterative DPO. For example, the DNO framework could also be directly extended to the regularized preference case (as discussed in Appendix A) or equipped with other advanced sample techniques (e.g., Liu et al., 2024b, RSO) as suggested by Theorem 1 for sample efficiency. On the other hand, although the soft policy iteration (or the KL-regularized reward optimization) is used in both DNO and DPO, they arise from fundamentally different reasons. For DNO, KL-regularization originates from online learning, no-regret learning through mirror descent (Nemirovskĳ and Yudin, 1983) or followthe-regularized-leader (FTRL) (Kalai and Vempala, 2005; Cesa-Bianchi and Lugosi, 2006; Shalev-Shwartz et al., 2012; Hazan et al., 2016). For DPO and PPO, the KL-regularization is an approximation for the total variation penalty to ensure monotonic improvement of the policy (Kakade and Langford, 2002; Schulman et al., 2015). Later, this approach was simplified by Schulman et al. (2017, PPO), and recently used for post-training LLMs (Ouyang et al., 2022). This paper is available on arxiv under CC BY 4.0 DEED license. Authors: (1) Corby Rosset, Microsoft Research and Correspondence to corbyrosset@microsoft.com; (2) Ching-An Cheng, Microsoft Research; (3) Arindam Mitra, Microsoft Research; (4) Michael Santacroce, Microsoft Research; (5) Ahmed Awadallah, Microsoft Research and Correspondence to hassanam@microsoft.com; (6) Tengyang Xie, Microsoft Research and Correspondence to tengyangxie@microsoft.com. Authors: Authors: (1) Corby Rosset, Microsoft Research and Correspondence to corbyrosset@microsoft.com; (2) Ching-An Cheng, Microsoft Research; (3) Arindam Mitra, Microsoft Research; (4) Michael Santacroce, Microsoft Research; (5) Ahmed Awadallah, Microsoft Research and Correspondence to hassanam@microsoft.com; (6) Tengyang Xie, Microsoft Research and Correspondence to tengyangxie@microsoft.com. Table of Links Abstract and 1 Introduction Abstract and 1 Introduction 2 Preliminaries 2 Preliminaries 2.1 RLHF Based on Reward Models 2.1 RLHF Based on Reward Models 2.2 RLHF with General Preferences 2.2 RLHF with General Preferences 3 Direct Nash Optimization and 3.1 Derivation of Algorithm 1 3 Direct Nash Optimization and 3.1 Derivation of Algorithm 1 3.2 Theoretical Analysis 3.2 Theoretical Analysis 4 Practical Algorithm – Iterative Contrastive Self-Improvement 4 Practical Algorithm – Iterative Contrastive Self-Improvement 5 Experiments and 5.1 Experimental Setup 5 Experiments and 5.1 Experimental Setup 5.2 Results and Analysis 5.2 Results and Analysis 6 Related Work 6 Related Work 7 Conclusion and References 7 Conclusion and References Appendix Appendix A Extension to Regularized Preferences A Extension to Regularized Preferences B Detailed Proofs B Detailed Proofs C Additional Experimental Details C Additional Experimental Details 4 Practical Algorithm – Iterative Contrastive Self-Improvement In this section, we shift our focus to the algorithmic design of the practically scalable version of DNO, following the principles discussed in the last section. A primary challenge encountered in the implementation of the conceptual algorithm DNO (Algorithm 1) stems from the necessity to compute the expectation with respect to the preference function P under the current policy πt. Perhaps surprisingly, as we will show, all we need is a properly implemented iterative DPO-like contrastive learning algorithm. We present our the practical implementation of DNO in Algorithm 2 (DNO-Prct), which is a batched on-policy algorithm that conducts self-improvement iteratively via contrastive learning. One key consideration in our algorithmic design is that we only need to implicitly use the reward function rt. This comes from the specifically designed on-policy sampling, data filtering, and pair construction. While these specific design choices make DNO-Prct seem similar to simply performing DPO iteratively, there are significant reasons for these design decisions, as we will discuss below. Relationship between DNO-Prct and DPO. The reader may discern that DNO-Prct (Algorithm 2)—the practical implementation of DNO—can be described as an iterative version of the DPO algorithm. Such similarity is by design, intended to harness the simplicity and effectiveness of DPO (Rafailov et al., 2023) and build on empirical advancements from recent work that applies DPO iteratively (e.g., Yuan et al., 2024; Tran et al., 2024). Our experiments point to the importance of several design choices which help accommodate the general preferences, such as rankings derived from pair-wise win rates. More interestingly, our findings point to a surprising connection—that “a meticulously designed iterative DPO algorithm” could approach the Nash equilibrium of any given general preferences. Relationship between and “a meticulously designed iterative “a meticulously designed iterative algorithm” could approach the Nash equilibrium of any given general preferences. algorithm” could approach the Nash equilibrium of any given general preferences. Our general algorithmic framework—DNO (Algorithm 1)—is broader and fundamentally different from iterative DPO. For example, the DNO framework could also be directly extended to the regularized preference case (as discussed in Appendix A) or equipped with other advanced sample techniques (e.g., Liu et al., 2024b, RSO) as suggested by Theorem 1 for sample efficiency. On the other hand, although the soft policy iteration (or the KL-regularized reward optimization) is used in both DNO and DPO, they arise from fundamentally different reasons. For DNO, KL-regularization originates from online learning, no-regret learning through mirror descent (Nemirovskĳ and Yudin, 1983) or followthe-regularized-leader (FTRL) (Kalai and Vempala, 2005; Cesa-Bianchi and Lugosi, 2006; Shalev-Shwartz et al., 2012; Hazan et al., 2016). For DPO and PPO, the KL-regularization is an approximation for the total variation penalty to ensure monotonic improvement of the policy (Kakade and Langford, 2002; Schulman et al., 2015). Later, this approach was simplified by Schulman et al. (2017, PPO), and recently used for post-training LLMs (Ouyang et al., 2022). 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

How Contrastive Learning Helps AI Self-Improve

Hoe kontrastiewe leer help AI selfverbeter

Com l'aprenentatge contrastant ajuda a la IA a millorar-se

Πώς η αντίθετη μάθηση βοηθά την αυτοβελτίωση

Cómo el aprendizaje contrastante ayuda a la IA a mejorarse

Como o aprendizaxe contrastante axuda a AI a mellorarse

対照的な学習がAIが自らを改善するのを助ける方法

Cum învățarea contrastantă ajută AI să se îmbunătățească

Как контрастное обучение помогает ИИ самосовершенствовать

Stories, News & Mentions about ITERATIVE

Categories

Trending Topics

Stories, News & Mentions about ITERATIVE

Iterative’s Stories on HackerNoon

Categories

Trending Topics