Quantifying Generalization Complexity for Large Language Models
Authors: Zhenting Qi
Hongyin Luo
Xuliang Huang
Zhuokai Zhao
Yibo Jiang
Xiangjun Fan
Himabindu Lakkaraju
James R. Glass
Venue: ICLR 2025 Poster (2025)
Keywords: large language model
generalization
evaluation
Primary area: foundation or frontier models, including LLMs

Abstract: 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 28 LLMs including 
both open-sourced models such as LLaMA and Qwen families, and closed-sourced models like Claude and 
GPT, providing a more robust evaluation and establishing a clearer 
understanding of LLMs' generalization capabilities.

Published as a conference paper at ICLR 2025
QUANTIFYING GENERALIZATION COMPLEXITY FOR LARGE LANGUAGE MODELS
Zhenting Hongyin Luo?, Xuliang Huang", Zhuokai Zhao Yibo Jiang? Xiangjun Fan', Himabindu Lakkaraju', James Glass Haarvard University, *Massachusetts Institute of Technology
University of Illinois at Urbana-Champann *Meta, University of Chicago zhentingee iranniingg@g..... hww.ard.eda.... byluoêmit.c. cemmmiteed edu
ABSTRACT
While large language models (LLMs) have shown exceptional capabilities in un- derstanding complex queries and performing sophisticated tasks, their generaliza- tion abilities 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 exper- iments, we uncover non-monotonic relationship between task complexity and the performance gap between ID and OOD data, which we term the generaliza- tion valley. Specifically, this phenomenon reveals critical threshold-referree to as critical complexity-whert 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 memorization. Leveraging SCYLLA and the concept of critical complexity, we benchmark 28 LLMs including both open-sourced models such LLaMA and Qwen families, and closed-sourced models like Claude and GPT, providing more robust evaluation and establishing a clearer understanding of LLMs' generalization capabilities.
INTRODUCTION
Large language models (LLMs) have revolutionized natural language processing by exhibiting ex- ceptional abilities in understanding complex queries, generating human-like text, and performing a variety of downstream tasks (OpenAl 2023 Google 2024 Bubeck et al. 2023 Hoffmann et al.)
2022). Beyond their impressive text-generation capabilities, these models also demonstrate emerg- ing skills in reasoning (Wei et al. 2022b Kojima al. (022). Through increased inference-tine computation (Chen et 2024bb Snell et al. [024]] Bansal et al. 2024 Qi et al.) 2024: Wang et al.)
2024), LLMS have achieved or surpassed human-level performance
benchmarks that
quire nontrivial reasoning abilities (Cobbe et al. 2021 Hendrycks et al. 2021 2020 Chen et al.)
2021 Han et al. 2022). Despite these impressive advancements, research has also demonstrated that
LLMs face significant challenges when solving problems that involve terms, patterns, or concepts
that are less common in their training data (Razeghi et al., 2022 Kandpal al. 2023 Chen al.)
2024a Antoniades et al.) 2024). Additionally. concerns have been raised regarding data contam- ination (Magar& Schwartz, 2022b) [Carlini et al. [0222] Dong et al.] [2044). as many benchmark
datasets are sourced from the web and may overlap with the training data, either directly or in- directly, which undermines the reliability of results on such benchmarks. Consequently. there ongoing debate about whether LLMs truly possess human like reasoning abilities simply rely memorized patterns when solving problems (Kambhampati] 2024 Scchaarsschid et al. 2024).
"Wrk completed during Zhenting's visit to MIT CSAIL. Source code will be available https: g github. ctchub.commzie zhent inggi//innnnnnnn 11

---

