Quantifying Generalization Complexity for Large Language Models

The study does not examine how different prompt techniques might impact model performance. Could simple prompt techniques significantly enhance base model performance and reduce the peak in performance gaps?

We highly appreciate your suggestion to examine the impact of different prompting techniques on model performance. However, our choice to focus on the zeroshot-cot paradigm was deliberate. Adding few-shot examples would introduce a confounding variable—the selection and structure of the examples—which could bias the results and obscure the intrinsic effects of model generalization. Thus, the decision was aligned with our goal of isolating and rigorously evaluating the genuine generalization capabilities of LLMs.

In response to your suggestion, we conducted additional experiments incorporating the fewshot-cot method. We use Gemma-2-2B-Instruct as the LLM, and use 3 shot CoT examples that are obtained from Gemma’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:

From the results, fewshot-cot prompting does improve performance across both ID and OOD datasets compared to zeroshot-cot prompting. This is especially evident in lower-complexity tasks (e.g., $O(N)$ and $O([N-N^2])$). While fewshot-cot generally reduces the accuracy gap between ID and OOD tests, the peak performance gap remains significant, particularly for intermediate complexity tasks (e.g., $O([N^2-N^3])$). Even with fewshot prompting, the generalization valley phenomenon persists, and the critical complexity still remains at the same complexity level compared to zeroshot prompting.

These additional experiments support the hypothesis that few-shot cot prompting can enhance performance, particularly for ID datasets, but the core phenomena observed in our study—such as the generalization valley and critical complexity—remain robust. Therefore, while prompt techniques like fewshot can modulate performance, they do not fundamentally alter the underlying generalization patterns of the models, as revealed by SCYLLA.

We hope this addresses your concerns and clarifies our methodological choices. Thank you for your constructive feedback, which has strengthened our analysis.

We appreciate your observation regarding the predictability of the generalization valley and critical complexity shift, and we acknowledge that it is intuitive that "simpler tasks are easier and complex tasks are harder". However, we reiterate the novelties in our work and hope that our clarifications address your concerns:

1. The fact that “simple tasks are easy and complex tasks are hard” does imply the rightward shift of critical complexity, but does not imply the existence of the generalization valley: As tasks become more complex, the reliance on non-generalizable behaviors first increases to a peak (critical complexity) and then decreases, indicating an intermediate point where the model still performs well on ID tasks but poorly on OOD tasks. Without this increasing-decreasing trend, we cannot obtain the critical complexity.

2. We do not intend to argue that "right shift of critical complexity" is an unexpected phenomenon. Conversely, that "right shift of critical complexity is intuitive since larger models should be able to handle more complex tasks" actually shows that the definition of critical complexity is meaningful and aligns with intuition.

3. The critical complexity highlights an important threshold beyond which the generalization ability drastically diminishes. This metric allows for a quantitative comparison of generalization capabilities across models of varying sizes and architectures, adding rigor to the evaluation.

4. Even if the generalization valley may seem predictable in hindsight, formalizing this behavior through systematic experiments across multiple models provides a robust empirical framework. Our work benchmarks this phenomenon quantitatively for the first time, enabling the community to use critical complexity as a measurable indicator of model generalization.

5. Using algorithmic complexity as a controlled metric to evaluate performance provides further insights into why certain tasks cause a pronounced/small performance gap. This approach also reveals differences in how specific models handle memorization versus generalization, contributing new angles for model evaluation.

In conclusion, while our observations may seem intuitive at a high level, our work introduces quantitative rigor, systematic analysis, and actionable metrics that contribute to the overall understanding of LLM generalization behaviors.

How could you extract test examples? What are "the individual components within these examples"?

We apologize for the confusion in the description. To clarify: Suppose the following is an example of response generated by the model after we query it:

• Test input 1: [1, 2, 3, 4]
• Test input 2: [5, 6, 7, 8]
• Test input 3: [9, 10, 11, 12]

We extract these test examples using regular expressions, yielding the following outputs: [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]].

The individual components are the numbers within these lists, i.e., [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12].

Given that you generate no less than 10k examples, why only 256 are selected in the end?

We generate over 10k examples to estimate the ID distribution and ensure sufficient diversity for OOD data generation. From this pool, we select 256 examples for testing to balance computational efficiency and statistical robustness. Testing with 256 examples provides reliable and meaningful insights while keeping computational costs manageable.

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?

No, ID/OOD data is model-specific. The ID data reflects patterns familiar to the specific model, which varies depending on its training data.

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.

