acceptodds
Under review as a conference paper at ICLR 2027

ALPS: Climbing the Probabilistic Program Landscape with LLM-guided Synthesis

Abstract

Trustworthy modeling requires more than accurate predictions: it requires confidence estimates grounded in an explicit understanding of the process that generated the data. Models written as probabilistic programs (PPs) meet this need directly, as each program represents a transparent and human-readable generative process, with dependencies and noise sources laid out as executable code. Several approaches have explored constructing probabilistic programs from data alone, without prior knowledge of the data-generating process, but the problem remains challenging, as the space of possible structures is combinatorially large, and parameter optimization requires a fixed structure. We introduce ALPS (Automated LLM-guided Probabilistic programs Synthesis), a pipeline that pairs LLM-guided structural proposal and mutation with gradient-based optimization of each candidate's continuous parameters. This approach combines informed and diagnostics-driven structural search with efficient gradient-based parameter refinement. Across nine benchmarks common in the PP literature, we compare ALPS against four baselines and show that our approach attains the best likelihood fit on average on all the benchmarks and remains competitive in distributional distance to the ground-truth program. Beyond these metrics, we show qualitatively that ALPS more reliably recovers the correct correlation structure underlying the data, yielding programs that are not only accurate but also faithful to the underlying generative process. We further validate ALPS on a real-world dataset, and show that prior domain knowledge can be injected as natural-language hypotheses.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Probabilistic programs, Program synthesis, Large language models, Structure learning, Generative modeling

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_5rqJOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents ALPS. It uses an LLM to search for program structures and a gradient-based method to fit their parameters in DeGAS. It keeps the best candidate programs ans the LLM then improves these programs based on their code, data statistics, and optimization results. It also compare the ALPS with four other methods on nine benchmarks. They use held-out negative log-likelihood and Wasserstein-type distances to measure performance. They also test the effects of the LLM, parameter fitting, program changes, and feedback. Finally, they use real UCI heart disease data to test ALPS on real-world data. They also use natural language hypotheses to guide the search for program structures.

Critical strengths
  1. ALPS combined LLM-guided structural search with gradient-based parameter fitting, it addressed two interdependent challenges in probabilistic program discovery.

  2. ALPS produces clear generative programs and it evaluates their ability to reproduce observed distributions beyond likelihood fit.

Critical weaknesses
  1. ALPS leaves the comparability of likelihood scores across discrete and continuous representations unclear, weakening its interpretation of its model-discovery gains.

  2. ALPS does not separate the benefit of its search strategy from the greater capability of its LLM backend relative to the baselines.

Questions for authors

1.How does ALPS make sure that the likelihood scores can fully reflect model quality, instead of how discrete variables are written? 2. Does ALPS still perform better than the existing methods when they use the same LLM and the same budget? 3. Do the real-data results show that the ALPS can find reliable programs when all runs, including failed ones, are counted?

3 comments
AuthorsOpenReview ↗

Response to Reviewer 5rqJ

Do the likelihood scores reflect model quality rather than how discrete variables are written?

We agree that likelihoods computed with respect to different reference measures are not directly comparable: DeGAS scores a discrete value as a narrow Gaussian density, whereas a language with native discrete distributions scores it as a probability mass. For this reason, our evaluation only compares likelihoods between programs written in DeGAS and scored by the same DeGAS likelihood. This holds for all baselines, including RS-MCMC, whose programs are translated back into DeGAS for evaluation (App. C.2). To check that ALPS's advantage does not depend on how discrete variables are written, we note that on the three purely continuous benchmarks (If, MoG, MultiBranch), where no discrete variables are present, ALPS still has the best NLL, significantly against all four baselines (p < 0.05, Table 6).

To complement the likelihood, we also report W₂², the Wasserstein-type distance between the Gaussian-mixture representations of each synthesized program and the ground-truth program. When comparing against a method outside DeGAS, as with the original RefineStat (in PyMC) in our real-world case study, we do not compare likelihoods and instead report the empirical Wasserstein distance W₁ between the distribution of num in generated samples and in the real data, which does not depend on how a variable is represented.

