acceptodds
Under review as a conference paper at ICLR 2027

Predicting Performance of Symbolic and Prompt Programs with Examples

Abstract

A prompt program may succeed on a few test cases yet fail on new inputs 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 labeled examples, predict its success rate on unseen instances from the same task distribution. We model each pass/fail execution as a Bernoulli random variable whose success probability is the program's unknown performance. Under this model, the posterior over performance is determined by the observed execution outcomes and a performance prior. We estimate empirical performance priors from a corpus of programs and tasks. In this corpus, symbolic-program success rates concentrate near zero and one, whereas prompt programs have a more diffuse prior with many programs that pass most, but not all, evaluated tests. These priors explain why a few passing tests support greater confidence in near-perfect performance for symbolic programs than for prompt programs in the studied setting. We introduce RAP (Retrieved Approximate Prior), which retrieves related labeled examples and prompt programs from a corpus to construct a proxy prior. With few target observations, RAP achieves higher mean posterior density at held-out reference success rates and narrower 95% credible intervals than no-corpus and all-corpus baselines in the evaluated in-domain and out-of-domain settings.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Bayesian Inference, Performance Prediction

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_F6enOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to use a small number of labeled test samples to predict the accuracy of symbolic programs and large language model prompt programs on unseen data. The authors treat program performance as an unknown Bernoulli success probability and use Bayesian inference to combine historical performance priors with a small number of test results to obtain the posterior distribution of accuracy and its uncertainty.
The authors generate 700 symbolic programs and 700 prompt programs across 70 tasks, with each program evaluated using 100 samples. The results show that under this sampling setup, the empirical accuracy of symbolic programs tends to concentrate near 0% and 100%, whereas prompt programs exhibit a more dispersed distribution. This indicates that even if both types of programs are tested with the same samples, their posterior performance predictions can differ due to differing priors.
Based on this, the authors propose the Retrieval Approximate Prior (RAP) method. This approach first retrieves historical samples similar to the target input and then selects historical programs with similar behavior based on success/failure patterns on these samples. Their accuracies are used to construct a Beta mixture prior, which is combined with a uniform prior according to retrieval similarity. Finally, the posterior is updated using the target test results.
Experiments cover knowledge question answering, code generation, and embodied intelligence scenarios, comparing RAP with corpus-free and full-corpus baselines. RAP typically achieves higher posterior density scores, smaller point estimation errors, and narrower credible intervals with few target observations. The appendix also reports reference accuracy coverage and compares retrieval of similar samples under matched execution budgets. Overall, the paper supports the idea that relevant historical information is beneficial for few-shot performance prediction, though it has not yet fully ruled out alternative explanations arising from additional execution runs and baseline inference methods

Critical strengths

1.When test samples are limited or labeling is expensive, reliably predicting a program's overall accuracy on future inputs is a practical problem in the deployment and evaluation of large language models. This paper not only calculates the average accuracy of test samples but also investigates how program types and historical performance distributions affect judgments about future performance. Comparing the distributions of symbolic programs and prompt-based programs provides intuitive evidence for leveraging different priors, thus constituting substantial reasons supporting adoption.

2.RAP combines semantic retrieval, behavior similarity filtering, beta mixture priors, and posterior updating into an easily interpretable process, without requiring additional training of complex predictive models. Its benefits are not limited to a single metric: in same-domain settings, with four target observations, RAP's mean absolute error is 0.0542, outperforming the corpus-free baseline of 0.1335; the 95% credible interval covers the reference accuracy at a rate of 97.69%. Sample retrieval experiments with matching execution budgets also support that similarity-based selection outperforms random selection. These results provide empirical support for its effectiveness.

Critical weaknesses

1.Besides using m target observations, RAP also performs extra executions of the target program on retrieved historical corpus samples to select historically similar behaviors. Although these extra executions happen on historical samples, they still provide new behavior evidence from the target program to the predictor; the no-corpus baseline only uses the m target test results. Therefore, current comparisons can’t clearly distinguish whether improvements come from more effective historical knowledge transfer or from the extra executions of the target program. The authors did compare similar sample selection and random sample selection under the same execution budget in the appendix, but they didn’t directly compare with a strong no-corpus estimator under an equivalent total execution budget. This issue directly affects how we attribute RAP’s few-shot advantages. 2.The appendix pointed out that when updating the beta components, the full-corpus baseline still keeps equal-weight mixture coefficients, not a strict Bayesian posterior of the mixture prior; in contrast, RAP updates the mixture weights based on target observations, and the priors are also not exactly parameterized the same way. So the performance difference may not just come from the retrieval mechanism. Also, the independent benefits of behavior-similar program filtering still lack sufficient ablation; joint failures might raise behavior consistency scores but don’t necessarily indicate transferable capability similarity. Since the methodological innovation mainly comes from relevant historical information retrieval and prior construction, baseline and ablation issues can substantially affect how the technical contribution is judged.

