PPDL: LLM-Based Flows as Probabilistic Programs

Building reliable applications that leverage large language models (LLMs) remains a significant challenge. While LLMs offer impressive capabilities across diverse tasks, their outputs often lack accuracy and provide no clear measure of confidence. This uncertainty compounds in flows of multiple calls to LLMs and other tools, making it difficult for developers and end-users to trust the results. This paper introduces a probabilistic language for programming LLM-based flows. It enables developers to quantify and propagate uncertainty throughout the application's flow, and experiment with different inference scaling techniques without adding a single line of code beyond the flow's logic. We present an experimental study to demonstrate this capability, and a case study building a theorem proving agent for the Rocq theorem prover.

When building applications that chain multiple large language model (LLM) calls together, for example by first creating a plan and then generating code, uncertainty compounds at each step. Current solutions that run tasks multiple times to improve accuracy are complicated to implement and don't show users how confident the system is. We introduce PPDL, a programming language designed to make these applications more reliable and transparent. Instead of producing just one answer, PPDL generates a distribution of answers (i.e., several possible answers along with how likely each one is). Developers write their workflow once, while PPDL automatically explores different possibilities and evaluates them using checks, such as tests or automated reviews. PPDL offers three main benefits. (1) Flexibility: developers can swap between majority voting, importance sampling, and particle filtering without rewriting their programs. (2) Accuracy: across tasks like math problem solving and code generation, PPDL shows consistent improvements in our experiments over single runs or majority voting, and we use it to build a proof-search agent for the Rocq theorem prover. (3) Transparency: by showing multiple answers and their likelihoods, PPDL helps users understand how confident the system is and make more informed decisions. This helps make LLM-based applications more trustworthy in practice.