Does ALPS still outperform existing methods with the same LLM and the same budget?

To separate the contribution of the search from that of the LLM, we re-ran ALPS with Qwen2.5-Coder-7B-Instruct, the model used by the RefineStat-based baselines, with and without grammar-constrained decoding. Without it, ALPS converges on five of nine benchmarks and achieves the best NLL and W₂² on all five; its weakness at this scale is producing valid programs (29/45 valid runs). With grammar-constrained decoding through llguidance, ALPS converges on all nine benchmarks (44/45 valid runs) and, against the baselines with the same model, achieves the best NLL on seven of nine and the best W₂² on six. Results are reported in the general response to all reviewers (above) and in the new App. E.

Regarding budget, the methods spend compute in different units, so they cannot be equalized on a single one; each method runs until its own stopping criterion (App. D.7). With gpt-oss-120b, an ALPS run makes on average 8.1 LLM calls (39.6 generated programs) and takes 16.3 minutes; with the 7B model, it makes 9.3 calls (≈46 programs) and takes 5.6 minutes. RS-Grad generates on average 9.7 programs in 4.3 minutes, and RS-MCMC 53.7 programs in 237 minutes. RS-MCMC thus sees a comparable number of programs at about 40× the wall-clock cost of ALPS with the same 7B model, and still performs worse on most benchmarks. RS-Grad stops early because its acceptance criterion is met, not because its budget is exhausted: it allows up to 100 refinement rounds, and some runs generate up to 102 programs.

Do the real-data results show that ALPS finds reliable programs when all runs, including failed ones, are counted?

We repeated the heart-disease experiment with 10 runs per method, using the same prompt as for the benchmarks (no prior knowledge injected), and counted every run, including the failed ones (revised Sec. 5). ALPS produced a valid program in 8/10 runs, RefineStat in 4/10. Over the successful runs, the Wasserstein-1 distance between the real and the predicted distribution of num had a median of 0.197 (IQR 0.178–0.495) for ALPS and 0.469 (IQR 0.351–0.479) for RefineStat. One of RefineStat's successful runs (W₁ = 0.000) uses num as a predictor of itself; excluding it gives 0.469 (IQR 0.469–0.490). Counting failed runs as the worst score, the ALPS median is 0.343, while the median RefineStat run is a failure. The ALPS failures occur when the LLM writes programs over placeholder variable names instead of the dataset's columns. RefineStat's failures are runs that never produce a model PyMC can sample from, or that hang during NUTS sampling.

Dear Reviewer 5rqJ,

Thank you again for your review. As the discussion period ends on November 18, we would like to ask whether our response addresses your concerns, in particular the comparability of likelihoods across representations, the comparison with the same 7B model (App. E) and the real-data experiment repeated with 10 runs, counting failed ones (Sec. 5). We would be happy to clarify any remaining points.

Best regards, The Authors

AuthorsOpenReview ↗

Follow up on discrete variables

Dear Reviewer 5rqJ,

Following up on your first question, we re-evaluated all methods with a corrected likelihood that scores discrete variables as probability masses, so that scores no longer depend on how a discrete variable is written. ALPS remains best on 6 of 9 benchmarks, and on all 9 when re-run with the corrected likelihood as its objective; the comparison is on equal terms with all baselines except RS-Grad, which could not yet be re-run due to time constraints. Details are in the general response (additional results) and in the new App. F.

We thank you for raising this point, which will improve the evaluation in the final version.

Reviewer_5vAmOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

ALPS is a pipeline for synthesizing probabilistic programs from observational data. An LLM proposes and mutates program structures, Gaussian-mixture parameters are refined with gradient-based method on top of the closed-form likelihood provided by DeGAS, and an evolutionary loop that keeps the top-M candidates is iterated until convergence. On nine benchmarks, the paper compares against various baselines, reporting the best NLL value. Ablations show that gradient refinement contribute significantly, whereas feeding gradient information into the mutation prompt has no effect.

