Constraint Saturation Evaluation: Instruction Following Collapses Past 5-6 Simultaneous Constraints

Authors: Mariya I. Vasileva

arXiv ID: 2608.12426

Problem: LLMs are deployed in settings that require simultaneous adherence to many explicit constraints - reasoning structure, safety boundaries, output schemas. Individual constraints are handled proficiently, but the compositional regime (many constraints holding jointly) is poorly characterized: how fast does performance degrade, what governs it, and can the collapse be mitigated?

Key Methodology:

Constraint Saturation Evaluation (CSE): a procedurally generated benchmark varying the number of simultaneous constraints (k=1-12), every constraint scored by a deterministic rule-based verifier with zero LLM-judge involvement
15 models, 36 constraint types, 369,753 checks
35 pages of analysis on decay rates, constraint-type differences, and failure dependence

Key Results:

Per-constraint pass rate decays gradually and predictably, but 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
Constraints do not degrade equally: structural constraints lose 2x more baseline capability per added constraint than lexical ones, separated by a comprehension-maintenance gap (sustained tracking vs binary decisions)
Failures are nearly independent, which makes accumulation multiplicative; residual coupling tracks shared output features (a wrong sentence count fails every constraint that reads it)
Probe-level success falls below 50% at 7 constraints for the strongest model, and at 3 or fewer for 12 of 15 models

What it means for developers: Constraint load is a budget: past 5-6 simultaneous constraints, reliable instruction following breaks down no matter the model. Split large constraint sets into staged prompts or executable checks rather than one prompt, and treat all-k scores as the honest metric for constraint-heavy agents - per-constraint averages hide the cliff.

Paper: arXiv:2608.12426