Automata-based constraints for language model decoding

Authors: terry  koo
frederick  liu
luheng  he
google  deepmind
Venue: colmweb_org_COLM_2024_Conference
Published: 2024-03-22 15:36:37

Abstract: Language models (LMs) are often expected to generate strings in some formal language; for example, structured data, API calls, or code snippets.
Although LMs can be tuned to improve their adherence to formal syntax, this does not *guarantee* conformance, especially with smaller LMs suitable for large-scale deployment.
In addition, tuning requires significant resources, making it impractical for uncommon or task-specific formats.
To prevent downstream parsing errors we would ideally *constrain* the LM to only produce valid output, but this is severely complicated by tokenization, which is typically both ambiguous and misaligned with the formal grammar.
We solve these issues through the application of automata theory, deriving an efficient closed-form solution for the *regular languages*, a broad class of formal languages with many practical applications, including API calls or schema-guided JSON and YAML.
We also discuss pragmatic extensions for coping with the issue of high branching factor, and extend our techniques to *deterministic context-free languages*, which similarly admit an efficient closed-form solution.
Previous work on this topic (Willard and Louf, 2023) layers bespoke solutions onto automata, leading to problems with speed, correctness, and extensibility.
Instead, we reformulate the entire task in terms of automata so we can leverage well-studied and well-optimized algorithms.
Our system compiles constraints ~7,000x faster, is provably correct, and can be extended in a modular fashion.

Main paper: 
 introduction: 
 A common use case for LMs is generating output in some formal language (Liu et al., 2024) ; for example, structured data, API calls (Yao et al., 2023) , or code snippets (Li et al., 2022) . While powerful LMs often produce syntactically well-formed output, this is not guaranteed. This paper describes methods for constraining an LM to generate broad classes of formal languages. One general recipe for applying constraints to any LM is to mask the decoder logits (Deutsch et al., 2019; Zhang et al., 2019) :1. Based on the current state of the constraint, build a mask of valid next tokens. 2. Penalize the sampling logits using the mask, so only valid tokens are considered.3. Feed the selected token back to the constraint, to update its state for the next step.Tokenization is a major problem because popular LMs use data-driven sub-word tokenizers (Sennrich et al., 2016; Kudo & Richardson, 2018) whose segmentations are generally both ambiguous and misaligned with formal-language tokens. For example, consider an API call like foo(x="bar"), which is typically lexed as foo ( x = "bar" ). An LM might tokenize this as foo( x=" ba r "), merging some lexer tokens and splitting others; see Appendix A.Naively, we could force the tokenization to align with the formal syntax, but this can harm quality (Lundberg, 2023) . On the other hand, accepting a token like x=" involves recognizing a variable name, operator, and the start of a string literal in one step. Mapping a formal language constraint onto an arbitrary LM tokenizer involves a long tail of such special cases.We find elegant solutions to these issues in automata theory (Hopcroft et al., 2001; Riley et al., 2009) . Our main contributions are primarily conceptual rather than empirical: 1. Identify an as-yet unnoticed connection between detokenization and transduction. 2. Solve the tokenization issues using this connection and operations on automata.3. Define extensions that address practical problems of efficiency and convenience. Prior work (Willard & Louf, 2023) has addressed these tokenization issues, but with bespoke solutions. By developing a proper theoretical grounding, we gain advantages in speed (see Section 6.1), correctness (see Appendix B), and extensibility (see Section 3.2 and 4.3). 
