CS Paper Radar

A Flexible and Generic Approach for Explainable Landscape Analysis and the pyXla Toolbox

Tony Ombaso, Anna S. Bosman, Arnaud Liefooghe, Katherine M. Malan, Sébastien Verel

cs.NE cs.MS ·submitted 2026-10-05 13:56 UTC · v1

Abstract

Landscape analysis has been successfully applied to understand complex optimisation problems, gain insights into algorithm behaviour, and automate algorithm selection and configuration. Although many landscape analysis techniques have been developed over the last decades, it remains difficult for researchers and practitioners to decide which approaches are appropriate and to implement them in practice. Some tools are available, but these are either restricted to particular problem domains (e.g., unconstrained black-box continuous optimisation), or are limited in what they model and measure. In addition, output from landscape analysis is often not easily interpretable, especially when computed landscape features do not correspond with aspects of problems that practitioners are familiar with. In this paper, we introduce a principled approach for explainable landscape analysis (XLA) with an associated Python package called pyXla. The approach is generic in that it applies to problems with different representations (continuous or combinatorial), with single or multiple objectives, with or without constraints. The extent of analysis provided by the XLA framework depends on the data available, with richer analysis offered as additional information is provided by the user. We demonstrate the explainable output produced by pyXla on a selection of hand-crafted problems with diverse landscape characteristics.

Comment
40 pages, 32 figures, submitted to Evolutionary Computation Journal

Closest papers

Nearest neighbours by meaning across the whole index.

ExaTune: Exhaustive Hyperparameter Landscape Exploration at Scale

cs.LG ·2026-11-02 ·Kevin Dick, Katie Lonsway
benchmarkcode/data similarity 0.59
Abstract · 11 pages, 3 figures, includes supplementary materials

Hyperparameter optimization (HPO) returns a single optimal configuration, systematically discarding the explored performance landscape that encodes how results depend on configuration choices. Fitness landscape analysis comprises a robust collection of methods from evolutionary computation offering ruggedness indices, autocorrelation functions, and fitness-distance correlation that have never been applied to machine learning hyperparameter spaces at scale, given that fine-grained ground-truth enumeration data has not existed. We present ExaTune, an open-source HPC system to produce a new artifact class: the hyperparameter landscape map. ExaTune exhaustively evaluates every point on a discretized hyperparameter grid via $K$-fold cross-validation, aggregates results into reproducible parquet benchmarks, and applies a suite of five formalized landscape metrics: spatial autocorrelation (Moran's $I$), ruggedness, local optima density, fitness-distance correlation (FDC), and variance-based parameter importance. We release a benchmark collection of 8 complete landscape maps (totalling 285,080 exhaustively evaluated configurations) spanning five model families (SVMs, random forests, XGBoost, ridge regression, and $k$-nearest neighbors) across six classification and two regression benchmarks, hosted on HuggingFace. Empirical analysis demonstrates that Bayesian optimization, Optuna, Hyperband, and Random Search at standard trial budgets systematically miss instability regions, secondary optima, and parameter interaction effects that are visible in complete landscapes; information that is structurally unavailable to any optimizer by design.

0.38

Reachable Global Optimization in AI Systems: How Global Is Global?

cs.AI ·2026-08-20 ·Wesley Shu
benchmarktheory similarity 0.58
Abstract

AI systems increasingly claim to optimize prompts, policies, architectures, plans, tool-use trajectories, reasoning traces, and test-time computation. This paper argues that such claims are underspecified unless they state the region actually reachable by the system that performed the optimization. We introduce Reachability-Induced Optimization (RIO), a model in which a generator, verifier, controller, memory, tools, and budget induce a reachable candidate region. The returned solution is therefore a best visited point, an approximate reachable optimum, or an exact global optimum only when additional certificates relate the reachable region to the full formal space. We prove reachable-optimality, false-globality, gap- decomposition, certificate, escape, pruning, and control-value results. The full benchmark record contains 66,150 executed trials over six known-optimum landscape families, seven control policies, 270 landscapes, and 35 runs per landscape-method. The online appendix includes raw trial records, aggregate tables, figures, benchmark code, validation scripts, and checksums. The results show that control can restrict, expand, or misdirect reachability, and that optimization quality, reachability quality, and control reliability must be reported separately.

0.24

Learning to Optimize UAV Path Planning for Data Sensing in Wireless Sensor Networks

cs.RO cs.NE ·2026-09-15 ·Sijie Ma, Zeyuan Ma, Weijia Cao, Yue-Jiao Gong, Lingling Ma +2 more
similarity 0.52
Abstract

UAVs have emerged as highly flexible platforms for data sensing in Wireless Sensor Networks (WSNs). Path planning for UAVs in such tasks plays a key role to assure remote sensing effectiveness and friendly energy consumption. However, existing approaches show two key limitations: i) they are primarily hand-crafted with certain design biases that harm adaptation on unseen tasks. ii) they predominantly assume idealized spatial complexities of actual environments through simplified simulation, causing them to underperform during real-world deployment. In this paper, we propose a novel learning-assisted planning framework, termed Landscape-Aware Meta Differential Evolution (LAMDE), to tackle the mentioned limitations. The major contributions come from the following aspects. We first re-formulate such UAV path planning problem to embrace challenging constraints. To efficiently navigate this highly constrained space, we propose a bi-level learning to optimize approach, where the meta-level is a trainable algorithm configuration policy that meta-learns an adaptable planning strategy for low-level planning algorithm. To address the potential training data scarcity and distribution shift in real-world environments, we introduce a landscape-aware automatic augmentation scheme that enriches training data. At the low-level, a Differential Evolution algorithm is deployed for solving the path planning tasks. To enhance the solving flexibility, we further design a variable-length encoding strategy that dynamically prunes redundant hover points and optimizes continuous flight parameters concurrently within a unified search space. Based on all proposed designs, we meta-train LAMDE and compare it with representative baselines. Comprehensive experiments demonstrate that LAMDE achieves state-of-the-art performance on the tested complex UAV path planning tasks in WSN data collection scenarios.

