🤖 machine learning

PPDL: LLM-Based Flows as Probabilistic Programs

This paper introduces PPDL, a probabilistic programming language that enables developers to quantify and propagate uncertainty across LLM-based application flows and experiment with inference scaling techniques without modifying the core logic, as demonstrated through a theorem proving agent for the Rocq prover.

Original authors: Louis Mandel, Guillaume Baudart, Mandana Vaziri, Martin Hirzel

Published 2026-08-07

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Louis Mandel, Guillaume Baudart, Mandana Vaziri, Martin Hirzel

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a really tricky puzzle, but instead of doing it alone, you have a super-smart, creative friend who can talk to you. This friend is an Artificial Intelligence called a Large Language Model (LLM). They are amazing at writing stories, solving math problems, and even writing computer code. However, they aren't perfect. Sometimes they get confident about the wrong answer, or they might make up facts that sound real but aren't. This is called "uncertainty."

Now, imagine you need to solve a really hard problem that requires many steps. You ask your AI friend for a plan, then ask them to write code based on that plan, then ask them to check the code, and so on. Every time you ask a question, the AI gives an answer, but that answer might be slightly shaky. If you chain ten of these shaky answers together, the final result could be a total mess. It's like trying to build a tower of Jenga blocks where every block is slightly wobbly; the higher you go, the more likely the whole thing is to collapse. Developers and users often feel lost here: "Is this answer right? How sure are we? Should I trust it?"

To fix this, scientists have tried a few tricks. One popular idea is "inference scaling." Think of this as asking your AI friend to try the same puzzle ten different times and seeing which answer comes up most often. It's like asking a group of friends to guess the answer to a riddle and going with the majority vote. But here's the catch: doing this manually is messy. You have to write special computer code to run those ten tries, keep track of which ones look good, and throw away the bad ones. It's like having to build a new factory every time you want to bake a batch of cookies just to make sure they taste right. It's complicated, expensive, and hard to change if you want to try a different way of baking.

The Paper's Big Idea: The "Magic Scorecard"

This paper introduces a new tool called PPDL (Probabilistic Prompt Declaration Language). You can think of PPDL as a special "magic scorecard" for AI workflows. Instead of just asking the AI a question and getting a single answer, PPDL lets you write a program that naturally understands that the AI might be unsure.

Here is how it works in plain language:

The Flow: You write your instructions for the AI just like you normally would (e.g., "Plan the code," then "Write the code," then "Check the code").
The Magic Factor: You add a special instruction called a factor. This is like a scorecard where you tell the AI, "Hey, if the plan sounds logical, give it a high score. If the code has errors, give it a low score."
The Result: When you run the program, the computer doesn't just give you one answer. It runs the whole process many times in parallel (like having a hundred different versions of you trying the puzzle at once). It uses your "scorecard" to weigh the results. If one path looks really promising, the computer focuses more energy on that path. If a path looks bad, it drops it.

The coolest part is that you don't have to write the complex "run it ten times" code yourself. PPDL handles all that heavy lifting in the background. You just write the logic once, and the system automatically figures out the best way to explore all the possibilities.

What They Found

The authors tested this idea on several challenges, from solving grade-school math problems to writing complex computer code and even proving mathematical theorems.

Better Accuracy: In their tests, using PPDL with these "scorecards" made the AI significantly more accurate. For example, on a math test called GSM8k, a standard AI got about 83.8% of the answers right. But when they used PPDL with a method called "Importance Sampling" (which is like a smart way of picking the best guesses), the accuracy jumped to 93.7%.
The "Smart" Way Wins: They compared different ways of using the scorecards. Sometimes, just taking the "majority vote" (the most common answer) worked well. But often, the smarter methods (like Importance Sampling and Sequential Monte Carlo) were much better. These methods are like having a detective who doesn't just count votes but actually investigates why an answer is good or bad, discarding bad paths early and focusing on the good ones.
The Theorem Prover Case Study: To really stress-test the system, they built an AI agent to prove mathematical theorems using a tool called Rocq. This is a very hard task where the AI has to write a proof, check if it's wrong, and fix it repeatedly. They found that the "smart" method (Sequential Monte Carlo) was much better at finding the right proof than just trying random guesses over and over. It could explore many different paths at once and quickly abandon the ones that were going nowhere.

What They Didn't Claim

The authors are careful not to say this is a "magic bullet" that solves everything. They point out that the "scorecards" (the factors) are only as good as the information you put into them. If your scorecard is bad, the system won't magically fix it. Also, while this method makes the AI more reliable, it doesn't mean the AI is suddenly perfect; it just means we have a much better way to measure how sure we should be about the answer.

Why It Matters

This paper suggests that by treating AI workflows as "probabilistic programs" (programs that understand uncertainty), we can make AI applications much more trustworthy without making them incredibly complicated to build. It's like giving developers a new set of tools that automatically handle the messy business of "trying again and again," so they can focus on building cool things while the computer figures out the best way to get the right answer.

Technical Summary: PPDL: LLM-Based Flows as Probabilistic Programs

Problem Statement

