Research map / Large language models / Agents, code and math
Adaptable Logical Control for Large Language Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Ctrl-G distills an HMM from an LLM and conditions generation on logical constraints expressed as DFAs, enabling guaranteed constraint satisfaction with a frozen LLM and HMM.
Problem
Controlling LLM generation at inference time to reliably satisfy logical constraints (keyphrases, length, order) is intractable because the probability of future constraint satisfaction cannot be computed efficiently.
Approach
Distill an HMM as a white-box approximation of the LLM, represent constraints as DFAs, and compute the probability of DFA acceptance under the HMM via a dynamic-programming recurrence so that next-token sampling is reweighted by p_hmm(alpha | x_t, x_<t); the LLM and HMM stay frozen once trained and constraints can change without retraining.
Key results
- On interactive text editing, Ctrl-G (TULU2-7B + 2B HMM) reaches 92% overall satisfaction for continuation vs 56% for GPT4, and 79% vs 24% for insertion.
- On CommonGen with GPT2-large, Ctrl-G achieves 100% constraint satisfaction and test BLEU-4 31.5 vs GeLaTo 29.0.
- On GSM subset of 293 problems where numbers were omitted, Ctrl-G raises accuracy from 24.9% to 28.3% (3.4 points) with majority vote over 16 samples.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Ctrl-G instead of GeLaTo | GPT2-large on CommonGen · CommonGen dev | BLEU-4: 30.3 -> 32.1 | Helped |
| Use Ctrl-G instead of GeLaTo | GPT2-large on CommonGen · CommonGen test | BLEU-4: 29.0 -> 31.5 | Helped |
| Use Ctrl-G instead of ILM | GPT2-small on text infilling · Text infilling, 40% masking | BLEU-4: +3.4 | Helped |
| Use Ctrl-G instead of ILM | GPT2-small on text infilling · Text infilling, 13% masking | ROUGE-L: -$0.3 | Hurt |
| Use Ctrl-G instead of GPT4 | TULU2-7B on interactive text editing · Continuation, average | Overall satisfaction: 56% -> 92% | Helped |
| Use Ctrl-G instead of GPT4 | TULU2-7B on interactive text editing · Insertion, average | Overall satisfaction: 24% -> 79% | Helped |
| Constrain chain-of-thought to use the problem numbers | TULU2-7B · GSM, 293 examples where model omitted numbers | Accuracy: 14.6% -> 28.3% | Helped |
| Use Ctrl-G rather than unconstrained TULU2-7B | TULU2-7B on interactive text editing · Continuation and insertion, constrained settings | Constraint success: GPT4: 57% / 36%; Ctrl-G: 100% / 100% | Helped |
Surprising findings
- GPT4 quality drops sharply with more complex constraints (e.g., insertion K&L overall satisfaction 14%), while Ctrl-G stays consistent.
- Guidance-style pure logical reasoning produces unnatural text, motivating probabilistic over purely logical constraint enforcement.
Limitations
- Runtime overhead scales as h^2 with HMM hidden states and implementation is naive.
- Human evaluation inter-annotator agreement is only moderate (Kendall W 0.449).
- Constraints must be expressible as DFAs over bounded-length sequences; the GSM study is only a proof of concept.
Experimental setup
Datasets: CommonGen ROCStories text infilling benchmark CoAuthor WritingPrompt GSM8K
Benchmarks: CommonGen CommonGen+ ROCStories text infilling CoAuthor-based interactive text editing GSM
Metrics: BLEU-4 ROUGE-L CIDEr SPICE constraint satisfaction rate human quality score overall satisfaction rate accuracy
Baselines: GPT3.5 GPT4 FUDGE NADO NeuroLogic A*esque GeLaTo ILM TULU2 instruction-tuned
Builds on: GeLaTo NeuroLogic decoding Knuth-Morris-Pratt Aho-Corasick
Closest papers by meaning
- TRACE Back from the Future: A Probabilistic Reasoning Approach to Controllable Language Generation (ICML 2025 · similarity 0.88)
- Scaling Instruction-tuned LLMs to Million-token Contexts via Hierarchical Synthetic Data Generation (ICLR 2025 · similarity 0.88)
- Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo (ICLR 2025 · similarity 0.88)
- Aligning Large Language Models with Representation Editing: A Control Perspective (NeurIPS 2024 · similarity 0.87)
- Larimar: Large Language Models with Episodic Memory Control (ICML 2024 · similarity 0.87)
- LensLLM: Unveiling Fine-Tuning Dynamics for LLM Selection (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.