Research map / Large language models / Agents, code and math
Online Prompt Selection for Program Synthesis
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes CYANEA, an online multi-armed bandit (k-NN contextual) that selects among symbolic solvers and LLM-prompt pairs for program synthesis queries, with time/token budget allocation.
Problem
Users must choose which LLM, prompting style, or symbolic solver to use for each program synthesis query; wrong choices waste time and money, and no single solver dominates across tasks.
Approach
Frame solver and prompt selection as a contextual multi-armed bandit over solvers (LLM-prompt pairs plus an enumerative solver), using k-nearest-neighbor predictions on query features, a single-layer or layered bandit variant, and exponential-MLE-based time and token budget allocation to run solvers sequentially.
Key results
- CYANEA solves 88.3% of 1269 queries (about 1120 solved) versus 64.3% for the best single solver (llama-p4), a 37.2% improvement in number solved.
- Best CYANEA instance achieves about 96% of the virtual best solver's reward and Par-2 score below 40% of the best single solver's score.
- Virtual best solver solves 91.8% of queries, so CYANEA is within about 4% of the oracle.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use single k-NN solver and prompt selection with r^c reward instead of the best individual solver | Cyanea · Synthesis queries (1,269 queries) | % solved: 88.3% vs 64.3% | Helped |
| use single k-NN solver and prompt selection with r^c reward instead of the best individual solver | Cyanea · Synthesis queries (1,269 queries) | Par-2 score: 37636.3 vs 95251.2 | Helped |
| use single k-NN selection instead of layered double k-NN selection | Cyanea · Synthesis queries (1,269 queries) | % solved: 84.5% -> 88.3% | Helped |
| use single k-NN selection instead of layered double k-NN selection | Cyanea · Synthesis queries (1,269 queries) | % solved: 71.8% -> 87.0% | Helped |
| use linear rather than dynamic budget allocation (ablation) | Single k-NN (r^t) · Synthesis queries (1,269 queries) | % solved: 88.2% -> 87.0% | Hurt |
| use linear rather than dynamic budget allocation (ablation) | Double k-NN (r^c) · Synthesis queries (1,269 queries) | % solved: 84.5% -> 71.8% | Hurt |
| use linear rather than dynamic budget allocation (ablation) | Double k-NN (r^c) · Synthesis queries (1,269 queries) | avg. cost: 6366.8 -> 4589.1 | Mixed |
| select using r^t instead of r^c (ablation) | Single k-NN · Synthesis queries (1,269 queries) | Par-2 score: 37636.3 -> 37813.7 | Helped |
| select using r^c instead of r^t (ablation) | Single k-NN · Synthesis queries (1,269 queries) | avg. cost: 3122 vs 3176.9 | Helped |
| select using r^b instead of r^c (ablation) | Single k-NN · Synthesis queries (1,269 queries) | % solved: 88.1% vs 88.3% | Helped |
| use linear rather than dynamic budget allocation (ablation) | Cyanea single k-NN · Synthesis queries (1,269 queries) | Par-2 score | Mixed |
Surprising findings
- Double-layer k-NN performs worse than single-layer k-NN, attributed to sparse data for lower-layer selectors and higher variance across orderings.
- Linear budget allocation with the double k-NN yields lower average cost but solves far fewer queries (71.8% vs 84.5%).
Limitations
- Evaluated on only two LLMs and one enumerative solver, with a fixed set of six prompt styles.
- Multi-layer bandit has high variance in results due to sparse data for lower-layer selectors.
- Cost estimate for the enumerative solver is a fixed constant, not measured.
Experimental setup
Datasets: SyGuS competition queries ranking function synthesis queries from literature queries generated from SMT competition problems
Benchmarks: SyGuS competition queries ranking function synthesis queries SMT-derived synthesis queries
Metrics: number of queries solved Par-2 score total reward (r^b, r^t, r^c) average solving cost
Baselines: Single k-NN Single k-NN linear Double k-NN Double k-NN linear virtual best solver gpt-p1 through gpt-p6 llama-p1 through llama-p6 enumerator
Builds on: CEGIS Euphony MedleySolver SyGuS-IF
Closest papers by meaning
- On Speeding Up Language Model Evaluation (ICLR 2025 · similarity 0.89)
- HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis (NeurIPS 2024 · similarity 0.89)
- Scaling Prompt Synthesis for Large Language Model Reasoning (ICML 2026 · similarity 0.88)
- What Makes Large Language Models Reason in (Multi-Turn) Code Generation? (ICLR 2025 · similarity 0.88)
- Program Synthesis via Test-Time Transduction (NeurIPS 2025 · similarity 0.88)
- ToolACE: Winning the Points of LLM Function Calling (ICLR 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.