Beyond Constraint Counts: A Difficulty-Aware View of Instruction Following in Language Models

Large language models increasingly operate under complex user instructions, where violating explicit requirements can undermine otherwise useful outputs. Many instruction-following evaluations summarise compliance at the task level or by constraint count, potentially obscuring substantial variation among individual requirements. We study whether model-conditioned properties of constrained satisfaction provide a more informative characterisation of this variation. Across structurally graded tasks, we estimate individual difficulty using boundary slack, concentration among sampled successful outputs, and conditional perplexity. Compliance is consistently associated with all three properties, with a mean absolute correlation of \(|\rho|\approx0.55\), while prompt interventions designed to shift these properties improve compliance by approximately 6.5 percentage points on average. In multi-constraint settings, the same properties characterise interaction difficulty, where coupling can reduce constituent compliance by up to $15$ points, while at fixed constraint counts, mean follow rates differ by $>50$ points across sets stratified by measured constituent difficulty. We further test controlled extensions beyond feasible sharp constraints, showing that across low to high difficulty settings, infeasibility recognition and fuzzified properties increase by approximately \(70.7%\) and change with a mean $53.7\%$, respectively. Together, these results provide evidence that difficulty-aware measurements capture variation in instruction following that raw constraint counts miss, motivating broader evaluation of difficulty-aware diagnostics and mitigation.