Questions for authors

1.How much improvement comes from executing extra targets?
Please clearly report the number of target program executions, the cost of existing historical labels, and the precomputation cost separately, and compare RAP with a simple accuracy estimator under the same total target execution budget. If the additional results from RAP are directly used in Bayesian or other estimation methods, does RAP still significantly outperform these methods? The answer directly determines whether the small-sample advantage holds.
2.What happens if the full-corpus baseline uses consistent strict Bayesian updates?
Why does the full-corpus baseline retain equal-weight mixture coefficients? If it uses the same prior strength, component parametrization, and observation-driven strict Bayesian weight updates as RAP, does RAP’s advantage still exist? This could clarify whether the gain comes from retrieval itself or from inconsistent probabilistic modeling.
3.Is behavior similarity retrieval really necessary?
Can we verify the independent contribution of behavior retrieval by removing it, randomly selecting historical programs, or using an alternative consistency metric? Since the current scoring rewards both joint success and joint failure, is there a bias toward programs that fail together? These results would significantly affect the evaluation of RAP’s core mechanism.

2 comments

Thank you for these constructive questions. We understand that your concerns center on two aspects:

(1) Cost-effectiveness of RAP and fairness of the comparisons. (weakness 1)

To answer this question, we conducted an additional cost-effectiveness experiment (Figure 13), comparing RAP with the No-Corpus baseline under different monetary budgets. We account for the costs of target-example labeling, LLM execution, and corpus retrieval to ensure a comprehensive comparison.

To avoid overstating RAP's cost advantage, we conservatively estimate the labeling cost at \1pertargetexample,althoughtheactualcostcouldexceed1 per target example, although the actual cost could exceed \\30 when accounting for expert hourly rates and the time required to prepare questions and answers. In contrast, we estimate the cost of each LLM execution at approximately \$0.02 per example. These estimates allow us to quantify the relative costs of acquiring additional target-domain observations and leveraging existing corpus information under a consistent accounting framework.

The results reveal a clear cost-dependent advantage of RAP. Under budgets below \$8, RAP achieves better predictive performance at a lower total cost. As the budget increases, however, collecting additional labeled target examples can yield higher predictive accuracy. This highlights RAP's particular advantage in budget-constrained scenarios, where leveraging retrieved corpus information provides a more cost-effective alternative to acquiring additional target-domain labels.

(2) the source of RAP's performance gains and whether the ablation studies adequately isolate the contributions of its components. (weakness 1, 2)

To address these concerns, we conducted two additional experiments:

  1. Retrieval Strategy Ablation (Section 6.3, Table 2): To evaluate the contribution of each retrieval component, we conduct an ablation study comparing random sampling with RAP's similarity-based retrieval for both examples and programs. By independently varying the retrieval strategy for each component, we isolate their individual contributions and investigate their complementary effects on predictive performance.

The results show that both similarity-based retrieval components improve predictive performance over random sampling. Notably, combining similarity-based example and program retrieval achieves the highest PDS in both in-domain and OOD settings. These findings demonstrate that the two retrieval components provide complementary benefits and jointly contribute to RAP's improved predictive performance.

  1. Prior Construction Ablation (Section 6.3, Figure 7): To isolate the contribution of prior construction, we compare different prior construction strategies while keeping the retrieved examples fixed. This allows us to distinguish the effect of RAP's adaptive prior construction mechanism from that of retrieval.

The results demonstrate that RAP produces more informative and better-calibrated priors, particularly in OOD settings. Compared with the No-Corpus baseline, RAP maintains substantially higher empirical coverage as the number of retrieved examples increases (75% vs. 46% at 64 examples in the OOD setting). Meanwhile, RAP achieves narrower credible intervals than the All-Corpus baseline. In contrast, All-Corpus exhibits nearly constant interval widths and consistently low empirical coverage (approximately 60%), suggesting that its overly concentrated prior prevents the posterior from adequately adapting to new evidence.

