# ABS: Enforcing Constraint Satisfaction On Generated Sequences Via Automata-Guided Beam Search

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 42 references that are in the map.
- First posted on arXiv 11 Jun 2025.

## Builds on (most cited first, 28 of 28)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [CIDEr: Consensus-based Image Description Evaluation](https://mlsanity.com/paper/1411.5726/) (2014)
- [SPICE: Semantic Propositional Image Caption Evaluation](https://mlsanity.com/paper/1607.08822/) (2016)
- [Neural Probabilistic Logic Programming in DeepProbLog](https://mlsanity.com/paper/1907.08194/) (2019)
- [GeDi: Generative Discriminator Guided Sequence Generation](https://mlsanity.com/paper/2009.06367/) (2020)
- [FUDGE: Controlled Text Generation With Future Discriminators](https://mlsanity.com/paper/2104.05218/) (2021)
- [A Semantic Loss Function for Deep Learning with Symbolic Knowledge](https://mlsanity.com/paper/1711.11157/) (2017)
- [Neurosymbolic AI: The 3rd Wave](https://mlsanity.com/paper/2012.05876/) (2020)
- [Efficient Guided Generation for Large Language Models](https://mlsanity.com/paper/2307.09702/) (2023)
- [NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics](https://mlsanity.com/paper/2112.08726/) (2021)
- [NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints](https://mlsanity.com/paper/2010.12884/) (2020)
- [Enabling Language Models to Fill in the Blanks](https://mlsanity.com/paper/2005.05339/) (2020)
- [Semantic Probabilistic Layers for Neuro-Symbolic Learning](https://mlsanity.com/paper/2206.00426/) (2022)
- [Analyzing Differentiable Fuzzy Logic Operators](https://mlsanity.com/paper/2002.06100/) (2020)
- [CGMH: Constrained Sentence Generation by Metropolis-Hastings Sampling](https://mlsanity.com/paper/1811.10996/) (2018)
- [Logic Tensor Networks for Semantic Image Interpretation](https://mlsanity.com/paper/1705.08968/) (2017)
- [Tractable Control for Autoregressive Language Generation](https://mlsanity.com/paper/2304.07438/) (2023)
- [From Statistical Relational to Neuro-Symbolic Artificial Intelligence](https://mlsanity.com/paper/2003.08316/) (2020)
- [Incorporating Domain Knowledge into Deep Neural Networks](https://mlsanity.com/paper/2103.00180/) (2021)
- [A-NeSI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inference](https://mlsanity.com/paper/2212.12393/) (2022)
- [Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo](https://mlsanity.com/paper/2504.13139/) (2025)
- [MultiplexNet: Towards Fully Satisfied Logical Constraints in Neural Networks](https://mlsanity.com/paper/2111.01564/) (2021)
- [Deep Learning with Logical Constraints](https://mlsanity.com/paper/2205.00523/) (2022)
- [Controllable Text Generation with Neurally-Decomposed Oracle](https://mlsanity.com/paper/2205.14219/) (2022)
- [Multi-Label Classification Neural Networks with Hard Logical Constraints](https://mlsanity.com/paper/2103.13427/) (2021)
- [NeuPSL: Neural Probabilistic Soft Logic](https://mlsanity.com/paper/2205.14268/) (2022)
- [VAEL: Bridging Variational Autoencoders and Probabilistic Logic Programming](https://mlsanity.com/paper/2202.04178/) (2022)
- [Controllable Generation via Locally Constrained Resampling](https://mlsanity.com/paper/2410.13111/) (2024)

## Built on by (most cited first, 3 of 3)

- [Mitigating Bias in Locally Constrained Decoding via Tractable Proposals](https://mlsanity.com/paper/2606.01926/) (2026)
- [First-Order Temporal Logic Tensor Networks](https://mlsanity.com/paper/2606.29972/) (2026)
- [Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance](https://mlsanity.com/paper/2608.28229/) (2026)

## Abstract (arXiv)

Sequence generation and prediction form a cornerstone of modern machine learning, with applications spanning natural language processing, program synthesis, and time-series forecasting. These tasks are typically modeled in an autoregressive fashion, where each token is generated conditional on the preceding ones, and beam search is commonly used to balance exploration and fluency during decoding. While deep learning models and Large Language Models (LLMs) excel at capturing statistical patterns in this setting, they remain ill-equipped to guarantee compliance with formal constraints. In this paper, we introduce ABS: a general and model-agnostic inference-time algorithm that guarantees compliance with any constraint that can be compiled into a Deterministic Finite Automaton (DFA), without requiring retraining. ABS leverages the DFA to guide a constrained variant of beam search: at each decoding step, transitions leading to violations are masked, while remaining paths are dynamically re-ranked according to both the model's probabilities and the automaton's acceptance structure. We formally prove that the resulting sequences are guaranteed to satisfy the given constraints, and we empirically demonstrate that ABS also improves output quality. We validate our approach on three distinct tasks: constrained image-stream classification, controlled text generation, and text infilling. In all settings, ABS achieves perfect constraint satisfaction, while outperforming or matching state-of-the-art baselines on standard quality metrics and efficiency.