0.42

LandscapeSHAP: Which Persistent Homology Class Gets the Credit?

cs.LG math.AT ·2026-09-25 ·Nikola Milićević
similarity 0.51
Abstract · 42 pages, 11 figures, 1 table, fixed typos, fixed errors in Example 3.6, improved stability results, expanded bibliography

Shapley values, a solution concept from cooperative game theory, have recently become a standard tool for feature credit allocation in machine learning. They provide an axiomatically justified method to fairly distribute a model's prediction among the data features. Shapley values have not yet been applied to explain machine learning models trained on features from topological data analysis. We develop what we believe is the first such approach, focusing on the persistence landscape featurization of persistence diagrams. Because each landscape coordinate is a rank statistic, crediting a model's prediction back to individual persistent homology classes (persistence diagram points) is nontrivial. We introduce LandscapeSHAP, a method for fair credit allocation to persistence diagram points based on a model's prediction. For linear models on persistence landscapes, LandscapeSHAP has a closed form expression that gives the exact Shapley value of every persistence diagram point. In particular, there is no coalition sampling required. We further prove that the four Shapley "fairness" axioms uniquely characterize this credit allocation for any model, not only linear ones. For a general nonlinear model, this unique value can only be calculated exactly from its defining coalition averaging formula, which requires considering all $2^N$ many coalitions, where $N$ is the number of points in the persistence diagram. This is computationally intractable for persistence diagrams of realistic size. We complement the exact linear model result with an efficient Monte Carlo sampling of persistence diagram coalitions. We give convergence rates in terms of number of samples needed to approximate to a desired degree of accuracy. We also prove stability results for the LandscapeSHAP credit allocation, for any model.

0.28

Provably Complete Generalized Planning with LLMs

cs.AI ·2026-09-22 ·Katharina Stein, Chaahat Jain, Jörg Hoffmann, Alexander Koller
benchmark similarity 0.49
Abstract

Generalized planning aims to compute a plan that solves all instances of a planning domain. Recent work has used LLMs to automatically generate and debug such generalized plans in the form of Python programs and achieved perfect test data coverage for several domains. However, whether these generalized plans are actually complete, i.e. solve all instances of the domain, could only be determined by manual evaluation. Here, we present an approach for automatically generating generalized plans in Lean together with proofs of their completeness relative to a specification of the domain constraints provided as input. We introduce a semantic-preserving PDDL-to-Lean conversion, and use an LLM to generate both the generalized plan and the formal proof that it solves every instance satisfying the domain constraints. The correctness of the completeness proof is determined by Lean's kernel. We evaluate our approach on 13 commonly used benchmark domains, using GPT-5.6-Sol as the LLM. For 12 of the domains we obtain generalized plans together with valid completeness proofs. This is a major advancement of the state of the art in automatic generalized-plan completeness proofs.

0.40

Synthesizing Feature Extractors: An Agentic Approach for Algorithm Selection