We acknowledge that our study focuses on a narrower scope of algorithmic and numerical reasoning tasks, while the term "generalization" may imply a broader range. However, we claim that this narrower focus was intentional, grounded in the need to satisfy the four critical criteria for task design in our study. Algorithmic and numerical tasks were chosen because they meet these criteria effectively:

1. Scalability (Quantifiability): Tasks must allow for a clear and systematic scaling of complexity. Algorithmic and numerical problems lend themselves to this by leveraging constructs like time complexity. This quantifiability ensures that model performance can be rigorously evaluated as task difficulty increases.

2. Dynamic Generation: Robust evaluation requires the ability to dynamically generate test instances to mitigate issues such as data contamination. Algorithmic tasks can be easily randomized and synthesized during testing.

3. Knowledge-Light: The chosen algorithmic tasks require minimal external knowledge, relying primarily on logical or computational reasoning. This ensures that performance differences arise from reasoning capabilities rather than disparities in pre-existing domain knowledge.

4. Memorization Awareness: By explicitly differentiating between ID and OOD numerical data, algorithmic tasks allow us to disentangle memorization from generalization.

While this narrower focus enables rigorous and controlled experimentation, we agree that future work should expand the scope to include more diverse categories. For example, natural language based reasoning tasks involving semantic understanding; multimodal scenarios integrating visual, textual, and auditory inputs; applications like financial forecasting or medical diagnostics that simulate real-world complexity. These extensions could enable a more comprehensive understanding of generalization across a broader spectrum of tasks and domains.

We will revise our claims to align more precisely with the current scope of the study, emphasizing its focus on algorithmic and numerical reasoning as a foundational framework for evaluating LLM generalization. We will underscore the study's value as a proof-of-concept, while leaving room for future exploration of broader generalization phenomena.

other interesting conclusions you may draw by comparing different open-source models that are fine-tuned on code/math or not.

We appreciate your suggestion and would like to highlight that we have already conducted a comparative analysis between base models and domain specific fine-tuned counterparts in Section 4.4 (Line 460). Specifically, we observed that Qwen2.5-Math-7B and Qwen2.5-Coder-7B outperform their base version (Qwen2.5-7B) on simpler tasks (e.g., $O(N)$ and $O([N, N^2])$ levels). However, these fine-tuned models did not exhibit significant improvements on higher-complexity tasks (e.g., $O([N^2-N^3])$ and beyond). This indicates that while domain-specific fine-tuning enhances performance within the original scope of complexity, its benefits diminish for tasks requiring higher reasoning skills. This finding underscores the importance of task alignment when evaluating generalization in fine-tuned models. We acknowledge that extending this analysis to other open-source models, such as DeepSeek, would provide additional insights, and we aim to explore these comparisons in future work. Thank you for emphasizing this area of improvement.

Dear Reviewer,

As the rebuttal period is drawing to a close, I would appreciate your response to the authors' rebuttal at your earliest convenience.

Best Regards,

Area Chair

Limited task types

Thank you very much for your suggestion on incorporating more task types. We claim that this narrower focus was intentional, grounded in the need to satisfy the four critical criteria for task design in our study. Algorithmic and numerical tasks were chosen because they meet these criteria effectively:

1. Scalability (Quantifiability): Tasks must allow for a clear and systematic scaling of complexity. Algorithmic and numerical problems lend themselves to this by leveraging constructs like time complexity (e.g., $O(N)$, $O(2^N)$). This quantifiability ensures that model performance can be rigorously evaluated as task difficulty increases.

2. Dynamic Generation: Robust evaluation requires the ability to dynamically generate test instances to mitigate issues such as data contamination. Algorithmic tasks can be easily randomized and synthesized during testing.

3. Knowledge-Light: The chosen algorithmic tasks require minimal external knowledge, relying primarily on logical or computational reasoning. This ensures that performance differences arise from reasoning capabilities rather than disparities in pre-existing domain knowledge.

4. Memorization Awareness: By explicitly differentiating between ID and OOD numerical data, algorithmic tasks allow us to disentangle memorization from generalization.

While this narrower focus enables rigorous and controlled experimentation, we agree that future work should expand the scope to include more diverse categories. For example, natural language based reasoning tasks involving semantic understanding and contextual reasoning; multimodal scenarios integrating visual, textual, and auditory inputs; applications like financial forecasting or medical diagnostics that simulate real-world complexity. These extensions could enable a more comprehensive understanding of generalization across a broader spectrum of tasks and domains.

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.

We apologize for the confusion. We create OOD samples for each single model.

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?