finite-state constraints: 
 In this section, we provide some background and then describe our main set of contributions.A finite-state automaton A is a tuple (Σ, Q, I, F, E) where Σ is a set of input symbols, Q is a finite set of states, I ∈ Q and F ⊆ Q are initial and final states, and E ⊆ Q × Σ × Q, where Σ = Σ ∪ { }, is a set of edges (Hopcroft et al., 2001; Riley et al., 2009) . Each edge e ∈ E is a tuple (e s , e σ , e t ) of source state e s , input label e σ or if none, and target state e t . See Figure 1 .An FSA A accepts w ∈ Σ * if there exist e 1 , ..., e n ∈ E such that w = e σ 1 ••• e σ n , e s 1 = I, e t n ∈ F, and e s i = e t i-1 for i > 1; note that n > |w| iff ∃i, e σ i = . To express the functional behavior of FSAs, we overload notation and define A(w) as a predicate that is true iff A accepts w. For any FSA A, we define its language L A = {w ∈ Σ * : A(w)} as the set of strings it accepts. More generally, the regular languages can be defined as {L A : A is an FSA} (Chomsky, 1956) .Conveniently, the regular languages can also be defined by regular expressions1 , which are equivalent to FSAs (Kleene, 1951) . Common tools like UNIX grep compile regular expressions into FSAs with Σ = Unicode, which are then used as predicates on text (McNaughton & Yamada, 1960; Thompson, 1968) . See Figure 2 (left). An FSA is deterministic if ∀e ∈ E, e σ = and ∀q ∈ Q, a ∈ Σ, |{e ∈ E : e s = q ∧ e σ = a}| ≤ 1.Intuitively, outbound edges have unique inputs so executing the FSA is trivial: track the current state and traverse the edge matching the next input. Surprisingly, non-deterministic and deterministic FSAs are equivalent. In particular, given an arbitrary FSA A one can build a deterministic FSA A such that L A = L A (Rabin & Scott, 1959) . See Figure 2 .A finite-state transducer is an FSA that generates output. Formally, an FST T is a tuple (Σ, ∆, Q, I, F, E) where Σ, Q, I, and F are as defined for FSAs, ∆ is a set of output symbols, and (Mohri, 1997; 2004; Riley et al., 2009) . Each edge e ∈ E is a tuple (e s , e σ , e δ , e t ) where e s , e σ , and e t are as defined for FSAs and e δ is its output label, or if none. See Figure 3 . E ⊆ Q × Σ × ∆ × Q is a set of edgesAn FST T transduces w ∈ Σ * into v ∈ ∆ * if there exist e 1 , ..., e n ∈ E such that w = e σ 1 ••• e σ n , v = e δ 1 ••• e δ n ,e s 1 = I, e t n ∈ F, and e s i = e t i-1 for i > 1. Similar to FSAs, we write2 v = T (w) if T transduces w to v. Critically, the output of one FST can be fed as the input of another FST or FSA (Riley et al., 2009) . Given FSTs T 1 and T 2 where∆ 1 = Σ 2 , we can compose them into a new FST T = T 2 • T 1 where Σ = Σ 1 , ∆ = ∆ 2 ,and T (w) = T 2 (T 1 (w)). Similarly, given an FST T 1 and FSA A 2 where ∆ 1 = Σ 2 , we can compose them into a new FSA A = A 2 • T 1 where Σ = Σ 1 and A (w) = A 2 (T 1 (w)).Our first contribution is a reformulation of detokenization (i.e., the process of converting token sequences back into text) as an FST, using the following construction:Algorithm 1 Builds detokenizing FST T V = (Σ V , ∆ V , Q V , I V , F V , E V ) from vocabulary V Σ V ← V, ∆ V ← {v i : v ∈ V, 1 ≤ i ≤ |v|} inputs/outputs are tokens/characters of V Q V ← {q r }, I V ← q r , F V ← {q r }, E V ← {}initially, T V only has a root state q r for v ∈ V do q 0 ← q r , n ← |v| for i = 1 to n -1 do build a chain for all but the last characterQ V ← Q V ∪ {q i }, E V ← E V ∪ {(q i-1 , , v i , q i )} no input with non-final output E V ← E V ∪ {(q n-1 , v, v n , q r )}input whole token with last output, cycle to root For compactness, common prefixes of the chains can be merged to form a trie-like structure, as in Figure 4 ; see Appendix B.1 for a proof of correctness.Our next contribution is a generic method for adapting any FSA from characters to tokens. Specifically, given a token vocabulary V and an FSA A that accepts character sequences, A = A • T V accepts essentially the same language as A, but in token form. More precisely, for each token sequence w ∈ L A , the detokenization of w is in L A .Note that the converse does not hold: w ∈ L A has a counterpart in L A only if w can be segmented into tokens from V. For example, suppose A accepts any number in hexadecimal format, but the tokens in V only cover the digits 0-9. Nevertheless, to the extent that L A can be tokenized by V, strings in L A are represented in L A . Indeed, due to tokenization Note that the same text can have many tokenizations (e.g., foo vs f oo), and tokens are allowed to cross sub-expression boundaries (e.g., food merges the last repeat of /(foo)+/ with /d/). ambiguity, there may be multiple token sequences in L A that are equivalent to the same string in L A . See Figure 5 .We now present our method for constraining an LM to a regular language:Algorithm 2 Constrains LM L with vocabulary V to generate the language of regex R TV ← BUILDDETOKENIZINGFST(V) token-to-character FST, see Algorithm 1 A R ← BUILDREGEXFSA(R)character-accepting FSA (Thompson, 1968 ) A R•V ← DETERMINIZE(A R • T V ) token-accepting FSA q ← I R•V start from initial FSA state for t = 1 to T do decoding steps ← COMPUTELOGITS(L) A ← {e σ : e ∈ E R•V ∧ e s = q} allowed next tokens for i = 1 to |V| do penalize logits as in Deutsch et al. (2019) if v i ∈ A then i ← -∞ v ← SAMPLENEXTTOKEN(L, ) ê ← e s.t. e ∈ E R•V ∧ e s = q ∧ e σ = vfind the matching edge q ← êt traverse the edge Note that A R•V is a closed-form solution: it expresses R using all relevant tokens from V and can be executed independently from both. See Appendix B.2 for a proof of correctness.The required operations are indexing, slicing, and basic arithmetic, which are efficient and simple enough to execute directly on an accelerator with minimal latency overhead. One pleasing aspect of this solution is how neatly it separates concerns amongst the two halves:• T V is vocabulary-specific and, while large, can easily be pre-computed for each LM.• A R is vocabulary-agnostic, easily specified, and portable across different LMs. This clean decomposition is only possible because FST-FSA composition provides a fast, automatic, and general method for joining the two halves.For example, alternative detokenization automata (see Section 4.3) can be slotted into T V without changing the rest of the system. Similarly, alternative constraint automata (see Section 3.1) can be substituted for A R and FST composition still works.Our last contribution in this section is a set of regular expression extensions, written as specially-named capturing groups, that greatly increase the efficiency and expressiveness of the system. We describe some illustrative examples below and list others in Table 1 .One problem in our approach occurs with "wildcard" matches like /./ or /[ˆ0-9]/ that match nearly any character. After composition with T V , some states in the resulting FSA will have almost |V| outbound edges, making it expensive to use-keep in mind that |V| > 100k for commonly-used LMs (Willard & Louf, 2023, Section 3 describes a similar issue).We mitigate this issue by defining terminal labels, which are token IDs disjoint from V that map to pre-computed masks of valid tokens. For example, /(?P<PARAGRAPH TOKEN>)/ parses into a terminal edge whose mask indicates newline-free tokens. This is useful for structuringQUOTED TEXT Matches a quoted string with backslash escapes.Matches a YAML-style non-quoted string.Matches an image generated by a multi-modal LM.Matches a single text token.Matches a single text token with no newlines.Matches text tokens until a stop phrase appears.Matches any substring of a given string.Matches a delimited list of homogeneous items. DELIMITED SUBSEQUENCE OF Matches a delimited subset of a heterogeneous list.Table 1 : A sampling of available extensions. Those above the line are wildcard matchers (see Section 2.5.1), while those below are syntactic sugar (see Section 2.5.2). free text: for example, /Summary:(\n\* (?P<PARAGRAPH TOKEN>)+){3,5}/ would match the heading "Summary:" followed by three to five bullets.When penalizing logits, terminal masks are applied en masse. When updating state, if the selected token matches a terminal mask we traverse that terminal edge.Note that a normal token edge and terminal edge can both match the sampled token, leading to ambiguity about which to traverse. Similarly, two terminal edges can match the sampled token. We address this with a simple heuristic: prefer normal token edges when available, and otherwise follow a semi-arbitrary precedence ordering over terminal labels. This heuristic has worked well because terminals are generally used for wildcard matches, and in practice wildcards are typically abutted by disjoint delimiting expressions. For example, in the bulleted list constraint above, the /(?P<PARAGRAPH TOKEN>)+/ expression is bounded by a newline.Sometimes, a constraint is inefficient to define as a regular expression. For example, suppose we wish to reduce hallucination by forcing the LM to generate a substring of some reference u, such as a user utterance. Unfortunately, the regular expression for substrings of u is O(|u| 2 ), even though the corresponding FSA is O(|u|)-this can be viewed as a defect of the specification language.We therefore define the syntactic sugar /(?P<SUBSTRING OF>abc)/ to match any substring of "abc", resolving the defect by providing a O(|u|) specification syntax. Besides improving usability, these extensions mitigate the explosion in regular expression size that can occur in complex applications like JSON constraints. In some cases, growth in the regular expression reflects growth in the resulting FSA, but we have found that they diverge in some important practical use cases. 
