Source-linked AI summary
NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints
Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula, Yejin Choi
TL;DR
Conditional generation needs reliable lexical constraint satisfaction, but finetuned language models often fail even with substantial task-specific data. NeuroLogic Decoding enforces predicate-logic constraints during inference and improves decoding across four tasks, including supervised and zero-shot settings. Its runtime analysis counts deep-generator calls while excluding auxiliary bookkeeping.
Problem
Finetuned language models often fail to follow lexical constraints reliably, even when trained on large task-specific datasets.
Method
NeuroLogic Decoding converts arbitrary predicate-logic lexical constraints into decoding penalties and uses beam-based search with constraint-state tracking.
Results
NeuroLogic Decoding produces broad and consistent improvements across four tasks, including new state-of-the-art results in supervised and zero-shot settings.
Takeaways & Limitations
Inference-time decoding algorithms can provide a practical alternative for fine-grained controllable generation without modifying model structure or training.
Takeaways & Limitations
Runtime analysis measures the number of deep-generator calls and excludes auxiliary bookkeeping costs.
Abstract
from arXiv · showhide
Conditional text generation often requires lexical constraints, i.e., which words should or shouldn't be included in the output text. While the dominant recipe for conditional text generation has been large-scale pretrained language models that are finetuned on the task-specific training data, such models do not learn to follow the underlying constraints reliably, even when supervised with large amounts of task-specific examples. We propose NeuroLogic Decoding, a simple yet effective algorithm that enables neural language models -- supervised or not -- to generate fluent text while satisfying complex lexical constraints. Our approach is powerful yet efficient. It handles any set of lexical constraints that is expressible under predicate logic, while its asymptotic runtime is equivalent to conventional beam search. Empirical results on four benchmarks show that NeuroLogic Decoding outperforms previous approaches, including algorithms that handle a subset of our constraints. Moreover, we find that unsupervised models with NeuroLogic Decoding often outperform supervised models with conventional decoding, even when the latter is based on considerably larger networks. Our results suggest the limit of large-scale neural networks for fine-grained controllable generation and the promise of inference-time algorithms.
1 Introduction
Constrained generation requires outputs to include or exclude specified words, but finetuned language models often fail to satisfy these requirements reliably. NeuroLogic Decoding enforces predicate-logic lexical constraints during decoding and improves results across four generation tasks.
- Motivation: Finetuned language models can violate lexical constraints even with hundreds of thousands of task-specific examples.A GPT2 recipe generator still hallucinates extra ingredients despite extensive finetuning.
- Motivation: Increasing GPT2 finetuning data by an order of magnitude yields only modest constraint-satisfaction gains with standard beam search.
- Approach: NeuroLogic Decoding controls generation at inference time to satisfy positive, negative, and logically combined lexical constraints.It searches for likely sequences among outputs satisfying the specified constraints without modifying model structure or training.
- Evaluation: NeuroLogic Decoding is evaluated on generative commonsense reasoning, recipe generation, data-grounded dialogue, and gender-bias reduction in machine translation.
- Results: NeuroLogic Decoding achieves new state-of-the-art results in both supervised and zero-shot settings while maintaining constraint satisfaction and generation quality.
2 Method
The method represents lexical requirements as predicate-logic constraints and searches for likely sequences that satisfy them. It combines penalty-based objectives with state tracking, pruning, grouping, and selection to approximate constrained optimization efficiently.
- Predicate Logic Constraint: NeuroLogic accepts predicate-logic constraints in conjunctive normal form, where literals require key phrases to appear or be omitted.Because propositional formulas can be converted to CNF, the method can handle arbitrary predicate-logic formulas.
- Objective: The decoding objective balances sequence likelihood against penalties for violated clauses.
- Constraint States: Clause tracking distinguishes reversible and irreversible satisfaction or unsatisfaction during generation.Two prefix tries track relevant positive and negative literals so computation can be reused efficiently.
- Pruning: At each time step, beam candidates receive constraint states, after which pruning removes irreversibly unsatisfied candidates and filters by likelihood and satisfied clauses.The α and β parameters control tolerance for fluency and constraint satisfaction.
- Grouping and Selection: Grouping preserves diverse partial constraint solutions, while selection ranks candidates by likelihood and matched prefixes before filling the beam.The final hypothesis is chosen from candidates with the maximum number of satisfied clauses.
3 Related Work
Prior constrained-decoding methods trade off constraint expressivity, search quality, and runtime. NeuroLogic Decoding addresses these limitations by supporting arbitrary predicate-logic constraints with beam-search-equivalent asymptotic runtime.
- NeuroLogic Decoding: NeuroLogic Decoding handles the full scope of CNF constraints, whereas previous methods typically support only conjunctions.
- NeuroLogic Decoding: Its O(Nk) runtime is constant with respect to the number of constraints C, unlike constrained beam search’s O(Nk2^C) complexity.N is sequence length and k is beam size; runtime counts calls to the deep generator.
- Comparison: Table 1 compares decoding methods by expressivity and runtime across AND, Positive Set AND, and Predicate Logic Formula constraints.The table defines Predicate Logic Formula as any combination of positive and negative constraints and notes that editing steps E usually exceed sequence length N.
- Previous constrained decoding: Grid beam search reduces runtime to O(NkC) but greedily favors constraint satisfaction, collapses search diversity, and can reduce language quality.Dynamic beam allocation removes GBS’s explicit dependence on C but retains its language-quality issue.
- Applications: Lexically constrained decoding supports applications including translation, paraphrase generation, image captioning, and response generation.
4 Experiments I: Constrained Commonsense Generation
COMMONGEN evaluates whether generated sentences use all input concepts while remaining grammatical and coherent. Across supervised, unsupervised, and decoding-method comparisons, NeuroLogic improves constraint satisfaction and generation quality over conventional and prior decoding approaches.
- Task: COMMONGEN asks models to generate a grammatical sentence describing a common scenario using all supplied object and action concepts with appropriate morphological inflections.
- Constraints: Concept coverage treats an input concept as satisfied when any of its morphological inflections appears in the generated sentence.
- Evaluation: The evaluation uses pretrained models fine-tuned on COMMONGEN and compares conventional beam search with NeuroLogic decoding across standard generation metrics and concept Coverage.
- Results: NeuroLogic outperforms previous constrained and unconstrained decoding methods across all reported metrics, improving both constraint satisfaction and generation quality.Prior constrained methods achieve high constraint satisfaction at a generation-quality cost, whereas NeuroLogic improves both dimensions.
- Results: NeuroLogic improves performance across supervised models and metrics, with especially substantial gains when model capability or pretraining is less effective.
- Results: In model-size comparisons, unsupervised models using NeuroLogic become comparable to supervised NeuroLogic models and often outperform larger supervised models using conventional beam search.
5 Experiments II: Recipe Generation
Recipe generation tests whether a model can produce cooking instructions from a dish title and ingredient set while controlling which ingredients appear. NeuroLogic improves both ingredient control and generation quality over the evaluated baselines.
- Task: Recipe generation takes a dish title and unordered ingredient set as input and produces a paragraph describing multi-step cooking instructions.
- Constraints: NeuroLogic constrains recipes to include every given ingredient while excluding ingredients outside the input set.Generic terms may refer to specific ingredients, such as vegetables referring to onions or carrots.
- Evaluation: RecipeGPT is evaluated on Recipe1M+ against beam search, sampling, and prior constrained decoding methods using generation, ingredient Coverage, and Extra metrics.Recipe1M+ contains over one million cooking recipes, and Extra measures hallucinated ingredients relative to given ingredients.
- Results: NeuroLogic outperforms all baselines on every reported metric, with especially large gains in coverage of given ingredients and reduction of extra ingredients.
- Results: NeuroLogic covers almost all given ingredients without using other ingredients, while boosting controllability and generation quality without extra computational cost.
6 Experiments III: Data-Grounded Dialogue Response Generation
This experiment targets zero-shot dialogue generation by forcing supplied facts into natural-language responses. NeuroLogic Decoding outperforms or matches supervised baselines, suggesting pretrained language models can generate constrained responses without massive task-specific finetuning.
- Problem Formulation: The task generates natural-language responses from a query type and an unordered set of factual attribute-value pairs.Given facts must appear in the response in proper natural-language form, using simple templates for conversion.
- Dataset, Approach and Baseline: The evaluation uses a hotel and restaurant dialogue corpus with 8 query types and 12 attribute types.The study follows the train-dev-test split from Wen et al. (2016) and compares against finetuned GPT-2, BART, T5, and prior state of the art.
- Dataset, Approach and Baseline: Standard finetuned seq2seq models struggle when users provide new query or attribute types, motivating zero-shot dialogue generation.The experiment uses a hand-crafted query-type prompt with pretrained GPT2 and applies NeuroLogic Decoding to include the facts.
- Results: Zero-shot generation with NeuroLogic Decoding outperforms or matches supervised baselines.The result suggests pretrained language models can support powerful constrained dialogue generation without massive finetuning or extra computational cost.
7 Experiment IV: Reducing Gender Bias in Machine Translation
This experiment constrains machine translation to use gender-appropriate target-language inflections inferred from English entities. NeuroLogic Decoding substantially improves gender accuracy and reduces reliance on stereotypical gender roles.
- Problem Formulation: The task translates English scenarios into German or French with correct gender inflections for identified human entities.The input contains role-identified entities, and the desired translation uses the appropriate target-language gender forms.
- Problem Formulation: Gender indicators are obtained through coreference resolution, and correctly gendered entity forms are constrained to appear in the output.Female and male inflections are specified for entities associated with female and male characters.
- Dataset: The dataset is adapted from English-only coreference gender-bias studies, including Winogender and Wino-Bias.The experiment follows the task setup and dataset of Stanovsky et al. (2019).
- Results: 30.5 percentage points for German and 28.0 percentage points for French are the accuracy increases from NeuroLogic Decoding with inferred gender markers.With ground-truth gender markers, performance increases by an additional 4% for German and 8.9% for French.
- Results: 91% accuracy is achieved by the baseline model with NeuroLogic Decoding, exceeding the best reported commercial translation result of 74.1% accuracy.The best commercial result was Microsoft Translator for German; the diagnostic results also show reduced performance differences between stereotypical and non-stereotypical roles.
8 Conclusion
The paper concludes that NeuroLogic Decoding is an efficient, general method for generation under arbitrary predicate-logic constraints. Across four tasks, it produces broad and consistent improvements in decoding quality.
- Conclusion: NeuroLogic Decoding is an efficient and general method for generating text with arbitrary predicate-logic constraints.The conclusion presents it as an extension to existing models rather than a task-specific generation system.
- Conclusion: Across 4 different tasks, NeuroLogic Decoding shows broad and consistent improvement to decoding quality.The paper demonstrates intuitive applications of the method across multiple generation settings.
- Conclusion: The gender-bias experiment uses an off-the-shelf coreference resolution model with 78.4% accuracy to infer gender markers.This implementation detail defines one assumption in the translation application.
Concept-Set {lose, board, balance, fall, ride}
The figure presents generation examples for the concept set {lose, board, balance, fall, ride}, comparing models with and without NeuroLogic Decoding in supervised and zero-shot settings.
- Concept-Set {lose, board, balance, fall, ride}: The displayed outputs include GPT-2, UniLM, BART, and T5 generations for the concept set.The examples differ in how they describe losing balance, falling, riding, and a board.
- Concept-Set {lose, board, balance, fall, ride}: Generation examples compare different models in supervised and zero-shot settings, with and without NeuroLogic Decoding.The examples are shown for COMMONGEN.
- Concept-Set {lose, board, balance, fall, ride}: The figure is intended to compare model generations with and without NeuroLogic Decoding rather than report a numerical metric.No outcome beyond the example generations is stated in the supplied figure text.