Critical strengths
  • The paper is generally well-written.
  • The problem is important and timely. Recovering a human-readable generative model from observation is a long-standing goal.
  • By coupling DeGAS’s closed-form likelihood and gradients with LLM-driven structural search, the paper is the first in PP synthesis to separate structure search from parameter fitting.
  • The ablations are well-designed and interseting.
Critical weaknesses
  • Prior work with the same recipe, and the corresponding baseline, are missing. The framework of LLM proposer + program parameter optimization + evolutionary search is the one LLM-SR (ICLR 2025) built on top of FunSearch (2023), yet neither paper appears in the related work. As a result, the statement that natural-language prior injection is a capability no other baseline exposes is overstated, and because the most natural baseline (LLM-SR placed on top of DeGAS) is absent, the value of ALPS’s own mutation design cannot be assessed.
  • Benchmark memorization (contamination) is not addressed. It seems some of the benchmarks' ground-truth programs and datasets have been public on github (https://github.com/schasins/PPL-synthesis). There is no discussion of whether LLM saw these programs during training, nor any control for it (e.g., anonymizing variable names).
Questions for authors

See weaknesses

2 comments
AuthorsOpenReview ↗

Response to Reviewer 5vAm

Missing prior work with the same recipe (FunSearch, LLM-SR) and the corresponding baseline (LLM-SR on top of DeGAS); the claim that natural-language prior injection is unique to ALPS is overstated.

We thank the reviewer for pointing out these related works. We have added FunSearch and LLM-SR to Sec. 2.1, and now position ALPS as following the same recipe (an LLM proposer, parameter optimization and evolutionary search), applied to probabilistic programs. Here candidates are generative models scored by the likelihood of the data, so optimizing their parameters requires a differentiable semantics such as DeGAS; as the reviewer notes, this makes ALPS the first PP synthesis method to separate structure search from parameter fitting. Unlike ALPS, LLM-SR targets symbolic regression: deterministic equations y = f(x; θ) fitted by squared error. It cannot be run as is for PP synthesis, where each candidate is a generative model of the joint distribution, possibly with discrete variables and branching, scored by likelihood. Placing it on top of DeGAS would reuse ALPS's evaluation and gradient refinement and change only how the LLM is prompted and the pool is managed, making it a variant of ALPS rather than an independent baseline. To address the concern behind this request, namely whether ALPS's iterative search adds value beyond what the LLM generates on its own, we added a best-of-N baseline, as also suggested by Reviewer vq7y (new App. D.10): it samples many programs from the same LLM and keeps the best one. Compared with this baseline, ALPS achieves the lowest held-out NLL on 8 of 9 benchmarks and the lowest W₂² on 5 of 9, using the same number of LLM calls and the same total optimization budget.

Finally, we have removed the claim that natural-language prior injection is unique to ALPS, since BoxLM and LLM-SR also accept domain knowledge in natural language.

Contamination is not addressed: some benchmark programs and datasets are public on GitHub, with no discussion or control (e.g., anonymized variable names).

We agree that contamination is a real concern for these benchmarks, and the revised paper now addresses it. We state the limitation explicitly in Sec. 4 and discuss it in App. B. As a control, we re-ran ALPS with every variable renamed to an unrelated common noun everywhere the LLM sees a name (new App. D.9). The results are essentially unchanged: ALPS still achieves the best mean NLL on 8 of 9 benchmarks, and on W₂² it leads on the same four benchmarks as with the original names. Details are in the general response to all reviewers (above).

Dear Reviewer 5vAm,

Thank you again for your review. As the discussion period ends on November 18, we would like to ask whether our response addresses your concerns, in particular the positioning with respect to FunSearch and LLM-SR (Sec. 2.1), and the variable-renaming control (App. D.9). We would be happy to clarify any remaining points.

Best regards, The Authors

