- 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
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 \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 \1 in additional retrieval costs. We provide a detailed cost breakdown for each value of considered in Figure 6 below.
| Target observations (m) | In-domain extra executions | Out-of-domain extra executions | Target labeling cost | RAP’s additional In-domain retrieval cost | RAP’s Out-of-domain retrieval cost |
|---|---|---|---|---|---|
| 1 | 50.00 ± 0.00 | 50.00 ± 0.00 | \$1.02 | \0.00 | \0.00 |
| 2 | 43.95 ± 5.20 | 44.00 ± 4.62 | \$2.04 | \0.10 | \0.09 |
| 4 | 41.98 ± 4.27 | 40.67 ± 3.97 | \$4.08 | \0.09 | \0.08 |
| 8 | 40.93 ± 4.39 | 38.61 ± 3.84 | \$8.16 | \0.09 | \0.08 |
| 16 | 42.69 ± 4.14 | 37.75 ± 3.78 | \$16.32 | \0.08 | \0.08 |
| 32 | 45.82 ± 4.72 | 38.89 ± 4.24 | \$32.64 | \0.09 | \0.08 |
| 64 | 44.16 ± 4.34 | 36.06 ± 5.37 | \$65.28 | \0.09 | \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.
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,althoughtheactualcostcouldexceed30 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:
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.
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 (κ) 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.