Technical Summary: Predicting Performance of Symbolic and Prompt Programs with Examples

Problem Statement

Large Language Model (LLM) prompting is widely adopted for naturally stated tasks but suffers from unreliability; a prompt may pass a few test cases yet fail unpredictably at deployment. In contrast, symbolic programs (e.g., Python, regex) are often considered trustworthy once they pass a few representative test cases. This paper investigates the fundamental question: Why do a few passing tests certify symbolic programs but not prompt programs?

The authors frame this as a performance prediction problem: given a program (either symbolic or a prompt executed by an LLM) and a small set of in-domain execution outcomes (pass/fail), predict its true performance ($\theta$) on unseen tasks from the same domain. The goal is to infer a posterior distribution over the program's success rate to determine deployability and confidence levels.

Methodology

1. Theoretical Framework: The Coin-Flip Model

The authors adopt a Bayesian approach, modeling each program execution on a test case as an independent Bernoulli random variable (a "coin flip").

• Observation ($O$): A set of $a$ passes and $b$ fails.
• Likelihood: $P(O|\theta) \propto \theta^a (1-\theta)^b$.
• Posterior: $P(\theta|O) \propto P(\theta) \cdot \theta^a (1-\theta)^b$.

The critical insight is that while the likelihood is easily computed, the performance prior $P(\theta)$ is unknown and dictates the posterior distribution. The paper argues that the difference in predictability between symbolic and prompt programs stems entirely from the shape of their respective priors.

2. Empirical Performance Priors

To understand the priors, the authors compiled a corpus of 700 symbolic programs (sp) and 700 prompt programs (pp) across diverse domains (e.g., Regex, HumanEval, ARC, List Rules). They evaluated each program on 100 sampled instances to estimate its true performance.

• Symbolic Programs (sp): Exhibit an "all-or-nothing" prior. The distribution is sharply bimodal, concentrated near $\theta=0.0$ (completely incorrect) and $\theta=1.0$ (perfect).
• Prompt Programs (pp): Exhibit a diffuse prior. There is substantial mass on intermediate performance values, representing "nearly-correct" programs that may pass a few tests by luck but fail on others.

Implication: For symbolic programs, a few successes shift the posterior mass rapidly toward 1.0, providing high confidence. For prompt programs, the same successes only slightly shift the diffuse prior, leaving the true performance uncertain.

3. RAP (Retrieved Approximate Prior)

To address the difficulty of predicting prompt program performance, the authors propose RAP, a retrieval-based method to construct a task-specific prior.

• Input: A target prompt program ($p_{target}$), a set of observed in-domain examples ($D$), and a corpus of tasks and prompts ($M$).
• Retrieval:
  1. Similar Tasks: Retrieve top-$n$ tasks from the corpus similar to the observed examples using textual embeddings.
  2. Similar Prompts: Retrieve top-$K$ prompt programs from the corpus that exhibit similar behavior (agreement on correctness) to $p_{target}$ on the retrieved tasks.
• Prior Construction: The performance of the retrieved prompts on the retrieved tasks is used to construct a mixture of Beta distributions as the approximate prior.
• Update: The observed outcomes ($O$) update this mixture prior via conjugacy.
• Refinement: RAP includes a Component-wise Prior Strength Adjustment. It scales the parameters of each Beta component based on the Earth Mover's Distance (EMD) between the retrieved component and the prior derived solely from in-domain observations. This prevents irrelevant corpus data from distorting the posterior when in-domain data is scarce.

Key Contributions

1. Formalization: The paper formalizes performance prediction as Bayesian inference under a simple coin-flip model, explicitly separating the likelihood (observed data) from the prior (program type characteristics).
2. Empirical Discovery: It provides the first empirical evidence that symbolic programs have an "all-or-nothing" performance prior, while prompt programs have a diffuse prior with significant mass on intermediate performance. This explains the certification gap between the two program types.
3. Algorithmic Solution: The introduction of RAP, a retrieval-based method that constructs an approximate domain-specific prior from a corpus. RAP outperforms baselines that use no corpus or the entire corpus naively.

Results

The authors evaluated RAP on 60 prompt programs across various settings (in-domain and out-of-domain) using metrics of Probability Density at Ground Truth (SC) and Absolute Error (AE).

• Superiority: RAP consistently outperforms baselines (no-corpus and all-corpus) in both in-domain and out-of-domain settings.
• In-Domain Advantage: Using in-domain examples in the corpus significantly improves prediction accuracy, particularly when the number of observed test cases is small.
• Convergence: As the number of in-domain observations increases, RAP gracefully converges to the empirical posterior, ensuring that the likelihood term eventually dominates the prior.
• Robustness: The method remains robust across different hyperparameter choices, corpus sizes, and LLM backbones.

Significance and Claims

The paper claims to be the first work to study performance prediction for both symbolic and prompt programs using a unified Bayesian framework. Its primary significance lies in:

• Quantifying Intuition: Providing a mathematical explanation for why few test cases certify symbolic code but not prompts, attributing it to the structural differences in their performance priors.
• Practical Deployment: Offering a method (RAP) to estimate the confidence of deploying a prompt program when only limited test data is available, a critical need for non-critical settings where 80% performance is valuable but uncertainty must be managed.
• Limitations: The authors modestly note that RAP is a "first line of attack." They acknowledge that retrieving top-$K$ relevant pairs becomes computationally expensive as the corpus grows, suggesting future work in active querying and low-rank approximations of the task-prompt corpus.