Published as a conference paper at ICLR 2025
Several efforts have been made to explore the interplay between generalization and memorization in LLMs' reasoning behaviors [Wu et al., 2023; Lotfi et al. 2023 Zhu et al. 2023 Antoniades
et al.
2024 Dong et al., 2024). Lotfi et al. (2023) present the first non- convvauuuus generalization
bounds for L.Mss demonstrating their ability to discover patterns that generalize to unseen data. et al. 2023) suggest that generalization and memorization often exist on a continuum, as LLMS exhibit above-random performance on counterfactual tasks, though with some degradation com- pared to default tasks. Their study proposes that the seemingly "reasoning" behaviors of LLMs may stem from a combination of: (1) generalization behaviors, such as abstract logic and learned skills, and (2) memorization behaviors, including memorized input-output mappings and pattern matching. Despite these recent insights, the relationship between task difficulty, model size, and the balance between generalization and memorization remains poorly understood. Several factors undermine the robustness of current findings. First, reliable methods for quantifying task difficulty are still underdeveloped, and the distinction between problem length and intrinsic task complexity is often overlooked. Additionally, evaluations usually complicated by data contamination and the entanglement with knowledge, introducing confounding factors to reasoning assessments.
In this work, quantify the generalization ability of LLMs by aligning models with the intrin- sie complexity of reasoning tasks. We address two specific research questions: 1) How does task complexity affect the balance between generalizable (generalization) and non-generalizable (memorization) behaviors? 2) How does model size influence this balance? We first de- velop a novel evaluation framework, SCYLLA, that is scalable in task complexity, dynamic, knowledge-liggh light, and memorization-awarc for understanding the working mechanism of generalization, and show that no existing eval- uation methods fully meet them. SCYLLA enables the generation of in-distribution (ID) and distr--iistriuttinn (OOD) data of a given task, and the performance gap between them is con- sidered an indicator of reliance on non-generalizable behaviors to solve the task. This al- lows us to assess how well models generalize learned task skills beyond their training distri- bution. We evaluate the performance of LLMs both ID and OOD data across varying lev- els of quantified task complexity. The results of our experiments lead to two key findings: 1) Non-monotonic performance gap across task complexity: the performance gap between ID and OOD data initially widens task com- plexity increases, reaches a peak, and then nar- rows as tasks become more complex-a phe- nomenon we refer to as generalization valley. As shown in Fig. [ this monooono rela- tionship suggests that LMs are most vulnerable to distribution shifts at certain intermediate task complexity levels, where overfitting to training data leads to a greater dependence on memo- rization. and 2) Peak of generalization valley shifts rightward with increasing model size: as the model size increases, the peak of per- formance gap, referred to as the critical com- plexity, shifts to the right. As shown in Fig. [ this rightward shift indicates that larger mod- els are better equipped handle more complex tasks without over-relying on memorization, maintaining generalization capabilities across broader range of task difficulties.
We explain the necessity of each of these criteria
ID Acc.
OOD Acc.
Gap
Hama3.1-708
1.0
0.8
0.6
0.4
0.2
0.0
o(N)
OWN.. 1)
O(N2,, NN1]
O(NN N11)
0(2%)
O(N)
O(NN. N2
O(N?, N21)
ONN? N/
0(2%)
Figure 1: An illustration of generalization valley, where the reliance non non-generalizable behay- iors first increases and then decreases; and criti- cal complexity shift, where the peak of the valley shifts rightward as model size increases.
The contributions of this paper are fourfold. First, we present novel, task-centric evalua- tion framework that scalable in task complexity, dynamic, knowledge-light, and memorization- aware, specifically designed to overcome limitations found in existing evaluation methods. Second, through a detailed analysis of performance across varying task complexities and model sizes, we uncover insights into generalization behavior, revealing patterns that distinguish when models in- creasingly rely on memorization versus generalization. And third, we highlight the impact of model size on generalization, demonstrating that larger models experience delayed over-reliance mem- orization, with peak performance discrepancies occurring at higher task difficulties than in smaller
2

---

Published as a conference paper at ICLR 2025
models. Finally, leveraging proposed framework and insights, we define new metric that aims to reward models with strong generalization to OOD data while penalizing those that exhibit overfit- ting to ID data, and conduct a comprchensive benchmarking of 28 popular LLMs, focusing on their genuine reasoning capabilities.
2 RELATED WORK
2.1
GENERALIZATION & MEMORIZATION IN LLMS' REASONING
The debate over whether LLMs can genuinely reason simply rely memorization remains cen- tral to understand their true capabilities (Zhang et al. 2021
T Tänzer et al. 2021 Zečević et al. 2023]
Tang et al. 2023 Yin et al., 2023 Biderman et al. (2024) Wu et al (2023) argue that models like GPT-4 perform well on default tasks but struggle sigmificanlly with counterfactual ones, implying that much of their success comes from memorization of specific patterns. Similarly, [Dong et al. (2024) highlight how data contamination can inflate perceived generalization by enabling models to rely on memorized data, while Antoniades et al. (2024) observe that even larger models, which gen- erally show stronger generalization, still exhibit memorization behaviors, especially for frequently encountered n n-grams. Kambhampati (2024) assert that LLMs primarily perform "aaproximate re- trieval" from large pretraining datasets rather than true reasoning. In contrast, Lotñ et al. (2023) introduce the first non-vacuous generalization bounds for L.Ms,, providing a mathematical frame- work that demonstrates LLMs' capability to discover regularities and generalize beyond their train- ing data, particularly as models scale up, and thus disprove that larger L.LMs are simply better at regurgitating training data. Together, these works highlight the ongoing tension between memoriza- tion and generalization, and the need for more robust evaluations that diffcrentiate between the two.
2.2 EVALUATION OF LLMS' REASONING ABILITIES
Reasoning is recognized as a key component of both human cognition and Al development, driv- ing research to evaluate the reasoning abilities of LLMs (Zhu al., 2023). Recent research has emphasized tasks requiring logic and deduction-Such as those involving math, text, and code-as benchmarks for reasoning across domains, generally divided into static and dynamic categories.
Specifically, static benchmarks, including MATH (Hendrycks et al.] (021). GSM8K (Cobbe et al., 2021). BoardgameQA (Kazemi et al., 2023). and FOLIO (Han et al.) 2022] use mathematical and logical problems to assess reasoning performance. However, these benchmarks. which remain fixed after publication, are vulnerable to data contamination (Magar & Schwartz, 2022a Golchin & Sur- deanu, (023) and reasoning gap issues (Srivastava et 20,44. To address these limitations, recent benchmarks have adopted a dynamic approach, either by generating new problem instances at test time by regularly refreshing test data. CLRS-Text (Veličković et al.) 2022), for instance, draws on algorithms from Introduction to Algorithms (Cormen et al. 2009) and synthesizes algorithmic reasoning problems in text form. Similarly, NPHardEval (Fan et al. 2023) is built upon algorithm tasks. It organizes them by complexity class, defines difficulty levels by problem lengths, and re- freshes data a monthly basis to mitigate the risk of overfitting. LiveBench (White et al., 2024) also frequently updates questions from the most recent information sources, but the task set tends be too knowledge-intense
to be a good testbed for reasoning. Dy (Zhu al., 2023) employs a graph-informed algorithm to generate math, logic, and algorithm test cases, but faces challenges in manually specifying problems as graphs and defining valid constraints. Despite these research efforts, they barely disentangle reasoning and generalization from memorization or quantitatively align the intrinsic task complexity and generalization ability.
3 METHOD
3.1 MOTIVATION
To conduct reliable evaluations of the generalization capabilities of LLMs, we begin by discussing several key features that are essential for an effective benchmark. While prior research has touched
upon the importance of scalable and dynamic evaluation (Zhu et al.; 2023 Fan et al. 2023), refine these criteria with clearer definitions and emphasize two additional critical dimensions: knowledge- light and memorization-aware.
3

---

Published as a conference paper at ICLR 2025
Scalable inherent complexity. The difficulty of an ideal evaluation task should be both quantifi- able and scalable (Zhu et al., 2023; Fan et al. 2023). There are two dimensions that influence the difficulty of solving task: (1) the intrinsic complexity of the task and (2) the length of an imput problem instance. The former refers to tasks that inherently require more sophisticated reasoning and greater number of intermediate steps, with the number of steps increasing as function of the length of the input instances. Consequently, when benchmarks increase task difficulty by both ex- lending input lengths and introducing tasks of varying complexity, as seen in (Fan et al. [203 Zhu et al., 2023), it becomes difficult to distinguish whether performance drops stem from the challenges with longer inputs or the tasks' intrinsic complexity. Plus, LLMs are known struggle with length generalization problem, exhibiting a sharp decline in performance (Anil et al. (2022 or becoming
unstable (Zhou et al. 2024) as input length increases. For these reasons, problem length is not an ideal hyperparameter for adjusting task difficulty and should be controlled. In other words, task difficulty should scale independently of input length.
Dynamic question generation. Optimal benchmark task instances should be generated dynamically to minimize the risk of data contamination. Many widely adopted reasoning benchmarks, such as those for mathematical reasoning (Cobbe al., 2021 Hendrycks et al. 2021), are based on static datasets. However, evaluations based on static data often encounter challenges such as the reasoning
gap problem (Srivastava et al. 2024) and data contamination (Magar & Schwartz, 2022a Golchin
& Surdeanu 2023) issues, reducing the robustness and reliability of these assessments.
Knowledge-light prerequisite. Ideal evaluation tasks for reasoning should require minimal back- ground knowledge, containing only simple task descriptions and queries. By minimizing the reliance on external information, we ensure that any performance differences most likely attributable to the models' reasoning abilities rather than disparities in their knowledge bases, eliminating the am- biguity of whether a model's 's failure is due to lack of necessary knowledge (Kandpal et al. 2023 Srivastava et al. 2022 Suzgun et al., 2022) or an inherent limitation in reasoming ability.
Memorization-awee evaluation. The benchmark should explicitly differentiate between task in- stances that are more likely to have been memorized and those that are less likely. This differentia- tion helps us accurately attribute the model's performance to either memorization or generalization.
3.2 SCYLLA BENCHMARK
Considering that none of the current benchmarks or evaluation frameworks meet all of the require- ments defined above, we propose new benchmark, SCYLLA, which distinguishes itself from exist- ing benchmarks through the following key features:
Scalable inherent Complexity: We utilize algorithmic complexity to quantify task complexity, defining tasks as more complex when they require algorithms of higher complexity for their so- lution. To ensure consistent complexity across tasks, we impose explicit constraints on problem lengths, ensuring the variation remains within a stable range while keeping the upper bound man- ageable, so that task complexity is minimally influenced by problem length. Our choice of tasks and their corresponding complexity bounds are detailed in $3.2.1
DYnamic problem generation: All data are generated during the evaluation, ensuring that each evaluation instance is unique and unaffected by pre-exposed data. Details of the data synthesis methodology can be found in $3.2.2
KnowLedge-Liige prerequisite: Tasks are designed to require no background knowledge, featur- ing simple and clear descriptions and straightforward instructions. All the tasks are designed to be solvable with basic skills such as additions and comparisons of non-negative integers.
Memorization-Al Aatiioo--wrree evaluation: Generalization and reasoning capabilities are more clearly dis- entangled from memorization through explicit differentiation between mn-disrrbbttoon (ID) and duitt--ditt (OOD) data. Performance on ID data reflects a combination of both general- ization and memorization, as the model is familiar with both the length and patterns of the task instances. Conversely, performance on OOD data primarily indicates generalization, as the model is only familiar with the length of the task instances but not the specific patterns of the task el- ements. Therefore, we propose to utilize the performance gap between ID and OOD data as an estimation of the model's ''s reliance memorization, allowing us to assess how well models gen- eralize learned task skills beyond their familiar instances. Procedures for generating ID and OOD data are detailed in 3.2.2
4

---

Published as a conference paper at ICLR 2025
Additionally, SCYLLA requires only black-box access LLM, enabling users to evaluate and compare different models across platforms without delving into their internal workings. Its task- centric design also ensures high adaptability and extensibility, allowing users to seamlessly tomize and expand it by incorporating new tasks and complexity levels to make the evaluation results more precise and reliable. Further comparisons with existing benchmarks or evaluation frameworks can be found in Appendix A.2
3.2. TASKS & COMPLEXITY LEVELS
To categorize and define the tasks in our benchmark, we adopt the notion of time com- plexity, which measures the order of growth of an algorithm's running time and pro- vides a standardized framework for comparing the efficiency of different algorithms (Cor- men et al., (009). In this context, we re-purpose LLMs as algorithm executors, where their ability to handle tasks expected to depend on the underlying computational complex- ity of those tasks. Our experiments, detailed later, validate this hypothesis by demonstrat- ing that time complexity provides a meaningful and rigorous method for task classification.
we first introduce chor tasks that define the intrinsic complex- ity levels in benchmark. Specifically, we utilize six levels of time complexity: O(N), O(N log N). O(N²), O(N"), O(N)), and O(2*) ) to define our complexity intervals. For specific task, we define its difficulty us- ing complexity range, denoted as O C2D, where C₁ and C2 represent the lower and upper bounds of the time complexity for algorithms that solve the task. The anchor tasks are selected based on two key crite- the se-
As shown in Fig. [
0(2%)
O(N
Ic5
Andtor
Probe
OijMiigh
Figure 2: Left: Anchor tasks. These tasks form the core of our benchmark, providing a structured set of challenges across varying time complexities. Right: Probe tasks. These tasks are used to evaluate the level of complexity that LLMs adopt to solve them.
ria. First, the time complexity lected tasks should fall within one two ad- jacent complexity levels to maintain consis- tency in difficulty. This ensures that the tasks within each group are comparable in terms of computational demands, preventing signif-
icant changes in difficulty. It also avoids scenarios where models face both very simple and highly complex tasks, which could lead inconsistent performance measurements and obscure the under- lying reasoning capabilities we aim to evaluate. Second, the tasks must be simple and should avoid reliance on advanced mathematical knowledge, common sense, or natural language understand- ing-factors outside the scope of the reasoning abilities we aim to evaluate. For instance, matrix multiplication involves specific mathematical concepts, which are not aligned with our focus on rea- soning capabilities. In contrast, tasks like "find max", which only require basic number ordering, provide a more appropriate measure of reasoning ability.
For anchor tasks, we propose three to four tasks for each complexity interval. The time complex- with complexity increasing in a clockwise direction the pie chart. Some task names abbreviated in the figure, but detailed in Table T
ities of these tasks are illustrated in the left of Fig. 2
To explore how LLMS handle tasks
Table 1: Anchor tasks for each complexity interval.
with multiple solutions of varying time complexities, we also introduce set of tasks termed probe tasks.
O(N)
Find min, find max, find mode
O[[N, N2
Find top k. two sum, sort numbers, remove duplicates 3-sum multiple ton, 3-sum in range. 3-sum 4-sum multiple ten, 4-sum in range, 4-sum
These tasks, including longest com- mon subarray (LCS), longest increas- ing sequence (LIS), and longest con- secutive elements (LCE), allow us to observe whether LLMs favor more efficient solutions task complexity increases. The correspond- ing time complexities of these tasks are shown in the graph on the right of Fig. 2 The behavior of
O[[N2 2
O[NN3 N2) 0(2*)
Subset sum mulliple ten, subset sum in range, subset sum, travelling salesman problem
LLMs in choosing between multiple solutions for these tasks is further discussed in $4.5) For both the anchor tasks and probe tasks, a detailed explanation of their time complexity, along with other relevant information, be found in Appendix
5

---

Published as a conference paper at ICLR 2025
ID Instanous
Valide d Giber
Dedk
Stcrple
[, Bl
ID Test Samples
15.
Prompl
bxttattest esumples
Intract clements
Generate number lists inputs for testing a program that, sulves the task of TwoSum.
Elazanta
Here are sume instiputt: [S 7,81 [t 9, 16]
[5, 7, 1, 16....
T3 Proboen Lorghs
LLM
4......
Sample from complament:stt
Task D Description
odtt Elaneck
Grven member list and barget valon, find two mombers in the list that up the larget value.
[4922, 6450, 4434, 7821, 2424, 8776, 7611....
DOD Instances
[4822, 6456, 6434] 17821,843 8776, 76111.
Valskae like
Detag.
Samçls
OOD Test Samples
Figure 3: Pipeline for generating ID and OOD dataset for a given task, tailored to each LLM.
Our time complexity-based approach contrasts with benchmarks such as CLRS (Veličković al., 2022 Markeeva et al.] (024) by not only grouping tasks by algorithm type, but also systemati- cally representing the relationships between tasks of varying complexities. While approaches like NvHardEval (Fan et al. ) and Val (Zhu et al., 2023) categorize tasks based on input length, they lack a clear connection between input length and task difficulty, and thus makes it difficult to discern whether lower performance stems from handling larger inputs or from the higher intrinsic complexity of the task itself. In contrast, SCYLLA improves upon these approaches by following more rigorous procedures of selecting tasks, defining complexities, and generating data, providing more reliable evaluations of L.LMs' generalization abilities.
3.2.2 DATA SYNTHESIS PIPELINE
The entire pipeline for synthesizing data is illustrated in Fig. 3 For a given task, the first step is to obtain the ID test data, consisting of instances that the LLM is already familiar with. However, directly accessing the pre-training dataset of an LLM is often impractical, as the dataset composition and pre-training mixtures are generally not publicly available. Moreover, the vast size of the text corpora makes processing challenging. In addition, proprietary models like GPT-4 usually provide only black-box APIs, limiting the ability to conduct in-depth analysis of the model itself.
To address these challenges, rectly querying the model about the distribution it is familiar with. Specifically, we first prompt the model to generate a substantial amount of test inputs tailored the task descrip- tion (see Appendix D.6] for prompt details). From these generated responses, we use regu- lar expressions to extract test examples and designate them as the ID test data. Addition- ally, the individual numbers within these examples are identified as ID elements, with their lengths referred to as ID problem lengths.
propose a workaround to approximate the ID) data by di-
our experiments, we typically prompt mod- els to generate no less than 10k instances and obtain around 100k ID elements for each task.
In Fig. 4 we show an example where we
query Mistral 7B model on the task of
Find Longest Increasing Subsequence. Be-
Probability
0.06
sides this task, we observe that for tasks in
0.04
SCYLLA, most of the ID elements fall within the range of (0, 100), and the example lengths are typically between 4 and 16. For further validation of this approximate method, please refer to Appendix B Next, we sample OOD elements from the complement of the ID el- ements, i.e., the set of elements that do not overlap with the ID elements. This is imple- mented by sampling elements from a univer- sal set and excluding those that overlap with the ID elements. To identify an appropriate universal set, one manually check the distribution of the extracted ID elements, shown in Fig. 4 From our experiments, a large and diverse range of numbers like [0, 9,999] is sufficient for defining the universal set for all the LLMs we have tested. Note that the upper bound of the universal set is also
0.02
40
80
100
Value
Figure 4: An example of probability distribution of ID elements collected by querying Mistral 7B v0.3 on the task of Find Longest Increasing Subsequence. The histogram shows the most frequent values with probabilities adding up to 90% (top-p=0.9).

---

Published as a conference paper at ICLR 2025
Acc. on ID data (Mean Std. Dev.)
O(N)
0.78 0.12
0.8 0.18
0.91 0.07
0.95 0.04
0.99 0.02
0.95 0.05
0.99 0.01
OIN,, N²1)
0.45 0.31
0.32 = 0.2
0.53 x: 0.19
0.75 = 0.23
0.83 x 0.19
0.95 z 0.05
0.96 0.03
2NIO (ee)
0.05 = 0.03
0.11 = 0.1
0.13 0.07
0.19 = 0.1
0.3 = 0.05
0.26 = 0.19
0.36 =: 0.03
ENI)O (L
0.03 0.04
0.06 0.06
0.06
0.06 0.04
0.21 0.1
0.22 0.14
0.36 0.22
((2M)
0.05 0.08
0.05 a 0.06
0.09 0.15
0.05 0.06
0.07 a 0.04
0.06 0.03
0.18 0.12
Acc. on OOD data (Mean + Std. Dev.)
((N)
0.66 a 0.21
0.72 x 0.13
0.91 x: 0.03
0.9 x 0.07
0.98 x 0.02
0.93 a 0.07
0.98 a 0.03
NNO, N21)
0.34
0.26 = 0.17
0.21
: 0.35
0.96 0.03
2NIO (le)
0.05 0.03
0.12 0.04
0.16 0.07
0.13 0.09
0.22 0.1
0.19 0.11
0.25 0.09
ENDDO
_N*])
0.01 0.0
0.07 = 0.04
0.09 a 0.03
0.04 = 0.03
0.16 a 0.11
0.09 2 0.07
0.21 + 0.02
0(2
0.03 0.07
0.03 a: 0.03
0.13
0.05 0.06
0.06 a: 0.04
0.01
#: 0.13
1.8B
4B
7B
14B
32B
72B
110B
Figure 5: ID/OOD performance of Qwen 1.5 family across five complexity levels.
Avg. Gap
Llama-3.2-38
Llama-3-8B
Gemma-2-9B
Claude-3-Sonnet
GPT-4o
01-mini
1.0
0.8
0.6
0.4
0.2
0.
atei
auR,8' ean' NPD cin gon o
ogN HPD aun' NDD own' gell
amm
oun NPD oun' N'D cqn sep
ote
odN HDD oun' out'.w' sa one. 111)
ouN. oww. NPn cuN'
otli
odN 6911
oun .1)
own get
Figure ID and OOD accuracy and performance gap curves for Llama-3.2-3B, Llama-3-8B, Gemma-2-9B, -laude-3-Somne,, GPT-4o. and ol mini. A significant drop in OOD accuracy is ob- served at the models' critical complexity, indicating a sudden decline in generalization ability.
restricted to avoid too many extra tokenizations of large numbers. To control for the length factor, we use the ID example sizes and OOD elements to construct OOD examples and obtain the OOD test data. During the actual benchmark experiments, be invalid or duplicated for both ID and OOD test data. To resolve this problem, we apply a vali- dation process, which filters out invalid examples and removes duplicates. Finally, 256 test samples are selected for each of the ID and OOD dataset.
notice that some generated examples may
4 EXPERIMENTS
In this section, we conduct extensive experiments using SCYLLA on a series of LLMs. Throughout $4.1 $4.2 and $4.4 we use anchor tasks to conduct evaluations. In $4.5 we use probe tasks to examine whether LLMs favor more efficient solutions when tasks can be solved with algorithms with wider range of time complexities. We used zero-shot chain-of-thougle method (Kojima al.) 2022] when prompting these models for solutions. Our choice to focus on zero-shot was deliberate, as adding few-shot examples would introduce a confounding variable- the selection and structure of the examples- could bias the results and obscure the intrinsic effects of model generalization.
4.1 PERFORMANCE ON ID AND OOD DATASET
We begin by evaluating 1.5 models on their generated ID and OOD datasets, as shown in Fig. 5 Accuracy on ID data consistently increases with model size. Smaller models (1.8B, 4B) show lower and more variable performance, whereas larger models (32B, 72B, 1 11OB) achieve nearly perfect accuracy with reduced variance. OOD performance also improves with model size. How- ever, the gap between ID and OOD accuracy persists, especially in smaller models. Larger models (32B and above) demonstrate significant OOD gains but still show greater variance in performance compared to ID tasks, highlighting the ongoing challenge of generalization.
7

---

Published as a conference paper at ICLR 2025
4.2 THE GENERALIZATION VALLEY PHENOMENON
Building initial evaluation of ID and OOD performance across different model sizes, now specifically focus on the performance gap between ID) and OOD data: max (0, Ap - AOOD). where Ap and AooD denote accuracy IID and OOD data, respectively. The performance gap between ID and OOD data provides deeper insights into the models' reliance on memorization versus their ability to generalize. As shown in Fig. 6 results for Llama-3.2-3B, Llama-3-8B, Gemma-2-9BB Claude-3-Sonnet, and GPT-4o reveal non-monotonic relationship between task complexity and the ID-OOD performance gap, which we refer to as generalization valley. Specif- ically, as task complexity increases, the gap widens, reaching a peak where models rely most on memorization, meaning that the model performs well on ID tasks but poorly on OOD tasks. This peak marks the point of critical complexity, at which models strug- gle generalize to unseen data, over- relying on memorized patterns from the training distribution. Fig. 6 also shows how models exhibit a clear drop in OOD accuracy as task reaches the critical complexity, which signals that models' ability to generalize is overwhelmed by the complexity of the task, leading to a sharp increase in the performance gap. Beyond this peak. both ID and OOD accuracy decline significantly, and the perfor- mance gap stabilizes at a lower level, reflecting the model's failure of relying on either memorization or generalization, showing model's 's diminished capacity to handle tasks of higher complexity.
L-m
Llama-3 3.1708 1-70B
Laam-33 1-408
0.15 0.19
Arc. cap bewweer ID 050
0.5
0.05
0.00
Owen-1.5-4
Owen-1 1.3-28
Owen-1 1.5-11088
0.200
0.05
Gemma-22
Gemma 2-98
Gemma-2- 2-278
0.5
D1N WoD
aute APD
ome, .r)
029
ow))
out aop
omn wD)
DRW ptp
0.00
oml
oUN HoD
amn" .P
omee A9)
ape
Figure 7: Critical complexity shifts to the right as model
size increases for open-sourced LLMs, indicating enhanced generalization capacity.
In Fig. and Fig. B we compute the perfor- mance gap between ID and OOD test data, and compare open-sourced and close-sourced mod- els across various sizes. We observe a right- ward shift of the critical complexity as models scale up in size. As shown in Fig. 7 larger mod- els, such as Llama-3. 1.mma-3.1140555. 1-00BB, handle more com- plex tasks before reaching their peak reliance on memorization. This suggests that increas- ing model size enhances the model's general- ization capacity, enabling better performance on harder tasks before overfitting to ID data be- comes dominant factor. However, even the largest models eventually reach critical complexity at very high task difficulties, suggesting that while scaling delays the reliance memorization, it does not entirely eliminate it. We also notice that GPT-4o-mini, despite having a smaller size than GPT-4o, exhibits a higher critical complexity (bottom-left in Fig. R) We hypothesize that GPT-4o-mini might have undergone more aggressive or sophisticated training on a high-quality dataset based on GPT-4o, leading to enhanced generalization capabilities at higher task complexities.
Acc, Gap between ID & 00D
Claude-3-Haiku
Claude-3-Sonnet
0.1-
0.1
0.0
GPT-4o-mini
GPT-4o
0.2
0.2
0.0
0.0
otMi
OWN NPD
Oln un
OIN N'))
(12%)
O(Ni
ouN, HPD
oun'? NoD)
anN' Nh
o12*)
Figure 8: Critical complexity shifts for closed- source models: Sonnet shows higher critical com- plexity than Haiku, while GPT-4o-mini deviates from this trend.
4.3 GENERALIZATION SCORE
Based on performance on ID and OOD data, we propose a new metric termed the General- ization Score (S). This metric is designed to reward models that perform well on OOD data while penalizing those that overfit to ID data. The generalization score is defined as: S = AOoD max (0, App - AOOD), where App represents the accuracy on ID) data, and AooD denotes the accuracy on OOD data. The score S ranges from -1 to 1, inclusive. The rationale behind this metric is twofold: 1) encouraging high OOD performance, where higher AooD indicates that the model can generalize learned skills to new, unseen data distributions, reflecting genuine rea- soning abilities rather than mere memorization. And 2) penalizing over-reliance on memorization: the term max (0, Ap - AooD) measures the performance gap between ID and OOD data. If the model performs significantly better on ID data than OOD data, this suggests reliance mem-
8

