LLM-Guided Graph Generation for Structure-Based Loc... | AI Research

The paper "LLM-Guided Graph Generation for Structure-Based Local Improvement Methods" introduces an automated pipeline that uses Large Language Models (LLMs) to create problem-agnostic graph generators for constraint optimization. By converting diverse MiniZinc problems into a uniform weighted graph representation, the researchers enable a structure-based local improvement framework (SLIM) to optimize various problem types without requiring manual, domain-specific engineering.

Automating Structure Extraction

Traditionally, structure-guided local improvement methods require significant manual effort from domain experts to design variable selection strategies tailored to specific problem types. This paper proposes using an LLM as a "semantic compiler." By providing an LLM with semantic guidelines, the authors generate a Python-based graph generator for each MiniZinc model. This generator maps any instance of a problem into a uniform graph where nodes represent decision variables—carrying weights and domain sizes—and edges represent constraint relationships with coupling strengths. This process is a one-time effort per problem type, allowing the resulting SLIM framework to operate on a standardized structure regardless of the original problem domain.

Standardized Optimization and Selection

Once the uniform graph is generated, the SLIM framework performs local optimization by selecting neighborhoods of variables based on the graph’s weights and topology. The authors utilize two primary extraction methods: a breadth-first search (BFS) approach that captures local structure and a random selection method. Because all problem instances share the same generic graph format, the researchers can extract 54 consistent topological and statistical features from any instance. These features are then used to train machine learning models to select the most effective SLIM configuration from a set of 30 options, enabling cross-problem algorithm selection.

Performance Results

The authors evaluated their pipeline on instances across 20 MiniZinc competition problems. They report that their approach achieved a 39.5% average problem-weighted win rate against a one-shot Gurobi baseline, which more than doubled the 19.3% win rate of the best single configuration. After applying configuration and feature ablation, the performance increased to 44.0%. The results indicate that while the pipeline performs well on most problems, it showed lower performance on specific types such as rectangle-packing and VRP, where it yielded worse solutions on more than 50% of instances.

Franklin Analysis

The evidence suggests that the primary value of this approach is the reduction of expert intervention in constraint optimization. By shifting the burden of structure extraction from human engineers to an LLM-generated program, the researchers successfully created a modular system that generalizes across heterogeneous problem types. The reliance on a uniform graph representation is the key mechanism that enables both the generic SLIM operations and the cross-problem algorithm selection, as it allows the same feature set to be applied to disparate optimization tasks.