Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo

João Loula; Benjamin LeBrun; Li Du; Ben Lipkin; Clemente Pasti; Gabriel Grand; Tianyu Liu; Yahya Emara; Marjorie Freedman; Jason Eisner; Ryan Cotterell; Vikash Mansinghka; Alexander K. Lew; Tim Vieira; Timothy J. O'Donnell

Source-linked AI summary

Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo

João Loula, Benjamin LeBrun, Li Du, Ben Lipkin, Clemente Pasti, Gabriel Grand, Tianyu Liu, Yahya Emara, Marjorie Freedman, Jason Eisner, Ryan Cotterell, Vikash Mansinghka, Alexander K. Lew, Tim Vieira, Timothy J. O'Donnell

arXiv:2504.13139v2Apr 17, 2025cs.CLcs.AIcs.LG

TL;DR

Constrained language-model generation can be formulated as sampling from a posterior that combines an LM with syntactic and semantic constraints, but exact sampling is generally intractable. The paper develops programmable sequential Monte Carlo inference and finds that it improves posterior approximation and lets small models outperform much larger and fine-tuned models across four domains.

Problem
Exact generation from the constraint-conditioned distribution can be intractable and may differ substantially from the LM's base distribution.
Method
The paper develops a programmable sequential Monte Carlo architecture that incrementally incorporates diverse constraints and reallocates computation during generation.
Results
Across four domains, SMC lets small open-source models outperform models over 8× larger and closed-source fine-tuned models, while better posterior approximation tracks performance.
Takeaways & Limitations
SMC provides a flexible and efficient framework for controlled generation, with downstream gains linked to approximation quality rather than only the LM base distribution.
Takeaways & Limitations
Locally constrained decoding is exact only with the expected future potential, whose exact computation is typically intractable; it also requires cheap evaluation across one-token continuations.

Abstract

from arXiv · show

A wide range of LM applications require generating text that conforms to syntactic or semantic constraints. Imposing such constraints can be naturally framed as probabilistic conditioning, but exact generation from the resulting distribution -- which can differ substantially from the LM's base distribution -- is generally intractable. In this work, we develop an architecture for controlled LM generation based on sequential Monte Carlo (SMC). Our SMC framework allows us to flexibly incorporate domain- and problem-specific constraints at inference time, and efficiently reallocate computational resources in light of new information during the course of generation. By comparing to a number of alternatives and ablations on four challenging domains -- Python code generation for data science, text-to-SQL, goal inference, and molecule synthesis -- we demonstrate that, with little overhead, our approach allows small open-source language models to outperform models over 8x larger, as well as closed-source, fine-tuned ones. In support of the probabilistic perspective, we show that these performance improvements are driven by better approximation to the posterior distribution. Our system builds on the framework of Lew et al. (2023) and integrates with its language model probabilistic programming language, giving users a simple, programmable way to apply SMC to a broad variety of controlled generation problems.

1 INTRODUCTION

The paper frames constrained language-model generation as probabilistic conditioning and develops sequential Monte Carlo (SMC) to approximate the resulting posterior while incorporating diverse constraint signals. Across four challenging domains, the approach improves performance and supports a programmable inference framework.

1 INTRODUCTION: The method accommodates heterogeneous signals, including static checks, execution tests, simulations, rollout scores, and language-model critiques with different costs and evaluation frequencies.These signals may be hard or soft constraints and may provide dense or sparse guidance during generation.
1 INTRODUCTION: Exact sampling from the global product-of-experts posterior is generally intractable, motivating approximate inference for constrained generation.The distribution combines an autoregressive LM prior with potential functions representing constraint signals.
1 INTRODUCTION: SMC integrates syntactic and semantic constraints for code generation, including signals that cannot be evaluated incrementally over the full vocabulary or only apply at irregular intervals.The framework supports programmable proposals and potentials and integrates with the language-model probabilistic programming framework of Lew et al. (2023).
1 INTRODUCTION: Across data science, text-to-SQL, goal inference, and molecule synthesis, the approach significantly improves performance, allowing small open-source models to outperform models over 8× larger and closed-source fine-tuned models.The evaluation compares SMC with six alternatives across the four domains.
1 INTRODUCTION: The probabilistic perspective is supported because the best-performing methods produce outputs closer in KL divergence to the global product-of-experts distribution and show stronger probability–performance correlation.These findings connect downstream performance with the quality of posterior approximation.

