PaperlayerView exact revision on arXiv

Source-linked AI summary

Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation

Luca Beurer-Kellner, Marc Fischer, Martin Vechev

arXiv:2403.06988v1cs.LGcs.CL

TL;DR

Constrained decoding must enforce formal output constraints without disrupting an LLM’s subword tokenization, task accuracy, or generation speed. DOMINO addresses this with subword-aligned constrained decoding using pre-computation and speculative decoding. It matches or improves unconstrained accuracy while achieving substantial throughput gains over existing methods.

  • Problem

    Misalignment between LLM subword vocabularies and external constraints can impair task accuracy, while constrained decoding methods also incur generation overhead.

  • Method

    DOMINO enforces context-free grammars in a minimally invasive, subword-aligned manner using pre-computation and speculative decoding.

  • Results

    DOMINO achieves the best accuracy across all evaluated tasks, maintains or improves unconstrained accuracy, and accelerates inference by up to 2.71×.

  • Takeaways & Limitations

    Minimally invasive constrained decoding can provide valid structured generation with high accuracy and low or negative throughput overhead.

Abstract

from arXiv · show

To ensure that text generated by large language models (LLMs) is in an expected format, constrained decoding proposes to enforce strict formal language constraints during generation. However, as we show in this work, not only do such methods incur performance overhead during generation, but many of them also significantly impair task accuracy, if they do not correctly align the underlying LLM sub-word vocabularies with external constraints. To address this, we present a novel decoding algorithm, DOMINO, that can enforce constraints in a fully subword-aligned fashion, while leveraging pre-computation and speculative decoding to achieve virtually no overhead and in some cases even almost 2$\times$ speedup over unconstrained decoding -- thereby outperforming existing approaches by a wide margin.

1. Introduction

Constrained decoding enforces formal output constraints, but misalignment between LLM subword tokens and grammar terminals can distort generation, reduce accuracy, and add overhead. DOMINO addresses this with minimally invasive, efficient, subword-aligned decoding.

  • 1. Introduction: Constrained decoding guarantees syntactically valid outputs for formats such as templates, regular expressions, and context-free grammars.It can reduce reliance on ad-hoc parsing, retries, prompting, fine-tuning, or post-processing.
  • 1. Introduction: Misalignment between subword tokens and grammar terminals can force suboptimal tokens, diverge from unconstrained generation, and impair downstream reasoning.Bridge tokens may span multiple parser terminals, but computing them online can be costly.
  • 1. Introduction: The paper defines minimally invasive constraining as enforcing a grammar while intervening as little as possible during generation.This aims to preserve faithful, low-perplexity model output.
  • 1. Introduction: DOMINO combines subword-aligned grammar enforcement with pre-computation and speculative decoding for low-overhead generation.It is designed to avoid token misalignment while enforcing context-free grammars.
  • 1. Introduction: DOMINO is evaluated as minimally invasive, low-overhead, and often faster than unconstrained generation.The evaluation reports that it significantly outperforms other methods and can exceed unconstrained throughput in many cases.

2. Challenges of Constrained Decoding

Constrained decoding must balance expressive constraints, faithful tokenization, and inference efficiency. Existing approaches expose this trade-off through token misalignment, fixed templates, or costly online vocabulary checks.

  • 2. Challenges of Constrained Decoding: A constrained decoder updates a checker and applies a token mask at each step, with every rejected otherwise-selected token counted as an intervention.This operationalizes how constraining changes the decoding process.
  • 2. Challenges of Constrained Decoding: Naive constrained decoding can reduce JSON-encoded GSM8K accuracy from 41.5% to 30.8%, whereas minimally invasive constraining reaches 41.8%.The comparison uses five-shot Mistral 7B.
  • 2. Challenges of Constrained Decoding: Online parser-guided methods can support full context-free grammars and bridge tokens but may check the entire vocabulary at every step, causing high overhead.Regex-based methods are simpler to check and can use offline vocabulary pre-computation.
  • 2. Challenges of Constrained Decoding: Template-based decoding reduces model forward passes by inserting fixed tokens deterministically, but external tokenization can produce unnatural formatting and higher perplexity.Template-based outputs show perplexities of 24.50–26.75 versus 4.17 for unconstrained generation, while naturalizing the full output reaches 49.39.
  • 2. Challenges of Constrained Decoding: Token healing can improve transition-point tokenization, yet many templated tokens remain fixed and output differences persist.The limitation remains even when token healing is active.
  • 2. Challenges of Constrained Decoding: The central challenge is supporting regexes, context-free grammars, and templates while remaining minimally invasive and computationally efficient.These requirements motivate DOMINO.

