Quantifying Generalization Complexity for Large Language Models
Authors: name: Zhenting Qi, name: Hongyin Luo, name: Xuliang Huang, name: Zhuokai Zhao, name: Yibo Jiang, name: Xiangjun Fan, name: Himabindu Lakkaraju, name: James Glass

While large language models (LLMs) have shown exceptional capabilities in
understanding complex queries and performing sophisticated tasks, their
generalization abilities are often deeply entangled with memorization,
necessitating more precise evaluation. To address this challenge, we introduce
Scylla, a dynamic evaluation framework that quantitatively measures the
generalization abilities of LLMs. Scylla disentangles generalization from
memorization via assessing model performance on both in-distribution (ID) and
out-of-distribution (OOD) data through 20 tasks across 5 levels of complexity.
Through extensive experiments, we uncover a non-monotonic relationship between
task complexity and the performance gap between ID and OOD data, which we term
the generalization valley. Specifically, this phenomenon reveals a critical
threshold - referred to as critical complexity - where reliance on
non-generalizable behavior peaks, indicating the upper bound of LLMs'
generalization capabilities. As model size increases, the critical complexity
shifts toward higher levels of task complexity, suggesting that larger models
can handle more complex reasoning tasks before over-relying on memorization.
Leveraging Scylla and the concept of critical complexity, we benchmark 28LLMs
including both open-sourced models such as LLaMA and Qwen families, and
close-sourced models like Claude and GPT, providing a more robust evaluation
and establishing a clearer understanding of LLMs' generalization capabilities.