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

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.