# RefineStat: Efficient Exploration for Probabilistic Program Synthesis

arXiv: https://arxiv.org/abs/2509.01082 · HTML: https://mlsanity.com/paper/2509.01082/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 65 references that are in the map.
- First posted on arXiv 1 Sep 2025.

## Builds on (most cited first, 29 of 29)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Qwen2.5-Coder Technical Report](https://mlsanity.com/paper/2409.12186/) (2024)
- [Pyro: Deep Universal Probabilistic Programming](https://mlsanity.com/paper/1810.09538/) (2018)
- [A Conceptual Introduction to Hamiltonian Monte Carlo](https://mlsanity.com/paper/1701.02434/) (2017)
- [Efficient Guided Generation for Large Language Models](https://mlsanity.com/paper/2307.09702/) (2023)
- [Composable Effects for Flexible and Accelerated Probabilistic Programming in NumPyro](https://mlsanity.com/paper/1912.11554/) (2019)
- [Time Travel in LLMs: Tracing Data Contamination in Large Language Models](https://mlsanity.com/paper/2308.08493/) (2023)
- [Synchromesh: Reliable code generation from pre-trained language models](https://mlsanity.com/paper/2201.11227/) (2022)
- [CodeGemma: Open Code Models Based on Gemma](https://mlsanity.com/paper/2406.11409/) (2024)
- [Generalization or Memorization: Data Contamination and Trustworthy Evaluation for Large Language Models](https://mlsanity.com/paper/2402.15938/) (2024)
- [Practical Bayesian model evaluation using leave-one-out cross-validation and WAIC](https://mlsanity.com/paper/1507.04544/) (2015)
- [Rank-normalization, folding, and localization: An improved widehatR for assessing convergence of MCMC](https://mlsanity.com/paper/1903.08008/) (2019)
- [Structure Discovery in Nonparametric Regression through Compositional Kernel Search](https://mlsanity.com/paper/1302.4922/) (2013)
- [XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models](https://mlsanity.com/paper/2411.15100/) (2024)
- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [An Introduction to Probabilistic Programming](https://mlsanity.com/paper/1809.10756/) (2018)
- [Automata-based constraints for language model decoding](https://mlsanity.com/paper/2407.08103/) (2024)
- [Bayesian Workflow](https://mlsanity.com/paper/2011.01808/) (2020)
- [Estimating Contamination via Perplexity: Quantifying Memorisation in Language Model Evaluation](https://mlsanity.com/paper/2309.10677/) (2023)
- [Data Contamination Quiz: A Tool to Detect and Estimate Contamination in Large Language Models](https://mlsanity.com/paper/2311.06233/) (2023)
- [Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo](https://mlsanity.com/paper/2504.13139/) (2025)
- [Automated Statistical Model Discovery with Language Models](https://mlsanity.com/paper/2402.17879/) (2024)
- [CRANE: Reasoning with constrained LLM generation](https://mlsanity.com/paper/2502.09061/) (2025)
- [Type-Constrained Code Generation with Language Models](https://mlsanity.com/paper/2504.09246/) (2025)
- [Validating Large Language Models with ReLM](https://mlsanity.com/paper/2211.15458/) (2022)
- [Bayesian Synthesis of Probabilistic Programs for Automatic Data Modeling](https://mlsanity.com/paper/1907.06249/) (2019)
- [Semantic Probabilistic Control of Language Models](https://mlsanity.com/paper/2505.01954/) (2025)
- [Counterexample-Driven Synthesis for Probabilistic Program Sketches](https://mlsanity.com/paper/1904.12371/) (2019)

## Built on by (most cited first, 5 of 5)

- [Enforcing Temporal Constraints for LLM Agents](https://mlsanity.com/paper/2512.23738/) (2025)
- [Likelihood Hacking in Probabilistic Program Synthesis](https://mlsanity.com/paper/2603.24126/) (2026)
- [AdaptFuse: Training-Free Sequential Preference Inference via Externalized Bayesian Computation](https://mlsanity.com/paper/2604.03925/) (2026)
- [Probabilistic Programs of Thought](https://mlsanity.com/paper/2604.17290/) (2026)
- [Imprompt: A Language Framework for Prompt Programming](https://mlsanity.com/paper/2607.22683/) (2026)

## Abstract (arXiv)

Probabilistic programming offers a powerful framework for modeling uncertainty, yet statistical model discovery in this domain entails navigating an immense search space under strict domain-specific constraints. When small language models are tasked with generating probabilistic programs, they frequently produce outputs that suffer from both syntactic and semantic errors, such as flawed inference constructs. Motivated by probabilistic programmers' domain expertise and debugging strategies, we introduce RefineStat, a language model--driven framework that enforces semantic constraints ensuring synthesized programs contain valid distributions and well-formed parameters, and then applies diagnostic-aware refinement by resampling prior or likelihood components whenever reliability checks fail. We evaluate RefineStat on multiple probabilistic-programming code-generation tasks using smaller language models (SLMs) and find that it produces programs that are both syntactically sound and statistically reliable, often matching or surpassing those from closed-source large language models (e.g., OpenAI o3).