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

• URL: http://arxiv.org/abs/2608.12426v1
• Date: Wed, 12 Aug 2026 10:57:06 GMT
• Title: Large Language Models Can Follow Instructions, But Not Many at Once: Phase Transitions in Compositional Constraint Satisfaction
• Abstract summary: Large language models are increasingly deployed in settings that require simultaneous adherence to multiple explicit constraints.<n>Individual constraints are handled proficiently, but the compositional regime remains poorly characterized.<n>We introduce Constraint Saturation Evaluation (CSE), a benchmark that systematically varies the number of simultaneous constraints.
• Score: 2.668746022268522
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Constraint-Guided Enterprise Data Mapping with Large Language Models [0.25453602861405583]
  We propose a neuro-symbolic method with three stages: (i) schema-grounded admissibility constraints with metadata mc = tau_c, delta_c>, (ii) constraint-restricted candidate generation with cascade relaxation to guarantee a nonempty feasible set under noise, and (iii) neural ranking with bounded disambiguation restricted to that feasible set.<n> Methodologically, constraints operate as hypothesis-space operators rather than post-hoc validators, enabling controlled degradation under relaxation and auditable, human-guidable decisions.
  arXiv  Detail & Related papers  (2026-08-25T08:23:45Z)
• Bridging Auxiliary Constraints to Resolve Instruction Following in Large Reasoning Models [52.87406450655783]
  Large Reasoning Models (LRMs) have demonstrated impressive capabilities in many tasks, yet they struggle with reliably following multiple instructions.<n>We formalize this challenge as the Constraint Adherence Problem (CAP)<n>This paper introduces a novel framework that addresses CAP by representing instructions as a structured knowledge graph of constraints.
  arXiv  Detail & Related papers  (2026-06-02T13:23:28Z)
• Models Recall What They Violate: Constraint Adherence in Multi-Turn LLM Ideation [0.0]
  We introduce DriftBench, a benchmark for evaluating constraint adherence in scientific ideation.<n>We find that iterative pressure reliably increases structural complexity and often reduces adherence to original constraints.<n>We release all briefs, prompts, rubrics, transcripts, and scores as an open benchmark.
  arXiv  Detail & Related papers  (2026-04-30T15:46:33Z)
• Compact Constraint Encoding for LLM Code Generation: An Empirical Study of Token Economics and Constraint Compliance [0.0]
  We investigate whether compact, structured constraint headers can reduce prompt token consumption without degrading constraint compliance.<n>We find that compact headers reduce constraint-portion tokens by approximately 71% and full-prompt tokens by 25-30%, replicated across three independent rounds.
  arXiv  Detail & Related papers  (2026-04-08T15:18:33Z)
• The Model Says Walk: How Surface Heuristics Override Implicit Constraints in LLM Reasoning [9.898274894485107]
  Large language models systematically fail when a salient surface cue conflicts with an unstated feasibility constraint.<n>We study this through a diagnose-measure-bridge-treat framework.
  arXiv  Detail & Related papers  (2026-03-30T21:36:09Z)
• CCTU: A Benchmark for Tool Use under Complex Constraints [66.87622847854337]
  We introduce CCTU, a benchmark for evaluating large language models (LLMs) under complex constraints.<n>The benchmark comprises 200 carefully curated and challenging test cases across diverse tool-use scenarios.<n>We develop an executable constraint validation module that performs step-level validation and enforces compliance.
  arXiv  Detail & Related papers  (2026-03-16T14:05:13Z)
• Did You Forget What I Asked? Prospective Memory Failures in Large Language Models [0.0]
  Large language models often fail to satisfy formatting instructions when they must simultaneously perform demanding tasks.<n>We study this behaviour through a prospective memory inspired lens from cognitive psychology, using a controlled paradigm.<n>Vulnerability is highly type-dependent, with drops up to 50%, while avoidance constraints remain comparatively robust.<n>A salience-enhanced format (explicit instruction framing plus a trailing reminder) recovers much of the lost compliance, restoring performance to 90-100% in many settings.
  arXiv  Detail & Related papers  (2026-03-07T05:58:19Z)
• Programming over Thinking: Efficient and Robust Multi-Constraint Planning [54.77940831026738]
  SCOPE is a framework that disentangles query-specific reasoning from generic code execution.<n>SCOPE achieves state-of-the-art performance while lowering cost and latency.
  arXiv  Detail & Related papers  (2026-01-14T02:58:07Z)
• Adaptive Neighborhood-Constrained Q Learning for Offline Reinforcement Learning [52.03884701766989]
  offline reinforcement learning (RL) algorithms typically impose constraints on action selection.<n>We propose a new neighborhood constraint that restricts action selection in the Bellman target to the union of neighborhoods of dataset actions.<n>We develop a simple yet effective algorithm, Adaptive Neighborhood-constrained Q learning (ANQ), to perform Q learning with target actions satisfying this constraint.
  arXiv  Detail & Related papers  (2025-11-04T13:42:05Z)
• A Multi-Dimensional Constraint Framework for Evaluating and Improving Instruction Following in Large Language Models [48.361839372110246]
  We develop an automated instruction generation pipeline that performs constraint expansion, conflict detection, and instruction rewriting.<n>We evaluate 19 large language models and uncover substantial variation in performance across constraint forms.<n>In-depth analysis indicates that these gains stem primarily from modifications in the model's attention modules parameters.
  arXiv  Detail & Related papers  (2025-05-12T14:16:55Z)
• RAYEN: Imposition of Hard Convex Constraints on Neural Networks [47.494620411594624]
  RAYEN is a framework to impose hard convex constraints on a neural network. It achieves times between 20 and 7468 times faster than state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2023-07-17T09:12:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.