Reviewer_vq7yOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper presents a technique called ALPS which builds probabilistic programs from data using an evolutionary loop. The main contribution as mentioned in the paper is in the variation step of the algorithm. Previous evolutionary and MCMC approaches change programs with fixed, syntax-level edits that do not take meaning into account. ALPS uses an LLM as the mutation operator, so it can propose meaningful structural changes like splitting a mixture component or adding a conditional. Gradient descent through DeGAS (a prior work) then fits each candidate's parameters. On nine small benchmarks with 2-4 variables, the paper reports the best log-likelihood on all of them and competitive distance to the true distribution. There's also a small real-data case study on heart disease data.

Critical strengths
  • The paper is well written and easy to follow. The method is simple and the pipeline is clearly explained.

  • The experimental methodology is solid. Results are averaged over 5 seeds with significance tests, and the paper is honest about failures and compute costs.

  • The ablations are fairly comprehensive. They cover gradient refinement, the mutation step, the feedback given to the LLM and the choice of LLM backend

  • The ability to inject domain knowledge as plain-English hypotheses is a nice practical idea.

Critical weaknesses
  • The novelty is limited. Using an LLM as the mutation operator in an evolutionary loop is already well established (FunSearch, AlphaEvolve, etc.), and the main new piece is applying it to probabilistic programs though applying it to probabilistic programs is a useful contribution.

  • The comparison is not fair on model size. ALPS uses a 120B model, while the LLM baselines use a 7B model. The paper explains why, but never runs ALPS with the small model on all benchmarks, so it's hard to tell how much of the gain comes from the bigger model. I understand the limitation with grammar constrained generation. But the authors could 1) show the main results for ALPS for the same model as the baselines. 2) or use other grammar constrained techniques like xgrammar or llguidance that are integrated in common serving engines.

  • Simple best-of-N baseline is missing. Sampling about 40 programs from the same LLM and keeping the best would clearly show if the evolutionary loop actually helps.

  • I believe the "optimization feedback" claim is not fully true. The paper's own ablation shows that giving the LLM the gradient information makes no significant difference (Tables 11 and 12)

  • The benchmarks are tiny and well known, so the LLM may have seen them during training (I understand that this is a limitation of PPL as a field but the authors should clearly mention this limitation)

Minor

  • The introduction has no citations.
Questions for authors
  • How does ALPS do with the same 7B model on all nine benchmarks?
  • How does it compare with a best-of-N sampling baseline using the same number of LLM calls?
  • Did the baselines get the same point-mass hint for discrete variables?
  • Does performance hold up if the variables are renamed?
4 comments
AuthorsOpenReview ↗

Response to Reviewer vq7y

Novelty.

We agree that LLM-guided variation within evolutionary search is well established. We now cite FunSearch, AlphaEvolve and LLM-SR in Sec. 2.1, and position ALPS as an application of this paradigm to probabilistic programs, where candidates are generative models scored by likelihood and fitting their parameters requires a differentiable semantics such as DeGAS. We thank the reviewer for recognizing this application as a useful contribution.

How does ALPS do with the same 7B model as the baselines?

We thank the reviewer for this suggestion. We followed both proposed options. With Qwen2.5-Coder-7B-Instruct, the model used by the RefineStat-based baselines, ALPS converges on five of nine benchmarks and achieves the best NLL and W₂² on all five; its weakness at this scale is producing valid programs (29/45 valid runs). Adding grammar-constrained decoding through llguidance removes this failure: ALPS then converges on all nine benchmarks (44/45 valid runs) and, against the baselines with the same model, achieves the best NLL on seven of nine and the best W₂² on six. We report the full results in the general response to all reviewers (above) and in the new App. E.

Add a baseline: sample ~40 programs from the same LLM and keep the best.

We thank the reviewer for this suggestion. We added a best-of-N baseline (new App. D.10) to test whether ALPS's evolutionary loop improves on simply sampling many programs from the same LLM and keeping the best one.

