SynCode: LLM Generation with Grammar Augmentation

1 Introduction

• Existing grammar-guided methods are described as either error-prone or imposing significant inference overhead, while prompting and fine-tuning do not fully resolve syntax accuracy.Source: §1 · p. 2
• LLM tokens do not directly correspond to grammar lexical tokens, making soundness difficult to establish for grammar-guided generation.Source: §1 · p. 2
• SynCode accepts user-provided CFGs and composes with greedy, beam-search, and sampling decoding strategies.Source: §1 · p. 2
• During decoding, SynCode derives acceptable terminal sequences and a remainder from partial output, then uses both to construct masks for valid next tokens.Source: §1 · pp. 2–3
• An offline DFA-derived lookup table supports efficient token-mask computation, and GPU offloading parallelizes a substantial portion of syntactical generation computations.Source: §1 · p. 3
• SynCode is sound, retaining syntactically valid tokens at each generation step, and complete under specific conditions, rejecting syntactically invalid tokens.Source: §1 · p. 3
• SynCode eliminates JSON syntax errors and reduces Python and Go syntax errors by 96.07% on average compared with standard generation.Source: §1 · p. 3
• Evaluations cover JSON, SQL, Python, and Go generation, including JSON schema validation and SQL compilation and execution accuracy.Source: §1 · p. 3

2 Background

• The background introduces notation for character alphabets, strings, and concatenation, including the empty string.Σ denotes a finite character alphabet, while Σ* denotes all strings over it, including ε.Source: §2 · p. 3

2.1 Language Models

• LLMs tokenize character strings into vocabulary tokens, with common words sometimes kept whole and rare identifiers split into multiple tokens.The model produces next-token scores that softmax converts to probabilities, and decoding repeats token selection until EOS or another stopping condition.Source: §2.1 · pp. 3–4
• A mask marks viable tokens and discards others; SynCode uses masking to exclude syntactically invalid tokens during decoding.In the depicted workflow, the parser supplies accept sequences and a remainder to the DFA mask store, which creates the token mask.Source: §2.1 · p. 4, Figure 1 · p. 4

2.2 Formal Language Grammar

• CFG production rules replace a single nonterminal with a string of terminals and nonterminals regardless of surrounding symbols.Terminals can be described with regular expressions and recognized by DFAs; the lexer assumes one-character lookahead and no backtracking.Source: §2.2 · p. 5

3.1 Illustrative Example

• SynCode rejects invalid DSL continuations during decoding, whereas the unconstrained LLaMA-7B example emits nonexistent functions and extra question-answer pairs.After the model generates math, SynCode excludes invalid continuations such as _area, allowing it to choose _sqrt instead.Source: §3.1 · p. 6

3.2 SynCode Algorithm

• SynCode’s formulation works with greedy, sampling, or beam-search decoding by applying the chosen algorithm to the syntactically valid token subset.Source: §3.2 · p. 7
• At each step, SynCode parses the partial output into a fixed lexical prefix and mutable remainder, then derives acceptable terminal sequences and a vocabulary mask.The remainder is the suffix whose lexical type may change in later generations; a one-character-lookahead, no-backtracking lexer supports this assumption.Source: §3.2 · p. 7
• The offline DFA mask store precomputes vocabulary masks by DFA state; runtime walks DFAs for the remainder and unions masks across accept sequences.Precomputed masks can be stored as tensors and combined with a small number of tensor union operations.Source: §3.2 · pp. 8–9
• The combined mask overapproximates viable tokens, ensuring soundness; with larger LR lookahead, SynCode is complete and the mask equals Vk.Source: §3.2 · p. 9

3.3 Time Complexity

• O(T∪·|A|) is the per-step complexity; |A| is typically under 10 and at most |Γ|, which is 94 for the largest Python grammar.T∪ is the time for boolean mask union operations.Source: §3.3 · p. 9

4.1 Syntactical Decoding Problem

• For a partial output, syntactical decoding computes vocabulary tokens whose addition keeps the output a valid grammar prefix.SynCode parses the partial output to obtain a remainder and acceptable terminal sequences, then uses them with the precomputed mask store to find valid extensions.Source: §4.1 · pp. 9–10

4.2 Parsing Partial Output

• With one-character-lookahead lexing, SynCode isolates an unstable or unlexed suffix as remainder r and derives accept sequences from the parser state.One- and two-terminal accept sequences are described as efficient and precise in practice; longer sequences can improve precision at increased computational cost.Source: §4.2 · pp. 10–11

4.3 Grammar Mask

