Earley-Driven Dynamic Pruning for Efficient Structured Decoding
Authors: Xintong Sun
Chi Wei
Minghao Tian
Shiwen Ni
Venue: ICML 2025 poster (2025)
Keywords: constrained decoding
structured generation
LLM inference
MLSys
Primary area: deep_learning->large_language_models
TL;DR: ZapFormat is a novel dynamic pruning algorithm to accelerate structured generation in LLMs.

Abstract: Large Language Models (LLMs) have shown remarkable capabilities, yet ensuring their outputs conform to strict structural or grammatical constraints remains challenging, which is critical in function calls and domain-specific language (DSL) generation. Constrained decoding with context-free grammar is a flexible approach to guarantee LLMs' adherence to a specific format by dynamically building a token logits mask. However, creating this mask requires checking the validity of all tokens in the LLM vocabulary at every decoding step, which often incurs significant overheads in existing constrained decoding engines. To address this challenge, we propose $\textbf{ZapFormat}$, a novel $\textbf{dynamic pruning}$ strategy based on the Earley algorithm that identifies and eliminates invalid or redundant Earley states in real-time, significantly reducing memory occupation of the Earley algorithm's states. This further enables us to use a state cache to speed up structured generations on a large number of queries. We implemented ZapFormat in a new constrained decoding engine called Formatron which also incorporates existing optimizations. Through comprehensive experiments on structured generation tasks, including JSON generation, JSON Schema validation, and semantic parsing, we demonstrate that Formatron not only $\textbf{consistently maintains}$ high-precision compliant outputs but also achieves $\textbf{significant improvements}$ in inference speed up to 2x compared to state-of-the-art implementations. More importantly, Formatron is generally applicable across various LLM architectures. We release Formatron as open source at https://github.com/Dan-wanna-M/formatron.

