REVIEW 3 major objections 4 minor 32 references
Online Prompt Selection for Program Synthesis
T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read An online multi-armed bandit, CYANEA, chooses per query between a symbolic solver and LLM-prompt pairs, and this selection solves 37.2% more synthesis queries than the best single solver while staying within 4% of a perfect selector.
desk verdict CYANEA is a solid, honest empirical paper on contextual bandit selection of LLM/prompt/solver portfolios for synthesis; the missing no-context baseline and underspecified features are the main soft spots, not the central result. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The engine is a contextual k-nearest-neighbor multi-armed bandit. For each new query, it computes a feature vector (frequencies of SMT-LIB keywords, query length, constants, and logic type), finds the k previously solved queries closest in that feature space, and ranks each solver by the sum of rewards those neighbors earned. A second mechanism handles budgets: for each ranked arm, the cost needed per query is estimated by fitting an exponential distribution via maximum likelihood to the observed costs of nearby queries, and the total per-query token and time budgets are divided greedily along the ranking. The paper tests three reward functions—time-based, cost-based, and binary solve/not-solve—and two topologies: one bandit over all arms, and a layered set of bandits that first chooses the model and then chooses the prompt.
What would settle it
Take the same 1,269-query benchmark, the same budgets, reward functions, and one configuration of CYANEA, but replace the hand-designed features with random feature vectors; if the percentage of solved queries does not drop substantially below 88.3% toward the 64.3% of the best single solver, the feature-similarity assumption is falsified. A second test is to train the bandit on the SyGuS and ranking-function queries and evaluate only on the fresh SMT-derived queries; if the improvement over the best single solver vanishes, the learned similarity does not generalize across distributions.
Extended reading notes
Core claim
The paper's central claim is that per-query solver-and-prompt selection can be learned online well enough to make a portfolio behave like a near-oracle. Concretely, CYANEA treats each symbolic solver and each LLM-prompt pair as an arm; after each query it receives a reward based on solving success, time, and token cost. A k-nearest-neighbor contextual bandit ranks the arms for the next query using the rewards of the k most similar previously solved queries, and a budget allocator spends the per-query time and token budget across the ranked arms. On 1,269 queries drawn from SyGuS, ranking-function, and SMT-derived benchmarks, the best run solved 88.3% of queries, compared with 64.3% for the best fixed solver and 91.8% for a virtual best selector that always makes the optimal choice. The authors conclude that the learning, not any individual solver, is what delivers the improvement.
Load-bearing premise
The whole gain rests on the assumption that the hand-built features describing a synthesis query (keyword frequencies, length, constants, logic type) make queries that look similar behave similarly under each solver, so past rewards on nearby queries predict which solver will win next.
Editorial extensions
If this is right
- A non-expert with a batch of synthesis queries can deploy a portfolio of solvers and prompts without knowing which one will work, and still solve far more queries than using any single solver.
- Because the reward function is plug-in, the same system can optimize for wall-clock time, API cost, or raw solve count depending on user priorities.
- The per-query budget allocation lets the system recover when its top-ranked solver fails, by saving enough time and tokens to try lower-ranked arms.
- The layered bandit variant shows a trade-off: decomposing model choice from prompt choice reduces the data available to each learner and increases variance, so the single-layer design is the more stable configuration.
- Any new solver or prompting style can be added as another arm without retraining the feature extractor or the bandit, so the portfolio can grow over time.
Reading between the lines
- An untested extension: replace the hand-designed features with random feature vectors on the same 1,269 queries; if the solved-query rate stays near 88%, the k-NN similarity is not the active ingredient, and if it falls toward the 64.3% of the best single solver, the features carry the result.
- Because the rewards and bandit are agnostic to query syntax, the same machinery should transfer to other synthesis or code-generation settings, such as invariant synthesis, patch generation, or SMT solver selection, whenever a feature extractor can be defined.
- A tighter time or token budget would stress the budget allocator more than the current setting, in which the system can often afford to run all arms on one query; testing under budgets small enough that only a few arms can be tried would separate the value of ranking from the value of allocation.
- The remaining gap to the virtual best suggests headroom is in prediction rather than in the solver library, so a richer feature space or a bandit that models uncertainty could close more of the gap; this conjecture is not tested in the paper.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes CYANEA, a system that frames solver and prompt selection for program synthesis as an online contextual multi-armed bandit problem. Given a set of synthesis queries, CYANEA featurizes each SyGuS-IF query, uses k-NN with hand-designed features to rank a portfolio of 13 solvers (12 LLM-prompt pairs plus an enumerative solver), and allocates time and token budgets across the ranked solvers before deploying them sequentially. The evaluation on 1,269 queries from SyGuS, ranking-function synthesis, and SMT-derived benchmarks reports that the best CYANEA instance solves 88.3% of queries, versus 64.3% for the best single solver and 91.8% for a virtual best solver, with results averaged over 20 randomly shuffled runs. The paper also compares single-layer versus double-layer bandit architectures and reward functions for time, cost, and binary solve success.
Significance. If the result holds, the paper addresses a practical and timely problem: non-expert users of LLM-based synthesis must choose not only between symbolic solvers and LLMs but also among LLMs and prompting styles. The evaluation is substantial for an empirical systems paper: 1,269 queries, 20 shuffled runs, reported standard deviations, a virtual-best upper bound, and a parameter sweep showing stability for k in 10-15. The framing as an online learning problem is appropriate, and the paper does not overclaim the ability of any single LLM. However, the central attribution of the gains to the learned contextual ranking is not established, because no baseline removes the learned context while keeping the same portfolio and budget allocator, and the feature representation is too underspecified to support the claimed transferability.
major comments (3)
- [Section 5, Features] The evaluation lacks a baseline that removes the learned contextual ranking. The 'Single k-NN linear' rows solve 87.0% of queries (1104±0), while the exponential-allocation 'Single k-NN' rows solve about 88.1-88.3%; the difference is only about 1.3 percentage points, yet both variants use the same k-NN ranking. The zero standard deviation of the linear rows is consistent with a regime in which most or all solvers are attempted on every query, making the learned ordering almost irrelevant. To support the paper's central claim that online contextual selection drives the improvement, please add a fixed-order baseline, a random-order baseline, and a non-contextual bandit (e.g., UCB without features) using the same budget allocator, and report the resulting solve rates and scores.
- [Section 5, k-Nearest Neighbor] The feature vector is underspecified and its predictive power is not demonstrated. The paper lists 'Keywords: Frequencies of specific SMT-LIB keywords (e.g., +, -, *, div, etc.)', 'Query length', 'Constants', and 'Query logic', but does not give the actual keyword list, the encoding of 'Query logic', or any normalization scheme. Euclidean ('cartesian') distance over raw counts of heterogeneous features is likely dominated by query length, in which case the 'nearest neighbours' are nearest in length rather than in problem structure. Please provide the exact feature construction and add an ablation comparing full features against length-only or random features to show that the contextual mechanism, rather than the budget allocator or portfolio composition, is responsible for the reported gains.
- [Section 5, Time and Token Budget Allocation] The ranking procedure is incompletely specified. The text states that the score for a solver is the sum of rewards over the k nearest previously solved queries, but it does not state how ties are broken or how the final ordering is made deterministic; it says only that solvers absent from the k-neighbor set are randomly shuffled and appended. With 13 solvers and k=15, many solvers may receive zero score on a given query, so the random component could be substantial. Please specify the exact tie-breaking and shuffling procedure, and report the variance attributable to this randomness separately from the variance due to query order.
minor comments (4)
- [Section 7, Reproducibility] The sentence claiming that 'the highest number of queries solved is achieved using rb' is contradicted by Table 2, where Single k-NN (rc) solves 1120.6 queries and Single k-NN (rb) solves 1117.5; likewise, the claim that rt gives the best Par-2 score is contradicted by rc's Par-2 score of 37636.3 versus rt's 37813.7.
- [Section 5, Time and Token Budget Allocation] No code, complete prompt templates, or feature-extraction code are released. Given that the paper is an empirical systems paper and that the feature and prompt definitions are not fully specified, this severely limits independent verification of the reported 20-run results.
- [Section 5, Reward functions] The parameters δ1 and δ2 are introduced in the budget-allocation derivation but no numeric values are reported, and the formula for c_i appears to use δ rather than δ2. Please state the values used in the experiments and clarify the notation.
- [Table 2] Several constants that could affect the results are not swept or otherwise justified: the reward exponent 4, the output-token cost multiplier 3, the enumerative solver fixed cost 0.4, the 'up to 16 attempts' limit, and the total budgets T=100 and C=100,000. At minimum, a sensitivity analysis for the reward exponent and the cost multiplier would help establish that the headline solve rate is not an artifact of these choices.
Circularity Check
No significant circularity: CYANEA's headline performance is an empirical, self-contained evaluation, with only minor non-load-bearing self-citations.
full rationale
The central claim—that CYANEA's contextual k-NN bandit plus budget allocation solves 88.3% of 1,269 queries versus 64.3% for the best single solver and within 4% of the virtual best—is an empirical result, not a consequence of the paper's definitions. The k-NN predictor ranks solvers by rewards on previously solved queries in feature space; this is standard contextual bandit learning, and the evaluation uses sequential queries over 20 randomly shuffled runs. The reward functions r_t, r_c, and r_b are defined independently of the reported performance metrics (Par-2 score, average time, average cost, solve rate); although r_t correlates with Par-2, the paper explicitly reports this as expected and does not derive the solve-rate claim from that reward. The virtual-best baseline is constructed by an oracle per-query choice within the same solver library, so it is an upper bound, not an input to CYANEA. The k parameter is swept and reported stable for k=10–15 with k=15 used, so the headline is not forced by a tuned constant. The only self-referential elements are citations to prior work by overlapping authors for the data-generation procedure (Parsert and Polgreen 2024) and enumerative solver details (Li, Parsert, and Polgreen 2024); these support experimental components rather than the load-bearing derivation, and external SyGuS and ranking-function benchmarks are also used. The feature vector is under-specified (exact keyword list and normalization are absent), and no non-contextual or random-ordering baseline is reported, so the contribution of the learned context versus portfolio diversity is not fully isolated; those are correctness and robustness concerns, not circularity. No equation or fitted parameter is renamed as a prediction, and no uniqueness theorem is imported from the authors. Therefore no significant circularity is found.
Assumptions & free parameters
free parameters (6)
- k (k-NN neighborhood size) =
15 (swept between 10 and 15)
- Reward exponent 4 =
4
- Output-token cost multiplier =
3
- Enumerative solver fixed cost =
0.4
- Time and cost budgets =
T=100s, C=100,000 tokens
- LLM attempts per query =
16
assumptions (5)
- domain assumption Feature similarity implies solver performance similarity
- domain assumption Per-solver cost and runtime follow exponential distributions
- domain assumption Reward functions reflect user objectives
- domain assumption The validation SMT solver (cvc5) correctly checks candidate solutions
- domain assumption Solver results are independent across queries
Cite this review
Pith. "Pith review of Online Prompt Selection for Program Synthesis." pith.science (2026). https://pith.science/paper/UU5VYLKN
@misc{pith2026250105247,
author = {Pith},
title = {Pith review of: Online Prompt Selection for Program Synthesis},
year = {2026},
howpublished = {\url{https://pith.science/paper/UU5VYLKN}},
note = {Machine review of arXiv:2501.05247}
}
read the original abstract
Large Language Models (LLMs) demonstrate impressive capabilities in the domain of program synthesis. This level of performance is not, however, universal across all tasks, all LLMs and all prompting styles. There are many areas where one LLM dominates, one prompting style dominates, or where calling a symbolic solver is a better choice than an LLM. A key challenge for the user then, is to identify not only when an LLM is the right choice of solver, and the appropriate LLM to call for a given synthesis task, but also the right way to call it. A non-expert user who makes the wrong choice, incurs a cost both in terms of results (number of tasks solved, and the time it takes to solve them) and financial cost, if using a closed-source language model via a commercial API. We frame this choice as an online learning problem. We use a multi-armed bandit algorithm to select which symbolic solver, or LLM and prompt combination to deploy in order to maximize a given reward function (which may prioritize solving time, number of synthesis tasks solved, or financial cost of solving). We implement an instance of this approach, called CYANEA, and evaluate it on synthesis queries from the literature in ranking function synthesis, from the syntax-guided synthesis competition, and fresh, unseen queries generated from SMT problems. CYANEA solves 37.2% more queries than the best single solver and achieves results within 4% of the virtual best solver.
Figures
Reference graph
Works this paper leans on
-
[1]
, " * write output.state after.block = add.period write newline
ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...
-
[2]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...
-
[3]
Alur, R.; Fisman, D.; Singh, R.; and Udupa, A. 2024. Syntax Guided Synthesis Competition. https://sygus-org.github.io. Accessed: 2024-01-16
work page 2024
-
[4]
Auer, P.; Cesa - Bianchi, N.; Freund, Y.; and Schapire, R. E. 2002. The Nonstochastic Multiarmed Bandit Problem. SIAM J. Comput. , 32(1): 48--77
work page 2002
-
[5]
Barbosa, H.; Barrett, C. W.; Brain, M.; Kremer, G.; Lachnitt, H.; Mann, M.; Mohamed, A.; Mohamed, M.; Niemetz, A.; N \" o tzli, A.; Ozdemir, A.; Preiner, M.; Reynolds, A.; Sheng, Y.; Tinelli, C.; and Zohar, Y. 2022. cvc5: A Versatile and Industrial-Strength SMT Solver. In TACAS (1) , volume 13243 of Lecture Notes in Computer Science, 415--442. Springer
work page 2022
-
[6]
Barke, S.; Gonzalez, E. A.; Kasibatla, S. R.; Berg - Kirkpatrick, T.; and Polikarpova, N. 2024. HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis. CoRR, abs/2405.15880
arXiv 2024
-
[7]
Barke, S.; Peleg, H.; and Polikarpova, N. 2020. Just-in-time learning for bottom-up enumerative synthesis. Proc. ACM Program. Lang. , 4( OOPSLA ): 227:1--227:29
work page 2020
-
[8]
Deng, M.; Wang, J.; Hsieh, C.-P.; Wang, Y.; Guo, H.; Shu, T.; Song, M.; Xing, E. P.; and Hu, Z. 2022. Rlprompt: Optimizing discrete text prompts with reinforcement learning. arXiv preprint arXiv:2205.12548
arXiv 2022
Show all 32 references
-
[9]
Giacobbe, M.; Kroening, D.; and Parsert, J. 2022. Neural termination analysis. In ESEC/SIGSOFT FSE , 633--645. ACM
2022
-
[10]
Giesl, J.; Rubio, A.; Sternagel, C.; Waldmann, J.; and Yamada, A. 2019. The Termination and Complexity Competition. In TACAS (3) , volume 11429 of Lecture Notes in Computer Science, 156--166. Springer
2019
-
[11]
A.; Zhang, M.; Mei, Q.; and Bendersky, M
Kong, W.; Hombaiah, S. A.; Zhang, M.; Mei, Q.; and Bendersky, M. 2024. PRewrite: Prompt Rewriting with Reinforcement Learning. arXiv preprint arXiv:2401.08189
2024 arXiv
-
[12]
Lee, W.; Heo, K.; Alur, R.; and Naik, M. 2018. Accelerating search-based program synthesis using learned probabilistic models. In PLDI , 436--449. ACM
2018
-
[13]
Li, C.; Wang, J.; Zhang, Y.; Zhu, K.; Hou, W.; Lian, J.; Luo, F.; Yang, Q.; and Xie, X. 2023. Large language models understand and can be enhanced by emotional stimuli. arXiv preprint arXiv:2307.11760
2023 arXiv
-
[14]
L.; and Liang, P
Li, X. L.; and Liang, P. 2021. Prefix-tuning: Optimizing continuous prompts for generation. arXiv preprint arXiv:2101.00190
2021 arXiv
-
[15]
Li, Y.; Parsert, J.; and Polgreen, E. 2024. Guiding Enumerative Program Synthesis with Large Language Models. In CAV (2) , volume 14682 of Lecture Notes in Computer Science, 280--301. Springer
2024
-
[16]
L.; Choi, Y.; and Hajishirzi, H
Liu, J.; Liu, A.; Lu, X.; Welleck, S.; West, P.; Bras, R. L.; Choi, Y.; and Hajishirzi, H. 2021 a . Generated knowledge prompting for commonsense reasoning. arXiv preprint arXiv:2110.08387
2021 arXiv
-
[17]
Liu, J.; Shen, D.; Zhang, Y.; Dolan, B.; Carin, L.; and Chen, W. 2021 b . What Makes Good In-Context Examples for GPT- 3 ? arXiv preprint arXiv:2101.06804
2021 arXiv
-
[18]
Liu, P.; Yuan, W.; Fu, J.; Jiang, Z.; Hayashi, H.; and Neubig, G. 2023. Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing. ACM Computing Surveys, 55(9): 1--35
2023
-
[19]
Lu, Y.; Bartolo, M.; Moore, A.; Riedel, S.; and Stenetorp, P. 2021. Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. arXiv preprint arXiv:2104.08786
2021 arXiv
-
[20]
Myung, I. J. 2003. Tutorial on Maximum Likelihood Estimation. J. Math. Psychol., 47(1): 90–100
2003
-
[21]
Odena, A.; Shi, K.; Bieber, D.; Singh, R.; Sutton, C.; and Dai, H. 2021. BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration. In ICLR . OpenReview.net
2021
-
[22]
Padhi, S.; Polgreen, E.; Raghothaman, M.; Reynolds, A.; and Udupa, A. 2023. The SyGuS Language Standard Version 2.1. CoRR, abs/2312.06001
2023 arXiv
-
[23]
Parsert, J.; and Polgreen, E. 2024. Reinforcement Learning and Data-Generation for Syntax-Guided Synthesis. In AAAI , 10670--10678. AAAI Press
2024
-
[24]
Pimpalkhare, N.; Mora, F.; Polgreen, E.; and Seshia, S. A. 2021. MedleySolver: Online SMT Algorithm Selection. In Li, C.; and Many \` a , F., eds., Theory and Applications of Satisfiability Testing - SAT 2021 - 24th International Conference, Barcelona, Spain, July 5-9, 2021, P...
2021
-
[25]
Prasad, A.; Hase, P.; Zhou, X.; and Bansal, M. 2022. Grips: Gradient-free, edit-based instruction search for prompting large language models. arXiv preprint arXiv:2203.07281
2022 arXiv
-
[26]
L.; Wallace, E.; and Singh, S
Shin, T.; Razeghi, Y.; Logan IV, R. L.; Wallace, E.; and Singh, S. 2020. Autoprompt: Eliciting knowledge from language models with automatically generated prompts. arXiv preprint arXiv:2010.15980
2020 arXiv
-
[27]
Solar-Lezama, A.; Tancau, L.; Bodik, R.; Seshia, S.; and Saraswat, V. 2006. Combinatorial sketching for finite programs. In Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, 404--415
2006
-
[28]
Weber, T.; Conchon, S.; D \' e harbe, D.; Heizmann, M.; Niemetz, A.; and Reger, G. 2019. The SMT Competition 2015-2018. J. Satisf. Boolean Model. Comput., 11(1): 221--259
2019
-
[29]
H.; Le, Q
Wei, J.; Wang, X.; Schuurmans, D.; Bosma, M.; Ichter, B.; Xia, F.; Chi, E. H.; Le, Q. V.; and Zhou, D. 2022. Chain-of-Thought Prompting Elicits Reasoning in Large Language Models. In NeurIPS
2022
-
[30]
M.; Hamadi, Y.; and de Moura, L
Wintersteiger, C. M.; Hamadi, Y.; and de Moura, L. 2009. A Concurrent Portfolio Approach to SMT Solving. In Bouajjani, A.; and Maler, O., eds., Computer Aided Verification, 715--720. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 978-3-642-02658-4
2009
-
[31]
Zhang, T.; Wang, X.; Zhou, D.; Schuurmans, D.; and Gonzalez, J. E. 2022. Tempera: Test-time prompting via reinforcement learning. arXiv preprint arXiv:2211.11890
2022 arXiv
-
[32]
A Helpful Assistant
Zheng, M.; Pei, J.; and Jurgens, D. 2023. Is "A Helpful Assistant" the Best Role for Large Language Models? A Systematic Evaluation of Social Roles in System Prompts. CoRR, abs/2311.10054
2023 arXiv
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.