# Predicting Performance of Symbolic and Prompt Programs with Examples

arXiv: https://arxiv.org/abs/2605.21515 · HTML: https://mlsanity.com/paper/2605.21515/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 20 references that are in the map.
- First posted on arXiv 15 May 2026.

## Builds on (most cited first, 13 of 13)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models](https://mlsanity.com/paper/2206.04615/) (2022)
- [Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations](https://mlsanity.com/paper/2312.08935/) (2023)
- [GEPA: Reflective Prompt Evolution Can Outperform Reinforcement Learning](https://mlsanity.com/paper/2507.19457/) (2025)
- [State of What Art? A Call for Multi-Prompt LLM Evaluation](https://mlsanity.com/paper/2401.00595/) (2023)
- [Benchmarking Prompt Sensitivity in Large Language Models](https://mlsanity.com/paper/2502.06065/) (2025)
- [Efficient Prompt Optimization Through the Lens of Best Arm Identification](https://mlsanity.com/paper/2402.09723/) (2024)
- [How Predictable Are Large Language Model Capabilities? A Case Study on BIG-bench](https://mlsanity.com/paper/2305.14947/) (2023)
- [Benchmarking Multimodal Regex Synthesis with Complex Structures](https://mlsanity.com/paper/2005.00663/) (2020)
- [Rethinking LLM Evaluation: Can We Evaluate LLMs with 200x Less Data?](https://mlsanity.com/paper/2510.10457/) (2025)
- [PredictaBoard: Benchmarking LLM Score Predictability](https://mlsanity.com/paper/2502.14445/) (2025)

## Abstract (arXiv)

LLM prompting is widely used for naturally stated tasks, yet it is unreliable it may succeed on a few test cases but fail at deployment time. We study performance prediction: given a program, either symbolic (e.g. Python) or a prompt executed on an LLM, and a few in-domain examples, predict its performance on unseen tasks from the same domain. We use a simple coin-flip model, treating each pass/fail program execution as a Bernoulli random variable, whose success probability is the programs unknown performance. In this model, performance depends entirely on: 1) the observed execution outcomes on test cases, and 2) a prior over performances. We compile empirical performance priors from a corpus of diverse programs and tasks, and find that performance for symbolic programs (e.g., Python) are all or nothing, while prompt programs have a diffuse prior with many nearly-correct programs. This difference explains why a few passing tests can certify symbolic programs but not prompt programs. Building on this insight, we develop RAP (Retrieved Approximate Prior), which retrieves similar tasks and prompt programs from an existing corpus to construct a proxy prior, which is then used to predict performance. We show RAP achieves solid performances.