2 MONTE CARLO INFERENCE FOR CONSTRAINED SEMANTIC PARSING

The paper frames constrained generation as sampling from a global product-of-experts posterior, then develops Monte Carlo methods that approximate it despite intractable exact sampling. It combines local proposals, importance weighting, and sequential resampling to correct local greediness, incorporate expensive constraints, and focus computation on promising partial sequences.

Target distribution: Controlled generation samples from a global product-of-experts distribution combining an autoregressive LM prior with nonnegative constraint potentials, but exact sampling is generally intractable.For binary potentials, this target corresponds to rejection sampling, whose expected runtime is 1/Z per accepted sample when Z is the acceptance rate.
Local decoding: Local decoding normalizes constraint-adjusted probabilities at each step, so it generally differs from the globally normalized target and may greedily follow globally poor paths.Exactness would require the expected future potential Φ*(x), whose computation is typically intractable.
Local decoding: Local decoding also requires cheap evaluation of potentials on every one-token continuation, excluding constraints such as test-based error checking from efficient use.The framework therefore partitions potentials into efficiently evaluable and expensive components.
Importance sampling: Importance sampling uses the efficient local product of experts as a proposal, then reweights complete particles to correct local greediness and incorporate expensive potentials.The resulting weighted-particle approximation converges to the target as the number of particles grows under mild conditions.
Sequential Monte Carlo: Sequential Monte Carlo extends importance sampling by applying incremental weighting and resampling during generation, reallocating future computation toward promising partial sequences.Intermediate targets are defined over partial and complete sequences and approach the final target as the generation step increases.

3 EXPERIMENTS

Experiments compare constrained-generation methods across four semantic-parsing domains, testing grammar constraints, weight corrections, expensive potentials, resampling, model scale, particle budgets, and posterior approximation. Full SMC improves downstream performance and computational efficiency while its strongest methods better approximate the global product-of-experts distribution.

Component Ablations: Adding grammar constraints improves downstream accuracy over the base LM across every domain where they are used.This improvement occurs even without importance-weight corrections.
Component Ablations: Expensive potentials improve accuracy, with large gains in goal inference, data science, and molecular synthesis and a smaller significant gain in text-to-SQL.The text-to-SQL improvement is statistically significant under a paired permutation test (p < 0.01).
Component Ablations: Weight corrections often improve accuracy but contribute modest gains relative to other components, with no observed harm and no significant effect in several domain-component combinations.Their benefits are strongest for text-to-SQL when expensive potentials are present; they do not significantly affect goal inference there.
Component Ablations: Resampling improves downstream accuracy in every domain except text-to-SQL, where it neither significantly improves nor harms performance.This supports adaptively concentrating computation on promising partial sequences.
Other Evaluations: Full SMC lets smaller language models outperform models over 8 times larger in 3 of 4 domains and also improves resource use over Full IS.It performs as well as or better than Full IS with one-tenth the particles in three domains and outperforms it with fewer particles in the fourth.
Validation of the Probabilistic Perspective: The best-performing methods more closely approximate the global product-of-experts distribution, and these approximation trends align with downstream accuracy.Without weight correction, local-product sampling has significantly worse approximation in all domains; resampling further improves approximation in data science and goal inference, while molecular-generation resampling also improves diversity and de-novo similarity.

CONCLUSION

The paper formulates constrained generation as sampling from a global product-of-experts distribution and introduces SMC to approximate it using incremental constraint signals. Across experiments, SMC enables smaller models to outperform larger and fine-tuned models, improves computational efficiency, and links downstream performance to posterior approximation quality.

SMC lets smaller models outperform larger and fine-tuned models across constrained-generation experiments.The paper reports this outcome across a series of experiments spanning multiple domains.
The method is an SMC algorithm that flexibly incorporates different constraints while incrementally using their signals.
SMC is reported to be an order of magnitude more efficient than non-incremental approaches.
Downstream performance is linked to the quality of the posterior approximation, supporting the paper’s probabilistic formulation.