• SynCode tests remainder-plus-token strings against accept-sequence patterns through DFA traversal, using an offline mask store for efficient generation-time lookups.Prefix matches are conservatively accepted, and increasing the mask store’s lookahead parameter improves precision but enlarges the table.Source: §4.3 · pp. 11–12

4.4 Soundness and Completeness

• SynCode is sound for valid extensions with accept sequences of length at least 1, and complete when sequence length exceeds token length, but completeness does not ensure whole-output termination.Soundness extends to implementations using varying sequence lengths under the stated relation between accept-sequence sets; the completeness theorem concerns valid partial outputs, not convergence to a valid complete output.Source: §4.4 · pp. 13–14

4.5 SynCode Implementation

• LR(1) parsing computes acceptable terminals in O(|Γ|), so SynCode uses LR parsers; evaluation indicates LR(1) suffices to eliminate most syntax errors.LALR(1) requires O(TP · |Γ|) to confirm terminal validity, while LR(κ) for κ > 1 has high memory requirements.Source: §4.5 · p. 14
• SynCode constructs accept sequences of length 1 or 2 from LR(1) parser states, yielding sound but incomplete decoding that is efficient and precise in practical scenarios.For complete tokens, sequences account for token extensions and changes in the final token type; for incomplete tokens, they use single-terminal sequences from A1.Source: §4.5 · p. 15

4.6 Time Complexity

• Per generation step, SynCode’s cost is O(TA + TP + |Γ| · len(r) + T∪· |Γ|), simplifying to O(T∪· |Γ|) for LR(1) with a small remainder.Offline construction of M0 and M1 costs O(|QΩ|.|V |.|Γ|) and is a one-time cost amortized over generations.Source: §4.6 · p. 15

4.7 SynCode Framework

• Users can add unambiguous LALR(1) or LR(1) grammars in EBNF, and SynCode supports selected non-CFG constraints, including indentation and custom parsing rules, but not semantic constraints.Built-in grammars include JSON, Python, and Go; ignore terminals such as whitespace and comments are handled with trivial one-length accept sequences.Source: §4.7 · p. 16
• SynCode supports LALR(1) and LR(1) base parsers, with LR(1) more efficient at inference-time accept-sequence computation but potentially slower to generate offline.The LR(1) parser generator may take up to 2 minutes for the Python grammar; SynCode adds incremental parsing by caching parser state.Source: §4.7 · p. 16

• The evaluation selected diverse state-of-the-art open-weight models because closed-source APIs do not expose generation logits.JSON used Llama-2-7B-chat and Gemma2-2B-it; text-to-SQL also used Llama-3.2-1B, Llama-3.2-3B, and Gemma-2-2B-it, while code completion used LLaMA-7B, WizardCoder-1B, and CodeGen-350M.Source: §5 · pp. 16–17
• Datasets included JSON-Mode-Eval (100 zero-shot problems), Spider text-to-SQL (1,034 problems), Multilingual HumanEval, and MBXP (974 problems).Multilingual HumanEval extends 164 Python problems to languages including Go; the datasets cover JSON, SQL, Python, and Go generation.Source: §5 · p. 17
• The Python and Go grammars covered substantial language subsets, including common control flow and loops, but excluded features such as Python lambda functions.The JSON grammar has 19 rules and 12 terminals; Python has 520 rules and 94 terminals, and Go has 349 rules and 87 terminals.Source: §5 · p. 17
• Language-specific standard compilers were used to evaluate syntax errors in generated outputs.Source: §5 · p. 17
• Experiments ran on a 48-core Intel Xeon Silver 4214R CPU with two Nvidia RTX A5000 GPUs, using PyTorch, HuggingFace transformers, and Lark.The implementation cites Paszke et al. (2019a) for PyTorch and Wolf et al. (2020) for HuggingFace transformers.Source: §5 · p. 17
• Baselines were Outlines v0.1.1, guidance v0.1.16, and llama.cpp v0.3.1; SynCode used opportunistic masking for fair runtime comparisons.Warmup runs excluded one-time precomputation from inference runtime.Source: §5 · p. 17

6 Experimental Results

• With a fixed maximum token limit, generation may stop before emitting EOS, so syntax errors can still result.SynCode permits EOS only when the output belongs to L(G), but reaching EOS within nmax tokens is not guaranteed.Source: §6 · p. 18
• Evaluations covered 100 JSON-Mode-Eval problems, 1,034 Spider text-to-SQL problems, and 4,154 HumanEval/MBXP-generated samples for each of Python and Go.Source: §6.1 · p. 18, §6.2 · p. 19, §6.3 · p. 20

6.1 Effectiveness of SynCode for JSON Generation

