Technical Summary: LLM Priors for ERM over Programs

Problem Statement

The paper addresses the fundamental tension between sample efficiency and computational efficiency in learning short, discrete program descriptions (e.g., "Python code") from labeled data.

Classical learning theory (PAC learning) suggests that if a target function admits a short program description of length $L$ over an alphabet $\Sigma$, it can be learned from $\tilde{O}(L \log |\Sigma|)$ examples via Empirical Risk Minimization (ERM) over the class of programs. However, implementing ERM requires exhaustive enumeration of candidate programs, which scales exponentially as $\Theta(|\Sigma|^L)$, rendering it computationally infeasible for even moderate $L$.

Conversely, modern deep learning approaches using Stochastic Gradient Descent (SGD) on high-capacity neural networks avoid explicit enumeration and are computationally efficient. Yet, theoretical results in the Statistical Query (SQ) framework indicate that gradient-based methods struggle with structured, "SQ-hard" families (such as parity functions and cryptographic primitives). These methods often require exponentially many samples to succeed because the gradient interface is poorly matched to the discrete structure of the target rule, leading to failure in generalizing beyond training sequence lengths.

The central question is: Can we recover the sample efficiency of ERM over short programs without paying the full cost of exhaustive enumeration?

Methodology: LLM-PV

The authors propose LLM-PV (LLM Propose-and-Verify), a learning algorithm that treats a pretrained Large Language Model (LLM) not as a predictor, but as a search prior for ERM.

The Algorithm

LLM-PV decouples the roles of proposal and selection:

1. Proposal (The Prior): A pretrained LLM is prompted with a training set $S_{tr}$ to induce a data-dependent distribution over candidate programs. The LLM generates a small number of candidate programs (or edits) that are hypothesized to explain the data.
2. Verification (The ERM Step): Each candidate program is compiled and executed on a held-out validation set $S_{val}$. Programs that fail to compile, do not halt, or produce invalid outputs are discarded.
3. Selection: The algorithm selects the program with the lowest validation error. Crucially, no gradient updates are performed on the LLM, and no validation feedback is used to adapt the LLM's sampling distribution during the search. The LLM acts solely as an inductive bias mechanism.

Theoretical Framework

The paper formalizes the performance of LLM-PV using a "propose-and-verify" guarantee. If the LLM's proposal distribution places a non-negligible mass $p_\epsilon(S_{tr})$ on programs with population error $\le \epsilon$, then the number of trials $k$ required to find a good hypothesis scales as $O(\log(1/\delta) / p_\epsilon(S_{tr}))$. This replaces the exponential search space $|\Sigma|^L$ with an effective search size of $1/p_\epsilon(S_{tr})$.

The authors also provide theoretical lower bounds demonstrating that for planted $k$-parity problems, finite-precision mini-batch coordinate SGD requires $\Omega(\sqrt{N}/2^b)$ fresh examples (where $N$ is the number of possible targets), whereas enumeration requires $\Theta(|\Sigma|^L)$ time. This establishes a regime where both naive enumeration and standard gradient-based training fail, motivating the LLM-PV approach.

Key Contributions

1. Formalizing the Compute-Sample Tension: The paper isolates a specific small-data regime (planted $k$-parity) where finite-class ERM is sample-efficient but computationally intractable, while gradient-based training is computationally convenient but sample-inefficient due to SQ hardness.
2. LLM-PV Algorithm: The introduction of a clean "propose-and-verify" pipeline that uses pretrained LLMs strictly as a proposal mechanism. This preserves the auditability and theoretical guarantees of ERM (selection based on held-out error) while leveraging the LLM's ability to concentrate search on plausible hypotheses.
3. Empirical Evidence of Rule Recovery: Extensive experiments across diverse algorithmic tasks (parity variants, pattern matching, palindromes, Dyck-2, primality testing, cellular automata, and SHA-256 parity) show that LLM-PV often recovers the exact underlying rule from as few as 200 labeled examples.
4. Length Generalization: Unlike SGD-trained transformers, fine-tuned models, or in-context learning (ICL) baselines, which often memorize training distributions and fail to generalize to longer input sequences, LLM-PV frequently synthesizes dimension-invariant programs that generalize perfectly to input lengths far exceeding the training set.
5. Auditability: The method produces executable, human-readable code and a full reasoning trace (the sequence of proposed programs and their validation errors), allowing for direct debugging and mechanistic validation of the learning process.

Results

The authors evaluated LLM-PV against a wide range of baselines, including classic ML (XGBoost, SVM, Genetic Algorithms), SGD-trained models (from scratch and fine-tuned), and In-Context Learning (ICL) with large instruction-tuned models.

• Algorithmic Tasks: On tasks like 10-Parity, Cellular Automata Parity, and Primality testing, standard baselines (including 30B+ parameter ICL models) performed near chance (50% accuracy) at test lengths ($n=100$), even when trained on 200 examples. In contrast, LLM-PV achieved 100% test accuracy on these tasks with the same 200 examples.
• Generalization: When trained on short sequences ($n=10$) and tested on long sequences ($n=100$), SGD and fine-tuning baselines collapsed to chance accuracy. LLM-PV maintained high accuracy, successfully synthesizing rules that were invariant to input length.
• Data Scaling: Increasing the training set size for SGD-based models (up to 100k examples) did not resolve the generalization failure on parity and cellular automata tasks, confirming the SQ-hard nature of these problems for gradient-based learners.
• Tool Use: The paper notes that while tool-augmented ICL (where the model can run code) improves performance over direct prompting, it still fails to reliably recover algorithmic rules. The success of LLM-PV is attributed to the specific search objective (proposing programs and selecting by validation error) rather than tool access alone.
• Tabular Data: On standard tabular benchmarks, LLM-PV performed comparably to strong tabular learners, suggesting the approach is not limited to synthetic sequence tasks.

Significance and Claims

The paper claims that pretrained LLM priors can serve as effective search biases for ERM, successfully narrowing the gap between statistical and computational efficiency in program learning.

The core significance lies in the separation of roles: the LLM is used only to propose hypotheses, while the learning objective remains grounded in executable verification and held-out error. This approach:

• Avoids the "black box" nature of gradient-based predictors by outputting explicit, verifiable code.
• Overcomes the sample inefficiency of gradient-based methods on structured, discrete tasks where the target admits a short description.
• Provides a mechanism for length generalization that standard deep learning methods fail to achieve on algorithmic tasks.

The authors are modest about the scope, acknowledging that the method relies on the LLM's ability to place sufficient mass on correct programs and that the approach is currently tailored to structured, low-data regimes rather than serving as a general replacement for supervised deep learning on unstructured data. The success depends on the "proposer" being capable and the "verification" step being robust.