Each run collects 40 programs from gpt-oss-120b, matching the average number of programs an ALPS run generates. The programs come from 8 independent calls with ALPS's initial prompt, each asking for 5 programs (one per structure type), which matches ALPS's average of LLM calls per run; no call sees the results of another. From the same 40 programs, we report two variants. In both, programs that fail to compile are discarded and the one with the lowest training NLL is evaluated on held-out data:

  • No fit: each program is scored at the parameter values written by the LLM.
  • Equal compute: each program is fitted by gradient descent with ALPS's optimizer settings, using an equal share of the total number of gradient steps ALPS uses on that benchmark.

ALPS achieves the lowest held-out NLL on 8 of 9 benchmarks. The exception is MoG, where the equal-compute baseline is lower (6.43 vs. 6.65), although ALPS has the best W₂² there. ALPS also has the lowest W₂² on 5 of 9 benchmarks. Since the equal-compute baseline uses the same LLM calls and the same total optimization budget, the gap in likelihood reflects how ALPS's loop uses that budget, not additional computation: independent sampling with uniform fitting does not match ALPS's likelihood fit.

The "optimization feedback" claim is not supported by the ablation.

We thank the reviewer for this observation, which we agree with. We have revised the abstract, introduction, Sec. 4 and conclusions accordingly. The revised claim is that the LLM mutates candidates whose parameters have already been fitted by gradient refinement and which were selected by their refined likelihood. Optimization therefore shapes the search through parameter fitting and selection, not through the diagnostics shown in the prompt.

The introduction has no citations.

We have added citations throughout the introduction, covering probabilistic programming, prior PP synthesis approaches (MCMC-based, evolutionary and constrained decoding), LLMs for code and LLM-guided model discovery, DeGAS, and the sources of our benchmarks.

Did the baselines get the same point-mass hint?

The point-mass guidance is part of ALPS's system prompt, and the baselines do not receive it. However, they search the same DeGAS language, in which discrete variables are expressible, for example as zero-variance mixture components or constant assignments, so they can produce such programs as well. The Evolutionary baseline, for instance, does so on CSI and Hurricane, where it reaches an NLL close to ALPS's and the best W₂² of all methods. Moreover, on the three purely continuous benchmarks (If, MoG, MultiBranch), where point masses play no role, ALPS has the best NLL, significantly against all four baselines (Table 6).

Benchmarks are tiny and well known, so the LLM may have seen them; state this limitation. Do results hold if variables are renamed?

We agree and thank the reviewer. We now state this limitation explicitly in Sec. 4 and discuss it in App. B. Following the reviewer's suggestion, we re-ran ALPS with every variable renamed to an unrelated common noun (new App. D.9; more details in the general response to all reviewers). Performance holds up: with anonymized names, ALPS still achieves the best mean NLL on 8 of 9 benchmarks (on Hurricane it is 0.04 behind Evolutionary, within run-to-run spread), and on W₂² it leads on the same four benchmarks as with the original names.

Dear Reviewer vq7y,

Thank you again for your review. As the discussion period ends on November 18, we would like to ask whether our response addresses your questions, in particular ALPS with the same 7B model (App. E), the best-of-N baseline (App. D.10), and the variable-renaming control (App. D.9). We would be happy to clarify any remaining points.

Best regards, The Authors

Thanks for addressing my concerns. The additional results using the same LLM for the baseline added in App E are useful for the comparison. The new results with ALPS + Grammar constrainer decoding are impressive. I would encourage the authors to move some of these results up in the main paper.

Dear Reviewer vq7y,

Thank you for your positive feedback. We agree that the comparison with the same LLM strengthens the paper, and we will move these results, including ALPS with grammar-constrained decoding, from the appendix into the main text.

Best regards, The Authors

Comments on the paper

2 comments
AuthorsOpenReview ↗

General response to all reviewers

We thank all the reviewers for their careful reading and constructive feedback, which has substantially improved the paper. All changes in the revised PDF are highlighted in magenta. Two concerns were raised by several reviewers, so we address them here.

1. Fairness of the comparison with respect to LLM size

A question shared by several reviewers concerns the fairness of the comparison with respect to the size of the LLM. In the main experiments, ALPS uses gpt-oss-120b, while the RefineStat-based baselines (RS-MCMC and RS-Grad) use Qwen2.5-Coder-7B-Instruct, because their grammar-constrained decoding requires a model loaded locally. To separate the contribution of the search from that of the LLM, we ran two new experiments, now reported in App. E.