• SynCode eliminated JSON syntax errors; standard generation was invalid on 98% (Llama-2-7B-chat) and 59% (Gemma2-2B-it) of original prompts.The evaluations used original and explicit prompts; the reported invalid-completion rates are for original prompts.Source: §6.1 · p. 18, Table 1 · p. 18
• Gemma2-2B-it schema validation rose from 41% to 99% (original prompts) and from 41% to 100% (explicit prompts) with SynCode.For Llama-2-7B-chat, SynCode also exceeded the grammar-guided baselines in schema validation accuracy.Source: Table 1 · p. 18, §6.1 · p. 19

6.2 Effectiveness of SynCode for SQL Generation

• For Llama-3.2-3B, SynCode increased execution success to 81.4% from 67.4% with unconstrained generation and improved execution accuracy from 28.6% to 34.9%.For Gemma2-2B-it, SynCode showed a 1.7x generation-speed gain and reduced the number of tokens generated.Source: §6.2 · p. 20

6.3 Effectiveness of SynCode for GPL

• SynCode reduced syntax errors by over 90% in most Python and Go experiments and to less than 1% of total samples.The experiments covered 4,154 generated samples per language across HumanEval and MBXP.Source: §6.3 · p. 20, Table 3 · p. 20
• On HumanEval, SynCode slightly improved pass@1 and pass@10 functional correctness over standard generation.Functional correctness was measured by whether generated samples passed unit tests.Source: §6.3 · pp. 20–21, Table 4 · p. 21

6.4 Mask Store Overhead

• DFA mask stores required less than 2 GB of memory and several minutes to generate across evaluated models and grammars; generation is a one-time task.The Llama-2-7B-chat JSON store took 113.72 seconds to create and used 181 MB.Source: §6.4 · p. 21, Table 5 · p. 21

7 Related Work

• Fine-tuning and prompt engineering demand substantial data, compute, and time and offer no formal guarantees; architectural changes are complementary to grammar-guided decoding.The authors also state that these architectural techniques have not yet achieved performance comparable to current state-of-the-art standard LLMs.Source: §7 · p. 21
• Guidance supports CFG constraints but checks the vocabulary at each step and cannot be directly combined with arbitrary decoding strategies; Outlines performs worse than SynCode on JSON and lacks large GPL grammar support.Guidance uses Earley parsing; Outlines uses an incremental Lark-based LALR parser and a combined DFA.Source: §7 · p. 22
• llama.cpp iterates over the vocabulary and updates parse-stack states, while its non-standard grammar syntax and limited grammar features constrain its evaluation to simpler grammars such as JSON.The paper reports that SynCode is more efficient and produces fewer syntax errors in its evaluation.Source: §7 · pp. 22–23
• Picard targets SQL and requires considerable effort to add a grammar, whereas Synchromesh supports DSLs and semantic constraints but SynCode focuses exclusively on syntax.Synchromesh is described as using a non-incremental parser and a union of terminal regular expressions.Source: §7 · p. 23
• Domino under-approximates tokens using parser lookahead, while SynCode conservatively over-approximates and claims soundness for any lookahead.The paper says Domino’s largest supported grammar is a simplified C grammar with 70 rules and roughly 25% overhead, and that its code was unavailable for comparison.Source: §7 · p. 23
• SynCode focuses on CFG-guided generation rather than fixed-schema generation, where limited syntactic choices can enable token skipping or speculative decoding.The paper notes that speculation is not useful for CFGs where the schema is not fixed.Source: §7 · p. 23

8 Conclusion

• During decoding, SynCode incrementally parses partial output and uses its remainder, acceptable terminal sequences, and precomputed DFA mask store to constrain the LLM vocabulary to syntactically valid tokens.Source: §8 · p. 23
• Across JSON, SQL, Python, and Go evaluations, SynCode eliminated JSON syntax errors and improved JSON schema validation over baselines.Source: §8 · p. 23
• SynCode reduced Python and Go syntax errors by 96.07% on average compared with standard generation.Source: §8 · p. 24

A.1 List of Symbols

• G denotes a formal grammar, L(G) its language, and Lp(G) its prefix language; τ denotes a grammar terminal and τi the terminal type of the i-th lexical token.Source: §A.1 · p. 29
• T denotes an LLM tokenizer, V its vocabulary, and Vk the subset of vocabulary tokens acceptable at generation iteration k.Source: §A.1 · p. 29
• Mα is the DFA lookup-store function for terminal sequences of length α, while m denotes a Boolean mask and δ and δ* denote DFA transition functions.Source: §A.1 · p. 29

A.2 Proofs for Theorems

