Across 20 algorithmic tasks spanning five time-complexity levels, the accuracy gap between in-distribution and out-of-distribution data first widens as task complexity increases, reaches a peak (the critical complexity), and then narrows. This pattern is observed consistently across model families including Qwen 1.5, Llama 3/3.1/3.2, Gemma 2, Claude 3, and GPT-4o. At the peak, models perform well on familiar (ID) inputs but degrade sharply on novel (OOD) inputs, indicating over-reliance on memorized patterns rather than true generalization. Beyond the peak, both ID and OOD accuracy decline, reflecting the model's inability to handle the task at all.
Evidence
correlational
Key metric
Qwen1.5-1.8b: ID acc 0.78±0.12 vs OOD acc 0.05±0.03 at O(n); Qwen1.5-110b: ID acc 0.99±0.02 vs OOD acc 0.18±0.12 at O(n). Llama-3.1-405b generalization scores: 0.997, 0.996, 0.847, 0.516, 0.262 across O(n) to O(2^n). GPT-4o: 0.997, 0.992, 0.787, 0.457, 0.238.
Caveat
The ID data is approximated by querying the model to generate examples, not by accessing the actual pretraining corpus. The authors validate this approximation with OLMo-7B but acknowledge it is an approximation. All results use zero-shot chain-of-thought prompting.