Source-linked AI summary
IterGen: Iterative Semantic-aware Structured LLM Generation with Backtracking
Shubham Ugare, Rohan Gumaste, Tarun Suresh, Gagandeep Singh, Sasa Misailovic
TL;DR
Structured LLM generation libraries lack backtracking, limiting mid-generation correction. ITERGEN uses grammar-symbol navigation and semantic checks to revise selected output; evaluations report improvements across SQL and Vega-Lite accuracy and privacy leakage.
Problem
Current structured-generation tools use left-to-right decoding without backtracking, while grammar-guided methods constrain syntax but do not ensure semantic properties.
Source: §1 · pp. 1–2Method
ITERGEN uses grammar symbols to navigate generation forward and backward, letting users check semantic properties and selectively resample violating fragments.
Source: §1 · p. 2Results
Across tasks, ITERGEN improves SQL and Vega-Lite accuracy and eliminates privacy leaks in LLM-generated text.
Source: §7 · p. 10Takeaways & Limitations
ITERGEN provides a framework for enforcing syntactic and semantic constraints during structured LLM generation.
Source: §7 · p. 10ITERGEN currently supports only single-sequence generation, not multiple-sequence generation in batch.
Source: §6 · p. 10
Abstract
from arXiv · showhide
Large Language Models (LLMs) are widely used for tasks such as natural language and code generation, but their outputs often suffer from issues like hallucination, toxicity, and incorrect results. Current libraries for structured LLM generation rely on left-to-right decoding without support for backtracking, limiting the ability to correct or refine outputs mid-generation. To address this, we introduce IterGen, a user-friendly library for iterative, grammar-guided LLM generation that enables users to move both forward and backward within the generated output based on grammar symbols. By leveraging a symbol-to-position mapping and maintaining the key-value (KV) cache state, IterGen ensures efficient and structured generation while allowing for corrections during the process. We demonstrate IterGen's effectiveness in two important applications: reducing privacy leakage in LLM outputs and improving the accuracy of LLM-generated SQL and Vega-Lite queries. Our code and additional resources are available at https://structuredllm.com.
1 INTRODUCTION
ITERGEN adds grammar-symbol navigation and semantic checks to structured LLM generation, allowing users to correct selected fragments instead of restarting. Its evaluation covers SQL and Vega-Lite accuracy and privacy leakage.
1 INTRODUCTION
- Prior grammar-guided methods enforce syntax but do not ensure properties such as defined-before-use variables or avoidance of harmful language.This motivates adding semantic checks beyond grammatical validity.Source: §1 · p. 1
- Grammar symbols provide an interpretable way to navigate generation, addressing tools’ inability to detect semantic violations or pause at intermediate points.Token-level backtracking does not identify which syntax caused a violation, and users often must otherwise restart from scratch.Source: §1 · p. 1
- ITERGEN lets users specify a context-free grammar and programmatically check and correct semantic properties by resampling violating fragments while preserving valid output.Navigation uses higher-level units such as statements or expressions rather than fixed token counts.Source: §1 · p. 2
- ITERGEN dynamically maps grammar symbols to positions in partially parsed output to navigate forward and backward despite model-token and grammar-token misalignment.It also stores generated-token history as a tree to avoid heuristically regenerating the same tokens.Source: §1 · p. 2
- SQL accuracy improves by 18.5% mean over the state-of-the-art grammar-guided technique; privacy leaks fall from 51.4% to 0%; Vega-Lite accuracy improves by 17.8%.These are the three scenarios reported in the evaluation.Source: §1 · p. 2
2 BACKGROUND
The background introduces language-model decoding and grammar-guided generation, then describes the gap between syntactic constraints and semantic properties. It also establishes the notation and parsing concepts used by ITERGEN.
2 BACKGROUND
- Σ is a finite character alphabet, Σ* is the set of strings over it, and S* denotes sequences formed from a set S.The empty string is denoted ϵ.Source: §2 · p. 2
2.1 LANGUAGE MODELS
- An autoregressive language model tokenizes a prompt, maps the token sequence to vocabulary scores, and samples the next token from the resulting probability distribution.Decoding repeats until EOS or another stopping condition; greedy, sampling, and beam-search strategies are among the options described.Source: §2.1 · p. 2
- Constrained masking excludes disallowed tokens at a position by applying a use-case-specific mask to the vocabulary probabilities.The mask marks viable tokens with 1 and discarded tokens with 0.Source: §2.1 · p. 3
2.2 GRAMMAR-GUIDED GENERATION
- A context-free grammar specifies strings through production rules, while an LR parser incrementally analyzes input using shift and reduce operations.Constrained grammar-guided generation uses parser results to filter tokens that would make output syntactically invalid.Source: §2.2 · p. 3
3 ITERATIVE STRUCTURED GENERATION
ITERGEN uses grammar symbols to navigate structured LLM generation in both directions. Its interface supports inspecting, extending, and revising output, while its parser-based position map, decoding trace, and KV-cache management support that navigation.
3 ITERATIVE STRUCTURED GENERATION
- ITERGEN introduces forward and backward navigation through generation using grammar symbols, addressing semantic violations without requiring a full restart.The section presents an interface and algorithm for enabling this navigation.Source: §3 · p. 3
3.1 ITERGEN INTERFACE
- Forward generates until a specified number of terminal or nonterminal symbols appears; backward removes output through a specified number of such symbols.View inspects the partial generation associated with a grammar symbol, helping users check properties before backtracking.Source: §3.1 · pp. 3–4
- The example grammar treats paragraph and sentence as nonterminals and punctuation such as ., !, and ? as terminals.The interface can stop at a sentence, backtrack by two words, or return the generated words for inspection.Source: §3.1 · p. 4
3.2 ITERGEN ALGORITHM
- Forward appends output until the requested number of stop symbols is reached or a termination condition, such as EOS, stops generation earlier.Backward returns the longest prefix remaining after removing the requested symbol occurrences, returning to the initial prompt if too few occur.Source: §3.2 · pp. 4–5
- An incremental LR parser updates a symbol-position map on reductions, recording each reduced symbol’s start and end positions from its component symbols.The map enables counting grammar-symbol occurrences and locating spans in generated output.Source: §3.2 · p. 5, Figure 2 · p. 5
- A token-tree decoding trace preserves generation history for forward and backward navigation, while a recurrence penalty discourages repeatedly selecting backtracked tokens.ITERGEN also keeps the KV cache coherent across navigation to avoid repeating the cache prefill step.Source: §3.2 · pp. 5–6
4 EVALUATION
The evaluation presents ITERGEN applications for SQL generation, privacy protection, and Vega-Lite specification generation. Across these case studies, it tests semantic constraints and reports gains over relevant baselines.
4 EVALUATION
- The evaluation uses three case studies to demonstrate semantic-constrained decoding for SQL, privacy leakage, and Vega-Lite generation.The implementation also supports other languages, including a large fragment of Python.Source: §4 · p. 6
4.1 SQL GENERATION
- For SQL, ITERGEN checks generated table and column names against the schema and backtracks before invalid names; max_iter bounds retries.The study uses Spider and compares against unconstrained STANDARD generation and SYNCODE, which ensures syntax but not other execution errors.Source: §4.1 · pp. 6–7
- 41.63% overall SQL accuracy and 75.84% execution success for ITERGEN, versus 28.9% and 50.28% for STANDARD and 35.22% and 63.72% for SYNCODE.Table 1 compares methods across models on accuracy, execution success, token count, and generation time.Source: Table 1 · p. 7, §4.1 · p. 7
4.2 PRIVACY LEAKAGE
- The privacy study defines a leak as output containing sensitive data from pretraining and evaluates email extraction on the Enron corpus.The corpus contains roughly 600,000 emails between Enron employees.Source: §4.2 · p. 8
- ITERGEN preserved privacy with 100% success, with small increases in average completion time, generated tokens, and response perplexity.The reported overhead mostly comes from discarded tokens during backtracking and minor processing delays.Source: §4.2 · p. 8, Table 2 · p. 8
4.3 VEGA-LITE
- Vega-Lite constraints check field names, field-type compatibility, and allowed aggregations; for type checks, backtracking occurs before the type value.The evaluation uses 814 NLV examples paired with Vega-Lite specifications.Source: §4.3 · p. 9
- ITERGEN significantly improved validation and accuracy over SYNCODE across all evaluated models; for Llama-3-8B, accuracy was 30.5% versus 24.7%.For Qwen2.5-1.5B, ITERGEN's average validity was 46.6%, compared with SYNCODE's 44.5%.Source: §4.3 · p. 9, Table 3 · p. 9
5 RELATED WORK
Related work includes grammar-guided decoding, semantic-constraint methods, and tools with related navigation or generation features. ITERGEN is distinguished by grammar-symbol navigation and user-defined semantic constraints across grammars.
5 RELATED WORK
- Grammar-guided tools such as GCD, OUTLINES, DOMINO, SYNCODE, and AICI constrain syntax, while the passage contrasts them with ITERGEN's semantic constraints.Language-server methods enforce some semantic constraints but lack syntactic-accuracy guarantees and depend on server availability and performance.Source: §5 · pp. 9–10
- GUIDANCE lacks backtracking and constrains generated holes with regular expressions, while ITERGEN supports forward and backward operations over grammar symbols.ITERGEN accepts standard Lark EBNF grammars, including large grammars such as SQL; GUIDANCE offers string insertion and function-call features outside this paper's scope.Source: §5 · p. 10
- SYNCHROMESH uses predictive masking and rejection sampling at token level; ITERGEN instead targets intuitive, grammar-general programs for semantic constraints.PICARD adds SQL table and column constraints but is T5-only, preventing an empirical comparison to ITERGEN; the authors also report an unofficial SYNCHROMESH implementation errored on complex Lark grammars.Source: §5 · p. 10
- ITERGEN is a building block in CRANE, which combines constrained decoding with unconstrained reasoning for symbolic reasoning benchmarks such as GSM-symbolic and FOLIO..Source: §5 · p. 10
6 LIMITATIONS
The paper identifies limits in batched generation support and in its recurrence-penalty heuristic.
6 LIMITATIONS
- ITERGEN supports only single-sequence generation, and its recurrence-penalty heuristic can skew the model distribution at the first token.Supporting batches requires careful grammar synchronization, especially when backtracking only one sequence.Source: §6 · p. 10
7 CONCLUSION
IterGen supports grammar-symbol-based iteration over structured LLM outputs and reports gains across text-SQL, privacy protection, and Vega-Lite generation.
7 CONCLUSION
- ITERGEN uses BNF grammar symbols to provide intuitive, bidirectional iteration over LLM generation of structured outputs.The conclusion frames bidirectional iterators as a familiar programming-language capability brought to LLM generation.Source: §7 · p. 10
- 18.5% mean improvement over existing state-of-the-art techniques for text-SQL and 17.8% improvement in Vega-Lite specification accuracy are reported.The conclusion also reports fully eliminating privacy leaks in LLM-generated text.Source: §7 · p. 10
- Enforcing syntactic and semantic constraints is presented as advancing LLM-output reliability.The stated future scope includes expressing and enforcing complex semantic properties in code, documents, and natural language during generation with open-source LLMs.Source: §7 · p. 10
A.1.1 ALGORITHM 1: START FUNCTION
The start function initializes an ITERGEN session from a prompt, setting up the state needed for subsequent generation.
A.1.1 ALGORITHM 1: START FUNCTION
- START initializes the decoding trace, KV cache, symbol-position map, and parser, stores the prompt, and tokenizes it.These are the session components and prompt-processing steps described for initialization.Source: §A.1.1 · p. 14
- The function takes an ITERGEN object and input prompt string O0.The object contains the model and tokenizer.Source: §A.1.1 · p. 14
A.1.2 ALGORITHM 2: FORWARD FUNCTION
The forward function generates tokens under grammar constraints until a specified symbol count or token-length limit is reached, then returns the output string.
A.1.2 ALGORITHM 2: FORWARD FUNCTION
- FORWARD repeatedly scores tokens, updates the parser from partial output, masks disallowed tokens, and applies a recurrence penalty to previously generated tokens.The function returns when the requested stop-symbol count is reached, the token limit is exceeded, or the model emits EOS.Source: §A.1.2 · p. 14
- The function accepts a stop symbol, occurrence count, maximum token limit, and recurrence penalty γ, and returns string On.The recurrence penalty is specified as ranging from 0 to 1.Source: §A.1.2 · p. 14
A.1.3 ALGORITHM 3: BACKWARD FUNCTION
The backward function returns a prefix ending at a selected grammar-symbol occurrence and resets session state to that point.
A.1.3 ALGORITHM 3: BACKWARD FUNCTION
- BACKWARD finds the requested symbol position, truncates the output there, crops the KV cache, and updates the symbol-position map and current tokens.The function takes a stop symbol and a number of symbols to backtrack, then returns the backtracked output string Om.Source: §A.1.3 · p. 15
- The function accepts a stop symbol and the number of occurrences to backtrack, returning string Om.It identifies the corresponding token index so session state can be aligned with the selected character position.Source: §A.1.3 · p. 15
A.2 ADDITIONAL DETAILS FOR VEGA-LITE CASE STUDY
These appendices provide additional details on IterGen’s case studies, ablations, and privacy-protection mechanics and limitations. They also specify the SQL and Vega-Lite grammars, including supported SQL constructs and the structure and values of visualization specifications.
A.2 ADDITIONAL DETAILS FOR VEGA-LITE CASE STUDY
- In the Vega-Lite case study, many tasks require multiple backward calls, and Figure 4 shows successful generations left of the 50-iteration limit.The privacy evaluation uses 100 DecodingTrust Enron email-extraction problems with 5-shot prompts; its leak value counts prompts revealing a correct email from the original dataset.Source: §A.2 · p. 15, Figure 4 · p. 15, §A.3 · p. 16
A.3 ADDITIONAL DETAILS FOR PRIVACY LEAKAGE CASE STUDY
- For privacy protection, ITERGEN generates one EMAIL terminal at a time, checks it with view, and backtracks before any valid employee email so generation can retry.The experiment disallows exact corpus emails, but the simple matching function may still permit private email fragments; more critical applications can use a more comprehensive matcher.Source: §A.3 · p. 16
A.4 REJECTION SAMPLING BASELINE
- ITERGEN exceeds SYNCODE pass@2 and pass@3 with greedy SQL decoding, while SYNCODE pass@5 is higher but uses roughly five times more tokens; ITERGEN also outperforms rejection-sampling baselines on privacy and Vega-Lite tasks.For privacy, the comparison covers leak rates and generated-token counts; for Vega-Lite, ITERGEN’s score is consistently higher than rejection-sampling pass@k scores.Source: §A.4 · p. 17, Table 4 · p. 17, Table 5 · p. 17
A.5.1 AVERAGE NUMBER OF FORWARD/BACKWARD CALLS FOR SQL CASE STUDY
- The SQL forward/backward-call analysis reports average forward steps, backward steps, and max_iter threshold hits across models evaluated on 1,034 SQL problems.The supplied passage describes Table 7’s reported statistics but does not provide their values.Source: §A.5.1 · p. 18, Table 7 · p. 18
A.5.3 ABLATION STUDY ON RECURRENCE PENALTY γ
- On Spider with Qwen2.5-0.5B, accuracy stays around 0.34 at higher recurrence penalties but falls to 0.28 with γ = 0.0, while validity increases slightly and tokens and response time vary minimally.γ = 0 is equivalent to no recurrence penalty.Source: §A.5.3 · p. 18, Table 9 · p. 19
A.5.4 ABLATION STUDY ON PROMPTING LLM WITH EXECUTION FEEDBACK
- On Spider’s first 400 problems with Qwen2.5-0.5B, ITERGEN outperforms STANDARD and SYNCODE even with compiler feedback, although execution feedback improves accuracy while substantially increasing tokens and time.The ablation gives the first response’s execution error to the model when that response fails.Source: §A.5.4 · p. 19, Table 10 · p. 19
A.5.5 ABLATION FOR MAX NEW TOKENS AND M A X_I T E R
- For ITERGEN, execution success reaches 68.57% at 200 tokens and 30 iterations, while execution time rises from 0.54s at 50 tokens and 10 iterations to 1.02s at 200 tokens and 30 iterations.Increasing max_iter improves accuracy and execution success with diminishing returns beyond 20 iterations; for SYNCODE, gains in execution accuracy and success plateau beyond 150 tokens, while execution time rises from 0.43s at 50 tokens to 0.94s at 200 tokens.Source: §A.5.5 · p. 20, Table 12 · p. 20, Table 11 · p. 20
A.6 SQL ERROR ANALYSIS FOR SYNCODE VS ITERGEN
- In the cited examples, ITERGEN queries use templates, teacher, and dogs, while SYNCODE produces nonexistent-table errors for cre_Doc_Template_Mgt and course_teach and an invalid-column error for dogs.Source: §2 · p. 20, §3 · p. 21, §7 · p. 21
A.9.2 SQL GRAMMAR
- The SQL grammar defines casts, aggregations and ranking, window forms, arithmetic expressions, comparisons, filtering, literals, and date/time expressions.Its productions include window partitioning and ordering, Boolean and IN predicates, and timestamp expressions such as NOW() and TODAY().Source: §A.9.2 · pp. 24–26
A.9.3 VEGA-LITE GRAMMAR
- The Vega-Lite grammar defines specifications with schema, data, mark, encoding, and other properties, plus nested objects, arrays, values, and mark types.Allowed mark types include bar, circle, line, area, geoshape, and text.Source: §A.9.3 · pp. 26–27