---

Published as a conference paper at ICLR 2025
orized patterns specific to the training distribution. An ideal LLM reasoner should achieve high accuracy on OOD data (AooD close to 1) and exhibit a minimal performance gap between ID and OOD data (Ai AOoD close to 0). This results in generalization score S approaching 1. Con- versely, a model that performs well on ID data but poorly on OOD data-indicating heavy reliance on ceamorization-wolle have larger performance gap, leading lower or even negative S.
4.4 BENCHMARK RESULTS
We evaluate 28 models across different families, versions, sizes, and expertise, including Qwen fam- ily (Qwen-1.5-1.8) 1BB.8////BBBB/11//2///B88 10B, 2- Qwen-2.5-3B/7B, Qwen-2.5- 5-Cdder- 7B, and Owen-2.5-Mathh-7B) LLaMA family (LLaMA-2-7B,, LLaMA-3-8B/70B, LLaMA-3.1- 8B/70B/405B, and LLaMA-3.2-3B). Gemma family (Gemma---22B99B222 GPT family (GPT-40, GPT-4o-mini, GPT-o1-mini), Claude family (Claude-3-Sommet/Haiau) and Mistral-7B-v0.33 Unless otherwise specified, all tested models are instruction-tuned models. We test each LLM and report their generalization scores in Table 2
The results demonstrate that closed-sourced models generally exhibit stronger generalization abili- ties and achieve higher critical complexity than their open-sourced counterparts. Notably, GPT-4o- mini and ol-mini are the only models that reach the critical complexity of O(2N), indicating their ability to handle a broad range of highly complex tasks. The ol ol-mini model, in particular, outper- forms all other models across every complexity class, achieving a perfect generalization score of on (NN) tasks and maintaining superior performance even in the most challenging O(2 category. Revisiting Fig. [ the performance gap curve for ol-mini remains almost flat when compared on the same scale as other models, indicating its exceptional generalization abilities across task complex- ities, with minimal dependence on memorization. More discussions and examples of how ol-mini reasons on SCYLLA's 's tasks can be found in Appendix
Among open- sourced models, Llama-3. 3.1--05B stands out with the strongest performance, achieving wear-perfect generalization scores of 0.997 and 0.996 on O(N) and O(N, N2) tasks, respectively, and exhibiting robust generalization up to O[N N4) complexity. This suggests that scaling open- source models, such as Llama, can significantly improve their generalization capabilities, approach- ing the performance of proprietary models at the higher end of the task complexity spectrum. Within 7B-9B models, Qwen-2.5-7B emerges as the top performer, with generalization scores of 0.617 and 0.632 for O(N) and O N2), respectively, and maintaining strong performance at higher com- plexity levels, with scores of 0.514 and 0.136 for tasks in the O I) and O([N3, ") ranges. This positions Qwen-2.5-77 7B as a leading contender for medium-scale open-sourced models capable of handling diverse levels of task complexity.
We also compare models fine-tuned for specific domains, such as math and code, against their base versions. Swee2.5--Mtt--7B and Bwwn2.5-Coder-7BB outperform the base Qwen2.5-7B on tasks of lower complexity (O(N) ) and O[N, N²))), but do not necessarily show improved results on tasks of higher complexity. This suggests that domain-speeific fine-tuning enhances a model's generalization within the complexity range it was originally effective in, but offers limited gains for tasks that exceed this range.
4.5 WITCH COMPLEXITY DOES AN LLM PREPER TO SOLVE TASK?
To further explore our benchmark, we designed a set of probe tasks to analyze the time complexity that different LLMs employ to solve these tasks. First, we constructed a mapping that correlates time complexity with OOD accu- racy. For this analysis, we used Llama-3-8B and Mistral- 7B as examples. Initially, we plotted the mapping, rep- resented by the black line in the graph. Next, we tested the accuracy of these two models on three probe tasks: longest common subarray (LCS), longest increasing sub- sequence (LIS), and longest consecutive elements (LCE). The results are shown in Fig. where green, yellow, and purple lines represent the accuracy for each task. By iden- tifying the intersection points between the accuracy re- sults and the mapping curves, we can infer the complexity of algorithms used by each L.M based on the corresponding x-coordinate of the intersection points.
LCS
US
LCE
Llama-3-88
Mistral-7B
1.0
0.8
0.6
0.4
0.2
own
004.8P))
onween NPI)
ORtN N5W
oun IDD ortw N71)
Figure 9: Illustration of correlations be- tween task complexity and OOD accu- racy for three probe tasks.