3. Efficient Aligned Constrained Decoding

DOMINO aligns grammar terminals with LLM subword tokens through precomputed scanner structures and parser-guided traversal, enabling expressive constrained decoding with low inference overhead. Its subterminal trees and speculative prediction support legal-token masking while reducing online computation.

  • 3.2. Character Scanner: DOMINO separates CFG recognition into a parser for high-level structure and a scanner for terminal-level regular expressions, then dynamically coordinates their states during generation.The scanner alone accepts the broader regular-language superset, so parser state is needed to permit or reject transitions that preserve the CFG.
  • 3.2. Character Scanner: DOMINO constructs a character-level NFA by combining each terminal’s regular-expression automaton while retaining which terminal subautomaton each state represents.The construction adds epsilon transitions from terminal accepting states to a shared accepting state and from the shared start state to each terminal automaton.
  • 3.3. Vocabulary-Aligned Subterminal Tree: Subterminal trees align vocabulary tokens with partially or fully traversed terminal NFAs by classifying full, start, end, and continuation subterminals.For each scanner state and vocabulary token, DOMINO enumerates reachable subterminal sequences and stores them in a prefix tree.
  • 3.3. Vocabulary-Aligned Subterminal Tree: At inference time, DOMINO traverses the relevant subterminal trees and uses parser state to prune illegal continuations before producing the token mask.The lookahead parameter k controls traversal depth; k = 0 ensures CFG legality, while sufficiently large k admits all valid tokens eventually.
  • 3.5. DOMINO: Precomputing scanner states and subterminal trees reduces online work because the trees are smaller than the model vocabulary, while DOMINO can also extend to other constraints such as GUIDANCE programs.The method is described as enabling expressive constraining with far less overhead than fully online approaches.
  • 3.6. Speculative Decoding: DOMINO accelerates constrained decoding with a parser- and scanner-state-conditioned count model that proposes legal next tokens for speculative validation by the large LLM.The approach exploits predictable structured languages and can operate independently of, or jointly with, standard speculative decoding.

4. Experimental Evaluation

DOMINO is evaluated against constrained-decoding baselines on accuracy, throughput, and parameter sensitivity across multiple models, datasets, grammars, and inference backends. It achieves the strongest reported combination of task accuracy and efficiency, while lookahead and speculation affect performance by workload.

  • Setup: The evaluation covers Mistral 7B and Llama-2 13B, using transformers and llama.cpp on A100 or H100 GPUs with offline-known grammars.Accuracy is measured on GSM8K and CoNLL-2003, while throughput is tested across JSON, schema-driven JSON, C, XML, and regex-based workloads.
  • Task Accuracy: DOMINO achieves the best accuracy for all evaluated tasks and accelerates inference up to 2.71× over unconstrained generation.Its accuracy is the same as or better than unconstrained generation, whereas standard GUIDANCE loses up to 11 percentage points.
  • Parameter Study: DOMINO with infinite lookahead recovers and slightly exceeds unconstrained GSM8K accuracy, while lower k values significantly impair performance.Missing bridge tokens can force irregular whitespace behavior and prevent Llama-2 from producing object lists longer than one item.
  • Efficiency: Speculative decoding with s ∈{6, 8, 10} reaches 1.7× throughput for schema-driven JSON, whereas free-form JSON favors opportunistic masking with only 4.21% overhead.The speculation results use Mistral 7B and compare schema-driven with free-form JSON generation.
  • Efficiency: DOMINO outperforms GUIDANCE and llama.cpp online parsing, reaching up to 77% higher throughput than unconstrained generation on predictable grammars.The reported throughput excludes precomputation, which takes 1–5 seconds for tested grammars and about 20 seconds for C.
  • Efficiency: C generation has the highest overhead because its grammar is most complex, but DOMINO still runs at 0.78× versus llama.cpp at 0.74×.Speculation provides no benefit for C code under the simple count-based predictor.

