Research map / Large language models / Language, safety and interpretability
Quantifying Generalization Complexity for Large Language Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces Scylla, a dynamic, knowledge-light, memorization-aware framework that measures LLM generalization via ID-vs-OOD performance gaps across 20 algorithmic tasks at five time-complexity levels, revealing a "generalization valley" whose peak (critical complexity) shifts right with model size, and benchmarks 28 LLMs.
Problem
Generalization of LLMs is entangled with memorization and data contamination, and existing reasoning benchmarks conflate task length with intrinsic complexity, so it is unclear how task complexity and model size affect the balance between generalizable and memorized behavior.
Approach
Scale task difficulty by algorithmic time complexity (with input length controlled), generate ID data by querying the model itself for inputs it is familiar with, and create OOD data by sampling numbers outside the model's ID element set; the ID-OOD accuracy gap serves as a memorization indicator, yielding a generalization valley and critical complexity.
Key results
- Llama-3.1-405B reaches generalization scores of 0.997 on O(N) and 0.996 on O([N,N^2]) and 0.847 on O([N^2,N^3]).
- o1-mini achieves the highest generalization scores across all classes (1, 0.998, 0.979, 0.949, 0.68) and is one of two models with critical complexity O(2^N), alongside GPT-4o-mini.
- Among open models, critical complexity shifts rightward with scale, e.g. Qwen1.5 from O(N) at 1.8B to O([N^3,N^4]) at 72B/110B.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase model size within open-source model families | Open-source LLMs evaluated with Scylla · Scylla task complexities | Critical Complexity | Helped |
| Increase task complexity | LLMs evaluated with Scylla · ID-OOD performance gap across anchor-task complexity levels | ID-OOD performance gap | Mixed |
| Use GPT-4o-mini instead of GPT-4o | GPT-4o · Scylla critical complexity | Critical Complexity | Helped |
| Fine-tune Qwen2.5-7B for mathematics | Qwen2.5-7B · Scylla O(N) and O([N,N^2]) | Generalization Score: 0.617 -> 0.971; 0.632 -> 0.874 | Helped |
| Fine-tune Qwen2.5-7B for code | Qwen2.5-7B · Scylla O(N) and O([N,N^2]) | Generalization Score: 0.617 -> 0.969; 0.632 -> 0.832 | Helped |
| Fine-tune Qwen2.5-7B for mathematics | Qwen2.5-7B · Scylla O([N^2,N^3]) | Generalization Score: 0.514 -> 0.591 | Helped |
| Fine-tune Qwen2.5-7B for code | Qwen2.5-7B · Scylla O([N^2,N^3]) | Generalization Score: 0.514 -> 0.205 | Hurt |
| Fine-tune Qwen2.5-7B for mathematics | Qwen2.5-7B · Scylla O([N^3,N^4]) | Generalization Score: 0.122 -> 0.135 | Helped |
| Fine-tune Qwen2.5-7B for code | Qwen2.5-7B · Scylla O([N^3,N^4]) | Generalization Score: 0.122 -> -0.021 | Hurt |
| Use Scylla evaluation across increasing task complexity | LLMs evaluated on anchor tasks · ID-OOD performance gap | ID-OOD performance gap | Mixed |
Surprising findings
- GPT-4o-mini shows a higher critical complexity than expected for its size, and Qwen2.5-Math-7B and Qwen2.5-Coder-7B improve on low-complexity tasks but not on higher ones.
- Some models (e.g., Llama-3-70B, Llama-3.1-70B) have negative generalization scores at high complexity levels, indicating larger OOD than ID accuracy.
Limitations
- Evaluation relies on algorithmic tasks with numeric inputs, limiting coverage of general reasoning.
- ID data is approximated by querying the model for inputs it generates, which is an indirect proxy for true pretraining familiarity.
- Only 256 test samples per ID and OOD set, and time-complexity levels are assigned by the authors' analysis rather than verified empirically.
Experimental setup
Datasets: model-generated ID inputs (about 10k prompts, about 100k elements per task) synthetic OOD inputs sampled from [0, 9999]
Benchmarks: Scylla
Metrics: accuracy generalization score ID-OOD performance gap critical complexity
Baselines: CLRS-Text NPHardEval DyVal LiveBench
Builds on: zero-shot chain-of-thought CLRS-Text NPHardEval DyVal
Closest papers by meaning
- Generalization v.s. Memorization: Tracing Language Models’ Capabilities Back to Pretraining Data (ICLR 2025 · similarity 0.91)
- What Do Learning Dynamics Reveal About Generalization in LLM Mathematical Reasoning? (ICML 2025 · similarity 0.90)
- Delving into the Reversal Curse: How Far Can Large Language Models Generalize? (NeurIPS 2024 · similarity 0.90)
- metabench - A Sparse Benchmark of Reasoning and Knowledge in Large Language Models (ICLR 2025 · similarity 0.90)
- Supervised Knowledge Makes Large Language Models Better In-context Learners (ICLR 2024 · similarity 0.89)
- An Analysis for Reasoning Bias of Language Models with Small Initialization (ICML 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.