# Large Language Models Can Follow Instructions, But Not Many at Once: Phase Transitions in Compositional Constraint Satisfaction

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 43 references that are in the map.
- First posted on arXiv 12 Aug 2026.

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

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Measuring and Narrowing the Compositionality Gap in Language Models](https://mlsanity.com/paper/2210.03350/) (2022)
- [Winoground: Probing Vision and Language Models for Visio-Linguistic Compositionality](https://mlsanity.com/paper/2204.03162/) (2022)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [SugarCrepe: Fixing Hackable Benchmarks for Vision-Language Compositionality](https://mlsanity.com/paper/2306.14610/) (2023)
- [Generalizing Verifiable Instruction Following](https://mlsanity.com/paper/2507.02833/) (2025)
- [T2V-CompBench: A Comprehensive Benchmark for Compositional Text-to-video Generation](https://mlsanity.com/paper/2407.14505/) (2024)
- [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)
- [GenAI-Bench: Evaluating and Improving Compositional Text-to-Visual Generation](https://mlsanity.com/paper/2406.13743/) (2024)
- [Self-play with Execution Feedback: Improving Instruction-following Capabilities of Large Language Models](https://mlsanity.com/paper/2406.13542/) (2024)
- [COLLIE: Systematic Construction of Constrained Text Generation Tasks](https://mlsanity.com/paper/2307.08689/) (2023)
- [ImpossibleBench: Measuring LLMs' Propensity of Exploiting Test Cases](https://mlsanity.com/paper/2510.20270/) (2025)
- [ConceptMix: A Compositional Image Generation Benchmark with Controllable Difficulty](https://mlsanity.com/paper/2408.14339/) (2024)
- [LLM Self-Correction with DeCRIM: Decompose, Critique, and Refine for Enhanced Following of Instructions with Multiple Constraints](https://mlsanity.com/paper/2410.06458/) (2024)
- [Adaptive Testing for LLM Evaluation: A Psychometric Alternative to Static Benchmarks](https://mlsanity.com/paper/2511.04689/) (2025)
- [How Compositional Generalization and Creativity Improve as Diffusion Models are Trained](https://mlsanity.com/paper/2502.12089/) (2025)
- [ConMe: Rethinking Evaluation of Compositional Reasoning for Modern VLMs](https://mlsanity.com/paper/2406.08164/) (2024)
- [Controllable Text Generation with Language Constraints](https://mlsanity.com/paper/2212.10466/) (2022)
- [Order Matters: Investigate the Position Bias in Multi-constraint Instruction Following](https://mlsanity.com/paper/2502.17204/) (2025)
- [RECAST: Expanding the Boundaries of LLMs' Complex Instruction Following with Multi-Constraint Data](https://mlsanity.com/paper/2505.19030/) (2025)
- [AIR: Complex Instruction Generation via Automatic Iterative Refinement](https://mlsanity.com/paper/2502.17787/) (2025)
- [Revisiting Compositional Generalization Capability of Large Language Models Considering Instruction Following Ability](https://mlsanity.com/paper/2506.15629/) (2025)
- [CCTU: A Benchmark for Tool Use under Complex Constraints](https://mlsanity.com/paper/2603.15309/) (2026)
- [Confident Rankings with Fewer Items: Adaptive LLM Evaluation with Continuous Scores](https://mlsanity.com/paper/2601.13885/) (2026)
- [ConceptMix++: Leveling the Playing Field in Text-to-Image Benchmarking via Iterative Prompt Optimization](https://mlsanity.com/paper/2507.03275/) (2025)
- [Enhancing Complex Instruction Following for Large Language Models with Mixture-of-Contexts Fine-tuning](https://mlsanity.com/paper/2505.11922/) (2025)
- [LexInstructEval: Lexical Instruction Following Evaluation for Large Language Models](https://mlsanity.com/paper/2511.17561/) (2025)

## Abstract (arXiv)

Large language models are increasingly deployed in settings that require simultaneous adherence to multiple explicit constraints - reasoning structure, safety boundaries, output schemas. Individual constraints are handled proficiently, but the compositional regime, where many must hold jointly, remains poorly characterized: how rapidly does performance degrade, what governs the degradation, and can the collapse be mitigated? We introduce Constraint Saturation Evaluation (CSE), a procedurally generated benchmark that systematically varies the number of simultaneous constraints (k), with every constraint scored by a deterministic, rule-based verifier and zero LLM-judge involvement: 15 models, 36 constraint types, 369,753 checks at k=1-12. Three findings emerge. First, per-constraint pass rate decays gradually and predictably, while the chance of satisfying all k constraints collapses - a model passing individual constraints at ~41% at k=8 succeeds on all eight just 5.7% of the time. Second, constraints do not degrade equally: structural constraints lose 2x more baseline capability per added constraint than lexical ones, ordered by a comprehension-maintenance gap that separates constraints requiring sustained tracking from binary decisions immune to composition. Third, failures are nearly independent, which is what makes the accumulation multiplicative; the residual coupling that does exist tracks shared output features rather than pairwise interference - a wrong sentence count fails every constraint that reads it. Reliable instruction following breaks down beyond 5-6 simultaneous constraints: probe-level success falls below 50% at 7 constraints for the strongest model, and at 3 or fewer for 12 of 15.