Technical Summary: Orthographic Constraint Satisfaction and Human Difficulty Alignment in Large Language Models

1. Problem Statement

Large language models (LLMs) face a fundamental challenge when generating text under hard orthographic constraints: satisfying discrete, character-level rules while navigating large combinatorial spaces. Unlike semantic pattern matching, which dominates LLM training, constrained generation requires strict adherence to structural validity (e.g., using only a specific set of letters, including a mandatory character, and meeting minimum length requirements).

A core tension exists between distributional plausibility and structural validity. Models trained on distributional patterns may assign low generation probabilities to constraint-valid solutions that exhibit atypical orthographic patterns (e.g., doubled consonants or specific letter repetitions), even if those words are frequent in training data. While prior work has examined semantic constraints or used decoding-time guarantees (e.g., Grid Beam Search), there is a lack of systematic evaluation on how instruction-tuned models handle hard orthographic constraints in open-vocabulary settings without external enforcement mechanisms. Furthermore, the interaction between model scale, computational budgets (reasoning tokens), and human-calibrated difficulty remains under-explored.

2. Methodology

The authors evaluate 39 model configurations across three families (Qwen3, Claude Haiku 4.5, and GPT-5-mini) on 58 puzzles from the New York Times Spelling Bee.

Task Definition

Models are tasked with generating English words using a specific set of seven letters, where one letter is mandatory. Valid outputs must:

1. Contain at least four letters.
2. Use only the provided seven letters (repetition allowed).
3. Include the mandatory center letter.
4. (Bonus) Use all seven letters to form "pangrams."

Experimental Setup

• Models:
  • Qwen3: Five open-source models (4B, 8B, 14B, 32B dense; 30B-A3B Mixture-of-Experts). Tested in direct generation and "thinking" modes at 4K, 8K, and 16K token budgets.
  • Claude Haiku 4.5: Proprietary model tested in direct and extended thinking modes at 4K, 8K, and 16K budgets.
  • GPT-5-mini: Proprietary model tested at three reasoning effort levels (mapped to approximate token budgets).
• Prompting: Zero-shot prompts explicitly list constraints without revealing solution counts or expected output lengths to isolate intrinsic constraint-handling capabilities.
• Human Difficulty Baseline: The study utilizes aggregate performance data from 10,000 human solvers per puzzle to establish ground-truth difficulty metrics (success rates ranging from 3% to 97%).
• Metrics: Precision, Recall, and F1 score. Additionally, the study measures calibration strength (Spearman rank correlation between human difficulty and model miss rates) and length-stratified recall.

3. Key Contributions

1. Cross-Family Performance Characterization: The study demonstrates that differences between model families are substantially larger (2.0–2.2× F1 gap) than gains achieved through parameter scaling within a single family (83% gain from 4B to 32B in Qwen). This gap is driven primarily by recall rather than precision.
2. Heterogeneous Budget Sensitivity: The impact of "thinking" budgets is not uniform. High-capacity models show strong returns on increased compute, while mid-sized models (e.g., Qwen-14B) may degrade with increased allocation, and smaller models show no sensitivity.
3. Human Difficulty Alignment and Failure Analysis: Using large-scale human data, the authors establish modest but consistent calibration (ρ = 0.28–0.42) across families. Crucially, they identify systematic failures on common words with unusual orthography (e.g., "data," "loll," "acai") where human success is high (>80%) but model miss rates are extreme (>92%).

4. Key Results

Cross-Family vs. Within-Family Scaling

• Performance Gap: Proprietary models (GPT-5-mini, Claude Haiku) achieve F1 scores 2.0–2.2× higher than the largest open-source Qwen3 configuration (32B).
• Recall vs. Precision: The performance gap is driven by recall (Proprietary: 68% vs. Qwen-32B: ~23%), while precision differences are modest (9 percentage points).
• Pangram Recall: The gap widens significantly for complex constraints; GPT-5-mini achieves 77.6% pangram recall versus 15.8% for Qwen-32B.
• Tokenization Confound: A partial-correlation analysis rules out tokenizer design as the primary confound for within-family scaling differences.

Budget Sensitivity

• High-Capacity Models: Dense (32B) and MoE (30B) Qwen variants, along with proprietary models, show positive returns from increased thinking budgets. The MoE 30B variant (with only 3B active parameters) shows the strongest dependence, requiring substantial budget to compensate for limited effective capacity.
• Mid-Sized Degradation: The Qwen-14B model exhibits paradoxical degradation, where performance drops as the reasoning budget increases. The authors suggest this may be due to the amplification of distributional plausibility without proportional improvement in constraint verification.
• Small Model Insensitivity: Smaller models (4B, 8B) show flat performance across budgets, often failing to generate any valid words on 51% of puzzles without thinking mode.

Human Difficulty Alignment

• Calibration: There is a modest correlation between human difficulty and model miss rates (ρ = 0.28–0.42). Proprietary models show higher alignment than open-source counterparts.
• Systematic Failures: Models consistently fail on common words with specific orthographic patterns:
  • Doubled Consonants: "illicit," "loll," "annotation."
  • Repeated Letters: "papa," "nana," "toon."
  • Atypical Patterns/Loanwords: "data," "acai."
  • Observation: These words are frequent in training data but are missed because their orthographic patterns are underrepresented relative to their frequency or violate the model's learned distributional priors.

Length-Dependent Degradation

• Human vs. Model: Human success declines gently with word length (1.3× drop from 4-letter to 7+ letter words).
• Model Collapse: Models show catastrophic degradation with length, ranging from 1.5× to over 71× drops in recall depending on capacity. This suggests a lack of robustness in handling increasing combinatorial complexity compared to human working memory strategies.

5. Significance and Claims

The paper claims that current LLM architectures exhibit a systematic over-reliance on distributional plausibility, which penalizes orthographically atypical but constraint-valid patterns. The findings suggest that:

1. Constraint Satisfaction is Distinct: Satisfying hard orthographic constraints engages different mechanisms than natural language generation, revealing bottlenecks in working memory and systematic enumeration that are not resolved by parameter scaling alone.
2. Architecture Matters More than Scale: Cross-family architectural differences (likely involving training data composition or optimization) are more critical for constraint satisfaction than increasing parameter counts within a family.
3. Budget Allocation is Non-Linear: Increasing computational budgets does not universally improve performance; for some models, it exacerbates failures by amplifying distributional biases.
4. Future Directions: The authors propose that addressing these issues requires explicit verification modules independent of distributional priors, training objectives that reward orthographically unusual solutions, and model-specific budget allocation policies. They also note that these findings may generalize to other constrained domains like code synthesis and structured data generation where correct outputs may be distributionally atypical.

The study concludes that while models can satisfy constraints, they do so with a fragility that differs significantly from human cognition, particularly regarding the verification of structural validity against learned statistical priors.