push-down constraints: 
 This section briefly presents our second set of contributions, describing how our system is easily extended to grammar-based constraints using push-down automata. We begin with some background on PDAs and then describe our contributions.A push-down automaton can be viewed as an FSA equipped with a stack. Formally, a PDA P is a tuple (Σ, Π, S, Q, I, F, E) where Σ, Q, I, and F are as defined for FSAs, Π is a set of stack symbols, S ∈ Π is a unique initial stack symbol, and (Hopcroft et al., 2001) . Each edge e ∈ E is a tuple (e s , e σ , e ↑ , e t , e ↓ ) where e s , e σ , and e t are as defined for FSAs, and e ↑ and e ↓ are popped and pushed stack symbols. See Figure 6 .E ⊆ Q × Σ × Π * × Q × Π * is a set of edgesP accepts w ∈ Σ * if there exist e 1 , ..., e n ∈ E such that w = e σ 1 ••• e σ n , e s 1 = I, e t n ∈ F, e s i = e t i-1for i > 1, and e ↑ i and e ↓ i form a coherent sequence of stack edits. Formally, let s i be the stack before e i wheres 1 = S, n i = |s i |, m i = n i -|e ↑ i |, and s i+1 = s i 1:m i e ↓ i , then e ↑ i = s i m i +1:n i must Rules S -> /ab/ S -> /a/ S /b/ 3 0 1 a [• a (S → /a/ S • /b/ 2 b •] b S → /a/ S • /b/)Figure 6 : A grammar for the canonical context-free language a n b n (left), and an equivalent PDA (right). Edge labels have e σ on top, then e ↑ marked with ) and e ↓ marked with (. The stack symbols are Earley-style dotted rules (Earley, 1970) denoting "return addresses" (Allauzen & Riley, 2012, Section 4.5) . The initial stack symbol S is written as a dot marked with square brackets Figure 7 : A simple vocabulary of tokens (left), the detokenizing FST built from it (center), and its composition with the PDA from Figure 6 (right). Note that edges are allowed to cross the boundaries of terminals and non-terminals, allowing them to push or pop multiple stack symbols. For legibility, the stack symbols have been simplified into single brackets that are interleaved with the characters of the token.hold. In other words, at each step e ↑ i must match the suffix of s i , and we update the stack by popping e ↑ i off and pushing e ↓ i on. As above, we write P (w) to indicate that P accepts w. Unlike FSAs, non-deterministic and deterministic PDAs are not equivalent: the former accept the context-free languages, which are also defined by context-free grammars (Chomsky, 1956; Hopcroft et al., 2001) , while the latter accept a strict subset, the deterministic contextfree languages (Ginsburg & Greibach, 1966) . This subset nevertheless includes all regular languages and the LL(k) and LR(k) languages (Knuth, 1965) , covering the syntax of most programming languages. As a result of this non-equivalence, there is no general algorithm to determinize an arbitrary PDA, as we had for FSAs. Instead, as LL(k) and LR(k) parsers do, our system detects non-deterministic grammars and signals an error, leaving it to the author of the grammar to rewrite the grammar in a deterministic manner.Although PDAs are more expressive than FSAs, they behave similarly in many ways and, crucically, FSTs and PDAs are composable (Allauzen & Riley, 2012) . Formally, given an FST T 1 and PDA P 2 where ∆ 1 = Σ 2 , we can compose them into a new PDA P = P 2 • T 1 where Σ = Σ 1 and P (w) = P 2 (T 1 (w)). As with FSAs, composition with the detokenizing FST T V adapts a character-based PDA into one that accepts tokens in V. See Figure 7 . This allows us to reuse Algorithm 2 with minimal modification (see Appendix B.3 for proof):Algorithm 3 Constrains LM L with vocabulary V to generate the language of grammar G T V ← BUILDDETOKENIZINGFST(V) token-to-character FST, see Algorithm 1 P G ← BUILDGRAMMARPDA(G) character-accepting PDA (Allauzen & Riley, 2012) P G•V ← P G • T V token-accepting PDA q ← I G•V , s ←start from initial PDA state and empty stack for t = 1 to T do decoding steps ← COMPUTELOGITS(L) A ← {e σ : e ∈ E G•V ∧ e s = q ∧ s ends with e ↑ } allowed next tokens for i = 1 to |V| do penalize logits as in Deutsch et al. (2019) if v i ∈ A then i ← -∞ v ← SAMPLENEXTTOKEN(L, ) ê ← e s.t. e ∈ E G•V ∧ e s = q ∧ s ends with e ↑ ∧ e σ = v find the matching edge q ← êt , m ← |s| -| ê↑ |, s ← s 1: m ê↓traverse the edge (Willard & Louf, 2023) . Blue boxes are unique to this paper, yellow ovals are unique to Outlines, and green rounded boxes are common to both. Note that composition is many times faster than indexing (see Section 6.1).It's worth re-emphasizing the benefits of formulating detokenization as an FST. By representing the entire task in terms of automata, our approach easily generalizes from regular expressions to grammars while preserving many desirable features. For example, just as FST-FSA composition enables tokens to cross sub-expression boundaries in the regular expression (see Figure 5 ), FST-PDA composition enables tokens to cross (non-)terminal boundaries in the grammar (see Figure 7 ). 
related work: 
 There is a great deal of work related to the use of automata to constrain learned models.Automata have been used to constrain learned sequence models for some time. Below, we mention a few representative examples from the literature.Sproat & Jaitly (2017) and Zhang et al. (2019) , among others in this line of work, examine text normalization for TTS applications. Certain phrases are difficult to verbalize (e.g., "4/5" to "four fifths" or "April fifth" or "four out of five [stars]"), and neural models are prone to hallucinations (e.g., "60" to "six"). The authors build FSTs that translate from written forms to possible verbalizations, and use those to guide the deep model similarly to this work. Our approach allows a wider range of constraints, supporting any regular or deterministic context-free language, and also addresses the token-mismatch issues endemic to current LM tokenizers (see Appendix A). Deutsch et al. (2019) use (intersections of) FSAs and PDAs to constrain the output of a sequential model to some formal language. This work predates the rise of general-purpose LMs, and thus does not address the problems created by mismatches between the LM's tokenization and the targeted formal language. Both Outlines (Willard & Louf, 2023) and this work address those mismatches, but by different means.The most relevant work is Outlines (Willard & Louf, 2023), which is based on a bespoke "indexing" operation that builds a token-based overlay on an FSA or PDA. Unfortunately, when applied to PDAs their algorithm is over-constrained w.r.t. tokenization3 (see Appendix A.1), whereas our approach naturally generalizes to PDAs while preserving tokenization freedom (see Section 3.2). Our approach also easily generalizes to different tokenization schemes (see Section 4.3), which does not seem possible for Outlines and likely requires a rewrite of their indexing algorithm. Finally, their approach is ~7,000x slower to compile than ours (see Section 6.1), so it is only practical when the constraint can be pre-compiled. Our core innovation allows us to recast the entire process in automata-theoretic terms, making our solution extensible (via decomposition into FST and FSA/PDA modules), correct (via basic properties of FSTs), and fast (via access to highly-optimized algorithms). For clarity, Figure 8 illustrates which parts of our system are similar to or different from Outlines.Building on Outlines, Yin et al. (2024) extended the package with the ability to "compress" runs of text into prefills. This technique is of significant practical interest and could be adapted to our approach as our techniques appear to be largely orthogonal.SynCode (Ugare et al., 2024 ) is a more recent system that also exploits FSAs, but handles grammars using LALR(1) and LR(1) parsers rather than PDAs. Like Outlines, their approach relies on a bespoke algorithm; in this case, they speculatively unroll future lexer tokens to allow LM tokens to cross multiple lexer tokens. This introduces significant complexity relative to our purely automata-theoretic approach, and deciding how many lexer tokens to unroll is a trade-off between computational cost and completeness. Some less closely-related approaches still constrain by masking logits, but dynamically match the vocabulary on each step instead of devising a method to statically pre-compute these matches, as we and the systems above do. For example, Synchromesh (Poesia et al., 2022) iterates the entire LM vocabulary on every decoding step, making it impractical with current LMs. Guidance (Microsoft, 2023) improves upon this with a cached trie, and grammar-constrained decoding (Geng et al., 2023) adds expressive power beyond contextfree. While these latter two are more flexible than our approach, they are less efficient and harder to deploy at scale. Finally, some other approaches no longer predictively mask logits, but instead sample unconstrained continuations and reject invalid ones post-hoc. For example, PICARD (Scholak et al., 2021) converts the top-k tokens to text and performs various levels of validation. Lew et al. (2023) do sequential Monte-Carlo sampling that, in the case of hard constraints, reduces to something like rejection sampling with rescoring. These approaches are quite flexible, but may have issues when the constraints require the LM to select a low-probability token. In addition, note that post-hoc filtering is orthogonal to predictive masking, so our approaches could be merged.Concurrently with review, Berglund et al. (2024) presented a finite-state machine that only accepts "correct" BPE tokenizations. Unlike the simple detokenizing FST presented in Section 2.3, their FSA is unambiguous: for any character sequence w, it only accepts the correct BPE tokenization of w. As they mention in their conclusion, their construction can be straightforwardly generalized into an FST.From there, we could compose their FST with any regex-derived FSA or grammar-derived PDA, yielding an automaton that accepts only correct BPE tokenizations that also obey the constraint. In essence, any tokenization policy that can be expressed in finite-state form can be dropped into our approach, demonstrating its modularity and generality. 
applications: 
 The clean design and efficiency of our approach enable a number of different applications. We present several illustrative examples here.JSON (Pezoa et al., 2016 ) is a widely-used structured data format that LMs are often expected to generate. We study the problem of generating JSON that conforms to a schema, which is a mapping from field name to type. Field types range from simple primitives like booleans, numbers, and strings, to sub-objects based on sub-schemas, and arrays or unions of other types. Field values can be nullable, meaning that they can be substituted with null, and fields can be marked optional, meaning that both the field name and value may be omitted.Although the set of all JSON expressions of any kind is a context-free language, somewhat surprisingly the set of JSON expressions conforming to a particular schema is a regular language, as the schema limits recursion. It is difficult to manually write the regular expression corresponding to a particular schema: while leaf-level matchers like /(true|false)/ are simple enough, complexity grows quickly as they are composed into objects, arrays, and unions. For user convenience, we have implemented tools that automatically translate schemas into regular expressions.We have also explored schema-free JSON, which as mentioned above is context-free. A simple approach is to impose constant limits k O and k A on object and array nesting, which reduces from context-free to regular, and we have implemented tools to generate regular expressions for this form of depth-truncated JSON. Naturally, one can also directly convert the JSON grammar into a PDA-based constraint.Another case study is constraining LMs to output Python dataclasses (Van Rossum & Drake, 2009) . Like the JSON schemas described above, a Python dataclass defines a mapping from field names to types, and we have implemented similar tooling that reflects on a dataclass to automatically build a regular expression matching constructor calls. This enables a particularly convenient API where one can use a dataclass type T to build a constraint, and then parse the constrained LM response back into an instance of T.Speculative decoding (Leviathan et al., 2023 ) is a method for speeding up LM inference via speculative execution. Short runs of tokens are sampled from a faster approximation model, and then verified with a more accurate target model that accepts some prefix of the sampled tokens. Although the system now runs two LMs instead of one, significant latency reductions can still be achieved due to batching and parallelization of the target model. The speedup is largely determined by the acceptance rate, which is the proportion of speculatively-sampled tokens that pass verification.The approximation model is typically a smaller LM that has disproportionately greater difficulties following formal syntax, so a natural application is to constrain the approximation model and increase its acceptance rate on formal language outputs. There are several complications to address. For one, the constraint must be "rewindable" because the target model can reject some of the speculated tokens, forcing the approximation model to restart at an earlier point. This can be accomplished by tracking a full history of states instead of just one. In addition, the logits of the target model must also be penalized, or the divergence between the two will reduce the acceptance rate and may even allow the target model to resample invalid tokens. To avoid re-evaluating the constraints, we devised a method for sharing the penalties with the target model. 
experiments: 
 Here we provide an empirical evaluation of the speed and correctness of our approach.We measured our system and Outlines (Willard & Louf, 2023) on the following tasks:1. Constraint compilation: Time to convert a regular expression into an automaton that can consume decoder tokens. See Appendix C.2 for details. 2. Per-step overhead: Time to apply constraints on each decoding step. See Appendix C.3 for details.We used Gemma (Team et al., 2024) , executed both systems on the same workstation, and averaged over 10 runs to reduce noise. Both systems were timed on several regexes reflecting different usage regimes and applications. Since runtime can vary based on platform, instead of giving precise latencies we report scaling factors relative to Outlines; see Table 2 .Gemma-2B 0.09 1.0 Gemma-7B 0.65 1.0Table 3 : Proportion of responses that conform to the required output schema, for Gemma models of different sizes, with and without constraints.To help ground the comparison, here are some rough latency ranges. For constraint compilation, Outlines takes 10s of seconds on JSON and a few seconds elsewhere, while our system takes a few milliseconds on JSON and 100s of microseconds elsewhere. For per-step overhead, Outlines takes 10s of microseconds and our system takes a few microseconds.While our system has less per-step overhead, in practice both systems have negligible latency so the speedup is not very impactful. The compilation speedup, on the other hand, is a qualitative difference that lowers the barriers to entry for applying constraints and enables new usage patterns-for example, pre-compilation is no longer required.The primary reason for the large compilation speedup is that we use OpenFST's highlyoptimized4 implementations of FST operations (Riley et al., 2009) . Critically, this is only possible because we reformulated the whole problem in terms of automata. As an analogy, imagine two programs for some scientific computing task. The first is entirely written by hand, while the second reduces the problem to linear algebra and uses NumPy (Harris et al., 2020) . The latter is likely to be much faster, due to the sheer volume of effort that has gone into optimizing NumPy.We exercise output formatting correctness with Gemma on GPQA (Rein et al., 2023) ; see Table 3 for results and Appendix D for additional details. The Gemma models have issues following the schema without constraints, but achieve perfect conformance with constraints. 
conclusion and future work: 
 In this paper, we described a system for constraining LM decoding. Our key contribution is a reformulation of detokenization as an FST, which enables our other contributions by bringing the entire task of constrained decoding into the domain of automata. Although the problems raised by ambiguous and misaligned tokenizations are quite thorny, we derive simple, elegant, and highly-performant solutions by leveraging the considerable toolkit of automata theory.In future work, we would like to explore PDAs more deeply, as thus far we have focused on FSAs because they appeared to be the more robust and scalable option. One particular issue is that the grammar must be written carefully to avoid yielding a non-deterministic PDA. This is a well-studied problem, and there are similar limitations regarding grammar specification in parsers for determinstic context-free languages: as a simple example, an LL(k) parser cannot parse a left-recursive grammar. There is a deep literature characterizing deterministic grammars and PDAs that seems like it would have many useful insights for avoiding unnecessary non-determinism (Greibach, 1965; Koch & Blum, 1997; Harrison & Havel, 1973; Havel & Harrison, 1974; Geller et al., 1976, among others) .Other avenues of exploration for PDAs include use cases and efficiency of representation.When decoding from an LM, one generally specifies a finite maximum budget of decoded tokens, and that limit shrinks the gap between context-free and regular languages. For example, if we decode at most 100 characters then the language a n b n is no longer contextfree, since we can bound n ≤ 50. It may be interesting to investigate longer-running, possibly multi-phase constraint use cases where PDAs can provide more benefit. On the other hand, even for shorter outputs where FSAs are competitive, PDAs might still provide value because they are generally more compact than equivalent FSAs. 4 (left), and the equivalent compact trie-like FST copied from Figure 4 for convenient reference (right). Note, for example, that there are three " :f" edges on the left, which are merged into a single edge on the right.S → FUNCTION "(" NUMBER ")" FUNCTION → "foo" | "bar" NUMBER → "123" | "456"This grammar follows typical practice and defines separate terminals for brackets like (, identifiers like foo, and literals like 123. If LM tokens are not allowed to cross between terminals, then tokens like r(4 will be forbidden. This can lead to a ranking inversion as described above, where the best LM output changes depending on whether tokenization is free or restricted. 
 
 Appendix: Here we prove the correctness of our approach.In this section we prove that, given a vocabulary V, Algorithm 1 constructs an FST that transduces any token sequence into its detokenization. Recall that there are two versions of the detokenizing FST: the "original" structure as constructed by Algorithm 1, and the "compact" structure where equivalent initial edges of each cycle have been merged. See Figure 9 for examples of both.We first prove correctness for the original detokenizing FST, and then briefly extend to the compact detokenizing FST.Formally, let V be a set of opaque tokens, where each token v ∈ V can be detokenized into a unique character sequence d(v) ∈ Σ * . Let W = {d(v) : v ∈ V} be the set of detokenizations of each token. The detokenization of a token sequence x ∈ V * is the concatenation of the detokenizations of each token:D(x) = d(x 1 )d(x 2 )••• d(x n ),where n = |x|. Let T V be the FST as originally constructed from V by Algorithm 1. Recall that the notation T V (x) denotes the output sequence generated by that FST for the input x-our goal is to prove T V (•) ≡ D(•).We now review the structure of T V ; see Figure 9 (left) for a visual example. First, note that T V has exactly one initial and final state, which are the same "root" state q r . For each v ∈ V, Algorithm 1 adds exactly one cycle that starts and ends at q r and generates the characters of d(v) as outputs, in order. The last edge of each cycle consumes input v, while the other edges consume nothing (i.e., input ). There are no edges outside of those |V| cycles.Before proving the main theorem, we first prove some supporting results. First, we define the possible paths one may traverse through T V .Lemma 1. Every valid transduction by T V starts and ends at q r , and traverses zero or more of the |V| cycles, in any order.Proof. By definition of I V and F V , every transduction must start and end at q r . A trivial transduction stops immediately at q r , traversing no edges or cycles. Any traversal that leaves q r must enter one of the |V| cycles and cannot stop until it returns to q r by completing the cycle-an arbitrary number of cycles may be traversed in this manner. Finally, since all cycles are start and end at q r , there are no ordering dependencies: any cycle may be traversed after any other cycle. Therefore, a transduction by T V must traverse any number of cycles in any order.From this we derive several related corollaries, which we prove en masse.Corollary 1. The domain of T V (•) is V * . Corollary 2. The codomain of T V (•) is W * . Corollary 3. For any x ∈ V * , T V (x) is D(x).Proof. Each result is immediate from Lemma 1 and the fact that each of the |V| cycles in T V uniquely consumes exactly one input token v and outputs exactly the characters of d(v).These combine to prove the main theorem.Theorem 1. For any vocabulary V, T V (•) ≡ D(•).Proof. First, observe that D(•) : V * → W * has the same domain and codomain as T V (•). Two functions are equivalent if they have the same domain (Corollary 1), codomain (Corollary 2), and map the same inputs to the same outputs (Corollary 3).We briefly extend the proof above to the compact detokenizing FST shown in Figure 4 and Figure 9 (right). This FST is constructed from the original detokenizing FST by recursively merging equivalent initial edges of each cycle, resulting in a structure similar to a prefix trie.First, note that the last edge in each of the |V| original cycles is never merged, because each final edge consumes a unique input token. The compact detokenizing FST can thus be partitioned into two halves: a prefix trie over the first |v| -1 characters of every token, and |V| edges cycling back from the leaves of the trie to q r .It follows that there are still exactly |V| cycles in the compact FST, where each cycle consists of a path from q r to a leaf of the prefix trie followed by one of the |V| edges back to q r . Stated another way, all of the |V| original cycles still exist, but instead of being disjoint they now share some edges. Therefore, Lemma 1 still holds and the rest of the proof follows.This proof proceeds in two phases: we first show that A R•V accepts exactly the token sequences we want, and then briefly argue that the constraint application in the decoding loop is correct.For brevity, we reuse the notation set up in Appendix B.1.1 instead of restating it. Recall that we overload notation so A R•V (x) is a predicate indicating whether A R•V accepts x. The proof is a straightforward application of existing results.Theorem 2. For any x ∈ V * , A R•V (x) is true iff D(x) matches the regex R.Proof. First, note that A R•V is the composition of A R and T V . From previous work establishing the connection between regexes and FSAs (Kleene, 1951; McNaughton & Yamada, 1960; Thompson, 1968) , we know that for any character sequence w ∈ Σ * , A R (w) is true iff w matches the regex R. From the definition of FST-FSA composition (Riley et al., 2009) , we know that for any x ∈ V * , A R•V (x) = A R (T V (x)). Finally, by applying Theorem 1 we have that A R•V (x) = A R (D(x)).Stated plainly, A R•V accepts all token sequences that, when detokenized, match the regex R.Prior work by Deutsch et al. (2019) and Zhang et al. (2019) already developed a framework for applying token-accepting FSA constraints (called "covering grammars" in the latter) to sequence models, so we merely sketch a proof here.The decoding loop is augmented with a state q, initially I R•V , that tracks the current state in the constraint FSA (a single state suffices because A R•V is determinized). On each decoding step, we mask out the sampling logits of any token not among the outbound edges of q, and then update q based on the decoded token. A R•V accepts the decoded LM output by construction, and from Theorem 2 we know that the detokenized LM output matches the regex R. In addition, since Algorithm 2 does not touch the logits of non-masked tokens, the LM is free to output any token sequence that matches R.As in the previous section, we first prove correctness of P G•V and then briefly argue for the correctness of the constraint application. As Algorithm 3 is a minor variation on Algorithm 2, the proofs and arguments are very similar.For brevity, we reuse the notation set up in Algorithm B.1.1 instead of restating it. Recall that we overload notation so P G•V (x) is a predicate indicating whether P G•V accepts x. As with Theorem 2, the proof is a straightforward application of existing results.Theorem 3. For any x ∈ V * , P G•V (x) is true iff D(x) matches the grammar G.Proof. First, note that P G•V is the composition of P G and T V . From previous work (Allauzen & Riley, 2012 , Section 4.5), we know that for any character sequence w ∈ Σ * , P G (w) is true iff w matches the grammar G. From the definition of FST-PDA composition (Allauzen & Riley, 2012, Section 4. 2), we know that for any x ∈ V * , P G•V (x) = P G (T V (x)). Finally, by applying Theorem 1 we have that P G•V (x) = P G (D(x)).The decoding loop in Algorithm 3 is essentially the same as Algorithm 2, but with minor changes to traverse a PDA instead of an FSA. Specifically, whereas Algorithm 2 only tracks an FSA state q, Algorithm 3 tracks a PDA state q and a stack s, initially empty (a single q and s suffice, because we assume G is a deterministic context-free grammar). When considering the outbound edges of q, each edge e is also filtered based on whether the current stack s matches e ↑ , the stack symbols popped by e. Finally, when an edge is traversed, the stack s is also updated by popping e ↑ and pushing e ↓ .By traversing P G•V during decoding and masking logits according to the outbound edges allowed by q and s, the LM is forced to generate a token sequence that P G•V accepts. Therefore, by Theorem 3 the detokenized LM output must match the grammar G. At the same time, since Algorithm 3 does not touch the logits of non-masked tokens, the LM is free to generate any output that matches G. In particular, the LM is allowed to output tokens that span multiple terminals or non-terminals (see Figure 7 ).This section provides additional details about the experiments we ran to measure speed.Following the instructions on the Outlines (Willard & Louf, 2023) homepage, we downloaded and installed Outlines using the command pip install outlines. The specific version we received was Outlines v0.0.34.We accessed the Gemma (Team et al., 2024) model via its integration into Outlines, using the command outlines.models.transformers("core-outline/gemma-2b-instruct"). Note that for these experiments, the LM's parameter size does not matter because we are timing computations outside the LM. Only the vocabulary size matters, and the vocabulary is constant across Gemma sizes.For our system, compilation includes the following operations:1. Parsing the regex into an FSA. 2. Optimizing the regex FSA (e.g., determinization).3. Composing the FSA with the vocabulary FST. 4. Optimizing the composed FSA.For Outlines, we were not familiar with that codebase and did not want to inadvertently include or exclude the wrong operations. Instead of trying to isolate the exact function(s) to benchmark, we took a black-box approach. We first called outlines.generate.regex() on the trivial regex /x/ to establish a baseline latency. Then we called it again on the target regex and subtracted off the baseline latency. In this way, we hoped to exclude any fixed costs that do not scale with regex complexity.This baseline correction is significant, as the trivial regex latency was 1/4 to 1/3 as large as most target regex latencies. For consistency, we performed the same baseline subtraction on our system, though it had far less impact-around 1/20 of most target regex latencies.For both systems, we processed a warm-up regex before starting the timed runs in order to trigger any lazy initialization. This is important in Outlines, because the vocabulary index is lazily initialized and takes tens of seconds to build.Recall that for each regex, we timed 10 runs and averaged the results to reduce noise.Outlines has a regex-to-indexed-FSM cache, however, so naïvely the last 9 runs would be cache hits with inaccurate latency. We addressed this by calling outlines.disable cache() to force the full computation on every run. Based on our (non-expert) inspection of the codebase, the only relevant cache this disables is the regex-to-indexed-FSM cache.As a sanity check, we also tried leaving caching on and instead appended a unique dummy character to the target regex on each run (e.g., /foo0/, /foo1/, etc.). This effectively "disables" the regex-to-indexed-FSM cache without impacting any other non-obvious caching in the system. These timings were very similar and slightly slower, likely due to the extra dummy character. Thus we infer that outlines.disable cache() does not cause a significant distortion of our measurements. The reported figures in Table 2 are based on measurements with the cache disabled, rather than the dummy character approach, as they were faster and did not require us to mangle the regex.For both systems, per-step overhead includes the following operations:1. From the start state of the automaton, find the set of valid next tokens. 2. Use these to build a vector marking valid and invalid tokens.3. Advance the automaton to the state corresponding to the first valid next token.We initially tried a more end-to-end approach, where we ran a Gemma LM with and without constraints and subtracted to measure the overhead. Unfortunately, LM latency is several orders of magnitude larger than the constraint overhead, so the measurements are dominated by noise in the LM computation-often yielding negative overhead measurements. Therefore, we measured the operations above in isolation from the LM.Here, we describe the constraints used in the speed experiments.This matches a set of predefined texts: /Red|Orange|Yellow|Green|Blue|Indigo|Violet/ This example represents the simplest type of constraint that one might realistically want to apply. For example, this could be used for basic /Yes|No/ question answering, or classification tasks like /Sports|Politics|Weather/.This matches an ISO 8601-style date time expression: This example represents a slightly more complex constraint, with a non-trivial but relatively straightforward lattice structure.This matches an IPv4 address and is copied from the Outlines This example is moderately complex and exercises grouped repetition. Beyond those characteristics, we primarily chose this constraint because, as it comes from Outlines, it is clearly not a "cherry-picked" example.This matches a double-quoted string like "foo". This example is intended to highlight the extensions we presented in Section 2.5. The comparison in Table 2 shows a clear advantage relative to the other constraints.This matches a JSON object that conforms to a JSON schema (see Section 5.1). Both our system and Outlines have methods for converting a JSON schema into a regex. The resulting regexes are quite verbose, however, so we specify the schema instead of the full regex:{ "type": "object", "properties": { "name": {"type": "string"}, "class": { "type": "string", "enum": ["Warrior", "Rogue", "Sorceror"] }, "life": {"type": "integer"}, "mana": {"type": "integer"}, "equipment": { "type": "array", "items": {In this paper we use the mathematical definition of regular expressions. Many tools extend regular expressions with non-regular features like backreferences-at the cost of exponential runtime.T (w) should be a set because a non-deterministic FST can transduce the same input to different outputs. In this paper, the FSTs we define satisfy |T (w)| = 1 so we simply write v = T (w).https://github.com/outlines-dev/outlines/issues/684Even further optimization is possible, too. For example, Argueta & Chiang (2018) claim a 4.5x improvement over OpenFST by applying GPUs.https://outlines-dev.github.io/outlines/reference/regex/ 


Decision: This submission presents an interesting tokenization approach that can contribute to improving the applicability of language models. The paper makes a formal contribution, and does it well. It could be stronger by including an empirical contribution. The authors conducted some experiments during the discussion period, and the paper would be strengthened significantly by including these (and further expanding them). Beyond the empirical evidence, it will allow for better comparison to prior work.

Reviews: review: paper_summary: paper_summary: The paper presents a system for restricting LM decoding to guarantee correct statements in a particular formal language like json expressions or python coding. The proposal is to use a grammar written as regular expressions, but before it is necessary getting units of the language vocabulary out of the subwords delivered because input has been tokenized into subwords. Finite state automatas are proposed to handle this.
strength_weakness: strength_weakness: The contribution of the paper in relation to the areas covered by the call is not clear, because the paper does not address the language modelling.  The use of regular expressions to handle the output of the model is not new, as the authors recognized. 
Authors propose to use FST for detokenization, but it looks as is only the reconstruction of acceptable terms out of the subtokens that the model delivers as output. There is no evaluation of the requirements of building the FST for a particular language. There is no consistent evaluation of the proposal made in this paper that could help to see the contribution.  In fact, authors acknowledge that their contribution is not empirical, but conceptual.
paper_summary: paper_summary: This draft deals with the problem of constraining a LM to generate output satisfying a certain syntax that can be expressed by means of some formal grammar, as for instance the syntax of specific API calls. This problem is complicated by tokenization, which is misaligned with the formal grammar. The proposed approach is based on the idea of detokenization and uses the framework of automata theory to derive an efficient solution for the regular language case. The idea is also extended to deterministic context-free languages.
strength_weakness: strength_weakness: None that I can see. The basic implementation of detokenization through finite automata is very simple, but I don't think this is a reason to reject.
questions: questions: No question to the authors. What follows is a list of minor suggestions.

You write sequences in the form $e_1 \ldots e_n$, but a much more used convention in formal language theory is $e_1 \cdots e_n$. There are several instances in the draft. 

pg.1,l.-7: separator > operator ?

pg.2: iff e_i^\sigma = \ep. > iff e_i^\sigma = \ep, for some i. 

the following bib entry seems incomplete: 'Brandon T. Willard and Remi Louf. Efficient guided generation for large language models, 2023.'.
paper_summary: paper_summary: This paper explores constraining the output of an LLM using finite state techniques, since many constrained languages can be defined in terms of formal languages (either a context-free language or even a regular language).  It also notes that tokenization issues can be accounted for by simply creating a finite state transducer to shift from the tokenized language to the output language in which the constraints are defined, and this transducer and finite state machine (or in fact, a context free equivalent called a pushdown automata) can be composed and evaluated efficiently.  The authors also suggest some "wildcard" extensions to cover common use cases, such as a paragraph of text or any single token.

The authors make a reasonable case for their approach, and is generally quite clear and accessible for a mathematically adept audience.  The case they make for using an FST to convert between languages is a useful observation.  One slight complaint is that the description of PDA is a little dense --  the example could be explained a little more -- and it is hard to understand if/how the switch to context free languages affects the efficiency, etc.

The biggest issue with the paper is the omission of an "experiments" section, where the method would be empirically evaluated on real data.  The suggested approach could be measured in terms of memory use, time/compute resources, etc. compared to other proposals or even a simple baseline (checking and rejecting non-accepted output, needing to ask the model again).  Certainly it could be compared with some of the related work, such as Outlines which has a github page with an available implementation to test against.  The paper would also be much stronger if an example implementation was provided along with the conceptual description.

Regarding related work, it is a bit unclear to me how this project differs from Outlines.  I can see they both use Finite state automata.  This paper's authors claim that their approach is more generalizable, and link to a github issue, but it is not clear to me the substance of this difference.  Is the difference in using the FST to map between the LLM tokens and external text, as hinted to in the three contributions (listed on the first page of the paper)?
strength_weakness: strength_weakness: - lack of empirical validation

- lack of clear comparison with other existing techniques (either empirical --especially when those techniques have existing implementations, or even theoricial, i.e., comparison of runtimes in terms of tokens, vocabulary size, etc.)
paper_summary: paper_summary: Paper authors propose an approach to force the LLM output to adhere to a given regular expression or a deterministic grammar. According to the paper, one important problem when this task should be carried out is how to handle the misalignment between the requested constraints and text tokenization. In order to solve this problem, the detokenization task is formalized as a finite state automaton. Such automaton is then composed with another automaton reflecting the regular expression or deterministic grammar that will be used to constrain the output of the LLM. The paper also enumerates some possible applications of the proposed LLM output guidance system.

I think the paper addresses a very important and timely problem within the subfield of LLMs. I also find the proposed approach elegant and effective in solving the LLM's output guidance task. However, I think there are some problems with the paper that I would like to summarize below:

- The paper is strongly focused on describing the theoretical aspects of the proposed techniques but there are no examples that help the reader to really understand the motivation of the proposal. For instance, I miss a few or at least one example of LLM guidance where tokenization can result in a failure of the system and how the proposed technique is able to successfully remove those problems.

- The paper lacks an experimentation section measuring the performance of the proposal. Also such performance is not compared with that of previously existing approaches. Authors do mention that there is a strong relationship between their work and the work carried out by Willard & Louf, 2023, but no comparison is carried out. The authors state that their automata-theoretic-based technique makes "much easier to apply finite-state automata and generalize to push-down automata", but I think the paper does not clarify which are exactly the advantages that are introduced. Even if a systematic comparison is not reported, I think that at least some comparison examples would be needed to understand the relative merits of the proposal. Something similar to this is done in [Willard & Louf, 2023] and I think is very useful to have a better idea of the proposed work.

- I miss that the paper provides algorithms describing the two main LLM guidance techniques that are proposed. Instead, those techniques are described as enumerations in the paper's text. In spite of the fact that those enumerations are understandable, I think that using algorithms would be more suited in this case to explain the techniques in a precise and unambiguous way.

I am ambivalent about this paper. On one hand, I really like the elegance of the proposal, but on the other hand, the lack of a meaningful comparison with other works beyond what is stated in the Related Work section makes difficult for the reader to understand how the proposed technique improves previously existing ones.
strength_weakness: strength_weakness: - The paper mentions related work but there is no experimental section nor any comparison between the proposed technique and previously existing ones, in particular the technique proposed in [Willard & Louf, 2023].

- The paper does not include examples that would facilitate a better understanding of the problems being addressed.

Comments: title: New Response
appreciate recognizing the main point
not allowed to submit revision during discussion
Theory vs. experiments
changes sound good
Kind reminder on the close date of discussion is approaching
Kind reminder on the close date of discussion is approaching
Refining the example
Rebuttal Reponse
comment: I deeply appreciate the careful responses of the authors. I think they have made a nice work with the paper as I stated in my initial review. However, when analyzing the messages exchanged in the rebuttal period, I continue thinking that the paper in its current state does not include important empirical results demonstrating the improvements introduced by their technique, and in my view, their inclusion would require to conduct a new review process. Because of this, I cannot modify the score I have assigned to the paper. In any case, I strongly encourage the authors to introduce the new data into the paper, since this will result in a really nice work.
Thanks for trying to clarify the main issues I raised in my review. I appreciate you have now empirical evaluation to assess your proposal. I changed the score, although, to me the paper is not convincing in describing the importance of the problem and the solution.
We thank the reviewer for spending the time to reply and recognizing the main point we try to convey in this draft.
We thank the reviewer for taking the time to go through our rebuttal and increasing the score. We would love to update the submission to reflect our changes but according to the email sent by PCs titled **[COLM] Clarification regarding rebuttals + camera ready page limit**
```
We do not allow to revise the submitted content during the rebuttal and discussion period, and we limit the length of rebuttals. 
```
We will reflect our changes in the final submission as promised. We hope this is understandable. Thank you!
I like the theoretical contribution in this draft, and I am convinced it will stimulate further work in this direction on the part of the community.  I don't feel experimental assessment is needed in this case, therefore I still stand by my original score.
In this response, the authors do confirm what I already inferred, that their finite state composition approach was more generalizable than other approaches like that of Outlines, which is helpful.  As far as the reasons this is more useful, I do think this is covered well in the paper and I am also aware of the "wealth of well-optimized algorithms" available with automata.  Though useful to know, this clarification alone doesn't change my score of the paper.

As far as the weakness regarding experiments, if they author do make the changes promised, this would add substantially to the paper, at least shifting it to "6: Marginally above acceptance threshold" if not higher.  However, I am not able to review such changes myself, I can only score the paper as written, so I will raise my score to "5".
Dear reviewer wViX, 
Thank you for the constructive suggestions! We would like to kindly raise your awareness that the close date of discussion is approaching. We hope our rebuttal have addressed most of the concerns and if not happy to provide more clarification.
Dear reviewer iNwk, 
Thank you for the constructive suggestions! We would like to kindly raise your awareness that the close date of discussion is approaching. We hope our rebuttal have addressed most of the concerns and if not happy to provide more clarification.
Sorry for our misunderstanding.  Our approach and Outlines have the **same guarantees for regular expressions**, so we cannot provide an example where either system is better than the other.  Our approach is **strictly better for grammars**, because Outlines [prevents tokens from crossing (non)terminal boundaries](https://github.com/outlines-dev/outlines/issues/684), whereas we do not.

As an example of where this might cause issues for Outlines but not our system, reconsider the example above, but now in the context of a CFG like:

```
S => FUNCTION "(" NUMBER ")"
FUNCTION => "foo" | "bar"
NUMBER => "123" | "456"
```

Since `foo`, `(`, `123`, and `)` are separate terminals, LM scoring with Outlines **would be distorted** in the manner described above, where the first and last rows are excluded and the LM scoring after constraints inverts the ranking of `foo(123)` vs `bar(456)`.  In contrast, our approach does not have any restrictions on (non)terminal boundaries, so LM scoring is **not distorted**.

Note that the grammar above is not contrived or specially-constructed to cause problems—in programming language grammars it is natural to treat parentheses, identifiers, and numbers as separate terminals.

One last note is that even if we had full parity with Outlines in terms of guarantees or correctness, our system is still more **generic/modular** and **much faster**.
Dear authors,

thanks for your careful response. I was aware of the example provided in the introduction. However, what I was missing in the paper is a specific example of how your technique succeeds in constraining the LLM output where another previously existing one fails. This could be shown for instance for the Willard & Louf, 2023 technique. 

After reading your rebuttal, I was wondering if the scoring distortion problems you mention would apply to the Willard & Louf's technique.