RAISE: LLM-based Automated Heuristic Design with Robust Adversary Instance Search

• URL: http://arxiv.org/abs/2606.31801v1
• Date: Tue, 30 Jun 2026 15:19:27 GMT
• Title: RAISE: LLM-based Automated Heuristic Design with Robust Adversary Instance Search
• Abstract summary: We propose a framework that integrates constrained worst-case instance search within a neighborhood of a training distribution.<n> RAISE consistently maintains strong performance across all tested and problem scales.
• Score: 2.8822232242646533
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Automated Heuristic Design (AHD) with Large Language Models (LLMs) has shown remarkable progress in discovering high-quality heuristics. However, existing LLM-based AHD methods optimize heuristics for a fixed training instance set and may fail catastrophically when deployed under real-world distributional shifts. We propose Robust Adversary Instance Search (RAISE), a framework that integrates constrained worst-case instance search within a principled neighborhood of the training distribution into the LLM-based evolutionary search loop. RAISE treats robust AHD as a constrained adversarial instance search problem: the outer loop evolves heuristics via LLM operators, while an LLM-free inner loop efficiently identifies hard instances within an epsilon-ball around the training instance set using a basis distribution parameterization with boundary projection. Comprehensive experiments on Online Bin Packing (OBP), Online Job Shop Scheduling (OJSP), and Online Vehicle Routing (OVRP) across five distribution families demonstrate that existing LLM-based AHD methods degrade by up to 19 times under distribution shift, while RAISE consistently maintains strong performance across all tested distributions and problem scales

Related papers

• MOSAIC: Adversarial Co-evolution of Specialist Heuristics and Problem Instances for LLM-based Automated Heuristic Design [16.59846708454225]
  We propose a grid-based framework that adversarially co-evolves problem instances and specialist features inside a Quality-Diversity (QD) archive.<n>For each pair sampled from distant grid regions, an LLM-guided evolutionary loop generates discriminative instances.<n>A LLM then contrasts the two reflections to produce multi-directional insights that persist in those regions and guide crossover and mutation.
  arXiv  Detail & Related papers  (2026-07-31T04:22:17Z)
• AHD Agent: Agentic Reinforcement Learning for Automatic Heuristic Design [5.7547035595428255]
  Automatic design (AHD) has emerged as a promising paradigm for solving NP-hard optimization problems.<n>Existing AHD frameworks typically treat large language models (LLMs) as passive generators within fixed contexts.<n>We propose AHD Agent, a novel tool-integrated, multi-turn framework that empowers LLMs to proactively decide whether to generate tools or retrieve targeted evidence.
  arXiv  Detail & Related papers  (2026-05-09T07:36:45Z)
• Rethinking LLM-Driven Heuristic Design: Generating Efficient and Specialized Solvers via Dynamics-Aware Optimization [21.449921296295884]
  We propose Dynamics-Aware Heuristics (DASH), a framework that co-optimizes solver search mechanisms and runtime schedules guided by a convergence-aware metric.<n>DASH improves runtime efficiency by over 3 times, while surpassing the solution quality of state-of-the-art baselines across diverse problem scales.
  arXiv  Detail & Related papers  (2026-01-14T05:06:42Z)
• ArenaRL: Scaling RL for Open-Ended Agents via Tournament-based Relative Ranking [84.07076200941474]
  ArenaRL is a reinforcement learning paradigm that shifts from pointwise scalar scoring to intra-group relative ranking.<n>We construct an intra-group adversarial arena and devise a tournament-based ranking scheme to obtain stable advantage signals.<n>Experiments show that ArenaRL substantially outperforms standard RL baselines.
  arXiv  Detail & Related papers  (2026-01-10T08:43:07Z)
• Diffusion LLMs are Natural Adversaries for any LLM [50.88535293540971]
  We introduce a novel framework that transforms the resource-intensive (adversarial) prompt optimization problem into an emphefficient, amortized inference task<n>Our core insight is that pretrained, non-autoregressive generative LLMs, can serve as powerful surrogates for prompt search.<n>We find that the generated prompts are low-perplexity, diverse jailbreaks that exhibit strong transferability to a wide range of black-box target models.
  arXiv  Detail & Related papers  (2025-10-31T19:04:09Z)
• Inpainting-Guided Policy Optimization for Diffusion Large Language Models [67.97530437998117]
  Masked diffusion large language models (dLLMs) are emerging as promising alternatives to autoregressive LLMs.<n>We explore how inpainting can inform RL algorithm design for dLLMs.
  arXiv  Detail & Related papers  (2025-09-12T16:44:31Z)
• Agentic Reinforced Policy Optimization [66.96989268893932]
  Large-scale reinforcement learning with verifiable rewards (RLVR) has demonstrated its effectiveness in harnessing the potential of large language models (LLMs) for single-turn reasoning tasks.<n>Current RL algorithms inadequately balance the models' intrinsic long-horizon reasoning capabilities and their proficiency in multi-turn tool interactions.<n>We propose Agentic Reinforced Policy Optimization (ARPO), a novel agentic RL algorithm tailored for training multi-turn LLM-based agents.
  arXiv  Detail & Related papers  (2025-07-26T07:53:11Z)
• Iterative Self-Incentivization Empowers Large Language Models as Agentic Searchers [74.17516978246152]
  Large language models (LLMs) have been widely integrated into information retrieval to advance traditional techniques.<n>We propose EXSEARCH, an agentic search framework, where the LLM learns to retrieve useful information as the reasoning unfolds.<n>Experiments on four knowledge-intensive benchmarks show that EXSEARCH substantially outperforms baselines.
  arXiv  Detail & Related papers  (2025-05-26T15:27:55Z)
• LLM-AutoDiff: Auto-Differentiate Any LLM Workflow [58.56731133392544]
  We introduce LLM-AutoDiff: a novel framework for Automatic Prompt Engineering (APE)<n>LLMs-AutoDiff treats each textual input as a trainable parameter and uses a frozen backward engine to generate feedback-akin to textual gradients.<n>It consistently outperforms existing textual gradient baselines in both accuracy and training cost.
  arXiv  Detail & Related papers  (2025-01-28T03:18:48Z)
• Invar-RAG: Invariant LLM-aligned Retrieval for Better Generation [43.630437906898635]
  We propose a novel two-stage fine-tuning architecture called Invar-RAG. In the retrieval stage, an LLM-based retriever is constructed by integrating LoRA-based representation learning. In the generation stage, a refined fine-tuning method is employed to improve LLM accuracy in generating answers based on retrieved information.
  arXiv  Detail & Related papers  (2024-11-11T14:25:37Z)

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.