• If appending token t keeps partial output Ck.t in the grammar language, Theorem 1 guarantees that t is retained by GrammarMask.The result assumes Ad contains all possible accept terminal sequences of length d.Source: §A.2 · p. 32
• When A1 ≼ A2, the mask formed from A2 retains a subset of the tokens retained by the mask formed from A1.Source: §A.2 · p. 32
• When d exceeds the length of t, Theorem 2 guarantees that a token retained by GrammarMask yields a partial output in the grammar language.The theorem assumes Ad contains all possible accept terminal sequences of length d.Source: §A.2 · p. 32

A.3 Incremental Parsing Algorithm

• A state map S associates lexical-token prefixes with parser states, allowing parsing to resume from the longest matching prefix.The map accounts for tokenization changes, such as Python quotes changing from a complete empty-string token to an incomplete docstring prefix.Source: §A.3 · p. 34
• The implementation makes parsing incremental but not lexing, because experiments found lexing time insignificant compared with parsing.Source: §A.3 · p. 34
• The parser uses Next to consume a lexer token and Follow to return acceptable terminals at the current parser state.The base parser is standard and non-incremental.Source: §A.3 · p. 34
• The algorithm lexes the partial output, restores a saved state, then processes remaining tokens and stores updated states and acceptable terminals.It returns accept sequences A and remainder r.Source: §A.3 · p. 34

A.4 Ablation Studies

• The incremental-parsing comparison uses CodeGen-350M on HumanEval Python prompts with one sample per prompt.It compares average generation time with and without incremental parsing across maximum new-token limits.Source: §A.4 · p. 34
• At 300 max new tokens, incremental parsing achieves 9x speedup over parsing from scratch.For longer token limits, scratch-parsing time increases significantly, while incremental-parsing time increases slowly.Source: §A.4 · p. 35, Figure 10 · p. 35
• Generation time increases as the maximum number of new tokens increases, both with and without SynCode augmentation.The ablation uses CodeGen-350M to generate completions from HumanEval Python prompts.Source: §A.4 · p. 35

A.5 Few-Shot Prompting

• SynCode is reported effective for few-shot prompting, complementing its effectiveness in zero-shot code generation.Source: §A.5 · p. 35
• The study compares standard generation with SynCode across MBXP Python examples using CodeGen-350M, LLaMA-7B, and WizardCoder-1B.Source: §A.5 · p. 35
• Table 7 reports error counts by error type and the percentage reduction from standard generation to SynCode.Source: §A.5 · p. 35

A.6 SynCode Syntax Errors

• SynCode guarantees completeness for syntactically correct partial programs, but may fail to generate a syntactically correct complete program before the maximum token limit.The example is from a HumanEval problem: the partial output is syntactically correct, but the full program is incomplete.Source: §A.6 · p. 36

A.8.2 SQL Grammar

• The SQL excerpt defines column names, boolean expressions, comparison predicates, literals, timestamps, and names through grammar productions.Examples include AND/OR expressions, comparison operators, Boolean and numeric literals, NOW()/TODAY(), and identifiers or escaped strings.Source: §A.8.2 · pp. 39–40

A.8.3 Python Grammar

• The Python excerpt gives productions for function parameters, simple and compound statements, imports, control flow, and indented suites.It includes function definitions with optional annotations and return types, while suites may contain a simple statement or indented statements.Source: §A.8.3 · pp. 41–42
• Python grammar excerpts define expression precedence, postfix calls, indexing and attribute access, and atom forms such as tuples, lists, dictionaries, names, and literals.The excerpts also include rules for comparisons, arithmetic, and subscripting.Source: §A.8.3 · p. 42

A.8.4 Go Grammar

• Go grammar excerpts describe source-file structure, including package and import clauses, declarations, function and method declarations, blocks, and statement forms.The listed statement forms include assignments, returns, conditionals, switches, and loops.Source: §A.8.4 · pp. 44–45
• Go productions define type-switch, select, and for statements, including case clauses, communication clauses, and range clauses.The excerpt also gives a receive-statement form and a go-statement form.Source: §A.8.4 · p. 45
• The type productions include array, pointer, interface, slice, map, and channel types.The excerpt also defines type names, function types, signatures, results, and parameters.Source: §A.8.4 · p. 45
• Expression productions cover primary and unary expressions, arithmetic and bitwise operators, comparisons, and logical conjunction.The grammar also defines disjunction as an expression-level production.Source: §A.8.4 · p. 46
• Literal productions distinguish basic literals from composite and function literals, and enumerate decimal, binary, octal, and hexadecimal integers.Source: §A.8.4 · p. 46