# SCOPE: Synthetic Conditional Objectives for Policy Evolution in Black-Box Combinatorial Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 63 references that are in the map.
- First posted on arXiv 30 Jul 2026.

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

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [CodeBERT: A Pre-Trained Model for Programming and Natural Languages](https://mlsanity.com/paper/2002.08155/) (2020)
- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Scaling Laws for Reward Model Overoptimization](https://mlsanity.com/paper/2210.10760/) (2022)
- [Teaching Large Language Models to Self-Debug](https://mlsanity.com/paper/2304.05128/) (2023)
- [Measuring Coding Challenge Competence With APPS](https://mlsanity.com/paper/2105.09938/) (2021)
- [GraphCodeBERT: Pre-training Code Representations with Data Flow](https://mlsanity.com/paper/2009.08366/) (2020)
- [InCoder: A Generative Model for Code Infilling and Synthesis](https://mlsanity.com/paper/2204.05999/) (2022)
- [Reinforcement Learning with Unsupervised Auxiliary Tasks](https://mlsanity.com/paper/1611.05397/) (2016)
- [CodeT: Code Generation with Generated Tests](https://mlsanity.com/paper/2207.10397/) (2022)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Text2Reward: Reward Shaping with Language Models for Reinforcement Learning](https://mlsanity.com/paper/2309.11489/) (2023)
- [Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2501.08603/) (2025)
- [Motif: Intrinsic Motivation from Artificial Intelligence Feedback](https://mlsanity.com/paper/2310.00166/) (2023)
- [ParamILS: An Automatic Algorithm Configuration Framework](https://mlsanity.com/paper/1401.3492/) (2014)
- [DrEureka: Language Model Guided Sim-To-Real Transfer](https://mlsanity.com/paper/2406.01967/) (2024)
- [Combinatorial Bayesian Optimization using the Graph Cartesian Product](https://mlsanity.com/paper/1902.00448/) (2019)
- [Safe Imitation Learning via Fast Bayesian Reward Inference from Preferences](https://mlsanity.com/paper/2002.09089/) (2020)
- [HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs](https://mlsanity.com/paper/2412.14995/) (2024)
- [Bayesian Optimization of Combinatorial Structures](https://mlsanity.com/paper/1806.08838/) (2018)
- [Bayesian Optimisation over Multiple Continuous and Categorical Inputs](https://mlsanity.com/paper/1906.08878/) (2019)
- [Improving Reinforcement Learning from Human Feedback with Efficient Reward Model Ensemble](https://mlsanity.com/paper/2401.16635/) (2024)
- [MaestroMotif: Skill Design from Artificial Intelligence Feedback](https://mlsanity.com/paper/2412.08542/) (2024)
- [HiFo-Prompt: Prompting with Hindsight and Foresight for LLM-based Automatic Heuristic Design](https://mlsanity.com/paper/2508.13333/) (2025)
- [Automated Design of Metaheuristic Algorithms: A Survey](https://mlsanity.com/paper/2303.06532/) (2023)
- [Stochastic Load Balancing on Unrelated Machines](https://mlsanity.com/paper/1904.07271/) (2019)
- [Back to the Beginning of Heuristic Design: Bridging Code and Knowledge with LLMs](https://mlsanity.com/paper/2605.06123/) (2026)

## Abstract (arXiv)

Black-box combinatorial optimization requires systematically identifying high-quality solutions under a limited evaluation budget, yet the unknown objective function provides little guidance for deciding where the search should explore next. We introduce SCOPE, a general framework for Synthetic Conditional Objectives for Policy Evolution in Black-Box Combinatorial Optimization. Rather than directly optimizing the inaccessible objective, SCOPE learns a set of synthetic objectives conditioned on the accumulated search history, where each objective is designed to expose a distinct and potentially useful preference over candidate solutions. These objectives are then used to evolve search policies that generate diverse candidates, whose true quality is subsequently assessed through black-box evaluations. The outer loop adaptively updates and selects synthetic objectives according to how effectively their induced policies discover promising regions. In contrast, the inner loop returns a portfolio of top-performing policies to reduce the risk of relying on a single surrogate preference. This formulation reframes objective design as a mechanism for guiding policy exploration, enabling the search process to exploit observed evidence while maintaining structured diversity across discrete solution spaces. Extensive experiments across multiple benchmark problems demonstrate that SCOPE consistently improves black-box search performance under limited evaluation budgets and generalizes well across diverse combinatorial structures.