Research map / Large language models / Agents, code and math
Ballad: Bandit-Based LLM Routing for Automated Heuristic Discovery
Samidha Verma, Ankit Anand, Sayan Ranu
AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Ballad, a bandit-based router that selects among LLMs during automated heuristic discovery, arguing that the most expensive models do not consistently yield better heuristics.
Problem
Automated heuristic discovery (AHD) uses LLMs to iteratively mutate and refine heuristics for NP-hard combinatorial optimization problems, but it is unclear which LLM to use at each step, since larger and more expensive models do not consistently produce better heuristics.
Approach
Treats choice of LLM at each mutation step as a multi-armed bandit problem, routing queries across models to balance heuristic quality and cost rather than always using the most powerful model.
Key results
- Across multiple NP-hard combinatorial optimization problems, no consistent advantage was found for larger, more expensive LLMs in automated heuristic discovery.
Surprising findings
- More powerful and more expensive LLMs do not consistently yield better heuristics in AHD.
Closest papers by meaning
- HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs (AAAI 2025 · similarity 0.88)
- PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs (ICML 2026 · similarity 0.88)
- LLMs Improving LLMs: Agentic Discovery for Test-Time Scaling (NeurIPS 2026 · similarity 0.88)
- EVOLvE: Evaluating and Optimizing LLMs For In-Context Exploration (ICML 2025 · similarity 0.88)
- SayCanPay: Heuristic Planning with Large Language Models Using Learnable Domain Knowledge (AAAI 2024 · similarity 0.87)
- ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution (NeurIPS 2024 · similarity 0.87)
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.
