NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints

1 Introduction

• Recipe generation must include specified ingredients and avoid unrequested ones, illustrating how semantic requirements can be represented as lexical constraints.For example, a recipe using garlic, steak, and soy sauce should not introduce pork or beans.Source: §1 · p. 1
• Fine-tuning is under-specified: increasing GPT-2’s data tenfold yields only modest constraint-satisfaction improvement with standard beam search, as likelihood gains may reflect dataset-specific style instead.A GPT-2 model finetuned on hundreds of thousands of recipes still hallucinates extra ingredients.Source: §1 · p. 2
• NeuroLogic Decoding controls generation to satisfy any predicate-logic constraints, including positive, negative, and combined requirements, without changing the model or training pipeline.It converts hard constraints into a soft penalty in the decoding objective, uses beam-based search for approximately optimal satisfying outputs, and tracks constraint states to reuse computation.Source: §1 · p. 2
• Across four tasks, NeuroLogic Decoding ensures constraint satisfaction while maintaining high generation quality, achieving new SOTA results in supervised and zero-shot settings.The tasks are CommonGen, recipe generation, data-grounded dialogue response generation, and gender-bias reduction in machine translation.Source: §1 · p. 2

2.1 Predicate Logic Constraint

• NEUROLOGIC represents phrase presence or absence as positive or negative literals in CNF clauses, which express any propositional formula, and seeks high-likelihood sequences satisfying every clause.A phrase may be a unigram or multi-gram; the beam-based search approximates the objective balancing sequence likelihood and constraint satisfaction.Source: §2.1 · pp. 2–3

2.2 Constraint States

• Clauses occupy four reversible or irreversible satisfaction states; prefix tries track reversible unsatisfied positive literals and satisfied negative literals, while irreversible states need no tracking.A clause with only negative literals that remains unsatisfied is irreversible, whereas a satisfied clause containing a positive literal stays satisfied.Source: §2.2 · p. 3

2.3 Algorithm

• Each decoding step prunes irreversibly unsatisfied candidates and those outside likelihood and constraint top tiers, then groups survivors by irreversibly satisfied clauses to preserve partial-solution diversity.The top-tier thresholds are adjustable parameters controlling tolerance for sequence fluency and constraint satisfaction.Source: §2.3 · p. 3
• Within each group, candidates are scored by likelihood with a partial reward for matched prefixes of positive literals, then selected in rounds until the beam is full, favoring groups with higher top scores.The final hypothesis is the highest-scoring candidate among those with the maximum number of satisfied clauses.Source: §2.3 · p. 4

3 Related Work

• NeuroLogic supports full CNF predicate-logic constraints, searches efficiently and diversely, and runs in O(Nk), independent of constraint count C.Here N is sequence length and k is beam size; runtime counts calls to the deep generator, the most expensive decoding operation.Source: §3 · p. 4, §3.1 · p. 4

3.1 Previous Constrained Decoding Approach

• Anderson et al. (2017)’s constrained beam search tracks all 2^C satisfaction states and has O(Nk2^C) complexity, making many applications infeasible.Source: §3.1 · p. 4
• Hokamp and Liu (2017)’s grid beam search runs in O(NkC) but can harm language quality; Post and Vilar (2018)’s dynamic allocation retains that issue, sometimes worsening it.Hu et al. (2019a) made dynamic beam allocation GPU-efficient, but fewer hypotheses at each step can further reduce quality.Source: §3.1 · pp. 4–5
• Miao et al. (2019)’s CGMH and Sha (2020)’s gradient-guided editing avoid runtime dependence on constraint count but may be inefficient and sensitive to initialization or edits.CGMH inserts positive keywords in random order and samples replacement, insertion, or deletion edits; Sha (2020) uses objective gradients to guide edits.Source: §3.1 · p. 5

3.2 Applications of Constrained Generation

• Lexical constraints support translation, paraphrase generation, image captioning, and response generation, including terminology, source-word exclusion, object grounding, and semantic correctness.Examples include terminology constraints in translation (Hasler et al., 2018; Dinu et al., 2019), paraphrase generation (Hu et al., 2019a; Kajiwara, 2019; Hu et al., 2019b; Miao et al., 2019), image captioning (Anderson et al., 2017; Ren et al., 2015; Krause et al., 2016), and response generation (Balakrishnan et al., 2019).Source: §3.2 · p. 5

4 Experiments I: Constrained Commonsense Generation

• COMMONGEN requires a grammatical sentence describing an everyday scenario that uses all concepts from an unordered set, with correct morphological inflections.The benchmark is designed to test generative commonsense reasoning.Source: §4 · p. 5

4.2 Results II: NeuroLogic across Different Supervised Models

• Across supervised language models, NeuroLogic improves constraint satisfaction and generation quality on every model and metric, with especially large gains for weaker models or architectures.The models are supervised on COMMONGEN; Table 2 compares conventional beam search with NeuroLogic decoding.Source: Table 2 · p. 6, §4.2 · p. 7

4.1 Results I: NeuroLogic vs Other Decoding Methods