5. Conclusion

The paper concludes that minimally invasive constrained decoding is needed for accurate, efficient grammar-constrained generation. DOMINO combines precomputation, speculative decoding, and opportunistic masking to provide no accuracy loss with often overhead-free or faster inference.

  • DOMINO implements minimally invasive grammar constraining through precomputation, speculative decoding, and opportunistic masking.The conclusion characterizes the resulting generation as often overhead-free or faster while preserving accuracy.

A. Whitespace-Flexible GUIDANCE Programs

Whitespace-flexible GUIDANCE replaces fixed template whitespace with an LLM-generated whitespace token, giving the model more formatting freedom. This improves task accuracy but substantially reduces inference efficiency.

  • A standard GUIDANCE program fixes the high-level JSON template and generates only field values, including constrained numeric and categorical fields.The example uses generation, regex, and select operations for different JSON fields.
  • Whitespace-flexible GUIDANCE replaces explicit templated whitespace with a {WS} token generated through zero_or_more selection of spaces or newlines.The approach leaves whitespace formatting to the LLM rather than fixing it in the template.
  • Whitespace-flexible GUIDANCE improves task accuracy but significantly increases inference time because the runtime must generate whitespace tokens explicitly.The experiments report higher accuracy alongside lower efficiency because the runtime cannot skip as many tokens.
  • Model-based retokenization computes an LLM-preferred tokenization of target text by greedily selecting the highest-likelihood vocabulary token that remains a prefix.Algorithm 3 repeatedly computes logits, selects an admissible token, appends it, and removes its prefix from the target.

B. Model-Based Retokenization

Model-based retokenization converts target text into the tokenization the model would prefer under a prompt. It exposes why fixed template tokens can be costly and poorly aligned with model generation.

  • Retokenization greedily re-encodes target text using vocabulary tokens that maximize sequence likelihood conditioned on the prompt.The resulting tokenization is the sequence the model would produce under arg max decoding while being masked to the target text.
  • Template-based constrained generation cannot directly use retokenization because computing it costs as much as generating all templated tokens from scratch.That overhead negates the efficiency benefit of using a template-based approach.

C. Grammars And Prompts

The experiments use formal grammars and task-specific prompts to constrain outputs for JSON, C programs, XML, fixed templates, and structured mathematical reasoning.

  • C. Grammars And Prompts: For GSM8K, the JSON reasoning grammar requires an answer number and a list of thoughts, each containing a step, calculation, and result.The experiments use five-shot prompts for questions from the GSM8K test split.
  • C. Grammars And Prompts: The XML grammar constrains person records with names, ages, jobs, salaries, and optional friends, using prompts describing people with or without friends.The grammar also defines job titles, salaries, names, numbers, and whitespace conventions.
  • C. Grammars And Prompts: The fixed-template grammar constrains RPG character profiles to required fields such as identity, attributes, equipment, class, mantra, strength, and three items.Prompts vary from generic character profiles to level 5 human or dwarf fighter descriptions.

D. Structured Reasoning Outputs

The constrained outputs represent reasoning and task answers in structured formats for GSM8K and CoNLL2003, making them straightforward to parse for downstream processing.

  • D. Structured Reasoning Outputs: Constrained outputs for GSM8K and CoNLL2003 are presented as structured task responses rather than unrestricted text.The section introduces prompted and constrained model outputs for both task settings.
  • D. Structured Reasoning Outputs: The GSM8K format represents reasoning as an array of thought objects containing steps, calculations, and numerical results.The example includes a calculation and result within the structured reasoning sequence.
  • D. Structured Reasoning Outputs: These outputs facilitate downstream processing because their structured format allows them to be parsed easily.The stated benefit applies in practice to the generated task outputs.
  • D. Structured Reasoning Outputs: Few-shot demonstrations alternate questions and answers in a simple repeated format.The demonstrations use a Q/A pattern for prompting.
Loading 2403.06988v1…