ALPS with the 7B model. We re-ran ALPS on all nine benchmarks with Qwen2.5-Coder-7B-Instruct (5 runs per benchmark, all other settings unchanged). On the five benchmarks where it converges, ALPS achieves the best NLL and W₂² of all methods using this model. At 7B, its weakness is generating valid programs, not the search itself: on the other benchmarks, the small model often leaves variables out of its first programs, so only some runs produce a valid candidate (29/45 runs overall, vs. 43/45 for RS-Grad and 39/45 for RS-MCMC). RefineStat's constrained decoding rules out this failure by construction, since it only accepts a program once every variable is defined. With gpt-oss-120b, ALPS converges in all 45 runs.

ALPS with the 7B model and grammar-constrained decoding. To remove this failure mode, we coupled ALPS with grammar-constrained decoding through llguidance, which forces every LLM response to be a well-formed JSON object whose programs are syntactically valid DeGAS. The grammar also enforces four semantic checks: a variable is defined before it is used; conditions test only variables that are already defined; after an if/else, a variable counts as defined only if both branches define it; and every dataset variable is defined by the end of the program. Prompts, the mutation loop, gradient fitting and early stopping are unchanged.

With the constraint, ALPS with the 7B model converges on all nine benchmarks (44/45 valid runs, against 29/45 without it). Compared with the RefineStat-based baselines, with the same model and constrained decoding in both, it has the best NLL on seven of nine benchmarks and the best W₂² on six. ALPS with gpt-oss-120b remains the strongest configuration overall, with the lowest NLL on eight of nine benchmarks and the lowest W₂² on five, more than either 7B variant.

2. Possible training-data contamination

Some reviewers pointed out that the benchmarks are small and well known, so the LLM may have seen them during training. We agree, and now state this limitation explicitly in Sec. 4 and discuss it in App. B. To test whether ALPS benefits from recognizing benchmarks, we re-ran it with every variable renamed to an unrelated common noun (new App. D.9). The new names are lowercase words with no digits or symbols, whose alphabetical order does not follow the data columns (e.g., in EasyTugWar, skill1, skill2 and p1wins become pepper, almond and candle). The LLM (gpt-oss-120b), prompts, mutation loop and fitting are unchanged.

The main conclusions are unchanged. With anonymized names, ALPS still achieves the best mean NLL on 8 of 9 benchmarks. On W₂², it leads on the same four benchmarks as with the original names. The largest drop is on EyeColor, where the original names plausibly help by signalling that the variables are categorical, yet ALPS remains the best method there. This makes it unlikely that ALPS's results stem from recognizing benchmarks by name. Since this does not rule out every form of contamination, we list newly designed target programs as future work.

AuthorsOpenReview ↗

General response (additional results): likelihood and discrete variables.

We would like to share one additional experiment, prompted by Reviewer 5rqJ’s question on whether the likelihood reflects model quality rather than how discrete variables are written. In DeGAS, a discrete variable modelled by a near-zero-variance Gaussian receives a density that grows without bound as the variance shrinks, which favours programs that use point masses. We therefore computed a corrected likelihood: for the variables that are discrete in the data-generating process, the density of each mixture component is integrated over the unit interval around the observed value, conditioning on the continuous variables, so that the discrete part becomes a probability mass. On purely continuous benchmarks it coincides with the original likelihood.

Re-evaluating the programs of all methods, including the original ALPS runs, with the corrected likelihood, ALPS remains best on 6 of 9 benchmarks. Since those ALPS runs had searched with the uncorrected likelihood, we re-ran ALPS with the corrected likelihood as its objective: it then has the best NLL on all nine benchmarks. The baselines either already search with an equivalent likelihood or have been re-run with it, except RS-Grad, which could not be re-run within the discussion period due to time constraints. We report this analysis in the new App. F; in the final version we will include RS-Grad and qualify our claims accordingly.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.