These improvements stem from RAP's adaptive prior construction mechanism, which adjusts the prior uncertainty according to corpus quality and uses (κ\kappa) to control the effective contribution of retrieved evidence. Together, these mechanisms allow RAP to leverage relevant corpus information without becoming overconfident, achieving a better balance between predictive informativeness and uncertainty calibration.

Taken together, these ablation studies clarify the contributions of individual components to RAP's overall performance and address the reviewer's central concerns. We now turn to the remaining questions.

Q1: How much improvement comes from executing extra targets?

To directly evaluate RAP's cost-effectiveness, we conducted an additional experiment comparing RAP with the No-Corpus baseline under different cost budgets (Figure 13). We conservatively assume a labeling cost of \1pertargetexampleandanLLMinferencecostof1 per target example and an LLM inference cost of \\0.02 per example. Based on these assumptions, we estimate the total cost of each approach. As shown, RAP offers a clear cost advantage under budgets below \8.Notably,RAPachievesbetterpredictiveperformancewithonlyapproximately8. Notably, RAP achieves better predictive performance with only approximately \\1 in additional retrieval costs. We provide a detailed cost breakdown for each value of mm considered in Figure 6 below.

Target observations (m)In-domain extra executionsOut-of-domain extra executionsTarget labeling costRAP’s additional In-domain retrieval costRAP’s Out-of-domain retrieval cost
150.00 ± 0.0050.00 ± 0.00\$1.02\1.00±1.00 ± \\0.00\1.00±1.00 ± \\0.00
243.95 ± 5.2044.00 ± 4.62\$2.04\0.88±0.88 ± \\0.10\0.88±0.88 ± \\0.09
441.98 ± 4.2740.67 ± 3.97\$4.08\0.84±0.84 ± \\0.09\0.81±0.81 ± \\0.08
840.93 ± 4.3938.61 ± 3.84\$8.16\0.82±0.82 ± \\0.09\0.77±0.77 ± \\0.08
1642.69 ± 4.1437.75 ± 3.78\$16.32\0.85±0.85 ± \\0.08\0.76±0.76 ± \\0.08
3245.82 ± 4.7238.89 ± 4.24\$32.64\0.92±0.92 ± \\0.09\0.78±0.78 ± \\0.08
6444.16 ± 4.3436.06 ± 5.37\$65.28\0.88±0.88 ± \\0.09\0.72±0.72 ± \\0.11

Q2: What happens if the full-corpus baseline uses consistent strict Bayesian updates?

It exhibits worse predictive performance. To ensure a fair comparison across methods, we conducted an additional experiment (Section 6.3) to isolate the effect of prior construction, keeping the retrieved information fixed while varying the prior construction algorithms. The results show that the All-Corpus baseline, which uses all available corpus information to construct the prior, produces an excessively concentrated Beta distribution (e.g., Beta(337, 160)). Consequently, the strong prior dominates the Bayesian update, making the posterior relatively insensitive to additional target observations. As illustrated in Figure 7 and Figure 12, the All-Corpus baseline exhibits little change as more observations are incorporated, demonstrating its limited ability to adapt to new evidence.

Q3: Is behavior similarity retrieval really necessary?

They are necessary. Our additional ablation study demonstrates that both similarity-based example retrieval and program retrieval contribute to predictive performance, with their combination achieving the highest PDS in both in-domain and OOD settings. To isolate the contribution of each component, we independently replace RAP's similarity-based retrieval strategies with random sampling while keeping the remaining settings unchanged. As shown below, RAP substantially outperforms random retrieval, improving PDS from 1.30 to 3.96 in-domain and from 1.22 to 2.37 OOD. Moreover, program retrieval provides particularly strong gains, while combining both components yields the best performance, demonstrating their complementary benefits. These results have been incorporated into Section 6.3 of the revised manuscript.

