Online Prompt Selection for Program Synthesis

Yixuan Li, Lewis Frampton, Federico Mora, Elizabeth Polgreen

Abstract

Program synthesis—the automated generation of code from formal specifications—has been significantly advanced by Large Language Models (LLMs). However, the performance of these models is highly sensitive to prompt engineering and the specific nature of the task, with no single model or prompt style consistently outperforming others. This paper introduces CYANEA, an online learning framework that treats solver selection as a Contextual Multi-Armed Bandit (MAB) problem. By dynamically selecting from a portfolio of LLMs, prompt templates, and symbolic solvers based on task features, CYANEA achieves an 88.3% success rate, solving 37.2% more problems than the best single-model approach and reaching 96.1% of the theoretical maximum performance of its portfolio.

Introduction

In the current landscape of AI-assisted programming, developers face a "selection tax." While LLMs like GPT-4 or Llama-3 are powerful, their efficacy is notoriously fickle; a prompt that succeeds for one logic type may fail for another. Furthermore, traditional symbolic solvers often outperform neural models on logically dense, low-level tasks. Currently, users must either commit to a single "good enough" model or manually iterate through prompts—a process that is both time-consuming and computationally expensive.

This research addresses the challenge of automated solver selection. The authors propose CYANEA, a system designed to learn which combination of model and prompt is most likely to succeed for a given synthesis query in real-time. By framing this as an online optimization problem, CYANEA minimizes latency and token costs while maximizing the probability of finding a valid solution.

The CYANEA Framework

1. Problem Featurization

When a new synthesis query arrives (formatted in the standard SyGuS-IF logic), CYANEA first converts it into a feature vector. These features include:

  • Keywords: Presence of operators like +, div, or ite (if-then-else).
  • Metadata: Query length and the specific logic domain (e.g., BitVectors vs. Linear Integer Arithmetic).

2. Contextual Multi-Armed Bandit (MAB) Selection

CYANEA utilizes a $k$-Nearest Neighbor ($k$-NN) algorithm to act as its selector. When presented with a new task, the system identifies similar problems solved in the past and ranks its "arms" (available solvers) based on historical rewards. This allows the system to adapt its strategy based on the specific context of the query.

3. The Solver Portfolio

The system’s portfolio is diverse, combining neural and symbolic techniques:

  • Large Language Models: GPT-3.5 and Llama-3-70B.
  • Prompt Engineering: Six distinct templates, including few-shot examples, "role-playing" prompts, and emotional stimuli (e.g., "This is important for my career").
  • The Lisp Bridge: A notable strategy where the LLM is prompted to write code in Lisp before translating it to SyGuS-IF. This leverages the LLM's familiarity with Lisp's parenthesized notation, which mirrors the target synthesis language.
  • Symbolic Solver: An enumerative solver based on the A* search algorithm, providing a fallback for tasks where LLMs struggle with logical precision.

4. Budget Allocation

To manage resources, CYANEA uses Maximum Likelihood Estimation (MLE) to model the probability of a solver succeeding within specific time or token constraints. It greedily allocates its total budget across the ranked list of solvers until a solution is found or the budget is exhausted.

Experimental Evaluation

The authors evaluated CYANEA on a comprehensive dataset of 1,269 synthesis queries drawn from the SyGuS Competition, ranking function literature, and SMT (Satisfiability Modulo Theories) benchmarks.

Key Results

  • Superior Success Rate: CYANEA solved 88.3% of all tasks, significantly outperforming the best single-solver configuration (Llama-3 with a fixed prompt), which only achieved 64.3%.
  • Efficiency: Using the Par-2 metric (which penalizes timeouts), CYANEA scored less than 40% of the best single solver, indicating it finds solutions much faster on average.
  • Near-Optimality: The framework reached 96.1% of the "Virtual Best Solver" (VBS)—the theoretical performance achieved if the optimal solver were chosen perfectly for every task.

Discussion and Insights

The Importance of Hybrid Approaches

The inclusion of a symbolic enumerative solver proved critical. While LLMs are adept at high-level reasoning, they often "hallucinate" complex logic for simple problems that symbolic solvers can solve via brute-force search in milliseconds.

Prompting Nuances

The study confirmed that "vibe-based" prompting—such as assigning the LLM a role or adding emotional pressure—yields measurable performance gains in formal synthesis. Furthermore, the "Lisp Bridge" demonstrated that intermediate representations can effectively close the gap between natural language and niche formal logics.

Architecture: Single vs. Multi-Layer

Interestingly, the researchers found that a single-layer bandit (choosing from all model-prompt pairs simultaneously) outperformed a hierarchical bandit (choosing the model first, then the prompt). This was attributed to data sparsity; the lower-level bandits in a hierarchy did not receive enough examples to learn effective selection policies.

Conclusion and Future Work

CYANEA demonstrates that online learning is a highly effective way to navigate the volatility of LLM performance in program synthesis. By automating the selection of models and prompts, the framework removes the "selection tax" from the user while achieving near-optimal performance. Future research may explore "meta-optimization," where LLMs generate new prompt styles on the fly, and more sophisticated learning algorithms to handle even larger search spaces of possible solvers.

Summary updated

BibTeX
@inproceedings{li2025online,
  author = {Yixuan Li and Lewis Frampton and Federico Mora and Elizabeth Polgreen},
  title = {{Online Prompt Selection for Program Synthesis}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i11.33227},
}
Figure