Probabilistic Programs of Thought

Poorva Garg, Renato Lui Geh, Daniel Israel, Todd Millstein, Kyle Richardson, Guy Van den BroeckarXiv 2026 · arXiv

TL;DR

Generating multiple code samples from Large Language Models (LLMs) to find a correct solution is highly effective but incredibly GPU-intensive. Probabilistic Programs of Thought (PPoT) solves this by turning a single LLM-generated program into a probabilistic program using the model's own token probabilities. This allows engineers to cheaply sample exponentially many variations of a program on the CPU with zero extra GPU compute, boosting accuracy by up to 7%.

What Problem Does This Paper Address?

When LLMs are used for code generation or mathematical reasoning (via "programs of thought"), they often make minor, fatal mistakes—like using the wrong arithmetic operator or miscalculating a single constant. The standard workaround is Best-of-n sampling: generate $n$ independent programs, execute them, and pick the one that works.

However, each new sample requires a full, autoregressive GPU generation pass. For large models, generating dozens of samples per problem becomes prohibitively expensive. The authors address this bottleneck by asking: Can we generate diverse alternate programs without re-running the LLM on the GPU?

Methods

The authors introduce a test-time decoding framework called Probabilistic Programs of Thought (PPoT).

Instead of discarding the next-token probabilities (logits) after an LLM finishes generating a piece of code, PPoT preserves them. The framework performs a "token analysis" to identify key program components—specifically digits, arithmetic operators, comparison operators, and assignment operators.

PPoT then converts these specific tokens into categorical random variables parameterized by the LLM's original logits. This transforms the deterministic script into a probabilistic program that implicitly represents exponentially many variations of the code.

New variations are sampled directly from this probabilistic program on the CPU. To ensure the framework doesn't just keep regenerating the exact same code, the authors introduce a specialized sampling algorithm that conditions the generation on not reproducing previously seen samples.

[Standard LLM Generation] 
       │
       ▼
Deterministic Program + Logits
       │
       ▼ (Token Analysis & Compilation)
Probabilistic Program (Key tokens become Random Variables)
       │
       ▼ (Cheap CPU Inference)
Exponentially many alternate programs sampled for free!

Datasets

The authors evaluated PPoT using Qwen2.5 Coder (0.5B, 3B, 7B) and Qwen2.5 VL (3B, 7B) across three distinct benchmarks:

  • GSM8k: A standard dataset of grade-school math word problems, solved by generating Python code.
  • Plot2Code: A multimodal benchmark where the model must write matplotlib code to replicate a scientific plot image.
  • CRUXEval: A code reasoning and program inversion benchmark where the model must deduce the correct input to a Python function given its output.

Key Insights and Ideas

  • The LLM's Uncertainty is an Asset: When an LLM generates an incorrect program, the correct token is often sitting just below the surface in the top-k logit distribution. PPoT exposes and exploits this latent distribution.
  • Local Sensitivity of Code: Program execution is highly sensitive to minor local changes. Changing a single + to a - or a 0 to a 1 can completely fix a broken program. PPoT targets exactly these high-leverage points.
  • Exponential Space for Free: A single probabilistic program can compactly represent $2^V$ (where $V$ is the number of random variables) deterministic programs. Sampling from this structured space on a CPU takes milliseconds, bypassing the massive matrix multiplications of an LLM forward pass.

Key Results

  • Consistent Performance Gains: Across all benchmarks and model sizes, adding just $m=5$ PPoT samples per LLM generation consistently boosted accuracy. For instance, it raised Qwen2.5 Coder 0.5B's GSM8k accuracy from 24.94% to 28.51%.
  • Massive Compute Savings: On GSM8k, PPoT achieved the same accuracy with 8 LLM generations that standard sampling required 20 LLM generations to reach.
  • High "Effective" Sample Yield: Using a scaling law analysis, the authors showed that for 20 LLM samples, generating 20 PPoT variations per sample yielded an accuracy boost equivalent to running ~39 additional full LLM generations—at near-zero computational cost.

Limitations and Future Work

  • The Single-Token Constraint: Currently, PPoT only converts program components contained within a single token (e.g., single digits or basic operators) into random variables. Converting multi-token components (like multi-digit variables or entire function names) requires computing marginal distributions over sequences, which is theoretically #P-hard.
  • Independence Assumption: To make sampling tractable, PPoT assumes that tokens succeeding a resampled token are independent of it. While the authors prove this is robust enough to work well in practice, it is an approximation of the LLM's true autoregressive nature.
  • Future Directions: The authors plan to expand the framework to handle more complex structures like entire sub-expressions and control flow blocks, as well as using PPoT to compute expectations directly from code distributions.

Summary updated

Abstract

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.
BibTeX
@misc{garg2026probabilistic,
  author = {Poorva Garg and Renato Lui Geh and Daniel Israel and Todd Millstein and Kyle Richardson and Guy Van den Broeck},
  title = {{Probabilistic Programs of Thought}},
  year = {2026},
  eprint = {2604.17290},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2604.17290},
}

Loading related content...

Figure