A.1 SMALLER BASE LMS

Using smaller base language models, the authors evaluate posterior-weighted accuracy across methods and domains. SMC components continue to improve performance, and the full method generally retains advantages over larger-model baselines.

The evaluation reports posterior-weighted accuracy across methods and domains using smaller base models.Text-to-SQL, Molecular Synthesis, and Goal Inference use Llama 3.2 (1B), while Data Science uses Llama 3.1 (8B).
The full SMC approach with smaller models outperforms the larger base LM in Data Science.
With the exception of Text-to-SQL, the smaller-LM approach outperforms larger-LM locally constrained decoding in the other evaluated domains.
Weight corrections, expensive potentials, and resampling steps improve performance even though smaller models have significantly lower accuracy overall.
The relative accuracy gains from the method are generally more pronounced for smaller language models.

A.2 ACCURACY BY NUMBER OF PARTICLES

Particle-count experiments show that Full SMC uses computational resources more efficiently than non-incremental importance sampling. The benefit of adding particles depends on the domain and the informativeness of expensive potentials.

The analysis reports downstream accuracy for N = 5, N = 10, and N = 50 particles using Llama 3.1 (8B) models.Direct-sampling baselines are omitted because particle count does not influence their accuracy.
Full SMC outperforms Full IS with one tenth as many particles in Data Science, Molecular Synthesis, and Text-to-SQL, and one fifth as many in Goal Inference.Full IS does not incorporate incremental information.
Increasing particles has marginal impact in Molecular Synthesis, but improves accuracy in Goal Inference and Data Science.In Data Science, the significant improvement occurs when increasing from 5 to 10 particles.
The domain-dependent particle effects are consistent with richer potentials requiring more computation to exploit fully.

A.3 RESAMPLING WITHOUT REPLACEMENT (LEW ET AL., 2023)

The authors compare multinomial resampling with the without-replacement scheme of Lew et al. (2023) in text-to-SQL. Without-replacement resampling slightly reduces performance relative to multinomial resampling.

The experiment replaces multinomial resampling in Full SMC with Lew et al. (2023)’s without-replacement scheme.The comparison uses N = 5 particles and a beam size of 3 for the without-replacement baseline.
Without-replacement resampling slightly hurts weighted accuracy compared with multinomial resampling.
The comparison is restricted to text-to-SQL because of computational-resource limitations.

A.4 COMPUTATIONAL COST

The framework adds computational cost mainly from resampling and expensive potentials, but resampling is negligible and expensive potentials rarely exceed about 30 ms per token. Set-based proposal methods aim to reduce runtime while preserving SMC’s proper-weighting invariant.

A.4 COMPUTATIONAL COST: Resampling is negligible, while expensive potentials are the main added cost and rarely exceed about 30 ms per token across domains.Caching at semantically meaningful boundaries and CPU execution can further reduce expensive-potential costs.
A.4 COMPUTATIONAL COST: The proposal framework supports character-level and grammar-based potentials, including specialized handling for token vocabularies whose size makes per-token evaluation expensive.The character-based implementation uses trie structures and is designed to evaluate many token continuations efficiently.
A.4 COMPUTATIONAL COST: The speedup modifies SMC’s extend and reweight steps with approximate proposals and weights while preserving the proper-weighting invariant.The goal is to improve runtime without compromising soundness.
A.4 COMPUTATIONAL COST: Set-based proposals reduce the cost of evaluating locally constrained distributions by sampling subsets of tokens and estimating weights from those subsets.The procedure is inspired by the Horvitz–Thompson estimator and evaluates expensive potentials only on a randomly chosen subset.

3. Compute the set-conditioned distribution q(x | S)

The set-based proposal speedup approximates locally constrained sampling by selecting token subsets, computing corrected subset weights, and returning properly weighted proposals. The construction preserves SMC’s target-approximation invariant while enabling tractable inference-quality estimation.