Earley-Driven Dynamic Pruning for Efficient Structured Decoding
Xintong Sun
Chi Wei
Minghao Tian' Shiwen Ni
Abstract
1. Introduction
Large Language Models (LLMS)) have shown remarkable capabilities, yet ensuring their out- puts conform to strict structural or grammatical constraints remains challenging, which is crit- ical in function calls and domain-specific lan- guage (DSL) generation. Constrained decoding with context-free grammar is a flexible approach to guarantee LLMs' adherence to a specific for- mat by dynamically building a token logits mask. However, creating this mask requires checking the validity of all tokens in the LLM vocabu- lary at every decoding step, which often incurs significant overheads in existing constrained de- coding engines. To address this challenge, we propose ZapFormat, a novel dynamic pruning strategy based on the Earley algorithm that iden- tifies and climinates invalid or redundant Earley states real-time, significantly reducing mem- ory occupation of the Earley algorithm's 's states. This further enables to use state cache to speed up structured generations on large num- ber of queries. We implemented ZapFormat in a new constrained decoding engine called Forma- tron which also incorporates existing optimiza- tions. Through comprehensive experiments on structured generation tasks, including JSON gen- eration, JSON Schema validation, and semantic parsing, we demonstrate that Formatron not only consistently maintains high-precisieg compliant outputs but also achieves significant improve- ments in inference speed up to 2x compared to state-of-the-arr implementations. More impor- tantly, Formatron is generally applicable across various LLM architectures. We release Formatron open source at https://ithub.commDDn waaaaubba.comaaaanaaaaaaaaaaaaaa wanna- M/formatron.
In recent years, Large Language Models (LLMs) have demonstrated remarkable progress, achieving breakthrough advances across multiple frontier domains including natural language processing (OpenAI & Sandhini Agarwal, 2024), code generation CCen et al., 2021; Wang et al., 2021), and robotic control (Liu et al., 2023; OpenAI, 2024). As their ap- plications continue to expand, a critical research challenge has emerged: how to guide models to generate text that precisely adheres to required grammatical and formatting specifications. In numerous practical applications, the struc- tural conformity of output text is paramount Beurrr-Kelllee et al., 2023; Lundberg et al., 2023). For instance, in func- tion calling or external tool interactions, systems typically require generated text to comply with specific parseable for- mats (e.g.. JSON). imposing heightened demands on LLMs (Shin et al., 2021; Roy et al., 2024; Fang et al., 2023).
Constrained decoding (Deutsch al., 2019; Kuchnik et al., 2023) is one of the prevalent technical approaches to tackle this challenge, which filters out tokens that violate grammat- ical requirements by screening the entire vocabulary at each decoding step, thereby ensuring model outputs conform to specified formal grammars. Among various constraint forms, context- grammar (CFG) (Chomsky, 1956) is regarded as a flexible and universal constraint format due its robust descriptive capabilities across multiple languages and structures. However, when applying these methods to large language models, several common challenges emerge:
1. Computational Overhead from Large Vocabularies and Complex Grammars. To ensure each newly decoded token correctly follows CFG rules, it is typically necessary to continuously assess the compatibility of all candidate tokens in the vocabulary and maintain the grammar parsing stack or state in real-time. For scenarios involving large vo- cabularies, long sequences, or complex grammars, this can lead to increases in computational and memory consumption (Geng et al., 2023; Beurer- Kelleer et al., 2024).
Eqqual contribution 'Department of Computer Science, Rice University, Texas, the United States "Shenzhen Institutes of Ad- vanced Technology, Chinese Academy of Sciences, Shenzhen, China. Correspondence to: Shiwen Ni <sw. www.ni@siat.. ac..cc.....c..
2. State Redundancy and Maintenance Complexity. De- coding requires storing and updating multiple parsing states, including information that may branch backtrack. When state quantities rapidly accumulate, the timely elimination of repetitive, invalid, or unused states becomes crucial (Willard & Louff, 2023). If not handled properly, these redundant
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Earley-Driven Dynamic Pruning for Efficient Structured Decoding
states can trigger cache misses, increase memory usage, and ultimately result in decreased inference speeds (Opedal et al., 2023).
Schema, and semantic parsing), it maintains high- precision output while achieving up 2x inference speed improvements.
We propose ZapFormat, a novel dynamic pruning strat- egy based on the Earley algorithm, which serves as the core component of our new constrained decoding engine Formatron. This approach identifies and eliminates invalid or redundant Earley states in real-time, significantly reduc- ing memory occupation. Formatron integrates ZapFormat with state-of-the-art optimizations to achieve both grammat- ical compliance and computational efficiency.
We demonstrate the universality of the Formatron en- gine, showcasing its broad applicability across various language model architectures, efficiently supporting structured generation tasks in both large-scale language models and task-specific applications.
2. Related Work
The key insight behind our approach is that during the pars- ing process, many intermediate parsing states become "ob- solete" or "dead" meaning they no longer contribute to finding valid parsing paths but continue consume mem- ory resources. Traditional parsing algorithms, including the widely-used Farley algorithm, tend to accumulate these unnecessary states throughout the decoding process, leading to memory bloat and reduced performance.
Constrained Decoding is method that ensures text gen- erated by Large Language Models (LLMs) conforms to specific formats or task requirements. Within the archi- tecture of LLMs, tokens serve as atomic processing units that mediate between raw text input and generated output. While each token represents a fixed-length character se- quence, this representation often fails to preserve linguistic integrity- either by splitting semantically coherent units, syntactically meaningful structures, or fragmenting multi- byte Unicode characters (Wang et al., 2020). For instance, as discussed in (Beurer- et al., 2024), a standard ISON string like "I am Van" might be tokenized into <" I am > and < Van" >, which disrupts both semantic and syntactic coherence. These tokenization limitations pose significant challenges for structured text generation tasks, especially in applications requiring strict syntactic compliance or fine- grained semantic control, such as output requirements for a valid JSON format. Prior work has addressed similar chal- lenges in semantic parsing (Xiao et al., 2016) and syntactic code generation (Yin & Neubig, 2017), demonstrating the importance of incorporating structural constraints during text generation.
Our core mechanism continuously tracks the utility of pars- ing states during decoding, allowing Formatron to swiftly identify and discard these dead states while maintaining only the states useful for parsing. For instance, consider parsing the input "aa" with the grammar (A + AB| B; B - a). In the baseline Earley parser, Earley Set 1 (after scanning the first 'a') retains four states: the completed (B + a 0), active items (A- + A); and (A + B); and the predicted (B + ea; However, the completed state (B -> a=; 0) becomes obsolete once subsequent parsing states (e.g., Earley Set 2's (A + AB 0)) no longer ref- erence its start position. Formatron's dynamic pruning removes such dead states immediately, reducing memory footprint and lowering overall state counts. This approach ensures that only relevant states propagate, streamlining the parsing process without compromising grammatical adher- ence.
Several works (Beurer- et al., 2023; Lundberg et al., 2023; Willard & Louf, 2023) use regular expressions for constrained decoding, but the approach's 's expressiveness is also limited to regular expressions, which excludes all formats that can only be described by CFG. These formats include json grammar, json schema, almost all programming languages, and more. To support full CFG, several studies (Scholak et al., 2021; Poesia et al.; Geng et al.) utilise parser and scanner running in parallel with the LLM, and then calculate online which tokens are valid continuations at each step. However, these approaches incur a relatively high inference overhead, and in the worst case, they must examine a nontrivial subset of vocabulary each step.
Experimental evaluations on structured generation tasks demonstrate Formatron's 's efficacy. Experimental results demonstrate that while meeting strict format output require- ments, this method effectively reduces memory usage and accelerates inference, providing an efficient and universal technical pathway for structured generation in large lan- guage models. Our contributions are as follows:
We propose a dynamic pruning method based on the Earley algorithm, which significantly reduces memory usage during inference and improves computational efficiency through real-time cleanup of invalid states.
Recently researchers have worked on achieving highly effec- tive and efficient constrained decoding. Beurer-Kellner et al. (2023) use precomputation, speculative decoding and oppor- tunistic masks to achieve minimally invasive and efficient constrained decoding. Koo et al. proposed an approach based on automata theory to provide an efficient closed
We design and implement a new constrained decod- ing engine, Formatron, integrating dynamic pruning with existing optimization techniques. Across multi- ple structured generation tasks (such as JSON, JSON
2

---

Earley-Driven Dynamic Pruning for Efficient Structured Decoding
form solution for regular languages. Recent work XGram- mar (Dong et al., 2024) significantly accelerates constrained decoding by classifying the tokens in the vocabulary into -oneext-indeeendentt and context- deeeexeeee tokens, which enables effective usage of precomputable adaptive context- independent token masks. To further accelcrate constrained decoding, our work investigates a dynamic pruning strategy for the Earley algorithm that is able identify and elim- inate invalid or redundant Earley states in real-time, thus significantly reducing the memory footprint of the Earley algorithm states. This further enables us to leverage Harley state caching to accelerate structured generation.
So: S - A B
Sei S - A + (0)
So: A a, (0)
So: - C, (0)
Scus "x"
S₁: A - (0)
Reject
S₁: S - A + B, (0)
3. Preliminaries
Scan
3.1. Context-Free Grammar
Sy: S - A + B, (0)
In computer science, Context-Free Grammar (CFG) repre- sents crucial grammar type commonly used to describe programming language syntax. To understand CFGs in- tuitively, think of them as a set of rules that define how to construct valid sentences or structures, similar to how grammatical rules in natural language define valid sentence constructions.
Sz: B - b, (2)
Sz: B (2)
San "5'
San
Reject
Sz: B d, (2)
Sy - A
A CFG consists of a set of rules (or productions), where each rule has non-terminal symbol on the left side and a sequence of terminal symbols and non-terminal symbols on the right side. Here, non-terminal symbols represent abstract structural components (like "noun phrase" " in lin- guistics), while terminal symbols are the actual characters or words that appear the final text. Each rule takes the form:
Figure I. Early parse. This diagram provides detailed illustration of the Earley parsing process for the input string 'a d' based on the grammar S + A + B, A + alc, B + bld. In the diagram, red arrows indicate Predict operations: yellow arrows represent Scan operations; and green arrows denote Complete operations.
A +
3.2. Earley's Algorithm
The Earley algorithm represents dynamic programming approach to parsing context-free grammars, notable for its linear time and space complexity for all LR(k) grammars (Leo, 1991), and its polynomial-time ((n²) parsing capabil- ity for ambiguous grammars. Unlike simpler parsing meth- ods that might get stuck or fail when encountering complex grammar structures, the Earley algorithm can handle any context-free grammar, making it particularly valuable for real-world applications where grammar complexity varies significantly. It not only avoids the exponential complex- ity that plagues many other parsing approaches but also maintains the capability to parse all context-free grammars.
Where A is a non-terminal symbol and a is a sequence com- posed of terminal and non-terminal symbols. For example, a simple addition grammar might have the following rule:
Expression + Expresssoo Term
Term
This grammar rule indicates that an expression can be com- posed of either another expression plus term, or simply term
In practical applications, CFGs serve as the backbone for parser design in compiler construction and natural language processing. Their formal nature provides a clear framework for analyzing and processing structured input, whether in programming languages natural language text. For con- strained text generation with large language models, CFGs act as blucprints that specify exactly what constitutes valid output, for instance, to ensure that generated JSON follows proper syntax or that code snippets comply with program- ming language rules.
The algorithm maintains a sequence of state sets S[0], S(I]. S[nn], where each set Sli] contains Earley items representing all valid partial parses position i in the input string. Think of these state sets as snapshots of all possible ways the parser could interpret the input up to each position-sine similar to how a human reader might consider multiple interpretations of a sentence while reading it word by word. Each Earley item within these sets takes the form
3

---

Earley-Driven Dynamic Pruning for Efficient Structured Decoding
(X B,j), where X ox9 is grammar rule with a and / being sequences of terminals and non-terminals, the
Out Token
dot (+) indicates the current parsing position within the rule and j indicates where in the input string this rule started being applied. The dot can be understood as a bookmark showing "we've successfully matched everything before this point, and we're looking for what comes after."
Token Mask
Prodict Logits
The algorithm parses the input string through three funda- mental operations:
LLM Inference
Grammar
The prediction operation handles states of the form (X -> e Y j) where Y is a non-terminal symbol; it adds all rules starting with Y to the current state set S(k),, where & the current position.
Figure 2. Constrained decoding. Constrained decoding can be achieved by masking the illegal tokens at the current step.
The scanning operation (X - a aB.j) where is terminal symbol: if matches the current input symbol, it
valid tokens can be sampled.
adds the state (X + aa maa.8,)) 3) to the next state set S(k + 1).
To illustrate, consider generating a JSON structure with simple CFG JSON -> "(" Pairlist ";", where Pairlist represents key-value pairs. During generation, after producing (', an Earley parser identifies that only ." (for starting a string) or ; (for empty objects) are valid next tokens. The constrained decoding step then masks all other tokens' logits to -o, restricting sampling to only these valid tokens. This ensures the generated text strictly adheres to the specified grammar.
The completion operation activates when encountering states where the dot has reached the end (X + )). where y represents the portion of the rule that has been fully matched up to this point; it finds all states in S(j) where the dot precedes X (like Y + a XB, i), and adds the advanced state (Y + aX (, to S(k). Importantly each state set maintains only unique states without duplicates.
Consider a simple grammar: S + AB, A - a, B + b processing the input "ab" with the start rule S + AAB Through prediction, it adds A + aa Upon scanning 'a', creates A + a in S[1]. leading to S + A B. The process continues until reaching S AB in the final state set, confirming successful parse. This simple example demonstrates how the algorithm systematically explores parsing possibilities: it predicts what could come next, scans to match actual input, and completes patterns when they 're fully recognized.
4. Formatron
4.1. Motivation
Although the Earley algorithm can parse any context-free grammar and possesses theoretical universality, it often en- counters significant memory and computational overhead in practical applications. When the input length is n. the Earley parser constructs a set S[i] at each position i (from 0 to n.). For scenarios involving large inputs or numerous grammar rules, this scale often leads to excessive memory consumption.
3.3. LLM Constrained Decoding
Large Language Models (LLMs) like GPT-4, Llama, and Mistral generate text in an auto-regressive manner: at each step, the model predicts the next token based on previously generated tokens (or input prompt). Specifically, the model outputs a logits vector over its vocabulary, which is con- verted into probability distribution through the softmax function for token sampling.
Furthermore, to perform backtracking and check expandabil- ity during the Complete steps, the parser typically retains all previous sets. However, in many cases, certain sets or items become obsolete in subsequent steps: for instance, when parsing JSON objects, once a key-value pair has been fully recognized, there is no need to continue tracking its associated states. Similarly, terminals are often defined using regular expressions and implemented as finite state machines (FSM) for matching; once a terminal's 's match is completed, the corresponding FSM instance has fulfilled its recognition purpose, and retaining it further only unnec- essarily occupies memory resources. In modern computer architectures, these "dead" or "idle" states result in numer- ous ineffective accesses, increasing the probability of cache misses, thereby slowing down program execution. More
When generating text that must conform to specific syntactic structures or formats (e.g., JSON, SQL queries, or templated text), directly sampling from the model's probability distri- bution alone may not guarantee valid outputs. Constrained decoding addresses this challenge by applying logits mask before token sampling. This process sets the logits of in- valid tokens that violate output formats to -o0, effectively zeroing their probabilities after softmax, ensuring only

---

Earley-Driven Dynamic Pruning for Efficient Structured Decoding
formally, we can define the rules that can create such "dead" states in parser High-level Regular Rule(HRR) in CFG: let the rule's s LHS symbol be A. then the rule is HRR if the rule satisfies one of the following forms:
rally arise from the Earley algorithm's operations: Predict, Scan, and Complete.
Predict Dependency. When an item p = (A + a B3, i.j) triggers the prediction of all rules B + in the grammar, each new predict item & = (B + * 7 J. j) is said to depend on p. We then say Dpred
(A-GA- Ba, A + }
B
where A, B are non-terminal symbols, B is not ambiguous, are terminal symbols and denotes the empty string. Intuitively, HRR creates "dead" states because after c, e, B are parsed, we technically no longer need to record the states before or during c, e or I3s parsing, while existing parsing algorithms retain them by default.
7 E p and p = (A- a B,,
Scan Dependency. A SCAN operation moves the dot past a terminal symbol that matches the current input token. If the next input token is a and we have an item p (A - aB, i,j), then scanning yields g = (A + a 3, + 1). We then say: Dscau(q:7) P) - impurlj] = a and p (A + a aB, 1.
When the Farley algorithm is employed for constrained de- coding in conjunction with large language models (LLMs), the aforementioned issues become even more severe. Un- like traditional Earley algorithm processing a static input sequence "left-to-right", constrained decoding needs to pro- cess all tokens in the vocabulary along with already gen- erated tokens so that we can construct logits mask at each decoding step to filter out candidate tokens that vio- late syntactie constraints. This requires the Earley parser to real-time update and return viable tokens after each LLM decoding step: however, if the parser retains numerous irrel- evant states or sets and fails to promptly clean up "dead" or "idle" Earley items, it slows down the decoding process.
Complete Dependency. The completion operation occurs when we have fully parsed nonterminal symbol in the grammar. Specifically, when an item has its dot at the end, indicating complete derivation of nonterminal B, it can be used to advance all items whose postdot nonterminal is its left hand side. Suppose p = (B + ,,k,j) 9 = (A + a B,3, i, k), and we form the new item r (A +
a B B) We then say Dcomp pT, 4 p
B + 7 j, and q = (A + i)),
4.2.2. DEPENDENCY GRAPH
To address this, we propose a dynamic pruning strategy that aims to minimize redundant storage and repeated com- putations of ineffective sets while preserving the theoretical completeness of the Earley algorithm. In simple terms, this strategy "online" tracks which sets and states may still be referenced in subsequent steps during the parsing process, and promptly discard items that no longer contribute, sig- nificantly reducing memory usage and accelerating parsing speed.
To efficiently track these dependencies, we construct a di- rected graph
G= G=(VE)),
where each vertex v E V corresponds to an Earley item, and each directed edge (Ir, E E. indicates that y depends on x. This graph is maintained dynamically as new items are created.
The dependency graph construction process operates on Earley item sets, maintaining vertices V and edges E to track parsing dependencies. When the parser begins, V is empty and grows as new items are discovered. For each item creation through PREDICT, SCAN, or COMPLETE op- erations, corresponding edges are inserted to record depen- dencies from source items. The graph updates dynamically as new Farley item sets (So, .I....) are formed, ensuring comprehensive dependency tracking throughout the parsing process.
4.2. ZapFormat
This section introduces ZapFormat, a novel method for track- ing dependencies among Earley items (Earley, 1970) and applying reachability- pruning strategy in real time. By maintaining a dependency graph, we can effectively remove items that will not contribute to any valid parse, thereby reducing the overall number of states.
4.2.1. DEPENDENCIES
4.2.3. REACHABILITY AND DYNAMIC PRUNING
To enable more effective tracking of parsing progress and dependencies, we extend the traditional Earley item nota- tion to (A + B, j. in this enhanced representation, (A - 3) denotes production rule from the grammar, while the span [i, precisely captures a's coverage of the input sequence from position i up to (but not including) j. Based on the extended representation, we proceed to define dependencies. Three types of inter-item dependencies natu-
For effective pruning, we first define the reachability closure. Note that PREDICT, SCAN, and COMPLETE operations all starts by checking items in the lastly created Earley set. Intuitively, this means the reachability of an item can be defined as whether the item depends on any item in the last set. More formally, given an item in an Earley set, we determine which items should be retained through the following definitions:
5

---

Earley-Driver Dynamic Pruning for Efficient Structured Decoding
dynamic pruning approach not only provides theoretical completeness guarantees but also demonstrates superior per- formance optimization in practice.
$
S2
Grammar:
A - AB|B B - 'a' Input: "a"
AB,
B ''' (0)
"
A (0) B - a.. (0)
A - B (0) A A (0) B (1)
A AB- (
4.3. Context-independent Tokens Mask Cache
A A R. (0)
a5 (2)
Inspired by XGrammar's (Dong et al., 2024) context- independent token mask cache, we use a token mask cache method to enhance decoding efficiency in our constrained decoding engine. The core of token mask cache mechanism categorizes tokens into two types: Lontext-Indeeendent tokens, whose validity can be determined by examining postdot terminals of items in the last Earley set, and Context- Dependent tokens, which require full parsing context. The token mask cache accelerates the parsing process by pre- computing valid and invalid context-indepente each terminal, which are then efficiently stored as bitsets. Note that unlike XGrammar, we do not consider the pos- sible suffix strings of terminals when determining invalid context-independee tokens to save precomputation time. At runtime, the valid and invalid context- mnneext-indeeendent tokens are retrieved directly from the cache, eliminating redundant computations and thus reducing the overall decoding time.
Figure 3. Dynamic pruning. Red parts indicate prunable nodes, and green dashed lines represent Complete dependency paths. First,already completed Earley items only lead to modifications on their residing Earley set. Once their residing Earley set is fully processed, we can remove them. In addition, after one Earley set fully processed, if Farley set is referenced by the union of reference chains of all items in the last Earley set, then it can be removed.
tokens for
Reachability Closure: For each item a E V, if there exists a path from x to an item a in the last earley set, we consider this item "reachable". Formally, we define the reachability closure as:
Reach(a) = {x E V x ---aaa a},
In scenarios where multiple postdot terminals exist, the token masks from each terminal are merged into a single final token mask. By reducing the number of computations required for token validation through leveraging precom- pution, the adaptive token mask cache significantly speeds up the decoding process.
where +* denotes a directed path (potentially multi-step)
from a.
Active Item Set: We define the active item set R as the union of all reachable items:
R = U Reach(a).
4.4. Rejection Prefix Optimization
aEV
We introduce prefix-based early rejection mechanism that enhances parsing efficiency by identifying grammatically impossible input paths at the earliest stage of the parsing process. The optimization maintains a set of "rejected pre- fixes" - minimal byte sequences that definitively preclude valid parses regardless of subsequent input extensions. These prefxxe represent fundamental grammatical viola- tions that cannot be completion. The optimization operates by maintaining and continuously updating these sequences that, when encountered during parsing, immediately indi- cate the impossibility of a valid parse.
Only items within this active set need to be retained.
We enhance the original Earley parsing algorithm by intro- ducing a compact operation after the complete phase and before prediction phase, evaluating each item's 's retention necessity. This phase ordering eliminates useless computa- tions on newly predicted items which always only depend the items before prediction in the last set). Specifically, the Compact operation examines all items in the current set, eliminating those that do not belong to the active item set R.
To ensure both correctness and efficiency of the pruning op- erations, we implement an incremental update strategy. The active item set is updated after each parsing phase, particu- larly following the completion and compaction phases. This dynamic maintenance strategy ensures that pruning opera- tions remain responsive parsing state changes, avoid re- searching the whole V repeatedly, and maintain algorithmic correctness. By combining forward reachability analysis with dynamic pruning, our algorithm significantly reduces the number of items requiring processing while preserv- ing parsing correctness. This forward reachability-
For instance, in a context- free grammar (CFG), if the pre- fix "aaac" " constitutes rejected prefix according to the grammar rules. Once this sequence is detected (e.g., in input "aaacde f frf"), no grammatical derivation can produce valid parse trees for any extension of this prefix, regardless of subsequent characters.
When a rejected prefix is detected, the parser can safely discard all extensions of that prefix without state exploration. This set is updated whenever a token is rejected at each decoding step.
6

---

Earley-Driven Dynamic Pruning for Efficient Structured Decoding
4.5. Grammar Transformation
ing to fixed predicates and finite entity constraints. JSON Schema (Pezoa et al., 2016) generation produces JSON instances compliant with type, enumeration, and regular expression constraints. JSON Grammar generation creates syntactically valid and semantically coherent nested JSON structures with cross-field dependencies. Data examples are shown in Appendix D.
To optimize constrained decoding efficiency, we use grammar transformation framework (Hoperoft & Ullman, 1979;;b). The primary transformation step involves struc- tural optimization, where we identify and eliminate useless rules that cannot contribute to valid derivations, thereby reducing the grammar size without affecting its expressive- ness. This is particularly helpful for grammar generated from a high-level format like json schema, where the gener- ator, potentially built by third parties, may fail to remove all unreferenced rules.
Evaluation Metries. Throughput represents a fundamen- tal metric in the assessment of LLM constrained decoding performance, defined as the ratio of constraint-satisfyl to- kens generated to temporal duration, expressed in tokens per second (Token/s). This measurement provides insights into computational efficiency and resource utilization efficacy.
Another crucial optimization addresses null rules. We systematically handle rules that can derive empty strings through a three-phase approach: first identifying all null symbols, then generating alternative productions, and fi- nally selectively retaining specific null productions where necessary. This transformation substantially reduces the branching factor during parsing.
5.2. Experimental Results
We conducted a comprehensive evaluation of the forma- tron engine across four mainstream large language models. Table presents a performance comparison of different ap- proaches under various constraint types:
5. Results
Performance Advantage Analysis. The experimental re- sults robustly validate the efficacy of formatron. In most tested scenarios, formatron achieved significant perfor- mance improvements compared to baseline methods. These enhancements can be attributed to formatron's core inno- vation: dynamically pruning invalid or redundant Earley states, substantially reducing memory consumption during constraint parsing. Coupled with an efficient caching mech- anism, formatron consistently maintains high-throughput output. These empirical data comprehensively demonstrate formatron's 's performance superiority in constrained decod- ing tasks.
5.1. Experimental Setup
All experiments were conducted on a system equipped with an NVIDIA GeForce RTX 3090 (24GB VRAM) and an AMD EPYC 7452 32-core processor. The soft- ware environment consisted of PyTorch 2.4.0 and CUDA 12.4, with model inference performed using Transformers 44.4..0. Four pre-trained large language models were em- ployed in this study: google/gemma-229b-it (Gemma Team & Shreya Pathak, 2024), meta-llama//Llmmm3 I-Isrruct (Dubey et al., 2024), misttalai/Mistrra--BBBSnssee (Jiang et al., 2023), and qwenn/Qwen2.5-77--nnmm et al., 2024), all utilizing half- half-precision (FP16) inference. For more details of Python libraries, see the appendix A.
(Yang
Robustness Analysis. In terms of model robustness, for- matron exhibits exceptional cross-architectural adaptability. By testing across models with different scales and architec- tures, formatron consistently maintains stable performance, verifying its characteristic of being generally applicable across various LLM architectures. From 9B to 7B model scales, formatron demonstrates consistent high-efficiency performance.
Baselines. in-forrmateefooreer (v0.10.9) (Jiang et al., 2024) implements incremental validation based on syntax tree pre-computation, suitable for structured constraints but with significant memory overhead. outlines (v3.1.13) (Willard & Louf, 2023) employs finite state machines for dynamic masking of invalid tokens, excelling in regular constraints but not directly applicable to context-free gram- mars. One significant consequence of this limitation is that they can only support a small subset of json schemas (dottxt-ai/ouliines contributors, 2023). XGrammar 100.1.10) (Dong et al., 2024) supports Context-Free Grammars (CFG) through simulating pushdown automata with tree-structured stacks, offering high versatility but introducing parsing la- tency. It also cannot directly handle left-recursive CFGs (mlc-ai/ggrammar contributors, 2024).
Regarding task robustness, formatron excels in diverse con- strained decoding tasks. From JSON generation to JSON Schema validation and semantic parsing, formatron con- sistently produces high-precision compliant outputs. This cross-task stability comprehensively substantiates the reli- ability and generalizability of the formatron technical ap- proach.
Comparative Method Analysis. Formatron possesses ad- vantages compared to existing methods. While outlines only supports regular grammars through finite state automata, formatron manages to support full context-free grammar with Earley algorithm and achieves superior performance
Test Task. Geoquery (Davis& & Meltzer, 2007) transforma- tion converts natural language queries into FunQL, adher-
7

---

Earley-Driven Dynamic Pruning for Efficient Structured Decoding
Table Commprattiv Throughput Performance of Different Meth- ods in Constraint Parsing Tasks (tokens/s). Here, '-' indicates that the method not applicable to task, and bold indicates the best result. All experimental results were obtained in the same local environment, Im-format represents im-format-enforeer Json_s represents SionSShhamm and Json.g represents Json.Gramme Grammar.
Table 2. Throughput Comparison of Different Models and Meth- ods Across Multiple Runs. enforcer.
Im-format represents Im-format-
Number of Runs
Model Method
run
3 run
5 run
10 run
Model Method
geoquery
json_s
json-g
Im-format
60.08
63.48
66.15
75.84
Gemma
Outlines
61.62
61.66
62.00
62.13
Im-format
60.08
22.95
Gemma
Xgrammar
1473.99
1577.05
1564.97
1551.51
Outlines
61.32
Formatron
7943.34
10609.08
11323.63
11993.89
Xgrammar
616.66
1473,99
10245.04
Formatron
12174.68
7943.34
8668.69
Im-format
120.56
121.51
139.99
159.34
Llama3
Outlines
114.10
104.71
105.13
103.44
Im-format
120.56
47.79
Llama3
Xgrammar
2796.36
2533.45
2578.91
2629.54
Outlines
114.10
Formatron
8207.85
10271.73
11018.91
11945.94
Xgrammar
2758.98
2796.36
7757.15
Formatron
6700.87
8207.85
8535.64
Im-format 576.11
723.72
794.30
796.68
Qwen Mistral
Outlines
598.98
634.63
649.78
641.22
Im-format
576.11
372.55
Mistral
Outlines
598.98
Xgrammar
8421.43
7673.90
7699.77
7885.20
Formatron
10639.87
13522.77
13841.85
14424.69
Xgrammar
5926.64
8.21.43
15273.72
Formatron
11703.00
10639.87
12046.54
Im-format
45.31
41.89
46.65
49.47
Outlines
112.10
89.82
90.13
90.22
Im-format
45.31
21.26
Xgrammar
2037.26
2247.04
2299.04
2284.37
Qwen
Outlines
112.10
Formatron
9234.08
10537.26
11397.31
12202.48
Xgrammar 1725.86
2037.26
7290.30
Formatron
6399.68
9234.08
9811.02
5.3. Multiple Runs
To mitigate the impact of random factors, we conducted multiple runs of experiments on Schema. To con- duct multiple runs, we utilized LLM for data augmentation. For further details, please refer to the appendix E. The ex- perimental results (shown in Table 2) demonstrate that our proposed Formatron method significantly outperforms ex- isting baseline approaches in terms of throughput. Through systematic evaluation across different numbers of runs, we observed several key trends:
over outlines regular grammars. Unlike Informaten- forcer's naive input token prefix cache, formatron's 's state cache with dynamic pruning greatly increases cache hit rate and decreases memory occupation, since multiple different input token sequences can correspond the same pruned Earley states. Notably, XGrammar, developed concurrently with our work (published within three months of our paper submission), represents contemporary approach in this do- main. By combining our novel algorithm with optimizations proposed by XGrammar, formatron achieves competitive performance across most tasks, with XGrammar showing superior performance certain specific scenarios (e.g.. geo- query Gemma and Json_s Mistral), while formatron excels in the majority of other tasks without incurring more precomputation costs. These advantages substantially en- hance formatron's 's processing efficiency in constrained de- coding tasks.
First, Formatron exhibits remarkable performance advan- tages in single-run scenarios. Across all tested models, For- matron achieves substantially higher throughput compared to baseline methods, with particularly notable advantages in the Mistral and Qwen models. This performance enhance- ment can be primarily attributed to Formatron's 's dynamic pruning mechanism, which effectively reduces redundant operations in computation paths.
To further validate the effectiveness and reliability our proposed method, we conducted two additional experiments addressing potential concerns about our evaluation method- ology. First, performed a comprehensive analysis of whole pipeline component performance. Second, we eval- uated output quality using accuracy metrics to ensure that our efficiency gains do not come at the expense of gener- ation quality. The detailed results of these supplementary experiments are presented in Appendix B.
Furthermore, in multi-run scenarios, we observed an inter- esting performance evolution pattern. Formatron demon- strates progressive throughput improvement as the number of runs increases, showing consistent performance gains from three runs to five and ten runs. In contrast, baseline methods show limited improvement in multi-run scenarios, exhibiting stability but lacking breakthrough performance. This phenomenon demonstrates Formatron's 's performance stability and robustness across extended operations.
8

---

Earley-Driven Dynamic Pruning for Efficient Structured Decoding
Table Experimental results of ablation. Here, "&& cache" in- dicates the ablation of the cache in addition to the ablation of pruning.
Table 4. Maximum memory usage comparison during constrained decoding. Model
Method
Max Memory Usage (MB)
Number of runs
Formatron
1635.92
LLM
Method
Llama3
w/o pruning
1655.
3 run
5 run
10 run
Formatron
1519.09
Gemma
Formatron
10609.08
11323.63
11993.89
Mistral
w/o pruning
1530.77
-pruning
698 1.35
6628.69
7674.78
& cache
3595.48
3038.70
3365.96
Llama3
Formatron
10271.73
11018.91
11945.94
-pruning
6269.24
7064.69
7619.57
The proposed ZapFormat algorithm based on the identifi- cations of HRR in CFG, which reduces memory usage via dynamic Earley state pruning based on dependency reacha- bility analysis; (2) A hybrid optimization framework com- bining grammar- token masking with prefix rejection. Evaluations across JSON generation and semantic parsing tasks demonstrate consistent performance improvements while maintaining 100% structural compliance, establish- ing new efficiency benchmarks for grammar-guide LLM decoding.
-& cache
3464.36
3438.40
3445.73
Formatron
13522.77
13841.85
14424.69
mistral
-pruning
9727.00
9824.90
9707.45
-& cache
8845.90
8204.43
7669.42
Formatron
10537.26
11397.31
12202.48
qwen
-pruning
8635.20
9476.70
10048.19
& cache
4189.57
4180.18
4196.09
Acknowledgements
5.4. Ablation Study
Shiwen Ni was supported by GuangDong Basic and Ap- plied Basic Research Foundation (2023A1515110715 and 2024A China Postdoctoral Science Founda- tion (2024M153398)) Postdoctoral Fellowship Program of CPSF (GZC20232873) and Shenzhen Major Science and Technology Project (KCXF72004000339400000))
To investigate the contribution of each component in Forma- tron, conducted ablation experiments by removing the pruning and caching mechanisms. Table 5.4 presents the results across different models and run configurations.
The ablation study reveals that removing the pruning mech- anism (-pruning) results in significant performance degrada- tion, with throughput reductions of 30-50% for most models, demonstrating its crucial role in optimization. The further removal of caching (-& cache) generally leads to additional performance deterioration.
Impact Statement
This study introduces methodological improvements for constrained decoding in large language models, with partic- ular emphasis on computational efficiency gains for struc- tured text generation tasks. Our approach enhances the reliable generation of grammatically valid outputs in practi- cal applications ranging from automated API call generation to standardized data formatting. The proposed techniques raise ethical considerations common language model technologies, particularly regarding their potential deploy- ment in automated decision makinn systems. While the improved efficiency may expand access to structured gener- ation tools across various sectors, appropriate safeguards are still necessary to mitigate risks associated with uncontrolled automation. important to note that the main techni- cal udvancc-refining grammatical constraint enforcement mechanisms does not introduce novel ethical concerns be- yond those already present in conventional language model applications. Researchers and practitioners adopting these methods should maintain established responsible innova- tion practices, including rigorous output verification and maintenance of human oversight protocols.
In addition, even with both pruning and caching ablated, our method still outperforms several baselines, demonstrat- ing the substantial contributions of other optimizations dis- cussed earlier, including prefix rejection and grammar trans- formation.
On the other hand, in order to validate our claims regarding memory reduction, we conducted additional experiments measuring the maximum memory usage (in MB) during constrained decoding (Table 4). The results show that our pruning mechanism reduces memory consumption. These results confirm that our approach successfully reduces mem- ory footprint by eliminating redundant Earley states.
6. Conclusion
We present Formatron, an efficient LLM constrained decod- ing engine that achieves 1.5-2x speedup over state-of-the-an art method. Our Formatron contains two core innovations: (1)

---

Earley-Driven Dynamic Pruning for Efficient Structured Decoding
References
Earley, An efficient context-free parsing algorithm. Com-
mun. ACM, 13(2):94-102, February 1970. ISSN 0001- 0782. doi: 10. 10.1145732207:362005 URL https: //doi.
Beurer-Kellnet, L., Fischer, M., and Vechev, M. Prompting is programming: A query language for large language models. Proceedings the the ACM on Programming Lan- guages, 7(PLD1)):944-1966 2023.
362035.
Fang, H., Balakrishnan, A., Jhamtani, H., Bufe, J., Craw- ford, J., Krishnamurthy, J., Pauls, A., Eisner, J., An- dreas, J., and Klein. D. The whole truth and noth- ing but the truth: Faithful and controllable dialogue re- sponse generation with dataflow transduction and con- strained decoding. In Rogers, A., Boyd- J., and Okazaki, N. (eds.), Findings of the Association for Computational Linguistics: ACL 2023, pp- 5682-5700, Toronto, Canada, July 2023. Association for Computa- tional Linguistics. doi: 10. 10.18653/11220333.mmmmm 351. URL https: / /a//acaaaaaa www.aatwwwwoo....o.o.oooooo 2023. E LEndings-acl. 351/
Beurer- Kellee,, L., Fischer, M., and Vechev, M. Guiding Ilms the right way: fast, non-invasive constrained genera- tion. In Proceedings of the 41st International Conference on Machine Learning, ICML'24. JMLR.org, 2024.
Chen, M., Tworek, J., Jun, H., Yuan, Q. Pondé, H., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., Ray, A., Puri, R., Krueger, G., Petrov, M., Khlaaf, H., Sastry, G., Mishkin, P. Chan, B., Gray, S., Ryder, N., Pavlov, M., Power, A., Kaiser, L.,, Bavarian, M., Winter, C., Tillet, P. Such, F. P., Cummings, D. W., Plappert, M., Chantzis, F., Barnes, E., Herbert-Voss, A., Guss, W. H., Nichol, A., Babuschkin, I., Balaji, S., Jain, S., Carr, A., Leike, J., Achiam, J., Misra, V., Morikawa, E., Radford, A., Knight, M. M., Brundage, M., Murati, M., Mayer, K., Welinder, P., McGrew, B., Amodei, D., McCandlish, S., Sutskever, I., and Zaremba, W. Evaluating large lan- guage models trained on code. ArXiv, awwpaabsssa.aaoo abs/2117..0337, 2021. URL https: http::::///pp.ssanniiiiccsss.s www.nticscoools.........occtc http/CooppsII::2555555
Gemma Team, M. R. and Shreya Pathak, e. Gemma 2: Improving open language models at practical size, 2024. URL www.h:tpps/.ooo /ttp///axxvvvv.vv org.ii.orrrraaeeeeo. haag///b///// / 248. 88 00118. 8.
Geng, S., Josifoski, M., Peyrard, M., and West, R. Grammar- constrained decoding for structured nip tasks without fine- tuning. In The 2023 Conference on Empirical Methods in Natural Language Processing.
Geng, S., Josifoski, M., Peyrard, M., and West, R. Grammar- constrained decoding for structured NLP tasks without finetuning. In Bouamor, H., Pino, J., and Bali, K. (eds.), Proceedings of the 2023 Conference on Empirical Meth- ods in Natural Language Processing, pp. 10932-10952, Singapore, December 2023. Association for Computa- tional Linguistics. doi: 10.18653/ 674. URL https: https///acaaatthhhc org/ emn 1p 1pmmap-mm n. 674/.
Chomsky, N. Three models for the description of language. IRE Transactions on information theory, 2(3): 13-124, 1956.
Davis, S. and Meltzer, P. S. Geoquery: a bridge between the gene expression omnibus (geo) and bioconductor. Bioin- formatics, 23(14):1846-1888 2007.
Hopcroft, J. E. and Ullman, J. Introduction to Automata Theory, Languages, and Computation. Aldison-Wesley 1st edition, 1979a. remove useless rules.
Deutsch, D., Upadhyay, S., and Roth, D. A general- general-purpose purpose algorithm for constrained sequential inference. In Pro- ceedings of the 23rd Conference on Computational Natu- ral Language Learning (CoNLL), pp. 482 492, 2019.
Hopcroft, J. E. and Ullman, J. Introduction to Automata Theory, Languages, and Computation. addison-Wesley, 1st edition, 1979b. remove nullable rules.
Dong, Y., Ruan, C. F., Cai, Y., Lai, R., Xu, Z., Zhao, Y., and Chen, T. Xgrammar: Flexible and efficient struc- tured generation engine for large language models. arXiv preprint arXiv:2411. 1,55000, 2024.
Jiang, A. Q., Sablayrolles, A., Mensch, A., Bamford, C., Chaplot, D. S., Casas, D. d. L., Bressand, F,, Lengyel, G., Lample, G., Saulnier, L., et al. Mistral 7b. arXiv preprint arXiv:2310006825, 2023.
dottxt-ai/outlins contributors. schema field constraints
Implement json 215, August 2023.
Jiang, X., Li, X., Ma, W., Fang, X., Yao, Y., Yu, N., Meng, X., Han, P., Li, J., Sun, A., et al. Sketch: A toolkit for streamlining IIm operations. arXiv preprint M:Xiv:2409.03346 2024.
URL https://githut com/ com//ootxt:.. ai/ outlines/issues/
Accessed: [2025-01-15]
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., et al. The Ilama herd of models. arXiv preprint arXiv:2407.2778 2024.
Koo, T., Liu, F., and He, L. Automata based constraints for language model decoding. In First Conference on Language Modeling.
10

---

Earley-Driven Dynamic Pruning for Efficient Structured Decoding
Kuchnik, M., Smith, V., and Amvrosiadis, G. Validating large language models with relm. Proceedings of Ma- chine Learning and Systems, 5:457-476, 2023.
Poesia, G., Polozov, A., Le, V., Tiwari, A., Soares, G., Meek, C., and Gulwani, S. Synchromesh: Reliable code genera- tion from pre-trained language models. In International Conference on Learning Representations.
Langley, P. Crafting papers on machine learning. In Langley, P. (ed.), Proceedings of the 17th International Conference on Machine Learning (ICML 2000), pp. 1207-1216, Stan- ford, 2000. Morgan Kaufmann.
Roy, S., Thomson, S., Chen, T., Shin, R., Pauls, A., Eisner, J., and Van Durme, B. Benchclamp: A benchmark for evaluating language models on syntactic and semantic parsing. Advances in Neural Information Processing Systems, 36, 2024.
Leo, J. M. A general context-free parsing algorithm running in linear time on every Ir(k) grammar without using lookahead. Theoretical Computer Science, 82(1):165-117, 1991. ISSN 0304-3975. doi: http:///o..oo////.00000004449919
Scholak, T., Schucher, N., and Bahdanau, D. Picard: Pars- ing incremenially for constrained auto-regressive decod- ing from language models. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, Pp. 9895-9901, 2021.
URL httpsss/www.scceeceeediiee com/ science/articlle//i/////ss//////
Liu, B., Jiang, Y., Zhang. X., Liu, Q. Zhang, S., Biswas, J., and Stone, P. Lim+p: Empowering large language models with optimal planning proficiency. arXiv preprinl arXiv:2304.11477, 2023.
Shin, R., Lin, C.,, Thomson, S., Chen, C.,, Roy, S., Platanios, E. A., Pauls, A., Klein, D., Eisner, J., and Van Durme, B. Constrained language models yield fhw-shot seman- tic parsers. In Moens, M.-F,, Huang, X., Specia, L., and Yih, S. W.-t. (eds.), Proceedings of the 2021 Con- ference on Empirical Methods in Natural Language Pro- cessing, pp. 7699-7715, Online and Punta Cana, Domini- can Republic, November 2021. Association for Computa- tional Linguistics. doi: 10.18653/v 1/222551/122222mmmmmm main. 608. URL https: https///aaaattthhoo hwwphhhhwlg.oo.oggg.eeeee 2021. emnlp main. 608/.
L Lundberg, S., Ribeiro, M. T. C., et al. Guidance-ai/guidancee A guidance language for controlling large language mod- els. URL https://github. pengguddance-aiguidann 2023.
mlc-ai/xgrammar contributors. Support left recursive gram- mars. currently going into infinite loop 126, Decem- ber 2024. URL https: /ts////tttt /ggtttu...... com m1 mma/cclcccaaaaam xgrammar issussssssssisee /226. Accessed: [205-01-15].
Opedal, A., Zmigrod, R., Vieira, T., Cotterell, R., and Eis- ner, Efficient semiring-weighted Earley parsing. In Rogers, A., Boyd-Graber, J., and Okazaki, N. (eds.), Pro- ceedings of the 61 Annual Meeting of the Association for Computational Linguistics ( (Volume 1: Long Papers), pp. 3687-3713, Toronto, Canada, July 2023, Associa- tion for Computational Linguistics. doi: 10.18653/v1/ 2023.acl-1ong.204, URL arg/2023.ac111200 1ong..on.22200 204/.
Wang. C., Cho, K., and Gu, J. Neural machine translation with byte-level subwords. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 9154 9160, 2020.
Wang. Y., Wang, W., Joty, S., and Hoi, S. C. CodeT5: Identifier-aware unified pre-trained encoder-decoder models for code understanding and generation. In Moens, M.-F. Huang, X., Specia, L.,, and Yih, S. W.-t. (eds.), Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 8696-8708, Online and Punta Cana, Dominican Republic, November 2021. Association for Computa- tional Linguistics. doi: 10. 10.18665/11/22221mmll--maa 685. URL tittps:/accaanthc..o. emnlp main. 685/.
OpenAI. Function calling- OpenAl API, 2024. URL muiies/functiion-co 2024].
openai. aepenai.com/aee ccom/doss [Accessed 26-10-
OpenAI, Josh Achiam, A. and Sandhini Agarwal, e. Gpt- technical report, 2024. URL httttttss//aiiit 2oss/2333.00 047
2021.
Willard, B. T. and Louf, R. Efficient guided generation for large language models, 2023. URL https: //axxiv...vvv/////// org/ abs /20/2230.22222 09702.
Pezoa, F., Reutter, J. L., Suarez. F., Ugarte. M.. and Vrgoë, D. Foundations of json schema. In Proceed- ings of the 25th International Conference World Wide Web, WWW '16, pp. 263-273, Republic and Canton of Geneva, CHE, 2016. International World Wide Web Con- ferences Steering Committee. ISBN 9781450341431. doi: 10. 10.1145/287242 227880229 URL https: /ooi. brg/10.1145/28722 2883029.
Xiao, C., Dymetman, M., and Gardent, C. Sequence- based structured prediction for semantic parsing. In Erk, K. and Smith, N. A. (eds.), Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Pupers), pp. 1341-1354

---

Earley-Driven Dynamic Pruning for Efficient Structured Decoding
Berlin, Germany, August 2016. Association for Compu-
tational Linguisties. doi: 10. 10.18653/1//11--1122) URL https: http::://aalaanhhloggo.o wwwppoo-g22//// 1127/.
Yang, A., Yang, B., Zhang, B., Hui, B., Zheng, B., Yu,
B., Li, C., Liu, D., Huang, F,, Wei, H., al. Qwen2. 5 technical report. arXiv preprint 1511 2024.
Yin, P. and Neubig. G. A syntactic neural model for general purpose code generation. Barzilay, and Kan, M.-Y. (eds.), Proceedings of the 55th Annual Meet- ing of the Association for Computationnl Linguistics (Volume 1: Long Papers), pp. 440-450, Vancouver, Canada, July 2017. Association for Computational Lin- guistics, doi: /0.1-111/ URL ht htsps: /acllantboloog..or//e1---11111
12

---

Earley-Driven Dynamic Pruning for Efficient Structured Decoding
A. Appendix: Python Library Versions
This appendix provides a comprehensive list of Python libraries and their respective versions used our project. Docu- menting the exact versions of these dependencies is crucial for ensuring the reproducibility of our work. By maintaining consistent environment with the specified versions, readers can accurately replicate our experiments and avoid potential issues arising from version discrepancies. Below, present the libraries and their versions in tabular format for easy reference.
Table Python Libraries and Versions
Package
Version
Package
Version
Package
Version
accelerate
1.2.1
aiohappyeyeballs
2.4.4
aiohttp
3.11.11
aiosignal
1.3.2
airportsdata
20241001
annotated-types
0.7.0
astunparse
1.6.3
attrs
24.3.0
cloudpickle
3.1.1
datasets
3.2.0
dill
0.3.8
diskcache
5.6.3
dnspython
2.6.1
cinops
0.8.0
expecttest
0.2.1
flash-attn
2.7.3
frozendict
2.4.6
frozenlist
1.5.0
fsspec
2024.6.1
general_sam
1.0.1
huggingface-hub
0.27.1
hypothesis
6.108.4
iniconfig
2.0.0
interegular
0.3.3
jsonpointer
2.1
jsonschema
4.23.0
jsonschema-specifications
2024.10.1
lark
1.2.2
lintrunner
0.12.5
Im-formattenforcer
0.10.9
mkl-service
2.4.0
multidict
6.1.0
multiprocess
0.70.16
nest-asyncio
1.6.0
ninja
1.11.111
numpy
1.26.4
optree
0.12.1
outlines
0.1.13
outlines_core
0.1.26
pandas
2.2.3
pluggy
1.5.0
propcache
0.2.1
protobuf
5.29.3
pyarrow
19.0.0
pybind11
2.13.6
pycountry
24.6.1
pydantic
2.10.5
pydantic _connticccoreeeeo
ccre
2.27.2
pytest
8.3.4
python-dateutil
2.9.0.posto
python-eted
0.4.5
referencing
0.36.1
regex
2024.11.6
rpds-py
0.22.3
safetensors
0.5.2
sentencepiece
0.2.0
sortedcontainers
2.4.0
tiktoken
0.8.0
tokenizers
0.21.0
torch
2.4.0
torchaudio
2.4.0
torchelastic
0.2.2
torchvision
0.19.0
transformers
4.48.0
triton
3.0.0
types- dataclasses
types-dataclasses
0.6.6
typing extensions
4.12.2
tzdata
2024.2
xgrammar
0.1.10
xxhash
3.5.0
yarl
1.18.3
B. Additional Experimental Results
To address potential concerns about the completeness of our evaluation and to provide more comprehensive analysis of our proposed method, we conducted two additional experiments that examine different aspects of performance measurement and output quality assessment.
B.1. Pipeline Component Analysis: Parsing and Masking Throughput
In response to questions about whether our reported throughput results reflect the performance of the entire generation pipeline, we clarify that the main results presented in our paper focus specifically on the parsing and mask generation stages to provide precise performance analysis of our key technical innovations. However, to address this concern, we conducted additional experiments measuring throughput for the complete pipeline, including throughput without constrained decoding (w/o CD).
Table 6 presents the detailed throughput measurements (JSON objects second) across different models and methods. While the complete pipeline results show lower throughput due to the inclusion of LLM calls and generation processes, our proposed Formatron method maintains competitive efficiency compared to other constrained decoding approaches, performing nearly as well as the unconstrained baseline (w/o CD).
13

---

Earley-Driven Dynamic Pruning for Efficient Structured Decoding
Table Throughput comparison for parsing and masking stages different models and methods (JSON objects per second)
Model
Method
JSON/s
w/o CD
18.16
Im-format
11.75
Gemma
Outlnnes
13.56
X Xgrammar 17.72
Formatron
18.02
w/o CD
31.75
Im-format
20.51
Llama3
Outlines
23.71
Xgrammar 30.42
Formatron
30.42
w/o CD
35.40
Im-format
16.23
Qwen
Outlines 25.98
Xgrammar 34.34
Formatron
34.46
B.2. Output Quality Assessment: Accuracy Metries
While single schema is compatible across multiple constrained decoding libraries, currently standardized interpretation exists across implementations. JSON Schema, for instance, does not define allowed whitespace patterns or positions within valid ISON structures. Given that most models' tokenizers are sensitive to whitespace character position and type, identical schemas may yield different outputs when processed through different libraries.
To provide a more comprehensive evaluation beyond throughput measurements, conducted additional experiments assess output quality using accuracy metrics. This addresses the important question of whether performance gains come the cost of generation quality.
Table shows the accuracy results for different models and methods across two evaluation scenarios: json. schema and jisonggramma The results demonstrate that our proposed method achieves competitive performance compared to existing approaches while maintaining the efficiency advantages shown in the main results.
Table 7. Accuracy comparison across different models and methods for JSON schema and grammar tasks
Model
Method
json_schema
ison_grammar
baseline
0.73
Im-format
0.74
0.71
Gemma
Outlines
0.80
Xgrammar
0.76
0.71
Formatron
0.73
0.74
baseline
0.47
Im-format
0.60
0,40
Llama3
Outlines
0.73
Xgrammar
0.69
0.47
Formatron
0.67
0.48
baseline
0.09
Im-format
0.53
0.10
Mistral
Outlines
0.44
Xgrammar
0.53
0.09
Formatron
0.52
0.11
14

---

Earley-Driven Dynamic Pruning for Efficient Structured Decoding
These additional experiments confirm that method maintains competitive accuracy while achieving superior efficiency, thus validating both the effectiveness and reliability of our approach.
C. Notation and Terminology
To improve the readability of this paper, we provide a comprehensive notation table for reference. The following table contains the key symbols and concepts used throughout our work.
Symbol
Description
A, B, X,Y
Non-terminal symbols in context-free grammar
a,c
Terminal symbols in context-frr free grammar
0,8,7
Sequences composed of terminal and non-terminal symbols
Empty string
Sli)...., ,[n]
Sequence of Earley state sets, where S[i] contains items at position i
(X
8.
Earley item notation, where indicates current parsing position and j indicates starting position Extended Earley item notation, where span [ captures fI's coverage range
(A a B,i,))
D. Task Examples
Below are iuput-output examples for the three constrained generation tasks:
Geometry
Input: name all the rivers in colorado.
Output: answer river 2oo.llootttttiideee (" colorado "))))
JSON Schema and JSON Grammar
Input:
"content": "You are a helpful assistant that answers in JSON. Here the json schema you must adhere to: to: neschmma>/mmm title :
WirelessAcessPoim'
"type"s 'object', 'properties ('ssid f title :: 'SSID" 'type': 'string } 'sccurityProtocol '; ('title "
SecurityProtocol "type" 'string '). 'bandwidth" : ('title
Bandwidth', 'type': 'string }} 'required ": ['ssid',
- securityProtocol!' 'bandwidth ']} n<//cchmm>\\n",
role": "system"
"content": "I'm currently configuring a wireless access point for our office network and need to generate JSON object that accurately represents its settings. The access point's SSID should be OfficeNetSecure it uses EPA2-Enterprise as its security protocol, and it's capable of a bandwidth of up to 1300 Mbps on the GHz band. This ISON object will be used to document our network configurations and to automate the setup process for additional access points in the future. Please provide ISON object that includes these details.".
"role". "user"
12
Output:
{
13
14
"ssid": "OfficeNettSecure"
15

---

Earley-Driven Dynamic Pruning for Efficient Structured Decoding
Pecurityyrotocol "WPA2- "wPA--Enterprise. "bandwdtt"" " "1300 Mbps"
E. Data Augmentation Workflow
Text Generation We use five models (deepseek-chat,
--fi----e-flash-expppp gemini-exp, gpt-4, and gpt-4o) generate text variations. Each model generates 25 variations, resulting in total of 125 data points. The following prompt is used for text generation:
Generate 25 variations of the user message. Follow these guidelines:
1. MUST include all required fields and maintain data accuracy.
3
2. Vary sentence structures using these techniques:
Use different verb forms (active/ passive).
Apply paraphrasing while keeping the same meaning. Change word order when possible.
Use synonyms for non-key terms.
3. Vary these properties creatively: {chr (10). join fieeldiisstructions
4. Keep key terminology consistent (names / etc). Sound natural and conversational.
10
Answer in English.
7. Output MUST be pure ISON only text, comments, markdown.
Required JSON format:
15
{
16
" "content"; [
17
"content": "Example message I...".
"role": "user"
22
"ccontent:: "Example message 2...",
23
"role", "user"
34
Critical Requirements:
Final ISON MUST NOT be truncated.
Last array item MUST end with }11 without a comma.
30
31
Escape all double quotes inside content.
22
Ensure all brackets are properly closed.
Original Message Structure Reference: (original.message
Data Processing The content field is extracted from the generated JSON data. Incomplete or malformed data points are removed during initial filtering.
Quality Evaluation We ol evaluate the filtered data. The evaluation prompt is follows:
You are an expert text quality evaluator.
For each input text, provide a JSON object with "results" array containing evaluation objects.
3 Each evaluation object must contain exactly four fields: "textNumber": The index of the text (starting from 1).
16

---

Earley-Driven Dynamic Pruning for Efficient Structured Decoding
relevance : A relevance score between 0 and 100 (based schema keywords)
"uniqueness": A uniqueness score between 0 and 100 (based on sentence
4 structure),
"coherence": A coherence score between 0 and 100 (based on semantic flow).
8
Response format:
10
{
"results": [
"texiNumber": 1, "relevance"; 94, "uniqueness"; 85. "coherence"; 90 }
"textNumber": 2, "relevance"; 95, '"uniqueness": 88. "cchheence": 92 },
14
{
"textNumber"; 3, "relevance"; 93, "uniqueness": 82, "coherence"; 89 }
15
16
Important rules:
1. Each text must be evaluated individually.
2. The "textNumber" must match the order of the input texts (starting from 1)
4
3. Scores must be integers between and 100.
22
4. Do not include any additional fields or comments in the JSON response.
5. Ensure the response is valid JSON and can be parsed directly.
The data is sorted based evaluation scores (relevance, uniqueness, and coherence). For each schema, the top 100 highest-scoring data points are retained. The final filtered data is saved JSON file for downstream use.
17


Reviews:
[{"review_id": "RpvsSNkKzi", "reviewer": "Reviewer_xPX3", "summary": "This paper proposes ZapFormat, a dynamic pruning strategy that extends the Early algorithm for CFG parsing by eliminating invalid or redundant states. ZapFormat can improve inference speed of LLMs in constrained decoding.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "## Q: I wonder if they are just the throughput of parsing & masking\n\nThanks for raising this important point on result presentation. We clarify that the throughput results in our paper indeed only reflect the parsing and mask generation stages, not the entire pipeline. We isolated these components to provide precise performance analysis of our key technical innovations.\n\nYou're right that entire pipeline performance measurement would be valuable. we conducted additional experiments on throughput for the entire pipeline, including the throughput without contrained decoding (w/o CD).\n\n|Model|Methods|Json/s|\n|-|-|-|\n|Gemma|w/o CD|18.16|\n||lm-format|11.75|\n||Outlines|13.56|\n||Xgrammar|17.72|\n||Formatron|18.02|\n|Llama3|w/o CD|31.75|\n||lm-format|20.51|\n||Outlines|23.71|\n||Xgrammar|30.42|\n||Formatron|30.42|\n|Qwen|w/o CD|35.40|\n||lm-format|16.23|\n||Outlines| 25.98|\n||Xgrammar|34.34|\n||Formatron|34.46|\n\nSince the entire pipeline result includes LLM calls and generation, the throughput will be much lower. As can be seen from the new experimental results, our **Formatron is still the most efficient** among all constrained decoding methods, almost close to of w/o CD.\n\n## Q: The style of subsubsection titles such as 4.2.1 seems mismatching with the other section titles.\n\nThank you for highlighting this formatting inconsistency. We appreciate your meticulous review of the document structure. We will ensure all section and subsection titles follow a consistent style throughout the paper in our revision.\n\n## Q: The 4.3 4.4 and 4.5 sections seem irrelevant to ZapFormat. Maybe you should describe them elsewhere.\n\nThank you for your valuable feedback on paper organization. We agree that these sections may not directly contribute to the ZapFormat. We will restructure the paper to place these sections in a more appropriate location that better serves the overall narrative flow of our work.\n\n## Q: How much do you think the speed of constrained decoding matters for reasoning models which have a really long output (thought) before calling some function?\n\nThank you for this excellent question regarding constrained decoding for reasoning models.\n\nOur approach is flexible: for reasoning models with extensive thought processes, we can selectively apply constraints only to the function call portions, thereby maintaining efficiency comparable to non-reasoning models since the long reasoning output does not matter in this case. Alternatively, constrained decoding ensures that for ensuring thinking tags match, particularly for smaller models (7B parameters or fewer) or when processing out-of-distribution inputs. This helps maintain the paired tag structure required for proper reasoning format. For this case, the speed of constrained decoding is even more important since the number of constrained tokens could be enormous, much larger than non-reasoning models. This specific area is relatively unexplored though.\n\nHence, your question identifies an important research direction worthy of further exploration, especially when reasoning processes require specific formatting constraints and maintaining generation efficiency is necessary.", "claims_and_evidence": "The claims are clear and the evidence is convincing.", "methods_and_evaluation_criteria": "Yes. They make sense.\n\nI do have one question regarding throughput results. I wonder if they are just the throughput of parsing & masking or if they include both parsing and generation time. Because 5000+ token per second seems way too fast even for non-constrained decoding.\n\nIf they only include parsing and masking, I think it would be better if the author could also report overall throughput, so that the improvements can be put into context.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "Yes. The experiment designs are sound.", "relation_to_broader_scientific_literature": "This paper is a continuation of the efforts made to speed up constrained decoding. The methods used in it are a combination of existing ideas and the authors' own proposal. The results look really significant.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "The style of subsubsection titles such as 4.2.1 seems mismatching with the other section titles.\n\nThe 4.3 4.4 and 4.5 sections seem irrelevant to ZapFormat. Maybe you should describe them elsewhere.", "questions_for_authors": "How much do you think the speed of constrained decoding matters for reasoning models which have a really long output (thought) before calling some function?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NaABCMNMkB", "reviewer": "Reviewer_KTEP", "summary": "This paper proposes using the Earley parsing algorithm to speed up constrained decoding (e.g., for requiring output to be valid json). While existing methods for constrained decoding require looping over all tokens in the model vocabulary to generate the \"mask\" which determines which tokens are vs are not allowed to be generated at a given position during decoding, the Early algorithm avoids this large computational expense using a state-tracking algorithm.  With this approach, it is able to attain up to 2x speedup relative to state-of-the-art constrained decoding methods like XGrammar.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "## Q1: I think the background necessary for understanding this paper, as well as the core method, could be better explained, I had a hard time understanding it.\n\nThank you for this important feedback about the paper's accessibility. We acknowledge that the background and core methodology of our paper could be more clearly presented. Due to the 8-page limit, we had to balance background explanation with results. In our revision, we will carefully enrich the background section and methodology description, taking full advantage of the additional space available in the camera-ready version. Additionally, we will invite colleagues from diverse technical backgrounds to review our revised manuscript to ensure our explanations are accessible and clear.\n\n## Q2: I'm not sure how much algorithmic novelty there is here. Is this just an efficient implementation of an existing algorithm?\n\nThank you for this important question regarding the novelty of our approach.\n\nOur work builds upon the Earley algorithm, which is fundamentally a theoretical framework. Our contribution lies in the innovative adaptations required to transform this theoretical construct originally designed for languages parsing into a practical solution for language model applications, which required developing both theoretical observations and theory-backed algorithm modifications rather than simply optimizing an existing implementation through engineering.\n\nWe have made several adaptations to bridge theory and practice:\n\n1. We noted that constrained decoding only requires format recognition rather than obtaining complete parsing trees, implying the potential to prune states in a modified Earley algorithm.\n2. We formalized the idea of high-level regular grammars, allowing us to show what kinds of substructures will lead to repetitive states in the context of format recognition and hence can be effectively pruned.\n3. Based on these theoretical constructs, we developed a domain-specific pruning strategy to manage Earley states efficiently in the context of language model generation.\n\n## Q3: It would be helpful to provide a bit more of a primer for the key ideas/notation used in the paper.\n\nWe appreciate the reviewer's suggestion on how to improve readability. We will enhance the paper by:\n\n1. Adding a comprehensive notation table for reference. The following table is a partial example.\n\n| Symbol | Description |\n|--------|-------------|\n| A, B, X, Y | Non-terminal symbols in context-free grammar |\n| a, c | Terminal symbols in context-free grammar |\n| α, β, γ | Sequences composed of terminal and non-terminal symbols |\n| ε | Empty string |\n| S[i], ..., S[n] | Sequence of Earley state sets, where S[i] contains items at position i |\n| (X → α • β, j) | Traditional Earley item notation, where • indicates current parsing position and j indicates starting position |\n| (A → α • β, i, j) | Extended Earley item notation, where span [i, j] captures β's coverage range |\n\n2. Providing a more accessible introduction to key concepts before diving into technical details\n3. Including intuitive examples for complex ideas\n\nThese improvements will make the paper more accessible.\n\n## Q4: Does this method have any important limitations?\n\nWe thank the reviewer for this important question on our method's applicability. \n\nOur method has no fundamental algorithmic limitations. However, the primary challenge lies in the nature of constrained decoding approaches generally - can only be applied during inference time and cannot be directly integrated into the model training process. Integrating constraint-decoding directly into supervised and RL training represents a promising direction for future research.\n\n## Q5: Does it work for batched inference as well?\n\nWe thank the reviewer for this important question about our method's efficiency in large-scale inference settings.\n\nYes, Formatron fully supports batched inference. Our dynamic pruning and state caching mechanisms operate efficiently across multiple concurrent requests:\n\n1. Our state caching system maintains separate pruned state sets for each sequence in the batch, allowing independent parsing paths from different grammars while sharing the same underlying algorithmic optimizations.\n2. When processing multiple inputs simultaneously, Formatron's memory efficiency benefits become even more significant, as the dynamic pruning reduces the aggregate memory footprint across all batch elements.\n3. The context-independent token mask cache is particularly effective in batched scenarios, as the precomputed masks can be efficiently applied across multiple sequences that share the same grammar constraints.", "claims_and_evidence": "I believe so.", "methods_and_evaluation_criteria": "I believe so.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "I saw no immediate issues with the experimental soundness.", "relation_to_broader_scientific_literature": "I am not familiar with the literature on this method.", "essential_references_not_discussed": "Not sure.", "other_strengths_and_weaknesses": "Strengths:\n- The speedup results look quite good relative to the baselines.\n- Constrained decoding is an important problem.\n\nWeaknesses:\n- I think the background necessary for understanding this paper, as well as the core method, could be better explained, I had a hard time understanding it.\n- I'm not sure how much algorithmic novelty there is here. Is this just an efficient implementation of an existing algorithm?\n\nI currently am scoring this paper with \"weak accept\" given that the results seem impressive, but I have low confidence in this review since I am not familiar with the literature or SOTA methods for tackling this problem.", "other_comments_or_suggestions": "- It would be helpful to provide a bit more of a primer for the key ideas/notation used in the paper.", "questions_for_authors": "Does this method have any important limitations? Does it work for batched inference as well?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8rpSeE9hbh", "reviewer": "Reviewer_YX9o", "summary": "This paper is about a novel method for grammar constrained decoding. Grammar constrained decoding poses many challenges to auto-regressive language model decoding, and as such a primary concern is to make it more efficient. This paper presents Formatron, an algorithm which keeps track of which states are still relevant, with the goal to make grammar-constrained decoding more efficient. It uses dynamic pruning based on the Earley algorithm. In particular, authors introduce “ZapFormat,” a method for tracking dependencies and removing unnecessary items. Experiments are provided, showing that the throughput is greatly increased using Formatron over other baseline methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "## Q1: In order to enhance clarity of Section 4, it would be useful to also include pseudocode.\n\nWe appreciate the reviewer's valuable suggestion regarding Section 4. We agree that including pseudocode would enhance the clarity of this section. We will incorporate pseudocode in the revised manuscript.\n\n## Q2: It would be nice to also report on some metric of the output such as accuracy or perplexity.\n\nThank you for your insightful suggestion. We have evaluated output quality using accuracy metrics. Our experiments show that the proposed method achieves competitive performance compared to previous methods. We will incorporate this additional analysis in the revised manuscript.\n\n| Model  | Methods   | json_schema | json_grammar |\n|--------|-----------|-------------|--------------|\n| gemma  | baseline  | 0.73        | -            |\n|        | lm-format | 0.74        | 0.71         |\n|        | Outlines  | 0.80        | -            |\n|        | Xgrammar  | 0.76        | 0.71         |\n|        | Formatron | 0.73        | 0.74         |\n| Llama3 | baseline  | 0.47        | -            |\n|        | lm-format | 0.60        | 0.40         |\n|        | Outlines  | 0.73        | -            |\n|        | Xgrammar  | 0.69        | 0.47         |\n|        | Formatron | 0.67        | 0.48         |\n| Mistral| baseline  | 0.09        | -            |\n|        | lm-format | 0.53        | 0.10         |\n|        | Outlines  | 0.44        | -            |\n|        | Xgrammar  | 0.53        | 0.09         |\n|        | Formatron | 0.52        | 0.11         |\n\n## Q3: The Formatron algorithm's throughput degrades at 3 runs as seen in Table 2. Why is this the case? Is there anything different occurring in these different runs?\n\nThank you for your insightful question. The throughput variation in our initial 3 runs was likely due to resource contention on the shared server where we conducted experiments. After re-running tests on an idle server, we observed consistent improvements (see updated table). These new results confirm Formatron's throughput are stable. We will ensure all results in our revised paper are free from resource contention.\n\n| Model   | Methods   | 1 run     | 3 run     | 5 run     | 10 run    |\n|---------|-----------|-----------|-----------|-----------|-----------|\n| gemma   | Formatron | 7453.87   | 10180.72  | 10900.42  | 11929.77  |\n| Llama3  | Formatron | 7616.25   | 10271.73  | 11018.91  | 11945.94  |\n| Mistral | Formatron | 12828.53  | 13522.77  | 13841.85  | 14424.69  |\n| qwen    | Formatron | 8449.92   | 10537.26  | 11397.31  | 12202.48  |\n\n## Q4: Due to the claims of reduction in memory consumption, it would be insightful to share empirical details or other analysis regarding this claim.\n\nThank you for your important question regarding memory usage. We conducted additional experiments on max memory usage(unit: MB) of the process during constrained decoding. We note that pruning does help reducing memory usage. We will include these results in the revised manuscript.\n| Model   | Method       | Max Memory Usage (MB) |\n|---------|--------------|------------------------|\n| Llama3 | Formatron    | 1635.92               |\n| | w/o pruning  | 1655.48               |\n| Mistral    | Formatron    | 1519.09               |\n| | w/o pruning  | 1530.77               |", "claims_and_evidence": "The claims made in the submission are indeed supported by clear and convincing evidence. However, it would be informative to also report on the memory consumed by the various methods and their baselines (or alternatively, to give some analysis of how the memory should scale). This is because one of the primary claims is that this method reduces the memory overhead as well.", "methods_and_evaluation_criteria": "The benchmark datasets and the baseline methods do make sense for the problem at hand. In order to enhance clarity of Section 4, it would be useful to also include pseudocode. There are many components and it would be nice to present how they all interact with each other.", "theoretical_claims": "N/a", "experimental_designs_or_analyses": "See below.", "relation_to_broader_scientific_literature": "Methods like verifiers and grammars are in general becoming more popular for language models. It appears as though some sort of supervision may be useful. Hence, methods to improve efficiency for such methods should allow the literature to continue to explore these directions with a more scalable approach.", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "Strengths:\n* This paper adapt a well-known algorithm to language models. There are two issues with the Earley algorithm when it comes to decoding: one is that the required amount of sets to store scales with the length of the input, and the other is that the parser does not get rid of previous sets. This paper analyzes the challenges imposed by the Earley algorithm in LM decoding.\n* This paper introduces an online method which is well-suited for inference both because it is more efficient (by dynamically pruning items) and requires less memory overhead.\n* Experiments show that throughput is much faster with the proposed algorithm than three other methods on four tasks. Ablations are included as well.\n\nWeaknesses:\n* While it makes sense to report on the throughput of tasks on Task 1, (as this is one of the main goals of efficient GCD) in order to show that the method is also performing well qualitatively, it would nice to also report on some metric of the output such as accuracy or perplexity.\n* The Formatron algorithm’s throughput degrades at 3 runs as seen in Table 2. Why is this the case? Is there anything different occurring in these different runs?\n* Due to the claims of reduction in memory consumption, it would be insightful to share empirical details or other analysis regarding this claim.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sc4brhbSB7", "reviewer": "Reviewer_wJ9T", "summary": "LLM can be equipped with a grammar verifier which verifies next token prediction at each step to satisfy grammatical constraints. The key step is to incremental update the grammar state in the parsing algorithm to output the possible next tokens. Given a general form of grammar (CFG), the paper leverages Earley parsing and proposes improvements on the Earley parsing algorithm to achieve efficient next possible token calculations. Compared to available techniques, the paper achieves efficient next possible token calculation efficiency as demonstrated by the high throughput for LLM constrained decoding process.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "## Q1: Although cache optimization is proposed in XGrammar (2024) a detailed comparison to compare the two is missing.\n\nWe appreciate the reviewer's concern. Section 4.3 addresses this comparison. Both methods categorize tokens into Context-Independent and Context-Dependent types, but we don't use suffix strings to identify invalid context-dependent tokens. For example, XGrammar precomputes all possible suffixes of `{` to reject tokens like `{//ABC` without the parser, while we don't.\nWe omit this optimization because:\n1. There's no theoretical guarantee that it significantly reduces context-dependent tokens across all grammars and vocabularies,\n2. Precomputation overhead scales with grammar size.\n3. Formatron already matches or exceeds XGrammar's throughput without it.\n\nThat said, this optimization is orthogonal to ours, so it is possible to include the optimization if needed.\n\n## Q2: Do you have a concrete example in the dataset where you can show techniques in 4.4 helps?\n\nThank you for your insightful question. When a context-dependent token is rejected by the parser, the bytes from the first to the byte that is rejected by the parser become a rejected prefix. For each unprocessed context-dependent token, if it shares a prefix with rejected prefixes, then it can be immediately rejected. This allows us to reject tokens with common prefixes faster. \n We collected following examples from experiments:\n- prefix: ` \".`, token: ` \"..\\..\\..\\`\n- prefix: `=\"\"`, token: `=\"\"></`\n- prefix: `=\"<`, token: `=\"<?=$`\n\n## Q3: From this viewpoint, a baseline is missing where only 4.5 is present\n\nWe agree with your suggestion. Here's the baseline with 4.5 only. \n|Model|Method| json_s|\n|-|-|-|\n|Genma|Formatron|7453.87|\n|| only 4.5| 27.90|\n|Llama3| Formatron|7616.25|\n||only 4.5|50.04|\n|Mistral| Formatron|12828.53|\n||only 4.5| 264.31|\n|Qwen| Formatron| 8449.92|\n||only 4.5| 46.69|\n\n## Q4: How do you explain the decrease about 3 times run?\n\nThank you for your careful review. **Reviewer YX9o** had the same question. To allow more space for addressing your other concerns in detail, please refer to our response to **Reviewer YX9o: Q3**.\n\n## Q5: No. However, I think it would be nice to mention that the NLP community has examined neural constrained decoding from 2016\n\nWe appreciate the reviewer's suggestion. We will incorporate Xiao et al. (2016) and Yin et al. (2017) in our revised manuscript as important references to this field's early work.\nWe did not include them as baselines because:\n1. Adapting these methods to transformer architecture would require significant engineering modifications and LLM continual pretraining.\n2. The grammar state maintenance in these approaches would consume excessive memory when applied to LLM.  \n\n## Q6: Sections 4.2.1 and 4.2.2 introduce the format and the associated graph, however, it is not clearly stated how such representations help the pruning. Adding this would enhance the paper's readability.\n\nThank you for requesting clarification on how the representations facilitate pruning. You're right that sections 4.2.1 and 4.2.2 would benefit from a more explicit connection to the pruning mechanism.\n\n4.2.1 defines inter-item dependencies and lays the foundation for pruning: for independent items, removing one will not affect Earley actions on others. The enhanced Earley item representation emphasizes that while the same Earley item often spans multiple sets, its dependencies are only affected by its starting and end position. Thus, we need not search all Earley sets in between to find all its dependencies.\n\n4.2.2 defines the dependency graph directly enables pruning since reachability closure is defined on this graph. A path from `x` to `a` is a dependency chain from `a` to `x`. If `a` (indirectly) depends on `x`, then `x` is reachable from `a`. That's why reachable items must be kept; removing them would disrupt the dependency chains required for correctness.\n\n## Q7: It is also important to know the throughput without constrained decoding\n\nWe appreciate your insightful question. The throughput metric in our manuscript is only applicable when constrained decoding component is present in the pipeline since it only measures the throughput of the constrained decoding component only. To answer your question, we conducted additional experiments on throughput for the entire pipeline, including the throughput without contrained decoding (w/o CD).\n\n|Model|Methods|Json/s|\n|-|-|-|\n|Gemma|w/o CD|18.16|\n||lm-format|11.75|\n||Outlines|13.56|\n||Xgrammar|17.72|\n||Formatron|18.02|\n|Llama3|w/o CD|31.75|\n||lm-format|20.51|\n||Outlines|23.71|\n||Xgrammar|30.42|\n||Formatron|30.42|\n|Qwen|w/o CD|35.40|\n||lm-format|16.23|\n||Outlines| 25.98|\n||Xgrammar|34.34|\n||Formatron|34.46|\n\nAll constrained decoding methods require additional computation, of which our **Formatron remains the fastest**, almost approaching the speed of w/o CD.", "claims_and_evidence": "The paper claims that the following techniques achieve high throughput (high efficiency of the next possible token calculation):\n- Overall: yes, higher than existing techniques significantly (Table1)\n- By pruning non influencing states: yes, Table 3\n- By optimizing cache: yes, Table 3. Although cache optimization is proposed in XGrammar (2024) a detailed comparison to compare the two is missing.\n- Rejection Prefix Optimization: No\n- Grammar Transformation: No\nAlthough the later two might contribute to the overall throughput improvement.", "methods_and_evaluation_criteria": "The throughput seems to be a sensible metric for this task. \n\nTwo datasets are established benchmarks and fit well to the studied problem. The authors further propose another task that is similar in grammar to json_s, so a sensible benchmark.", "theoretical_claims": "- In Earley algorithm, pruning the particular states as the authors indicate should be able to save memory, eliminate useless states for next token parsing (4.1) thus save time for next possible token calculations.\n - The dependency construction using indices help to identify and prune completed states to help accelerate the next token prediction calculations; although I think it is not clearly stated in the paper how this new presentation helps pruning.\n- The cache helps as already shown by XGrammar.\n- 4.4 Not sure how much such techniques help in practice: taking the same example as the paper, if \"aaac\" if an invalid prefix, it would never be generated by constrained decoding as a prefix. The help happens to reject \"aaacdefrf\" a bit quicker during state calculation.\n- 4.5 The claim is right but the benchmarks should more appropriately use 4.5 as baselines.", "experimental_designs_or_analyses": "- 4.5 helps the performance but is not a strong scientific contribution, from this viewpoint, a baseline is missing where only 4.5 is present in the system to measure throughput.\n- It is also important to know the throughput without constrained decoding\n- There requires an explanation why 3 run throughput decreases consistently for the proposed techniques.", "relation_to_broader_scientific_literature": "- It is related to grammar parsing. The paper is based on Earley parsing algorithm which is a classic parsing algorithm for general CFG grammar.\n- It is also related to accelerating LLM throughput which is broadly related to LLM inference speed.", "essential_references_not_discussed": "No. However, I think it would be nice to mention that the NLP community has examined neural constrained decoding from 2016 with papers like https://aclanthology.org/P16-1127 and https://arxiv.org/abs/1704.01696", "other_strengths_and_weaknesses": "None", "other_comments_or_suggestions": "- 4.2.1 and 4.2.2 introduces the format and the associated graph, however, it is not clearly stated how such representations help the pruning, putting which I think would enhance the paper readability.\n- As mentioned previously, I think some baselines are missing (or would be better to include): a baseline with only changes from 4.5 and a baseline where no contrained decoding is used.", "questions_for_authors": "- How do you explain the decrease about 3 times run?\n- Do you have a concrete example in the dataset where you can show techniques in 4.4 helps\n- Are there comparisons between the different cache strategies in terms of performance?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper focus on improving LLM decoding speed in a grammar constrained environment. The paper leverages Earley parsing and proposes improvements on the Earley parsing algorithm to achieve efficient next possible token calculations. Experiment results show impressive improvement on throughput parsing and masking.

Reviewers generally agree that this paper provide a solid improvement on accelerating grammar constrained decoding. Although some concern about the experiment setting has been raised, the author has addressed them accordingly.
Decision: Accept (poster)