Online Prompt Selection for Program Synthesis

• URL: http://arxiv.org/abs/2501.05247v2
• Date: Wed, 29 Jan 2025 16:52:16 GMT
• Title: Online Prompt Selection for Program Synthesis
• Abstract summary: Large Language Models (LLMs) demonstrate impressive capabilities in the domain of program synthesis.<n>A key challenge for the user is to identify 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.<n>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.
• Score: 14.188804919928591
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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.

Related papers

• Formalize, Don't Optimize: The Heuristic Trap in LLM-Generated Combinatorial Solvers [52.23061619664667]
  Large Language Models (LLMs) struggle to solve complex problems through direct reasoning, so recent neuro-symbolic systems increasingly use them to synthesize executable solvers.<n>We introduce CP-SynC-XL, a benchmark of 100 problems (4,577 instances), and evaluate three solver--construction paradigms: native algorithmic search (Python), constraint modeling through a Python solver API (Python + OR-Tools), and declarative constraint modeling.
  arXiv  Detail & Related papers  (2026-05-12T17:15:45Z)
• Execution-Verified Reinforcement Learning for Optimization Modeling [49.171122807323634]
  Execution-verified learning framework treats a mathematical programming solver as a deterministic, interactive verifier.<n>Experiments on NL4OPT, MAMO, IndustryOR, and OptiBench across Gurobi, OR-Tools, and COPT show that EVOM matches or outperforms process-supervised SFT.
  arXiv  Detail & Related papers  (2026-04-01T03:39:11Z)
• A Solver-in-the-Loop Framework for Improving LLMs on Answer Set Programming for Logic Puzzle Solving [14.391923692962754]
  We introduce a novel ASP-solver-in-the-loop approach for solver-guided instruction-tuning of large language models (LLMs)<n>Our method only requires problem specifications in natural language and their solutions.<n>We apply supervised fine-tuning to train LLMs on curated data and further improve robustness using a solver-guided search.
  arXiv  Detail & Related papers  (2025-12-18T21:45:45Z)
• On the Effectiveness of LLM-as-a-judge for Code Generation and Summarization [54.965787768076254]
  Large Language Models have been recently exploited as judges for complex natural language processing tasks, such as Q&A.<n>We study the effectiveness of LLMs-as-a-judge for two code-related tasks, namely code generation and code summarization.
  arXiv  Detail & Related papers  (2025-07-22T13:40:26Z)
• Towards Efficient Multi-LLM Inference: Characterization and Analysis of LLM Routing and Hierarchical Techniques [14.892995952768352]
  Language Models (LMs) have excelled at tasks like text generation, summarization, and question answering.<n>Their inference remains computationally expensive and energy intensive in settings with limited hardware, power, or bandwidth.<n>Recent approaches have introduced multi LLM intelligent model selection strategies that dynamically allocate computational resources based on query complexity.
  arXiv  Detail & Related papers  (2025-06-06T23:13:08Z)
• LLM-Guided Compositional Program Synthesis [16.867355177975387]
  Large language models (LLMs) have the ability to solve PBE tasks by generating code in different target languages, but they can fail unpredictably. We introduce a novel technique that recovers from failure by constructing simpler subtasks for the LLM to solve.
  arXiv  Detail & Related papers  (2025-03-12T00:36:43Z)
• Scaling Autonomous Agents via Automatic Reward Modeling And Planning [52.39395405893965]
  Large language models (LLMs) have demonstrated remarkable capabilities across a range of tasks. However, they still struggle with problems requiring multi-step decision-making and environmental feedback. We propose a framework that can automatically learn a reward model from the environment without human annotations.
  arXiv  Detail & Related papers  (2025-02-17T18:49:25Z)
• PickLLM: Context-Aware RL-Assisted Large Language Model Routing [0.5325390073522079]
  PickLLM is a lightweight framework that relies on Reinforcement Learning (RL) to route on-the-fly queries to available models.<n>We demonstrate the speed of convergence for different learning rates and improvement in hard metrics such as cost per querying session and overall response latency.
  arXiv  Detail & Related papers  (2024-12-12T06:27:12Z)
• MetaLLM: A High-performant and Cost-efficient Dynamic Framework for Wrapping LLMs [20.793892860721712]
  We introduce MetaLLM, a framework that dynamically and intelligently routes each query to the optimal large language models (LLMs) By framing the selection problem as a multi-armed bandit, MetaLLM balances prediction accuracy and cost efficiency under uncertainty. Our experiments, conducted on popular LLM platforms such as OpenAI and Together AI, showcase MetaLLM's efficacy in real-world scenarios.
  arXiv  Detail & Related papers  (2024-07-15T15:45:07Z)
