# Probabilistic Programs of Thought

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 28 of its 56 references that are in the map.
- First posted on arXiv 19 Apr 2026.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)

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

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Qwen2.5-VL Technical Report](https://mlsanity.com/paper/2502.13923/) (2025)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Qwen2.5-Coder Technical Report](https://mlsanity.com/paper/2409.12186/) (2024)
- [Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks](https://mlsanity.com/paper/2211.12588/) (2022)
- [DSPy: Compiling Declarative Language Model Calls into Self-Improving Pipelines](https://mlsanity.com/paper/2310.03714/) (2023)
- [CRUXEval: A Benchmark for Code Reasoning, Understanding and Execution](https://mlsanity.com/paper/2401.03065/) (2024)
- [RL with KL penalties is better viewed as Bayesian inference](https://mlsanity.com/paper/2205.11275/) (2022)
- [From Word Models to World Models: Translating from Natural Language to the Probabilistic Language of Thought](https://mlsanity.com/paper/2306.12672/) (2023)
- [Language Model Cascades](https://mlsanity.com/paper/2207.10342/) (2022)
- [Sequential Monte Carlo Steering of Large Language Models using Probabilistic Programs](https://mlsanity.com/paper/2306.03081/) (2023)
- [Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo](https://mlsanity.com/paper/2504.13139/) (2025)
- [How Do Large Language Monkeys Get Their Power (Laws)?](https://mlsanity.com/paper/2502.17578/) (2025)
- [DSPy Assertions: Computational Constraints for Self-Refining Language Model Pipelines](https://mlsanity.com/paper/2312.13382/) (2023)
- [A Pseudo-Semantic Loss for Autoregressive Models with Logical Constraints](https://mlsanity.com/paper/2312.03905/) (2023)
- [Sample, Don't Search: Rethinking Test-Time Alignment for Language Models](https://mlsanity.com/paper/2504.03790/) (2025)
- [Plot2Code: A Comprehensive Benchmark for Evaluating Multi-modal Large Language Models in Code Generation from Scientific Plots](https://mlsanity.com/paper/2405.07990/) (2024)
- [BIRD: A Trustworthy Bayesian Inference Framework for Large Language Models](https://mlsanity.com/paper/2404.12494/) (2024)
- [Probabilistic Soundness Guarantees in LLM Reasoning Chains](https://mlsanity.com/paper/2507.12948/) (2025)
- [NAVER: A Neuro-Symbolic Compositional Automaton for Visual Grounding with Explicit Logic Reasoning](https://mlsanity.com/paper/2502.00372/) (2025)
- [Large Language Bayes](https://mlsanity.com/paper/2504.14025/) (2025)
- [NePTune: A Neuro-Pythonic Framework for Tunable Compositional Reasoning on Vision-Language](https://mlsanity.com/paper/2509.25757/) (2025)
- [Scaling Integer Arithmetic in Probabilistic Programs](https://mlsanity.com/paper/2307.13837/) (2023)
- [RefineStat: Efficient Exploration for Probabilistic Program Synthesis](https://mlsanity.com/paper/2509.01082/) (2025)
- [Likelihood Hacking in Probabilistic Program Synthesis](https://mlsanity.com/paper/2603.24126/) (2026)
- [Enhancing Visual Programming for Visual Reasoning via Probabilistic Graphs](https://mlsanity.com/paper/2512.14257/) (2025)

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

- [Verifier-Guided Code Translation via Meta-Step Decoding](https://mlsanity.com/paper/2605.17626/) (2026)

## Abstract (arXiv)

LLMs are widely used for code generation and mathematical reasoning tasks where they are required to generate structured output. They either need to reason about code, generate code for a given specification, or reason using programs of thought. The typical approach to code generation is to prompt the model and generate samples until an appropriate program is obtained. Within this process, sampling n programs from the language model requires n GPU compute-intensive generations which becomes prohibitively expensive for larger values of n. In this work, we address this limitation by exposing the LLM's distribution within the generated programs themselves. We propose a novel test-time framework we dub probabilistic programs of thought to obtain more samples from the model with fewer LLM generations. Given a program generated by a model and the associated next-token probabilities, we build a probabilistic program that compactly represents exponentially many deterministic programs. Since performing probabilistic reasoning in this probabilistic program is much cheaper, our approach allows sampling new programs without any additional GPU compute and little CPU overhead. We instantiate our approach on benchmarks for code generation, code understanding and mathematical reasoning and report improvements in performance with fewer generations from the LLM.