💻 computer science

Relation Reasoning with LLMs in Expensive Optimization

This paper introduces R2SAEA, a novel surrogate-assisted evolutionary algorithm that leverages a reinforcement-trained large language model to perform efficient, zero-shot relation-based reasoning for expensive optimization problems, thereby overcoming the retraining overhead of traditional surrogates and achieving state-of-the-art performance.

Original authors: Ye Lu, Bingdong Li, Aimin Zhou, Hao Hao

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ye Lu, Bingdong Li, Aimin Zhou, Hao Hao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the best route through a massive, foggy mountain range. The problem is that checking the elevation of any single spot takes a full day of hiking (this is what the paper calls an "expensive evaluation"). You have a limited number of days (a tight budget), so you can't just hike everywhere.

Traditionally, scientists use "maps" (mathematical models) to guess where the low points are. But these maps are tricky: as you explore new areas, the old maps become useless, and you have to spend valuable time redrawing them from scratch. This is the bottleneck the paper tries to solve.

Here is the paper's solution, broken down into simple concepts:

1. The New "Map": A Smart Judge Instead of a Calculator

Instead of trying to predict the exact height of a spot (which is hard and requires constant redrawing), the authors teach an AI to act like a judge in a boxing match.

Old Way: The AI tries to guess the exact score of every fighter.
New Way (R2SAEA): The AI only looks at two fighters at a time and answers a simple question: "Is Fighter A better than Fighter B?"

This is called Relation Reasoning. Since evolutionary algorithms (the search method) mostly care about which option is better than another, not the exact numbers, this "judge" approach is much more efficient.

2. The "Anchor" Trick: Avoiding the Library Overload

If you have 100 hikers and want to know how every single one compares to every other one, you'd have to ask the judge about 10,000 pairs. That's too many questions for the AI to handle at once (it would run out of "memory" or context).

The authors invented an "Anchor" strategy:

Instead of asking about everyone at once, they pick one hiker as the "Anchor" (the reference point).
They ask the AI: "How does Hiker A compare to the Anchor? How does Hiker B compare to the Anchor? How does Hiker C compare to the Anchor?"
They do this for every hiker, one by one.
The Result: This turns a massive, confusing pile of questions into a series of small, manageable lists. It's like asking a teacher to grade a class by comparing every student to the "class average" one by one, rather than trying to compare every student to every other student simultaneously.

3. The "Voting" System: Turning Opinions into a Score

After the AI judges all the pairs, it has a bunch of "Better/Worse" opinions. How do you pick the best hiker?

The system uses a Voting Mechanism.
If the AI says "Hiker X is better than 90% of the Anchors," Hiker X gets a high score.
If Hiker X is worse than most, they get a low score.
This converts the AI's "opinions" into a clear ranking, so the search algorithm knows exactly which hikers to send out for the expensive, real-world check.

4. Training the Judge: Reinforcement Learning (The "Coach")

The authors didn't just use a generic AI; they trained a specific one (based on a model called Qwen2.5) to be a master judge.

They created a "Coach" (Reinforcement Learning) that watched the AI make guesses.
If the AI guessed the relationship correctly, the Coach gave a reward. If it guessed wrong, it got a penalty.
Over time, the AI learned to spot the subtle differences between solutions much better than a generic AI could.
The Magic: Once trained, this AI doesn't need to be retrained every day. It can just "think" (infer) on the fly. This saves a huge amount of time and money.

5. The "Pocket-Sized" Judge: Running on Small Devices

Usually, powerful AI needs giant, expensive supercomputers. The authors showed that by shrinking the model and compressing its "brain" (a process called quantization), this smart judge can run on small, portable devices like a high-end laptop or even a specialized chip used in drones or robots (edge devices).

The Bottom Line

The paper claims that by turning the problem into a series of simple "A vs. B" comparisons, using a clever "Anchor" method to keep the questions manageable, and training a specialized AI judge, they can find the best solutions to difficult problems using far fewer expensive tests than previous methods.

It's faster: No need to redraw the map every time.
It's cheaper: The AI can run on smaller, less expensive hardware.
It works better: In tests, this method found better solutions than other top-tier methods across both single-goal and multi-goal problems.

The authors have made their "smart judge" and the code available for others to use, proving that you don't need a supercomputer to solve expensive optimization problems if you ask the right questions.

Technical Summary: R2SAEA – Relation Reasoning with LLMs in Expensive Optimization

Problem Statement
Expensive Optimization Problems (EOPs) are characterized by black-box objective functions where evaluations are costly (e.g., physical experiments, high-fidelity simulations) and gradients are unavailable. The primary bottleneck in solving EOPs is the limited evaluation budget. While Surrogate-Assisted Evolutionary Algorithms (SAEAs) mitigate this by using learned models to screen candidates, conventional surrogates (regression, classification, or relation models) typically require frequent retraining as the population evolves. This "train-predict" loop incurs significant computational overhead, which can negate the efficiency gains of surrogate assistance. Furthermore, while Large Language Models (LLMs) have shown promise in optimization, directly deploying frontier models in evolutionary loops is often impractical due to high inference costs and latency, and smaller models lack the specific reasoning capabilities required for reliable relation inference.