---

Published as a conference paper at ICLR 2025
Table 2: Generalization scores and critical complexities of 28 L.MS. The highest scores within each complexity range are highlighted in bold, and the escond-highes scores are underlined.
Model
O(N) O N21) D([N2,N9 O( ,ND) O(2*)
Critical Complexity
Open-sourced Models
Qwen
0.547
0.226
0.042
-0.009
0.018
O(N)
owen1.5-4B
0.631
0.173
0.094
0.061
0.007
O(N)
Qwen1.5-2 1.B
0.887
0.268
0.152
0.063
0.056
O .
Qwen .55114B
0.849
0.568
0.075
0,025
0.037
O(N, N
Qwen 3.32BB
0,969
0.521
0.137
0.102
0.045
O( N
Qwen .5-72B
0.911
0.825
0.115
+0027
0.01
O O N
Qwen I .5-1 10B
0.965
0.95
0.129
0.044
0.01 O N3 N
Qwen2-7B
0,986
0.824
0.065
0.081
0.019 O N2 N
Qwen2.5-3B
0.934
0.81
0,251
0.181
0.079 O N2 N
Qwen2.5-7B
0.617
0.632
0.514
0.122
0.136 O N N
Owen2.5-Math-
0,971
0.874
0.591
0.135
0.044 O N NN
Owen2.5-CCodr--1
0.969
0.832
0.205
-0.021
0.054 O NN N
Llama-2-7b
0.699
0.295
0.001
0.042
-0.051 O N. N
Llama- 3-8B
0.801
0.392
0,214
-0.005
0.044
O ON N
Llama-3-700
0.9
0.882
00.109
-0.218
-0.05 O N N
Llama-3. 3.1-B
0.667
0.603
0.047
0.025
-0.003 O N. N
Llama- 3.1-70B
0,982
0.89
+0.877
-0.233
-0.015
O N N
Llama-3 3. 14005B
0.997
0.996
0.847
0,516
0,262
O N N
Llama-3.22 3.2-3
0.827
0.247
-0.127
-0.079
0.051
OCN 2
Gemma-2-22
0.788
0.469
+0.994
0.021
0.05
O( N
Gemma-2-99
0.948
0.601
-0.124
-0.026
-0.065
O N N
Gemma-2-276
0.99
0.869
-0.1
-0.164
0.022
O O NO)
Mistral-7BB -B-ral-
0.949
0.558
-0.029
0.078
0.012
O No)
Closed Models
Claude-3-hait
0.984
0.844
0.019
-0.021
O(N2 No
Claude-3-sonnet
0.997
0.804
0.159
-0.056
0.07
O( No:
GPT-4o 0.997
0,992
0.787
0.457
0,238
O No)
GPT-4o-mini
0.974
0.989
0.768
0.517
-0.008
O(2
ol-mini
0.998
0.979
0,949
0.68
O(2")
Interestingly, the yellow and purple lines are nearly identical, indicating that both models use al- gorithms with similar time complexities. However, these two LLMs apply different time complex- ities when solving these two tasks. Mistral-7B uses a less efficient algorithm than Llama-3-8B, which is expected given Llama-3-8B's overall superior performance in benchmark (O(N2) O(N2, 2 For the "Longest Common Subarray" task, although the accuracy differs, the time complexity of the algorithms used by both models is relatively similar, around O([N, 22)). This suggests that either Mistral-7B performing better than its average, or Llama-3-8B is performing worse than expected.
CONCLUSION
In this work, we quantitatively study the generalization abilities of LLMs through the development and use of a novel evaluation framework, SCYLLA, which provides a scalable and dynamic eval- uation method disentangle generalization from memorization, allowing us to assess model per- formance across both ID and OOD data. Our findings highlight non-monotonic performance gap between ID and OOD data as task complexity increases, a phenomenon we refer to the general- izution valley. This behavior is indicative of the balance between memorization and generalization, which peaks at the critical complexity. As model size increases, the peak of this generalization valley shifts towards higher task complexity, demonstrating that larger models exhibit enhanced generalization capabilities before over-relying on memorization. Leveraging the insights provided by SCYLLA, conducted extensive benchmarking of 28 LLMs, both open-sourced and propri- etary, and more clearly show that larger models still face challenges with more complex tasks.
10

---

Published as a conference paper at ICLR 2025
ETHICS STATEMENT
We affirm our commitment to responsible and ethical conduct throughout the study. No human subjects were involved, and the datasets used were either publicly available or generated without personally identifiable information, avoid any kind of privacy invasion. All models we used are either open-sourced or accessible through APIs. We aim to minimize any negative social impact, including biases in model predictions. All methodologies followed best practices for transparency and reproducibility, adhering to standards of research integrity and legal compliance.
REFERENCES
Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ramasesh, Am- brose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length generalization in large language models. Advances in Neural Information Processing Systems, 35:38546-3888 38556, 2022.
Antonis Antoniades, Xinyi Wang. Yanai Elazar, Alfonso Amayuelas, Alon Albalak, Kexun Zhang, and William Yang Wang. Generalization vs memorization: Tracing language models' capabilities back to pretraining data. arXiv preprint 24XXi:2407.14983 2024.
Hritik Bansal, Arian Hosseini, Rishabh Agarwal, Vinh Tran, and Mehran Kazemi. Smaller, weaker, yet better: Training Ilm reasoners via compute-optimal sampling. arXiv preprint arXiv:2408. 16737, 2024.
Stella Biderman, Usvsn Prashanth, Lintang Sutawika, Hailey Schoelkopf, Quentin Anthony, Shivan- shu Purohit, and Edward Raff. Emergent and predictable memorization in large language models. Advances in Neural Information Processing Systems, 36, 2024.
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Ka- mar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint 223.::2303.12712, 2023.
Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models. arXiv preprint arXiv:2202. 07666, 2022.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint (tti::2077.03774 2021.
Zhaorun Chen, Yichao Du, Zichen Wen, Yiyang Zhou, Chenhang Cui, Zhenzhen Weng, Haoqin Tu, Chaoqi Wang, Zhengwei Tong, Qinglan Huang, et al. Mj-bench: is your multimodal reward model really a good judge for text-to-image generation? arXiv preprint arXiv:2407.044 044424 2024a.
Zhaorun Chen, Zhuokai Zhao, Zhihong Zhu, Ruiqi Zhang, Xiang Li, Bhiksha Raj, and Huaxiu Yao. Autoprm: Automating procedural supervision for multi-step reasoning via controllable question decomposition. arXiv preprint arXiv:2402.11452, 2024b.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 14168, 2021.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, Cambridge, MA, 3rd edition, 2009.
Yihong Dong. Xue Jiang. Huanyu Liu, Zhi Jin, and Ge Li. Generalization memorization: Data contamination and trustworthy evaluation for large language models. arXiv preprint 150.38802./5938. 2024.
Yanai Elazar, Akshita Bhagia, Ian Magnusson, Abhilasha Ravichander, Dustin Schwenk, Alane Suhr, Pete Walsh, Dirk Groeneveld, Luca Soldaini, Sameer Singh, et al. What's in my big data? arXiv preprint 2rXiv:2310.207077 2023.
11

---

Published as a conference paper at ICLR 2025
Lizhou Fan, Wenyue Hua, Lingyao Li, Haoyang Ling, Yongfeng Zhang, and Libby Hemphill. Nphardeval: Dynamic benchmark on reasoning ability of large language models via complex- ity classes. arXiv preprint arXiv:2312.14333 14890, 2023.
Shahriar Golchin and Mihai Surdeanu. Time travel in Ilms: Tracing data contamination large language models. arXiv preprint arXiv:2308.08449 2023.
Google. Gemini 1.5: Unlocking multimodal understanding across millions tokens of context.
arXiv preprint arXiv:2403.055300 2024.
Simeng Han, Hailey Schoelkopf, Yilun Zhao, Zhenting Qi, Martin Riddell, Wenfei Zhou, James Coady, David Peng, Yujie Qiao, Luke Benson, et al. Folio: Natural language reasoning with first-order logic. arXiv preprint arXiv:2209.00888 2022.
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Mcasuring massive multitask language understanding. arXiv preprint arXiv:2009.03300 030000 2020.
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song. and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. arXiv preprint arXiv:2103.03874, 2021.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Train- ing compute-optimal large language models. arXiv preprint
2022.
Berivan Isik, Natalia Ponomareva, Hussein Hazimeh, Dimitris Paparas, Sergei Vassilvitskii, and Sanmi Koyejo. Scaling laws for downstream task performance of large language models. arXiv preprint arXiv:2402.04177, 2024.
Subbarao Kambhampati. Can large language models reason and plan? Annals of the New York Academy of Sciences, 1534(1):15-18, 2024.
Nikhil Kandpal, Haikang Deng, Adam Roberts, Eric Wallace, and Colin Raffel. Large language models struggle to learn long-tail knowledge. In International Conference on Machine Learning, pp. 15696-15707. PMLR, 2023.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836/ 2020.
Mchran Kazemi, Quan Yuan, Deepti Bhatia, Najoung Kim, Xin Xu, Vaiva Imbrasaite, and Deepak Ramachandran. Boardgameqa: A dataset for natural language reasoning with contradictory information. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 39052-39074. Curran Associates, Inc., 2023. URL http:::/prrceeddngs..ee.e.ie httplpps.ccpppeeee cc/paper files/
Paper Datasets
and www.BBnncharrs..ck pdd
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 15:22199-222133 2022.
Sanae Lotfi, Mare Finzi, Yilun Kuang, Tim GJ Rudner, Micah Goldblum, and Andrew Gor- don Wilson. Non-vacuous generalization bounds for large language models. arXiv preprint arXiv:2312.17173 2023.
Inbal Magar and Roy Schwartz. Data contamination: From memorization to exploitation. arXiv preprint 22Xiv:2203.08222 2022a.
Inbal Magar and Roy Schwartz. Data contamination: From memorization to exploitation. arXiv preprint arXiv:2203.082. 2022b.
12

---

Published as a conference paper at ICLR 2025
Larisa Markeeva, Sean McLeish, Borja Ibarz, Wilfried Bounsi, Olga Kozlova, Alex Vitvitskyi, Charles Blundell, Tom Goldstein, Avi Schwarzschild, and Petar Veličković. The clrs-text al- gorithmic reasoning language benchmark. arXiv preprint arXhv:2406.0422 2024.
OpenAl. Gpt-4 technical report. arXiv preprint
08774, 2023.
OpenAl. Learning to reason with llms. https: /tpes////ppa...////// cwm.coomm........ ndex/ 2024. Accessed: 2024-09-30.
Searning-to-reason-
Zhenting Qi, Mingyuan Ma, Jiahang Xu, Li Lyna Zhang, Fan Yang, and Mao Yang. Mutual reason- ing makes smaller lims stronger problem-solvers arXiv preprint arXiv:2408.06199, 2024.
Yasaman Razeghi, Robert Logan IV, Matt Gardner, and Sameer Singh. Impact of pretraining term frequencies on few-shot reasoning. arXiv preprint arXiv:220..07006 2022.
Avi Schwarzschild, Zhili Feng, Pratyush Maini, Zachary C Lipton, and J Zico Kolter. Rethinking IIm memorization through the lens of adversarial compression. arXiv preprint arXiv:2404.1517 2024.
Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint 2xX1v:2408.03314. 2024.
Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonss al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. arXiv preprint arXiv:2206.044 04615, 2022.
Saurabh Srivastava, Anto PV, Shashank Menon, Ajay Sukumar, Alan Philipose, Stevin Prince, Sooraj Thomas, et al. Functional benchmarks for robust evaluation of reasoning performance, and the reasoning gap. arXiv preprint arXiv:2402. 2024.
Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoc Le, Ed H Chi, Denny Zhou, and Jason Wei. Challenging big- bench tasks and whether chain-of-thought can solve them. arXiv preprint arXiv:2210.0926.1 2022.
Xiaojuan Tang, Zilong Zheng, Jiaqi Li, Fanxu Meng, Song-Chun Zhu, Yitao Liang, and Muhan Zhang. Large language models are in-context semantic reasoners rather than symbolic reasoners. arXiv preprint arXiv:2305. Stt.:2305..4825.. 14825, 2023.
Michael Tänzer, Sebastian Ruder, and Marek Rei. Memorisation versus generalisation in pre-trained 2021.
language models. arXiv preprint
Petar Veličković. Adrià Puigdomènech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell, and Charles Blundell. The clrs algorithmic reasoning bench- mark. In International Conference on Machine Learning, pp.
PMLR, 2022.
Chaojie Wang, Yanchen Deng, Zhiyi Lv, Shuicheng Yan, and An Bo. Q#: Improving multi-step reasoning for 1lms with deliberative planning. arXiv preprint arXiv:2406. 2024.
Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yo- gatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. Emergent abilities of large language models. arxiv preprint arXiv:2206.0766 2022a.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837, 2022b.
Colin White, Samuel Dooley, Manley Roberts, Arka Pal, Ben Feuer, Siddhartha Jain, Ravid Shwartz- Ziv, Neel Jain, Khalid Saifullah, Siddartha Naidu, et al. Livebench: challenging, contamination- free Ilm benchmark. arXiv preprint arXiv:2406. /9314, 2024.
Zhaofeng Wu, Linlu Qiu, Alexis Ross, Ekin Akyürek, Boyuan Chen, Bailin Wang, Najoung Kim, Jacob Andreas, and Yoon Kim. Reasoning or reciting? exploring the capabilities and limitations of language models through counterfactual tasks. arXiv preprint (tt::2307.024777 2023.
13

---

Published as a conference paper at ICLR 2025
Xunjian Yin, Baizhou Huang, and Xiaojun Wan. Alcuna: Large language models meet new knowl- edge. arXiv preprint 0rXiv:2310.14820 2023.
Matej Zečević, Moritz Willig, Devendra Singh Dhami, and Kristian Kersting, Causal parrots: Large language models may talk causality but not causal. arXiv preprint arXiv:2308. /3067, 2023,
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115, 2021.
Yongchao Zhou, Uri Alon, Xinyun Chen, Xuezhi Wang. Rishabh Agarwal, and Denny Zhou. Trans- formers can achieve length generalization but not robustly. arXiv preprint arXiv:2402.09371, 2024.
Kaijie Zhu, Jiaao Chen, Jindong Wang, Neil Zhengiang Gong, Diyi Yang, and Xing Xie. Dyval: Graph-informed dynamic evaluation large language models. arXiv preprint arXiv:2309.17166 2023.
14

---

Published as a conference paper at ICLR 2025
APPENDIX
A ADDITIONAL RELATED WORK
A.I SCALING LAWS FOR LLMS
Scaling laws for LLMs have shown predictable improvements in performance models grow in size, data, and compute. Kaplan et al. (2020) established that model performance scales smoothly with these factors, following power-law relationships. Larger models are more efficient and require fewer samples to reach the same performance level, emphasizing the importance of scaling model size, data, and compute in tandem. |Hoffmann al. (2022) extended this by showing that many mod- els are undertrained relative to their size and should scale model size and data equally to optimize compute. They introduced Chinchilla, a smaller, compute-cfficient model that outperformed larger models like GPT-3 downstream tasks. Additionally, WWi et al. (2022a) explored the emergence of new abilities at larger scales, showing that some capabilities appear only after models surpass cer- tain thresholds. Isik et al. (2024) focused downstream performance, such translation, showing that scaling laws apply to transfer learning tasks but are highly sensitive to the alignment between pretraining and downstream datasets.
A.2 BENCHMARK COMPARISON
We compare SCYLLA with existing dynamic benchmarks for LLM reasoning across several key dimensions: 1) Scalability, 2) Knowledge Dependency, 3) Memorization Awareness, and 4) the Number of Tasks.
CLRS-text (Markeeva et al. 2024) demonstrates partial scalability, as does not explicitly orga- nize tasks by increasing complexity. Additionally, it evaluates LMs for ID and OOD performance by training them on traces of algorithm execution, a method that is often impractical for large-scale assessments.
Val (Zhu et al. 2023) and NVHardEval (Fan et al. 2023) increase task difficulty by extending problem length, introducing confounding factors. While NVHardEval explicitly categorizes tasks by complexity classes, both benchmarks offer limited insights into how LLMs handle varying levels of complexity with generalization abilities.
LiveBench (White al. 2024) is designed primarily for comprehensive evaluation of LLM capa- bilities, featuring many
intensive tasks such competition-level math problems and language comprehension tasks. As result, is not well-suited for testing reasoning abilities
alone.
Wu et al. (023) introduce tasks along with corresponding counterfactual tasks, enabling explicit evaluation of in-distribution (ID) and out-of ofitt--dist (OOD) performance. However, their framework does not address scalability in difficulty, and some tasks require significant domain knowledge to solve.
Table 3: Comparison of SCYLLA with existing dynamic benchmarks for LLM reasoning.
Benchmark
Scalability Knowledge Dependency Memorization Awareness
Number of Tasks
CLRS-text
half half half
low
half
30
Va
low
ZeTo
7
NvHardEval
low high medium
zero
9
LiveBench
zemo
7Cro
18
Wu et al. (2023)
zero
full
Scylla (Ours)
full
low
full
20
B VALIDATION OF ID/OOD DATA GENERATION
To demonstrate that our approximation of ID/OOD data both reasonable and meaningful, we use OL Mo-Mo7BB Instrruct as example to examine how the ID/OOD data obtained overlaps with the
15

---

Published as a conference paper at ICLR 2025
training data (i.e., genuine ID data). OLMo is open-sourced LM trained on the Dolma and Tulu datasets. With the tool WIMBD (What's ss In My Big Data) Elazar et al. 2023). we were able to count the occurrences of each ID and OOD example within the two training datasets of OLMo. We ran the data generation pipeline using OLMo and counted the ID and OOD examples obtained in Dolma and Tulu across 17 anchor tasks. We then calculated the average occurrences of examples for each task, and the results are presented in the table below.
in Dolma
Tal
Dolma Tule
in Dolma
O.D Talu
OOD Dolnu Tulu
FindMode
$214.58
5,8375
5220,4175
154,5773
1,3801
TweSum
31609 2667
19.1446
31628.4115
PeurSumMuutiplleen
128,3338
9.1145
137.4479
6.52e 05
6.52c 05
RemoveDoliccueuumbrrr
53715.7647
74,2690
53790.0337
L8235
0.0106
18832
Hipk
4293.4
8,5762
4301,7662
0
ThroeSum
515.1
6.5652
521. 361.6662
FourSum
14,5031
19.5031
FindMinimum
299740.0811
26.8876
299766.9687
ThraeSumloRang
293.4615
6.8534
300.3149
FourSuminRaage
3453,44
50,0364
3503.4764
0
SertNumbers
79879.9512
32,2312
79912,1724
ThreSSumMuliilleee
1300.4286
2,0165
1302.4751
0
SubserSamluRange
$2342.39
9,970
32382.3670
HindMasiimuu
311014.89
27.1009
311041.99.99
0
SubverSumMelipleeee
Avg
Table 4: Summary of ID and OOD statistics for tasks across Dolma and Tulu datasets.
From the results, it is evident that for each of the 17 anchor tasks and across both training datasets (Dolma and Tulu), the occurrence ID examples far exceeds that OOD examples. Specifically, nearly all OOD example occurrences RRemooeeDuliicateeunteee
zero, except for the tasks "FourSumMuutipleTTen and In contrast, the occurrence ID examples ranges from thousands to tens of thousands, highlighting substantial disparity the overlap of examples with the training data. These findings support the validity and meaningfulness of our method for formulating ID and OOD examples.
C IMPLEMENTATION DETAILS
C.I TASK TITLES, DESCRIPTIONS, AND ANSWER FORMATS
In Table we detail the 20 tasks in SCYLLA, including their titles, descriptions, and example inputs. This information will be used to construct prompts to evaluate LLMs (more details in the next section, C.2
16

---

Published as a conference paper at ICLR 2025
Task
Title
Description
Example Inpot
Find Minimum
linding minimon
Given a list of numbers seporated by spaces, find
48 85 41
the smallest number.
Find Maximum
linding maximum
Given a list of numbers separated by spaces, find
74 29 63 40 88
the lagest number.
Find Mode
linding mode
Given a list of numbers separated by spaces, find the mode of
9.17 21/259925 9.17
numbers,
Find TopK
linding top k
Given a list of numbers separated by spaces and positive integer find krth largest number. Given list of numbers separated by spaces and target value k. find two numbers in the list add up to the target value.
1= 100 90 80 70 60 50, 3
Two Sum
linding two numbers adding up to speeific sum
1= 29 4:
Numbers
sorting numbers
Given list of numbers separated spaces, 183174115477
the numbers in asccnding order.
Remove Duplicate Num-
removing, duplicate numbers
Given a
numbers separated by spaces, move duplicatc numbers so that every number ap- pears only
81245 78 23
bers
and ourput the remaining num- bers in their original order.
Three Sum Multiple Ten
finding three numbers adding up to be maltiple of 10
Given list of numbers separated spaces, find three numbers in the list that add up to be a multi- ple
73 2477242873344
Three Sum In Range
finding there numbers adding up
Given list of numbers separated by spaces and
1= 1= 32,
be specific range
numbers and find three numbers in the
list that add to value that is in the range (a, 6).
Three Sum
finding there numbers adding up a specific sum
Given list of numbers separated by spaces and a target value find three numbers the list add up to the target value.
1 30 000000445400 90 15, 105
Four Multiple
finding numbers adding up
Given list numbers sepurated by spuces, four numbers in the list that add up to be a multiplc
14 16:25
to be maltiple of 10
Four Sum In Range
finding four numbers adding up
Given a list of numbers separated by spaces and
= 30-45 60 75 105 120,
be a specific range
two numbers
four numbers the list
-300, 360
that add up to value that is in the range (a, b). Given list numbers sepurated by spaces a larget value k. find four numbers in the list that add up
Four
finding numbers adding up to specific sum
28 33,
target value.
Subset Ten
Sum Multiple
finding a subset adding up to be multiple
Given a list of numbers scparated by spaces, find
2.888.22 28 38
a subset 10.
that adds up to be multiple
Subset Sum Runge
finding a subset adding up be in specific range
Given list of numbers separated by spaces
29
two numbers a and b. lind subsct in the list that up value that
43
51,
52,
52,
5:
range (a, 6).
Subset Sum
finding the subset of numbers adding up specific sum
Given a list of numbers separated by spaces and list
=
14
20
26
22 44.50
a target value R. that add up to the target value. Given each pair of cities, your goal is to find the shoetest
numbers
Traveling Salesman Problem (TSP)
of cities
the distances between
D [10, 12, 18,
301,12, 0, 15, 22, 201112, 15.
path visits every city once returns to
28. 351,118.
171130.
starting city. The inputs include 1) n: the num- her of cities;
20,35, 17,
an adjacency matrix x r. where Diy is the distance between city and city j. The cotput should representing the order of cities to visät. The cities are indexed from to n 1. City is always the starting city.
list of integers
Longest Consecutive ements
finding the longest consecutive clements
Given u tum the longest consecutive number sequence in ascending order. consecutive sequence is quence of numbers where each number is exactly greater the previous number.
numbers sepurated by spaces, re-
46
Longest Increasing Sub- sequence
finding the longest increasing subsequence
Given a list of numbers separated by spaces, re- tum the longest strictly increusing subsequence. A subsequence is a list that can be derived from another list by deleting some no elements with- out changing the order of the remaining elements.
243517680
Longest array
Common Sub-
finding longest common sub- aray
Given integer arrays 1 1z. return I 21 l2 14 28 longest common subarray that appears in both ar- mays. suburay is contiguous sequence num-
35
bers within an aray..
Table 5: More details of tasks: Titles, descriptions, and example inputs.
17

---

Published as a conference paper at ICLR 2025
C.2 PROMPTS
For the first part of the data synthesis pipeline, we prompt the LLM to generate test inputs for given task. We the following prompt templates for each task type:
Prompt Template 1. Generate Number Lists
Randomly generate number lists test inputs for testing a program written for the task of [task_title). The task description is: beaskddescrittion. Enclose each number list by square brackets, e.g. [xl, x2, x3, x4]. Do not generate the corresponding output. Do not use generate any code. Make sure that the number elements are non-negative integers. Make sure that the number lists are not empty and not too long. Now please generate many such number lists as possible:
Prompt Template Generate Number List Pairs
Randomly generate pairs of number lists as test inputs for testing program written for the task of [task_title). title). The task description is: {task description). Enclose each of the two number list
by square brackets and put them in another list, e.g. [[x1, x2]. [x3, x4]]- Do not generate the corresponding output. Do not use or generate any code. Make sure that the number elements non-negative integers. Make sure that the number lists not empty and not too long. Now please generate as many such pairs number lists as possible:
Prompt Template 3. Generate Matrices
Randomly generate some adjacency matrices as test inputs for testing program written for the task of solving the task of [task_title). The task description is: {task .escriiisii)t Enclose each adjacency matrix by square brackets. Make sure the matrix is symmetric, and each element should non-negative integer. For example, [[O, x1, x2, x3), [x1, O, x4, x5], [x2, x4, 0, x6), [x3, x5, x6, O]] is a valid adjacency matrix. Do not generate the corresponding output. Do not use or generate any code. Make sure that the adjacency matrices have length larger than 3 but not too large. Now please generate many such adjacency matrices possible:
To ask for LLMs' solutions, use the following prompt template (Kojima al. 2022)
Prompt Template Zero-shot Chain-of of- ofl--oo-Tooh Thought Prompting
{instruction). Solve the task with the following input: {input). IM- PORTANT: End your response with "The answer is <ANSWER>" where you should fill <ANSWER> with your final answer and must format the final answer obeying the following rules: (armwtr.format requiremntt Your response: Let's think step by step.
Here is a task:
D DETAILS OF DIFFERENT COMPLEXITY TASKS
The anchor tasks are selected for the formulation of our benchmark. Therefore, they would have only one solution of two solutions with adjacent time complexities. The following detailed information about these tasks, arranged by their time complexity.
D.1 O(N)
Find Minimum. The task Find Minimum to find the minimum in the given list of numbers. requires looping over all the numbers in the list. To be specific, can set a flag number when looping over It is set as the first number at the very beginning. Once a number smaller than the flag number, it would be replaced. Then the final flag number after looping over the entire list would the result,Therefii Therefore, the time complexity would be O(N).
Find Maximum. The task Find Maximum is to find the maximum in the given list of numbers. The solution would be similar the previous task. The difference is when conducting the
18

---

Published as a conference paper at ICLR 2025
placement of the flag number, the current number should be bigger than the flag number. The time complexity would be O(N).
Find Mode. The task Find Mode is to find the mode in the given list numbers. The solution requires looping over the numbers. It requires dictionary when looping over the numbers. When it loops through a number, the count of the number would be added by one. After looping. it takes ((1) time to conduct the search to find the mode. The time complexity would be O(N).
D.2 N(I,,
Find Topk. The task Find Topk is to find the 1tth largest number in the given list of unsorted numbers. The method with the worst time complexity would be first conducting sorting. The time complexity would vary between O(N2) and O(N) based on the time complexity of the sorting algorithm. Then it would take O(1) time to look up the kth largest number in the sorted list.The time complexity would be O(N2). The method with the best time complexity is to use the quickselect algorithm. partitions the array around pivot recursively. Numbers that are smaller than the pivot go one side, and elements larger go to the other. If the pivot number is the kth largest number, the recursion ends, and we get the output. The time complexity of this method ((N).
Sort Numbers. The task Sort Numbers is to sort the given list of numbers. It is one of the most popular tasks among all the coding tasks. The time complexity varies from (NN) to O(N2) based on the algorithm. For example, bubble sort would have time complexity as O(N2). Merge sort would have time complexity as O(N log N). Counting sort would have time complexity of (NN.
Two Sum. The task Two Sum to find two numbers that add up to be a given number. The worst solution is to conduct all the permutations. In other words, it would require two loops to loop over all the possible outputs. Therefore, the worst time complexity of this task is O(N2). Besides, the solution with the best time complexity would be using hash table to look up and find the last number of the solution. Specifically, we will create hash table (or dictionary) to store numbers in the list, which takes O(N) time. Then by conducting permutations with one loop, would get all the possible answers without the last number, in other words, the complement as target-the one number. Since it takes only (11) time to check the dictionary, the time complexity would be O(N).
Remove Duplicate Numbers. The task Remove Duplicate Number is to remove the duplicate numbers in the given list of numbers. The time complexity would range from O(N) to O(N²). The method with the worst time complexity is to conduct the brute-force approach. It involves checking each element of the list against every other element see if a duplicate exists. This leads to O(N)) time complexity since it requires two nested loops. The method with the best time complexity is to use hash table. To remove duplicates efficiently, iterate through the list, adding each element to a set, which automatically discards duplicates. Then, convert the set back to a list. The time complexity would be O(N).
D.3 ([N2,N*)
Three Sum Multiple Ten. The task Three Sum Multiple Ten is to find three numbers whose sum is multiple of ten. The worst solution is to conduct all the permutations. In other words, it would require three loops to loop over all the possible outputs and test whether their sum in the given range. Therefore, the worst time complexity of this task is O(V3). The best time complexity solution is realized by building the hash table (dictionary), conducting permutations with two loop, and referring to the hash table. Specifically, would conduct the hash table based on the remainder of these numbers when divided by ten. Therefore, it would have the same time complexity as O(N2).
Three Sum In Range. The task category Three Sum In Range is to find three numbers whose sum is in a specific range. The worst solution is to conduct all the permutations. In other words, it would require three loops to loop over all the possible outputs and test whether their is in the given range. Therefore, the worst time complexity of this task is O(V3). The best time complexity algorithm is realized by building the hash table (dictionary), conducting permutations
19

---

Published as a conference paper at ICLR 2025
with N-1 loop, and referring the hash table. Therefore, it would have the same time complexity as O(N3).
Three Sum. The task Three Sum to find three numbers that add up be a given number. The worst solution is to conduct all the permutations. In other words, it would require three loops to loop over all the possible outputs. Therefore, the worst time complexity of this task is O(N3). Besides, the solution with the best time complexity would be using hash table to look up and find the last number of the solution. Specifically, we will create a hash table (or dictionary) to store numbers in the list, which takes O(N2) time. Then by conducting permutations with one loop, we would get all the possible answers without the last number, in other words, the complement as target-the number. Since it takes only O(1) time to check the dictionary, the time complexity would be O
D.4 O[ (N
Four Sum Multiple Ten. The task Four Sum Multiple Ten is to find four numbers whose sum is a multiple of ten. The worst solution is to conduct all the permutations. In other words, it would require four loops to loop over all the possible outputs and test whether their sum is in the given range. Therefore, the worst time complexity of this task is O(N*). It is realized by building the hash table (dictionary), conducting permutations with three loops, and referring to the hash table. Specifically, we would conduct the hash table based on the remainder of these numbers when divided by ten. Therefore, it would have the same time complexity as O(N3).
Four Sum In Range. The task Four Sum In Range is to find four numbers whose sum is in a specific range. The worst solution is to conduct all the permutations. In other words, it would require four loops to loop over all the possible outputs and test whether their sum is in the given range. Therefore, the worst time complexity of this task is O(N4). The best time complexity algorithm is realized by building the hash table (dictionary), conducting permutations with three loop, and referring to the hash table. Therefore, it would have the same time complexity as ((V3).
Four Sum. The task Four Sum is find four numbers that add up be given number. The worst solution is to conduct all the permutations. In other words, it would require four loops to loop over all the possible outputs. Therefore, the worst time complexity of this task is O(N*). Besides, the solution with the best time complexity would be using a hash table to look up and find the last number of the solution. Specifically, we will create a hash table (or dictionary) to store numbers in the list, which takes ((N3) time. Then by conducting permutations with one loop, we would get all the possible answers without the last number, in other words, the complement as target-the one number. Since it takes only ((1) time to check the dictionary, the time complexity would be (
D.5 0(2^)
Subset Sum Multiple Ten. The task Subset Sum Multiple Ten to find subset whose sum is a multiple of ten. The solution is to conduct all the permutations. In other words, it would require iterating through all the subsets and check whether its sum multiple of ten. Therefore, the time complexity is (22
Subset Sum In Range. The task Subset Sum In range is to find a subset whose sum is the given range. The solution is to conduct all the permutations. In other words, it would require iterating through all the subsets and check whether its sum is in the target range. Therefore, the time complexity is O(2
Subset Sum. The task Subset Sum is to find subset whose sum is the target sum. sum.The solution is to conduct all the permutations. In other words, it would require iterating through all the subsets and check whether its sum is the target sum. Therefore, the time complexity is ((2
TSP. The task TSP is the famous hP-hard task. The task is to find the shortest route for a salesman to visit each city exactly once and return to the starting city, given n vertices and (n(n-) /2 distances between each two of them. The time complexity of this task is O(2N). The method is to generate all the possible routes that cross all the cities and count the distance of these routes. By comparing them, we get the final answers. The time complexity would be O(2N).
20

---

Published as a conference paper at ICLR 2025
D.6 PROBE TASKS
As discussed in section 4.5, we set some probing tasks that have several different methods with different time complexities.
Longest Increasing Subsequence. The task Longest Increasing Subsequence is to find the longest contiguous increasing subarrays given list of numbers. The time complexity of these methods ranges from ONN log N) to O(2*). ). The worst time complexity approach is a brute-force approach. It involves checking all possible subsequences of the lists. Indeed, it is checking all the subsets of the list. Therefore, the time complexity would be 0(2*). The best time complexity approach is realized by using Binary Search with Dynamic Programming (DP). We first use a dynamic array to store the smallest possible tail of increasing subsequences of different lengths. Additionally, we create an array prev of size n, initialized to -1, to store predecessor indices. For each element nums [i], we use binary search to find the appropriate position in dp where this element should go. If the element is larger than any element in dp, it will be appended. If can replace an element in dp, replace the smallest element that is greater than or equal to it. Update the prev array. If nums [i] extends a subsequence, record the predecessor in prev. After processing all elements, the length of dp gives the length of the LIS. Trace back the sequence using the prev array, starting from the last element of the LIS. Reverse the sequence, as is reconstructed from the end to the beginning. For each binary search, it takes Ollog N) time and there are N elements in the array. Therefore, the overall time complexity would be O N log N).
Longest Common Subarrays. The task Longest Common Subarrays is to find the longest contigu- ous subarrays of two given arrays. The time complexity would range from O(N2) ) to O(2*). The worst time complexity is realized by the brute-force approach. It done by checking all possible subarrays of the two given arrays. For each array, it has 2 subarrays if the LLM cannot distinguish whether it is contiguous. Therefore, the time complexity of matching these subarrays one by one requires O22 time.
The best time complexity approach is using dynamic programming. We define a 2D array dp with dimensions (m + 1) x (n + 1), where each entry dp [i] [j] represents the "LCS" length be- tween the prefixes text 1 [0] and text2 [0]. We set dp [0] [il 0 for all 0 S j S n and dp [i] [0] = 0 for all 0 < i < m. For the remaining cases where i >> 0 and j > 0, we use the following recurrence relations: the characters at the current positions match, i.e., text1 [i-1]
text2 [i-1], the LCS length is dp [i-1] [j-1] + 1. as we include this matching character in the subsequence. If the characters do not match, i.e., textl[i-1]
* text2 [-1],, we take the maximum L.C length by either excluding the character from text1 or text2, so dp [ [j] max (dp [ [111] [i], dp [i] [j-1]). After filling the table, the value dp [m] [n] will con- tain the length of the Therrforr,,,,, the time complexity would be ((N2) because it loops through the whole 2D array, which has a size of N2.
Longest Consecutive Elements. The task Longest Consecutive Elements is to find the longest consecutive sequence in the given array. The time complexity ranges from O(N) to O(2*). The approach with the worst time complexity would be the brute-force method, where we find all subsets of the array and identify the longest consecutive subsequence. Its time complexity is O(2 The approach with the best time complexity uses a hashing function. It checks whether N+1, N+2, and so on, exist in the array for all the numbers in the array. By optimizing the search to avoid checking starting points where N-1 1 exists, the algorithm ensures each number is processed once, resulting in an overall time complexity of O(N).
E ADDITIONAL RESULTS: FEWSHOT PROMPTING
We conducted additional experiments to explore whether using fewshot-cot prompting affects findings. We use Gemma-2-22 2-2--a--2B-IIsiiiee Instrust as the testee LLM, and use 3-shot CoT examples that are obtained from Gemma's 's correct solutions and are excluded from the test set. Each task has its unique 3 shot examples. The results are summarized in the table below.
Key insights include:
21

---

Published as a conference paper at ICLR 2025
Metric
(
O( 10--NT N2))
O N
O N
O(2
zeroshot-cot ID acc 0.928385
0.699227
0.313481
0.120916
0.094084
fewshot-cot ID acc 0.989583
0.688128
0.376901
0.169025
0.112932
zeroshot-cot OOD ace 0.858073
0.601736
0.116127
0.050155
0.072648
fewshot-cot OOD acc 0.927083
0.595475
0.214492
0.060678
0.086146
zeroshot-cot acc gap fewshot-cot acc gap
0.070312
0.132647 0.092773
0.209727 0.162409
0.070761
0.022633
0.065104
0.
0.026786
Table 6: Performance metrics across complexity classes for zeroshot and fewshot chain-of-thouu (cot) using I-2t-t-ruut
Fewshot-cot prompting does improve performance across both ID and OOD datasets com- pared to zeroshot-cot prompting. This is especially evident in lower-complexity tasks (c.g., (N) and O[[N - -N²))).
2. While fewshot-cot generally reduces the accuracy gap between IDD and OOD tests, the peak performance gap remains significant, particularly for intermediate complexity tasks (c.g.,
O 2)))).
3. Even with fewshot prompting. the generalization valley phenomenon persists, and the criti- cal complexity still remains the same complexity level compared zeroshot prompting.
These additional experiments show that few-shot cot prompting can enhance performance, partic- ularly for datasets, but the core phenomena observed in our study-such as the generalization valley and critical complexity-remade robust. Therefore, while prompt techniques like few-shot prompting can modulate performance, they do not fundamentally alter the underlying generaliza- tion patterns of the models, revealed by SCYLLA.
F A GLIMPSE OF HOW 01-MINI DOES REASONING
Given the strong performance of ol-mini, we are interested to see how ol-mini manages to solve hard tasks even with OOD data, In this section, we look into the outputs of o1-mini when given hard problems.
In comparing how ol-mini and Llama-3. 1-40BB solve the problem of finding the longest increasing subsequence (Fig. [Q). ol-mini exhibits a more streamlined and intuitive approach. ol-mini starts by checking each number sequentially, quickly forming a subsequence, and then making necessary adjustments when the increasing order is broken. Its solution process is straightforward and efficient, leading to the correct result with minimal overhead. On the other hand, Llama-3. applies a dynamic programming algorithm, constructing arrays to track subsequence lengths and then backtracking to identify the correct sequence, which is correct but unnecessary for such a simple input. While both models produce the correct answer, ol-mini's method demonstrates stronger generalization and efficiency, solving the problem without requiring the more detailed intermediate steps employed by 1lama-3.1. This highlights ol-mini's superior ability to handle the task with fewer computational resources and reduced reliance on more structured, algorithmic approaches.
One notable feature of the ol-mini (OpenAl 2024) is its ability perform implicit complex rea- soning through what can be termed "reasoning tokens". We test o1-mini on the task of Subsetsum and TSP (Fig. [T]. From its output, we observe two types of implicit reasoning. Type 1: ol-mini directly generates correct answers with minimal explanation or intermediate steps. For example, in the Subset Sum task, oi-mini able to quickly identify subsets that satisfy the target sum with no explicit reasoning chain provided. Type 2: ol-mini produces more elaborate reasoning steps, but leaves out important intermediate steps. In TSP, ol-mini provides a clearer explanation of its thought process, including steps like evaluating possible routes, but the most critical parts of the reasoning-aa such as how it prioritizes routes or recognizes patterns still occur implicitly, without being explicitly outlined in the output.
Since ol-mini conceals its reasoning process, it is difficult to observe exactly how it arrives at so- lutions. We hypothesize that its strong generalization ability stems from advanced training tech-
22

---

Published as a conference paper at ICLR 2025
Task Description of of LonnesstiooeeeiinggSuueeueeeee Given a list numbers separated by spaces, return the longest strictly increasing subsequence. A subsequence list that can derived from another list by deleting some or no elements without changing the order remaining elements.
Liama-3. 3.1-00BBB
Input: 7015 2930 9379 2135 4033 7591
dynemic programming, The idea to maintain army where each element represents the length the longest incressing subsequance anding at position. AntoHane's a step-hy-stag solutionvviiet. Initialiss an amay dp
Output: To solve this task,
same langth the input list, with elements sot to 1. This because a single alament is always an increasing sutaequenca of langht 1.5tt22 intiaaize an aray prav'' to keep track of the previous etementi in the longest increasing subsequence ending each position. inin3. Iterate over the Input list. For each element, compare it with all prodius
alament greater clement.wwin4, the surrant slement can extand the acreasing subsequence anding pravious siement, and langth the rasuiting subsequance gneater than the current longest increasing subsequence ending at the current position, updete dp and prev' accorcingly/vlie, After tteating over the entire Ust, find the position wich the maximum value in cp This the end the longest increasing subsequence Antn. Use the prev arry to subsequence backtracking tusinAtter applying the algorithm, we gotimindp::11, 1,2, 4j [41,11
provioua
potentially
incressing subsequanci anding
reconstruct longest
with meximum
AnlnNoww aaply algarithm
given inttiintt 7015 9879 2133 maximum value in dp is which at the last position. Basktracking from this position using" prev we getinin72811 >s 4033 2135 > 28001ninSo, the longest stricily increasing subsequence is [2930, 2135 not valid as 2135 < 2800, so 2930 >a 4003 >a 7581 and also 7015 -> 6079 another increasing innltthhee
4jvavnhhe
subsequence, longest
[2930, 7591) (correct)
Input: 9722 3098 7007 4981 1976 5899 6356
Output: Given
of numbers:
1976, 5809, 6356,
find longest stricily incmesing subsequanca *Starrt
with the first number:" 9722tn -Nett number is 3098, which less than 9722, So, we can't include 3090 in the increasing subsequence starting
9722 Anlen. **Start with the second number: 30086n Next number is 2007, which greater than 3086. So, we include 2007 - -Nett number is 4561,
which than 7007. So,
include 4901,in number 1976, which is less than 7007.in Next number 5899, which greater than 7007. 6356,
3090, 7007, 5698, 6358kviis3 "Howwerr notiow that 5800 is less than 7007, which breaks the incressing order:" Therefors, we need adjust our subeequenca.o In Vn
5899
greater than 5839, we
6356.'n
subsrquence
Starting again from 3058dn -3088- -> 4981 5600 -s 63586nin This saquencs is strictly incmasing Intavé "Chhcck if then's as longer aubsaquencss
Starting 1978: 1976, 5899, 6356mn This shorter than the previous subsequence intnnherefore, the longeest increasing subsequence [2050,
6356) /oine The
(309e, 4981, 5800, 6356)** (cormct)
Figure 10: Comparison between ol-mini and Llama-3.1 1-40BB in solving the longest increasing subsequence problem. ol-mini demonstrates more direct and efficient approach, adjusting the sequence dynamically with minimal steps, while Llama-3.1 employs a complex dynamic program- ming method involving array tracking and backtracking to reach the solution.
Task Description of SubsetSum: Given list of numbers $1S separated by spaces and a target value $K$, find set of numbers in the list that add up to the target value.
[Implicit Reasoning Type (-35 of 256 instances)
Input: SIS- 4331 7679 6499 6300 1993 4301 7760, Sk$ 18304
Output: The answer (7679, 4331, 4301, 1993). (correct)
[Implicit Reasoning Type 2] (-15 out of 256 instances)
Imput: SIş = 3516 9902 8014 3841 3917 5729, $*$ = 21100
Output: We need to find subset of the numbers [3516, 9902, 8014, 3841, 5729]' that sums to 211100 AninAfter evaluating different combinations, the following set adds up the target value:Inin- *13516* 8014 3841 5729 21100 WjininThe answer is
-0014""in "3841"" "552g***onn"CCaccuuaainnono""
[3516, 8014, 3841, 5729). (correct)
Task Description of TSP: Given a of cities and the distances between each pair of cities, your task is to find the shortest path that visits every city once and returss the starting city. The inputs include 1) Sn$: the number cities; 2) SD$: adjacency matrix of size Sn Vitimes n& where $D liJS is the distance between city $:5 and city Sjš.
[Implicit Reasoning Type (-25 out of 256 instances)
Input: $n$ 5, $n$ wnw.hh/iiiigggnnemmneeeooo & 588 & 248 308 529 WWV6686 & & 981 & 717 484 Wil62448 & 981 O.O. 903 & 303 WiNn308 717 993 & 399399991 Win329 404 390 399 & (inteendiimmttiiejnnn
Output: The answer is [0, 2, 4, 1, 0]. (correct)
[implicit Reasoning Type 2) (-50 out of 256 instances)
Input: $nž 6, $D$ snntte/lboognteeeeeeseeo 994 139 786 & 469 WWW18844 & 736 983 471 WiNn119 & 70033330000 453 247 WiNn786 & 983 455 0 712 WWwvee 471 & 247 & 712 [wwteeddeemarrrquuu
Output: To solve the Traveling Salesman Problem (TSP) for the given input with cities, we evoluate all possible routes that start and other cities (1, 3, 3), identify the route the shortest distance AninAfter evalusting all 24 possible permutations, the shortest routes found are:/min1. *"oute** 20, 3, 1, 0J in *Total Distance**: 2515mmin2. "Route"": [0, 2, 0J TToal Distance 25151n/nBoth routes have same minimal total distance of 2515. For consistency, we'll present the first route Inkadd answer [0, 2, 0). (correct)
end city 0. calculating the total distance each permutation
Figure 11: Evaluation of o1-mini on OOD data for SubsetSum and TSP tasks. The model exhibits two distinct types of implicit reasoning, each occurring in significant portion of cases.
nique that allows the model to allocate large number of extra tokens for complex reasoning before producing the final response.
23


Reviews:
[{"review_id": "XrpXrSvZge", "reviewer": "Reviewer_r2Jo", "summary": "This paper introduces SCYLLA, a framework for evaluating LLMs' generalization abilities across different task complexities. The key findings include:\n\n- Discovery of a \"generalization valley\" - a non-monotonic relationship between task complexity and the performance gap between in-distribution (ID) and out-of-distribution (OOD) data\n- Observation that larger models can handle more complex tasks before reaching their critical complexity - the point where models rely most heavily on memorization\n- Benchmark results comparing 28 LLMs, showing closed-source models generally perform better at generalization", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Novel evaluation framework that considers both complexity scaling, generalization, and memorization.\n2. Comprehensive evaluation across many modern LLMs\n3. Clear methodology for testing generalization capabilities\n4. Interesting findings about model scaling and complexity relationships", "weaknesses": "1. ID/OOD Definition Issues (Major Issue):\n\n\nThe paper's method of determining ID data by asking the model to generate examples could be problematic\nBy using model-generated examples to determine what constitutes ID data and simply using complementary numbers for OOD, the paper creates a potentially circular and oversimplified definition of distribution shifts. This approach lacks validation against actual training distributions and may not capture meaningful distribution shifts. \n\n2. Other Issues:\n\n\n- Limited task types (mostly focused on numerical/algorithmic tasks)\n- No ablation studies on different prompt formats or chain-of-thought methods", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aagfYRa9In", "reviewer": "Reviewer_ZwYr", "summary": "This paper presents an analysis of the generalization abilities of LLMs. To conduct this analysis, they have created a framework, SCYLLA, composed of tasks with different levels of algorithmic complexity. They use this framework to quantify the balance between generalization and memorization in LLMs, by comparing the results on in-distribution and out-of-distribution samples. From the accuracy difference of the two, they conclude that there exists a generalization valley and a critical complexity in the modes. They present a Generalization Score to measure this phenomenon. Finally, they use probe tasks to analyze the complexity that LLMs use to solve these problems.", "questions": "In general it is a great paper and you have performed a great analysis from the results obtained. I have the following questions from the paper: \n\n- When creating the OOD sample, do you create 1 for each family of models or 1 for every single model? I do not think this is made clear in the paper. \n- What is the reason to select only problems that require numbers? Could it not be easily added some problem on string manipulation with a very similar strategy?\n- What is the takeaway for the gray line in Figure 9, is the goal to present how the OOD accuracy is reduced as the complexity increases? I think this is not highlighted in this case.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- New Evaluation Framework (SCYLLA). They present a new evaluation framework that can be used to measure to evaluate the generalization performance of LLMs. \n- They uncover and measure the Generalization Valley Phenomenon. According to the experiments conducted on several models, there seems to be a consistent gap between their ID and OOD evaluations. And this gap has a peak (critical complexity) that shifts to the right as model size increases in open-source models. \n-  They conduct a large set of experiments and evaluate a good amount of well-known models.", "weaknesses": "- Dependence on approximate ID data. Due to the inability to access pre-training data, it is hard to estimate in-distribution data. The approach presented is a workaround that only focuses in the number generation. They do not present the estimated distribution for the models and their difference with their out-of-distribution data. \n- As far as I understand, they focus on tasks that require mathematical operations. They do not show a possible generalization to other kind of tasks. Adding other type of tasks could have benefitted the overall quality of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "15pR2XRkcl", "reviewer": "Reviewer_pHuD", "summary": "The paper introduces a novel evaluation framework, SCYLLA, designed to assess the generalization capabilities of large language models (LLMs) across varying task complexities. The framework is scalable, dynamic, knowledge-light, and memorization-aware, addressing limitations of existing evaluation methods. \nThrough extensive experiments on 20 tasks across 5 complexity levels, the authors identify a non-monotonic relationship between task complexity and the performance gap between in-distribution (ID) and out-of-distribution (OOD) data, termed the \"generalization valley.\" \nThis reveals a critical complexity threshold where reliance on non-generalizable behavior peaks, indicating the upper bound of LLMs' generalization capabilities. The study shows that as model size increases, this critical complexity shifts to higher task complexities, suggesting larger models can handle more complex tasks before over-relying on memorization. The paper benchmarks 28 LLMs, including both open-sourced and closed-sourced models, providing a robust evaluation and deeper understanding of LLMs' generalization abilities. Additionally, a new metric is proposed to reward models with strong OOD generalization and penalize overfitting to ID data.", "questions": "See weaknesses", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The idea that the evaluation dataset should be generated dynamically is interesting and can be useful for promoting the accuracy of the evaluation. \n- The performance gap between ID and OOD data is also an interesting and novel indicator.", "weaknesses": "- The paragraph of Line 300 is not very clear. \"From these generated responses, we extract test examples and designate them as ID test data\". How could you *extract* test examples? I thought all the generated examples form a candidate pool for test data. What are \"the individual components within these examples\"? Given that you generate no less than 10k examples, why only 256 are selected in the end?\n- Can \"ID/OOD data\" selected by one model, i.e., mistral-7b, be regarded as ID/OOD data for another model, e.g., GPT-4?\n- The scope of your study is narrowed down to (algorithm and numerical-related) reasoning task. However the claim is a little bit of a wider range and is simply referred to as \"generalization\" as a whole. \n- The discussions (e.g., section 4.4 and 4.5) are mainly observed evidence while lack of more insights. E.g., we can easily induce that larger model size brings better generalization, however, there are some other interesting conclusions you may draw by comparing different open-source models that are fine-tuned on code/math or not. Currently only Qwen2.5-Math/Coder-7B is tested but I believe there are other models like deepseek which has different versions of instruction tuning data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ewGB7WcqCA", "reviewer": "Reviewer_r16m", "summary": "This paper introduces SCYLLA, a dynamic evaluation framework that quantifies the generalization abilities of LLMs by distinguishing between memorization and true generalization across a spectrum of task complexities. SCYLLA assesses models on both in-distribution and out-of-distribution data across various complexities, revealing a \"generalization valley\". Results from evaluating 28 LLMs highlight the effects of model size on generalization, offering insights into the threshold at which LLMs shift from generalizable to memorized behavior.", "questions": "1. Could simple prompt techniques significantly enhance base model performance and reduce the peak in performance gaps?\n2. The following study [1] also examines the relationship between OOD challenges and model size and complexity.\n\n[1] ALCUNA: Large Language Models Meet New Knowledge", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. The proposed method is straightforward and accessible, with clearly illustrated figures that enhance understanding.\n2. The study discusses a critical issue by evaluating LLMs' generalization capabilities, providing valuable insights into the models' potential and limitations.\n3. The experiments are comprehensive and detailed, offering sufficient details to ensure reproducibility.", "weaknesses": "1. The study does not examine how different prompt techniques might impact model performance. If a model can handle more complex OOD problems under few-shot prompts, does that indicate it possesses generalization capabilities?\n2. The method of generating OOD tasks by replacing numbers may be overly simplistic, potentially limiting its effectiveness. This approach might not produce genuinely OOD questions or represent all OOD types, as the model could easily recognize and substitute numbers. The tasks may be too similar in structure to ID tasks.\n3. Some conclusions, such as the presence of the generalization valley, may lack novelty. Since all models perform well on simple tasks but poorly on complex ones, the existence of the valley and the rightward peak shift might be predictable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)