# Relation Reasoning with LLMs in Expensive Optimization

arXiv: https://arxiv.org/abs/2605.02933 · HTML: https://mlsanity.com/paper/2605.02933/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 17 of its 68 references that are in the map.
- First posted on arXiv 30 Apr 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 17 of 17)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilities](https://mlsanity.com/paper/2507.06261/) (2025)
- [Large Language Models to Enhance Bayesian Optimization](https://mlsanity.com/paper/2402.03921/) (2024)
- [Language Model Crossover: Variation through Few-Shot Prompting](https://mlsanity.com/paper/2302.12170/) (2023)
- [Fin-R1: A Large Language Model for Financial Reasoning through Reinforcement Learning](https://mlsanity.com/paper/2503.16252/) (2025)
- [LLM Agents for Education: Advances and Applications](https://mlsanity.com/paper/2503.11733/) (2025)
- [OptiMUS: Optimization Modeling Using MIP Solvers and large language models](https://mlsanity.com/paper/2310.06116/) (2023)
- [Large Language Model-Enhanced Algorithm Selection: Towards Comprehensive Algorithm Representation](https://mlsanity.com/paper/2311.13184/) (2023)
- [Large Language Models as Surrogate Models in Evolutionary Algorithms: A Preliminary Study](https://mlsanity.com/paper/2406.10675/) (2024)
- [LegalDelta: Enhancing Legal Reasoning in LLMs via Reinforcement Learning with Chain-of-Thought Guided Information Gain](https://mlsanity.com/paper/2508.12281/) (2025)
- [L-AutoDA: Leveraging Large Language Models for Automated Decision-based Adversarial Attacks](https://mlsanity.com/paper/2401.15335/) (2024)
- [Legal Mathematical Reasoning with LLMs: Procedural Alignment through Two-Stage Reinforcement Learning](https://mlsanity.com/paper/2504.02590/) (2025)
- [Cultivating Helpful, Personalized, and Creative AI Tutors: A Framework for Pedagogical Alignment using Reinforcement Learning](https://mlsanity.com/paper/2507.20335/) (2025)

## Abstract (arXiv)

Expensive optimization problems (EOPs) are black-box tasks with costly objective evaluations and no gradient access, making the evaluation budget the key bottleneck. Surrogate-assisted evolutionary algorithms (SAEAs) reduce evaluations via surrogate predictions, but conventional surrogates often require frequent retraining as populations evolve, incurring overhead. This paper proposes R2SAEA, a reinforcement-trained relation-based large language model (LLM) surrogate assisted evolutionary algorithm. We cast relation-based surrogate modeling as an in-context pairwise reasoning task. To enable efficient inference in evolutionary loops, we develop an anchor-based iterative context construction strategy that reduces prompt complexity from quadratic to linear in population size, and a voting-based aggregation scheme that converts predicted relations into scores for offspring selection. We further build an RL pipeline from evolutionary trajectories and fine-tune Qwen2.5 with GRPO. Experiments on single- and multi-objective benchmarks show improved relation prediction and state-of-the-art optimization performance over strong SAEA baselines and general LLMs. Quantization also enables efficient edge deployment, supporting a zero-shot surrogate paradigm without per-generation retraining. Code and models are available at https://github.com/Septend9/R2SAEA.