Reviewer_fWgVOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper develops an empirical performance estimation of both symbolic programs (those written in defined programming languages with a defined set of rules) and prompt programs (those executed based on feeding a large language model a set of instructions and input data) by measuring success as a bernouli random variable, demonstrating the importance of a well constructed prior in providing accurate posterior estimations of a program’s performance. In order to better estimate the performance of a prompt program based on limited prior data in a specific domain, they develop the Retrieved Approximate Posterior (RAP) which can draw from examples and prompting programs in different domains to better establish the prior of a prompting program in a new domain before a limited set of target examples is used to evaluate the posterior probability. They show that this technique outperforms both uniform priors and those created based on all prior corpus programs both on reaching a posterior mean closer to the reference success rate as well as forming a tighter 95% confidence interval.

Critical strengths
  • Strong definition of both the core problem, as well as terms and methodologies in the main body of the paper. A non-subject area expert could easily parse the necessary math required.
  • The corpus of samples covered stretches across both natural language and few-shot example problems, as well as three different programming tasks, which provide a good basis for this study.
  • Accounts for uncertainty as a thread through the main results (demonstrates the performance of the techniques on confidence intervals in Figures 1 and 6). This helps to support the claim of the higher Posterior Density Scores that accompany them.
Critical weaknesses
  • While it is shown that the Retrieved Approximate Prior does demonstrate a Posterior Density Score that moves closer to the reference success rate than the all-corpus baseline, it is not clear whether this is due to the selection of relevant examples from cosine similarity, or from the fact that it updates both the overall distribution as well as the weights (Section 5, lines 274–276), while the all-corpus baseline keeps the weights equal (Section 6.1, lines 374-375). This means that some benefit may come from the updating procedure, and not necessarily the selection of similar examples, which is the argument for RAP’s effectiveness. While this was a deliberate design decision, the construction of an all-corpus baseline with these updated weights could isolate this effect, and provide a more fair comparison.
  • Section 5.1 introduces an embedding function e(x) for the purposes of calculating the cosine similarity, but to the best of my ability I cannot identify which embedding model implements it. This may impede future reproduction of the work.
Questions for authors
  • Does RAP’s improvement actually come from retrieving similar examples, or partly from its more favorable updating procedure? RAP updates both the overall distribution and the weights, whereas the all-corpus baseline keeps equal weights. Why is there no all-corpus baseline using the same weight-update procedure to isolate the effect of similarity-based retrieval and ensure a fair comparison?

  • Which embedding model is used to implement the embedding function e(x)e(x) in Section 5.1? Without specifying the model, version, and relevant configuration, how can the cosine-similarity retrieval process be reproduced or the reported results be independently verified?

1 comment

We thank the reviewer for their careful reading and constructive feedback. We address each concern below.

We understand that your primary concern is clarifying the specific contributions of our method. In RAP, there are two complementary components at work:

  1. retrieval related information from corpus
  2. construction of a prior from the retrieved information

Thus, we have conducted a more comprehensive ablation study to isolate the contributions of each component.

we put the ablation study result here first:

retrieval related information from corpus (section 6.3 table 2):

To evaluate the effectiveness of our retrieval strategy, we conduct an ablation study comparing different retrieval configurations. RAP consists of two retrieval components: example retrieval and program retrieval. For each component, we compare random sampling against RAP's similarity-based retrieval, which leverages embedding similarity for examples and behavioral similarity for programs. We fix the number of target examples at 4 and retrieve 50 examples and 5 programs from the corpus across all configurations to ensure a fair comparison.

The results are presented below:

Example RetrievalProgram RetrievalIn-Domain PDSOOD PDS
RandomRandom1.30 ± 0.051.22 ± 0.05
RandomRAP2.38 ± 0.152.09 ± 0.15
RAPRandom1.76 ± 0.121.32 ± 0.13
RAPRAP3.96 ± 0.282.37 ± 0.43

The results demonstrate that both retrieval components contribute to improved predictive performance compared with random sampling. Notably, combining both similarity-based retrieval strategies achieves the highest PDS in both in-domain and OOD settings, highlighting their complementary benefits and validating the effectiveness of RAP's retrieval strategy.

Prior Construction Algorithm (section 6.3 figure 7):

To isolate the effect of prior construction, we compare different methods using the same examples retrieved by RAP. We evaluate the resulting priors in terms of PDS, 95% credible interval width, and empirical reference coverage, as shown in Figure 7 of the revised manuscript.

