Automata-based constraints for language model decoding
Authors: Terry Koo
Frederick Liu
Luheng He
Venue: COLM (2024)
Keywords: finite state automaton, finite state transducer, pushdown automaton, language model, constrained decoding
TL;DR: Using automata theory to provide efficient, comprehensive, closed-form solutions for LM decoding constraints.

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.

Published as a conference paper at COLM 2024
Automata-based constraints for language model decoding
Terry Koo', Frederick Liu", and Luheng He
Google DeepMind {terrykoo, Seeerykko.fedeiickklle frederickliu, Luheng Aggoole..gggoo..cooo
Abstract
Language models (LMs) are often expected to generate strings in some formal language; for example, structured data, API calls, or code snip- pets. 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 impractícal 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 tokeniza- tion, 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 exten- sions 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 & 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.
1 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 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. 20166] Kudo & Richardson 2018) whose segmentations are generally both ambiguous and misaligned with formal-language tokens. For example, consider an API call [[x|=| | "bar" I). An LM might tokenize this as foo x=" |bal Gaarr" I)), merging some lexer tokens and splitting others; see Appendix A
like foo bx," which is typically lexed as fool (Ixi
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 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: 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.
* Equul contribution, alphabetical.

---

Published as a conference paper at COLM 2024
Figure FSAs that accept ab (left), odd numbers as (center), and runs of as or bs (right). States are depicted as circles, with the start state in bold and final states doubled. Edges are depicted as directed arcs, labeled with the relevant input symbol, or if none.
0
Figure 2:
The FSA constructed from the regular expression /a+ /a+ is initially non- deterministic (left), but can be determinized (right).
Prior work (Wllard & Louf 2023 has addressed these tokenization issues, but with bespoke solutions. By developing a proper theoretical grounding, we gain advantages speed (see Section 6.1) correctness (see Appendix B), and extensibility (see Section 3.2 and 4.3)
2 Finite-state constraints
In this section, we provide some background and then describe our main set of contributions.
2.1 Finite-state automata (FSAs)
A finite-state automaton A is a tuple (I, F,F,F) where Σ is set of input symbols, Q finite set of states, E and
are initial and final states, and E C Q x Eg Q, where E. = UU [e), is set of edges HHoprroft et al. 2001 Riley et al. 2009). Each edge e E is tuple (e",e" ,ee) of source state e", input label e none, and target state ef See Figure
An FSA A accepts w E' if there exist e ei...., en E E such that w eG ef = e, E F, and ei = = for i 1; note that > |wl iff 3i, ef =e. predicate that is true iff A accepts w. For any FSA AA, we define its language LA = {w E Σ A(w)) as the set of strings it accepts. More generally, the regular languages can be defined as { A is FSA} (Chomsky 1956).
e. To express the functional behavior of FSAs, we overload notation and define A(w)
Conveniently, the regular languages can also be defined by regular expressions which are equivalent to FSAs (Kleene 1951). Common tools like UNIX grep compile regular expres- sions into FSAs with > Unicode, which are then used as predicates on text (McNaughton Thompson 1968). See Figure (left).
& Yamada 1960:
An FSA is deterministiic if E E, e" e and Vg E Q E, 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. particular, given an arbitrary FSA one can build a deterministic FSA A' such that LA = LAy' (Rabin & Scott 1959). See Figure
2.2 Finite-state transducers (FSTs)
finite-state transducer is an FSA that generates output. Formally, an FST T is a tuple (Σ, Q, E) where Σ, Q, I, and F are as defined for FSAs, A is set of output symbols, and E C x x A x Q is a set of edges (Mohri 1997 2004 Riley et al.) 2009). Each edge E is tuple (e E ,e,ee) where é, e², and et are as defined for FSAs and e" its output label, or if none. See Figure
In this paper we the mathematical definition of regular expressions. Many tools extend regular expressions with non-regular features like backreferences at the cost of exponential runtime.
2

---

