🤖 AI

TESTNAV: Pareto-Guided Search for Compositional Robustness Testing

TESTNAV is a Pareto-guided framework that efficiently identifies severe yet realistic model failures in compositional robustness testing by formulating the problem as a bi-objective optimization to maximize performance degradation while preserving input fidelity, thereby recovering Pareto fronts significantly faster than existing search-based baselines.

Original authors: Arooj Arif, Tobias Hartung, Elena Botoeva, Alexandros Koliousis

Published 2026-08-21

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Arooj Arif, Tobias Hartung, Elena Botoeva, Alexandros Koliousis

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

Modern artificial intelligence systems, particularly those that power image recognition, language translation, and code generation, have become remarkably skilled at their tasks. Yet, they remain fragile. A slight shift in lighting, a smudge of noise on a camera lens, or a single typo in a sentence can cause these systems to fail completely. For years, researchers have tested these models by introducing one type of error at a time, such as blurring an image or changing a word. However, the real world is rarely so simple. In autonomous driving or medical imaging, multiple problems often happen simultaneously: a car might be driving through rain while the camera lens is dirty and the sun is glaring. These combined errors create a complex web of interactions that single-error tests often miss, leaving hidden weaknesses in the software that could lead to dangerous failures in practice.

To understand how these systems break under realistic pressure, a team of researchers from Northeastern University London and the University of Kent developed a new method called TESTNAV. They recognized that testing every possible combination of errors is impossible; with just four types of errors and six levels of severity for each, there are over a thousand unique scenarios to check. Furthermore, simply piling on more errors does not always reveal the most useful information. If an image is corrupted so heavily that it looks nothing like the original, the model's failure is expected and tells us little about its true limits. The most valuable failures are those where the input still looks and sounds like the real thing, yet the model gets it wrong. These specific cases expose genuine vulnerabilities rather than just obvious sensitivity to garbage data.

The researchers framed this challenge as a balancing act between two competing goals: making the model fail as badly as possible while keeping the input looking as much like the original as possible. They treated this not as a single goal to maximize, but as a search for the best possible trade-offs. Imagine trying to find the highest points on a rugged mountain range where the terrain represents different combinations of errors. Some points offer a steep drop in performance but keep the image clear; others keep the image perfect but fail to break the model. The researchers wanted to map the entire ridge line where these two goals meet, a path known in mathematics as a Pareto front. To do this efficiently, they used an evolutionary algorithm, a computer program that mimics natural selection. Instead of testing every single path, the program generates a population of test cases, keeps the most promising ones, and mixes them together to create new, better candidates, gradually refining the search until it finds the most critical failure points.

When the team applied this method to four different benchmarks covering image recognition, sentence matching, and code generation, the results were striking. Across these diverse tasks, TESTNAV found the most critical failure combinations up to 2.15 times faster than other search methods that did not use this balancing approach. In some cases, the new method needed to evaluate only about 36 percent of the possible error combinations to find the same set of critical failures that other methods found after checking nearly 90 percent. The study also tested whether simpler metrics, such as measuring how much a model's internal neurons fired or how uncertain it felt, could predict these failures. They found that these single-number indicators were not enough; they could not reliably identify the specific combinations of errors that caused the model to fail while the input remained realistic.

The researchers also discovered that the shape of the most critical failures depends heavily on how one measures the quality of the input. When using certain metrics to judge image quality, the most dangerous failures were spread out across many different combinations of errors, making a broad search strategy essential. In other cases, the failures were clustered tightly in one area, where a simpler, more focused search worked just as well. This suggests that there is no single "best" way to test all AI systems; the strategy must adapt to the specific nature of the data and the errors being tested. By focusing on the balance between breaking the model and keeping the input realistic, TESTNAV provides a practical way to find the hidden cracks in artificial intelligence before they cause real-world harm, ensuring that these systems are robust not just in theory, but in the messy, complex reality where they are actually used.

Technical Summary: TESTNAV – Pareto-Guided Search for Compositional Robustness Testing

1. Problem Definition

Deep learning models, while achieving strong task performance, remain vulnerable to real-world input perturbations. Traditional robustness testing often evaluates perturbations in isolation (e.g., single corruption types like noise or blur). However, real-world degradations frequently arise from the interaction of multiple factors (e.g., simultaneous brightness shifts and motion blur).

Evaluating these compositional perturbations introduces two primary challenges:

Combinatorial Explosion: The perturbation space grows exponentially. With $n$ perturbation types and $\ell$ discrete severity levels, the configuration space scales as $\ell^n$ . For example, four perturbation types with six levels each yield 1,296 configurations, making exhaustive evaluation computationally expensive.
Uneven Diagnostic Value: Not all perturbation combinations are equally informative. Some combinations produce inputs so degraded that they lose semantic fidelity (no longer resembling the original), rendering model failures trivial and expected. Conversely, some combinations preserve high input fidelity yet induce model failures, revealing genuine robustness weaknesses.

