Gram2Token: Enabling Run-time GPU-Native Grammar-Constrained Decoding for LLMs

Grammar-constrained decoding enables large language models (LLMs) to reliably generate structured outputs such as JSON, SQL, and domain-specific programs. Existing systems often enforce constraints by executing byte-level parser logic inside the token-level decoding loop, introducing CPU-side control flow and CPU--GPU synchronization that become bottlenecks under continuous batching. We propose Gram2Token, a GPU-native framework that preprocesses deterministic byte-level grammar execution into token-level transitions before inference. Gram2Token aligns tokenizer byte sequences with grammar transitions through a trie and groups tokens with identical transition outcomes across preprocessed grammar states. These categories yield compact validity masks and transition tables, reducing run-time enforcement to category lookup, masking, and state update rather than parser-style byte traversal. Across four model families under schema-diverse continuous batching, Gram2Token achieves a geometric-mean throughput improvement of 1.38$\times$ over the strongest baseline, with a maximum speedup of 1.85$\times$, at the cost of additional preprocessing and time-to-first-token overhead. Break-even and grammar-complexity analyses show that this overhead is amortized by grammar reuse, longer outputs, and larger batches. These results show that token-level grammar preprocessing is an effective design point for high-throughput structured LLM serving. Code is available at https://github.com/Paradozile/Gram2Token.

Large language models are increasingly used to produce structured outputs, such as JSON objects, database queries, and commands that other programs can read. These outputs must follow strict formatting rules: a missing bracket or a wrong structure can make the result unusable even when the content is otherwise correct. Existing constrained decoding systems can keep outputs valid, but they often slow generation down because formatting rules are usually checked character by character, while language models generate larger text pieces at a time, and this rule-checking can require extra coordination between the GPU running the model and other parts of the system. Thus, we propose Gram2Token, a system that moves much of this work before generation begins. It matches formatting rules to the pieces of text a model can generate, groups pieces that behave the same under those rules, and stores the resulting decisions as compact lookup tables on the GPU. During generation, Gram2Token still enforces the rules at every step, but it replaces complex parser-style reasoning with fast table lookups that identify valid next pieces and update the current formatting state. This keeps outputs structurally valid while improving efficiency in high-throughput structured generation, especially when formats are reused, outputs are longer, or many requests are served together. This can make structured generation more practical for AI agents, data tools, and software systems that need to produce reliable machine-readable outputs at scale.