Beyond Average Performance: Dynamic Instance Clustering and Specialized Algorithm Design in LLM-Assisted Evolutionary Search

• URL: http://arxiv.org/abs/2608.03129v1
• Date: Tue, 04 Aug 2026 04:59:48 GMT
• Title: Beyond Average Performance: Dynamic Instance Clustering and Specialized Algorithm Design in LLM-Assisted Evolutionary Search
• Abstract summary: We propose Dynamic Instance Clustering and Specialized Algorithm Design (DyCA), an LES framework with a feature-free, structure-aware mechanism for constructing reliable algorithm portfolios.<n>DyCA treats instance clustering as a co-evolving component within the search process, reusing evaluation data as feature-free signals.<n> Experimental results show DyCA outperforms state-of-the-art LES baselines, improving tail robustness by an average of 15.2% and overall performance by 7.1%.
• Score: 27.981714638078966
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large Language Model-assisted Evolutionary Search (LES) has emerged as a powerful paradigm for automated algorithm design. However, existing LES methods primarily optimize for average performance, inherently directing search effort toward instances that contribute most to this metric while leaving others poorly served, resulting in weak tail robustness and limited real-world reliability. To address this limitation, we propose Dynamic Instance Clustering and Specialized Algorithm Design (DyCA), an LES framework with a feature-free, structure-aware mechanism for constructing reliable algorithm portfolios under heterogeneous instance distributions. DyCA treats instance clustering as a co-evolving component within the search process, reusing accumulated evaluation data as feature-free signals to progressively partition instances with similar algorithmic response patterns. The uncovered clusters decompose the mixed objective into a set of structure-aware sub-objectives, thereby enabling finer-grained and more adaptive guidance for specialized algorithm design. Experimental results across four algorithm design tasks with heterogeneous instances demonstrate that DyCA outperforms state-of-the-art LES baselines, improving tail robustness by an average of 15.2\% and overall performance by 7.1\% while maintaining competitive head performance.

Related papers

• Imputation Meets Clustering: Exploiting Latent Subgroup Structure for Missing Data Recovery [52.29866804948133]
  We propose CAGI (Cluster-Aware Generative Imputation), a framework that reformulates clustering and imputation as a mutually reinforcing co-optimization process.<n>Experiments on 14 benchmark datasets with 15 representative baselines demonstrate the superiority of CAGI.
  arXiv  Detail & Related papers  (2026-07-08T02:50:02Z)
• Efficient Test-time Inference for Generative Planning Models [2.993222488868623]
  We show that a modified version of a classical Open-Closed List (OCL) search provides just such an efficient inference procedure.<n>Our algorithm synergizes two learned components: a generative model that performs fast rollouts from intermediate states and a model that prioritizes among candidate reasoning paths.
  arXiv  Detail & Related papers  (2026-05-30T08:46:44Z)
• FrontierOR: Benchmarking LLMs' Capacity for Efficient Algorithm Design in Large-Scale Optimization [61.43300970020897]
  Large language models (LLMs) are increasingly used for optimization modeling and solver-code generation.<n>Existing benchmarks are limited to small or simplified examples far below real-world scale and complexity.<n>We introduce FrontierOR, among the first benchmarks to evaluate LLM-based efficient algorithm design for realistic large-scale optimization problems.
  arXiv  Detail & Related papers  (2026-05-24T20:10:42Z)
• CDEoH: Category-Driven Automatic Algorithm Design With Large Language Models [18.725552141930542]
  Category Driven Automatic Algorithm Design with Large Language Models (CDEoH)<n>We propose Category Driven Automatic Algorithm Design with Large Language Models (CDEoH)<n>We show that CDEoH effectively mitigates convergence toward a single evolutionary direction, significantly enhancing evolutionary stability and achieving consistently superior average performance across tasks and scales.
  arXiv  Detail & Related papers  (2026-03-08T06:20:05Z)
• TIDE: Tuning-Integrated Dynamic Evolution for LLM-Based Automated Heuristic Design [7.264986493460248]
  TIDE is a Tuning-Integrated Dynamic Evolution framework designed to decouple structural reasoning from parameter optimization.<n> experiments across nine optimization problems demonstrate that TIDE significantly outperforms state-of-the-art tuning methods.
  arXiv  Detail & Related papers  (2026-01-29T04:00:02Z)
• An Evolutionary Framework for Automatic Optimization Benchmark Generation via Large Language Models [0.0]
  We propose an evolutionary automatic benchmark generation framework that leverages a large language model (LLM) as a generative operator.<n>In this framework, the LLM serves as an evolutionary operator that generates and evolves benchmark problems within a flexible, expressive representation space.<n> Experimental results show that LLM-EBG successfully produces benchmark problems in which the designated target algorithm consistently outperforms the comparative algorithm in more than 80% of trials.
  arXiv  Detail & Related papers  (2026-01-19T04:58:15Z)
• LLM-Based Instance-Driven Heuristic Bias In the Context of a Biased Random Key Genetic Algorithm [0.9214658764451348]
  We introduce a novel framework that integrates Large Language Models (LLMs) with a Biased Random-Key Genetic Algorithm (BRKGA) to solve the NP-hard Longest Run Subsequence problem.<n>Our approach extends the instance-driven bias paradigm by introducing a human-LLM collaborative process to co-design and implement a set of computationally efficient metrics.<n>Results show that our top-performing hybrid, BRKGA+Llama-4-Maverick, achieves significant improvements over the baseline.
  arXiv  Detail & Related papers  (2025-09-05T21:46:41Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• Rethinking Clustering-Based Pseudo-Labeling for Unsupervised Meta-Learning [146.11600461034746]
  Method for unsupervised meta-learning, CACTUs, is a clustering-based approach with pseudo-labeling. This approach is model-agnostic and can be combined with supervised algorithms to learn from unlabeled data. We prove that the core reason for this is lack of a clustering-friendly property in the embedding space.
  arXiv  Detail & Related papers  (2022-09-27T19:04:36Z)
• Evolving Pareto-Optimal Actor-Critic Algorithms for Generalizability and Stability [67.8426046908398]
  Generalizability and stability are two key objectives for operating reinforcement learning (RL) agents in the real world. This paper presents MetaPG, an evolutionary method for automated design of actor-critic loss functions.
  arXiv  Detail & Related papers  (2022-04-08T20:46:16Z)
• Towards Uncovering the Intrinsic Data Structures for Unsupervised Domain Adaptation using Structurally Regularized Deep Clustering [119.88565565454378]
  Unsupervised domain adaptation (UDA) is to learn classification models that make predictions for unlabeled data on a target domain. We propose a hybrid model of Structurally Regularized Deep Clustering, which integrates the regularized discriminative clustering of target data with a generative one. Our proposed H-SRDC outperforms all the existing methods under both the inductive and transductive settings.
  arXiv  Detail & Related papers  (2020-12-08T08:52:00Z)

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.