The core problem is how to efficiently explore this discrete, high-dimensional space under a limited evaluation budget to identify configurations that maximize performance degradation while preserving input fidelity.

2. Methodology: TESTNAV Framework

The authors propose TESTNAV, a framework that formalizes compositional robustness testing as a bi-objective optimization problem.

2.1 Objectives

TESTNAV seeks to approximate the Pareto front of perturbation configurations based on two competing objectives:

Performance Degradation ( $\delta$ ): Measures the drop in task performance (e.g., accuracy, Robust Pass) when the test set is perturbed. The goal is to maximize this value.
Input Fidelity ( $\rho$ ): Measures how closely the perturbed inputs resemble the original inputs using modality-specific metrics. The goal is to maximize this value.
- Vision: SSIM (Structural Similarity Index) and KID (Kernel Inception Distance, inverted).
- Language/Code: chrF and BERT-F1.

2.2 Search Algorithm

TESTNAV employs NSGA-II (Non-dominated Sorting Genetic Algorithm II), a multi-objective evolutionary algorithm, to navigate the configuration space.

Initialization: A population of configurations is sampled uniformly from the discrete lattice of all possible perturbation levels.
Variation: New candidates are generated via simulated binary crossover (SBX) and polynomial mutation. Since severity levels are integers, fractional values are rounded to the nearest valid level.
Selection: The algorithm ranks configurations using Pareto dominance (a configuration dominates another if it is better in at least one objective and not worse in the other). To maintain diversity across the trade-off surface, it uses crowding-distance selection, ensuring the population covers the entire degradation–fidelity spectrum rather than collapsing into a single region.
Termination: The search continues until a predefined evaluation budget ( $B$ ) is exhausted, returning a prioritized list of non-dominated configurations.

3. Key Contributions

Formalization: The paper formalizes compositional robustness testing as a budget-constrained bi-objective search problem, balancing failure severity against input fidelity.
Framework Implementation: It introduces TESTNAV, an NSGA-II-based framework that maintains a diverse set of non-dominated solutions along the degradation–fidelity trade-off.
Empirical Validation: The authors conduct a comprehensive study across four benchmarks spanning vision (Tiny-ImageNet), natural language (QQP), and code generation (HumanEval, MBPP).
- They construct ground-truth Pareto fronts by exhaustively evaluating all 1,296 configurations per dataset.
- They demonstrate that TESTNAV recovers these fronts up to 2.15× faster than search-based baselines (Random Search, Greedy Search, and standard Genetic Algorithms) while evaluating only 35.8%–89.3% of the total discrete space.
Metric Analysis: The study reveals that neural-coverage metrics (e.g., NAC, SNAC) and input-level prioritization signals (e.g., DeepGini, Surprise Adequacy) do not reliably identify the Pareto-optimal failure region, as they fail to capture the specific trade-off between degradation and fidelity at the configuration level.

4. Experimental Results

Efficiency: Under identical budgets, TESTNAV consistently achieves higher Area Under the Curve (AUC) for Recall@P* compared to non-Pareto baselines, particularly when the Pareto front is broad (e.g., using SSIM for vision or chrF for language).
Comparison with Scalar Search: When the Pareto front is small and concentrated (e.g., using KID for vision), scalar search (optimizing a single weighted score) can be competitive. However, TESTNAV's diversity-preserving mechanism proves superior when the front is spread out, preventing the search from collapsing into a single region of the trade-off surface.
Necessity of Bi-Objective: Ablation studies show that single-objective searches (optimizing only for degradation or only for fidelity) fail to recover the full Pareto front. Optimizing only for degradation sacrifices fidelity, while optimizing only for fidelity fails to induce significant model failures.
Input-Level Metrics: Input-level metrics (activation coverage, uncertainty) were found insufficient as proxies for the degradation–fidelity trade-off, often prioritizing novel inputs that do not correspond to severe, high-fidelity failures.

5. Significance and Claims

The paper claims that TESTNAV provides a systematic and efficient approach to identifying "informative failures"—cases where a model fails on inputs that remain semantically faithful to the original. By framing robustness testing as a multi-objective optimization problem, the framework avoids the pitfalls of exhaustive search and the biases of scalarized objectives.

The authors emphasize that the geometry of the Pareto front depends on the choice of performance and fidelity metrics. TESTNAV's significance lies in its ability to adapt to these geometries, recovering meaningful robustness weaknesses across vision, language, and code domains without requiring exhaustive evaluation. The work suggests that for compositional testing, balancing severity and fidelity is critical, and Pareto-guided search is a robust mechanism for achieving this balance under resource constraints.

Limitations: The current framework operates over discrete, predefined perturbation families and severity levels. The authors note that extending this to continuous perturbation spaces is a direction for future work.