TESTNAV: Pareto-Guided Search for Compositional Robustness Testing

arXiv:2608.198822026-08-21

A smarter way to test AI models against combined real-world glitches, without checking every possible combination

When multiple corruptions like brightness shifts and motion blur hit an image or text at the same time, the number of possible combinations explodes and most of them are unrealistically broken and not useful for testing. TESTNAV treats robustness testing as a balancing act between two goals -- how much a corruption combination breaks model performance and how much it still looks like the original input -- and uses the evolutionary algorithm NSGA-II to find the best trade-offs efficiently. Across four benchmarks covering images, text, and code, it matched the results of exhaustive baseline search while checking only 35.8%-89.3% of all possible combinations, and did so up to 2.15x faster.

What they did

Real-world inputs often suffer from several corruptions at once (brightness change, blur, noise), but testing all combinations explodes combinatorially -- four corruption types at six severity levels already yields 1,296 combinations, and many are so degraded they're not practically useful
TESTNAV reframes robustness testing as a bi-objective optimisation problem: maximise how much a corruption combination hurts model performance, while keeping the corrupted input faithful to the original, measured with modality-specific metrics like SSIM and KID for images, and chrF and BERT-F1 for language and code
It uses NSGA-II, a multi-objective evolutionary search algorithm, to approximate the set of best trade-off combinations (the Pareto front) without evaluating every single configuration
Tested against ground truth built by exhaustively evaluating all 1,296 configurations on four benchmarks (Tiny-ImageNet, QQP, HumanEval, MBPP), TESTNAV recovered the full set of optimal combinations up to 2.15x faster than other search methods, needing only 35.8%-89.3% of the full configuration space
Simpler baselines -- optimising for degradation or fidelity alone, or using existing neural-network coverage metrics -- performed worse, confirming that both goals need to be balanced together

TESTNAV: Pareto-Guided Search for Compositional Robustness Testing figure 0

Table 1: Benchmarks, datasets and models, perturbations, fidelity metrics ϕ, task-performance metrics ψ, and clean-set performance ψ⁡(𝒟).
Dataset 𝒟	Size	Model	Perturbations	Fidelity ϕ	Task ψ	Clean ψ⁡(𝒟)
Tiny-ImageNet	10,000	CaiT-S36	speckle noise, glass blur, brightness, pixelate	KID, SSIM	Accuracy	86.7%
QQP	1,000	RoBERTa-base	synonym, typo, contraction, punctuation	BERT-F1, chrF	Accuracy	91.2%
HumanEval	164	CodeGen-2B-mono	butterfingers, char case, whitespace, newline	BERT-F1, chrF	RP5@1	23.2%
MBPP	974	CodeGen-2B-mono	butterfingers, char case, whitespace, newline	BERT-F1, chrF	RP5@1	31.9%

TESTNAV: Pareto-Guided Search for Compositional Robustness Testing figure 2

TESTNAV: Pareto-Guided Search for Compositional Robustness Testing figure 3

Table 2: AUC-Recall@𝒫∗ for TestNav and search baselines across all benchmarks and fidelity metrics. Bold indicates the best score and underline indicates the second-best score per column.
Method	SSIM	KID	chrF	BERT-F1	chrF	BERT-F1	chrF	BERT-F1
TestNav	0.704	0.686	0.646	0.651	0.729	0.730	0.697	0.690
Greedy Search	0.557	0.464	0.638	0.782	0.742	0.783	0.681	0.751
Genetic Algorithm	0.540	0.552	0.693	0.707	0.753	0.767	0.640	0.631
Random Search	0.510	0.503	0.526	0.514	0.502	0.522	0.514	0.490

Figure 4: Input-level metrics versus TestNav on . Curves show Recall@𝒫∗ over unique configurations (top) and evaluation budget (bottom), using SSIM (left) and KID-derived fidelity (right).

Figure 7: 4D voxel visualisations of 𝒫∗ for non-vision benchmarks using chrF as the fidelity metric.

Table 3: Pareto-front composition per metric pair for .
Metric pair	𝒫∗	Θ1	Θ2	Θ3	Θ4
(δ,ρSSIM)	27	9	12	4	2
(δ,ρKID)	27	4	7	14	2

Why it matters

Testing every possible combination of real-world corruptions is computationally infeasible for large models, yet safety-critical systems like autonomous driving or medical imaging need to know how they fail under such combined conditions. TESTNAV offers a practical way to find the most meaningful, realistic failure cases within a limited testing budget, giving practitioners concrete guidance for building more reliable robustness tests.

Figure 8: 4D voxel visualisations of 𝒫∗ for non-vision benchmarks using BERT-F1 as the fidelity metric.

Terms in this paper

Pareto front · the set of best possible trade-off points where improving one goal necessarily makes another goal worse
NSGA-II · an evolutionary search algorithm designed to optimise multiple competing goals at once
SSIM/KID · metrics that measure how visually similar a corrupted image is to its original
chrF/BERT-F1 · metrics that measure how similar corrupted text or code is to its original
Recall@P* · a measure of how much of the true best-combination set a search method has found so far

Original abstract (English)

Deep learning models remain vulnerable to real-world input perturbations, especially when multiple corruptions co-occur in the same input (e.g., brightness shifts and motion blur). Compositional testing reveals these interaction effects but introduces two challenges: combinatorial growth of the perturbation space as dimensions and severity levels increase, and uneven diagnostic value-many combinations yield unrealistically degraded inputs with limited practical relevance. We present TESTNAV, 1 a Pareto-guided robustness testing framework for efficiently exploring discrete, compositional perturbation spaces when only a limited number of perturbation configurations can be evaluated. TESTNAV prioritises severe yet realistic failures by formulating robustness testing as bi-objective optimisation: maximise performance degradation while preserving input fidelity measured by modality-specific metrics (e.g., SSIM and KID for vision; chrF and BERT-F1 for language and code). It uses NSGA-II to approximate the bi-objective Pareto front. Across four benchmarks spanning vision, natural language, and code generation, TESTNAV recovers Pareto fronts up to 2.15x faster than search-based baselines, using 35.8%-89.3% of the discrete perturbation space defined by four perturbation dimensions with six levels each.

Authors · Arooj Arif, Tobias Hartung, Elena Botoeva, Alexandros Koliousis

Read on arXiv

Latest papers

All papers →

Latest from METAL LAB

Figures: Arooj Arif et al., arXiv:2608.19882, CC BY 4.0