# Quantifying Generalization Complexity for Large Language Models

arXiv: https://arxiv.org/abs/2410.01769 · HTML: https://mlsanity.com/paper/2410.01769/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 47 references that are in the map.
- First posted on arXiv 2 Oct 2024.

## Builds on (most cited first, 30 of 44)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context](https://mlsanity.com/paper/2403.05530/) (2024)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models](https://mlsanity.com/paper/2206.04615/) (2022)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [Quantifying Memorization Across Neural Language Models](https://mlsanity.com/paper/2202.07646/) (2022)
- [Large Language Models Struggle to Learn Long-Tail Knowledge](https://mlsanity.com/paper/2211.08411/) (2022)
- [Reasoning or Reciting? Exploring the Capabilities and Limitations of Language Models Through Counterfactual Tasks](https://mlsanity.com/paper/2307.02477/) (2023)
- [Data Contamination: From Memorization to Exploitation](https://mlsanity.com/paper/2203.08242/) (2022)
- [FOLIO: Natural Language Reasoning with First-Order Logic](https://mlsanity.com/paper/2209.00840/) (2022)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [Time Travel in LLMs: Tracing Data Contamination in Large Language Models](https://mlsanity.com/paper/2308.08493/) (2023)
- [Causal Parrots: Large Language Models May Talk Causality But Are Not Causal](https://mlsanity.com/paper/2308.13067/) (2023)
- [Emergent and Predictable Memorization in Large Language Models](https://mlsanity.com/paper/2304.11158/) (2023)
- [Impact of Pretraining Term Frequencies on Few-Shot Reasoning](https://mlsanity.com/paper/2202.07206/) (2022)
- [Mutual Reasoning Makes Smaller LLMs Stronger Problem-Solvers](https://mlsanity.com/paper/2408.06195/) (2024)
- [Generalization or Memorization: Data Contamination and Trustworthy Evaluation for Large Language Models](https://mlsanity.com/paper/2402.15938/) (2024)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Q*: Improving Multi-step Reasoning for LLMs with Deliberative Planning](https://mlsanity.com/paper/2406.14283/) (2024)
- [Rethinking LLM Memorization through the Lens of Adversarial Compression](https://mlsanity.com/paper/2404.15146/) (2024)

## Built on by (most cited first, 18 of 18)

- [SFT Memorizes, RL Generalizes: A Comparative Study of Foundation Model Post-training](https://mlsanity.com/paper/2501.17161/) (2025)
- [A Survey of Frontiers in LLM Reasoning: Inference Scaling, Learning to Reason, and Agentic Systems](https://mlsanity.com/paper/2504.09037/) (2025)
- [Satori: Reinforcement Learning with Chain-of-Action-Thought Enhances LLM Reasoning via Autoregressive Search](https://mlsanity.com/paper/2502.02508/) (2025)
- [Beyond Reward Hacking: Causal Rewards for Large Language Model Alignment](https://mlsanity.com/paper/2501.09620/) (2025)
- [CLIPPER: Compression enables long-context synthetic data generation](https://mlsanity.com/paper/2502.14854/) (2025)
- [Token-Level LLM Collaboration via FusionRoute](https://mlsanity.com/paper/2601.05106/) (2026)
- [LLM Evaluation Based on Aerospace Manufacturing Expertise: Automated Generation and Multi-Model Question Answering](https://mlsanity.com/paper/2501.17183/) (2025)
- [Rote Learning Considered Useful: Generalizing over Memorized Data in LLMs](https://mlsanity.com/paper/2507.21914/) (2025)
- [Sustainability via LLM Right-sizing](https://mlsanity.com/paper/2504.13217/) (2025)
- [Patterns and Mechanisms of Contrastive Activation Engineering](https://mlsanity.com/paper/2505.03189/) (2025)
- [LLM Chemistry Estimation for Multi-LLM Recommendation](https://mlsanity.com/paper/2510.03930/) (2025)
- [Rethinking the Unsolvable: When In-Context Search Meets Test-Time Scaling](https://mlsanity.com/paper/2505.22290/) (2025)
- [Why Does RL Generalize Better Than SFT? A Data-Centric Perspective on VLM Post-Training](https://mlsanity.com/paper/2602.10815/) (2026)
- [Enough is as good as a feast: A Comprehensive Analysis of How Reinforcement Learning Mitigates Task Conflicts in LLMs](https://mlsanity.com/paper/2607.22039/) (2026)
- [RegexPSPACE: A Benchmark for Evaluating LLM Reasoning on PSPACE-complete Regex Problems](https://mlsanity.com/paper/2510.09227/) (2025)
- [Disentangling generalization and memorization in large language models using chess](https://mlsanity.com/paper/2601.16823/) (2026)
- [OrdinalBench: A Benchmark Dataset for Diagnosing Generalization Limits in Ordinal Number Understanding of Vision-Language Models](https://mlsanity.com/paper/2603.07786/) (2026)
- [Understanding Large Language Models](https://mlsanity.com/paper/2607.01006/) (2026)

## Abstract (arXiv)

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.