3. Compute the set-conditioned distribution q(x | S): The set-based proposal samples a subset S, computes local weights, samples a token from that subset, and returns a weighted next-token proposal.The resulting proposal replaces exact locally constrained sampling and exact local-weight evaluation in the extend and reweight steps.
3. Compute the set-conditioned distribution q(x | S): The proposal is properly weighted for the unnormalized local product of experts, so replacing exact updates preserves SMC soundness.Proposition 1 establishes the proper-weighting guarantee for the set-based proposal distribution.
3. Compute the set-conditioned distribution q(x | S): The character-based implementation samples token sets through a character trie representing token prefixes and end-of-token markers.This construction instantiates the general set-based speedup for character-level potentials such as parsing.
3. Compute the set-conditioned distribution q(x | S): Inference quality is compared using log Z − KL(q ∥g), an approximation-quality measure whose algorithm-dependent variation reflects differences in KL divergence.Extended-state-space estimators make the quantity tractable for importance sampling and SMC, including hard-constraint settings after rejection sampling.

D.2 ESTIMATING INFERENCE QUALITY FOR REJECTION-SAMPLED VARIANTS

Hard constraints can make the direct KL divergence from an algorithm to the global product-of-experts distribution infinite. The paper therefore evaluates rejection-sampled variants to obtain a tractable approximation-quality comparison.

D.2 ESTIMATING INFERENCE QUALITY FOR REJECTION-SAMPLED VARIANTS: When hard constraints assign zero mass to failed proposals, KL(qalg ∥g) can be infinite because algorithms may generate sequences rejected by g.This issue arises when all generated proposals fail to satisfy the constraints.
D.2 ESTIMATING INFERENCE QUALITY FOR REJECTION-SAMPLED VARIANTS: The paper repeatedly samples each algorithm until a positive-mass output is obtained, then estimates log Z − KL(qr_alg ∥g) as approximation quality.The rejection-sampled formulation incorporates the algorithm’s acceptance rate into a tractable comparison.
D.2 ESTIMATING INFERENCE QUALITY FOR REJECTION-SAMPLED VARIANTS: Reversing the KL direction would require exact samples from g, which are impractical in the paper’s setting.The rejection-sampled approach avoids that requirement while retaining an algorithm-comparable quality measure.

E.1 TEXT-TO-SQL (SPIDER)

The Spider task evaluates whether generated SQL is both syntactically valid and semantically consistent with database schemas. The experiments combine efficient grammar constraints with an expensive table-column correspondence check applied at clause boundaries.

E.1 TEXT-TO-SQL (SPIDER): Spider asks models to generate SQL semantically equivalent to a ground-truth query from a natural-language question and database schema.Performance is evaluated on the development split using execution accuracy.
E.1 TEXT-TO-SQL (SPIDER): The efficient potential enforces valid SQL syntax and restricts table and column names to those present in the schema.These constraints are implemented using SQL grammars.
E.1 TEXT-TO-SQL (SPIDER): The expensive potential checks whether referenced columns correspond to existing tables, addressing a semantic relation not guaranteed by the grammar.The check returns 0 for invalid correspondences and 1 otherwise.
E.1 TEXT-TO-SQL (SPIDER): Table-column verification runs only at clause boundaries after the FROM clause is complete, when the necessary table or alias information is available.This timing reflects when the semantic constraint becomes meaningful.

E.4 DATA SCIENCE (DS1000)

DS-1000 tests Python code generation for data-science problems across six libraries, using English problem descriptions and Python test cases. The paper places this benchmark within a broader SMC framework that combines grammar constraints, expensive potentials, and asymptotically correct inference.

E.4 DATA SCIENCE (DS1000): DS-1000 covers Python data-science problems involving Pandas, NumPy, Scikit-Learn, SciPy, TensorFlow, and PyTorch.Each instance provides an English problem description and a sample Python test case; generated code must solve the problem and pass the test.
E.4 DATA SCIENCE (DS1000): The paper combines grammar constraints, expensive potentials, and asymptotically correct SMC inference for semantic parsing and code generation.This unifies the paper’s treatment of syntactic well-formedness, domain-specific signals, and posterior inference.
E.4 DATA SCIENCE (DS1000): The approach builds on SMC methods for posterior sampling while using incremental static and dynamic analyses rather than costly learned components.The paper contrasts its approach with Zhao et al. (2024), whose framework learns twist functions through contrastive fine-tuning.