One-sentence Summary

Researchers from Shanghai Jiao Tong University, Beihang University, and SenseTime Research propose Pre³, which transforms $\text{LR}(1)$LR(1) transition graphs into deterministic pushdown automata via precomputed prefix-conditioned edges, enabling ahead-of-time parallel edge analysis and eliminating runtime path exploration to achieve up to 40% reduction in time per output token and 36% throughput improvement for structured LLM decoding.

Key Contributions

• Pre³ is a deterministic pushdown automaton framework for constrained LLM generation with LR(1) grammars, precomputing prefix-conditioned edges to enable ahead-of-time edge analysis and parallel transition processing.
• Pre³ uses a cycle-aware construction that transforms LR(1) transition graphs into DPDAs using prefix-conditioned edges, eliminating runtime path exploration and bringing LR(1)-to-DPDA parsing to LLM decoding.
• Experiments integrate Pre³ into standard LLM inference frameworks, reducing time per output token by up to 40% and increasing throughput by up to 36%, with larger advantages over prior structured generation methods at large batch sizes.

Introduction

Large language models increasingly need structured outputs such as JSON for function calls, tool use, and embodied AI. Constrained decoding supports this by masking invalid tokens during generation, and LR(1) grammars provide flexible handling of complex recursive formats. However, prior accelerators such as XGrammar convert LR(1) grammars into nondeterministic pushdown automata, leaving runtime backtracking, speculative checks, stack management, and poor scaling at large batch sizes. The authors leverage the deterministic nature of LR(1) languages and introduce Pre^3, a constrained decoding method that directly builds a deterministic pushdown automaton from LR(1) grammars. This removes nondeterministic transitions, enables fuller preprocessing, supports parallel transition verification, and improves time per output token and throughput without sacrificing schema fidelity.

Method

The authors present $\mathrm{Pre}^3$Pre3, a constrained decoding framework that converts a given LR(1) grammar into a deterministic pushdown automaton before generation. The pipeline first derives an LR(1) state transition graph from the grammar, then constructs a DPDA whose transitions encode parsing progress and stack manipulation, and finally uses this automaton to mask invalid tokens from an LLM at runtime. Refer to the framework diagram below.

Because the construction is performed once and can be cached, grammar preprocessing takes only seconds for complex grammars and less than a fraction of a second for simpler ones. At decoding time, the DPDA maintains the parser state and stack, determines the legal next actions, and supplies the corresponding token constraints to the LLM generation loop.

A core design choice is to eliminate the nondeterminism that would otherwise require speculative exploration and persistent stack inspection during decoding. The authors exploit a property of LR(1) grammars: the current stack configuration and the next lookahead symbol uniquely determine the next parsing action. They therefore annotate each transition with a prefix-conditioned edge mechanism, where an edge is identified by the accepted symbol, the stack condition that must be matched, and the stack operations performed during the transition. A parallel check can verify multiple stack conditions, resolving ambiguity after a deterministic structure is produced. As shown in the figure below, a token that would require runtime route judging becomes deterministic once the edge carries explicit stack matching conditions.

The automaton is built from the LR(1) state transition graph, where each node represents an LR(1) item set and original edges represent shift transitions that accept symbols. The construction preserves these states but separates transitions into acceptance edges and reduction edges. Acceptance edges correspond to shifts: they consume an input symbol, push the new state onto the stack, and move to the target state. Reduction edges directly encode reduction transitions between reduction endpoints, avoiding repeated low-level reduction steps when nested grammar rules are involved. The role of each edge type is illustrated below.

Acceptance edges are inherited from the LR(1) state graph and do not require additional determinism handling because LR(1) construction prevents duplicate identical transitions from a given state. When such an edge is taken, the target state information is pushed onto the runtime stack. Reduction edges are added through a two-phase procedure. First, unconditional epsilon reductions are identified and propagated recursively through the state graph, popping states along the path until the reduction target is reached. Because these edges do not consume an input symbol, they can introduce ambiguity, so they are then merged with compatible acceptance edges, aligning stack operations and reduction targets while assigning the necessary accepted token or prefix condition.

A major construction challenge is the presence of cycles in the LR(1) state graph. If reduction edges are expanded naively, repeated traversal of a cycle can generate infinitely many reduction paths. The authors observe that, for a reduction, specifying an entry node and an exit node uniquely determines the relevant reduction context regardless of how many times a cycle has been traversed. For a cycle $C = (s_1, s_2, \ldots, s_n, s_1)$C=(s1​,s2​,…,sn​,s1​) with back edge $s_n \to s_1$sn​→s1​, they modify the back edge to pop the cycle state sequence $(s_1, s_2, \ldots, s_n)$(s1​,s2​,…,sn​) when a complete traversal is detected. The automaton checks whether all states from one traversal are already present in the stack; if so, it removes the redundant cycle context, ensuring that repeated traversals do not accumulate unnecessary state. The cycle handling mechanism is shown below.

Once the DPDA is deterministic and all transitions are fully specified by stack conditions and input symbols, additional preprocessing optimizations become possible. Edges that share the same stack matching condition and stack operations but differ only in accepted symbols can be aggregated, for example combining multiple digit transitions into one token class. Edges that can be executed consecutively under compatible conditions can also be merged into longer jumps, reducing the number of intermediate states that the automaton must visit. These operations shrink the final DPDA and improve constrained decoding efficiency. The optimization patterns are shown below.

Experiment

The evaluation integrates the implementation into LightLLM and compares it with XGrammar, Outlines, and Llama.cpp on H800 GPU servers using JSON-focused prompts with additional private data. Experiments assess per-step grammar-constrained decoding overhead, large-batch inference efficiency, and real-world throughput under varying concurrency, validating both efficiency and deployment scalability. Qualitatively, Pre3 consistently introduces less grammar-related overhead than prior systems and remains competitive as batch sizes and concurrency increase, indicating robust end-to-end scalability for structured generation.

Per-token latency increases with batch size for both unconstrained decoding and constrained decoding using XGrammar. The constrained method shows higher latency than the baseline across all tested batch sizes, and the gap becomes more pronounced as batch size grows. This trend supports the claim that constrained decoding can create a scaling bottleneck due to non-parallelizable validation overhead. Constrained decoding remains slower than unconstrained decoding at every tested batch size. The latency difference grows with batch size, indicating reduced scalability for the constrained method.

Across tested models and large batch sizes, Pre^3 requires less decode time than XGrammar under complex JSON constrained generation. The advantage remains visible at high batch sizes, while some very large batch cases could not be executed on the available hardware setup. Pre^3 consistently delivers lower inference latency than XGrammar in the reported large-batch evaluations The runtime benefit is especially relevant for large batches and larger model configurations

Pre^3 consistently requires less per-step decode time than XGrammar across the tested models and batch sizes. The advantage appears at batch size 1 and becomes more pronounced for Llama-3-8B at batch size 4. These results support the claim that Pre^3 introduces lower constraint decoding overhead than prior structured generation systems. Pre^3 has lower per-step decode times than XGrammar for both Llama-3-8B and Llama-2-70B. The decode time gap is larger at batch size 4 than at batch size 1 for Llama-3-8B.

Experiments evaluate per token latency for unconstrained decoding, XGrammar constrained decoding, and Pre^3 under JSON constrained generation across models and batch sizes. The results show that constrained decoding remains slower than unconstrained decoding at all batch sizes, with the gap widening as batch size grows, indicating a scaling bottleneck from validation overhead. In contrast, Pre^3 consistently requires less per step decode time than XGrammar, with the advantage becoming more pronounced at larger batch sizes and model scales, supporting lower structured generation overhead.