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

• URL: http://arxiv.org/abs/2604.27551v1
• Date: Thu, 30 Apr 2026 07:58:39 GMT
• Title: Beyond the Training Distribution: Mapping Generalization Boundaries in Neural Program Synthesis
• Abstract summary: Large-scale transformers achieve impressive results on program synthesis benchmarks.<n>But their true generalization capabilities remain obscured by data contamination and opaque training corpora.<n>We introduce a strictly controlled program synthesis environment based on a domain-specific arithmetic grammar.
• Score: 13.460704771478866
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Generalization Capability for Imitation Learning [1.30536490219656]
  Imitation learning holds the promise of equipping robots with versatile skills by learning from expert demonstrations.<n>However, policies trained on finite datasets often struggle to generalize beyond the training distribution.<n>We present a unified perspective on the generalization capability of imitation learning, grounded in both information theorey and data distribution property.
  arXiv  Detail & Related papers  (2025-04-25T17:59:59Z)
• Single Domain Generalization with Model-aware Parametric Batch-wise Mixup [22.709796153794507]
  Single Domain Generalization remains a formidable challenge in the field of machine learning.<n>We propose a novel data augmentation approach, named as Model-aware Parametric Batch-wise Mixup.<n>By exploiting inter-feature correlations, the parameterized mixup generator introduces additional versatility in combining features across a batch of instances.
  arXiv  Detail & Related papers  (2025-02-22T03:45:18Z)
• KL-geodesics flow matching with a novel sampling scheme [4.347494885647007]
  Non-autoregressive language models generate all tokens simultaneously, offering potential speed advantages over traditional autoregressive models.<n>We investigate a conditional flow matching approach for text generation.
  arXiv  Detail & Related papers  (2024-11-25T17:15:41Z)
• Learning Divergence Fields for Shift-Robust Graph Representations [73.11818515795761]
  In this work, we propose a geometric diffusion model with learnable divergence fields for the challenging problem with interdependent data. We derive a new learning objective through causal inference, which can guide the model to learn generalizable patterns of interdependence that are insensitive across domains.
  arXiv  Detail & Related papers  (2024-06-07T14:29:21Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion [66.21290235237808]
  We introduce an energy constrained diffusion model which encodes a batch of instances from a dataset into evolutionary states. We provide rigorous theory that implies closed-form optimal estimates for the pairwise diffusion strength among arbitrary instance pairs. Experiments highlight the wide applicability of our model as a general-purpose encoder backbone with superior performance in various tasks.
  arXiv  Detail & Related papers  (2023-01-23T15:18:54Z)
• HyperImpute: Generalized Iterative Imputation with Automatic Model Selection [77.86861638371926]
  We propose a generalized iterative imputation framework for adaptively and automatically configuring column-wise models. We provide a concrete implementation with out-of-the-box learners, simulators, and interfaces.
  arXiv  Detail & Related papers  (2022-06-15T19:10:35Z)
• Measuring Generalization with Optimal Transport [111.29415509046886]
  We develop margin-based generalization bounds, where the margins are normalized with optimal transport costs. Our bounds robustly predict the generalization error, given training data and network parameters, on large scale datasets.
  arXiv  Detail & Related papers  (2021-06-07T03:04:59Z)
• Out-of-Distribution Generalization in Kernel Regression [21.958028127426196]
  We study generalization in kernel regression when the training and test distributions are different. We identify an overlap matrix that quantifies the mismatch between distributions for a given kernel. We develop procedures for optimizing training and test distributions for a given data budget to find best and worst case generalizations under the shift.
  arXiv  Detail & Related papers  (2021-06-04T04:54:25Z)
• Extrapolatable Relational Reasoning With Comparators in Low-Dimensional Manifolds [7.769102711230249]
  We propose a neuroscience-inspired inductive-biased module that can be readily amalgamated with current neural network architectures. We show that neural nets with this inductive bias achieve considerably better o.o.d generalisation performance for a range of relational reasoning tasks.
  arXiv  Detail & Related papers  (2020-06-15T19:09:13Z)
• Hierarchical regularization networks for sparsification based learning on noisy datasets [0.0]
  hierarchy follows from approximation spaces identified at successively finer scales. For promoting model generalization at each scale, we also introduce a novel, projection based penalty operator across multiple dimension. Results show the performance of the approach as a data reduction and modeling strategy on both synthetic and real datasets.
  arXiv  Detail & Related papers  (2020-06-09T18:32:24Z)
• Synthetic Datasets for Neural Program Synthesis [66.20924952964117]
  We propose a new methodology for controlling and evaluating the bias of synthetic data distributions over both programs and specifications. We demonstrate, using the Karel DSL and a small Calculator DSL, that training deep networks on these distributions leads to improved cross-distribution generalization performance.
  arXiv  Detail & Related papers  (2019-12-27T21:28:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.