We appreciate that you bring up the string manipulation tasks as extended task types. We did consider string tasks before, but it is even harder to define in-distribution and out-of-distribution for strings. Plus, the tokenization process adds additional complexity to string-based tasks, which potentially introduces additional confounding factors.

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.

The goal here is to demonstrate “a set of probe tasks to analyze the time complexity that different LLMs employ to solve these tasks”. For the gray line specifically, OOD accuracy does reduce as the complexity increases, but as we have already shown this trend in Figure 5, we did not make more explanations here.

Dependence on approximate ID data.

Thank you for highlighting the limitations of dependence on approximate ID/OOD data.

We first want to clarify that our evaluation framework is designed to assess the generalization ability of any LLM with only black-box access. Consequently, obtaining genuine ID or OOD data is inherently impossible. To address this, we propose a workaround by prompting the model to generate ID data.

To demonstrate that this approximation is both reasonable and meaningful, we use OLMo-7B-Instruct as an example to examine how the ID/OOD data we obtained overlaps with the training data (i.e., genuine ID data). OLMo is an open-sourced language model trained on the Dolma and Tulu datasets. By utilizing the tool WIMBD (What’s In My Big Data) [1], we were able to count the occurrences of each ID and OOD example within the two training datasets of OLMo.

We ran the pipeline proposed in our work using OLMo and counted the ID and OOD examples obtained in Dolma and Tulu across our 17 anchor tasks. We then calculated the average occurrences of examples for each task, and the results are presented in the table below:

From the results, it is evident that for each of the 17 anchor tasks and across both training datasets (Dolma and Tulu), the occurrence of ID examples far exceeds that of OOD examples. Specifically, nearly all OOD example occurrences are zero, except for the tasks “FourSumMultipleTen” and “RemoveDuplicateNumbers”. In contrast, the occurrence of ID examples ranges from thousands to tens of thousands, highlighting a substantial disparity in the overlap of examples with the training data. These findings strongly support the validity and meaningfulness of our method for formulating ID and OOD examples.

We hope the above experiment addresses your concerns and demonstrates the effectiveness of our example-generation method. We sincerely appreciate your constructive feedback, which has helped enhance our analysis.

[1] Elazar, Y., Bhagia, A., Magnusson, I., Ravichander, A., Schwenk, D., Suhr, A., ... & Dodge, J. (2023). What's In My Big Data?. arXiv preprint arXiv:2310.20707.

Limited task types

We claim that this narrower focus was intentional, grounded in the need to satisfy the four critical criteria for task design in our study. Algorithmic and numerical tasks were chosen because they meet these criteria effectively:

1. Scalability (Quantifiability): Tasks must allow for a clear and systematic scaling of complexity. Algorithmic and numerical problems lend themselves to this by leveraging constructs like time complexity (e.g., $O(N)$, $O(2^N)$). This quantifiability ensures that model performance can be rigorously evaluated as task difficulty increases.

2. Dynamic Generation: Robust evaluation requires the ability to dynamically generate test instances to mitigate issues such as data contamination. Algorithmic tasks can be easily randomized and synthesized during testing.

3. Knowledge-Light: The chosen algorithmic tasks require minimal external knowledge, relying primarily on logical or computational reasoning. This ensures that performance differences arise from reasoning capabilities rather than disparities in pre-existing domain knowledge.

4. Memorization Awareness: By explicitly differentiating between ID and OOD numerical data, algorithmic tasks allow us to disentangle memorization from generalization.

While this narrower focus enables rigorous and controlled experimentation, we agree that future work should expand the scope to include more diverse categories. For example, natural language based reasoning tasks involving semantic understanding and contextual reasoning; multimodal scenarios integrating visual, textual, and auditory inputs; applications like financial forecasting or medical diagnostics that simulate real-world complexity. These extensions could enable a more comprehensive understanding of generalization across a broader spectrum of tasks and domains.

Different prompt formats

We highly appreciate your suggestion to examine the impact of different types of prompting on model performance. However, our choice to focus on the zeroshot-cot paradigm was deliberate. Adding few-shot examples would introduce a confounding variable—the selection and structure of the examples—which could bias the results and obscure the intrinsic effects of model generalization. Thus, the decision was aligned with our goal of isolating and rigorously evaluating the genuine generalization capabilities of LLMs.

In response to your suggestion, we conducted additional experiments incorporating the fewshot-cot method. We use Gemma-2-2B-Instruct as the LLM, and use 3 shot CoT examples that are obtained from Gemma’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:

