Paper deep dive

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

Mariya I. Vasileva

Year: 2026Venue: arXiv preprintArea: cs.AIType: PreprintEmbeddings: 147

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%

Last extracted: 8/14/2026, 4:16:29 AM

Summary

This paper introduces Constraint Saturation Evaluation (CSE), a benchmark assessing Large Language Models' ability to satisfy multiple simultaneous constraints. The study reveals a 'phase transition' where per-constraint pass rates decay gradually, but the joint satisfaction rate collapses multiplicatively. Structural constraints degrade faster than lexical ones, and failures are nearly independent, driven by shared output features rather than pairwise interference. Reliable instruction following breaks down beyond 5-6 constraints for most models.

Entities (8)

Constraint Saturation Evaluation · benchmark · 98%GPT-5.5 · model · 95%Llama 405B · model · 95%Marginal CSR · metric · 92%Strict CSR · metric · 92%Compositional Half-life · metric · 90%FollowBench · benchmark · 90%IFEval · benchmark · 90%

Relation Signals (5)

Constraint Saturation Evaluation → evaluates → Large Language Models

confidence 95% · CSE evaluates 15 models across 8 families... to measure the co-failure structure directly

Constraint Saturation Evaluation → uses → Deterministic Verifiers

confidence 95% · Every constraint is verified by a deterministic function rather than an LLM judge

Constraint Failures → exhibit → Near Independence

confidence 93% · Constraint failures are weakly correlated through shared output features... not pairwise interference.

Structural Constraints → degradesfasterthan → Lexical Constraints

confidence 92% · structural constraints lose 2.0× more baseline capability per added constraint than lexical ones

GPT-5.5 → outperforms → Llama 405B

confidence 90% · GPT-5.5 is a notable outlier... while the remaining 14 models cluster... Llama 405B shows 46.4% per-constraint competence

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract: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.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

145,913 characters extracted from source content.

Expand or collapse full text

