PPDL: LLM-Based Flows as Probabilistic Programs

Building reliable applications with Large Language Models (LLMs) is difficult because individual model outputs are often inaccurate and lack inherent measures of confidence. When these models are chained together in multi-step flows, uncertainty compounds, making it hard for developers to trust the final results. This paper addresses the challenge of making these LLM-based flows more reliable and interpretable.

The authors introduce PPDL, a probabilistic programming language designed specifically for LLM-based flows. PPDL extends existing prompt programming paradigms by adding a factor construct, which allows developers to assign scores to execution traces based on soft or hard constraints. By treating an LLM-based flow as a probabilistic program, PPDL enables the runtime to explore a distribution of possible execution traces rather than just a single path. This framework decouples the core program logic from the inference scaling strategy, allowing developers to swap between different inference engines—such as majority voting, importance sampling, or particle filtering—without modifying the underlying flow logic.

PPDL provides a principled way to track uncertainty across complex LLM workflows. The authors demonstrate that by using factor to incorporate constraints (e.g., using an LLM-as-a-judge or rule-based linters), the system can effectively estimate the posterior distribution of outputs. This allows the system to identify high-probability, correct solutions even when they are not the most frequent output. The paper validates this approach through an experimental study across various benchmarks and a practical case study involving a theorem-proving agent for the Rocq theorem prover, showing that the language is both versatile and effective for complex agentic tasks.

As LLMs are increasingly used in multi-step, agentic workflows, the need for reliability and uncertainty quantification becomes critical. PPDL offers a significant step forward by formalizing the interaction between prompt-based sampling and probabilistic inference. By providing a unified framework that handles the complexity of inference scaling, PPDL allows researchers and developers to build more robust applications while gaining visibility into the confidence of the generated outputs.