TL;DR
Enforcing specific grammatical structures in language model outputs is notoriously difficult, and even state-of-the-art models like GPT-4 fail when guided by prompting alone. This paper introduces a method that treats syntactic control as a posterior inference problem, combining Sequential Monte Carlo (SMC) sampling with a neural syntactic tagger. This approach boosts structural accuracy (F1 score) from as low as 12% up to over 93% in smaller models like GPT2-large and Llama3-8B, without sacrificing text fluency.
What Problem Does This Paper Address?
Large language models (LLMs) excel at generating fluent text, but guiding them to adhere to a strict, predefined grammatical structure—such as a specific constituency parse tree—remains a major hurdle. This type of fine-grained syntactic control is crucial for applications like maintaining stylistic consistency in legal or technical writing, designing targeted grammar tutoring tools, and generating controlled stimuli for psycholinguistic studies.
While programming languages can be constrained by rigid context-free grammars during decoding, natural language is inherently ambiguous and lacks simple, easily checkable rules. Standard prompting techniques, even few-shot prompting with advanced models like GPT-4, consistently fail because the models struggle to maintain global structural constraints. They frequently insert extra adjectives, adverbs, or punctuation that break the target syntax template.
Methods
The authors frame controlled generation as a posterior inference problem. They combine the language model's prior probability distribution $p(y)$ (which ensures fluency) with a syntactic likelihood factor $\phi(t|y)$ (which measures how well a string $y$ matches the target syntax tree $t$).
To compute this likelihood efficiently during generation, they utilize Tetratagger, a neural constituency parser that linearizes syntax trees by assigning a pair of tags to each word. Because exact inference over all possible strings is mathematically intractable, they employ Sequential Monte Carlo (SMC) sampling (a particle filtering approach) to track multiple candidate sentences ("particles") simultaneously.
The method introduces two key innovations:
- Autoregressive Tetratagger Shaping: They train an autoregressive version of Tetratagger to act as a "shaping function" (a look-ahead heuristic). This function evaluates the syntactic viability of partially generated sentences, allowing the algorithm to prune unpromising paths early and focus computation on high-quality candidates.
- Syntax-Informed Proposal Distribution: Instead of just sampling blindly from the base LLM, they introduce an alternative proposal distribution ($Q \propto p \cdot q$) that incorporates a part-of-speech bigram model. This guides the model to suggest tokens that are both fluent and syntactically appropriate for the current position in the tree.
Datasets
- Penn Treebank: The standard benchmark used to train both the autoregressive and bidirectional Tetratagger models.
- ParaNMT-based Evaluation Dataset: A compiled evaluation set consisting of 301 syntax trees derived from human-generated paraphrase pairs. The leaf nodes of these trees are replaced with question marks to serve as structural templates for the generation task.
Key Insights and Ideas
- Prompting Has a Hard Ceiling: Even when GPT-4 is given the exact "gold standard" sentence structure in a 1-shot prompt, it fails to copy the structure accurately, achieving an F1 score of only 70.17%. It frequently hallucinates extra modifiers (e.g., turning a simple noun phrase into one with an extra adjective), violating the strict target parse tree.
- Smaller Models Can Outperform Giants: By using posterior inference, relatively small models like GPT2-large (774M parameters) and Llama3-8B can achieve over 93% syntactic accuracy, vastly outperforming raw GPT-4.
- The Proposal Distribution is Crucial: Simply filtering the base LLM's outputs (sampling from the prior) isn't enough because the base model rarely hits the exact target structure by chance. Coupling SMC with a syntax-informed proposal ($Q \propto pq$) is what unlocks the massive jump to 93% accuracy.
- The Diversity Trade-off: While the syntax-informed proposal dramatically improves structural alignment, it restricts the vocabulary, leading to a noticeable drop in the diversity of the generated text (especially for GPT2-large), causing more repetitive outputs.
Key Results
- Massive Accuracy Boost: For GPT2-large, the bracketing F1 score skyrocketed from a baseline of 12.31% to 93.69% using SMC with the syntax-informed proposal. For Llama3-Instruct (0-shot), it improved from 29.41% to 92.78%.
- Preserved Fluency: The approach achieves this structural precision without compromising the language model's natural fluency, as shown by stable log-prior ($\log p$) values.
- Efficient Scaling: The authors found that decoding quality improves with the number of particles ($M$), but effectively plateaus around $M=6$, meaning high accuracy can be achieved with a modest computational budget.
Limitations and Future Work
- Pruned Trees: The method relies on full constituency tree structures to map tokens to tags, meaning it cannot be applied to trees with a pruned height.
- No Fault Tolerance: The algorithm strictly enforces the exact word count defined by the target tree. If the model fails to generate a coherent token that fits the syntax within its sampling budget, it can result in incomplete or grammatically awkward sentences.
- Language Constraint: The current study is exclusively evaluated on English due to data availability and parser performance; extending it to morphologically richer or structurally diverse languages remains future work.
Summary updated