• OptiBench Meets ReSocratic: Measure and Improve LLMs for Optimization Modeling [62.19438812624467]
  Large language models (LLMs) have exhibited their problem-solving abilities in mathematical reasoning. We propose OptiBench, a benchmark for End-to-end optimization problem-solving with human-readable inputs and outputs.
  arXiv  Detail & Related papers  (2024-07-13T13:27:57Z)
• Can Large Language Models Play Games? A Case Study of A Self-Play Approach [61.15761840203145]
  Large Language Models (LLMs) harness extensive data from the Internet, storing a broad spectrum of prior knowledge. Monte-Carlo Tree Search (MCTS) is a search algorithm that provides reliable decision-making solutions. This work introduces an innovative approach that bolsters LLMs with MCTS self-play to efficiently resolve turn-based zero-sum games.
  arXiv  Detail & Related papers  (2024-03-08T19:16:29Z)
• Are More LLM Calls All You Need? Towards Scaling Laws of Compound Inference Systems [76.69936664916061]
  We study how the number of LM calls affects the performance of Vote and Filter-Vote. We find, surprisingly, that across multiple language tasks, the performance of both Vote and Filter-Vote can first increase but then decrease as a function of the number of LM calls.
  arXiv  Detail & Related papers  (2024-03-04T19:12:48Z)
• All Language Models Large and Small [4.676589803026312]
  Many leading language models (LMs) use high-intensity computational resources both during training and execution. This poses the challenge of lowering resource costs for deployment and faster execution of decision-making tasks. We introduce a novel plug-and-play LM framework named Language Optimising Network Distribution (LONDI) framework.
  arXiv  Detail & Related papers  (2024-02-19T11:28:20Z)
• DiLA: Enhancing LLM Tool Learning with Differential Logic Layer [11.810200077863172]
  We propose a novel differential logic layer-aided language modeling (DiLA) approach, where logical constraints are integrated into the forward and backward passes of a network layer. We evaluate the performance of DiLA on two classic reasoning problems and empirically demonstrate its consistent outperformance against existing prompt-based and solver-aided approaches.
  arXiv  Detail & Related papers  (2024-02-19T07:38:57Z)
• Solving Math Word Problem with Problem Type Classification [12.700472956406005]
  Math word problems (MWPs) require analyzing text descriptions and generating mathematical equations to derive solutions. Existing works focus on solving MWPs with two types of solvers: tree-based solver and large language model (LLM) solver. This paper utilizes multiple ensemble approaches to improve MWP-solving ability.
  arXiv  Detail & Related papers  (2023-08-26T10:35:16Z)
• LaGR-SEQ: Language-Guided Reinforcement Learning with Sample-Efficient Querying [71.86163159193327]
  Large language models (LLMs) have recently demonstrated their impressive ability to provide context-aware responses via text. This ability could potentially be used to predict plausible solutions in sequential decision making tasks pertaining to pattern completion. We introduce LaGR, which uses this predictive ability of LLMs to propose solutions to tasks that have been partially completed by a primary reinforcement learning (RL) agent.
  arXiv  Detail & Related papers  (2023-08-21T02:07:35Z)
• SatLM: Satisfiability-Aided Language Models Using Declarative Prompting [68.40726892904286]
  We propose a new satisfiability-aided language modeling (SatLM) approach for improving the reasoning capabilities of large language models (LLMs) We use an LLM to generate a declarative task specification rather than an imperative program and leverage an off-the-shelf automated theorem prover to derive the final answer. We evaluate SATLM on 8 different datasets and show that it consistently outperforms program-aided LMs in the imperative paradigm.
  arXiv  Detail & Related papers  (2023-05-16T17:55:51Z)
• LLM+P: Empowering Large Language Models with Optimal Planning Proficiency [46.20085545432116]
  Large language models (LLMs) have demonstrated remarkable zero-shot generalization abilities. classical planners, once a problem is given in a formatted way, can use efficient search algorithms to quickly identify correct, or even optimal, plans. This paper introduces LLM+P, the first framework that incorporates the strengths of classical planners into LLMs.
  arXiv  Detail & Related papers  (2023-04-22T20:34:03Z)
• Leveraging Large Language Models for Multiple Choice Question Answering [6.198523595657983]
  We show that a model with high MCSB ability performs much better with the natural approach than with the traditional approach. We show that a model with high MCSB ability performs much better with the natural approach than with the traditional approach.
  arXiv  Detail & Related papers  (2022-10-22T05:04:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.