LLM Priors for ERM over Programs

We study program-learning methods that are efficient in both samples and computation. Classical learning theory suggests that when the target admits a short program description, for example a short piece of ``Python code'', it can be learned from few examples by ERM over the program class. However, this approach relies on enumerating candidate programs, which is typically exponential in the description length; gradient-based training avoids this explicit search but, for some families of short programs, can require exponentially many samples to succeed. We propose \textsc{LLM-PV}, a propose-and-verify recipe that enables ERM-style selection over a discrete program class without exhaustive enumeration: a pretrained LLM induces a proposal distribution over candidate programs, each proposal is executed and scored on a held-out validation set, and the best program is selected, with no gradient updates or validation feedback used to adapt the sampling distribution. Across algorithmic tasks including parity variants, pattern matching, and primality testing, \textsc{LLM-PV} often recovers the exact underlying rule from a small labeled set and generalizes far beyond the training sequence lengths, while SGD-trained transformers, fine-tuning, in-context learning, and classical ML baselines can fit the training data yet fail to generalize reliably. Together, these results suggest that pretrained LLM priors can serve as effective search biases for ERM, narrowing the gap between statistical and computational efficiency.

Many learning problems can be solved if the system discovers a simple rule behind the data, such as a short piece of code. Traditional methods can sometimes learn such rules from few examples, but they may require an enormous search over possible rules. Modern neural networks avoid this explicit search, but they can need many examples and may fail to discover the rule in a way that generalizes. We propose LLM-PV, a method that uses a large language model to suggest possible rules, then checks these rules by running them and testing how well they work on held-out examples. On several algorithmic tasks, this approach often finds the correct rule from a small number of examples and generalizes to much larger inputs than those seen during training. Our results suggest that large language models can be useful not only as predictors, but also as guides for searching over clear, executable, and verifiable solutions.