The results demonstrate that RAP constructs more informative and better-calibrated priors, particularly in OOD settings. Compared with the No-Corpus baseline, RAP maintains substantially higher empirical coverage as the number of retrieved examples increases (75% vs. 46% at 64 examples in OOD), while achieving narrower credible intervals than the All-Corpus baseline. In contrast, All-Corpus maintains nearly constant interval widths and low coverage (approximately 60%), indicating that its overly concentrated prior fails to adapt to new evidence.

These improvements stem from RAP's adaptive prior construction mechanism, which adjusts uncertainty according to corpus quality and limits the effective contribution of retrieved examples through (κ\kappa). Together, these mechanisms enable RAP to leverage retrieved evidence without becoming overconfident, achieving a more favorable balance between predictive informativeness and uncertainty calibration.

We believe that this comprehensive ablation study addresses your primary concern. We address the remaining questions below.


Response to W1 / Q1: Performance Attribution and Fair Comparison

We have provided detailed comparisons and ablation studies of RAP's mechanisms, along with additional baselines suggested by the reviewer, including adaptive weighting and a No-Corpus baseline under the same budget.

Q: Why is there no all-corpus baseline ... ensure a fair comparison?

In particular, the All-Corpus baseline uses all available corpus information to construct the prior, resulting in excessively concentrated Beta distributions (e.g., (Beta(337,160)\mathrm{Beta}(337,160)). Consequently, additional target observations have limited influence on the posterior, as the strong prior dominates the Bayesian update. This behavior is evident in Figure 7, where the All-Corpus baseline exhibits little change as the number of target examples increases.

In contrast, RAP achieves superior predictive performance and enables more reliable decision-making. These improvements stem from our prior construction mechanism, which uses κ\kappa to control the effective contribution of retrieved examples and regularizes the prior toward Beta(1,1)\mathrm{Beta}(1,1) based on corpus quality, thereby mitigating overconfidence and allowing the posterior to adapt to new observations.

Since all baselines employ the same posterior update procedure, these experiments isolate the impact of prior construction quality on predictive performance and decision reliability.

Response to W2 / Q2: Embedding Model and Reproducibility

We implement e(⋅)e(\cdot) using sentence-transformers/all-mpnet-base-v2, which is explicitly listed in Appendix A.1 of the current manuscript.

Reviewer_VauFOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how to estimate a fixed program's success rate on unseen inputs from a few labeled tests. It compares empirical performance priors for symbolic and LLM-prompt programs, then proposes RAP, which retrieves related labeled examples and historically similar prompt programs to construct a target-specific prior. Bayesian updating combines this prior with observed target outcomes. Across the evaluated tasks, RAP improves reported prediction metrics over uniform and all-corpus priors and a matched-budget experiment also finds selected corpus examples more informative than random ones on six MMLU domains.

Critical strengths
  1. The paper addresses an important and clearly defined reliability-estimation problem. Sections 1 and 3 define the success rate of a fixed program on future inputs from the same task distribution and explain why a few labeled tests may not estimate it reliably.
  2. The paper provides positive evidence that prior information and targeted retrieval can improve sparse performance prediction. Section 4 documents different empirical success-rate distributions for the sampled symbolic and prompt programs. In Section 6.3, RAP-selected corpus examples outperform random examples with the same four target observations and eight additional executions on six MMLU domains.
Critical weaknesses

My main concern is that the paper has not yet shown whether RAP provides reliable performance estimates at a worthwhile total evaluation cost. The two issues below are central to this assessment.

  1. The main performance advantage has not been established at comparable total evaluation cost. Section 5.2 states that RAP runs the target program on retrieved corpus examples in addition to the m target observations shown on Figure 6's horizontal axis. The no-corpus baseline does not receive these additional executions, and their number is not reported for each value of m. Appendix A.3 gives aggregate API expenditure rather than a per-prediction cost breakdown. The matched 4+8 experiment in Appendix B.3 supports retrieval over random corpus selection, but does not show whether RAP is preferable to allocating additional executions to target-task tests. Reusing existing corpus labels may save annotation effort, so execution and labeling costs should be accounted for separately. The present comparison therefore does not isolate RAP's practical advantage from the benefit of observing more target-program outcomes.
  2. The predictive improvements have not yet been connected convincingly to reliable threshold decisions. Higher posterior density at a reference rate, lower point-estimation error, and narrower intervals are encouraging, but do not by themselves establish calibrated uncertainty about the true success rate. Appendix C does report coverage of held-out empirical reference rates, which is useful evidence. However, these references are estimated from finite test sets, and the authors explicitly distinguish this check from true-rate calibration. Section 7 also leaves independent calibration validation and false acceptance or rejection at explicit quality thresholds to future work. Even within the stated target task distribution, it remains unclear whether the predictions help developers make more reliable accept/reject decisions. This limits the demonstrated practical value, although the absence of a full deployment study would not, by itself, justify rejection.
Questions for authors
  1. How many extra target-program executions does RAP use in Figure 6? At the same total execution budget, does it outperform testing more target-task examples, with labeling costs accounted for separately?
  2. Beyond Appendix C's finite-reference coverage, what evidence supports the calibration of RAP's 95% intervals? Can existing results show false acceptance and rejection at a stated success-rate threshold?
1 comment

We thank the reviewer for their careful reading and constructive feedback. The main concern is if RAP provides an advantage "at a worthwhile total evaluation cost". This is a great question, and we interpreted this question as: If you have some amount of money, which can be either allocated to additional executions of LLMs from an existing corpus, or allocated to procuring additional labeled examples from the target domain, how should one make this decision? We conducted an additional cost-effectiveness experiment comparing RAP with the No-Corpus baseline under different budgets, with the results reported in Figure 13 (Appendix B.6).

As we cannot upload the figure here, we'll summarize the key findings in text:

For a conservative comparison, we estimate the cost of labeling each target example at \1,althoughtheactualcostcouldexceed1, although the actual cost could exceed \\30 when accounting for expert hourly rates and the time required to prepare questions and answers for the kind of tasks in our dataset. In contrast, we estimate the cost of each LLM execution at approximately \$0.02 per example from our dataset.

The results reveal a clear cost-dependent advantage of RAP. Under budgets below \8,RAPachievesbetterpredictiveperformanceatalowertotalcost.Atabudgetabove8, RAP achieves better predictive performance at a lower total cost. At a budget above \\8, collecting additional labeled target examples can yield higher predictive accuracy. This demonstrates that RAP is particularly cost-effective when the available budget is limited, while providing a dollar-amount threshold to acquiring additional target-domain labels. We believe this key result (figure 13) directly addresses your central concern.

We address your remaining questions below.

Response to W1 / Q1: Execution and Labeling Costs

  1. the cost for each mm.

We have added Appendix B.7 and Table 5 to the revised manuscript, reporting the results of these additional experiments across different values of (m), with deduplication applied to the retrieved examples. Specifically, for each target example, we retrieve the ⌈50/m⌉\lceil 50/m \rceil most relevant corpus examples without duplicates to maintain a comparable retrieval budget across different settings. The results demonstrate that RAP achieves improved predictive performance at an additional cost of only approximately \1,fromabout50extraLLMcallsat1, from about 50 extra LLM calls at \\0.02 each.

Target observations (m)In-domain extra executionsOut-of-domain extra executionsTarget labeling costRAP’s additional In-domain retrieval costRAP’s Out-of-domain retrieval cost
150.00 ± 0.0050.00 ± 0.00\$1.02\1.00±1.00 ± \\0.00\1.00±1.00 ± \\0.00
243.95 ± 5.2044.00 ± 4.62\$2.04\0.88±0.88 ± \\0.10\0.88±0.88 ± \\0.09
441.98 ± 4.2740.67 ± 3.97\$4.08\0.84±0.84 ± \\0.09\0.81±0.81 ± \\0.08
840.93 ± 4.3938.61 ± 3.84\$8.16\0.82±0.82 ± \\0.09\0.77±0.77 ± \\0.08
1642.69 ± 4.1437.75 ± 3.78\$16.32\0.85±0.85 ± \\0.08\0.76±0.76 ± \\0.08
3245.82 ± 4.7238.89 ± 4.24\$32.64\0.92±0.92 ± \\0.09\0.78±0.78 ± \\0.08
6444.16 ± 4.3436.06 ± 5.37\$65.28\0.88±0.88 ± \\0.09\0.72±0.72 ± \\0.11

Response to W2 / Q2: Predictive Coverage and Threshold-Based Decisions

Good question. To evaluate decision-making reliability, we introduce a simple decision-making procedure comparing RAP with the No-Corpus baseline. The ideas is as follows: If a programmer wish to guarantee that their program is correct at over, for instance, 70% of the times, how can he make this judgement? Both methods use their respective posterior distributions to make decisions according to the same rule. The decision rule is defined as follows:

p = P(success_rate >= \tau | PP, [corpus])

if p >= 0.95:
    return "Accept"
elif p <= 0.05:
    return "Reject"
else:
    return "No Decision"

The results are presented below:

Threshold τ\tauRAPNo corpus
Decision made (%)Wrong acceptWrong rejectDecision made (%)Wrong acceptWrong reject
10%99.90070.000
20%87.80050.700
30%74.10050.7100
40%68.63129.750
50%71.10036.2540
60%67.00156.5040
70%62.50530.00120
80%55.00030.0020
90%68.410249.342

Overall, RAP enables substantially more confident decisions while reducing both false acceptances and false rejections compared with the No-Corpus baseline. These results demonstrate that incorporating retrieved prior information improves decision coverage and reliability. Do note that RAP performs poorly when the decision is 90%, this is the case because in the corpus considered, barely 10% of the total programs have a 90% accuracy. We expect this (the fractions of 90%) to improve as LLM capabilities improve.

Comments on the paper

1 comment

For AC:

We use this space to summarize the overall accepted contributions and criticisms of our work.

This work makes 3 contribution claims:

  1. the formulation of performance prediction --- given a program and a few examples from a target domain, predicting its eventual performance on the domain in deployment time --- through a simple Bayesian framework, centered around the performance prior
  2. the empirical evaluation of the performance prior for symbolic and prompt programs, revealing the insight as to why programmers trust symbolic programs with few passing examples, while not trusting prompt programs with a few passing examples.
  3. development of a novel performance prediction algorithm, RAP, which works by retrieving and constructing a relevant performance prior using the target program and a few target domain’s examples.

The reviewers (R1 R2 R3) all acknowledges contribution 1 and 2.

The concern is around contribution 3, summarized as follows:

a) if RAP is actually useful for a developer when evaluated end-to-end, using a realistic cost metric (R1, R3)