cs.AI ·2026-08-17 ·Hai Xia, Carlos Ansótegui, Stefan Szeider
similarity 0.49
Abstract

Algorithm selection for constraint satisfaction problems requires extracting features that capture problem structure. Manually designing feature extractors demands deep domain expertise and quickly becomes a bottleneck when new problem classes appear. We present an automated approach that uses Large Language Models (LLMs) in an agentic check--fix--verify loop to synthesize executable Python scripts that act as interpretable, problem-specific feature extractors. Given a high-level MiniZinc model and an instance, the LLM agent generates code that constructs a typed graph representation and computes structural properties such as graph density, variable clustering, and constraint tightness. We evaluate our approach on three combinatorial problems (vehicle routing, car sequencing, fixed-length error-correcting codes) with a portfolio of five state-of-the-art solvers. The synthesized extractors yield algorithm selectors that consistently outperform both expert-curated mzn2feat features (up to $8.3$ percentage points (pp) test-set accuracy on FLECC) and the best transformer-based trans2feat variants. In the meanwhile, the synthesized feature extractors remain inspectable.

0.35

Abstraction Agent

cs.MA cs.AIcs.CLcs.GT ·2026-09-03 ·Boning Li, Longbo Huang
top venuecode/data similarity 0.49
Abstract

Information abstraction, which groups strategically similar private states into a tractable number of buckets, is essential for scaling game-solving algorithms to large imperfect-information games. Constructing effective abstractions, however, has traditionally required domain-specific evaluators such as hand-strength calculators or equity estimators, which demand expert knowledge and engineering effort and are unavailable for most less-studied games. We propose the Abstraction Agent, a zero-shot pipeline that uses a large language model (LLM) to discover continuous strategic features from a natural-language game description, score private states on these features, and cluster them into abstraction buckets, without any game-specific evaluator, training data, or game-tree traversal during abstraction construction. The pipeline runs in four phases: feature discovery with calibration anchors, batched private-state scoring, correlation-based feature selection, and $k$-means clustering. The resulting abstractions reduce lifted-strategy exploitability by up to 62% relative to an expected-hand-strength baseline on heads-up no-limit Texas hold'em (HUNL) turn endgames, and beat a scalar rank baseline at every granularity on ROVER Trials, an original game absent from any pretraining corpus. Beyond these quantitative benchmarks, the pipeline transfers with unchanged prompts to four-card Pot-Limit Omaha, HUNL preflop and flop, and Riichi Mahjong, where the discovered features track each game's recognized strategic concepts. This is structured knowledge elicitation: converting implicit strategic knowledge in LLM parameters into explicit numerical features for downstream algorithmic computation. The code is available at https://github.com/lbn187/AbstractionAgent.

0.66

AlgoWorlds: Benchmarking Tool Use for Global Optimization in Algorithmic Worlds

cs.CL ·2026-08-29 ·Zixiang Xu, Jiaan Wang, Fandong Meng
benchmarkcode/data similarity 0.49
Abstract · Homepage: https://xzx34.github.io/AlgoWorlds/ Code: https://github.com/xzx34/AlgoWorlds

Tool-use benchmarks generally evaluate whether an agent completes a workflow using appropriate tools and valid arguments. However, feasibility alone is insufficient in real-world decision settings such as route planning and fleet dispatch. Individual choices interact through shared constraints and costs, so a feasible solution may still be substantially suboptimal. This raises a harder question: can an agent turn information gathered through tools into a globally optimal decision? We introduce AlgoWorlds, a benchmark that transforms formally specified combinatorial optimization problems into partially observed decision environments with verifiable global optima. Each environment contains a hidden instance observed only through task-specific information tools, after which the agent commits to one structured decision evaluated for feasibility and optimality. AlgoWorlds contains 240 environments covering ten combinatorial optimization families and four workload levels. Family-specific deterministic programs generate the instances, exact algorithms certify their optima and determine workload levels, and two structurally different tool interfaces present each underlying instance. We evaluate seven leading LLMs, including Claude Opus 4.8 and GPT-5.6 Sol. Achieving global optimality remains highly challenging: although leading models produce feasible decisions in most cases, the best-performing model reaches exact optimality in only 38.61% of cases. Even when agents collect sufficient information to reconstruct the hidden instance, most failures end in feasible but suboptimal decisions. The challenge therefore extends beyond information acquisition to information integration, global constraint reasoning, and decision verification. The project homepage is available at https://xzx34.github.io/AlgoWorlds/, and the code is available at https://github.com/xzx34/AlgoWorlds.

0.52