# Combining Constraint Programming Reasoning with Large Language Model Predictions

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 20 of its 46 references that are in the map.
- First posted on arXiv 18 Jul 2024.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference](https://mlsanity.com/paper/2403.04132/) (2024)
- [A Survey of Quantization Methods for Efficient Neural Network Inference](https://mlsanity.com/paper/2103.13630/) (2021)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search](https://mlsanity.com/paper/1704.07138/) (2017)
- [Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation](https://mlsanity.com/paper/1804.06609/) (2018)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics](https://mlsanity.com/paper/2112.08726/) (2021)
- [COLLIE: Systematic Construction of Constrained Text Generation Tasks](https://mlsanity.com/paper/2307.08689/) (2023)
- [Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization](https://mlsanity.com/paper/2006.01610/) (2020)
- [Holy Grail 2.0: From Natural Language to Constraint Models](https://mlsanity.com/paper/2308.01589/) (2023)
- [Why is constrained neural language generation particularly challenging?](https://mlsanity.com/paper/2206.05395/) (2022)
- ["I Want It That Way": Enabling Interactive Decision Support Using Large Language Models and Constraint Programming](https://mlsanity.com/paper/2312.06908/) (2023)
- [Constrained Text Generation with Global Guidance -- Case Study on CommonGen](https://mlsanity.com/paper/2103.07170/) (2021)
- [Constraints First: A New MDD-based Model to Generate Sentences Under Constraints](https://mlsanity.com/paper/2309.12415/) (2023)
- [Markov Constraint as Large Language Model Surrogate](https://mlsanity.com/paper/2406.10269/) (2024)
- [Intertwining CP and NLP: The Generation of Unreasonably Constrained Sentences](https://mlsanity.com/paper/2406.15473/) (2024)

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

- [MCP-Solver: Integrating Language Models with Constraint Programming Systems](https://mlsanity.com/paper/2501.00539/) (2024)
- [Reliable Proof Generation with LLMs via Analogical Retrieval and Symbolic Verification: A Case Study in Euclidean Geometry](https://mlsanity.com/paper/2505.14479/) (2025)
- [CP-Agent: Agentic Constraint Programming](https://mlsanity.com/paper/2508.07468/) (2025)
- [Distributed Multi-Agent Coordination Using Multi-Modal Foundation Models](https://mlsanity.com/paper/2501.14189/) (2025)
- [Large Language Model Meets Constraint Propagation](https://mlsanity.com/paper/2505.24012/) (2025)
- [LLMs versus the Halting Problem: Characterizing Program Termination Reasoning](https://mlsanity.com/paper/2601.18987/) (2026)
- [Text2Model: Modeling Copilots for Text-to-Model Translation](https://mlsanity.com/paper/2604.12955/) (2026)
- [Improving Constraint Models with LLM Agents](https://mlsanity.com/paper/2608.08127/) (2026)

## Abstract (arXiv)

Constraint Programming (CP) and Machine Learning (ML) face challenges in text generation due to CP's struggle with implementing "meaning'' and ML's difficulty with structural constraints. This paper proposes a solution by combining both approaches and embedding a Large Language Model (LLM) in CP. The LLM handles word generation and meaning, while CP manages structural constraints. This approach builds on GenCP, an improved version of On-the-fly Constraint Programming Search (OTFS) using LLM-generated domains. Compared to Beam Search (BS), a standard NLP method, this combined approach (GenCP with LLM) is faster and produces better results, ensuring all constraints are satisfied. This fusion of CP and ML presents new possibilities for enhancing text generation under constraints.