Methodology: R2SAEA
The paper proposes R2SAEA (Reinforcement-trained relation-based LLM surrogate assisted evolutionary algorithm), a framework that replaces the traditional retraining loop with an inference-only, relation-based surrogate powered by a fine-tuned LLM. The methodology consists of three core components:

Relation Reasoning as In-Context Learning:
Instead of training a parametric model, the paper casts relation surrogate modeling as an in-context pairwise reasoning task. The LLM is prompted to predict the relative superiority between solution pairs based on a set of labeled examples (context). Two mainstream criteria are supported:
- Function Criterion (C1): Binary labeling ( $+1/-1$ ) based on objective value superiority.
- Category Criterion (C2): Ternary labeling ( $+1/0/-1$ ) distinguishing inter-class (good vs. bad) and intra-class relationships.
Anchor-Based Iterative Context Construction:
To address the quadratic complexity of pairwise comparisons ( $O((n+q)^2)$ ) which exceeds context limits, the authors introduce an anchor-based iterative strategy.
- The task is decomposed into $n$ inference rounds, where each existing solution in the context set acts as a fixed "anchor."
- For each anchor, the LLM receives a prompt containing labeled relations between the anchor and other context solutions, plus unlabeled relations between the anchor and candidate solutions.
- This reduces prompt complexity to linear ( $O(n+q)$ ) per round, ensuring stability and scalability.
Voting-Based Aggregation:
The LLM outputs a matrix of pairwise relations. These are aggregated into absolute quality scores for candidate selection via a voting mechanism:
- For C1, the score is the negative sum of predicted relations (counting how many anchors a candidate beats).
- For C2, a normalized score is computed based on how often candidates are judged "better" or "worse" by "good" and "bad" anchor groups.
Reinforcement Learning Fine-Tuning (GRPO):
To enable efficient, zero-shot deployment without per-generation retraining, the authors fine-tune a compact LLM (Qwen2.5-7B) using Group Relative Policy Optimization (GRPO).
- Data: Training trajectories are generated from evolutionary runs on benchmark functions (LZG, CEC), creating instruction pairs where the ground truth is the actual pairwise relation.
- Reward: A rule-based reward function evaluates JSON output format compliance, relation accuracy, and output diversity (penalizing degenerate predictions).
- Advantage: GRPO eliminates the need for a separate critic model, using group-wise reward normalization to provide stable learning signals for discrete relation labels.

Key Contributions

Formulation: The paper formulates relation-based surrogate modeling as an in-context LLM reasoning problem under C1 and C2 criteria, introducing an anchor-based iterative prompt construction mechanism to reduce context complexity from quadratic to linear.
Aggregation Strategy: A voting-based aggregation strategy is designed to convert predicted pairwise relations into absolute scores for candidate ranking, enabling standard SAEA selection operators to utilize LLM outputs.
RL Pipeline: An end-to-end RL fine-tuning pipeline is established using evolutionary trajectories and GRPO. The resulting models (ReLLM-C1/C2) demonstrate superior relation prediction accuracy compared to strong general-purpose LLMs and enable zero-shot deployment without retraining.
Performance: The framework achieves state-of-the-art (SOTA) performance on both single-objective (SOP) and multi-objective (MOP) expensive optimization benchmarks, outperforming classical SAEAs (regression, classification, and relation-based) and general LLM baselines.

Experimental Results

Optimization Performance: On single-objective benchmarks (LZG, YLL suites), R2SAEA-SOP achieved the best mean rank (2.69) among seven algorithms, outperforming relation-based DRSO in 22/45 cases and Bayesian Optimization in 23/45 cases. In multi-objective tests (DTLZ, WFG, MaF), R2SAEA-MOP ranked first with a mean rank of 2.84, significantly outperforming classification-based (CPS-MOEA, CSEA) and regression-based (K-RVEA) surrogates.
Relation Prediction: Offline evaluations showed that the RL-fine-tuned ReLLM models significantly outperformed their pre-fine-tuning base models and frontier general-purpose LLMs (including GPT-4o, Gemini-2.5-Pro, and Qwen3-235B) in pairwise relation accuracy and ranking consistency (Spearman's $\rho$ ). Notably, general LLMs often yielded near-zero or negative correlations, failing to produce meaningful rankings without task-specific training.
Scalability and Robustness: The model demonstrated robustness to shifts in decision-space dimensionality ( $D \in \{5, 10, 30\}$ ) and context size. Local (prompt-level) normalization was found to be superior to global normalization for relational inference.
Deployment: Quantized variants (4-bit and 8-bit) of a 3B parameter model retained high accuracy while enabling efficient inference on edge devices (e.g., Jetson Orin NX), supporting a practical hardware-level surrogate paradigm.

Significance and Claims
The paper claims that R2SAEA bridges the gap between the high reasoning potential of LLMs and the strict efficiency requirements of expensive optimization. By shifting from a "train-predict" paradigm to an "inference-only" paradigm, the method eliminates the overhead of frequent surrogate retraining. The authors emphasize that their approach provides a zero-shot surrogate paradigm, where a single, specialized model can be embedded into evolutionary loops without further adaptation. The work represents the first explicit fine-tuning of LLMs specifically for surrogate-assisted evolutionary optimization, offering a feasible route toward hardware-friendly, real-time optimization in resource-constrained environments.