Building reliable applications using Large Language Models (LLMs) is challenging due to the inherent uncertainty and lack of confidence metrics in LLM outputs. This issue is exacerbated in "flows"—sequences of multiple LLM calls and tool interactions—where uncertainty compounds along the execution trace. While inference scaling techniques (e.g., repeating tasks, using verifiers) can improve accuracy, current implementations are often ad hoc, tightly coupled with program logic, and lack a principled framework for tracking uncertainty or exploring alternative execution paths. Developers struggle to assess the correctness of answers or experiment with different scaling strategies without rewriting core flow logic.

Methodology

The paper introduces PPDL (Probabilistic Prompt Declaration Language), the first probabilistic programming language specifically designed for LLM-based flows. PPDL unifies prompt programming with probabilistic programming by decoupling the core program logic from the inference scaling strategy.

Core Language Constructs

PPDL is built upon PDL (Prompt Declaration Language), a declarative language for composing LLM and tool calls. PPDL extends PDL with a single, orthogonal primitive: factor.

sample (Implicit): LLM calls act as sampling operations from a distribution defined by the model and current context.
factor: This construct updates the probability of the current execution trace based on user-specified constraints (soft or hard). Constraints can be derived from LLM-as-a-judge evaluations, rule-based tools (e.g., linters, test suites), or process reward models.
Execution Model: Instead of returning a single output, PPDL treats the program as a distribution over execution traces. The runtime explores this distribution using probabilistic inference engines.

Semantics and Inference

The paper formalizes PPDL's semantics as a weighted sampler.

Weighted Sampler: A single execution trace reduces a program $p$ to a value $v$ with an associated log-score (accumulated from factor statements).
Ideal Semantics: Defined as an infinite sum over all possible traces, normalized to form a categorical distribution over output values.
Approximate Inference: Since the ideal semantics are intractable, PPDL implements Monte Carlo approximation algorithms:
- Importance Sampling (IS): Executes $N$ independent particles (traces) and reweights them based on their final scores.
- Sequential Monte Carlo (SMC): Introduces resampling steps at factor points. Particles with low scores are discarded, and those with high scores are duplicated, allowing the system to focus computational resources on promising partial traces early in the flow.
- Majority Voting: A baseline where all particles are weighted equally.

Implementation

PPDL is an interpreted language implemented with parallelization.

Parallelism: Independent particles are executed in parallel. Within a single particle, independent model calls are parallelized using futures and deferred data structures to minimize blocking.
Orthogonality: Users write the flow logic once. The inference algorithm (IS, SMC, or Majority Voting) and particle count are configured at runtime without modifying the source code.

Key Contributions

PPDL Language: The first probabilistic prompt programming language for flows of LLM and tool calls, introducing factor as a mechanism to score and steer execution traces.
Formal Semantics: A rigorous definition of PPDL's behavior, formalizing the interplay between prompt-based sampling and probabilistic factors, and defining the resulting distribution of traces.
Inference Scaling Framework: A demonstration that PPDL enables systematic experimentation with different inference scaling algorithms (IS, SMC, Majority Voting) across various models and tasks without rewriting flow logic.
Case Study: Implementation of a theorem proving agent for the Rocq theorem prover, showcasing the utility of probabilistic inference in complex, iterative agent workflows.

Experimental Results

The authors evaluated PPDL across multiple benchmarks (GSM8k, Math500, MBPP, LiveCodeBench, Fever) and models (Granite, Llama, GPT-OSS).

Accuracy Improvements: Inference scaling generally outperformed the baseline (single execution, IS@1). While Majority Voting performed well in some cases, Importance Sampling (IS) and Sequential Monte Carlo (SMC) often yielded superior results, particularly when factor constraints provided meaningful information to distinguish correct from incorrect traces.
SMC Advantage: In complex, multi-step flows (like theorem proving), SMC significantly outperformed IS. By resampling at intermediate factor points, SMC could redirect computation toward promising paths earlier, avoiding the waste of tokens on incorrect partial traces.
Theorem Proving Case Study: In the MiniF2F-Rocq benchmark, SMC with 40 particles solved 39% of problems (95/244), compared to 30% (72.7/244) for the baseline IS@1 strategy, all within a fixed token budget. This demonstrated that probabilistic steering could improve base model performance on challenging tasks.

Significance and Claims

The paper claims that PPDL provides a principled way to handle uncertainty in LLM applications. By treating LLM flows as probabilistic programs, it allows developers to:

Quantify Uncertainty: Users receive a distribution of outputs, enabling them to assess confidence rather than relying on a single, potentially erroneous answer.
Experiment Efficiently: Developers can switch between inference scaling strategies (e.g., from simple voting to complex SMC) by changing runtime configuration rather than refactoring code.
Decouple Logic from Search: The separation of core flow logic from the search strategy (inference engine) simplifies the development of robust agentic workflows.

The authors acknowledge that inference scaling is not a "silver bullet" and that the quality of results depends on the quality of the constraints (factors) provided, which may be imperfect. However, PPDL offers a flexible framework to integrate and test various constraint sources and inference algorithms.