• NeuroLogic outperforms prior constrained and unconstrained decoding methods on every metric, improving both concept coverage and generation quality with supervised GPT-2.The reported metrics include ROUGE, BLEU, METEOR, CIDEr, and SPICE.Source: Table 4 · p. 6, §4.1 · p. 6

4.4 Results IV: Ablation

• Even with 100% of training data, supervised GPT-2 does not reliably learn COMMONGEN constraints and is outperformed in coverage by zero-shot GPT-2 with NeuroLogic.Figure 4 compares supervised GPT-2 using NeuroLogic with conventional beam search as training data increases.Source: Figure 4 · p. 7, §4.4 · p. 7
• Unsupervised models using NeuroLogic become comparable to supervised models using NeuroLogic, and smaller unsupervised models often outperform larger supervised models using conventional beam search.The comparison spans GPT-2 model sizes; NeuroLogic also considerably boosts performance over conventional beam search regardless of model size.Source: Figure 5 · p. 7, §4.4 · p. 7

4.3 Results III: NeuroLogic with Unsupervised Models

• The zero-shot experiment tests unsupervised pretrained language models with and without domain adaptation; unconstrained decoding provides no controllability.Table 3 presents the zero-shot constrained-generation comparison before and after domain adaptation.Source: Table 3 · p. 6, §4.3 · p. 7

Problem Formulation

• The task is to generate multi-step cooking instructions from a dish name and unordered ingredients, including every given ingredient and no others.Ingredient phrases can contain one or multiple words, and generic terms may refer to specific ingredients.Source: §5 · pp. 7–8

Result

• NeuroLogic outperforms all baselines on every metric, nearly covering all given ingredients while excluding others and improving controllability and generation quality without extra computational cost.Table 5 reports results on the Recipe1M+ test set; Coverage measures the percentage of given ingredients covered, and Extra measures hallucinated ingredients relative to the given ingredients.Source: Table 5 · p. 8, §5 · p. 8

Dataset, Approach and Baseline

• RecipeGPT is a GPT-2 model fine-tuned on Recipe1M+, evaluated against beam search, sampling, and prior constrained decoding methods using generation metrics and ingredient coverage and hallucination measures.Recipe1M+ contains over one million recipes; recipes average 118 words and nine ingredients.Source: §5 · p. 8

Problem Formulation

• Responses must convey every supplied attribute-value fact in natural-language form, using simple templates to express the facts.The input consists of a query type and an unordered set of facts; for example, accepts_credit_cards="no" becomes “doesn’t accept credit cards.”Source: §6 · p. 8

Dataset, Approach and Baseline

• Evaluation uses the hotel and restaurant dialogue corpus with 8 query types and 12 attribute types, comparing against finetuned GPT-2, BART, and T5 with vanilla beam search and Kiddon et al. (2016).The experiments use the same train-dev-test split as Wen et al. (2016).Source: §6 · pp. 8–9
• Because finetuned seq2seq models may fail on new query or attribute types, the approach prompts pretrained GPT-2 by query type and uses NeuroLogic Decoding to enforce the facts.This is the paper’s zero-shot dialogue-generation setup.Source: §6 · pp. 8–9

Results

• Zero-shot generation with NeuroLogic Decoding outperforms or matches supervised baselines for dialogue response generation.The authors argue that this can avoid massive finetuning and its extra computational cost.Source: §6 · p. 9

Experiment IV: Reducing Gender Bias in Machine Translation

• The task translates English scenarios into German or French, using coreference-linked gender pronouns to constrain entities to their correct female or male inflections.The input describes human entities identified by roles; constraints require the correctly gendered entities to appear in the translation.Source: §7 · p. 9
• The evaluation uses Stanovsky et al. (2019)’s dataset, built over the Winogender and Wino-Bias English-only coreference gender-bias studies.The passage identifies Winogender as Rudinger et al. (2018) and Wino-Bias as Zhao et al. (2018).Source: §7 · p. 9
• 30.5 percentage for German and 28.0 percentage for French: NeuroLogic Decoding increases correct-gender accuracy, with the baseline model reaching 91% versus Microsoft Translator’s 74.1% German best.With ground-truth gender markers, performance increases by an additional 4% for German and 8.9% for French.Source: §7 · p. 9
• NeuroLogic Decoding reduces performance difference ∆S between stereotypical and non-stereotypical gender roles, indicating less reliance on gender stereotypes.The diagnostic results report a significant decrease in ∆S.Source: §7 · p. 9

• NeuroLogic Decoding is an efficient, general method for generating text with arbitrary predicate-logic constraints.Source: §8 · p. 9
• The method was applied intuitively to four different tasks as an extension to existing models.Source: §8 · p. 9
• These applications showed broad and consistent improvement to decoding quality.Source: §8 · p. 9
• For coreference resolution on English Winograd-schema examples, the authors used a RoBERTa model fine-tuned on the Winograd Schema Challenge, with 78.4% accuracy.Source: §8 · p. 9

• Figure 6 shows CommonGen generation examples across supervised and zero-shot settings, both with and without NeuroLogic Decoding.Source: Figure 6 · p. 12