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

arXiv: https://arxiv.org/abs/2504.13139 · HTML: https://mlsanity.com/paper/2504.13139/

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- Builds on 73 of its 104 references that are in the map.
- First posted on arXiv 17 Apr 2025.

## Builds on (most cited first, 30 of 73)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Constitutional AI: Harmlessness from AI Feedback](https://mlsanity.com/paper/2212.08073/) (2022)
- [Learning to summarize from human feedback](https://mlsanity.com/paper/2009.01325/) (2020)
- [Do As I Can, Not As I Say: Grounding Language in Robotic Affordances](https://mlsanity.com/paper/2204.01691/) (2022)
- [Fine-Tuning Language Models from Human Preferences](https://mlsanity.com/paper/1909.08593/) (2019)
- [WebGPT: Browser-assisted question-answering with human feedback](https://mlsanity.com/paper/2112.09332/) (2021)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task](https://mlsanity.com/paper/1809.08887/) (2018)
- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [Plug and Play Language Models: A Simple Approach to Controlled Text Generation](https://mlsanity.com/paper/1912.02164/) (2019)
- [LLM+P: Empowering Large Language Models with Optimal Planning Proficiency](https://mlsanity.com/paper/2304.11477/) (2023)
- [DS-1000: A Natural and Reliable Benchmark for Data Science Code Generation](https://mlsanity.com/paper/2211.11501/) (2022)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [FUDGE: Controlled Text Generation With Future Discriminators](https://mlsanity.com/paper/2104.05218/) (2021)
- [Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint](https://mlsanity.com/paper/2312.11456/) (2023)
- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [DeepSeek-Prover: Advancing Theorem Proving in LLMs through Large-Scale Synthetic Data](https://mlsanity.com/paper/2405.14333/) (2024)
- [Secrets of RLHF in Large Language Models Part I: PPO](https://mlsanity.com/paper/2307.04964/) (2023)
- [Leveraging Pre-trained Large Language Models to Construct and Utilize World Models for Model-based Task Planning](https://mlsanity.com/paper/2305.14909/) (2023)
- [Efficient Guided Generation for Large Language Models](https://mlsanity.com/paper/2307.09702/) (2023)
- [Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning](https://mlsanity.com/paper/2305.13971/) (2023)
- [Preference Fine-Tuning of LLMs Should Leverage Suboptimal, On-Policy Data](https://mlsanity.com/paper/2404.14367/) (2024)
- [Planning with Large Language Models for Code Generation](https://mlsanity.com/paper/2303.05510/) (2023)
- [LINC: A Neurosymbolic Approach for Logical Reasoning by Combining Language Models with First-Order Logic Provers](https://mlsanity.com/paper/2310.15164/) (2023)
- [Constrained Language Models Yield Few-Shot Semantic Parsers](https://mlsanity.com/paper/2104.08768/) (2021)
- [COLD Decoding: Energy-based Constrained Text Generation with Langevin Dynamics](https://mlsanity.com/paper/2202.11705/) (2022)
- [Synchromesh: Reliable code generation from pre-trained language models](https://mlsanity.com/paper/2201.11227/) (2022)
- [NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics](https://mlsanity.com/paper/2112.08726/) (2021)
- [RL with KL penalties is better viewed as Bayesian inference](https://mlsanity.com/paper/2205.11275/) (2022)

## Built on by (most cited first, 30 of 46)

- [Enforcing Temporal Constraints for LLM Agents](https://mlsanity.com/paper/2512.23738/) (2025)
- [DINGO: Constrained Inference for Diffusion LLMs](https://mlsanity.com/paper/2505.23061/) (2025)
- [Modeling Open-World Cognition as On-Demand Synthesis of Probabilistic Models](https://mlsanity.com/paper/2507.12547/) (2025)
- [Neurosymbolic Diffusion Models](https://mlsanity.com/paper/2505.13138/) (2025)
- [Rare Event Analysis of Large Language Models](https://mlsanity.com/paper/2602.06791/) (2026)
- [Mitigating Bias in Locally Constrained Decoding via Tractable Proposals](https://mlsanity.com/paper/2606.01926/) (2026)
- [Inference-Time Scaling of Diffusion Language Models via Trajectory Refinement](https://mlsanity.com/paper/2507.08390/) (2025)
- [Neuro-Symbolic Predictive Process Monitoring](https://mlsanity.com/paper/2509.00834/) (2025)
- [Lookahead-then-Verify: Reliable Constrained Decoding for Diffusion LLMs under Context-Free Grammars](https://mlsanity.com/paper/2602.00612/) (2026)
- [On the Power of (Approximate) Reward Models for Inference-Time Scaling](https://mlsanity.com/paper/2602.01381/) (2026)
- [Scaling Discovery through Test-Time Communication](https://mlsanity.com/paper/2609.21032/) (2026)
- [Reinforced sequential Monte Carlo for amortised sampling](https://mlsanity.com/paper/2510.11711/) (2025)
- [What's the plan? Metrics for implicit planning in LLMs and their application to rhyme generation and question answering](https://mlsanity.com/paper/2601.20164/) (2026)
- [Beyond Individual Intelligence: Surveying Collaboration, Failure Attribution, and Self-Evolution in LLM-based Multi-Agent Systems](https://mlsanity.com/paper/2605.14892/) (2026)
- [RefineStat: Efficient Exploration for Probabilistic Program Synthesis](https://mlsanity.com/paper/2509.01082/) (2025)
- [Sampling for Quality: Training-Free Reward-Guided LLM Decoding via Sequential Monte Carlo](https://mlsanity.com/paper/2604.16453/) (2026)
- [Semantic Probabilistic Control of Language Models](https://mlsanity.com/paper/2505.01954/) (2025)
- [Collision- and Reachability-Aware Multi-Robot Control with Grounded LLM Planners](https://mlsanity.com/paper/2505.20573/) (2025)
- [Mitigating Premature Exploitation in Particle-based Monte Carlo for Inference-Time Scaling](https://mlsanity.com/paper/2510.05825/) (2025)
- [Repair, Not Improvement: Decomposing Constrained Decoding in Tool-Call Abstention](https://mlsanity.com/paper/2608.13959/) (2026)
- [ABS: Enforcing Constraint Satisfaction On Generated Sequences Via Automata-Guided Beam Search](https://mlsanity.com/paper/2506.09701/) (2025)
- [Constrained Adaptive Rejection Sampling](https://mlsanity.com/paper/2510.01902/) (2025)
- [Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference](https://mlsanity.com/paper/2603.07887/) (2026)
- [The Format Tax](https://mlsanity.com/paper/2604.03616/) (2026)
- [Improving Constrained Language Generation via Self-Distilled Twisted Sequential Monte Carlo](https://mlsanity.com/paper/2507.02315/) (2025)
- [Naive Prompt Optimization: Rethinking the Need for Complex Prompt Search](https://mlsanity.com/paper/2608.27266/) (2026)
- [Language and Experience: A Computational Model of Social Learning in Complex Tasks](https://mlsanity.com/paper/2509.00074/) (2025)
- [Entropy-Aligned Decoding of LMs for Better Writing and Reasoning](https://mlsanity.com/paper/2601.01714/) (2026)
- [Decoupling Exploration and Policy Optimization: Uncertainty Guided Tree Search for Hard Exploration](https://mlsanity.com/paper/2603.22273/) (2026)
- [Probabilistic Programs of Thought](https://mlsanity.com/paper/2604.17290/) (2026)

## Abstract (arXiv)

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.