Large Language Models Can Follow Instructions, But Not Many at Once: Phase Transitions in Compositional Constraint Satisfaction Mariya I. Vasileva * maria.i.vasileva@gmail.com Abstract Large language models are increasingly de- ployed in settings that require simultaneous adherence to multiple explicit constraints— reasoning structure, safety boundaries, out- put schemas. Individual constraints are han- dled 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 sys- tematically varies the number of simultane- ous constraints (k), with every constraint scored by a deterministic, rule-based verifier and zero LLM-judge involvement: 15 mod- els, 36 constraint types, 369,753 checks at k=1−12. Three findings emerge. First, per- constraint pass rate decays gradually and pre- dictably, while the chance of satisfying allk constraints collapses—a model passing indi- vidual constraints at∼41%atk=8succeeds on all eight just 5.7% of the time. Second, constraints do not degrade equally: structural constraints lose2×more baseline capability per added constraint than lexical ones, ordered by a comprehension-maintenance gap that sep- arates constraints requiring sustained tracking from binary decisions immune to composi- tion. Third, failures are nearly independent, which is what makes the accumulation multi- plicative; the residual coupling that does ex- ist tracks shared output features rather than pairwise interference—a wrong sentence count fails every constraint that reads it. Weak cou- pling means there is no pairing to exploit: no se- lection or arrangement of constraints mitigates the collapse. Three targeted ablations find little room at inference time: pre-generation plan- ning does not move the threshold at all, while post-hoc self-correction and best-of-5 retries delay it by only one to two constraints. Only raising the per-constraint pass rate helps. Reli- * Work done while at Meta Superintelligence Labs. able instruction following breaks down beyond 5–6 simultaneous constraints: probe-level suc- cess falls below 50% at 7 constraints for the strongest model, and at 3 or fewer for 12 of 15. All verifiers, probes, model outputs, and code are released for reproducibility. 1 Introduction Language models deployed in complex appli- cations must now adhere to multiple explicit constraints simultaneously—reasoning structure, safety boundaries, domain-specific protocols, out- put schemas—within a single response. Models handle individual constraints well, but performance under composition is poorly understood: does it degrade gracefully, or is there a sharp transition? Three specific questions remain open: what is the functional form of the degradation, is there a struc- ture governing which constraints fail first, and does the collapse arise from pairwise interference be- tween constraints or from something simpler? A fourth question follows from any answer to these: can the collapse be mitigated? Several benchmarks address pieces of this ques- tion. IFEval (Zhou et al., 2023) pioneered de- terministic verification across 25 constraint types but evaluates atk≤3. COLLIE (Yao et al., 2024) demonstrated through a formal constraint grammar that composition increases difficulty, but uses fixed compositions rather than varyingk. FollowBench (Jiang et al., 2024b) extends tok=5—the closest existing per-kanalysis—but relies on GPT-4 as judge. RECAST (Guo et al., 2025) pushes to 13+ constraints but reports at four coarse tiers; CCTU (Ye et al., 2026) finds no model exceeds 20% un- der strict multi-constraint adherence. InfoBench (Qin et al., 2024) observes that models fail number and linguistic constraints preferentially—a hierar- chy we extend acrossk. Outside text, Concept- Mix (Wu et al., 2024) reports that text-to-image models drop from 83% to 8% as concept count 1 arXiv:2608.12426v1 [cs.AI] 12 Aug 2026 grows from 1 to 7. In compositional generalization more broadly (Lake and Baroni, 2018), Dziri et al. (2023) show exponential decay with composition depth, and Press et al. (2023) quantify a compo- sitionality gap persisting at∼40%regardless of scale. Benchmarks that rely on LLM-based eval- uation (Jiang et al., 2024b; Guo et al., 2025; Wu et al., 2024) face a circularity at highk: the judge itself struggles with compositional constraint viola- tions in exactly the regime where models fail most. The pattern is otherwise consistent across bench- marks, modalities, and tasks: composition is hard. What is missing is the functional form—where ca- pability breaks, what drives the breakdown, and whether the trajectory is predictable. An extended discussion of all related work, including training methods, mechanistic explanations, cross-modal parallels, and phase transition theory, appears in Section B. We introduce Constraint Saturation Evalua- tion (CSE), designed to address all three. Every constraint is verified by a deterministic function rather than an LLM judge—a design choice that makes CSE’s measurements invariant to the same compositional degradation it studies. CSE evalu- ates 36 deterministically verifiable constraint types spanning 8 processing dimensions, 4,527 probes at k=1to12, 15 models across 8 families (369,753 constraint checks). We measure the co-failure structure directly and find failures nearly independent, which makes joint success approximately the product ofkper- constraint rates: a mild per-constraint decay com- pounds into a steep collapse. Prior work assumes interference. The rates, their 2%-to-28% spread across models, and the failure ordering are all ex- perimental results. We address three open questions: 1.Is the decay predictable? Per-constraint pass rate follows a multiplicative model (72.0%× 0.922 k−1 , held-out MAE=0.2p), but probe- level success collapses below 2% byk=9: a model passing individual constraints at∼41% atk=8succeeds on all eight just 5.7% of the time. Probe-level success drops below 50% at just 7 constraints for the strongest model, and at 3 or fewer for 12 of 15 (Section 4). 2.Do all constraints degrade equally? Structural constraints lose2.0×more baseline capability per added constraint than lexical ones (95% CI: [1.9, 2.3]), and the comprehension-maintenance gap (ρ=−0.584) predicts degradation rate: con- straints requiring sustained tracking during gen- eration degrade fastest, while binary decisions are immune (Section 4). 3.What drives the collapse—interference or ac- cumulation? Constraint failures are weakly correlated through shared output features (mean φ=+0.067), not pairwise interference. This near-multiplicative structure is what makes the decay in (1) predictable—and it means the only lever for improvement is per-constraint reliabil- ity, not constraint pairing (Section 4). 2 Related Work Several benchmarks address pieces of this ques- tion. IFEval (Zhou et al., 2023) and COLLIE (Yao et al., 2024) establish deterministic verification of instruction-following constraints, with COLLIE demonstrating through a formal constraint gram- mar that composition increases difficulty—but IFE- val evaluates atk ≤ 3, and COLLIE uses fixed compositions rather than systematically varyingk, precluding trajectory analysis. FollowBench (Jiang et al., 2024b) introduces a multi-level mechanism that incrementally adds one constraint per level up tok=5and tracks both hard and soft satisfac- tion rates across levels—the closest existing per-k analysis—but relies on GPT-4 as judge for open- ended constraints and does not characterize the functional form of the observed degradation. RE- CAST (Guo et al., 2025) pushes constraint density to 13+ per instance and proposes reinforcement learning from verifiable constraints, but reports per- formance at four coarse difficulty tiers rather than per-ktrajectories, precluding decay analysis. In constrained tool use, CCTU (Ye et al., 2026) finds no model exceeds 20% task completion under strict multi-constraint adherence. Outside text entirely, ConceptMix (Wu et al., 2024) reports that text-to- image models drop from 83% to 8% as concept count grows from 1 to 7. The pattern is consistent across benchmarks and modalities: composition is hard. What is missing is a characterization of the functional form of the degradation—where ca- pability breaks, what drives the breakdown, and whether the trajectory is predictable. An extended discussion of all related work, including training methods, mechanistic explanations, cross-modal parallels, and phase transition theory, appears in Section B. 2 3 Constraint Saturation Evaluation (CSE) 3.1 Constraint taxonomy CSE defines 36 constraint types across 8 dimen- sions (Table 2), selected to be deterministically verifiable and to span a range of processing de- mands. Constraints range from local pattern match- ing (lipogram: avoid a letter; forbidden word: ex- clude a token) through document-level structure (exact paragraph count, monotonic sentence length) to relational reasoning requiring structured output (scene graphs, logic grids) and self-referential rea- soning (a sentence correctly reporting its own word count). Whether this design choice produces a mea- surable hierarchy in degradation rates is tested in Section 4. All 36 verifiers are fully deterministic, each returning both a binary pass/fail judgment and a continuous scores ∈ [0, 1]representing partial compliance. Each constraint entered the pool through a four- stage vetting pipeline—deterministic verifiability, parameter calibration, composability analysis, and pilot validation (Section K). The composability stage is critical for a compositional benchmark: a constraint that individually tests an interesting capability but locks down multiple output dimen- sions (sentence count and word count and ordering) inherits the union of those dimensions’ incompat- ibilities and would distort the composition bias at highk. Composability profiles for all 38 candidates and a case study comparing an accepted constraint against a rejected one appear in Section K. Following Jiang et al. (2024b), we report two complementary satisfaction metrics. For a set of mprobes, each containingkconstraints with bi- nary outcomes s j i ∈0, 1: Strict CSR (sCSR): sCSR = 1 m m X i=1 k Y j=1 s j i (1) measures the fraction of probes where allkcon- straints are simultaneously satisfied. Marginal CSR (mCSR): mCSR = 1 mk m X i=1 k X j=1 s j i (2) measures the average per-constraint satisfaction rate. Atk=1, sCSR and mCSR are identical. Their di- vergence at higherkis the phase transition: mCSR decays gradually (each constraint fails somewhat more often under load), but sCSR collapses be- cause it is the product ofkmarginal rates. sCSR is the deployment-relevant metric—in practice, all constraints must hold simultaneously—and is where the phase transition is visible. mCSR shows that per-constraint competence is not the bottle- neck: models that pass individual constraints at 45% may succeed on complete probes only 12% of the time. We additionally report the mean continuous score ̄s i ∈ [0, 1]for each constraint, which credits near-misses (e.g., a model producing 48 words when the target is 50 scores∼0.96but passes=False). The comprehension-maintenance gap is ∆ i = ̄s i − mCSR i ,(3) where a large∆indicates that a model partially complies—demonstrating comprehension of the constraint—but fails to maintain full satisfaction. We define the compositional half-lifek ∗ for each model as the smallestkat which sCSR drops below 50%—the number of simultaneous constraints a model can reliably handle. 3.2 Probe generation CSE probes are generated procedurally (Algo- rithm 1). For each constraint countk, the composer drawsk-subsets from the constraint pool, rejects unsatisfiable combinations via the compatibility checker (Section I), instantiates parameters from fixed calibrated ranges, shuffles constraint presen- tation order, and assembles the prompt. The com- poser targets a fixed number of satisfiable probes perklevel, resampling new combinations when re- jections occur rather than accepting reduced yield. At lowk(≤5), all |C| k subsets are materialized and shuffled for uniform coverage; atk≥6, com- binations are sampled uniformly at random with a per-combination reuse cap. Compatibilitychecker. Thecompatibility checker enforces satisfiability through uncondi- tional pair blocks, parameter-dependent arithmetic checks, and cross-constraint propagation (Sec- tion I). Rejection rates increase withk: from ∼32%atk=4to∼98%atk=12; the resampling loop compensates by drawing additional combi- nations from the 36 k pool (∼24M compatible at k=12out of 36 12 ≈ 1.25B total; Table 11). The 3 resulting composition bias at highk—surviving probes exclude incompatible constraint types—is analyzed and controlled for in Section 4. Parameter control. All constraint parameters are sampled from fixed calibrated ranges held con- stant acrossk(e.g., word count targets of 40–60, lipogram bans on letters with English frequency rank 5–15), so that the phase transition measures compositional burden, not parameter variation. A Kruskal-Wallis test confirms no significant varia- tion in mean per-constraint difficulty acrosskstrata (H=6.23, p=0.96). Impossible probes. Additionally, 444 deliber- ately impossible probes test constraint prioriti- zation under logical impossibility. Each probe contains a constraint pair with a clean proof of unsatisfiability—e.g., L1 (avoid letter ‘e’) paired with L2 (include “telephone”)—and measures which constraint the model sacrifices when com- pliance is structurally unachievable. Probe types span direct contradictions between constraint pairs, hand-designed hierarchy tests (e.g., L1 vs R2 with all-‘r’ items, directly testing whether the depth-of- processing ordering extends from degradation rates to sacrifice priorities), and hidden impossibilities embedded atk=4−8to test whether impossibility detection degrades under compositional load along- side constraint satisfaction. Full probe inventory and analysis plan appear in Section R. Range ofk.We evaluate atk=1to12. Atk=12, each probe draws 33% of the constraint pool and the incompatibility rejection rate reaches∼98%, narrowing the diversity of surviving combinations; extending further yields diminishing combinato- rial coverage. The design splits the range into a training region (k=1−8) used for model fitting and a held-out region (k=9−12) used for validation (Section P). 3.3 Extraction and verification Models receive the full prompt containing a topic and allkconstraint instructions in natural language; no chain-of-thought scaffolding, decomposition hints, or constraint-ordering cues are provided. For example, a k=4 probe might read: Write a short essay about renewable energy. Your response must not contain the letter ‘e’ anywhere. Your response must contain exactly 3 paragraphs, each containing at least 2 sentences. Every word must be between 1 and 8 characters long. Your response must include all of the following words: “solar”, “carbon”, “wind”. Responses are wrapped in<answer>tags; only content inside the tags is scored. The extractor uses the last matched tag pair (handling mid-response revisions), accepts open-without-close tags so that constraints satisfied before truncation still count, and falls back to the full response when tags are ab- sent. Tag compliance is≥90%for 12 of 15 models; the three exceptions (Gemini Pro 47%, Kimi K2.6 67%, DeepSeek V4 Pro 73%) are scored via the fallback. Before verification, markdown artifacts (bold, italic, headings) that do not affect constraint semantics but interfere with character-level ver- ifiers are stripped; structural formatting (bullets, code blocks, tables) is preserved. All 36 verifiers are fully deterministic, each re- turning both a binary pass/fail judgment and a continuous scores ∈ [0, 1]representing partial compliance (Table 2; full specifications in Sec- tion H). A probe passes only if allkconstraints pass simultaneously—strict conjunction, no partial credit. 3.4 Evaluated models We evaluate 15 models across 8 families (Ta- ble 1): GPT (5.2, 5.4 Pro, 5.5), Claude (4.5 Son- net, 4.6 Opus, 4.7 Opus), Gemini (3.1 Flash-Lite, 3.1 Pro Preview), Llama (3.1 70B, 3.1 405B, 4 Mav- erick), Qwen 3 235B Instruct, DeepSeek V4 Pro, Kimi K2.6, and Grok 4.1. 4 Experiments Phase transition and decay model.All 15 mod- els exhibit the same qualitative pattern: high per- formance atk=1(70.7% aggregate sCSR), steep decline throughk=4−7, then near-zero sCSR at k≥10(Section E). This shape is consistent across all 8 families despite different architectures, scales, and training approaches. The overall mCSR across 314,108 satisfiable constraint checks is 42.8% (369,753 total checks including 55,645 on impos- sible probes; see Section R). GPT-5.5 is a notable outlier at 79.8% mCSR / 64.2% sCSR—the highest- performing model by a wide margin—while the remaining 14 models cluster between 15% and 67% mCSR. The gap between mCSR and sCSR is model-dependent: Llama 405B shows 46.4% per- constraint competence but only 12.4% probe-level success (34.0p penalty), while GPT-5.5 sustains 79.8% to 64.2% (15.6p)—a 2.2×range across these two models, widening to 12×across the full panel (Gemini Pro at 2.7p to Llama 405B 4 Table 1: Evaluated models ranked by sCSR (Equa- tion (1)) across 314,108 satisfiable constraint checks (temperature=0, greedy decode). Columns: sCSR (all-pass probe rate), mCSR (per-constraint rate, Equa- tion (2)), Score (continuous compliance, Equation (3)), k ∗ (compositional half-life: smallestkwhere sCSR drops below 50%), Tag (answer-tag compliance, Sec- tion 3.3—low fill indicates chain-of-thought leakage into scored content, itself an instruction-following fail- ure). Row shading:blue =compositionally robust (k ∗ ≥ 5),orange =cannot reliably handle even one constraint (k ∗ = 1); the 12 unshaded models cluster atk ∗ = 2−4. Ranking inversions between sCSR and mCSR reveal the compositionality penalty: Gemini Pro ranks #3 by sCSR but #11 by mCSR (Section L). ModelsCSR mCSR Score k ∗ Tag %↑%↑%↑ k↑ GPT-5.564.279.887.27 Claude 4.7 Opus49.667.080.76 Gemini 3.1 Pro39.442.158.84 Claude 4.6 Opus31.655.676.63 Gemini 3.1 Flash-Lite24.156.679.43 GPT-5.4 Pro23.235.658.53 DeepSeek V4 Pro22.422.447.13 GPT-5.218.834.057.82 Claude 4.5 Sonnet17.349.475.82 Llama 4 Maverick15.045.471.52 Qwen 3 235B Inst.12.645.771.02 Llama 3.1 405B12.446.474.62 Llama 3.1 70B11.644.671.62 Grok 4.111.342.770.82 Kimi K2.67.215.535.31 at 34.0p), reflecting differences in how correlated each model’s constraint failures are (Section J). Probe-level success becomes essentially impossi- ble past a threshold, even though individual con- straints are still satisfied at reasonable rates—this divergence between mCSR and sCSR is the phase transition. The completek-by-model table appears in Section E. Difficulty confound control. We test whether the phase transition could be an artifact if higher- kprobes systematically draw harder constraints rather than imposing genuine compositional bur- den via three independent controls.First, in- trinsic difficulty—measured as each constraint’s k=1-only pass rate to isolate single-constraint capability—shows no significant variation across kstrata (Kruskal-WallisH=6.23,p=0.96), and the compositional penalty is identical whether dif- ficulty is measured atk=1or marginally across allk(∆=0.0p at everyk). Second, stratifying probes into difficulty terciles within eachkreveals that easy, medium, and hard probes all converge to the same floor byk=5−6—even after exclud- ing the three compositionally immune constraints (L1, L5, W4). Third, constraint presentation or- der is randomized within each probe, and position shows negligible correlation with pass rate (mean |ρ|=0.029; Section N); IRT calibration preserves model rankings exactly (1PLρ=1.000on 2,952 dis- criminating probes; Section L). This suggests that the transition is driven by how many constraints are imposed, not by which ones or in what order. Two-regime decay model. If constraint failures are largely uncorrelated (Section 4), the aggregate sCSR should followP (k) = a· r k−1 . We test this by fitting onk=1−8and evaluating on held-out k=9−12(Figure 1). At the probe level (sCSR), the decay is steep:P (k) = 1.000· e −0.376k + 0.003, with sCSR dropping below 4% byk=9and below 2% byk=11. At the per-constraint level, the ag- gregate decay ismCSR(k) = 72.0%× 0.922 k−1 (held-out MAE= 0.2p)—each additional con- straint reduces the average pass rate to 92.2% of the previous level. The multiplicative model captures the aggre- gate but masks a per-model floor: 10 of 15 mod- els plateau above the prediction atk=12(mean underprediction−5.1p), sustained by composi- tionally immune constraints that require no track- ing during generation (L5: 89.7%, N2: 83.4%, L2: 80.1%; Section F). Per-model decay factors spanr = 0.721(DeepSeek V4 Pro) tor = 0.977 (Claude 4.7 Opus): slow-decay models (r > 0.93; Claude 4.7, GPT-5.5, Llama family, Claude 4.5, Flash-Lite, Qwen, Grok) sustain 30–53% atk=12; medium-decay models (r ≈ 0.86; GPT-5.2, GPT- 5.4, Gemini Pro) follow the multiplicative predic- tion; and fast-decay models (r < 0.77; DeepSeek, Kimi) collapse but stay off zero via immune con- straints. Per-kpredictions versus actuals appear in Section F. Co-failure structure. Prior work on composi- tional generalization implicitly assumes that con- straint interactions drive compositional difficulty— that specific pairs conflict, interfere, or compete for shared resources (Wen et al., 2024; Lv et al., 2026). We test this directly by computing pairwise φcoefficients across 601 constraint pairs (29 of 36 2 =630excluded for insufficient co-occurrence), conditioned onkto avoid the confound that ev- erything fails at highk. Eachφis computed per- model first (to prevent weak models from inflating co-failure rates), then aggregated via median across 5 The "compositionality penalty": individual vs. joint constraint satisfaction under compositional load 0% 20% 40% 60% 80% 100% 123456789101112 Constraint count (k) CSR (%) traintest mCSR sCSR 35p gap mCSR (per-constraint) sCSR (all-or-nothing) Multiplicative fit Decay: 72.0% × 0.922^(k−1) Held-out MAE: 0.2p 15 models, 36 constraints Figure 1: Compositional collapse: mCSR vs. sCSR with multiplicative fit. Blue: per-constraint mCSR—models still get each individual instruction right∼41%of the time atk=8, declining gently as72.0% × 0.922 k−1 (0.2p held-out MAE, dashed teal). Orange: probe- level sCSR—the chance of satisfying allkconstraints simultaneously, which drops below 4% byk=9and be- low 2% byk=11because it is the product ofkmarginal rates. Even atk=8, models still pass individual con- straints 40.7% of the time yet satisfy all eight simulta- neously only 5.7% of the time (35p gap)—the diver- gence between the two curves is the phase transition. Gray: per-model mCSR trajectories (n=15), revealing model-dependent floors—10/15 models plateau above the multiplicative prediction at k=12. models. Pairwise correlations are weak: the meanφ = +0.067and 322 pairs (54%) fall within|φ| ≤ 0.05 . Only 1 pair shows negativeφ(O4−R2, φ=−0.055), confirming that constraint selection cannot mitigate the transition—the only lever is per-constraint reliability. The elevatedφpairs share output features rather than exhibiting pairwise interference. The top three—F1−F2 (φ=0.517), L4−S2 (φ=0.501), N1−N3 (φ=0.490)—all depend on the same struc- tural output: document format (F1/F2), sentence count (L4/S2), or number count (N1/N3). When a model produces the wrong number of sen- tences, every sentence-dependent constraint fails simultaneously—not because L4 interferes with S2, but because both read from the same output feature. Within-dimension pairs show marginally higher coupling (mean|φ|=0.087) than across-dimension pairs (0.067), but this difference does not reach significance (Mann-Whitneyp=0.227) and is driven by the numerical–numerical ( ̄φ=0.275) and format–format ( ̄φ=0.241) clusters. Grouping con- straints by shared output feature rather than by di- mension confirms that within-cluster|φ|(0.113) exceeds across-cluster|φ|(0.058) atp < 10 −6 : Compositional synergy decay: actual vs. predicted sCSR 20% 20% 40% 40% 60% 60% 80% 80% 100% 100% 123456789101112 Constraint count (k) sCSR (%) Expected sCSR (%) +26p +14p +4p ≈0 Easy 94% Hard 44% Actual sCSR (%) Independence prediction Easy-anchor probes Hard-anchor probes Figure 2: Compositional synergy decay. Top: actual sCSR (%). Bottom (mirrored): predicted sCSR under independence. Shaded gap=synergy (actual−pre- dicted). Synergy drops from+26p atk=1to∼1p atk=12: models outperform the independence predic- tion at lowkbut converge to it under heavy composi- tional load. Dashed tercile curves stratify probes by per-constraint difficulty (Section 4). the co-failure structure reflects output-feature cou- pling, not cognitive interference (Section M). Con- straint failures compound near-multiplicatively— the residual correlations are mechanical, average out across the diverse constraint pool, and do not degrade the decay model’s 0.2p predictive accu- racy. Ruling out compliance mode.If models entered a focused “compliance mode” when facing easy constraints—concentrating resources to satisfy all ksimultaneously—easy probes would show arti- ficially high sCSR, inflating the synergy beyond what independence predicts. We test this by strati- fying probes at eachkinto terciles ranked by mean per-constraint difficulty: easy-tercile probes (com- posed of high-pass-rate constraints such as L5, L2, N2) start at 94% sCSR atk=1; hard-tercile probes (S4, M2, S1, W5) start at 44%. For each tercile, we compute synergy—actual sCSR minus the product of the constituent constraints’ marginal pass rates— which measures how much better models perform than the independence baseline predicts. If com- pliance mode were real, easy probes would show disproportionately high synergy from behavioral fo- cus. The opposite holds: easy-anchor probes show more synergy (+33p) than hard-anchor probes (+18p), but this is an arithmetic consequence of higher marginals producing a more pessimistic product-of-marginals baseline, not a behavioral sig- nal. Both terciles converge to∼1.5%sCSR by 6 k≈9−12regardless of starting point—initial dif- ficulty is irrelevant at saturation (Figure 2). The synergy itself decays concavely, not linearly (su- perlinearity improvement: 84% probe-level, 99% constraint-level), confirming that the transition is driven by compositional load, not by constraint- specific difficulty or model strategy. Degradation hierarchy.If constraint failures are largely uncorrelated and the transition is purely combinatorial, does every constraint degrade at the same rate? We compute per-constraint retention ret(k) = mCSR(k)/mCSR(k=1)—the fraction of baseline performance preserved at eachk—and fit a linear degradation slope. The compositional half-lifet 0.5 is the smallestkat which retention drops below 50%; constraints that never reach this threshold withink=1−12are markedt 0.5 >12in Table 2. Structural and ordering constraints degrade2.0× faster than lexical constraints (retention-normalized dimension-level slopes: structural−0.073, lexical −0.036; 95% CI on ratio:[1.9, 2.3]; Table 2). Lex- ical constraints are the slowest degraders across all 36 constraints and 15 models. The dimension hierarchy, however, is an emer- gent consequence of a more fundamental variable: the comprehension-maintenance gap∆(score− mCSR). This gap measures the difference be- tween a model’s ability to understand a con- straint (score) and its ability to maintain com- pliance throughout the response (mCSR). The gap predicts degradation rate withρ=−0.584 (p=0.0002, 95% CI:[−0.767,−0.302], boot- strap), a stronger predictor than baseline diffi- culty (ρ=+0.566) or dimension assignment. Con- straints requiring sustained attention—counting words (W1,∆=50.2p), tracking letter avoid- ance (L1,∆=48.6p), maintaining word length ranges (W2,∆=50.1p)—degrade fastest. Bi- nary constraints that require no sustained tracking— including a mandatory word (L2,∆=2.1p), pro- ducing a JSON structure (R1,∆=0.2p)—are im- mune. Composition depletes the same finite re- source that sustained constraint maintenance re- quires. Three constraints have retention> 80%atk≥8: L1 (lipogram, 95%), L5 (forbidden word, 89%), and W4 (no repeated bigrams, 86%). L1’s apparent immunity is a survivorship effect: among genuine content failures (n=4,022), 70.6% of violations occur in the first 20% of the response (median po- Table 2: Constraint profiles (36 constraints, 8 dimen- sions ordered fastest→slowest degradation).⋆indicates compositionally immune constraints (retention>80% atk≥8).t 0.5 >12indicates retention never drops be- low 50% within the evaluatedk=12range. Dimension- level slopes reported in text are observation-weighted aggregates; per-constraint slopes here are constraint- weighted, so simple averaging will not reproduce the dimension-level values. Full specifications in Table 7. Dim. Constraint k=1 mCSR ∆ Slope t 0.5 %↑%↑ p↓ ret.↑ k↑ Structural S1 Word count3914+41 −.0655 S2 Sent. count10054+20 −.0608 S3 Paragraph count10040+20 −.0655 S4 Character count198+31 −.0757 S5 Line count8937+20 −.0666 S6 Palindromic sent.4214+12 −.0624 Ordering O1 Monotonic length5229+34 −.0627 O2 Alphabetical9144+27 −.0607 O3 Alternating length8738+30 −.0675 O4 Relaxed growth6430+14 −.0616 Word-level W1 Unique words4728+50 −.0857 W2 Word length range8247+50 −.0698 W3 Min words/sent.9853+25 −.0486 W4 Unique bigrams ⋆5152+40 −.056 >12 W5 Consonant clusters4218+17 −.0597 Meta M1 Hidden message3920+22 −.0746 M2 Self-counting2213+34 −.0818 M3 Divisibility2422+36 −.073 >12 Format F1 Markdown table9464+5 −.045 12 F2 Bullet list9967+3 −.045 12 F3 Code blocks9167+3 −.051 10 F4 Unique closers9959+31 −.0479 Relational R1 Scene graph9368+0 −.031 >12 R2 Transitive ordering6536+22 −.0456 R3 Logic grid8567+3 −.037 >12 R4 Sentence bridge8630+23 −.0634 Numerical N1 Integer sum4934+19 −.0829 N2 No digits9983+16 −.035 >12 N3 Distinct numbers5234+22 −.077 10 N4 Equations8866+8 −.047 12 Lexical L1 Lipogram ⋆4751+49 −.052 >12 L2 Mandatory words9880+2 −.032 >12 L3 Sentence initial9348+17 −.0658 L4 Acrostic9950+19 −.0586 L5 Forbidden word ⋆9890+10 −.011 >12 L6 Vowel/cons. ratio8164+19 −.030 >12 sition 0.078)—models collide with the forbidden letter almost immediately or not at all, a vocabulary collision at generation onset rather than a capacity that erodes under compositional load. Full fail- ure mode decomposition, per-model profiles, and control analyses appear in Section G. Constraint prioritization under impossibility. CSE includes 444 impossible probes (55,645 con- straint checks across 15 models), each with a proof 7 Sacrifice pattern: deterministic constraint triage under impossibility 0%25%50%75%100% mCSR on impossible probes (%) L1 vs L2 L1=0%L2=73% N1 vs N2 N1=0%N2=91% N3 vs N2 N3=0%N2=91% N4 vs N2 N4=4%N2=84% O4 vs O3 O4=0%O3=56% W1 vs R4 W1=2%R4=62% O1+S6 O1=7%S6=4% L1 vs R2 L1=7%R2=33% Concrete inclusion > abstract avoidance Prohibition > requirement Natural structure > imposed structure Planning investment preserved Figure 3: Constraint sacrifice under impossibility. Three deterministic rules hold across all 15 models: concrete inclusion beats abstract avoidance (L2: 73%, L1: 0%), prohibition beats requirement (N2: 91%, N1: 0%), and natural prose beats imposed structure (O3: 56%, O4: 0%). The hierarchy inversion (L1 sacrificed for R2) suggests models preserve whichever constraint re- quired greater planning investment. Full analysis in Section R.2. of unsatisfiability (Section R). Zero probe×model pairs pass all constraints on any impossible probe: the deterministic verifiers are airtight. When forced to choose which constraint to vio- late, models reveal deterministic sacrifice priorities (Figure 3). Three rules emerge across all 15 models, unanimous and stable across k (Section R.2). 5 Interventions The multiplicative structure makes differential pre- dictions about what should help. If the collapse is set by per-constraint reliability rather than by disor- ganised generation, then restructuring the prompt should not shift it, while supplying additional attempts should buy a bounded improvement— bounded because, were failures on a given probe independent across resamples,Nretries would re- cover1− (1− p) N . We test three interventions, each on three models: pre-generation planning (a plan-first scaffold prepended to the prompt, run against a token-matched no-scaffold control), post- hoc self-correction (a second pass that re-prompts the model with its own output to check and re- vise), and best-of-5 retries (five independent gen- erations, the probe passing if any one satisfies all constraints). Throughout we report the composi- tional half-lifek ∗ : the smallestkat which probe- level success (sCSR) falls below 50%. Table 3 gives the per-model results. InterventionModelk ∗ Effect Planning Claude 4.7 Opus6→ 7 ∆r=−0.017 GPT-5.58→ 7 ∆r=+0.021 DeepSeek V4 Pro5→ 5 ∆r=+0.014 Self-correction Claude 4.7 Opus5→ 6 −0.0p GPT-5.57→ 8 +3.7p DeepSeek V4 Pro3→ 4 +11.5p Best-of-5 GPT-5.22→ 4 +22 / +53p Claude 4.6 Opus3→ 5 +22 / +54p Llama 4 Maverick 2→ 3 +24 / +51p Table 3: Effect of each intervention on the composi- tional half-lifek ∗ . Planning compares scaffold against a token-matched control; self-correction and best-of-5 compare against the single-pass baseline. Effect column: change in per-constraint decay factorrfor planning, change in sCSR for self-correction, and peak observed sCSR lift against the lift that independent resampling predicts for best-of-5. Planning does nothing; output budget does. Aggregate per-constraint decay is unchanged— control93.0%×0.948 k−1 against scaffold90.2%× 0.952 k−1 —and∆k ∗ is inconsistent in sign, with the strongest model regressing. Scaffold compli- ance was 100%, 100%, and 56%, so the null is not models ignoring the instruction. The output bud- get, by contrast, moves the threshold on its own: DeepSeek’s decay factor rises from0.730to0.877 andk ∗ from 3 to 5 between the baseline and the token-matched control, with no scaffold involved. Retries and correction help, and then plateau. Both recover one to two constraints, and self- correction returns most where per-constraint re- liability is worst—the ordering the mechanism pre- dicts, since a correction pass rescues borderline probes. The instructive number is the last column of Table 3: best-of-5 delivers roughly two-fifths of the lift that independent resampling predicts, despite draws being near-fully distinct (4.98–4.99 of 5). The model repeats the same failure across draws. Two senses of independence.This bounded ceil- ing does not contradict Section 4. Independence there holds across constraints within a response, which is what makes sCSR multiplicative. Best-of- Nprobes independence across resamples of one probe, which is where the correlation lies. Both hold: which constraints fail within a response is close to independent, while whether a given probe fails is largely deterministic across draws. 8 What moves the threshold.Adding attempts or a correction pass buys one to two constraints; re- structuring the prompt buys none; none removes the collapse. Per-constraint reliability remains the operative lever, with retries, a correction pass, and an adequate output budget as deployment-time pal- liatives. Each intervention was run on three models rather than all 15; GPT-5.5 rejects the temperature parameter and is therefore absent from the retry experiment; and the self-correction comparison is directional rather than strictly paired, as a small number of second-pass generations failed. 6 Discussion A combinatorial consequence.The decay does not require constraint interference to arise—it fol- lows from a simple arithmetic fact: the product of many numbers slightly less than 1.0 converges to zero. Unlikek-SAT phase transitions (Mertens et al., 2006; Mézard and Montanari, 2009), our de- cay requires no interaction structure; it is pure mul- tiplicative accumulation. The primary lever to shift the transition rightward is improving per-constraint reliability; there is no shortcut through constraint selection. Inference-time interventions such as constrained decoding (Lu et al., 2021, 2022), at- tention steering (Lv et al., 2026), and structured generation frameworks (Willard and Louf, 2023; Beurer-Kellner et al., 2023) can enforce some con- straints externally, potentially shifting what counts as the model’s “native” capability vs. the sys- tem’s. Whether such scaffolding delays the on- set or merely raises the floor—and whether chain- of-thought or decomposition prompting would let models manage more constraints by planning explicitly—remains open. CSE deliberately evalu- ates raw generation without scaffolding to isolate the model’s intrinsic compositional capacity; mea- suring the effect of scaffolding is a natural follow- up. The difficulty-stratification analysis (Section 4) provides indirect evidence that the transition is not driven by constraint familiarity: probes composed entirely of easy constraints—those models handle at 70–85% in isolation—show the same qualitative collapse atk=5−6as probes with hard constraints, suggesting the bottleneck is compositional capacity rather than per-constraint knowledge. Post-training shapes failure mode, not composi- tional capacity. Refusal strategies vary dramat- ically across model families: GPT-5.2 and GPT- 5.4 refuse∼50%of satisfiable probes they fail on, while Llama, Grok, and Flash-Lite refuse<1%. Within the GPT family, refusal decreases as capa- bility improves (GPT-5.5: 17%), suggesting that stronger models learn to distinguish genuine im- possibility from difficulty. This pattern is consis- tent with RLHF-trained refusal calibration (Ouyang et al., 2022) rather than a universal difficulty sig- nal. Post-training also shapes tag compliance: reasoning-heavy models (Claude 4.7, DeepSeek) spend tokens on chain-of-thought that either ex- hausts the output budget or bypasses answer tags, suppressing measured performance. These are instruction-following failures in their own right, but they reflect alignment training choices rather than intrinsic compositional limits—the same model with a larger token budget (Claude 4.7 at 16,384 vs 4,096 tokens) jumps from rank #10 to #2 without any change to its compositional capacity. Deployment implications. Production systems assuming linear degradation will experience unex- pected failures: a system reliable with 3 constraints may fail significantly with 5. Per-model decay fac- tors (r = 0.721to0.977) enable estimation of the maximumkat which a model meets a target com- pliance rate—for 90%, most models handle at most 1–2 constraints; the best (GPT-5.5,k ∗ =7) is lim- ited to∼6. Continuous compliance metrics over- estimate true satisfaction by up to 50p near the transition boundary (W1: 78.6% score vs. 28.4% mCSR; Equation (3)); strict binary verification is essential. Scale does not predict compositional perfor- mance. Counter to typical scaling expectations, we observe multiple ranking inversions: Gem- ini Pro ranks #2 atk=1(90.5% single-constraint pass rate) but #11 overall (42.1% mCSR); Flash- Lite ranks #6 atk=1(78.1%) but #3 overall (56.6%). Single-constraint competence does not predict compositional robustness—the models that understand constraints best in isolation are not nec- essarily the ones that compose them most reliably. A capacity parallel.The 5–6 constraint ceiling is strikingly close to human working memory limits: Miller’s7±2chunks (Miller, 1956) and Cowan’s more conservative4±1(Cowan, 2001). We do not claim a shared mechanism—LLMs do not have a working memory bottleneck in the cognitive sense— but the convergence suggests that compositional constraint satisfaction may face a capacity limit that is loosely independent of the substrate. Whether 9 this reflects a fundamental information-theoretic bound on simultaneous constraint tracking or a co- incidence of current architectures is an open ques- tion. 7 Conclusion CSE reveals that compositional instruction follow- ing degrades via a predictable multiplicative pat- tern, with reliable performance breaking down beyond 5–6 simultaneous constraints across all 15 models tested. A depth-of-processing hierar- chy governs which constraints fail first—structural constraints degrade2×faster than lexical ones— driven by processing demands rather than intrin- sic difficulty. Three directions would advance this work: measuring whether inference-time scaffold- ing shifts the transition rightward, testing invari- ance to constraint novelty, and measuring how con- straint load degrades primary-task accuracy. Limitations Conjunctive composition only. CSE evaluates pure conjunction: allkconstraints must hold simultaneously. Other composition structures— sequential chaining, conditional branching, nested dependencies (Wen et al., 2024)—may exhibit dif- ferent decay profiles and are left to future work. Verifiability selection bias. The 30 constraint types are chosen to be deterministically verifiable, which systematically excludes semantic, pragmatic, and discourse-level constraints (coherence, infor- mativeness, tone consistency, factual accuracy). This is the design tradeoff that enables CSE’s measurement invariance—the same compositional degradation that affects model generation would compromise an LLM-based judge in exactly the regime we study. Ecological validity.Thek=12regime is deliber- ately a stress test, not a simulation of typical deploy- ment. Real-world systems typically combine 2–6 high-level constraints (format, length, tone, content domain, safety boundaries) plus implicit norms. The practical implication of CSE’s findings lies at k=5−6—where the transition occurs—which falls within the range of realistic deployment constraint counts. Adversarial implications. The phase transition reveals a potential attack vector: an adversary aware that models reliably fail beyondk=5−6con- straints could craft prompts with many simultane- ous constraints to overwhelm safety-related con- straints, exploiting the finding that relational and structural constraints are dropped before surface- level ones. Characterizing this vulnerability is a prerequisite for defending against it. Specification gap exploitation.A systematic au- dit of all passing responses identifies four speci- fication gaps that models exploit under composi- tional pressure (Figure 4). Empty code blocks (F3, 82.4% of passes—models emit delimiter pairs with no content, ranging from 50.7% for Claude 4.5 to 100% for GPT-5.2/5.5) and palindromic sentence copying (S6, 19.4%—models duplicate sentences reversed to guarantee matched word counts, with strong model separation: Llama 405B at 83.3% vs. Claude models at≤8%) are the highest-prevalence patterns. Two-sentence trivial satisfaction of contra- dictory ordering constraints (O1+O3, 6 cases) and unicode escape substitution to bypass word unique- ness (W1, 10 cases) are quantitatively negligible. None of these gaps compromise the benchmark’s core findings: the difficulty-stratified analysis (Sec- tion 4) confirms that all terciles converge to the same floor, including after excluding composition- ally immune constraints, and the same robustness extends to exploitable ones—no single constraint drives any result. The gaps reveal that models un- der compositional load adopt mechanical shortcuts over genuine compliance—itself a finding about resource allocation under pressure—and all four are straightforward to close in future iterations. References Kaikai An, Li Sheng, Ganqu Cui, Shuzheng Si, Ning Ding, Yu Cheng, and Baobao Chang. 2025. ULTRA- IF: Advancing instruction following from the wild. arXiv preprint arXiv:2502.04153. Esma Balkır, Alice Pernthaller, Marco Basaldella, José Hernández-Orallo, and Nigel Collier. 2026. Con- fident rankings with fewer items: Adaptive LLM evaluation with continuous scores. arXiv preprint arXiv:2601.13885. Luca Beurer-Kellner, Marc Fischer, and Martin Vechev. 2023. Prompting is programming: A query language for large language models. In Proceedings of the 44th ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI). Howard Chen, Huihan Li, Danqi Chen, and Karthik Narasimhan. 2022.Controllable text genera- tion with language constraints.arXiv preprint arXiv:2212.10466. 10 (a) Empty code blocks + unicode escapes GPT-5.5 — CSE-E-k6-4693 (k=6) F3Code blocks: 0/2 non-empty (total: 2, empty: 2) W51/1 sentences meet ≥6 cluster words (passed via split) R36/6 correct (checked against 2 valid solution(s)) W126/26 unique words (passed via split) S5Target: 5 lines, Actual: 5 (off by 0) R2Expected: ['Florence', 'Portland', 'Barcelona', 'Toronto', 'Reykjavik', 'Amsterdam'], Got: ['Florence', 'Portland', 'Barcelona', 'Toronto', 'Reykjavik', 'Amsterdam'] (6/6) Specification gap: F3 + W1 Model response: Textile manufacturing history spans ancient workshops, craftspeople, strengthened spindles, Manchester factories, industrial looms, transformed marketplaces; pets "Alice":"pet":"cat","color":"red","Bob":" 0070et":"fish"," 0063olor":"blue"," Carol":"p 0065t":"dog","c 006flor":"green"; population numbered-list ranks 1st=Florence, 2nd=Portland, 3rd=Barcelona, 4th=Toronto, 5th=Reykjavik, 6th=Amsterdam. ``` ``` ``` ``` (b) Palindrome sentence copying Llama 405B — CSE-E-k1-0003 (k=1) S6Sentences: 7/7 | Word counts: [13,14,27,57,27,14,13] | Palindrome: 3/3 pairs match | COPIED: 3/3 mirror pairs identical Specification gap: S6 Model response: Bridges are designed to handle various types of stress, including tension and compression. Engineers use different materials and techniques to distribute the weight evenly across the bridge. The structure is typically composed of multiple layers, with each layer serving a specific purpose, such as providing support or stability, and is usually around twenty words. The main components of a bridge, including the deck, piers, and abutments, work together to resist external forces like wind, earthquakes, and the weight of vehicles, while also withstanding the internal forces that arise from the interactions between these components, and the way these forces change over time as the bridge is used and environmental conditions change. The structure is typically composed of multiple layers, with each layer serving a specific purpose, such as providing support or stability, and is usually around twenty words. Engineers use different materials and techniques to distribute the weight evenly across the bridge. Bridges are designed to handle various types of stress, including tension and compression. (c) 2-sentence trivial O1+O3 DeepSeek V4 Pro — CSE-IMP-A4-02 (k=2) O1Direction: increasing | Word counts: [5,32] | 1/1 pairs OK O3Word counts: [5,32] | 2/2 in correct position Specification gap: O1 + O3 Model response: Optical illusions trick our brains. They exploit the inherent assumptions and shortcuts within our visual processing system, causing us to perceive motion, depth, or color that does not actually exist in the static image before our eyes. Figure 4: Three specification gap exploitations. (a) GPT-5.5 on CSE-E-k6-4693: satisfies F3 (2 code blocks) with four empty“‘delimiters and W1 (unique words) via unicode escapes ( 0070etfor “pet”). (b) Llama 405B on CSE-E-k1-0003: satisfies S6 (palindromic word counts) by copying sentences 1–3 as sentences 5–7 reversed, guaranteeing identical word counts without generating original content. (c) DeepSeek V4 Pro on CSE-IMP-A4-02: satisfies both O1 (monotonic) and O3 (alternating) with exactly 2 sentences—a short sentence followed by a long one—exploiting the absence of a minimum sentence count requirement. Jiale Cheng, Xiao Liu, Cunxiang Wang, Xiaotao Gu, Yida Lu, Dan Zhang, Yuxiao Dong, Jie Tang, Hongn- ing Wang, and Minlie Huang. 2025. SPaR: Self-play with tree-search refinement to improve instruction- following in large language models. In The Thir- teenth International Conference on Learning Repre- sentations. Vanya Cohen, Geraud Nangue Tasse, Nakul Gopalan, Steven James, Matthew Gombolay, Raymond Mooney, and Benjamin Rosman. 2024. Composi- tional instruction following with language models and reinforcement learning. Transactions on Ma- chine Learning Research. ArXiv:2501.12539. Nelson Cowan. 2001. The magical number 4 in short- term memory: A reconsideration of mental storage capacity. Behavioral and Brain Sciences, 24(1):87– 114. Guanting Dong, Keming Lu, Chengpeng Li, Tingyu Xia, Bowen Yu, Chang Zhou, and Jingren Zhou. 2025. Self-play with execution feedback: Improving instruction-following capabilities of large language models. In The Thirteenth International Conference on Learning Representations. Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lor- raine Li, Liwei Jiang Jiang, Bill Yuchen Lin, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D Hwang, Soumya Sanyal, Sean Welleck, Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi. 2023. Faith and fate: Limits of transformers on com- positionality. In Advances in Neural Information Processing Systems, volume 36. Alessandro Favero, Antonio Sclocchi, Francesco Cagnetta, Pascal Frossard, and Matthieu Wyart. 2025. How compositional generalization and creativity im- prove as diffusion models are trained. In Forty- second International Conference on Machine Learn- ing. Thomas Palmeira Ferraz, Kartik Mehta, Yu-Hsiang Lin, Haw-Shiuan Chang, Shereen Oraby, Sijia Liu, Vivek Subramanian, Tagyoung Chung, Mohit Bansal, and Nanyun Peng. 2024. Llm self-correction with De- CRIM: Decompose, critique, and refine for enhanced following of instructions with multiple constraints. In Advances in Neural Information Processing Sys- tems. Haosheng Gan, Berk Tinaz, Mohammad Shahab Sepehri, Zalan Fabian, and Mahdi Soltanolkotabi. 2025. ConceptMix++: Leveling the playing field in text-to-image benchmarking via iterative prompt optimization. arXiv preprint arXiv:2507.03275. Zhengkang Guo, Wenhao Liu, Mingchen Xie, Jing- wen Xu, Zisu Huang, Muzhao Tian, Jianhan Xu, Yuanzhe Shen, Qi Qian, Muling Wu, Xiaohua Wang, Changze Lv, HeDa Wang, Hu Yao, Xiaoqing Zheng, and Xuanjing Huang. 2025. RECAST: Expanding the boundaries of LLMs’ complex instruction fol- lowing with multi-constraint data. arXiv preprint arXiv:2505.19030. Jordan Hoffmann, Sebastian Borgeaud, Arthur Men- sch, Elena Buchatskaya, Trevor Cai, Eliza Ruther- ford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, and 1 others. 2022. Training compute-optimal large language models. In Advances in Neural Information Processing Systems, volume 35, pages 30016–30030. Cheng-Yu Hsieh, Jieyu Zhang, Zixian Ma, Anirud- dha Kembhavi, and Ranjay Krishna. 2023. Sug- arCrepe: Fixing hackable benchmarks for vision- language compositionality. In Advances in Neural Information Processing Systems, volume 36. Irene Huang, Wei Lin, M. Jehanzeb Mirza, Jacob A. Hansen, Sivan Doveh, Victor Ion Butoi, Roei Herzig, Assaf Arbelle, Hilde Kuehne, Trevor Darrell, Chuang Gan, Aude Oliva, Rogerio Feris, and Leonid Karlin- sky. 2024. ConMe: Rethinking evaluation of compo- sitional reasoning for modern VLMs. arXiv preprint arXiv:2406.08164. 11 Kaiyi Huang, Chengqi Duan, Kaiyue Sun, Enze Xie, Zhenguo Li, and Xihui Liu. 2023.T2I- CompBench++: An enhanced and comprehensive benchmark for compositional text-to-image genera- tion. arXiv preprint arXiv:2307.06350. Qianyu Jiang, Jie Zeng, Qianxi He, Jiaqing Liang, and Yanghua Xiao. 2024a. From complex to simple: En- hancing multi-constraint complex instruction follow- ing ability of large language models. In Findings of the Association for Computational Linguistics: EMNLP. Yuxin Jiang, Yufei Wang, Xingshan Zeng, Wanjun Zhong, Liangyou Li, Fei Mi, Lifeng Shang, Xin Jiang, Qun Liu, and Wei Wang. 2024b. Follow- Bench: A multi-level fine-grained constraints fol- lowing benchmark for large language models. In Proceedings of the 62nd Annual Meeting of the Asso- ciation for Computational Linguistics. Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. 2020. Scaling laws for neural language models. arXiv preprint arXiv:2001.08361. Brenden M Lake and Marco Baroni. 2018. General- ization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks. In International Conference on Machine Learning (ICML). Beiqi Li, Zhiqui Lin, Deepak Pathak, Jiayao Li, Yixin Fei, Kewen Wu, Tiffany Ling, Xide Xia, Pengchuan Zhang, Graham Neubig, and Deva Ramanan. 2024. GenAI-Bench: Evaluating and improving compo- sitional text-to-visual generation. arXiv preprint arXiv:2406.13743. Peiyu Li, Xiuxiu Tang, Si Chen, Ying Cheng, Ronald Metoyer, Ting Hua, and Nitesh V. Chawla. 2025. Adaptive testing for LLM evaluation: A psychomet- ric alternative to static benchmarks. arXiv preprint arXiv:2511.04689. Zhixiang Liang, Zhenyu Hou, and Xiao Wang. 2025. Fine-grained constraint generation-verification for improved instruction-following. In Proceedings of the Fourth Workshop on Generation, Evaluation and Metrics (GEM 2 ), pages 862–879, Vienna, Austria. Association for Computational Linguistics. Wei Liu, Yancheng He, Yu Li, Hui Huang, Cheng- wei Hu, Jiaheng Liu, Shilong Li, Wenbo Su, and Bo Zheng. 2025. AIR: Complex instruction gen- eration via automatic iterative refinement. arXiv preprint arXiv:2502.17787. Ximing Lu, Sean Welleck, Peter West, Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ronan Le Bras, Lian- hui Qin, Youngjae Yu, Rowan Zellers, Noah A Smith, and Yejin Choi. 2022. NeuroLogic A*esque de- coding: Constrained text generation with lookahead heuristics. In Proceedings of NAACL. Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. 2021. Neuro- Logic decoding: (un)supervised neural text genera- tion with predicate logic constraints. In Proceedings of NAACL. Yuheng Lu, ZiMeng Bai, Caixia Yuan, Huixing Jiang, and Xiaojie Wang. 2025. Enhancing complex in- struction following for large language models with mixture-of-contexts fine-tuning.arXiv preprint arXiv:2505.11922. Fangrui Lv, Yulei Qin, Ruixin Hong, Jian Liang, Jinyang Wu, Ke Li, Xing Sun, and Changshui Zhang. 2026. Attend to the active: Structure-aware dynamic atten- tion in LLMs for compositional instruction following. In International Conference on Learning Representa- tions (ICLR). Stephan Mertens, Marc Mézard, and Riccardo Zecchina. 2006. Threshold values of random K-SAT from the cavity method. Random Structures & Algorithms, 28(3):340–373. Marc Mézard and Andrea Montanari. 2009. Informa- tion, Physics, and Computation. Oxford University Press. George A. Miller. 1956. The magical number seven, plus or minus two: Some limits on our capacity for processing information. Psychological Review, 63(2):81–97. Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, and 1 others. 2022. Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems. Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah A Smith, and Mike Lewis. 2023. Measuring and narrowing the compositionality gap in language models. In Findings of the Association for Computa- tional Linguistics: EMNLP. Valentina Pyatkin, Saumya Malik, Victoria Graf, Hamish Ivison, Shengyi Huang, Pradeep Dasigi, Nathan Lambert, and Hannaneh Hajishirzi. 2025. Generalizing verifiable instruction following. arXiv preprint arXiv:2507.02833. Yunjia Qi, Hao Peng, Xiaozhi Wang, Bin Xu, Lei Hou, and Juanzi Li. 2024. Constraint back-translation im- proves complex instruction following of large lan- guage models. arXiv preprint arXiv:2410.24175. Yiwei Qin, Kaiqiang Song, Yebowen Hu, Wenlin Yao, Sangwoo Cho, Xiaoyang Wang, Xuansheng Wu, Fei Liu, Pengfei Liu, and Dong Yu. 2024. InFoBench: Evaluating instruction following ability in large lan- guage models. In Findings of the Association for Computational Linguistics: ACL 2024. 12 Huimin Ren, Yan Liang, Baiqiao Su, Chaobo Sun, Hengtong Lu, Kaike Zhang, and Chen Wei. 2025. LexInstructEval: Lexical instruction following eval- uation for large language models. arXiv preprint arXiv:2511.17561. Yusuke Sakai, Hidetaka Kamigaito, and Taro Watan- abe. 2025.Revisiting compositional generaliza- tion capability of large language models consider- ing instruction following ability. arXiv preprint arXiv:2506.15629. Haoran Sun, Lixin Liu, Junjie Li, Fengyu Wang, Bao- hua Dong, Ran Lin, and Ruohui Huang. 2024a. Conifer: Improving complex constrained instruction- following ability of large language models. arXiv preprint arXiv:2404.02823. Kaiyue Sun, Kaiyi Huang, Xian Liu, Yue Wu, Zi- han Xu, Zhenguo Li, and Xihui Liu. 2024b. T2V- CompBench: A comprehensive benchmark for com- positional text-to-video generation. arXiv preprint arXiv:2407.14505. Tristan Thrush, Ryan Jiang, Max Bartolo, Amanpreet Singh, Adina Williams, Douwe Kiela, and Candace Ross. 2022. Winoground: Probing vision and lan- guage models for visio-linguistic compositionality. In Proceedings of CVPR. Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, and 1 others. 2022. Emergent abilities of large language models. Transactions on Machine Learning Re- search. Bosi Wen, Pei Ke, Xiaotao Gu, Lindong Wu, Hao Huang, Jinfeng Zhou, Wenchuang Li, Binxin Hu, Wendy Gao, Jiaxin Xu, and 1 others. 2024. Com- plexBench: Benchmarking complex instruction fol- lowing with multi-constraint composition. In Ad- vances in Neural Information Processing Systems. Brandon T. Willard and Rémi Louf. 2023. Efficient guided generation for large language models. arXiv preprint arXiv:2307.09702. Xindi Wu, Dingli Yu, Hangsibo Huang, Olga Rus- sakovsky, and Sanjeev Arora. 2024. ConceptMix: A compositional image generation benchmark with con- trollable difficulty. arXiv preprint arXiv:2408.14339. Shunyu Yao, Howard Chen, Austin W Hanjie, Runzhe Yang, and Karhik R Narasimhan. 2024. COLLIE: Systematic construction of constrained text genera- tion tasks. In Proceedings of ICLR. Junjie Ye, Caishuang Huang, Zhuohan Chen, Wen- jie Fu, Chenyuan Yang, Leyi Yang, Yilong Wu, Peng Wang, Meng Zhou, Xiaolong Yang, Tao Gui, Qi Zhang, Zhongchao Shi, Jianping Fan, and Xuan- jing Huang. 2025. A multi-dimensional constraint framework for evaluating and improving instruction following in large language models. arXiv preprint arXiv:2505.07591. Junjie Ye, Guoqiang Zhang, Wenjie Fu, Tao Gui, Qi Zhang, and Xuanjing Huang. 2026. CCTU: A benchmark for tool use under complex constraints. arXiv preprint arXiv:2603.15309. Jie Zeng, Qianyu He, Qingyu Ren, Jiaqing Liang, Yanghua Xiao, Weikang Zhou, Zeye Sun, and Fei Yu. 2025. Order matters: Investigate the position bias in multi-constraint instruction following. arXiv preprint arXiv:2502.17204. Ziqian Zhong, Aditi Raghunathan, and Nicholas Car- lini. 2025. ImpossibleBench: Measuring LLMs’ propensity of exploiting test cases. arXiv preprint arXiv:2510.20270. Jeffrey Zhou, Tianjian Lu, Swaroop Mishra, Siddhartha Brahma, Sujoy Basu, Yi Luan, Denny Zhou, and Le Hou. 2023. Instruction-following evaluation for large language models. In Advances in Neural Infor- mation Processing Systems. A Reproducibility All probes, deterministic verifiers, raw model out- puts, and evaluation code will be released upon pub- lication. The total evaluation comprises 67,905 API calls (15 models×4,527 probes) at temperature=0 with greedy decoding.Four of 15 evaluated models are open-weight and fully reproducible: Llama 3.1 70B and 405B Instruct, Llama 4 Maver- ick, and Qwen 3 235B Instruct. Proprietary model outputs are included in the release for verification. The probe composer, compatibility checker, cali- brated parameter sampling distributions, and all 36 verification functions are included in the released code. B Related Work (Expanded) This section provides an expanded version of the related work discussion summarized in Section 1. B.1 Compositional Instruction Following Evaluation benchmarks. IFEval (Zhou et al., 2023) established the paradigm of verifiable in- struction following with 25 constraint types and deterministic programmatic checks, but probes typ- ically containk ≤ 3constraints—insufficient to observe compositional degradation. A model scor- ing 80%+ on IFEval could in principle collapse atk=5−8on CSE, exposing degradation invisible to proficiency-oriented evaluation. Adaptive IRT methods (Balkır et al., 2026) extend the evalua- tion paradigm by enabling confident model rank- ings with fewer test items, though they require 13 more examinees than CSE’s 15-model panel. In- foBench (Qin et al., 2024) decomposes each in- struction into atomic verifiable criteria and evalu- ates per-criterion satisfaction via its Decomposed Requirements Following Rate (DRFR). GPT-4 achieves∼89%DRFR overall, yet more than 10% of requirements remain unfulfilled even for this strongest model, and no model fully satisfies num- ber or linguistic constraints. Performance is highest on content and style, intermediate on format, and lowest on number and linguistic dimensions—a constraint-type hierarchy that foreshadows CSE’s depth-of-processing finding, where structural con- straints degrade2.0×faster than lexical ones. In- foBench operates at the single-instruction level; CSE extends this analysis systematically across k=1to12, revealing how per-criterion gaps com- pound into the phase transition. FollowBench (Jiang et al., 2024b) scales tok=5and introduces the Consistent Satisfaction Level (CSL) metric for tracking partial compliance across difficulty levels, but relies on GPT-4 as a judge for several constraint types, introducing evaluation variance. CSL mea- sures which satisfaction level a model can sustain, which is conceptually adjacent to CSE’sk-curve— but CSE isolates where the transition occurs rather than tracking cumulative levels, and uses fully de- terministic verification throughout. COLLIE (Yao et al., 2024) is the closest prior work: it pioneered grammar-based constraint specification with for- mal CFG definitions and corpus-grounded extrac- tion ensuring natural solutions exist, and demon- strated that compositional constraints are harder than individual ones—a finding we confirm and extend. Three key differences: (1) COLLIE uses fixed constraint compositions while CSE systemat- ically varieskfrom 1–12, enabling the decay char- acterization that is this paper’s central contribution; (2) COLLIE reports that composition is hard but does not quantify where capability breaks or what functional form the degradation takes; (3) CSE’s dual scoring (binary + continuous) reveals gaps be- tween partial compliance and strict satisfaction that are absent from COLLIE’s binary-only evaluation. COLLIE is stronger in formal rigor (CFG gram- mar) and in its pass@kevaluation design; CSE contributes the systematic scaling analysis and the mechanistic decomposition of why composition fails. Complex constraint benchmarks. RECAST (Guo et al., 2025) pushes constraint counts to k=13+with 19 constraint types and proposes RLVC training with constraint-specific reward sig- nals, but does not report per-kperformance trajec- tories, precluding decay analysis. ComplexBench (Wen et al., 2024) models constraint composition structure—And, Chain, Selection, Nesting—rather than count, and is thus orthogonal to our analy- sis of how many constraints can be jointly sat- isfied. IFBENCH (Pyatkin et al., 2025) demon- strates that models overfit to IFEval’s 25 known constraint types and proposes IF-RLVR training for generalization—a different axis (unseen con- straints) from our focus (composition scaling). CCTU (Ye et al., 2026) evaluates constrained tool use, finding that no model exceeds 20% task com- pletion under strict multi-constraint adherence—a ceiling remarkably close to CSE’s probe-level floor atk≥9, despite a completely different task domain, suggesting the phase transition may reflect a gen- eral property of LLM compositional processing. Training methods. Conifer (Sun et al., 2024a) generates multi-level constraints with GPT-4 and employs curriculum tuning, while AutoIF (Dong et al., 2025) implements self-dialogue with execution-based verification; AIR (Liu et al., 2025) and MiSO (Lu et al., 2025) extend automatic re- finement and mixture-of-contexts fine-tuning, re- spectively, to complex instruction generation—all focus on training rather than diagnostic evaluation. MulDimIF (Ye et al., 2025) explores how constraint presentation mode (example, listing, incorporation) affects following and proposes GRPO training; LexInstructEval (Ren et al., 2025) introduces a for- mal grammar for lexical constraints with bilingual evaluation, finding that procedural depth degrades performance—complementary to our finding that constraint count does so. UltraIF (An et al., 2025) scales to 100K+ instructions via automatic con- straint decomposition; SPaR (Cheng et al., 2025) uses self-play with tree-search refinement for sim- ilar scaling. DeCRIM (Ferraz et al., 2024) takes a complementary approach, decomposing multi- constraint instructions into individual constraints and iteratively refining compliance; related de- composition strategies include Complex-to-Simple (Jiang et al., 2024a) and constraint back-translation (Qi et al., 2024)—approaches whose effectiveness CSE’s independence finding predicts, since failures accumulate per-constraint rather than through pair- wise interference. FiGV (Liang et al., 2025) syn- thesizes constraint-augmented training data with 14 hybrid LLM/function verification at the constraint level, confirming that deterministic verification of individual constraints produces higher-quality train- ing signal than holistic LLM judgment—a principle CSE applies to evaluation. Chen et al. (2022) for- malize controllable generation as satisfaction of language constraints, bridging constrained decod- ing and instruction following. Neurologic Decod- ing (Lu et al., 2021, 2022) approaches constraint satisfaction from the inference side via lexically- constrained beam search; more recent structured generation frameworks (Willard and Louf, 2023; Beurer-Kellner et al., 2023) can enforce format and keyword constraints at the decoding level, remov- ing them from the model’s compositional burden entirely. CSE evaluates raw generation without such scaffolding to isolate intrinsic compositional capacity; measuring how constrained decoding or chain-of-thought prompting shifts the transition is a natural follow-up (Section 6). Mechanistic explanations.ATA (Lv et al., 2026) identifies a mechanistic explanation for compo- sitional degradation:models diffusely attend across all sub-tasks in the input, and inactive sub- tasks cause interference via attention distraction— corroborating our phase transition with perfor- mance drops from 60% to 48% as sub-task count increases. Their inference-time attention steering recovers 6–10p without retraining, demonstrating that the transition is partially addressable through architectural intervention. In reinforcement learn- ing, CERLLA (Cohen et al., 2024) demonstrates that compositional value function representations with Boolean task algebra (AND, OR, NOT) en- able sample-efficient learning of 162 language- conditioned tasks. CSE’s constraint composition is purely conjunctive (allkconstraints must hold simultaneously), but the shared insight is that com- positional structure—whether in policy space or constraint space—determines scalability. B.2 Constraint Scaling and Cross-Modal Parallels Interaction vs. accumulation. A central ques- tion in compositional evaluation is whether diffi- culty arises from constraint interactions (specific pairs that conflict) or from accumulation (each ad- ditional constraint independently reducing success probability). ComplexBench (Wen et al., 2024) models structural interactions through nesting and branching but does not measure pairwise statistical independence. Zeng et al. (2025) demonstrate that constraint ordering affects performance by up to 25%, establishing that presentation matters—we find this effect is orthogonal to constraint count (Section 4). Ordered CommonGen (Sakai et al., 2025) evaluates whether LLMs can generate sen- tences with concepts in a specified order across 36 models, finding that even the best model follows the specified order only 75% of the time on a single or- dering constraint. CSE’s ordering constraints show similarly lowk=1rates (O1 monotonic length: 28.9%, O2 alphabetical: 43.7%), and these per- constraint imperfections are precisely what com- pound multiplicatively to produce the phase transi- tion. Phase transitions and scaling laws. Our find- ing that constraint failures are weakly correlated connects to the theoretical literature on phase tran- sitions in constraint satisfaction. Randomk-SAT exhibits a sharp satisfiability threshold driven by clause density and interaction structure (Mertens et al., 2006; Mézard and Montanari, 2009). Our transition is mechanistically simpler: it arises from near-multiplicative accumulation of failure proba- bilities without requiring interaction structure. This parallels neural scaling laws (Kaplan et al., 2020; Hoffmann et al., 2022), which established that sim- ple parametric models (power laws in compute and data) predict performance with practical ac- curacy. Favero et al. (2025) provide theoretical sup- port for hierarchical compositional learning: diffu- sion models learn grammar rules level-by-level, with sample complexityP ℓ ∝ m ℓ+1 for level- ℓrules—higher-level (more global) rules require polynomially more data. This predicts that con- straints requiring deeper compositional processing should be more fragile, consistent with our find- ing that structural constraints degrade2.0×faster than lexical constraints under compositional load (Section 4). Our floor modelP (k) = a· e −βk + c serves an analogous role for constraint composition: three parameters, fitted onk=1−8, predict held-out k=9−12within 0.2p—comparable predictive pre- cision from a comparably simple functional form. The “emergent abilities” literature (Wei et al., 2022) documents sharp capability transitions as a func- tion of model scale; we find analogous transitions as a function of compositional load. Cross-modal compositional decay.Earlier work on vision-language compositionality (Thrush et al., 2022; Hsieh et al., 2023) establishes that VLMs 15 struggle with compositional attribute binding even atk=2; Huang et al. (2024) show that these failures persist under controlled evaluation designs. The decay pattern we observe in text is consistent with cross-modal findings in generation tasks. Concept- Mix (Wu et al., 2024) reports that text-to-image models drop from 83% atk=1concepts to 8% atk=7—implyingr ≈ 0.65per added concept, steeper than CSE’s aggregater=0.922but follow- ing the same multiplicative functional form. Con- ceptMix++ (Gan et al., 2025) shows that prompt optimization can recover up to 20% of lost com- positional capability, suggesting the limitation is partially in prompt understanding rather than solely in generation. T2I-CompBench++ (Huang et al., 2023) documents degradation across attribute bind- ing, spatial relationships, and generative numer- acy. T2V-CompBench (Sun et al., 2024b) shows temporal composition failures in video generation. GenAI-Bench (Li et al., 2024) evaluates compo- sitional text-to-visual generation, reporting degra- dation with compositional complexity in image, video, and 3D generation. These are all constrained generation tasks, and the consistency of the decay pattern across text-to-text, text-to-image, and text- to-video generation suggests the transition may be a general property of compositional generation rather than a modality-specific limitation. Impossi- bleBench (Zhong et al., 2025) tests whether models detect infeasible constraint combinations in coding tasks; CSE includes deliberate impossible probes and finds zero hallucinated compliance—models either correctly refuse or fail on the constraint text itself. C Per-Constraint mCSR Heatmap Figure 5 shows per-constraint mCSR for all 36 constraints across 15 models. D Constraint Profiles Figure 6 visualizes three properties of each con- straint side by side: isolated difficulty (k=1 mCSR), compositional vulnerability (degradation slope), and the comprehension-maintenance gap. E Complete Phase Transition Table Table 4 reports per-model mCSR at eachkfor all 15 models, sorted byk=1performance. GPT-5.5 leads at everykvalue; the per-model decay factors r(Section 4) compress each trajectory into a single number. F Decay Model Predictions and Cross-Validation Aggregate decay model. The per-constraint ag- gregate decay is well-described by a pure mul- tiplicative model:rate(k) = 72.0% × 0.922 k−1 (held-out MAE= 0.2p onk=9−12). A three- parameter floor model (P (k) = a· e −βk + c, all- data fit:a=0.782,β=0.082,c=0.0%) does not improve on this aggregate fit (MAE= 0.2p), because averaging across 15 models with diverse decay profiles (r = 0.72−0.98) smooths the per- model floors into a continuous decline. Cross-validation.The floor parametercis unsta- ble under cross-validation: it collapses to 0.0% in 11 of 12 LOO folds and inflates to 9.4% whenk=1 is held out, indicating that 12 data points do not robustly constrain a three-parameter model at the aggregate level. Under multiple train/test splits, the floor model performs comparably to, but does not outperform, the multiplicative baseline. The floor is per-model, not aggregate. The aggregate curve masks per-model floors because between-model variance in decay rate (r = 0.72−0.98 ) dominates the signal. Atk=12, the multiplicative model systematically underpredicts 10 of 15 models (mean error:−5.1p), indicat- ing that these models plateau above the multi- plicative prediction. Even the weakest models (DeepSeek V4 Pro, Kimi K2.6) sustain∼11% per-constraint rates atk=12despite multiplica- tive predictions of1−3%—the compositionally im- mune constraints keep them off zero. Two mod- els (Claude 4.6 Opus, Claude 4.7 Opus) are over- predicted, decaying faster than the multiplicative model at highk. The floor is a per-model phe- nomenon, visible when models are analyzed indi- vidually but masked in the cross-model aggregate. Independent floor derivation.Compositionally immune constraints are identified by two crite- ria: degradation slope>−0.02(nearly flat across k) andk≥8pass rate> 5%(non-trivially con- tributing to the floor). Four constraints meet both criteria: L5 (forbidden word, 87.4% atk≥8), L1 (lipogram, 45.0%), M3 (word count divisibil- ity, 18.3%), and M2 (self-counting, 7.6%). S4 meets the slope criterion but has a trivially low rate (4.5% atk≥8). W4 (no repeated bigrams) narrowly misses the slope threshold (−0.021) but sustains 43.7% atk≥8(86% retention), qualifying as immune under the retention criterion used in 16 Table 4: Per-model mCSR (%) by constraint countk, sorted byk=1. Bold marks the best model at eachk. The rightmost columnris the per-model decay factor fromrate(k) = a· r k−1 , fitted onk=1−8: the fraction of performance retained per additional constraint (r=0.95means 5% loss per constraint). All 15 models start between 48–98% atk=1and converge toward a model-dependent floor atk≥8.rranges from0.721(DeepSeek, loses 28% per constraint) to0.977(Claude 4.7, loses 2%). Row shading indicates decay archetype: unshaded is slow decay (r>0.93, 10 models),medium (0.80≤r≤0.93),fast (r<0.80). Modelk=123456789101112r GPT-5.598.496.092.990.590.485.883.880.273.468.265.153.0.973 Gemini 3.1 Pro90.582.571.759.651.045.938.730.226.621.821.517.9.863 DeepSeek V4 Pro80.871.245.928.018.113.714.412.111.912.513.011.6.721 Claude 4.6 Opus80.380.277.173.370.165.060.050.245.737.332.623.5.944 Claude 4.7 Opus78.983.384.883.580.278.073.066.354.044.026.537.2.977 Flash-Lite78.176.268.964.661.359.153.653.850.647.947.542.4.943 GPT-5.4 Pro77.672.266.355.549.740.126.324.517.315.415.214.4.859 GPT-5.268.465.361.851.247.236.126.623.318.716.215.115.3.869 Llama 4 Maverick65.161.955.551.147.044.844.342.740.139.237.936.3.935 Claude 4.5 Sonnet64.368.862.859.356.253.550.845.942.639.936.031.7.951 Llama 3.1 405B62.461.554.652.349.147.346.443.041.941.139.437.3.947 Qwen 3 235B Inst.56.861.354.950.048.947.645.444.040.040.138.235.8.956 Llama 3.1 70B56.256.552.751.046.344.844.041.240.940.038.636.3.953 Grok 4.154.958.350.348.542.744.340.940.338.437.638.834.3.948 Kimi K2.648.429.820.316.912.313.113.314.712.012.513.211.8.769 Section 4. The independently predicted floor from these immune constraints isc=34.5%(meank≥8 rate of the four immune constraints, weighted by their representation)—far above the fittedc=0.0%. The gap confirms that the immune constraints’ per- constraint rates do not translate directly to an ag- gregate floor: their contribution is diluted by the 32 non-immune constraints whose rates converge toward zero, and by the between-model variance that smooths the aggregate curve. Floor estimate comparison. Methodc All-data fit (k=1−12)0.0% LOO mean± std0.8%± 2.7% k=1−8 extrapolation0.0% Independent (immune constraints)34.5% The fitted and LOO estimates converge near zero; the independent estimate overshoots because it counts immune constraint rates without account- ing for their dilution in the 36-constraint aggregate. The floor is real per-constraint (L5 at 87%, L1 at 45%, W4 at 44%, M3 at 18% atk≥8) and per- model (10/15 underpredicted atk=12), but is not a feature of the aggregate decay curve with 15 mod- els. G Failure Mode Details This appendix provides per-model breakdowns sup- porting the failure mode analysis in Section 4. Classifier design. Accurately separating meta- preamble from genuine failures required iterative refinement. An initial narrow classifier (keying on explicit preamble markers) identifies only 8 meta- preamble cases. Manual inspection reveals contam- ination: 4 of 5 top-ranked “genuine” failures are constraint self-narration (“Constraint L1 requires no letter ‘k’ ”). We expand the classifier with a constraint-echo regex matching patterns such as “no letter ‘X’ ”, “avoiding the letter”, and “Con- straint [L1]” within 60 characters of the violation, reclassifying matches in the first 150 characters as meta-preamble. This moves 106 cases from genuine to meta-preamble (8→114), primarily from Claude models (+50, +22, +23 for the three variants). The 150-character threshold prevents re- classifying violations deep in the response where constraint references may be legitimate. H Full Constraint Specifications Table 7 lists all 36 constraints with exact instruc- tion text and verifier specifications. Constraints marked with⋆were added through the design pipeline described in Section K. One candidate lex- ical constraint (anagram embedding) was rejected during this pipeline because its verifier requires fac- tual knowledge about which letter rearrangements are valid English words, violating the structural- verification-only design principle. 17 Table 5: L1 (lipogram) failure categorization by model (n=5,267total failures across 15 models). “Genuine” = model attempts the constraint and violates it in content; “Refusal” = model identifies infeasibility and the forbid- den letter appears in the explanation text; “Meta” = con- straint self-narration (restating the rule using the forbid- den letter); “Case” = case-folding artifact. The refusal rate varies widely: GPT-5.2 and GPT-5.4 refuse∼90% of failed probes, while open-weight models (Llama, Grok, Maverick) refuse <1%. ModelGenuine Meta Refusal Case Total Claude 4.5 Sonnet2355210288 Claude 4.6 Opus1563210189 Claude 4.7 Opus7246280146 DeepSeek V4 Pro56630329628 Gemini 3.1 Flash-Lite7610077 Gemini 3.1 Pro1443561204 GPT-5.25004430493 GPT-5.4 Pro3403970431 GPT-5.58050058 Grok 4.1427000427 Kimi K2.639446016456 Llama 3.1 405B511000511 Llama 3.1 70B485000485 Llama 4 Maverick409000409 Qwen 3 235B Inst.4550100465 Total4,02221098946 5,267 I Probe Generation and Compatibility Verification Whenkconstraints are sampled into a single probe, certain parameter combinations create provably un- satisfiable requirements. To prevent structurally impossible probes from entering the benchmark, the probe composer applies a multi-layered com- patibility checker (check_compatibility()) that rejects constraint combinations before probe gen- eration. We describe each category of structural conflict and the corresponding check. Hard incompatibilities. Nine constraint pairs are unconditionally incompatible regardless of pa- rameters and are blocked as a static reject list: F1+L1 (JSON keys contain the forbidden letter), M2+W1 (the self-counting phrase “This text con- tains exactlyNwords” inherently repeats com- mon words), O1+O3 (monotonic and alternating sentence lengths contradict), N1+N2 and N3+N2 (embedding numerical digits vs. forbidding all digits), F3+R2 (bullet list explicitly forbids num- bered lists, transitive ordering requires them), and N1+R2, N3+R2, N2+R2 (R2’s numbered list for- mat “1. first, 2. second, . . . ” injects digit sequences into the response text; numerical constraint veri- Table 6: Model failure strategy profiles for genuine L1 failures only (n=4,022). Median = normalized position of first violation (0 = response start, 1 = end).Pink = immediate strategy (median< 0.05): violations oc- cur at response onset.Blue= gradual strategy (me- dian≥0.10): violations distributed across the response. GPT-5.5 is excluded (8 genuine failures, insufficient for profiling). ModelMediann DeepSeek V4 Pro0.010566 Claude 4.7 Opus0.01272 Claude 4.6 Opus0.028156 Kimi K2.60.029394 Claude 4.5 Sonnet0.048235 Llama 4 Maverick0.105409 Llama 3.1 70B0.115485 Llama 3.1 405B0.134511 Qwen 3 235B0.159455 Grok 4.10.202427 Gemini 3.1 Pro0.232144 Gemini 3.1 Flash-Lite0.24276 GPT-5.20.37750 GPT-5.4 Pro0.43934 fiers that scan for digits viaextract_numbers() count these list markers as integers, corrupting N1’s count/sum, N3’s distinct count, and violating N2’s no-digits rule). Sentencecountconsistency. Threecon- straints independently impose an exact sentence count:S2 (explicit parameter), L4 (acrostic word length, e.g., DREAM→5 sentences), and M1 (hidden message word length, e.g., SPARK→5 sentences). A fourth constraint, S3 (paragraph structure),imposes a mini- mum sentence count:target_paragraphs × min_sentences_per_para (default:×2).If any two of S2, L4, M1 co-occur with different counts, or if S3’s minimum exceeds the count required by S2, L4, or M1, the probe is rejected. For example, S3 with 3 paragraphs requires≥ 6 sentences, but all M1 hidden words (BRAVE, LIGHT, DREAM, SPARK, STORM) have 5 letters, making S3+M1 impossible whenever the paragraph count exceeds 2. Word budget feasibility. When S1 (exact word count), W3 (minimum words per sentence), and a sentence-count constraint (S2, L4, or M1) co-occur, the probe is rejected if the product of sentence count and minimum words per sentence exceeds the word budget. For example, S1= 50words, S2= 6sentences, W3= 10minimum words 18 Table 7: Complete constraint taxonomy (36 constraints, 8 dimensions). The INSTRUCTION column shows the text injected into probe prompts; parameters in braces are instantiated from fixed calibrated ranges. The VERIFIER column summarizes the deterministic check applied to each response. Constraints marked ⋆ are new in CSE. IDNameInstructionVerifier STRUCTURAL (S1–S6): constraints on the macroscopic geometry of the output S1Exact word countYour response must contain exactly N words. A ‘word’ is any whitespace-separated token (e.g., ‘state-of-the-art’ counts as one word, ‘don’t’ counts as one word). count_words = N S2Exact sentence countYour response must contain exactly N sentences. count_sents = N S3Paragraph structure Your response must contain exactly N paragraphs, each with≥M sentences. paras = N, each≥ M sents S4Exact character countYour response must contain exactly N characters (incl. spaces and punctuation). len(text) = N S5Exact line count Your response must contain exactly N non-empty lines. non-empty lines = N S6⋆Palindromic sentence structure Your response must have N sentences. The word counts must form a palindrome (sent. 1 matches sent. N, sent. 2 matches sent. N−1, etc.). A ‘word’ is any whitespace- separated token. c i = c n−1−i ; middle free if n odd LEXICAL (L1–L6): constraints on which specific characters or words appear in the output L1Forbidden letterYour response must not con- tain the letter ‘c’ anywhere. No exceptions. letter c /∈ text L2Mandatory words Your response must include all of the following words: list. ∀w ∈ list: w present L3Sentence initial letter Every sentence must begin with a word starting with ‘c’. ∀sent: first word starts with c L4Initial acrostic N sentences; first letters spell “WORD”. sent. initials spell WORD L5Forbidden word Must not contain the word “word” (case-insensitive). word /∈ text (case-insens.) L6Vowel–consonant ratioVowel/consonant ratio must be between lo and hi. V/C ratio∈ [lo,hi]; non- alpha ignored Continued on next page 19 Table 7: Complete constraint taxonomy (continued). IDNameInstructionVerifier WORD-LEVEL (W1–W5): constraints on vocabulary properties enforced per-word or per-bigram W1Unique wordsEvery word must be unique (case-insensitive). all words unique (case- insens.) W2Word length rangeEvery word must be N– M characters long. ∀w: |w|∈ [N,M ] W3Minimum sentence words Every sentence must contain ≥N words. A ‘word’ is any whitespace-separated to- ken. ∀ sent: words≥ N W4⋆No repeated bigramsNo two-word sequence may appear more than once in your response. all bigrams unique (case- insens.) W5⋆Consonant cluster density Every sentence must contain ≥N words with a conso- nant cluster of three or more consecutive consonant letters (e.g., ‘str’ in ‘strong’, ‘nch’ in ‘branch’, ‘mpl’ in ‘sim- ple’). Two-letter clusters like ‘nd’ or ‘st’ do NOT count. ∀sent:≥N words match [bcdf. . . ]3, RELATIONAL (R1–R4): reasoning about dependencies between multiple discrete elements R1Scene graph outputOutput JSON with “objects” and “relations” keys repro- ducing all attributes and re- lations. parsed JSON matches all ob- jects + relations R2Transitive orderingGiven pairwise comparisons, list all items in correct order. numbered list=transitive closure R3Logic grid puzzleGiven clues about peo- ple/pets/colors,output solution as JSON. parsed JSON satisfies all clues (multi-solution) R4⋆Cross-sentence bridge The last word of each sen- tence must be the first word of the next sentence (case- insensitive). ∀i: last(s i ) = first(s i+1 ) FORMAT (F1–F4): constraints on output syntax and document-level form F1Markdown tableInclude a table with C columns and R data rows. C cols, R data rows in|for- mat F2Bullet list Exactly N items using “- ” format. exactly N - prefixed items F3Fenced code blocksExactly N fenced code blocks (“‘). exactly N“‘blocks; non- empty F4⋆Unique sentence closers Every sentence must end with a different word (case- insensitive,punctuation- stripped). all sent-final words distinct Continued on next page 20 Table 7: Complete constraint taxonomy (continued). IDNameInstructionVerifier META (M1–M3): constraints where the output must satisfy a property defined in terms of itself M1Terminal acrosticN sentences; last word of each starts with a letter spelling “WORD”. final-wordinitialsspell WORD M2Self-referential countMust contain “This text contains exactly N words” where N is a numeral (e.g., “42” rather than “forty-two”), and total word count must equal N. A ‘word’ is any whitespace-separated token. phrasepresent∧ count_words = N M3Word count divisibility Total word count must be di- visible by N. A ‘word’ is any whitespace-separated to- ken. count_words mod N = 0 NUMERICAL (N1–N4): constraints requiring arithmetic computation embedded in the output N1Embedded integer sumExactly K integers sum- ming to T. exactly K ints found, sum= T N2No digits No numerical digits (0–9). Write numbers as words. no chars 0–9 N3Distinct number countExactly N distinct num- bers (as digits). exactly N distinct ints N4⋆Embedded arithmetic Your response must contain exactly K correct equa- tions of the form “X + Y = Z” where X, Y, Z are integers. exactly KX+Y=Zequations, all correct ORDERING (O1–O4): sequential constraints on sentence arrangement O1Monotonic sentence lengthsEach sentence strictly dir in word count. A ‘word’ is any whitespace-separated to- ken. word counts strictly mono- tonic O2Alphabetical sentencesFirst word of each sentence in alphabetical order. first words in A–Z order O3Alternating lengthAlternate short (≤N) and long (≥M) sentences. A ‘word’ is any whitespace- separated token. odd sents≤N, even sents≥ M O4⋆Fibonacci-style growthYour response must contain a contiguous run of at least N sentences where, start- ing from the third sentence in the run, each sentence con- tains more words than the sum of the two sentences im- mediately before it in the run. The run can appear anywhere in your response. A ‘word’ is any whitespace-separated token. ∃window of N sents:c i > c i−1 + c i−2 21 Algorithm 1 Probe generation with compatibility- guaranteed resampling Require:PoolC, targets(k,g k ,n k ), topicsT, param ranges Θ Ensure: n k primary+ (g k − n k )reserve probes at each k 1: for each (k,g k ,n k ) do 2: P k ←∅ 3:while|P k | < g k do 4:S ← draw k-subset fromC▷ Exhaustive or random 5:θ ← sample parameters for S from Θ 6:Shuffle constraint order in S 7:if¬ CHECKCOMPAT(S,θ) then 8:continue 9:end if 10: P k ←P k ∪ PROBE(S,θ, NEXTTOPIC(T )) 11:end while 12: Mark firstn k as primary, remainder as re- serve 13: end for 14: return S k P k ∪ IMPOSSIBLEPROBES(C) per sentence requires≥ 60words but only 50 are allowed. Alternating length feasibility. O3 (alternating short/long sentences) defines a maximum word count for short sentences (short_max). If W3’s minimum words per sentence exceedsshort_max, no short sentence can satisfy both constraints si- multaneously, and the probe is rejected. Forbidden letter propagation. L1 (lipogram) forbids a single letter. Several constraints force that letter into the output: M1 requires a word starting with each letter of its hidden word (a word start- ing with ‘v’ necessarily contains ‘v’); L4 requires sentences starting with each letter of the acrostic word (same logic); L3 requires every sentence to start with a word beginning with a specific letter. If L1’s forbidden letter appears in M1’s or L4’s target word, or equals L3’s required letter, the probe is re- jected. Similarly, if L1’s forbidden letter appears in any of L2’s mandatory words, the probe is rejected. Word length range conflicts. W2 (word length range) restricts every word to[min_len, max_len] characters. Two constraints can force words out- side this range: L2 (mandatory words) may require words longer thanmax_len(e.g., “algorithm” is 9 characters, exceeding a[1, 8]range); M2 (self- counting phrase) requires the fixed phrase “This text contains exactlyNwords,” whose words “This” and “text” (4 characters each) may fall below a tight min_len. Both interactions are checked at genera- tion time. Lexical conflicts. L5 (forbidden word) and L2 (mandatory words) are checked for overlap: if the forbidden word appears in the required word list, the probe is rejected. Format exclusivity. F1 (valid JSON) requires the entire response to be a single JSON object with no text outside it. This is structurally incompatible with any constraint that requires non-JSON output formatting or whose verifier assumes prose with identifiable sentences. Specifically, F1 is blocked from co-occurring with 12 constraints in three cat- egories: (i) output format conflicts: F2 (mark- down table), F3 (bullet list), and R2 (numbered list), which demand non-JSON structure; (i) prose- dependent verifiers: S2 (sentence count), S3 (para- graph structure), L3 (sentence-initial letter), L4 (acrostic), M1 (terminal acrostic), O1 (monotonic sentence length), O2 (alphabetical sentences), O3 (alternating sentence length), and W3 (minimum words per sentence), all of which split the raw text into sentences—a JSON object contains no sentence boundaries in the prose sense, so these verifiers find zero sentences and fail deterministi- cally. F1 remains compatible with constraints that operate on raw text without assuming prose struc- ture, including word and character counts (S1, S4, S5), lexical constraints (L2, L5, L6), numerical constraints (N1–N3), word-level properties (W1, W2), meta-constraints (M2, M3), and other JSON- producing constraints (R1, R3), whose required keys can be merged into a single JSON object. Additionally, F3 (bullet list) explicitly states “Do not use numbered lists or other bullet formats,” which directly contradicts R2 (transitive ordering), whose instruction requires “Output them as a num- bered list (1. first, 2. second, etc.).” The F3+R2 pair is blocked unconditionally. Word count divisibility. S1 (exact word count N) and M3 (word count divisible byD) are checked for arithmetic compatibility: the probe is rejected if N mod D ̸= 0. Integer count consistency. N1 (embed exactly Kintegers summing toT) and N3 (exactlyDdis- tinct integers) are checked: the probe is rejected if 22 K < D, since the total number of integer occur- rences cannot be less than the number of distinct values required. Validation.In total, the compatibility checker en- forces 9 hard pair blocks, 12 F1 format-exclusivity blocks, and 14 parameter-dependent checks cover- ing sentence counts, word budgets, letter propaga- tion, word length ranges, word count divisibility, integer count consistency, and lexical conflicts. All checks are deterministic and run inO(k 2 )time dur- ing probe composition. The rejection rate increases withk: from∼32%atk=4to∼98%atk=12. High-kprobes are drawn from the restricted subset of compatible combinations; we analyze and con- trol for the resulting composition bias in Section 4. Probe sampling strategy.At lowk, the space of possible constraint combinations is small enough to enumerate exhaustively: the probe generator materializes all |C| k combinations, shuffles them uniformly, and iterates through them. For the 36- constraint pool used in CSE, this is feasible through k=5( 36 5 =376,992combinations,∼120MB). Atk≥6, exhaustive materialization exceeds a 500 MB memory cap ( 36 6 =1,947,792combina- tions,∼0.7GB; 36 10 =254,186,856,∼140GB), so the generator switches to uniform random sam- pling: combinations are drawn uniformly at ran- dom with a reuse cap of 10 per combination. Both paths feed into the same acceptance pipeline: draw a candidate combination, check compatibility, generate the probe if compatible, reject and redraw if not. The only difference is coverage uniformity: exhaustive shuffle guarantees each combination is visited at most once before repeating, while random sampling may revisit com- binations (though the reuse cap bounds this). For the paper’s analyses, this distinction is immaterial: atk=6we draw∼500probes from2.76M pos- sible combinations (0.018%sample), making the two strategies statistically indistinguishable. The compatibility checker serves as the acceptance gate in both cases—a probe is valid or it is not, regard- less of how the candidate combination was drawn. J Model Notes and API Success Rates Table 8 reports per-model API success rates. All models were evaluated on 4,527 probes (4,470 pri- mary+57 impossible) at temperature=0with an output token budget of 4,096 tokens (16,384 for Claude 4.7 Opus, which requires extended reason- ing). GPT-5.5 completed 4,526 of 4,527 probes (1 empty response excluded). Claude 4.7 Opus had 340 content-safety refusals from Anthropic’s integrity filter and 57 transient API errors; all 397 are excluded from scoring (treated identically to missing probes, not injected as failures), as they re- flect infrastructure-level safety filtering rather than intrinsic compositional capacity. Claude 4.5 Son- net (2 refusals) and Claude 4.6 Opus (1 refusal) are similarly excluded. All remaining models achieved ≥99.9% API success. Table 8: API success rates by model. “Refusals” are integrity-filter rejections excluded from scoring (the model never saw the prompt). “Errors” are transient API failures (rate limits, timeouts, empty responses), also excluded. Both are treated as missing probes—not as failures—to measure intrinsic compositional capacity independent of infrastructure behavior. ModelSuccessRefusalsErrorsCoverage Claude 4.5 Sonnet4,5252099.96% Claude 4.6 Opus4,5261099.98% Claude 4.7 Opus4,1303405791.2% DeepSeek V4 Pro4,5210699.9% Gemini 3.1 Flash-Lite4,5210699.9% Gemini 3.1 Pro4,52700100.0% GPT-5.24,52700100.0% GPT-5.4 Pro4,52700100.0% GPT-5.54,5260199.98% Grok 4.14,52700100.0% Kimi K2.64,52700100.0% Llama 3.1 70B4,52700100.0% Llama 3.1 405B4,52700100.0% Llama 4 Maverick4,52700100.0% Qwen 3 235B Inst.4,52700100.0% Compositionality penalty anomalies.Two mod- els show near-zero gaps between mCSR and sCSR: DeepSeek V4 Pro (22.4% marginal, 22.4% strict, 0.0p penalty) and Gemini 3.1 Pro (42.1% marginal, 39.4% strict, 2.7p penalty). Both are tag-compliance artifacts, not genuine composi- tional resilience. DeepSeek’s 72.9% answer-tag compliance means that∼27%of responses fail tag extraction entirely—all constraints are scored on raw text including chain-of-thought, produc- ing correlated all-fail outcomes that affect mCSR and sCSR equally. When extraction succeeds, DeepSeek attempts constraints genuinely, but the binary extraction-success/extraction-failure mode dominates the statistics and collapses the mCSR– sCSR gap. Gemini Pro (46.9% tag compliance) shows the inverse of the Llama pattern: Llama models have 100% tag compliance, so every probe receives clean evaluation and constraint failures 23 are distributed across different constraints in differ- ent probes (high mCSR, low sCSR). Gemini Pro’s low tag compliance suppresses its mCSR (many individual constraint checks fail because the ver- ifier scores reasoning text), but the probes where it produces clean answers tend to pass all con- straints simultaneously, yielding relatively high sCSR. This connects to the co-failure analysis (Sec- tion 4): tag-extraction failure acts as a shared out- put feature that induces correlated failures across all constraints within a probe, identical in mech- anism to the sentence-count coupling identified among constraint pairs. Bimodal constraint profiles.Grok 4.1 shows an unusually flat trajectory (r=0.948) despite ranking 14th atk=1(54.9%). Its per-constraint profile is bimodal: 7 constraints are near-zero even atk=1 (W5: 0.1%, S4: 0.0%, M1: 0.2%), while 7 are near- ceiling (L5: 98.3%, R1: 98.5%, F3: 90.2%). With little in between to erode, the trajectory is dom- inated by immune constraints maintaining their rates, and the∼34%floor atk=12is almost en- tirely the immune cluster. K Constraint Design Methodology Designing constraints for a compositional benchmark is harder than for a single-constraint benchmark: every candidate must be checked against all existing constraints for structural incompatibilities—bothunconditionaland parameter-dependent—and constraints that lock down multiple output dimensions simultaneously create disproportionate composition bias at highk. We formalize the vetting process as a four-stage pipeline. Stage 1: Deterministic verifiability. The con- straint is rejected if its pass/fail verdict cannot be computed as a deterministic function of the response text and constraint parameters, without LLM judgment. This is the foundational design choice: it excludes semantic and pragmatic con- straints but makes CSE’s measurements invariant to the same compositional degradation it studies (Section 1). All 36 constraints in the final pool pass this stage; rejected candidates included “maintain formal tone throughout” (requires stylistic judg- ment), “each paragraph must introduce a novel ar- gument” (requires semantic novelty detection), and “the response must be factually accurate” (requires knowledge verification). Stage 2: Composability analysis. Each surviv- ing candidate is assessed on four axes. Hard con- flicts: how many existing constraints are uncon- ditionally incompatible regardless of parameters? Parameter-dependent conflicts: how many are in- compatible for some parameter values but not oth- ers? Output dimensions constrained: how many aspects of the output (sentence count, word count, ordering, format, vocabulary) does the constraint lock down? High-k survival: what fraction of ran- domk=12constraint sets including this constraint would pass the compatibility checker? Constraints that constrain multiple output di- mensions simultaneously inherit the incompatibil- ities of each dimension. For example, a candi- date Fibonacci sentence length constraint (“the word count of consecutive sentences must follow the Fibonacci sequence starting from 3, 4”) locks down sentence count, per-sentence word count, and sentence ordering—essentially fusing S2+S1+O1 into a single constraint. It inherits 2 hard conflicts (O3 alternating length) and 6 parameter-dependent conflicts (S2, S1, W3, L4, M1, S3), giving it POOR composability. In contrast, R4 (cross-sentence word bridge: “the last word of each sentence must be the first word of the next”) constrains a single novel dimension (inter-sentence word dependency) with 0 hard conflicts and 2 parameter-dependent ones (L4, L3), giving it GOOD composability. R4 was accepted; the Fibonacci candidate was softened into O4 (relaxed growth: “each sentence must con- tain more words than the combined word count of the previous two”), which reduces the hard conflicts from 2 to 1 and the parameter-dependent conflicts from 6 to 3. Stage 3: Difficulty calibration.Each constraint is piloted atk=1on 3 models spanning the per- formance range. Parameters are adjusted to target 20–80% mCSR atk=1, ensuring the constraint is neither trivially satisfiable (uninformative at all k) nor near-impossible (unable to contribute to the decay signal). Constraints that floor (< 5%) or ceil- ing (> 95%) after parameter tuning are rejected. The fixed MEDIUM difficulty level used across all k values is calibrated at this stage. Case study: W6 (word length alternation) — rejected at Stage 3. W6 required words to al- ternate between short (≤Ncharacters) and long (≥Mcharacters). Three calibration attempts failed: strict alternation with a 3-character gap between bands (0% mCSR), strict alternation with no gap 24 (0% mCSR), and a 75% tolerance threshold (0% mCSR, 54% score). The root cause is distribu- tional: English word lengths are∼2:1 skewed toward short words—2–5 character words consti- tute∼65% of the lexicon—and the skew is even more pronounced in generated text, where high- frequency function words (the, and, for, is) dom- inate. Strict alternation requires roughly equal representation in alternating positions, which is structurally infeasible against this distribution. At 0% mCSR, W6 would contribute no decay signal and would poison co-occurring constraints in the φ analysis with guaranteed failures. Stage 4: Pool entry. The constraint enters the 36-type pool with its calibrated parameter ranges, verified composability profile, and deterministic verifier. The full pool spans 8 dimensions (Ta- ble 2), from surface-level lexical patterns (L1 li- pogram, L5 forbidden word) through document structure (S3 paragraph count, O1 monotonic sen- tence length) to relational reasoning (R1 scene graph, R3 logic grid). L IRT Validation A 1PL (Rasch) Item Response Theory model fit- ted on 2,952 informative probes (excluding 1,131 all-pass or all-fail probes that do not discriminate between models) converges in 234 iterations and recovers the identical model ranking (Spearman ρ = 1.000, MAE=0.0000). IRT ability estimates confirm the tier structure visible in raw sCSR: GPT- 5.5 is a massive outlier (θ = +4.3, 85.0% raw pass rate), Claude 4.7 Opus and Gemini 3.1 Pro form a second tier (θ = +1.8to+2.4), and a dense middle pack clusters aroundθ ≈ 0. At the other extreme, Kimi K2.6 (θ = −2.9, 6.3%) occupies a distinct lower tier. The perfect rank correlation confirms that raw sCSR is not distorted by item dif- ficulty confounds—IRT calibration preserves the ranking exactly, validating sCSR as a sufficient metric without adaptive testing infrastructure. The 28% of probes uninformative for IRT ranking are not wasted: they define the endpoints of the phase transition curve and power constraint-level analy- ses operating on all 369,753 checks. mCSR vs. sCSR ranking divergence. IRT val- idates the sCSR ranking, but the sCSR ranking itself diverges substantially from the mCSR rank- ing reported in Table 1. Table 9 shows the full comparison. The most striking mover is Gem- ini Pro, which ranks #11 by mCSR (42.1%) but #3 by sCSR (39.4%)—it passes fewer individual constraints but chains them together more reli- ably than models with higher per-constraint rates. Flash-Lite drops from #3 (mCSR) to #5 (sCSR); Claude 4.5 drops from #5 to #9. The mid-tier mod- els (Llama 405B, Llama 70B, Qwen, Grok) clus- ter tightly on sCSR (11–15%) despite spreading across 42–46% on mCSR—their constraint failures are distributed across different constraints in differ- ent probes, so per-constraint competence does not translate to probe-level success. This divergence is the compositionality penalty: mCSR measures whether a model can satisfy constraints individu- ally, while sCSR measures whether it can satisfy them simultaneously. Table 9: Model rankings by mCSR (per-constraint) vs. sCSR (probe-level). Rank changes≥3positions are highlighted. The divergence quantifies how much com- positional precision differs from per-constraint compe- tence. ModelmCSRRanksCSRRank GPT-5.579.8164.21 Claude 4.7 Opus67.0249.62 Flash-Lite56.6324.15 Claude 4.6 Opus55.6431.64 Claude 4.5 Sonnet49.4517.39 Llama 405B46.4612.412 Qwen 235B45.7712.611 Llama Maverick45.4815.010 Llama 70B44.6911.613 Grok 4.142.71011.314 Gemini Pro42.11139.43 GPT-5.4 Pro35.61223.26 GPT-5.234.01318.88 DeepSeek V4 Pro22.41422.47 Kimi K2.615.5157.215 Geometric mean ranking. A natural follow-up: what if we require models to rank high on both per- constraint and probe-level metrics? The geomet- ric mean √ mCSR× sCSRpenalizes imbalance— a model must score well on both to rank highly. Table 10 shows the result. The largest movers reveal what drives the reshuf- fling. Gemini Pro jumps from mCSR rank #11 to geometric rank #4: its balanced profile (42.1/39.4, 2.7p penalty) is rewarded by the geometric mean. However, this balance is a tag compliance artifact— 47% of Gemini Pro responses fail tag extraction entirely, suppressing both metrics equally rather than reflecting genuine compositional strength. Flash-Lite drops from #3 to #5: its high per- constraint competence (56.6%) is dragged down 25 Table 10: Model rankings under three metrics: mCSR (per-constraint breadth), sCSR (probe-level precision), and their geometric mean (balanced). Rank changes ≥3positions between mCSR and geometric mean are highlighted. The top 2 models are unambiguous under any metric; the middle tier reshuffles entirely depending on whether breadth or precision is valued. ModelmCSR mR sCSR sR Geom gR GPT-5.579.8164.2171.61 Claude 4.7 Opus67.0249.6257.62 Claude 4.6 Opus55.6431.6441.93 Gemini 3.1 Pro42.11139.4340.74 Flash-Lite56.6324.1536.95 Claude 4.5 Sonnet49.4517.3929.26 GPT-5.4 Pro35.61223.2628.77 Llama 4 Maverick45.4815.0 1026.18 GPT-5.234.01318.8825.39 Qwen 3 235B45.7712.6 1124.0 10 Llama 3.1 405B46.4612.4 1224.0 11 Llama 3.1 70B44.6911.6 1322.7 12 DeepSeek V4 Pro22.41422.4722.4 13 Grok 4.142.71011.3 1422.0 14 Kimi K2.615.5157.2 1510.6 15 by poor probe-level success (24.1%). Llama 405B drops from #6 to #11: the 34.0p compositionality penalty is devastating under a metric that requires both dimensions to be high. GPT-5.4 Pro rises from #12 to #7: moderate on both metrics (35.6/23.2), with no extreme gap. The top 2 models (GPT-5.5, Claude 4.7) are un- ambiguous under any metric. The middle tier is where the ranking depends entirely on whether one values breadth (mCSR) or precision (sCSR). The geometric mean is a principled compromise, but in practice it primarily surfaces the tag compli- ance confound (Gemini Pro, DeepSeek) rather than adding independent insight—models whose tag ex- traction suppresses both metrics equally appear “balanced” without being compositionally strong. Caveats.M =15models is below classical IRT recommendations (N ≥ 200for stable 2PL esti- mation). Recent work on adaptive IRT for LLM evaluation (Balkır et al., 2026; Li et al., 2025) shows that continuous scores and adaptive item selection can improve ranking confidence with fewer items, but requires more examinees than CSE’s 15-model panel.We also tried a 2PL model with L2-regularized discrimination param- eters (λ=0.5, centered atα=1.0). It does not converge despite 333 iterations and 2M func- tion evaluations, produces pathological parame- ter scales (θspanning[−15.9, +11.1],βspan- ning[−31.9, +25.2]), and degrades the ranking (ρ = 0.986). The regularization successfully con- trolledα(mean=0.67, std=0.54, max=1.70—no longer hitting the bound), but the optimizer com- pensated by inflatingθandβ, a classic sign of an underdetermined model withM =15examinees. The 2PL’s log-likelihood improvement over the 1PL is expected from doubling the parameter count and does not indicate better model identification. We use IRT as a validation check (which it passes: perfect rank preservation with a converged opti- mizer) rather than as a primary analysis. MCo-Failure Analysis: Additional Detail Within- vs. across-dimension. Within-dimension co-failure (mean|φ| = 0.087) exceeds across- dimension (0.067), but this difference does not reach significance (Mann-Whitneyp = 0.227) and is driven by the numerical–numerical ( ̄φ=0.275) and format–format ( ̄φ=0.241) clusters. Structural– structural ( ̄φ = 0.039), lexical–lexical ( ̄φ = 0.047 ), and most other within-dimension pairs are at noise level. Constraints within the same cog- nitive dimension do not interfere with each other more than constraints across dimensions, outside the shared structured-output dependency. No shortcut through constraint selection. The co-failure analysis contains only 1 synergistic pair (φ < −0.05): O4–R2 atφ=−0.055. If “compat- ible” constraint pairs existed—combinations that are easier together than independently—they would appear as negativeφvalues. They essentially do not. Co-occurrence coverage acrossk. Eachφcoef- ficient requires both constraints to appear together in the same probe. At constraint countk, the prob- ability that two specific constraints co-occur equals 34 k−2 / 36 k = k(k−1)/(36× 35), which is0.16% atk=2and0.95%atk=4. Consequently, theφ analysis is best powered atk≥4, where the ex- pected co-occurrence count per pair exceeds 3 for probe sets of size 200. Atk=2−3, most pairs have zero or one co-occurrence—a structural prop- erty of any design that drawsk-subsets from a 36- type pool, not a feature of sample size that can be overcome by generating more probes at feasible scale. Our independence estimates are therefore computed atk≥4and aggregated acrossklevels. This scope restriction is conservative: lowerkim- poses less compositional pressure and fewer com- peting demands on the model’s generation, so if constraints do not interfere atk≥4they are unlikely 26 to do so at k=2−3. Output-feature cluster analysis. Constraints can be grouped by the output feature they de- pend on rather than by linguistic dimension: sen- tence_structure (S2, S3, S5, S6, L3, L4, M1, O1–O4, R4, F4, W3), word_inventory (W1, W2, W4, L1, L2, L5), number_content (N1–N4), doc- ument_format (F1–F3), relational_json (R1, R3), global_statistics (S1, S4, M2, M3, L6, W5), and ordered_list (R2). Within-cluster constraint pairs show mean|φ| = 0.113, while across-cluster pairs show|φ| = 0.058(Mann-Whitneyp < 10 −6 ). This confirms that the elevatedφvalues in Sec- tion 4 reflect shared structural dependencies on the same output feature—when a model produces the wrong number of sentences, every sentence- dependent constraint fails simultaneously—rather than pairwise constraint interference. Grouping constraints by linguistic dimension (structural, lex- ical, etc.) does not predict which pairs co-fail (within-dimension mean|φ| = 0.087vs across- dimension0.067,p = 0.227). Grouping by out- put feature—sentence count, number count, doc- ument format—does (p < 10 −6 ). Co-failure is mechanical: when sentence splitting breaks, ev- erything that reads sentences breaks together, re- gardless of which dimension those constraints be- long to. L4 (lexical) and S2 (structural) share a sentence-count dependency (φ=0.501); L1 (lexi- cal) and L5 (lexical) share a dimension but not an output feature (φ=−0.039). N Constraint Ordering Position Effect Zeng et al. (2025) demonstrate that constraint or- dering affects performance by up to 25%, raising the concern that CSE’s degradation hierarchy could reflect prompt position rather than processing de- mands. To eliminate this confound by design, CSE randomizes the presentation order of constraints within each probe: after constraint selection and parameter instantiation, the constraint list is uni- formly shuffled before prompt assembly (Algo- rithm 1). This breaks any correlation between con- straint type and prompt position, ensuring that the ordering regression measures position effects rather than type effects. We verify that the randomization achieved its goal by regressing per-constraint pass rate on po- sition within the prompt (1st constraint, 2nd, . . . , kth). Within each k level, the correlations are neg- ligible: mean|ρ| = 0.029acrossk=2−12, with only 5 of 11kvalues reachingp < 0.05. Cru- cially, the directions are inconsistent—positive at k=3(ρ=+0.046) andk=11(ρ=+0.043), nega- tive atk=5(ρ=−0.073) andk=10(ρ=−0.056)— indicating no systematic primacy or recency bias. The largest per-keffect (k=5,ρ = −0.073) ex- plains< 0.5%of variance. Within eachklevel, position explains< 0.1%of variance (r 2 ≈ 0.001), confirming that the degradation hierarchy reflects constraint processing demands rather than presen- tation order. O Synergy at Lowk An unexpected finding: actual sCSRs exceed independence predictions at allk=1−11(from +26.4p atk=1to+1.1p atk=11, 95% CI ex- cludes zero), transitioning to approximate inde- pendence only atk=12(+1.0p). This is the opposite of interference—models perform better than chance when juggling small numbers of con- straints, and the synergy persists deeper than in CSE-30 (which reached independence atk=5). With 36 constraints (vs. 30), there is more room for constraint co-satisfaction before the multiplica- tive regime dominates. We test whether hard con- straints force models into a more careful “compli- ance mode” that benefits all constraints, by par- titioning probes by the difficulty of their harder constraint. Easy-anchor probes show more synergy (+32.6p) than hard-anchor probes (+17.7p)— the opposite of the compliance-mode prediction. The synergy is a base-rate artifact rather than a be- havioral strategy. Does the synergy disappear at a constant rate, or does it decay in a curve? We fit both a linear model (synergy(k) = a + bk) and a quadratic model (synergy(k) = a+bk+ck 2 ) to the penalty curve. The superlinearity improvement— the fraction of the linear model’s residual error that the quadratic term eliminates—is 98.8% at the con- straint level (83.7% at the probe level): the decay is strongly concave, not linear. Synergy drops sharply fromk=1tok=4(+26p→ +14p), then tapers gradually throughk=8−12(+4p→ +1p). This concave shape is consistent with the floor model: at lowkthere is substantial synergy to lose, while at highkthe system is already near the independence floor and little synergy remains to erode. P Whyk=12 Is the Upper Bound We evaluate atk=1to12rather than extending to higher values. This upper bound is determined by 27 three converging considerations: signal exhaustion, constraint diversity erosion, and scientific question coverage. Signal exhaustion. At the per-constraint level, the aggregate decay is well-described by a multi- plicative model (held-out MAE=0.2p; Section 4). Byk=12, the aggregate mCSR is 29.2%. At the probe level, sCSR reaches<4%byk=9and 1.4% atk=12—additionalkvalues measure probe-level performance at the noise floor. Thek=1−8range characterizes the decay;k=9−12validates it. All three contributions—the decay characterization, the hierarchy, and the co-failure structure—are fully resolved within k=1−12. Constraint diversity erosion. Atk=12, each probe draws 12 of 36 constraints (33% of the pool). Askincreases, probes become increasingly homo- geneous: the fraction of compatible combinations shrinks, and surviving probes are drawn from an increasingly narrow subset. The incompatibility rejection rate increases with k, as shown in Table 11. While the combinatorial pool grows rapidly ( 36 12 ≈ 1.25B ), the fraction of compatible combinations drops to∼2%atk=12. The resampling loop (Algorithm 1) compensates by drawing additional combinations until the target count is reached—feasible at allkvalues because the absolute number of compatible combinations remains large (∼24Matk=12). The composition bias at highk—surviving probes exclude incompat- ible constraint types—is analyzed and controlled for in Section 4. Table 11: Combinatorial pool size and estimated incom- patibility rejection rate at eachkfor|C|=36. “Compati- ble” is the estimated number of constraint combinations passing the full compatibility checker (Monte Carlo es- timate, 200,000 samples perk). The resampling loop draws from this pool until the target probe count is reached. k 36 k Rejection %Compatible 458,905∼32 ∼40K 61,947,792∼61 ∼751K 830,260,340∼82 ∼5.3M 10254,186,856∼94 ∼16M 121,251,677,700∼98 ∼24M Pool size as the fundamental constraint. The k=12ceiling is ultimately determined by the con- straint pool size (|C|=36). A larger pool would per- mit higherkvalues with maintained diversity and lower rejection rates. We chose|C|=36to balance three requirements: (1) sufficient diversity across 8 processing dimensions for the degradation hierar- chy, (2) all constraints deterministically verifiable with no LLM-judge involvement, and (3) feasible pilot calibration (36 verifiers×parameter sweeps × 2 validation phases). Q Verifier Audit and Known Edge Cases We conducted an exhaustive audit of all 30 con- straint verifiers across all 55,962 reported failures (82,628 total constraint checks, 59,897 failures af- ter excluding impossible probes). The audit identi- fied 5,733 discrepancies (10.2% of failures) across eight classes, ranked below by impact. An inde- pendent code-level audit of 25,000 checks against reimplemented verifiers confirmed 99.98% agree- ment on non-discrepant checks, and an LLM-as- judge evaluation of 300 stratified samples found 100% agreement. Class 1: Meta-note contamination (3,721 cases, 64.9% of discrepancies). Models that satisfy a constraint in their content sometimes add metacom- mentary (“Note: I avoided the letter ‘j’ ”) that itself violates the constraint. The verifier scores the entire response including the note. For example, a model avoiding the letter ‘j’ writes a complete essay with zero ‘j’ in the content, then appends “Note: I wrote this without using the letter ‘j’ anywhere”—the note contains ‘j’. This disproportionately penal- izes models that are good at the constraint: GPT- 5.4 Pro has 78% of its L1 (lipogram) failures from meta-notes alone. Affected constraints: W2 (835), W1 (753), M3 (708), N2 (506), L1 (375), S5 (98), L6 (71), N3 (45), S1 (8). Fix: wrap the final re- sponse in<answer>tags and score only the tagged content. Class 2: Markdown formatting (892 cases, 15.6%). Models use markdown syntax (#,**) which the verifier reads as literal characters. A heading# Historycauses the verifier to read ‘#’ as the first character instead of ‘H’. Bold formatting**D**ecliningcauses ‘*’ to be read as the first character instead of ‘D’. For L4 (acrostic), models that highlight acrostic let- ters with bold formatting—e.g.,**S**olar... **T**echnology... **O**utput...—produce a correct acrostic that the verifier reads as*****. Affected constraints: L3 (512), L4 (317), S3 (63). Fix: instruct models to write in plain text without 28 markdown. Class 3: Code fence interaction (503 cases, 8.8%). When F4 (code blocks) co-occurs with sentence-dependent constraints, the“‘markers and code contents create false structural elements. Fence markers are counted as sentences, lines, or paragraphs. Code content (variable names, JSON keys) skews word counts, vowel ratios, and num- ber counts. For example, a model writes 5 prose sentences plus a code block; the verifier splits on periods inside the code, counting 8 “sentences.” Affected constraints: S2 (52), S3 (95), S5 (29), O2, O3 (34), O1 (20), M1 (13), M3 (92), L6 (7), W1 (36), W2 (46). Fix: strip code block contents before running sentence/structure verifiers. Class 4:Numbered list sentence splitting (379 cases, 6.6%). Models write numbered lists (“1. First item. 2. Second item.”). The period after the digit (“1.”) triggers the sentence split- ter(?<=[.!?]) +, creating false sentence bound- aries. Each list item becomes two or more “sen- tences.” For O2 (alphabetical first words), list in- dices create “sentences” starting with digits, which break alphabetical order. Affected constraints: S2 (39), O2 (∼part of 340). Fix: define sentence boundaries explicitly in the prompt; optionally ex- clude +\. from the splitter. Class 5: R3 underdetermined puzzles (234 cases, 4.1%). 106 of 189 R3 (logic grid) probes have multiple valid solutions because the generated clues do not uniquely determine the assignment. The verifier accepts only one hardcoded solution. Mod- els that produce a correct alternative are marked as failures. For example, clues fix Bob’s pet and Carol’s color, but leave Alice’s and Carol’s pets unconstrained—both Alice:cat, Carol:fish and Alice:fish, Carol:cat are valid. Fix: brute-force all valid solutions (36 permutations) and accept any match. Fix the puzzle generator to produce uniquely solvable puzzles. Class 6:R2+N2 word-number interaction (126 cases, 2.2%). R2 (transitive ordering) re- quires a numbered list (“1. Mouse, 2. Rabbit...”). When N2 (no digits) co-occurs, models write “one. Mouse, two. Rabbit...” to satisfy both con- straints. R2’s parser cannot extract word-numbered lists—it looks for digit prefixes only. The model’s ordering is correct, and it correctly avoids digits, but the verifier cannot recognize the format. Fix: add word-number parsing to R2’s list extractor. Class 7: F3/F4 format variants (124 cases, 2.2%). Models use a different but functionally equivalent format. For F3 (bullet list), 101 models used aster- isk bullets (* item) instead of the required dash bullets (- item). For F4 (code blocks), 23 models used indented code blocks (4 spaces) instead of fenced blocks (“‘). These are arguably genuine failures since the constraint explicitly specifies the format, but could also be considered format-variant compliance. Class 8: R1 relation format mismatch (92 cases, 1.6%). The probe prompt describes spatial rela- tions as “A is above B.” Models faithfully repro- duce “is above” in their JSON output. The verifier expects just “above” (without the “is” prefix). Ex- act string matching fails despite correct semantics. Fix: strip common prefixes (“is ”, “are ”) before comparison; clarify expected format in the prompt. Summary. The answer-tag mechanism (wrap- ping the final response in<answer>tags and scor- ing only tagged content) eliminates Classes 1 and 2, which together account for 4,613 discrepancies (80.5% of all identified issues). The remaining 20% require targeted verifier fixes. Ten of 30 constraints (S4, L2, L5, W3, F1, F2, M2, N1, and arguably F3, F4) have zero discrepancies—their verifiers are fully reliable. CSE LLM-judge spot-check audit.To validate verifier accuracy on the expanded CSE benchmark (36 constraints, 15 models, 223,643 failed con- straint checks), we conducted a systematic spot- check using Claude Opus 4.6 as an independent LLM judge across nine parallel audit passes— one per constraint category (R2, S1, L1, N1/N3, W2/W4, O1/O2/O3, F1/F2/F4, R3, M1/M2/S6)— sampling 10–20 near-miss failures per pass (fail- ures with continuous score≥0.80, indicating the model nearly satisfied the constraint). For each sampled failure, the judge independently parsed the model’s response text, re-evaluated the constraint, and compared its verdict against the stored verifier output; all flagged discrepancies were then manu- ally verified by the authors to confirm or dismiss the finding, yielding four cross-cutting issues ranked by impact: (1) theextract_answer()function matching the first rather than last<answer>tag in responses where models quote the prompt in- struction, affecting 7,581+ scored rows across all constraints; (2) thesplit_sentences()func- tion treating JSON objects, markdown tables, 29 and bullet lists as prose sentences, producing 33–59% false failures among near-miss order- ing violations (O1/O2/O3) and 64 false S6 ver- dicts; (3) the R3 JSON parser spanning from the firstto lastacross multi-object responses, causing 1,051 false failures (19.2% of R3 fail- ures; DeepSeek V4 Pro CSR would increase from 15% to 59% with the fix); and (4) five R2 list- parsing gaps (inline multi-item lines, parentheti- cal numbering, space-delimited formats) causing ∼27% of sampled R2 failures to be false nega- tives where the model solved the ordering correctly but the parser could not extract it—Three of four issues were fixed and rescored before final analy- sis: (1)extract_answer()now usesrfind()to match the last structural<answer>tag, skipping quoted instruction text; (2) astrip_non_prose() helper removes JSON blocks, markdown tables, and bullet lists before sentence splitting in the O1, O2, O3, S6, F4, and W4 verifiers; (3) the R3 JSON parser now uses bracket-depth tracking to extract the first complete, schema-matching JSON object rather than spanning from firstto last. The R2 parser gaps (issue 4) remain as a known limita- tion; the detailed per-constraint audit with proposed code fixes is documented in the supplementary ma- terials. R Impossible Probe Experiment Beyond measuring how performance degrades under composition, CSE includes impossible probes—constraint combinations with a proof of unsatisfiability—to study how models prioritize when compliance is structurally unachievable. Every impossible probe requires a clean logi- cal proof of unsatisfiability; mechanical verifier conflicts (e.g., code-fence parsing interference) are excluded because the model cannot reason about verifier internals. This separates impossible probes (which test constraint understanding and prioriti- zation) from merely difficult probes (which test capacity). R.1 Design The 444 impossible probes (19 types×3 topic variants×up to 15 models=55,645 constraint checks) span three categories of impossibility. Binary contradictions pair two constraints that are logically incompatible regardless of parameters: forbidden letter vs. mandatory words containing that letter (L1+L2), embedding digits vs. forbid- ding digits (N1+N2), alternating vs. monotonic sentence lengths (O1+O3), cross-sentence word bridge vs. all-unique words (R4+W1). Each has a clean proof: for example, R4 forces the last word of sentenceito equal the first word of sentencei+1, so any response with≥2sentences must repeat at least one word, violating W1. Parameter-induced contradictions use constraint pairs that are compatible for most parameter values but impossible under specific choices enforced at probe generation time: a sentence count of 3 paired with an acrostic word of length 5 (S2+L4), a for- bidden letter that appears in the required hidden- message word (L1+M1), or two constraints that independently fix sentence count to different values (S2+S6). Hierarchy and load tests probe whether sacri- fice priorities change under compositional pressure. One probe pairs forbidden letter ‘r’ with a transitive ordering puzzle whose items all contain ‘r’ (rabbit, raccoon, raven, rooster, ram, robin)—there is no partial solution, so the model must choose which constraint to abandon entirely. Another embeds the L1+L2 contradiction among 2, 4, or 6 additional compatible filler constraints, testing whether the sacrifice ordering is stable askincreases from 4 to 8. A four-way probe (forbidden letter ‘e’+manda- tory words+unique words+exact word count) tests whether the strongest sacrifice priority erodes under multi-constraint tension. R.2 Results Across 55,645 constraint checks, 28.2% of individ- ual constraints were satisfied on impossible probes. Zero probe×model pairs passed all constraints on any impossible probe—the deterministic verifiers correctly reject every impossible probe for every model. Constraint survival ranking. Table 12 reports per-constraint pass rates on impossible probes, or- dered by survival rate. Binary constraints that re- quire no sustained tracking dominate the top (L5: 92.7%, N2: 69.5%, L2: 60.6%), while precise- count constraints requiring sustained maintenance cluster at the bottom (S4: 1.1%, S6: 2.9%, M2: 3.0%, S1: 3.2%). Sacrifice rules.Three deterministic rules emerge across all 15 models: 1.Concrete inclusion>abstract avoidance. L2 (mandatory words) survives at 73–100%; 30 Table 12: Per-constraint survival rate on 444 impossible probes. CIDPassScorenCIDPassScoren L592.7100.02038O318.552.0714 N269.599.4924N317.543.01363 L661.183.51620O215.249.62632 L260.663.01827M313.852.61547 R153.353.61136N113.533.51043 R348.551.81800O112.146.01072 F246.549.51778O411.325.62077 N445.251.61252W110.772.11156 F143.648.92967S39.737.21008 W343.274.21396R49.025.91051 F341.346.0641W58.923.81927 F438.384.91501S56.728.72984 W435.091.01365M16.224.51021 L132.998.42514S13.246.61651 S231.762.7833M23.026.41766 L428.548.42161S62.911.41637 W225.094.51759S41.123.71706 R221.337.4550 L1 (lipogram) is sacrificed at 0–7%. Models universally keep the named word and accept the letter violation. 2.Prohibition>requirement. N2 (no digits) survives at 84–91%; N1 and N3 are sacrificed at 0%, N4 at 4%. Models find it easier to omit than to include. 3. Natural structure>imposed structure. O3 (alternating) survives at 56%; O1 (mono- tonic) at 7% and O4 (growth) at 0%. Alternat- ing sentence lengths approximate natural prose more closely than strict monotonic or Fibonacci growth. Hierarchy inversion under binary choice. When forbidden letter ‘r’ is paired with a transi- tive ordering puzzle whose items all contain ‘r’, the model must abandon one constraint entirely. R2 (relational, the fastest degrader under compo- sitional load) survived at 33%, while L1 (lexical, compositionally immune) was sacrificed at 7%— the opposite of the degradation hierarchy. The same inversion appears when cross-sentence bridge (R4) is paired with unique words (W1): R4 survives at 62%, W1 is sacrificed at 2%. Both cases are sugges- tive of a sunk-cost mechanism: the model commits computation to the harder constraint (solving the ordering puzzle, maintaining the bridge pattern) and preserves it over the simpler one (letter avoid- ance, word uniqueness). These results rest onN =3 probes each and require replication. Stability under compositional load. When the L1+L2 contradiction is embedded among 2–6 ad- ditional compatible constraints (k=4tok=8), the sacrifice ordering is stable: L2 survives at 82–89% and L1 is sacrificed at 0–4% regardless ofk. In a four-way probe (forbidden letter ‘e’+manda- tory words+unique words+exact word count), L2 survives at 100% and L1 at 0%—the strongest sacrifice priority is unanimous even under multi- constraint tension. Compositional load compresses sacrifice margins slightly but does not alter the or- dering. Budget-exhaustion regime. On the 389 impos- sible probes where the model must triage across many jointly unsatisfiable constraints—rather than choosing between two that directly contradict—a second sacrifice regime emerges that preserves the degradation hierarchy rather than inverting it. Bi- nary constraints that require no sustained tracking survive at the highest rates (L5: 90–100%, N2: 56– 83%, L2: 53–73%). One-shot structural constraints also survive (F1: 41–60%, R1: 50–60%): format and relational JSON output require a single plan- ning decision rather than sustained maintenance. The consistently sacrificed constraints are precisely those with the highest sustained-tracking demand (S4: 0–7%, S6: 0–6%, M2: 0–6%, S1: 2–7%), matching the degradation hierarchy from Table 2. Two regimes of sacrifice. The sacrifice order- ing depends on the choice structure. Under binary choice—where one of two constraints must go— models preserve whichever constraint required greater planning investment, inverting the degra- dation hierarchy. Under multi-constraint triage— where the model must decide what it can fit from a jointly unsatisfiable set—the sacrifice ordering preserves the degradation hierarchy: the hardest constraints are dropped first, the easiest survive. S Comprehension vs. Execution: A Case Study Figure 7 presents a side-by-side comparison of two models responding to the same probe (CSE-E-k1- 0003, constraint S6: palindromic sentence struc- ture). The probe requires exactly 7 sentences whose word counts form a palindrome—sentences 1 and 7, 2 and 6, 3 and 5 must have the same word count. Claude 4.7 Opus reasons about the constraint ex- plicitly: it drafts sentences, counts words, catches errors (“S2: 11. Need 10. Fix. . . ”), revises, and verifies. Its chain-of-thought trace shows genuine comprehension of the palindromic structure. Yet the final answer has word counts [8, 9, 12, 20, 12, 10, 9]—pairs (1,7) are 8 vs. 9, (2,6) are 9 vs. 10. Off 31 by one word on two of three pairs (score = 0.33). Llama 405B bypasses reasoning entirely. It copies sentences 1–3 as sentences 5–7 in reverse order, producing word counts [13, 14, 27, 57, 27, 14, 13]—a perfect palindrome (score = 1.0). The sentences are not merely matched in word count; they are identical, which mechanically guarantees equal counts. This is not a violation of the constraint. The specification requires palindromic word counts, not unique sentence content. Llama’s strategy exploits a specification gap: copying is the most reliable way to guarantee exact word-count matches. Pre- venting this would require an additional constraint (“all sentences must be distinct”), which would it- self interact with W4 (no repeated bigrams) and significantly alter the compositional landscape. Thiscasestudyillustratesthatthe comprehension-maintenance gap is not solely about tracking difficulty—it is also about strategy selection. Models that find mechanical shortcuts to satisfy constraints outperform models that reason about them explicitly. Claude 4.7’s failure is not one of understanding (it comprehends the palindrome structure perfectly) but of execution (it cannot maintain exact word counts across revisions). The “dumber” strategy wins precisely because it eliminates the execution bottleneck entirely. 32 Per-constraint mCSR by model structural lexical word-level relational format meta numerical ordering 75%52%5%16%6%1%1%4%1%1%35%3%2%7%2% 84%70%69%72%68%58%58%54%60%54%49%46%43%21%9% 87%53%36%48%34%43%39%50%46%38%38%34%31%16%6% 65%40%2%3%1%0%0%0%0%0%12%1%0%0%0% 88%66%39%61%25%28%37%34%26%22%43%29%30%18%6% 62%56%14%19%10%1%2%2%1%0%32%2%2%13%3% 92%76%89%74%60%29%36%43%33%41%72%40%32%13%37% 87%92%98%88%94%96%96%91%93%92%45%46%47%90%49% 81%65%65%59%51%64%46%61%67%41%40%33%32%13%6% 76%71%69%57%58%53%56%52%62%47%41%40%36%20%8% 100%89%100%94%99%94%96%98%97%98%98%98%97%33%57% 76%65%47%61%69%80%68%69%81%59%57%63%62%57%48% 83%75%36%39%20%2%6%12%2%22%43%28%21%11%32% 87%62%79%59%31%20%45%50%37%31%69%44%38%16%34% 80%69%51%69%59%51%56%42%50%44%51%69%82%16%5% 90%77%69%53%62%17%69%37%18%89%66%51%39%7%42% 64%45%43%44%14%2%1%12%1%0%13%19%22%0%0% 84%85%99%82%93%99%95%84%93%98%9%32%35%22%7% 37%55%22%65%60%57%57%35%35%47%20%16%19%18%4% 83%82%93%76%82%94%81%82%85%72%34%27%26%68%18% 70%56%47%37%36%21%25%17%14%26%33%24%31%10%1% 79%75%97%67%83%99%87%83%97%85%22%30%29%19%4% 88%79%96%69%83%96%92%79%96%91%36%38%40%22%7% 74%81%82%80%91%86%94%79%83%90%34%47%49%29%9% 72%73%71%69%74%75%87%66%65%84%45%42%39%15%5% 74%27%4%12%0%37%0%25%24%0%33%15%32%13%1% 74%56%3%14%3%1%1%5%1%1%31%1%1%7%0% 81%62%16%16%14%11%12%15%13%12%41%11%14%18%7% 90%68%54%59%50%24%17%30%11%2%39%33%15%12%2% 100%88%99%83%92%96%84%93%90%98%60%99%95%27%46% 87%60%50%53%34%21%20%29%15%14%42%41%26%15%6% 88%81%93%76%88%84%91%86%83%66%43%44%42%18%7% 73%60%49%47%33%17%7%11%17%4%37%35%33%12%2% 79%65%64%63%45%56%26%50%56%24%40%41%38%10%2% 67%60%52%56%42%33%52%26%32%41%33%33%27%12%2% 70%73%13%59%22%28%5%5%11%2%35%18%9%72%36% S1 S2 S3 S4 S5 S6 L1 L2 L3 L4 L5 L6 W1 W2 W3 W4 W5 R1 R2 R3 R4 F1 F2 F3 F4 M1 M2 M3 N1 N2 N3 N4 O1 O2 O3 O4 GPT-5.5 Claude 4.7 Opus Gemini 3.1 Flash-Lite Claude 4.6 Opus Claude 4.5 Sonnet Llama 3.1 405B Qwen 3 235B Llama 4 Maverick Llama 3.1 70B Grok 4.1 Gemini 3.1 Pro GPT-5.4 Pro GPT-5.2 DeepSeek V4 Pro Kimi K2.6 14% 54% 40% 8% 37% 15% 51% 80% 48% 50% 90% 64% 29% 47% 53% 52% 19% 68% 36% 67% 30% 64% 67% 67% 59% 20% 13% 23% 34% 83% 34% 66% 29% 44% 38% 31% Avg 100% 0% Pass rate 79%67%56%56%50%47%46%45%44%43%41%35%34%21%14% Figure 5: Per-constraint mCSR by model (36 constraints×15 models). GPT-5.5 dominates across all dimensions (79.8% overall), followed by Claude 4.7 Opus (67.0%) and Flash-Lite (56.6%). The format–relational cluster is visible as a correlated block (F1–F3, R1, R3): models that fail structured output fail relational reasoning simultaneously—output-feature coupling, not cognitive interference (Section 4). Structural and meta constraints (S1, S4, S6, M2) are uniformly hard (≤15%), while lexical constraints (L5 forbidden word: 90%, L2 mandatory words: 80%) and numerical (N2 no digits: 83%) sustain the asymptotic floor. DeepSeek V4 Pro and Kimi K2.6 show the fast-decay pattern: high variance across constraints but uniformly low rates outside the immune cluster. 33 Constraint profiles: difficulty, degradation, and comprehension gap k=1 CSR (%)SlopeGap (%) structural lexical word-level relational format meta numerical ordering S139%-0.030 +41% S2100%-0.056 +21% S3100%-0.076 +21% S419%-0.016 +30% S589%-0.070 +21% S642%-0.028 L147%-0.008 +52% ★ L298%-0.033 L393%-0.060 L499%-0.063 L598%-0.009 ★ L681%-0.024 W147%-0.035 +52% W282%-0.058 +53% W398%-0.052 +26% W451%-0.023 +42% ★ W542%-0.029 R193%-0.034 R265%-0.035 +22% R385%-0.033 R486%-0.064 +22% F194%-0.047 F299%-0.048 F391%-0.049 F499%-0.052 +33% M139%-0.029 +21% M222%-0.018 +32% M324%-0.014 +36% N149%-0.036 N299%-0.034 N352%-0.036 +23% N488%-0.037 O152%-0.033 +34% O291%-0.061 +28% O387%-0.063 +30% O464%-0.040 0%25%50%75%100% Figure 6: Constraint profiles for all 36 constraints, grouped by dimension. Left:k=1mCSR (single-constraint difficulty in isolation). Center: per-constraint degradation slope (more negative = faster collapse under composi- tional load; warm = fast, cool = slow). Right: comprehension-maintenance gap∆ i = ̄s i − mCSR i (Equation (3)): filled circles show mCSR (strict binary satisfaction), open circles show continuous score (partial compliance), and the connecting bar is∆. Constraints with∆ > 20p are labeled. A large gap indicates that models partially comply—demonstrating comprehension—but fail strict verification (e.g., W1 unique words: score 78.6%, mCSR 28.4%,∆=50p). A near-zero gap indicates all-or-nothing behavior with no partial-credit regime (e.g., R1 scene graph: score 67.9%, mCSR 67.7%,∆=0.2p). Stars mark compositionally immune constraints (retention>80%at k≥8): L1, L5, W4. 34 Comprehension vs Execution: CSE-E-k1-0003 Topic: how bridges are designed to handle stress | k=1 | [S6] Your response must contain exactly 7 sentences. The word counts of the sentences must form a palindr... ome: sentence 1 and sentence 7, sentence 2 and sentence 6, sentence 3 and sentence 5 must have the s... Claude 4.7 OpusFAIL (score=0.33) Sentences: 7/7 | Word counts: [8,9,12,20,12,10,9] | Palindrome: 1/3 pairs match Reasoning (before <answer> tags): Draft: S1 (8): Bridges are designed to handle many different stresses. S2 (10): Engineers analyze tension, compression, torsion, shear, and the weight of vehicles. S3 (12): Materials like steel and reinforced concrete provide the strength needed for safety against loads. S4 (15): Suspension cables, trusses, and arches distribute forces along carefully calculated paths so that no single point becomes overloaded during use. S5 (12): Wind, earthquakes, and temperature shifts also require flexible joints and dampers. S6 (10): Computer simulations test the structure under extreme imagined conditions before construction. S7 (8): Regular inspections then ensure long-term structural reliability. Check counts: S1: Bridges/are/designed/to/handle/many/different/stresses = 8 ✓ S2: Engineers/analyze/tension,/compression,/torsion,/shear,/and/the/weight/of/vehicles = 11. Need 10. Fix: "Engineers analyze tension, compression, shear, and forces from vehicles." = 9. Try: "Engineers analyze tension, compression, torsion, shear, and vehicle weight." = 10 ✓ S3: Materials/like/steel/and/reinforced/concrete/provide/the/strength/needed/for/safety = 12 ✓ S4: any S5: need 12. "Wind, earthquakes, and temperature shifts also require flexible joints and dampers." = Wind,/earthquakes,/and/temperature/shifts/also/require/flexible/joints/and/dampers = 11. Add one: "Wind, earthquakes, and temperature shifts also require flexible joints and strong dampers." = 12 ✓ S6: need 10. "Computer simulations test the structure under extreme imagined conditions before construction." = 11. Remove one: "Computer simulations test structures under extreme conditions before actual construction." = Computer/simulations/test/structures/under/extreme/conditions/before/actual/construction = 10 ✓ S7: need 8. "Regular inspections then ensure long-term structural reliability." = 7. "Regular inspections then ensure long-term structural reliability and safety." = 8 ✓ Answer content: #WcSentencePair 18Bridges are designed to handle many different stresses.(1,7): 8 vs 9 ✗ 29Engineers analyze tension, compression, torsion, shear, and vehicle weight. (2,6): 9 vs 10 ✗ 312Materials like steel and reinforced concrete provide the strength needed for safety. (3,5): 12 vs 12 ✓ 420Suspension cables, trusses, and arches distribute forces along carefully calculated paths so that no single point becomes overloaded during use. middle 512Wind, earthquakes, and temperature shifts also require flexible joints and strong dampers. 610Computer simulations test structures under extreme conditions before actual construction. 79Regular inspections then ensure long-term structural reliability and safety. Llama 405BFAIL (score=0.50) Sentences: 7/7 | Word counts: [13,14,27,57,27,14,13] | Palindrome: 3/3 pairs match | COPIE (No reasoning outside <answer> tags) Answer content: #WcSentencePair 113Bridges are designed to handle various types of stress, including tension and compression. (1,7): 13 vs 13 ✓ 214Engineers use different materials and techniques to distribute the weight evenly across the bridge. (2,6): 14 vs 14 ✓ 327The structure is typically composed of multiple layers, with each layer serving a specific purpose, such as providing support or stability, and is usually around twenty words. (3,5): 27 vs 27 ✓ 457The main components of a bridge, including the deck, piers, and abutments, work together to resist external forces like wind, earthquakes, and the weight of vehicles, while also withstanding the internal forces that arise from the interactions between these components, and the way these forces change over time as the bridge is used and environmental conditions change. middle 527The structure is typically composed of multiple layers, with each layer serving a specific purpose, such as providing support or stability, and is usually around twenty words. 614Engineers use different materials and techniques to distribute the weight evenly across the bridge. 713Bridges are designed to handle various types of stress, including tension and compression. Figure 7: Comprehension vs. execution on probe CSE-E-k1-0003 (S6: palindromic sentence word counts,k=1). Left: Claude 4.7 Opus drafts, counts, and revises—demonstrating full comprehension of the palindrome structure— but miscounts by one word on 2/3 pairs (score 0.33). Right: Llama 405B copies sentences 1–3 as 5–7 reversed, mechanically guaranteeing a perfect palindrome (score 1.0) without explicit reasoning. The constraint requires palindromic word counts, not unique content; Llama’s copy strategy is a legitimate exploitation of this specification gap. Models that find mechanical shortcuts to satisfy constraints outperform models that reason about them explicitly—the comprehension-maintenance gap is about strategy selection, not just tracking difficulty. 35

Instant research discovery