Reproduce “Probabilistic Programs of Thought” on OpenResearch

About this paper

Poorva Garg, Renato Lui Geh, Daniel Israel, Todd Millstein, Kyle Richardson, Guy Van den Broeck

The paper introduces Probabilistic Programs of Thought (PPoT), which reuses next-token probabilities from generated code to sample program variants without another language-model generation. In a GSM8k comparison, Qwen2.5 Coder 0.5B accuracy rose from 42.53% to 49.13% with five LLM samples and added PPoT samples. This improves best-of-set results, not individual-program accuracy, with more candidates to execute and verify.

Key insights

• An LLM's autoregressive generation process inherently models a probability distribution over token sequences, which can be explicitly captured and reused post-generation.
• Transforming an LLM's output into a probabilistic program allows for a compact representation of exponentially many alternative programs from a single, costly LLM inference.
• The approach provides distributionally sound samples with respect to the original LLM, under specific independence assumptions, enabling reliable exploration of the solution space.

Summary by alphaXiv.