From the results, fewshot-cot prompting does improve performance across both ID and OOD datasets compared to zeroshot-cot prompting. This is especially evident in lower-complexity tasks (e.g., $O(N)$ and $O([N-N^2])$). While fewshot-cot generally reduces the accuracy gap between ID and OOD tests, the peak performance gap remains significant, particularly for intermediate complexity tasks (e.g., $O([N^2-N^3])$). Even with fewshot prompting, the generalization valley phenomenon persists, and the critical complexity still remains at the same complexity level compared to zeroshot prompting.

These additional experiments support the hypothesis that few-shot cot prompting can enhance performance, particularly for ID datasets, but the core phenomena observed in our study—such as the generalization valley and critical complexity—remain robust. Therefore, while prompt techniques like fewshot can modulate performance, they do not fundamentally alter the underlying generalization patterns of the models, as revealed by SCYLLA.

We hope this addresses your concerns and clarifies our methodological choices. Thank you for your constructive feedback, which has strengthened our analysis.

ID/OOD Definition Issues

Thank you for highlighting the limitations of the ID/OOD definitions.

We first want to clarify that our evaluation framework is designed to assess the generalization ability of any LLM with only black-box access. Consequently, obtaining genuine ID or OOD data is inherently impossible. To address this, we propose a workaround by prompting the model to generate ID data.

To demonstrate that this approximation is both reasonable and meaningful, we use OLMo-7B-Instruct as an example to examine how the ID/OOD data we obtained overlaps with the training data (i.e., genuine ID data). OLMo is an open-sourced language model trained on the Dolma and Tulu datasets. By utilizing the tool WIMBD (What’s In My Big Data) [1], we were able to count the occurrences of each ID and OOD example within the two training datasets of OLMo.

We ran the pipeline proposed in our work using OLMo and counted the ID and OOD examples obtained in Dolma and Tulu across our 17 anchor tasks. We then calculated the average occurrences of examples for each task, and the results are presented in the table below:

From the results, it is evident that for each of the 17 anchor tasks and across both training datasets (Dolma and Tulu), the occurrence of ID examples far exceeds that of OOD examples. Specifically, nearly all OOD example occurrences are zero, except for the tasks “FourSumMultipleTen” and “RemoveDuplicateNumbers”. In contrast, the occurrence of ID examples ranges from thousands to tens of thousands, highlighting a substantial disparity in the overlap of examples with the training data. These findings strongly support the validity and meaningfulness of our method for formulating ID and OOD examples.

We hope the above experiment addresses your concerns and demonstrates the effectiveness of our example-generation method. We sincerely appreciate your constructive feedback, which has helped enhance our analysis.

[1] Elazar, Y., Bhagia, A., Magnusson, I., Ravichander, A., Schwenk, D., Suhr, A., ... & Dodge, J. (2023). What's In My Big Data?. arXiv preprint arXiv:2310.20707.

Dear Reviewer,

As the rebuttal period is drawing to a close, I would appreciate your response to the authors' rebuttal at your earliest convenience.

Best Regards,

Area Chair

I appreciate the authors conducting additional experiments to address my concerns. My concerns regarding prompts have been resolved. However, I have additional questions about the ID and OOD statistics:

• Why are the numbers of examples in this table shown as float numbers rather than integers?
• WIMBD uses a very simple inverted index search method, which may limit the statistical accuracy of this table. This limitation should be discussed when presenting these results.
• Do you have any insights why “FourSumMultipleTen” and “RemoveDuplicateNumbers” has OOD while the others doesn't? like a case study with some examples? I am okay if the authors saying this is just a random case but I am curious if there is something else.

Finally, I am curious whether the data generation process for OOD and ID will be open-sourced. Without this, the contribution of this paper would be somewhat limited. Nevertheless, I maintain my positive assessment of this paper.

We highly appreciate your response and feedback, and we are glad to hear that our response resolved your concerns.

Regarding your additional questions:

Why are the numbers of examples in this table shown as float numbers rather than integers?

This is because we averaged over the occurrences of all examples we obtained for each task on each dataset.

WIMBD uses a very simple inverted index search method, which may limit the statistical accuracy of this table. This limitation should be discussed when presenting these results.

Thank you for pointing this out. While WIMBD is simple, we consider that it is the most efficient and straightforward way to validate the statistical meaning. We will discuss the limitations of using it in our newest version.

Do you have any insights why “FourSumMultipleTen” and “RemoveDuplicateNumbers” has OOD while the others doesn't?

We think that it is more likely just random cases. For "RemoveDuplicateNumbers", we think it may also be because the sequences containing duplicate numbers are more common than others.

whether the data generation process for OOD and ID will be open-sourced

Yes, the entire pipeline proposed in our work will be open-sourced.