b) what explains the efficacy of RAP, is it due to its better retrieved examples, or due to its better construction of a prior from the retrieved examples (R1, R2, R3)

c) can we give a decision algorithm which programmers can actually use to drive real decisions from the posterior constructed by RAP (R1)

These are all fantastic questions, and are addressable.

Here is how we answer them.

a) RAP is particularly effective under budget constraints. When the available budget is below $8, leveraging RAP provides better predictive performance at a lower cost. RAP offers a cost-effective solution when labeling resources are limited, while additional target observations become more beneficial when larger budgets are available. we have put the additional experiments result in revised paper figure 13.

b) Disentangling the contributions of retrieval and prior construction. Our ablation studies demonstrate that both components contribute to RAP's effectiveness. Similarity-based retrieval of relevant examples and programs provides complementary improvements in predictive performance, while adaptive prior construction produces more informative and better-calibrated priors, particularly in OOD settings. These results confirm that RAP's gains arise from the combination of effective retrieval and adaptive Bayesian prior construction, rather than either component alone. We have incorporated these additional ablation results into Section 6.3 of the revised manuscript (Table 2 and Figure 7).

c) Translating RAP's predictions into actionable decisions. We further demonstrate how RAP's posterior predictions can be used to support practical decision-making. Specifically, we introduce a simple threshold-based decision rule that determines whether to accept, reject, or defer a program based on its posterior probability of achieving a target success rate. Applying the same decision rule to RAP and the No-Corpus baseline, our results show that RAP enables substantially more decisions while reducing incorrect acceptances and rejections. For example, at a target success rate of 80%, RAP makes decisions on 55% of cases with no incorrect decisions, compared with only 30% for the No-Corpus baseline, which also incurs incorrect rejections. This demonstrates that RAP's calibrated uncertainty estimates provide a more reliable basis for practical decisions beyond predictive accuracy alone.

Finally, We thank the reviewers for their comments which were written responsibly, and coming from a place of genuine curiosity about our work.

Importantly, the reviewers' questions focused on further validating and clarifying our third contribution (RAP), rather than challenging the overall motivation of our work or the main empirical findings underlying our first two contributions (contribution claim 1 and 2). Addressing these questions has provided us with a valuable opportunity to strengthen our work, better articulate RAP's contributions, and clarify its practical significance.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.