Published as a conference paper at COLM 2024
822
Figure 3: FSIs that transduce ab into x (left), odd numbers of as into xoxo "*x (center), and runs of as bs into bracketed versions of themselves (right). Edge labels are el
cf
Tokens
ff
ca
00oo
00
foo
for food
foodd
Figure 4: A simple vocabulary of tokens (left), and a detokenizing FST that transduces sequences of those tokens into sequences of characters (right).
E Σ* into A if there exist é1, e,,,, en E such that w e en 0 == ef... e ej L, c E F, and e = for i >> 1. Similar to FSAs, we w == T if T transduces uces to D. Critically, the output of one FST can be fed as the input another FST or FSA (Riley et al.] 2009). Given FSTs Ti and T2 where A₁ Σz we can compose them into new F 220 20% where y' Σn, A' 42, and (ww) = (2( Similarly, given an FST Ti and FSA A where A E2, we can compose them into new FSA A' = o where E' Σ and A'(w) (w))
An FST transduces
2.3 Detokenization transduction
Our first contribution 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 Ty = (vv,Av, Qv, lv, Ev) from vocabulary V
Σv + V, Av + {1 : 1i < | >> inputs/ inputs/outputs outputs are cchrenn/caaacters of V initiallly, Ty only has a root state 9r
Qv + {{r}, lv + dr, Fv {9r), Ev t 0
for u E V do
90 < 9r, n + |p|
for = 1 1do
build chain for all but the last character >> no input with non-final output
Qv + Ey Ey ((n-110 9n)) b input whole token with last output, cycle to root
Ey + Ev U
For compactness, common prefixes of the chains can be merged to form a trie-like structure, as in Figure see Appendix for proof of correctness.
2.4 Adapting regular expressions to tokens
Our next contribution is generic method for adapting any FSA from characters to tokens. Specifically, given a token vocabulary and an FSA A that accepts character sequences, A' = A o Ty accepts essentially the same language A, but in token form. More precisely, for each token sequence w E LA the detokenization of w is in LA-
Note that the converse does not hold: w LA has counterpart in LA 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 (19, Nevertheless, to the extent that LA can be tokenized by V, strings in LA are represented in LA Indeed, due to tokenization
2T (w) should be set because non-deterministic FST can transduce the same input to different outputs. In this paper, the FSTs we define satisfy [T (w) we simply write Tww).
3

---

Published as a conference paper at COLM 2024
2
OU
0
food
Figure 5: The character-based FSA equivalent to /foo) +d/ (left) and its composition with the detokenizing FST from Figure 4 (right), Note that the same text can have many tokenizations (e-g,, foo 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 that are equivalent to the same string in A. See Figure
We now present our method for constraining an LM to regular language:
Algorithm Constrains LM L with vocabulary V generate the language of regex R
Tv + BUTLDDDETOKINTIINGSSTT())
token-to-character FST, see Algorithm D character-accepting FSA (Thompson 1968)
AR + BUI.DREGEXFSA (R)
ARoV +- DETERMINIZE(AR Tv)
> token-accepting FSA
4 IRoV
D start from initial FSA state
for f = 1 to T do
decoding steps
+ ()MPUTELOGITS(L)
A {e" :e EROV A = 9
> allowed next tokens penalize logits as in Deutsch et al. (2019)
for / = to [ooV[o |V|do do
if Dj & A then L
0 - SAMPLENEXTIOKEN
8 + s.t. eE EROV A = q &t
q A
find the matching edge b traverse the edge
Note that ARev is 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:
Ty is vocabulary-speccfic and, while large, can easily be pre-computed for each LM. .AR is vocabulary-agnostt, easily specified, and portable across different LMs.
This clean decomposition 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 Tv without changing the rest of the system. Similarly, alternative constraint automata (see Section 3.1 can be substituted for Ar and FST composition still works.
2.5
Extensions
Our last contribution in this section is set of regular expression extensions, written 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
2.5.1 Wildcard matching
One problem in our approach occurs with "wildcard" matches like /./ /["0-9]/ that match nearly any character. After composition with Tv, some states in the resulting FSA will have almost VI outbound edges, making it expensive to use- ase-keep in mind that V 100k for commonly-used LMs (Willard & Louf 2023) Section 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 valid tokens. For example, / (?P<PARAGRAPH TOKEN>> parses into terminal edge whose mask indicates newline-free tokens. This is useful for structuring

---

this be viewed as defect of Published as a conference paper at COLM 2024
Name
Description
QUOTED TEXT
Matches a quoted string with backslash escapes.
UNQUOTED TEXT
Matches YAML-style non-quoted string.
IMAGE
Matches an image generated by a multi-modal LM.
BOKEN
Matches single text token.
PARAGRAPH_ TOKEN
Matches a single text token with no newlines.
TEXT_UNTIL
Matches text tokens until a stop phrase appears.
SUBSTRING_OP
Matches any substring of a given string.
LMITED_LIS,
Matches delimited list of homogeneous items.
Matches a delimited subset of 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: Cin)* (PP<PARAGRAPHLTOKENN)) (3,55) 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 terminal mask we traverse that terminal edge.
Note that 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 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 bounded by newline.
2.5.2 Syntactic sugar
Sometimes, a constraint is inefficient to define as a regular expression. For example, suppose wish to reduce hallucination by forcing the LM to generate substring of some reference u, such as a user utterance. Unfortunately, the regular expression for substrings of u is ((Iu(2,, even though the corresponding FSA is the specification language.
/ to match any substring of "abc", resolving the defect by providing O[[u] specification syntax. Besides improving usability, these extensions mitigate the explosion 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.
We therefore define the syntactic sugar /wW.S/SSSSTIIINGFFFFOOOCC
3 Push-down constraints
This section briefly presents our second 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.
3.1 Push-down automata (PDAs)
push-down automaton can viewed as an FSA equipped with a stack. Formally, a PDA P tuple (Σ, 11, Q, 1, E) where Σ, Q, I, and F are defined for FSAs, 11 is set of stack symbols, S E 11 a unique initial stack symbol, and E C CQQ Ex 11 x Q x 11 is a set of edges (Hopcroft et al. 2001). Each edge E is tuple (e",", ee",e,,a e',e",,ee) where e², e and e are as defined for ESAs, and e' and e are popped and pushed stack symbols. See Figure
and
P accepts É Σ' if there exist é,, en E E such that e... E..ee, ef I, e¹ E F, = ej for i 1, and el and et form coherent sequence stack edits. Formally, let s' be the stack before e; where sl 5, n4 |s',, m; n; leel, and sl st,m, ej then e, s 1mn must

---

Published as a conference paper at COLM 2024
Rules
aa S /b/)
$ -> /ab/
-> /a/ S /b/
Figure A grammar for the canonical context-free language a"b" (left), and an equivalent PDA (right). Edge labels have ef on top, then el marked with and et marked with ( The stack symbols are Farley-style dotted rules (Farley) 1970) denoting "return addresses"
(Allauzen & Riley 2012, Section 4.5). The initial stack symbol S is written as a dot marked with square brackets aadd]
Tokens
bb
ca
a b bb
Cb
(atatab
aaab
[atatab
abab:b
Figure 7: A simple vocabulary of tokens (left), the detokenizing FST built from it (center), and its composition with the PDA from Figure (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, must match the suffix of s;, and update the stack by popping ej off and pushing e; on. As above, we write P (w) to indicate that P accepts w.
Unlike FSAs, non-deterministic and deterministic PDAs not equivalent: the former accept the contexi- free languages, which are also defined by context-free grammars (Chomsky 1956: Hopcroft et al. 2001), while the latter accept strict subset, the deterministic context- free langugges (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 result of this non-equivalence there is no general algorithu 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.
3.2 Adapting grammars to tokens
Although PDAs more expressive than FSAs, they behave similarly in many ways and, crucically, FSIs and PDAs are composable (Allauzen & Riley 2012). Formally, given an FST Ti and PDA P2 where A E2, we can compose them into new PDA p' P o Tı where Σ' = Σ and P'(w) = (T, (w)). ). As with FSAs, composition with the detokenizing FST Tv adapts 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
Tv + BUILDDETTOKENZINGGFSTVV
FST, see Algorithm
PG BULLDGRANMARPDA(G) > character-accepting PDA (Allauzen & Riley 2012
PGov + PG o Tv
> token-accepting PDA
f lçov, $ 5
4 start from initial PDA state and empty stack
for l = to T do
b decoding steps
+ COMPUTELOGITS(L)
A [ee : EgoV A
q As ends with et}
> allowed next tokens
for i = to [ do
penalize logits as in Deutsch et al. (2019)
if & A then e,
0 - SAMPLENEXTIOKENLA.
8 2- s.t. E EGOV A é 9 A ends with et Ae find the matching edge
+ ét, ń + ss 1,%,, + &
> traverse the edge

---

Published as a conference paper at COLM 2024
This paper
FST
Composition
Vocab
Regex
FSA
much faster
FSA
Outlines
Indexing
Figure Flowchart comparing this paper with Outlines (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 many times faster than indexing (see Section 6.1).
It's worth re-emphasizing the benefits of formulating detokenization as an FST. By repre- senting the entire task in terms of automata, our approach easily generalizes from regular expressions 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 cross (non-)terminal boundaries in the grammar (see Figure
Related work
There is great deal of work related to the use of automata to constrain learned models.
4.1 Automata for sequence 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 (017) and Zhang et al. (2019), among others this line of work, examine text normalization for TTS applications. Certain phrases are difficult to verbalize (e.g., "4/5" to "four fifths" or AAril fifth" or "four out of five [stars]"), and neural models are prone to hallucinations (e.g,, "60" to "six"). The authors build FSIs that translate from written forms to possible verbalizations, and use those to guide the deep model similarly to this work. Our approach allows wider range of constraints, supporting any regular deterministic context-fres free language, and also addresses the token-mismatch issues endemic to current LM tokenizers (see Appendix
Deutsch et al. 2019) use (intersections of) FSAs and PDAs to constrain the output of sequential model to some formal language. This work predates the rise of general- peneral--urpose 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.
4.2 Automata for general-purpose LMs
The most relevant work Outlines (Willard & Louf 2023), which based on bespoke "in- dexing" operation that builds token-based overlay an FSA or PDA. Unfortunately, when applied to PDAs their algorithm over-constrained w.r.t tokenization (see Appendix A..]. 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 rewrite of their indexing algorithm. Finally, their approach is ~7,000x slower to compile than ours (see Section 6. it is only practical when the constraint can be pre-compiled. Our 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 illustrates which parts of our system are similar 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 of significant practical interest and could be adapted to our approach as our techniques appear to be largely orthogonal.
pectps://githie httta:///ttttiiccocottiiieeeeres

---

Published as a conference paper at COLM 2024
SynCode (Ugare et al., 2024) is more recent system that also exploits FSAs, but handles grammars using (I and (R(1) parsers rather than PDAs. Like Outlines, their approach relies on 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-theorete 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 method to statically pre-compute these matches, as we and the systems above do. For example, Synchromesh (Poesia 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 2023 adds expressive power beyond context- free. 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 un- constrained continuations and reject invalid ones post-hoc. For example, PICARD (Scholak iet 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 lowprrobayility token. In addition, note that post-hoc filtering is orthogonal to predictive masking, so our approaches could be merged.
4.3 Automata for LM tokenization
Concurrently with review, |Berllund et al. 2024) presented finite-state machine that only
review,Bergluuge
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 BIE tokenization of w. As they mention 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.
5
Applications
The clean design and efficiency of our approach enable number of different applications. We present several illustrative examples here.
5.1 JSON expressions
JSON (Pezoa al. 2016) is widely-used structured data format that LMs often expected to generate. We study the problem of generating JSON that conforms to a schema, which is mapping from field name 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 expres- sion corresponding to particular schema: while leaf-level matchers like / /(truel 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 mentioned above is context-free. A simple approach is to impose constant limits ko and kA on object and array nesting, which reduces from context-free to regular, and we have implemented tools to generate regular
8

---

Published as a conference paper at COLM 2024
Compilation speedup
Per-step
Constraint
speedup
Multiple choice
7,970x
29.5x
ISO date-time
7,110x
24.3x
IP' address
6,850x
26.1x
Quoted text
13,400x
6.5x
JSON object
7,240x
33.6x
Table 2: Speed measurements, expressed relative speedups of this paper over Outlines (Willard & Louf 2023). The constraints are detailed in Appendix C.4
expressions for this form of depth-truncated JSON. Naturally, one can also directly convert the JSON grammar into PDA-based constraint.
5.2 Python dataclasses
Another case study is constraining LMs to output Python dataclasses (Van Rossum & Drake 2009). Like the JSÓN schemas described above, Python dataclass defines a mapping from hell names to types, and we have implemented similar tooling that reflects to automatically build a regular expression matching constructor calls. This enables particularly convenient API where one can use a dataclass type to build constraint, and then parse the constrained LM response back into an instance of T.
dataclass
5.3 Speculative decoding
Speculative decoding [eviathan et al. 2023) is method for speeding up LM inference via speculative execution. Short runs tokens are sampled from faster approximation model, and then verified with a more accurate larget 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-sanae sampled tokens that pass verification.
The approximation model is typically smaller LM that has disproportionately greater difficulties following formal syntax, tion 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 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 method for sharing the penalties with the target model.
natural application is to constrain the approxima-
Experiments
Here we provide an empirical evaluation of the speed and correctness of our approach.
6.1 Speed
We measured our system and Outlines (Wlllard & Louf 2023 the following tasks:
1. Constraint compilation:
Time 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 Ap- pendix C.3 for details.
We used Gemma TTeam 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; Table

---

Published as a conference paper at COLM 2024
Model
Unconstrained
Constrained
Gemma-2B
0.09
1.0
Gemma-7B
0.65
1.0
Table 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 com- pilation, Outlines takes 10s of seconds JSON and few seconds elsewhere, while our system takes a few milliseconds on JSON and 100s microseconds elsewhere. For per-step overhead, Outlines takes 10s of microseconds and our system takes 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 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 highly- optimized imt.reentttllleetttiiittoi of FST operations (Riley al., 2009). Critically, this is only possible because we reformulated the whole problem in terms of automata. As analogy, imagine two programs for some scientific computing task. The first entirely written by hand, while the second reduces the problem to linear algebra and uses NumPy (Harris et al.. 2020). The latter likely be much faster, due to the sheer volume of effort that has gone into optimizing NumPy.
6.2 Correctness
We exercise output formatting correctness with Gemma on GPQA RRin 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.
7 Conclusion and future work
In this paper, we described system for constraining LM decoding. Our key contribution is 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 automata theory.
solutions by leveraging the considerable toolkit of
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 well-studied problem, and there are similar limitations regarding grammar specification in parsers for determinstic context-free languages: as simple example, an LL(k) parser cannot parse left-recursive grammar. There is 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 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"b" is no longer context- free, since we can bound и S 50. It may be interesting to investigate longer-running, possibly multi-phase constraint other hand, even for shorter outputs where FSAs are competitive, PDAs might still provide value because they are generally more compact than equivalent FSAs.
cases where PDAs can provide more benefit. On the
'Even further optimization is possible, too. For example, Argueta & Chiang 2018 claim 4.5x improvement over OpenPST by applying GPUs
10

---

Published as a conference paper at COLM 2024
References
Cyril Allauzen and Michael Riley. A pushdown transducer extension for the openfst library. In Proceedings of the 17th International Conference on Impleeenntation and Applica- fion of Automata, C1AA'12, pp. 66-77, Berlin, Heidelberg, 2012. Springer-Verlag. ISBN 9783642316050. doi: 10.1007 12110779988-3662-336666 978-3-642-31666--77
URL https:://6oi.org//1g 1007/
Arturo Argueta and David Chiang. Composing finite state transducers on GPUs. In Iryna Gurevych and Yusuke Miyao (eds.), Proceedings of the 56th Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 2697-2705, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10.18653/11/P181110
URL
org/P18 1251
Martin Berglund, Willeke Martens, and Brink van der Merwe. Constructing a bpe tokeniza- tion dfa, 2024.
Noam Chomsky, Three models for the description of language. IRE Transactions on Informa- fion Theory, 2(3):113-124, 1956. doi: 10.1109 11T.195...05611..
Daniel Deutsch, Shyam Upadhyay, and Dan Roth. A general-purpose algorithm for con- strained sequential inference. In Mohit Bansal and Aline Villavicencio (eds.), Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL), pp. 482-492, Hong Kong, China, November 2019. Association for Computational Linguistics. doi: 10.18653/v1 111////11111105555 URL /tt/ttpps///ccaattooogo.oorrr///
Jay Earley. An efficient context-free parsing algorithm. Commun. 13(2)44-1111 feb 1970. ISSN 0001-0782,
doi: 10. 10.1145/360007.3220555 URL https:///doi.rr//1..
002007.362033
Matthew M. Geller, Michael Harrison, and Ivan M. Havel. Normal forms of deterministic
grammars. Discrete Mathematics, 16(4):313-32 1976. ISSN 0012-365X. doi: https://doi.
0tg/100.006//0000-66677700000000 prttccee/p1//0011236x7666666
URL https:
Saibo Geng, Martin Josifoski, Maxime Peyrard, and Robert West. Grammar-constrained decoding for structured NLP tasks without finetuning. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 10932-10952, Singapore, December 2023. Association for Computational Linguistics. doi: 10.18653/v1/2023.emr 2023. emnlp-main. 674
URL httphtttt///cclathoolooo orgg
Seymour Ginsburg and Sheila Greibach. Deterministic context free languages, Informa- fion and Control, (60-6688648, 1966. ISSN 0019-9958. doi: https://doi.org//100 60019-9955866))8019999
URL http:p//www...eeeeccaaeetttettts
500199958568001999 99
Sheila A. Greibach. A new normal-form theorem for context-free phrase grammars. A.M,M, 12(1):42-52, jan 1965. ISSN 0004-5411, doi: 10.1145/321250.322225 URL https 321254.
//doi wtt.orr//.1...1///3..1
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Vir- tanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy. Na- ture, (e355557755 September 2020. doi: 10.1038/ 1111///4118800002649444 URL https! //doi 1ttp//11..03//4155886
Michael A. Harrison and Ivan M. Havel. Strict deterministic grammars. Journal of Computer and System Sciences, 7(3):237-277, 1973. ISSN 0022-0000. doi: https:/ http///oiooooo/.////o 110.10016/ 00022-00000/73)8000--XX URL http://wwww/cccoo www.://cceeceeeeeeteccc//ceeeeee 038228000078800088
11

---

Published as a conference paper at COLM 2024
Ivan M. Havel and Michael A. Harrison. On the parsing of deterministic languages. ACM, 54 oct 1974. ISSN 0004-5411. doi: 10.1140 32145552211.0018511..... URL tts //doi.org/10.111 11110..11453228855 321851
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to automala theory, languages, and computation, 2nd edition. ACM Press, New York, NY, USA, 2001. doi: http:// 30o..ac.orrg10..155/// 10.11455/56488855686446
Stephen Cole Kleene. Representation of events in nerve nets and finite automata. Technical Report RAND-RM-704, The RAND Corporation, 1951. URL https://wwen wawd. org/
Content//amm/rand//bb///rrssss /ttp://sseeeeeeeeeeeeeerraaaa//a
memoranda/2008/ 20000///M704..ff
Donald E. Knuth. On the translation of languages from left to right. Information and Control,
8(6))607-633, 1965. ISSN 0019-9958, doi:
Robert Koch and Norbert Blum. Greibach normal form transformation, revisited. In Rüdiger Reischuk and Michel Morvan (eds.), STACS 97, pp. 47-54, Berlin, Heidelberg, 1997. Springer Berlin Heidelberg. ISBN 978-3-540--6342-11.
Taku Kudo and John Richardson. Sentencepiece: A simple and language independent subword tokenizer and detokenizer for neural text processing. CoRR, abs/ /////1888.00222 2018.
06226
Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, pp. 19274-19286. PMLR, 2023.
Alexander K. Lew, Tan Zhi-Xuan Gabriel Grand, and Vikash K. Mansinghka, Sequential monte carlo steering of large language models using probabilistic programs, 2023.
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d' A'Auumme, Igor Babuschkin, Xinyun Chen, Po-Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel J. Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando de Freitas, Koray Kavukcuoglu, and Oriol Vinyals. Competition-level code generation with alphacode. Science, 378(6624): 1092-1097, 2022. doi: 10.1126/ abqlle8. URL https: //www. science. www./orgg//o////ooo 10. 20.1126/science abq1 abq1188 158.
Michael Xieyang Liu, Frederick Liu, Alexander J. Fiannaca, Terry Koo, Lucas Dixon, Michael Terry, and Carrie J. Cai. "we need structured output": Towards user-centered constraints on large language model output. In Extended Abstracts of the CHI Conference on Human Factors in Computing Systems, CHI '44 ACM, May 2024. doi: 10.1145/36139955560077.
URL http://dxx www..org//.... wotg//....5/////// 1145/36 3905. 3650756
Scott Lundberg. The art of prompt design: Prompt boundaries and token healing. Towards Data Science, 2023. URL httos://toowarlssttttcciieee comm
R. McNaughton and H. Yamada. Regular expressions and state graphs for automata. IRE
Transactions on Electronic Computers, 47, 1960. doi: 10.109//ECC.196005221633
Microsoft. Guidance, 2023. URL http:/ppp//gtttto.oooo/////nnana
Mehryar Mohri. Finite-state transducers in language and speech processing. Computational Linguistics, 23(2):269-311, 1997. htt.http:.///caaattooooooo//////
Mehryar Mohri. Weighted Finite-State Transducer Algorithms. An Overview, pp. 551-563. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004. ISBN 978-3-540-39886688 /ttp://///.1111007777-----8--810
doi:
221000/977-3-555 3-540-3980-------- 29. URL htw.htttps:/doo..or/////// 1007
29
12

---

Published as a conference paper at COLM 2024
Felipe Pezoa, Juan L. Reutter, Fernando Suarez, Martín Ugarte, and Domagoj Vrgoč. Foun- dations of json schema. In Proceedings of the 25th International Conference on World Wide Web, WWW '16, pp. 263-273, Republic and Canton of Geneva, CHE, 2016. Interna- tional World Wide Web Conferences Steering Committee. ISBN 9781450341431. doi: 2883029
10.1145/2872427.1 2883029.
Gabriel Poesia, Alex Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. Synchromesh: Reliable code generation from pre-trained language models. In International Conference on Learning Representations, 2022. URL https://
M. O. Rabin and D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3(2):114-125, 1959. doi: 10.1147/rd... 1
David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Dirani, Julian Michael, and Samuel R. Bowman. Gpqa: A graduate-leve google- proof q&a benchmark, 2023.
Michael Riley, Cyril Allauzen, and Martin Jansche. OpenEst: An open-source, weighted finite-state transducer library and its applications to speech and language. In Ciprian Chelba, Paul Kantor, and Brian Roark (eds.), Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Lingwistics, Companion Volume: Tutorial Abstracts, pp. 9-10, Boulder, Colorado, May 2009, Association for Computational Linguistics. URL
org org/N09-4005
Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. PICARD: Parsing incrementally for constrained auto-regressive decoding from language models. In -rancnFran Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih (eds.), Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 9895-9901, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics. doi:
1tt66/3/v1222.emm///m/ 2021.emnIp-me semnpp-main... 779
URL htttps://aclanthology/ org/
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. In Katrin Erk and Noah A. Smith (eds.), Proceedings of the 54th Annual Meeting of the Association for Compulational Linguistics (Volume 1: Long Papers), pp. 1715-1725, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 11116533/11P116118 URL UKL/ittps://aaaaantoloog orrp:/oooo..orgg11-112122
Richard Sproat and Navdeep Jaitly Rnn approaches to text normalization: A challenge, 2017.
Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière Mihir Sanjay Kale, Juliette Love, Pouya Tafti, Léonard Hussenot, Pier Giuseppe Sessa, Aakanksha Chowdhery, Adam Roberts, Aditya Barua, Alex Botev, Alex Castro-Ros, Ambrose Slone, Amélie Héliou, Andrea Tacchetti, Anna Bulanova, Antonia Paterson, Beth Tsai, Bobak Shahriari, Charline Le Lan, Christopher A. Choquette-Choo, Clément Crepy, Daniel Cer, Daphne Ippolito, David Reid, Elena Buchatskaya, Eric Ni, Eric Noland, Geng Yan, George Tucker, George- Christian Muraru, Grigory Rozhdestvenskly, Henryk Michalewski, Ian Tenney, Ivan Grishchenko, Jacob Austin, James Keeling, Jane Labanowski, Jean-Baptiste Lespiau, Jeff Stanway, Jenny Brennan, Jeremy Chen, Johan Ferret, Justin Chiu, Justin Mao-Jones, Katherine Lee, Kathy Yu, Katie Millican, Lars Lowe Sjoesund, Lisa Lee, Lucas Dixon, Machel Reid, Maciej Mikula, Mateo Wirth, Michael Sharman, Nikolai Chinaev, Nithum Thain, Olivier Bachem, Oscar Chang, Oscar Wahltinez, Paige Bailey, Paul Michel, Petko Yotov, Rahma Chaabouni, Ramona Comanescu, Reena Jana, Rohan Anil, Ross Mcllroy, Ruibo Liu, Ryan Mullins, Samuel L Smith, Sebastian Borgeaud, Sertan Girgin, Sholto Douglas, Shree Pandya, Siamak Shakeri, Soham De, Ted Klimenko, Tom Hennigan, Vlad Feinberg, Wojciech Stokowiec, Yu hui Chen, Zafarali Ahmed, Zhitao Gong, Tris Warkentin, Ludovic Peran, Minh Giang, Clément Farabet, Oriol Vinyals, Jeff Dean, Koray Kavukcuoglu, Demis Hassabis, Zoubin Ghahramani, Douglas Eck, Joelle Barral, Fernando
13

---

Published as a conference paper at COLM 2024
Pereira, Eli Collins, Armand Joulin, Noah Fiedel, Evan Senter, Alek Andreev, and Kathleen Kenealy, Gemma: Open models based on gemini research and technology, 2024. URL
https://arxiv.org//e wtt.:oogg//bbboaoooo 2403. 08295
Ken Thompson. Programming techniques: Regular expression search algorithm. Commun. ACM, (16):4444)11 jun 1968. ISSN 0001-0782. doi: 10.1145/36337..3333/7 URL httss
1.00i..rr/10.1115//5533 363387
Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Singh. Improving Ilm code generation with grammar augmentation, 2024.
Guido Van Rossum and Fred L. Drake. Python 3 Reference Manual. CreateSpace, Scotts Valley, CA, 2009, ISBN 1441412697.
Brandon T Willard and Rémi Louf. Efficient guided generation for Ilms. arv preprint arXit:2307.09702 2023.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. In The Eleventh International Conference on Learning Representations, 2023. URL https: /
forum?id=WE..luYUU-
Liangsheng Yin, Ying Sheng, and Lianmin Zheng. Fast JSON Decoding for Local LLMs with Compressed Finite State Machine, 2024. URL https::/mmmss..org////
Hao Zhang, Richard Sproat, Axel H. Ng, Felix Stahlberg, Xiaochang Peng, Kyle Gor- man, and Brian Roark. Neural models of text normalization for speech applications. Computational Linguistics, 45(2):293-337, June 2019. doi: 10.1162/ aoliia_00000 URL httpss///eclaattooooo.orr//////
A Tokenization mismatch problems
Suppose that there two APIs that can be called like foo (123) bar (456), and that each call has two possible tokenizations, with the following LM scores:
Score
Tokenization
0.4
folo 3)
0.3
bar ( ([456])
0.2 fool (1123l)
0.1 ball r (4
When all tokenizations are allowed, foo()23) is clearly the best LM output. However, tokens like r44 are difficult support because they cross boundaries between different syntactic units. Handling all possible cases in manual implementation is difficult to the point of being impractical. It's worth emphasizing that this real problem in current LMs. For example, the Gemma (Team et al., 2024) vocabulary includes tokens like .),, or =r=""" which span across several syntactic units.
A naive constraint system might simply force the LM tokenization to fit the formal syntax, effectively excluding the first and last rows in the table above. This simplifies the implemen- tation, but in this example it also inverts the ranking- of the remaining rows, bar (456) is the best LM output. Thus, forcing the tokenization to the formal language can distort scoring in harmful ways.
A.1 Grammar-based constraints Outlines are over-constrained
As of this writing, grasmar-based constraints in Outlines (Willard & Louf 2023 do not allow LM tokens to cross between terminals in the grammar. This can lead to scoring distortions as described above, as their system will forbid certain tokenizations.
Reprising the example from earlier, consider the following simple CFG:
14

---

Published as a conference paper at COLM 2024
louce
E.0
cf
2
rif
0070
forrr
0
fooo
Eff
E:0
cf
foodd
6
r:0
foodd
Figure 9; The FST constructed by Algorithm from the vocabulary in Figure (left), and the equivalent compact trie-like FST copied from Figure convenient reference (right). Note, for example, that there are three "c:f" edges on the left, which are merged into single edge on the right.
S
FUNCTION "(" NUMBER ")"
FUNCTION NUMBER "123"
"foo"
"bar"
"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 r4 will be forbidden. This can lead to a ranking inversion as described above, where the best LM output changes depending whether tokenization is free or restricted.
B Proofs of correctness
Here we prove the correctness of our approach.
B.1 Proof of Algorithm
In this section we prove that, given a vocabulary V, Algorithm I 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 [ 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.
B.1.1 Correctness of the original detokenizing FST
Formally, let V be a set of opaque tokens, where each token E V can be detokenized into unique character sequence d(v) Σ² Let W (d(v)
V) be the set of detokenizations detokenizations of each token: (xx) = d(xx) )d [xg )d(xx)_..dxx,)
V* is the concatenation of the of each token. The detokenization of a token sequence where n |x|. Let Tv be the FST
as originally constructed from V by Algorithm | Recall that the notation Tv (x) denotes the output sequence generated by that FST for the input x-our goal is to prove (vv.) = D(.).
We now review the structure of Ty; see Figure (left) for visual example. First, note that Tv has exactly one initial and final state, which are the same "root" state 4r. For each v V, Algorithm Diiimmmadde adds exactly one cycle that starts and ends at 4r and generates the characters of (v) as outputs, in order. The last edge of each cycle consumes input v, while the other edges consume nothing (i.e., input e). There are edges outside of those [ cycles.
15

---

Published as a conference paper at COLM 2024
Before proving the main theorem, we first prove some supporting results. First, we define the possible paths one may traverse through Tv.
Lemma 1. Every valid transduction by Tv starts and ends at qr, and traverses zero or more of the [V] cycles, in any order.
Proof. By definition of Iv and Fv, every transduction must start and end at gr. A trivial transduction stops immediately at dr, traversing no edges or cycles. Any traversal that leaves Ir must enter one of the VV cycles and cannot stop until it returns to dr by completing the cycle-an arbitrary number of cycles may be traversed in this manner. Finally, since all cycles are start and end at fr, there are no ordering dependencies: any cycle may be traversed after any other cycle. Therefore, transduction by Tv must traverse any number of cycles in any order.
From this we derive several related corollaries, which we prove en masse.
The domain of (-) is Vt. Corollary The codomain of (Tv()) Corollary 3. For any x E V*, (x) is (xx).
Corollary 1.
(-) is W
Proof. Each result is immediate from Lemma and the fact that each of the [V] cycles in Tv
uniquely consumes exactly one input token and outputs exactly the characters of d(v).
These combine to prove the main theorem.
Theorem For any vocabulary V, Tv(.) = D(.).
Proof. First, observe that :(.)= - W has the same domain and codomain (v(-). Two functions are equivalent if they have the same domain (Corollary) codomain (Corollary 2
and map the same inputs to the same outputs (Corollary
B.1.2 Correctness of the compact detokenizing FST
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 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 |o| characters of every token, and [V] edges cycling back from the leaves of the trie to 9r-
follows that there are still exactly |V| cycles in the compact FST, where each cycle consists of path from qr to leaf of the prefix trie followed by one of the [V] edges back to gr. 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.
B.2 Proof of Algorithm 2
This proof proceeds in two phases: we first show that AROV accepts exactly the token sequences we want, and then briefly argue that the constraint application in the decoding loop is correct.
B.2.1 Correctness of Agov
For brevity, we reuse the notation set up in Appendix B.1.1 Appendix(B...] instead of restating it. Recall that we overload notation so ARoV (x) is a predicate indicating whether AREV accepts x. The proof is a straightforward application of existing results.
Theorem 2. For any x E V*, ARoV(( is true iff D(x) matches the regex R.
Ar and Tv. From previous work estab- lishing the connection between regexes and FSAs (Kleene 1951 McNaughton & Yamada 1960 Thompson 1968), we know that for any character sequence w E AR (W) is true iff matches the regex R. From the definition of FST-FSA composition (Riley et al. 2009
Proof. First, note that AroV is the composition
16

---

Published as a conference paper at COLM 2024
know that for any E V*, ARov(x) AR(Tv(x)). Finally, by applying Theorem | that (R) (D((x)))
we have
Stated plainly, ARav accepts all token sequences that, when detokenized, match the regex R.
B.2.2 Correctness of constraint application
Prior work by DDutsch et al. (0199) 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 proof here.
The decoding loop is augmented with state 9, initially IOVV, that tracks the current state in the constraint FSA (a single state suffices because AROV is determinized). On each decoding step, we mask out the sampling logits of any token not among the outbound edges of 9, and then update 9 based on the decoded token. Agav accepts the decoded LM output by construction, and from Theorem 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 free to output any token sequence that matches R.
B.3 Proof of Algorithm B
As in the previous section, we first prove correctness of PGvv and then briefly argue for the correctness of the constraint application. As Algorithm is a minor variation on Algorithm 2 the proofs and arguments are very similar.
B.3.1 Correctness of PGov
For brevity, we reuse the notation set up in Algorithm B.1.1 instead of restating it. Recall that we overload notation so Pcov(x (x) is predicate indicating whether Paav accepts x. As with Theorem 2
the proof is straightforward application of existing results.
Theorem For any x E V*, (x)v(x) is true iff (xx) matches the grammar G.
Proof. First, note that PGov is the composition of Pg and Tv. From previous work (Allauzen & Riley 2012 Section 4.5), we know that for any character sequence E Σ*, Pc(w) Is true
iff matches the grammar G. From the definition of FST-PDA composition (Allauzen &
Riley 2012 Section 4.2), we know that for any E V*, (xvv(x) = (x)Tv(x)), Finally, by we have that (x) (D)(x.).
applying Theorem
B.3.2 Correctness of constraint application
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 only tracks an FSA state 9, Algorithm 3 tracks PDA state g and stack s, initially empty (a single and s suffice, because we assume G is deterministic context-free grammar). When considering the outbound edges of 9, each edge e is also filtered based whether the current stack matches e',, the stack symbols popped by e. Finally, when an edge is traversed, the stack is also updated by popping el and pushing
By traversing Pcav during decoding and masking logits according to the outbound edges allowed by 4 and s, the LM is forced to generate token sequence that PGO accepts. Therefore, by Theorem the detokenized LM output must match the grammar G. At the same time, since Algorithm 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
C Speed measurement details
This section provides additional details about the experiments we ran to measure speed.
C.1 Outlines setup
Following the instructions the Outlines (Willard & Louf 2023) homepage, down- loaded and installed Outlines using the command pip install outlines. The specific version we received was Outlines v0.0.34.
17

---

Published as a conference paper at COLM 2024
We accessed the Gemma (Team et al. 2024 model via its integration into Outlines, ing the command outlines. aatlines.models models. transformers ("core-outlinn weiingggmmaa Note that for these experiments, the LM's parameter size does not matter because we are timing computations outside the LMM Only the vocabulary size matters, and the vocabulary is constant across Gemma sizes.
C.2 Constraint compilation
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 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, the trivial regex latency was 1/4 to 1/3 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 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.
C.2.1 Caching in Outlines
Recall that for each regex, we timed 10 runs and averaged the results to reduce noise. Outlines has a segex-to-indexed-FFe 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 the codebase, the only relevant cache this disables is the nngex-o-inndexd-FFe FSM cache.
cache, however, so naïvely the last 9 runs would be
As a sanity check, we also tried leaving caching on and instead appended a unique dummy character to the regex regex each run (e.g., /foo0/, /fool/ etc.). This effectively "disables" the regex-to-indexed -FM 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 coooloueee disable.caat (ebbhccccee))) does not cause 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.
C.3 Per-step overhead
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 domi- nated by noise in the LM computation-often yielding negative overhead measurements. Therefore, we measured the operations above in isolation from the LM.
C.4 Constraint regexes
Here, we describe the constraints used in the speed experiments.
18

---

Published as a conference paper at COLM 2024
C.4.1 Multiple choice
This matches a set of predefined texts:
/Red/Orange Yellow| Green [Blue] Indigo Violet/ Violee/
This example represents the simplest type of constraint that one might realistically want to apply. For example, this could be used for basic /No question answering, or classifica- tion tasks like /Sports Polliiiii Weather/.
C.4.2 ISO date-time
This matches an ISO 8601-style date time expression:
This example represents slightly more complex constraint, with non-trivial but relatively straightforward lattice structure.
C.4.3 IP address
This matches IPv4 address and is copied from the Outlines documentation
This example 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.
C.4.4 Quoted text
This matches double-quoted string like "foo". For system, the following extension-based regex:
/?P=<QUOTED_TEXT>>>
and for Outlines (Willard & Louf 2023), we use the following equivalent regex:
/"
I[\S"NNINN(''NN)>*
This example is intended to highlight the extensions presented in Section comparison in Sablee a clear advantage relative to the other constraints.
2.5 The
C.4.5 JSON object
This matches a JSON object that conforms to JSON schema (see Section 5.1p Both our system and Outlines have methods for converting a JSON schema into 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":
19

---

Published as a conference paper at COLM 2024
"type": "object",
"properties": {
"name": {"type": "string"), "durability": ("type": "integer"),
"quality": {
"type": "string",
"enum": ["Normal", "Magic", "Unique"]
This example represents a fairly complex constraint, as it involves enums, arrays, and nested sub-objects. However, commonly apply our system much more complex constraints.
D Correctness measurement details
We used Gemma TTam et al. 2024 zero-shot with the following prompt:
You will be given multiple choice question with different options such A, B, C, D. Think step by step before giving final answer to this question. Format your answer with the following JSON format which uses double quotes: jsson
{
"Final Answer": "x", "Solution": "step-by-step reasoning"
where X is the correct answer choice. If none of the options match, choose the closest option as the final answer.
20


Reviews:
[{"review_id": "11JBl9Xily", "reviewer": "Reviewer_wViX", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": true, "final_justification": "", "rebuttal": "Thank you for the review!\n\nWe believe our paper matches the selected areas: **inference algorithms** and **tools and code**.  Constraints are applied at inference time in the decoding loop, and can enforce formatting of tool API calls or code snippets. Our new experiment shows prompting alone can't guarantee proper format.\n\nBoth we and Outlines use regexes, but our use of automata theory is deeper and more general.  They handle detokenization with a **bespoke \"indexing\" algorithm**, whereas we reformulate detokenization as an FST.  Although the FST is simple, it crucially brings the **whole constraint problem** into the domain of automata, so we can apply **general algorithms** like composition instead of **bespoke algorithms** like Outlines.\n\nAs a result, our approach is more extensible.  For example, for CFGs Outlines' indexing algorithm **forbids** tokens from crossing (non)terminal boundaries (see footnote 3).  For us, FST-PDA composition is both **straightforward** and **more functional**, as it allows crossing.\n\nAs another example, arxiv.org/abs/2405.07671 proposed a DFA for \"correct\" BPE tokenization.  Handling BPE rules in Outlines likely **requires a rewrite** of their indexing algorithm.  For us, we simply convert that DFA into a detokenizing FST, compose it with the regex FSA, and we're done.\n\nAnother diff with Outlines is that we add extensions to optimize common expressions.\n\nThe reviewer mentions \"the requirements of building the FST for a particular language\" but we don't follow, **please clarify**.\n\nRegarding evals, we measured latency and quality.  We will add full results to the paper, summary below.\n\nLatency: We ran on Gemma tokenization, on the same workstation, averaging 10 runs.  Constraint compilation (regex => composed FSA) takes **100s of microseconds**, and overhead per decode step is **single-digit microseconds**.  Versus Outlines, we compile **7,000x-14,000x** faster and have **6x-25x** less step overhead.  These speedups enable applications that Outlines cannot support.\n\nQuality: We test the capability of output formatting with Gemma using [GPQA](https://arxiv.org/abs/2311.12022) by adding `\"\"\"Format your answer with the following JSON format which uses double quotes: ```json\\n{ \"Final Answer\": \"X\", \"Solution\": \"step-by-step reasoning\" }\\n```\"\"\"` to the preamble where X is one of the choices. Gemma2b and Gemma7b give **0.09** and **0.65** accuracy on schema-following without guided decoding and **1.0** with our constraints.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The presented work aims to improve the applicability of language models", "reasons_to_reject": "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. \nAuthors 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.", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VAPzIIeyPy", "reviewer": "Reviewer_CmqW", "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review!\n\nThanks for reading the paper so carefully and finding those issues, we will be sure to fix them in the paper.\n\nOne note on detokenization.  We agree that the current version is very simple, but our system generalizes to any tokenizer expressible as an FST.  For example, we recently saw arxiv.org/abs/2405.07671, which presents a construction for a DFA that represents \"correct\" BPE tokenizations.\n\nWe can easily convert their DFA into a detokenizing FST—just replace each token arc with a chain of `character_i:epsilon` arcs (`i` from `1` to `n-1`) followed by a `character_n:token` arc.  The rest of our system then works as-is, by composing a regex FSA or grammar PDA on top of that FST.\n\nWe would also like to highlight some experiments we ran on latency and quality.\n\nLatency: We ran on Gemma tokenization, on the same workstation, averaging 10 runs.  Constraint compilation (regex => composed FSA) takes **100s of microseconds**, and overhead per decode step is **single-digit microseconds**.  Versus Outlines, we compile **7,000x-14,000x** faster and have **6x-25x** less step overhead.  These speedups enable applications that Outlines cannot support.\n\nQuality: We test the capability of output formatting with Gemma using [GPQA](https://arxiv.org/abs/2311.12022) by adding `\"\"\"Format your answer with the following JSON format which uses double quotes: ```json\\n{ \"Final Answer\": \"X\", \"Solution\": \"step-by-step reasoning\" }\\n```\"\"\"` to the preamble where X is one of the choices. Gemma2b and Gemma7b give **0.09** and **0.65** accuracy on schema-following without guided decoding and **1.0** with our constraints.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The problem of constraining LM output to a given syntax is gaining increasing attention at time of writing. I like the formal approach of this draft, and I think the idea is original. The presentation is also very good. People will use this idea and cite this work.", "reasons_to_reject": "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_to_authors": "No question to the authors. What follows is a list of minor suggestions.\n\nYou 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. \n\npg.1,l.-7: separator > operator ?\n\npg.2: iff e_i^\\sigma = \\ep. > iff e_i^\\sigma = \\ep, for some i. \n\nthe following bib entry seems incomplete: 'Brandon T. Willard and Remi Louf. Efficient guided generation for large language models, 2023.'.", "extra_scores": {}}, {"review_id": "AWiyaHYHQm", "reviewer": "Reviewer_iNwk", "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.\n\nThe 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.\n\nThe 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.\n\nRegarding 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)?", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": true, "final_justification": "", "rebuttal": "Thank you for the review!\n\nWe have since run both latency and quality experiments.\n\nLatency: We ran on Gemma tokenization, on the same workstation, averaging 10 runs.  Constraint compilation (regex => composed FSA) takes **100s of microseconds**, and overhead per decode step is **single-digit microseconds**.  Versus Outlines, we compile **7,000x-14,000x** faster and have **6x-25x** less step overhead.  These speedups enable applications that Outlines cannot support.\n\nQuality: We test the capability of output formatting with Gemma using [GPQA](https://arxiv.org/abs/2311.12022) by adding `\"\"\"Format your answer with the following JSON format which uses double quotes: ```json\\n{ \"Final Answer\": \"X\", \"Solution\": \"step-by-step reasoning\" }\\n```\"\"\"` to the preamble where X is one of the choices. Gemma2b and Gemma7b give **0.09** and **0.65** accuracy on schema-following without guided decoding and **1.0** with our constraints.  \n\nWe will expand the related work section w.r.t. Outlines.\n\nAs the reviewer notes, the main difference is the detokenizing FST.  However, the FST itself is **not** the main value-add—the value comes from **expressing** detokenization as an FST.  This brings the **whole constraint problem** into the domain of automata, so we can apply **general algorithms** like composition instead of **bespoke algorithms** like \"indexing\" in Outlines.\n\nAs a result, our approach is more extensible.  For example, for CFGs Outlines' indexing algorithm **forbids** tokens from crossing (non)terminal boundaries (see footnote 3).  For us, FST-PDA composition is both **straightforward** and **more functional**, as it allows crossing.\n\nAs another example, arxiv.org/abs/2405.07671 proposed a DFA for \"correct\" BPE tokenization.  Handling BPE rules in Outlines likely **requires a rewrite** of their indexing algorithm.  For us, we simply convert that DFA into a detokenizing FST, compose it with the regex FSA, and we're done.\n\nIf you fully commit to automata as we have, the problem space **decomposes** nicely.  Any tokenizer expressible as an FST can be **swapped in**.  Any constraint expressible as an automaton can be **composed on top**.  Moreover, automata have been studied since the 1950s and have a **wealth of well-optimized algorithms**—note the stark latency comparison vs Outlines.\n\nAnother diff with Outlines is that we add extensions to optimize common expressions.\n\nFinally, we cannot provide full implementations, but will rewrite the algorithms in pseudo-code.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- new conceptual insights into efficiently constraining LLM output", "reasons_to_reject": "- lack of empirical validation\n\n- 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.)", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Uf42Mos1Cm", "reviewer": "Reviewer_mjW2", "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.\n\nI 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:\n\n- 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.\n\n- 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.\n\n- 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.\n\nI 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review!\n\nRegarding examples, there is a motivating example in the introduction that discusses the problems with tokenization.  We will sharpen or expand the example to make the issues clearer.\n\nSuppose that we have two APIs that can be called like so: `foo(123)` or `bar(456)`.  Now suppose each call has two possible tokenizations, with the following LM scores:\n\n| Score | Tokens |\n|---|---|\n| 0.4 | `fo o(1 2 3)` |\n| 0.3 | `bar ( 456 )` |\n| 0.2 | `foo ( 123 )` |\n| 0.1 | `ba r(4 5 6)` |\n\nTokens like `r(4` are painful to support in constraints, so we might naively **force** the tokenization to fit the formal syntax.  This simplifies the implementation but excludes the first and last rows.  Of the remaining rows, `bar(456)` is the best, but with full tokenization freedom `foo(123)` would win.  Thus, forcing tokenization **distorts** scoring.\n\nWe started with the naive approach long ago, but scoring distortions easily arise with data-driven LM tokenizers.  If you **don't** force the tokenization, however, you must deal with the mismatch between token boundaries and formal syntax—we solve this with automata.\n\nWe ran latency and quality evals.  Full results will be added to the paper, summary below.\n\nLatency: We ran on Gemma tokenization, on the same workstation, averaging 10 runs.  Constraint compilation (regex => composed FSA) takes **100s of microseconds**, and overhead per decode step is **single-digit microseconds**.  Versus Outlines, we compile **7,000x-14,000x** faster and have **6x-25x** less step overhead.  These speedups enable applications that Outlines cannot support.\n\nQuality: We test the capability of output formatting with Gemma using [GPQA](https://arxiv.org/abs/2311.12022) by adding `\"\"\"Format your answer with the following JSON format which uses double quotes: ```json\\n{ \"Final Answer\": \"X\", \"Solution\": \"step-by-step reasoning\" }\\n```\"\"\"` to the preamble where X is one of the choices. Gemma2b and Gemma7b give **0.09** and **0.65** accuracy on schema-following without guided decoding and **1.0** with our constraints.  \n\nOne qualitative difference from Outlines is that our approach is **modular**: any tokenizer expressible as an FST can be **composed** with any constraint expressible as an automaton.  The \"indexing\" algorithm used in Outlines is non-trivial to extend to either PDAs (with full tokenization freedom) or new tokenizing automata as in arxiv.org/abs/2405.07671.\n\nFinally, we will rewrite the algorithms in pseudo-code.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- The problem of LLM's output guidance is elegantly casted as a search process constrained by the composition of pairs of automata.\n\n- The proposed technique specifically addresses the problems introduced by tokenization steps when guiding the LLM output, which has not previously been done in the literature.", "reasons_to_reject": "- 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].\n\n- The paper does not include examples that would facilitate a better understanding of the problems being addressed.", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept