# Beyond the Training Distribution: Mapping Generalization Boundaries in Neural Program Synthesis

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 44 references that are in the map.
- First posted on arXiv 30 Apr 2026.

## Builds on (most cited first, 28 of 28)

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Qwen2.5-Coder Technical Report](https://mlsanity.com/paper/2409.12186/) (2024)
- [DeepSeek-Coder: When the Large Language Model Meets Programming -- The Rise of Code Intelligence](https://mlsanity.com/paper/2401.14196/) (2024)
- [CodeT5: Identifier-aware Unified Pre-trained Encoder-Decoder Models for Code Understanding and Generation](https://mlsanity.com/paper/2109.00859/) (2021)
- [Measuring Coding Challenge Competence With APPS](https://mlsanity.com/paper/2105.09938/) (2021)
- [A Survey on Large Language Models for Code Generation](https://mlsanity.com/paper/2406.00515/) (2024)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [StarCoder 2 and The Stack v2: The Next Generation](https://mlsanity.com/paper/2402.19173/) (2024)
- [The Stack: 3 TB of permissively licensed source code](https://mlsanity.com/paper/2211.15533/) (2022)
- [RepoBench: Benchmarking Repository-Level Code Auto-Completion Systems](https://mlsanity.com/paper/2306.03091/) (2023)
- [DeepSeek-Coder-V2: Breaking the Barrier of Closed-Source Models in Code Intelligence](https://mlsanity.com/paper/2406.11931/) (2024)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [CodeGemma: Open Code Models Based on Gemma](https://mlsanity.com/paper/2406.11409/) (2024)
- [SWE-Bench+: Enhanced Coding Benchmark for LLMs](https://mlsanity.com/paper/2410.06992/) (2024)
- [Transformers Can Achieve Length Generalization But Not Robustly](https://mlsanity.com/paper/2402.09371/) (2024)
- [SWE-bench Goes Live!](https://mlsanity.com/paper/2505.23419/) (2025)
- [Quantifying Contamination in Evaluating Code Generation Capabilities of Language Models](https://mlsanity.com/paper/2403.04811/) (2024)
- [SymFormer: End-to-end symbolic regression using transformer-based architecture](https://mlsanity.com/paper/2205.15764/) (2022)
- [A Transformer Model for Symbolic Regression towards Scientific Discovery](https://mlsanity.com/paper/2312.04070/) (2023)
- [Memorize or Generalize? Evaluating LLM Code Generation with Code Rewriting](https://mlsanity.com/paper/2503.02296/) (2025)
- [Principled Understanding of Generalization for Generative Transformer Models in Arithmetic Reasoning Tasks](https://mlsanity.com/paper/2407.17963/) (2024)
- [Out-of-Distribution Generalization in the ARC-AGI Domain: Comparing Execution-Guided Neural Program Synthesis and Test-Time Fine-Tuning](https://mlsanity.com/paper/2507.15877/) (2025)
- [On the Generalizability of Transformer Models to Code Completions of Different Lengths](https://mlsanity.com/paper/2501.05051/) (2025)

## Abstract (arXiv)

Large-scale transformers achieve impressive results on program synthesis benchmarks, yet their true generalization capabilities remain obscured by data contamination and opaque training corpora. To rigorously assess whether models are truly generalizing or merely retrieving memorized templates, we introduce a strictly controlled program synthesis environment based on a domain-specific arithmetic grammar. By systematically enumerating and evaluating millions of unique programs, we construct interpretable syntactic and semantic metric spaces. This allows us to precisely map data distributions and sample train and test splits that isolate specific distributional shifts. Our experiments demonstrate that optimizing density generalization -- through diverse sampling over both semantic and syntactic spaces -- induces robust out-of-distribution generalization. Conversely, evaluating support generalization reveals that transformers severely struggle with extrapolation, experiencing a performance drop of over 30% when forced to generate syntactically novel programs. While steadily scaling up compute improves generalization, the gains follow a strictly log-linear relationship. We conclude that robust generalization requires maximizing training diversity across multiple manifolds, and our findings indicate the necessity for novel search-based approaches to break through current log-linear scaling bottlenecks.