TESTNAV: Pareto-Guided Search for Compositional Robustness Testing

# TestNav: Pareto-Guided Search for Compositional Robustness Testing
Source: [https://arxiv.org/html/2608.19882](https://arxiv.org/html/2608.19882)
###### Abstract

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 presentTestNav,111Code and data are available in an anonymised[OSF repository](https://osf.io/kyb7g/overview?view_only=9a41411b99124f3d947712500e329da5)\.a Pareto\-guided robustness testing framework for efficiently exploring discrete, compositional perturbation spaces when only a limited number of perturbation configurations can be evaluated\.TestNavprioritises 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,TestNavrecovers Pareto fronts up to2\.15×2\.15\\timesfaster than search\-based baselines, using 35\.8%–89\.3% of the discrete perturbation space defined by four perturbation dimensions with six levels each\.

## 1Introduction

Modern deep learning models achieve strong task performance yet remain vulnerable to semantics\-preserving input perturbations that induce model failures[32](https://arxiv.org/html/2608.19882#bib.bib28);[14](https://arxiv.org/html/2608.19882#bib.bib27)\. Robustness testing typically evaluates perturbations in isolation[17](https://arxiv.org/html/2608.19882#bib.bib12);[24](https://arxiv.org/html/2608.19882#bib.bib16)\. In practice, however, real\-world degradations often arise from interacting factors \(e\.g\., brightness shifts, motion blur, and noise\), which rarely occur alone in deployment settings such as autonomous driving[25](https://arxiv.org/html/2608.19882#bib.bib30);[16](https://arxiv.org/html/2608.19882#bib.bib35)and medical imaging[6](https://arxiv.org/html/2608.19882#bib.bib34)\.

Compositional robustness testing—that is, evaluating inputs under combinations of multiple perturbations—reveals interaction effects that remain undetected under single\-perturbation evaluation[22](https://arxiv.org/html/2608.19882#bib.bib15);[18](https://arxiv.org/html/2608.19882#bib.bib14);[1](https://arxiv.org/html/2608.19882#bib.bib1)\. However, systematically exploring multi\-perturbation configuration spaces poses two key challenges:

\(i\)The perturbation space grows combinatorially: withnnperturbation types andℓ\\elldiscrete levels per type, the number of configurations scales asℓn\\ell^\{n\}\. For example, four perturbation types with six levels each yield64=1,2966^\{4\}=1\{,\}296perturbation configurations\. Exhaustive testing is computationally expensive and scales poorly as the number of perturbation types or test inputs grows\.\(ii\)Configurations are not equally informative: some produce heavily degraded inputs with low input fidelity—meaning the perturbed input no longer resembles the original—whereas others preserve input fidelity yet induce model failures\. Input fidelity does not degrade monotonically with the number of perturbations, rendering fixed\-order heuristics ineffective\.

What makes a failure informative?The most informative failures are those where a perturbed input remains semantically faithful to the original yet still causes the model to fail, exposing genuine robustness weaknesses rather than expected sensitivity to obvious input corruption\. Finding such failures requires balancing*two complementary objectives*: model performance degradation, which measures how much model performance drops under a given perturbation configuration, and input fidelity, which measures how closely perturbed inputs resemble the originals under appropriate similarity metrics\.

For robustness testing, we are interested in the*Pareto front*of perturbation configurations with respect to these two objectives\. The Pareto front𝒫∗\\mathcal\{P\}^\{\*\}consists of all*Pareto\-optimal*configurations—those where improving one objective necessarily worsens the other[21](https://arxiv.org/html/2608.19882#bib.bib8)\. Pareto\-optimal configurations are the natural candidates for robustness testing: they maximise model performance degradation while preserving input fidelity, and are therefore most likely to reveal meaningful robustness failures\.

We introduceTestNav, a framework for compositional robustness testing that formalises this idea as a bi\-objective optimization problem–balancing failure severity against input fidelity–and uses NSGA\-II[7](https://arxiv.org/html/2608.19882#bib.bib6), a multi\-objective evolutionary algorithm, to efficiently approximate the Pareto front\. Our contributions are:

1. \(1\)We formalise compositional robustness testing as a budget\-constrained bi\-objective search problem over perturbation configurations, with model\-performance degradation and input fidelity as competing objectives\. We instantiate this formulation inTestNav, an NSGA\-II\-based framework, which maintains a diverse set of non\-dominated solutions along the degradation–fidelity trade\-off\.
2. \(2\)We conduct an empirical study across four benchmarks—Tiny\-ImageNet, QQP, HumanEval, and MBPP—spanning vision, language, and code\. We exhaustively evaluate all646^\{4\}configurations per dataset to construct ground\-truth Pareto fronts, measuring fidelity via SSIM and KID \(images\) and chrF and BERTScore \(language/code\)\. Under identical budgets,TestNavrecovers these fronts up to2\.15×2\.15\\timesfaster than search\-based baselines\. Tiny\-ImageNet experiments further show that neural\-coverage metrics do not reliably identify the Pareto\-optimal failure region\.

## 2Related Work

Deep learning robustness testing evaluates model behaviour under controlled input perturbations intended to preserve task semantics while shifting the input distribution\. Testing methods differ in what they choose to vary:

\(i\)input\-level methods generate, rank, or assess individual test inputs using activation coverage, uncertainty, or distributional novelty; they provide baseline search signals in our study \(§[2\.1](https://arxiv.org/html/2608.19882#S2.SS1)\);\(ii\)perturbation\-level benchmarks evaluate predefined corruption or transformation families, typically one family at a time; they provide the perturbations used in our evaluation \(§[2\.2](https://arxiv.org/html/2608.19882#S2.SS2)\);\(iii\)configuration\-level methods evaluate combinations of perturbations, inducing a discrete space of perturbation configurations; they motivate the multi\-perturbation space searched byTestNav\(§[2\.3](https://arxiv.org/html/2608.19882#S2.SS3)\)\.

TestNavbuilds on the configuration\-level view and uses multi\-objective optimisation as the algorithmic basis for Pareto\-guided search \(§[2\.4](https://arxiv.org/html/2608.19882#S2.SS4)\)\.

### 2\.1Input\-level testing

Coverage\-guided methods use activation behaviour as a proxy for test adequacy\. DeepXplore[28](https://arxiv.org/html/2608.19882#bib.bib20)formulates DNN testing as an optimisation problem, generating inputs that maximise neuron activation coverage \(NAC\) across multiple models\. It was among the first to formulate test generation as guided search, but its coverage criterion is structural and does not measure whether generated inputs remain close to the originals\. DeepGauge[20](https://arxiv.org/html/2608.19882#bib.bib22)extends this idea to multi\-granularity activation criteria, including strong neuron activation coverage \(SNAC\),kk\-multisection neuron coverage \(KMNC\), and top\-kkneuron coverage \(TKNC\)\. This family of methods guides testing in input space rather than perturbation\-configuration space\.

Input\-prioritisation methods instead rank candidate inputs by fault\-revealing signals\. DeepGini[11](https://arxiv.org/html/2608.19882#bib.bib23)prioritises inputs on which the model has low confidence, using prediction uncertainty as a proxy for fault\-revealing potential\. Surprise Adequacy[19](https://arxiv.org/html/2608.19882#bib.bib21)ranks inputs by how distributionally unusual they are relative to training data, using likelihood\-based surprise adequacy \(LSA\) or distance\-based surprise adequacy \(DSA\)\. These methods help select individual test inputs, but do not explicitly balance performance degradation against input fidelity at the perturbation\- configuration level\.

### 2\.2Perturbation\-level robustness benchmarks

For vision, ImageNet\-C[17](https://arxiv.org/html/2608.19882#bib.bib12)benchmarks robustness under 19 fixed corruption types applied independently at five severity levels\. It provides a rigorous single\-perturbation baseline but cannot capture interactions between co\-occurring corruptions\. For natural language, TextAttack[23](https://arxiv.org/html/2608.19882#bib.bib17)provides a unified framework for word\-level adversarial transformations on NLP models, covering substitution, insertion, and deletion\. CheckList[30](https://arxiv.org/html/2608.19882#bib.bib18)defines capability tests across linguistic categories such as negation, vocabulary, and robustness to typos, with each capability tested largely in isolation\. For code, ReCode[35](https://arxiv.org/html/2608.19882#bib.bib19)evaluates code generation models under individual perturbation families such as butterfingers, character case, whitespace, and newline perturbations, measuring pass@kkper family independently\. These benchmarks provide the perturbation families used in our evaluation, but they evaluate families independently rather than searching over compositional perturbation configurations under a budget\.

### 2\.3Configuration\-level compositional testing

Chandrasekaran et al\.[4](https://arxiv.org/html/2608.19882#bib.bib29)showed that combinations of perturbations can expose failures that are not observable under isolated testing\. CIT4DNN[10](https://arxiv.org/html/2608.19882#bib.bib25)addresses the resulting combinatorial space through combinatorial interaction testing in a compressed latent space\. TestifAI[1](https://arxiv.org/html/2608.19882#bib.bib1)constructs multi\-perturbation spaces and estimates higher\-order robustness behaviour from lower\-order perturbation evaluations, motivating the configuration space we study\. Withnnperturbation types andℓ\\elldiscrete levels, however, the space containsℓn\\ell^\{n\}configurations\. For large models, evaluating each configuration requires inference over the full evaluation set, making exhaustive evaluation costly\. What remains open is how to explore this space under a limited evaluation budget while prioritising failures that are both severe and high\-fidelity\.

### 2\.4Multi\-objective optimisation

Multi\-objective optimisation is common in search\-based software engineering, where testing is formulated as a trade\-off between objectives such as coverage, diversity, and fault detection[21](https://arxiv.org/html/2608.19882#bib.bib8);[13](https://arxiv.org/html/2608.19882#bib.bib33);[27](https://arxiv.org/html/2608.19882#bib.bib26)\. In AI testing, DeepXplore[28](https://arxiv.org/html/2608.19882#bib.bib20)and DLFuzz[15](https://arxiv.org/html/2608.19882#bib.bib24)combine multiple objectives, including neuron coverage and behavioural divergence, to generate failure\-inducing inputs\. Most existing AI testing methods apply multi\-objective optimisation to individual test inputs, rather than perturbation configurations\.

A common alternative is to scalarise multiple objectives into a single fitness score and apply single\-objective search\. However, scalarisation fixes the degradation–fidelity trade\-off, biasing search toward one region of the surface\. NSGA\-II[7](https://arxiv.org/html/2608.19882#bib.bib6)avoids this by ranking configurations through non\-dominated sorting and preserving diversity with crowding\-distance selection\.TestNavuses NSGA\-II to search the multi\-perturbation configuration space, optimising performance degradation and input fidelity\.

E←∅E\\leftarrow\\emptyset

⊳\\trianglerightunique evaluated configurations

b←0b\\leftarrow 01

P←μP\\leftarrow\\muuniform samples from

Θ\\Theta2

foreach*𝛉∈P\\bm\{\\theta\}\\in P*do3

δ⁡\(𝜽\),ρ⁡\(𝜽\)←Evaluate​\(𝜽\)\\updelta\(\\bm\{\\theta\}\),\\uprho\(\\bm\{\\theta\}\)\\leftarrow\\textsc\{Evaluate\}\(\\bm\{\\theta\}\)4

E←E∪\{𝜽\}E\\leftarrow E\\cup\\\{\\bm\{\\theta\}\\\}5

b←b\+1b\\leftarrow b\+1
⊳\\trianglerightbudget counter

6

while*b<Bb<B*do7

m←min⁡\(μ,B−b\)m\\leftarrow\\min\(\\mu,\\,B\-b\)
⊳\\trianglerightremaining budget

Q←Variation​\(P,Θ,m\)Q\\leftarrow\\textsc\{Variation\}\(P,\\Theta,m\)8

9

foreach*𝛉∈Q\\bm\{\\theta\}\\in Q*do10

if*b=Bb=B*then11

break12

if*𝛉∉E\\bm\{\\theta\}\\notin E*then13

δ⁡\(𝜽\),ρ⁡\(𝜽\)←Evaluate​\(𝜽\)\\updelta\(\\bm\{\\theta\}\),\\uprho\(\\bm\{\\theta\}\)\\leftarrow\\textsc\{Evaluate\}\(\\bm\{\\theta\}\)14

E←E∪\{𝜽\}E\\leftarrow E\\cup\\\{\\bm\{\\theta\}\\\}15

b←b\+1b\\leftarrow b\+116

17

ℱ←\\mathcal\{F\}\\leftarrowrank

P∪QP\\cup Qby Pareto dominance18

P←P\\leftarrowselect

μ\\muconfigs from

ℱ\\mathcal\{F\}by rank and distance19

20

R←R\\leftarrowsort

EEby rank, then distance21

return*RR*22

Algorithm 1TestNav: NSGA\-II search over
compositional perturbation configurations

## 3TestNavFramework

TestNavidentifies perturbation configurations that expose severe model failures while preserving input fidelity\. Given a model, a clean test set, discrete perturbation space, task\-performance metric, fidelity metric, and evaluation budget,TestNavsearches for high\-quality degradation–fidelity trade\-offs using NSGA\-II, a multi\-objective evolutionary algorithm\. The result is a prioritised set of configurations for practitioner inspection\. We define the perturbation configuration space \(§[3\.1](https://arxiv.org/html/2608.19882#S3.SS1)\), the degradation and fidelity objectives \(§[3\.2](https://arxiv.org/html/2608.19882#S3.SS2)\), and the NSGA\-II search procedure \(§[3\.3](https://arxiv.org/html/2608.19882#S3.SS3)\)\.

### 3\.1Perturbation Configuration Space

We view perturbations as controlled transformations intended to preserve task semantics while shifting the input distribution\. Let𝒟\\mathcal\{D\}be the clean test set and let\{T1,…,Tn\}\\\{T\_\{1\},\\ldots,T\_\{n\}\\\}bennperturbation types, such as blur, noise, or whitespace corruption\. Each perturbation typeTiT\_\{i\}is applied at a discrete levelθi∈\{0,…,ℓ−1\}\\theta\_\{i\}\\in\\\{0,\\ldots,\\ell\{\-\}1\\\}, whereθi=0\\theta\_\{i\}\{=\}0denotes no perturbation\. A perturbation configuration𝜽=\(θ1,…,θn\)\\bm\{\\theta\}=\(\\theta\_\{1\},\\ldots,\\theta\_\{n\}\)specifies one level per perturbation type\. The resulting configuration space is the discrete lattice

Θ=\{0,…,ℓ−1\}n\.\\Theta=\\\{0,\\ldots,\\ell\{\-\}1\\\}^\{n\}\.Applying configuration𝜽\\bm\{\\theta\}to an inputxxcomposes the selected perturbations:

π𝜽\(x\)=Tnθn∘⋯∘T1θ1\(x\),\\pi\_\{\\bm\{\\theta\}\}\(x\)=T\_\{n\}^\{\\theta\_\{n\}\}\\circ\\cdots\\circ T\_\{1\}^\{\\theta\_\{1\}\}\(x\),whereTiθiT\_\{i\}^\{\\theta\_\{i\}\}denotes perturbation typeTiT\_\{i\}applied at levelθi\\theta\_\{i\}\. The*perturbed test set𝒯𝛉\\mathcal\{T\}\_\{\\bm\{\\theta\}\}*for a configuration𝜽\\bm\{\\theta\}is

𝒯𝜽=\{π𝜽​\(x\):x∈𝒟\}\.\\mathcal\{T\}\_\{\\bm\{\\theta\}\}=\\\{\\pi\_\{\\bm\{\\theta\}\}\(x\):x\\in\\mathcal\{D\}\\\}\.In our experiments,n=4n\{=\}4andℓ=6\\ell\{=\}6, yielding\|Θ\|=1,296\|\\Theta\|=1\{,\}296perturbation configurations\.

### 3\.2Objectives

Each configuration𝜽\\bm\{\\theta\}is evaluated using two objectives\. The first is performance degradation: how much task performance drops when the test set is perturbed\. Letψ\\psibe a task\-performance metric, such as accuracy or Robust Pass, e\.g\., RP5@1[35](https://arxiv.org/html/2608.19882#bib.bib19)\. We define the*performance degradation objective*δ\\updeltaon𝜽\\bm\{\\theta\}as

δ⁡\(𝜽\)=max⁡\(ψ⁡\(𝒟\)−ψ⁡\(𝒯𝜽\),0\)\.\\updelta\(\\bm\{\\theta\}\)=\\max\\bigl\(\\psi\(\\mathcal\{D\}\)\{\-\}\\psi\(\\mathcal\{T\}\_\{\\bm\{\\theta\}\}\),\\,0\\bigr\)\.\(1\)A higherδ\\updeltameans greater performance degradation\.

The second objective is input fidelity: how closely the perturbed inputs resemble the originals\. Letϕ\\phibe a modality\-specific fidelity score derived from a similarity or distance metric\. We define*input fidelity objectiveρ\\uprho*on𝜽\\bm\{\\theta\}as

ρ⁡\(𝜽\)=ϕ⁡\(𝒯𝜽,𝒟\)\.\\uprho\(\\bm\{\\theta\}\)=\\phi\(\\mathcal\{T\}\_\{\\bm\{\\theta\}\},\\mathcal\{D\}\)\.\(2\)A higherρ\\uprhomeans higher input fidelity\.

In our experiments, we instantiateϕ\\phiusing SSIM and KID for images, and chrF and BERT\-F1 for text and code\. Because KID is a distance metric, we invert it before normalisation so that higherρ\\uprhoconsistently indicates higher fidelity\. Bothδ\\updeltaandρ\\uprhoare normalised to\[0,1\]\[0,1\]in the experiments\.

### 3\.3NSGA\-II Search

Algorithm[1](https://arxiv.org/html/2608.19882#alg1)summarises the procedure\.TestNavbegins by sampling an initial populationPPofμ\\muconfigurations uniformly without replacement fromΘ\\Thetaand evaluating each onδ\\updeltaandρ\\uprho\(lines[1](https://arxiv.org/html/2608.19882#alg1)–[1](https://arxiv.org/html/2608.19882#alg1)\)\.Evaluate\(𝜽\)\(\\bm\{\\theta\}\)\(line[1](https://arxiv.org/html/2608.19882#alg1)\) constructs the perturbed test set𝒯𝜽\\mathcal\{T\}\_\{\\bm\{\\theta\}\}, computes the performance dropδ⁡\(𝜽\)\\updelta\(\\bm\{\\theta\}\)using Eq\.[1](https://arxiv.org/html/2608.19882#S3.E1), and computes the fidelity scoreρ⁡\(𝜽\)\\uprho\(\\bm\{\\theta\}\)using Eq\.[2](https://arxiv.org/html/2608.19882#S3.E2)\.

TestNavthen repeats four steps until the proposal budgetBBis exhausted\. It generates new candidatesQQ\(line[1](https://arxiv.org/html/2608.19882#alg1)\), evaluates any previously unseen candidates inQQ\(lines[1](https://arxiv.org/html/2608.19882#alg1)–[1](https://arxiv.org/html/2608.19882#alg1)\), ranks configurationsP∪QP\\cup Qby Pareto dominance \(line[1](https://arxiv.org/html/2608.19882#alg1)\), and selects the next populationPPby Pareto rank and crowding distance \(line[1](https://arxiv.org/html/2608.19882#alg1)\)\.

Variation\(P,Θ,m\)\(P,\\Theta,m\)takes the current populationPP, usesΘ\\Thetato enforce valid severity levels, and produces up tommnew candidatesQQ\(line[1](https://arxiv.org/html/2608.19882#alg1)\)\. It applies simulated binary crossover \(SBX\) and polynomial mutation to parents sampled fromPP\. Because severity levels are integers, fractional values produced by these operators are rounded to the nearest valid level inΘ\\Thetausing a rounding repair step[3](https://arxiv.org/html/2608.19882#bib.bib7)\.

TestNavranksP∪QP\\cup Qusing Pareto dominance \(line[1](https://arxiv.org/html/2608.19882#alg1)\)\. A configuration𝜽\\bm\{\\theta\}dominates𝜽′\\bm\{\\theta\}^\{\\prime\}if it is at least as good on bothδ\\updeltaandρ\\uprho, and strictly better on at least one\. Over the full configuration space, the ground\-truth Pareto front𝒫∗\\mathcal\{P\}^\{\*\}contains all configurations inΘ\\Thetathat are dominated by no other configuration inΘ\\Theta\.TestNavdoes not observe𝒫∗\\mathcal\{P\}^\{\*\}during search; it approximates it by applying non\-dominated sorting to the current candidate setP∪QP\\cup Q, partitioning candidates into successive fronts\. Crowding distance estimates how isolated a configuration is in the\(δ,ρ\)\(\\updelta,\\uprho\)objective space; larger values indicate less crowded regions of the trade\-off surface\. The next population is filled from the best\-ranked fronts first\. When a front does not fit, crowding\-distance selection retains candidates with larger crowding distance, preserving diversity across the degradation–fidelity trade\-off \(line[1](https://arxiv.org/html/2608.19882#alg1)\)\.

The loop continues until the proposal budgetBBis exhausted\. At the end,TestNavreturnsRR, the evaluated perturbation configurations ranked by Pareto rank and crowding distance\. This gives practitioners a prioritised list of severe, high\-fidelity configurations for robustness inspection\.

#### Hyperparameter selection\.

NSGA\-II requires three search parameters, which we tune by grid search:

\(i\)the crossover indexηc\\eta\_\{c\}controls how far offspring spread from their parents under SBX crossover: lower values promote broader exploration, while higher values favour local refinement\. We search overηc∈\{1,5,10,15\}\\eta\_\{c\}\\,\{\\in\}\\,\\\{1,5,10,15\\\};\(ii\)the mutation indexηm\\eta\_\{m\}controls the step size of polynomial mutation, with lower values producing larger steps\. We search overηm∈\{1,5,10,15\}\\eta\_\{m\}\\,\{\\in\}\\,\\\{1,5,10,15\\\};\(iii\)the population sizeμ\\mudetermines how many configurations are maintained per generation; larger populations preserve more Pareto\-front diversity but consume more budget per generation\. We search overμ∈\{20,50,80,110\}\\mu\\,\{\\in\}\\,\\\{20,50,80,110\\\}\.

This grid contains 64 settings, each evaluated on all four benchmarks under two fidelity metrics per benchmark: SSIM and KID for images, and chrF and BERT\-F1 for text and code\. With 10 random seeds, this yields5,1205\{,\}120runs\. We select the setting that maximises the number of benchmark–metric settings reaching Recall@𝒫∗≥0\.999\\mathcal\{P\}^\{\*\}\{\\geq\}0\.999, breaking ties by worst\-case recall\. This selectsηc=1\\eta\_\{c\}\{=\}1,ηm=5\\eta\_\{m\}\{=\}5, andμ=110\\mu\{=\}110\.

Dataset𝒟\\mathcal\{D\}SizeModelPerturbationsFidelityϕ\\phiTaskψ\\psiCleanψ⁡\(𝒟\)\\psi\(\\mathcal\{D\}\)Tiny\-ImageNet10,000CaiT\-S36speckle noise, glass blur, brightness, pixelateKID, SSIMAccuracy86\.7%QQP1,000RoBERTa\-basesynonym, typo, contraction, punctuationBERT\-F1, chrFAccuracy91\.2%HumanEval164CodeGen\-2B\-monobutterfingers, char case, whitespace, newlineBERT\-F1, chrFRP5@123\.2%MBPP974CodeGen\-2B\-monobutterfingers, char case, whitespace, newlineBERT\-F1, chrFRP5@131\.9%

Table 1:Benchmarks, datasets and models, perturbations, fidelity metricsϕ\\phi, task\-performance metricsψ\\psi, and clean\-set performanceψ⁡\(𝒟\)\\psi\(\\mathcal\{D\}\)\.![Refer to caption](https://arxiv.org/html/2608.19882v1/fig_pareto_imagenet_combined.png)
![Refer to caption](https://arxiv.org/html/2608.19882v1/fig_pareto_recode_combined.png)
![Refer to caption](https://arxiv.org/html/2608.19882v1/fig_pareto_mbpp_combined.png)

Figure 1:𝒫∗\\mathcal\{P\}^\{\*\}across benchmarks and fidelity metrics\. Each panel shows the full configuration space \(grey\) and Pareto front \(teal\);\|𝒫∗\|\|\\mathcal\{P\}^\{\*\}\|gives the front size per benchmark–metric pair\. Pareto fronts contain configurations with one to four active perturbation dimensions\. Counts by order 1–4 are: SSIM2727\(9,12,4,2\); KID2727\(4,7,14,2\); chrF1313\(2,7,2,2\); BERT\-F11212\(2,7,1,2\); chrF2020\(2,3,12,3\); BERT\-F11717\(3,9,5,0\); chrF2424\(1,5,13,5\); BERT\-F13030\(7,12,5,6\)\. See Appendix for details\.![Refer to caption](https://arxiv.org/html/2608.19882v1/recall_bw_imagenet.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/recall_bw_qqp.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/recall_bw_recode.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/recall_bw_mbpp.png)

Figure 2:Recall@𝒫∗\\mathcal\{P\}^\{\*\}across benchmarks and fidelity metrics\. For each benchmark, the top row uses unique configurations as thexx\-axis, and the bottom row uses evaluation budget\. Shaded bands show±1\\pm 1standard deviation over 10 seeds\. The vertical line indicates the number of unique perturbation combinations \(top\) and total budget \(bottom\) required byTestNavto discover all Pareto\-optimal configurations𝒫∗\\mathcal\{P\}^\{\*\}; endpoint markers \(■\\blacksquare\) show the highest Recall@𝒫∗\\mathcal\{P\}^\{\*\}achieved by each method\.\.MethodSSIMKIDchrFBERT\-F1chrFBERT\-F1chrFBERT\-F1TestNav0\.7040\.6860\.6460\.6510\.7290\.7300\.6970\.690Greedy Search0\.5570\.4640\.6380\.7820\.7420\.7830\.6810\.751Genetic Algorithm0\.5400\.5520\.6930\.7070\.7530\.7670\.6400\.631Random Search0\.5100\.5030\.5260\.5140\.5020\.5220\.5140\.490

Table 2:AUC\-Recall@𝒫∗\\mathcal\{P\}^\{\*\}forTestNavand search baselines across all benchmarks and fidelity metrics\.Boldindicates the best score andunderlineindicates the second\-best score per column\.![Refer to caption](https://arxiv.org/html/2608.19882v1/ablation2_bw_imagenet.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/ablation2_bw_qqp.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/ablation2_bw_recode.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/ablation2_bw_mbpp.png)

Figure 3:Multi\-objective versus single\-objective search across benchmarks and fidelity metrics\. Curves show Recall@𝒫∗\\mathcal\{P\}^\{\*\}over unique configurations in the top row and evaluation budget in the bottom row; bands show±1\\pm 1standard deviation over 10 seeds\.![Refer to caption](https://arxiv.org/html/2608.19882v1/coverage_bw_imagenet.png)

Figure 4:Input\-level metrics versusTestNavon \. Curves show Recall@𝒫∗\\mathcal\{P\}^\{\*\}over unique configurations \(top\) and evaluation budget \(bottom\), using SSIM \(left\) and KID\-derived fidelity \(right\)\.

## 4Evaluation

We address three research questions:

\(i\)whetherTestNavrecovers𝒫∗\\mathcal\{P\}^\{\*\}more efficiently than non\-Pareto baselines \(§[4\.2](https://arxiv.org/html/2608.19882#S4.SS2)\);\(ii\)whether single\-objective search can recover𝒫∗\\mathcal\{P\}^\{\*\}\(§[4\.3](https://arxiv.org/html/2608.19882#S4.SS3)\); and\(iii\)whether input\-level test metrics can proxy the degradation–fidelity trade\-off \(§[4\.4](https://arxiv.org/html/2608.19882#S4.SS4)\)\.

### 4\.1Experimental Setup

#### Benchmarks\.

Table[1](https://arxiv.org/html/2608.19882#S3.T1)summarises the four benchmarks, each defining four perturbation dimensions with six severity levels \(00–55\), where level 0 denotes no perturbation:

\(i\)*Image classification*\( \)\. We evaluate CaiT\-S36[33](https://arxiv.org/html/2608.19882#bib.bib5)on 10,000 Tiny\-ImageNet validation images[8](https://arxiv.org/html/2608.19882#bib.bib32)using four ImageNet\-C corruptions: speckle noise, glass blur, brightness, and pixelate[17](https://arxiv.org/html/2608.19882#bib.bib12);[31](https://arxiv.org/html/2608.19882#bib.bib13)\. Levels 1–5 follow the standard ImageNet\-C severity scale\.\(ii\)*Paraphrase detection*\( \)\. We evaluateRoBERTabase\\textsf\{RoBERTa\}\_\{\\textsf\{base\}\}on 1,000 Quora Question Pairs \(QQP\), where each pair is labelled for semantic equivalence[34](https://arxiv.org/html/2608.19882#bib.bib31)\. We use TextAttack[23](https://arxiv.org/html/2608.19882#bib.bib17)to apply synonym replacement, typos, contractions, and punctuation perturbations\. Levels 1–5 correspond to applying one to five edits\.\(iii\)*Code generation*\. We evaluateCodeGen\-2B\-monoon HumanEval \( \) and MBPP \( \)[5](https://arxiv.org/html/2608.19882#bib.bib2);[2](https://arxiv.org/html/2608.19882#bib.bib4);[26](https://arxiv.org/html/2608.19882#bib.bib3)\. Following ReCode[35](https://arxiv.org/html/2608.19882#bib.bib19), we use butterfingers, character\-case, whitespace, and newline perturbations, but apply them compositionally\. The same six severity levels are used for both datasets\.222For levels 1–5, butterfingers is applied with probabilityp∈\{0\.05,0\.1,0\.15,0\.2,0\.25\}p\\in\\\{0\.05,\\allowbreak 0\.1,\\allowbreak 0\.15,\\allowbreak 0\.2,\\allowbreak 0\.25\\\}, and character\-case withp∈\{0\.1,0\.2,0\.35,0\.5,0\.7\}p\\in\\\{0\.1,\\allowbreak 0\.2,\\allowbreak 0\.35,\\allowbreak 0\.5,\\allowbreak 0\.7\\\}; whitespace characters are added and deleted with\(padd,pdel\)∈\{\(0\.1,0\.05\),\(0\.15,0\.07\),\(0\.2,0\.1\),\(0\.25,0\.12\),\(0\.3,0\.15\)\}\(p\_\{\\mathrm\{add\}\},p\_\{\\mathrm\{del\}\}\)\\allowbreak\\in\\allowbreak\\\{\(0\.1,0\.05\),\\allowbreak\(0\.15,0\.07\),\\allowbreak\(0\.2,0\.1\),\\allowbreak\(0\.25,0\.12\),\\allowbreak\(0\.3,0\.15\)\\\}; and newline insertion addsn∈\{1,2,3,4,5\}n\\in\\\{1,2,3,4,5\\\}lines\.

#### Task performance and fidelity metrics\.

For each configuration𝜽\\bm\{\\theta\}, we compute task performanceψ⁡\(𝒯𝜽\)\\psi\(\\mathcal\{T\}\_\{\\bm\{\\theta\}\}\)and input fidelityϕ⁡\(𝒯𝜽,𝒟\)\\phi\(\\mathcal\{T\}\_\{\\bm\{\\theta\}\},\\mathcal\{D\}\)at the configuration level\. Task performance is accuracy for and , and Robust Pass RP5@1 for and[35](https://arxiv.org/html/2608.19882#bib.bib19)\.

For input fidelity, we use SSIM and KID for , and chrF and BERT\-F1 for , , and \. SSIM is computed per perturbed image against its clean original, then averaged over the test set\. KID is computed once per configuration between the clean and perturbed image distributions with subset size 1,000; we negate it before normalisation so that higher values indicate greater fidelity\. chrF is computed over the full set of perturbed and clean inputs\. BERT\-F1 is computed usingRoBERTabase\\textsf\{RoBERTa\}\_\{\\textsf\{base\}\}for andCodeBERTbase\\textsf\{CodeBERT\}\_\{\\textsf\{base\}\}[12](https://arxiv.org/html/2608.19882#bib.bib9)for and \. All fidelity scores are normalised to\[0,1\]\[0,1\], with higher values indicating greater input fidelity\.333We use the TorchMetrics library for SSIM, KID, and BERT\-F1[9](https://arxiv.org/html/2608.19882#bib.bib11), andSacreBLEUfor chrF[29](https://arxiv.org/html/2608.19882#bib.bib10)\.

#### Ground\-truth Pareto front\.

𝒫∗\\mathcal\{P\}^\{\*\}was computed exhaustively by evaluating all\|Θ\|=1,296\|\\Theta\|\{=\}1\{,\}296configurations and retaining those not dominated under\(δ,ρ\)\(\\updelta,\\uprho\)[7](https://arxiv.org/html/2608.19882#bib.bib6)\. It serves as the fixed ground truth against which all methods are evaluated\. Figure[1](https://arxiv.org/html/2608.19882#S3.F1)shows the resulting fronts for each benchmark and fidelity metric\. The fronts contain configurations with one to four active perturbations, showing that Pareto\-optimal failures are not limited to single perturbations\.

#### Search metrics\.

We set the evaluation budget toB=5×\|Θ\|=6,480B\\,\{=\}\\,5\{\\times\}\|\\Theta\|\{=\}6\{,\}480configuration proposals\. A proposal evaluates a configuration on the full perturbed test set unless the configuration has already been seen, in which case cachedδ\\updeltaandρ\\uprhovalues are reused\. We setBBlarger than\|Θ\|\|\\Theta\|only to observe full search traces, including convergence behaviour and repeated proposals; efficiency is measured by the number of unique configurations required to recover𝒫∗\\mathcal\{P\}^\{\*\}and by the recall trajectory defined below\. We also trackuu, the number of unique configurations evaluated so far;u⩽Bu\\leqslant Bbecause search may revisit configurations\.

We measure recovery of the ground\-truth Pareto front using Recall@𝒫∗\\mathcal\{P\}^\{\*\}\. LetEu⊆ΘE\_\{u\}\\subseteq\\Thetabe the set of the firstuuunique configurations evaluated by a method\. Then

Recall​@​𝒫∗​\(u\)=\|Eu∩𝒫∗\|\|𝒫∗\|\.\\mathrm\{Recall@\}\\mathcal\{P\}^\{\*\}\(u\)=\\frac\{\|E\_\{u\}\\cap\\mathcal\{P\}^\{\*\}\|\}\{\|\\mathcal\{P\}^\{\*\}\|\}\.A value of 1 means that all Pareto\-optimal configurations have been found\. Steeper recall curves indicate earlier discovery of𝒫∗\\mathcal\{P\}^\{\*\}\.

AUC\-Recall summarises the full recall trajectory overu=1,…,\|Θ\|u=1,\\ldots,\|\\Theta\|unique configurations\. Letri=Recall​@​𝒫∗​\(i\)r\_\{i\}=\\mathrm\{Recall@\}\\mathcal\{P\}^\{\*\}\(i\)\. Then

AUC​\-​Recall​@​𝒫∗=1\|Θ\|​∑i=1\|Θ\|−1ri\+ri\+12\.\\mathrm\{AUC\\mbox\{\-\}Recall@\}\\mathcal\{P\}^\{\*\}=\\frac\{1\}\{\|\\Theta\|\}\\sum\_\{i=1\}^\{\|\\Theta\|\-1\}\\frac\{r\_\{i\}\+r\_\{i\+1\}\}\{2\}\.Higher AUC\-Recall indicates earlier discovery of𝒫∗\\mathcal\{P\}^\{\*\}under the same evaluation budget\.

#### Execution protocol\.

All methods are evaluated under the same proposal budgetBBand run with 10 independent seeds on a GPU cluster at the Massachusetts Green High Performance Computing Center \(MGHPCC\)\.

### 4\.2DoesTestNavrecover𝒫∗\\mathcal\{P\}^\{\*\}more efficiently than non\-Pareto baselines?

TestNavuses Pareto\-guided bi\-objective selection over performance degradation and input fidelity\. We compare it against three baselines: objective\-free random search, local scalar search, and scalar genetic search\. For the scalar baselines, we uses⁡\(𝜽\)=min⁡\(δ⁡\(𝜽\),ρ⁡\(𝜽\)\)s\(\\bm\{\\theta\}\)\{=\}\\min\(\\updelta\(\\bm\{\\theta\}\),\\uprho\(\\bm\{\\theta\}\)\), so a configuration receives a high score only when both degradation and fidelity are high\. The baselines are:

\(i\)*Random Search*evaluates configurations inΘ\\Thetain a uniformly random order, visiting each configuration exactly once;\(ii\)*Greedy Search*starts from a random configuration and repeatedly moves to the highest\-scoring neighbour underss, where neighbours differ by±1\\pm 1in one severity dimension, restarting when no neighbour improves;\(iii\)*Genetic Algorithm*uses the same population size, crossover, mutation, and duplicate\-elimination settings asTestNav, but optimises the scalar scoressrather than selecting by Pareto rank and crowding distance\.

Figure[2](https://arxiv.org/html/2608.19882#S3.F2)reports Recall@𝒫∗\\mathcal\{P\}^\{\*\}over 10 seeds\. The top\-rowxx\-axis shows unique configurations visited and the bottom\-rowxx\-axis shows the corresponding consumed evaluation budget; shaded regions show±1\\pm 1standard deviation\. Table[2](https://arxiv.org/html/2608.19882#S3.T2)summarises the corresponding AUC\-Recall values\.

#### Pareto search helps on broad fronts\.

Using SSIM for vision and chrF for language/code,TestNavachieves the highest AUC\-Recall on and , while Genetic Algorithm is highest on and \(Table[2](https://arxiv.org/html/2608.19882#S3.T2)\)\.TestNavfully recovers𝒫∗\\mathcal\{P\}^\{\*\}up to2\.15×2\.15\\timesearlier than baselines that also achieveRecall@​𝒫∗=1\\text\{Recall@\}\\mathcal\{P\}^\{\*\}\{=\}1, evaluating 35\.8%–89\.3% ofΘ\\Theta\.TestNavachieves AUC 0\.704 on , which is 38% above Random Search \(0\.510\) and 26% above Greedy Search \(0\.557\)\. These gains suggest that, when the Pareto front is broad, diversity\-preserving selection helps recover degradation–fidelity trade\-offs that scalar search misses\.

#### Greedy search is competitive on compact fronts\.

With KID\-derived fidelity for vision and BERT\-F1 for language/code, Greedy Search achieves higher AUC thanTestNavon , , and \(Table[2](https://arxiv.org/html/2608.19882#S3.T2)\)\. Figure[1](https://arxiv.org/html/2608.19882#S3.F1)suggests why: under these metrics,𝒫∗\\mathcal\{P\}^\{\*\}is small and concentrated in the\(δ,ρ\)\(\\updelta,\\uprho\)space, so the scalar scores⁡\(𝜽\)s\(\\bm\{\\theta\}\)can recover much of𝒫∗\\mathcal\{P\}^\{\*\}without exploring broadly\. When𝒫∗\\mathcal\{P\}^\{\*\}is larger or more spread out, as under SSIM and chrF, scalar search is less effective, as it tends to concentrate on one region of the trade\-off surface\.TestNavmitigates this collapse through crowding\-distance selection, which encourages the population to spread across the degradation–fidelity surface\.

### 4\.3Can single\-objective search recover𝒫∗\\mathcal\{P\}^\{\*\}?

Figure[3](https://arxiv.org/html/2608.19882#S3.F3)comparesTestNavagainst two single\-objective ablations using identical evolutionary operators:*δ\\updeltaonly*maximises degradation without an input fidelity objective;*ρ\\uprhoonly*maximises input fidelity without a degradation objective\.

#### Single\-objective search recovers less of the front\.

Both single\-objective ablations recover substantially less of𝒫∗\\mathcal\{P\}^\{\*\}\. Theδ\\updelta\-only condition favours high\-degradation configurations, often at the cost of input fidelity; its AUC ranges from 0\.185 to 0\.384, up to 0\.545 belowTestNav\. Theρ\\uprho\-only condition favours high\-fidelity configurations, but lacks a signal for model failure; its AUC ranges from 0\.612 to 0\.771, within 0\.085 ofTestNav\. Both show wider variance bands thanTestNav, suggesting lower stability across seeds\.TestNavmaintains spread across the degradation–fidelity surface through crowding\-distance selection\. Together, these results show that both objectives are necessary for Pareto\-front recovery and stability\.

### 4\.4Can input\-level metrics proxy the trade\-off?

Figure[4](https://arxiv.org/html/2608.19882#S3.F4)evaluates seven input\-level baselines introduced in §[2\.1](https://arxiv.org/html/2608.19882#S2.SS1)on : NAC, SNAC, KMNC, TKNC, DeepGini, LSA, and DSA\. Each metric is used as the sole search objective; the ground truth is the corresponding bi\-objective Pareto front\.

#### Input\-level signals are insufficient\.

No input\-level metric matchesTestNavin final Recall@𝒫∗\\mathcal\{P\}^\{\*\}\. Under SSIM,TestNavreaches 0\.993, with KMNC next best, at 0\.900 \(9% lower\); TKNC \(0\.496\) and LSA \(0\.581\) are weakest\. Under KID\-derived fidelity,TestNavagain reaches 0\.993, matched by KMNC \(0\.993\)\. Input\-level metrics measure activation coverage, prediction uncertainty, or distributional novelty on individual inputs, but not where a perturbation configuration lies on the\(δ,ρ\)\(\\updelta,\\uprho\)surface\. Thus, maximising them can prioritise novel or activation\-diverse configurations without identifying severe, high\-fidelity failures\.

## 5Conclusion

TestNavis a Pareto\-guided search framework for compositional robustness testing, formulated as a bi\-objective problem over performance degradationδ\\updeltaand input fidelityρ\\uprho\. Rather than maximising failures alone,TestNavtargets configurations where models fail on inputs that still resemble the originals, highlighting candidate robustness weaknesses\.

The benefit of Pareto\-guided search depends on the geometry of the Pareto front\. Across vision, natural language, and code\-generation benchmarks,TestNavrecovers𝒫∗\\mathcal\{P\}^\{\*\}more efficiently than non\-Pareto baselines when the front is broad\. Removing either objective reduces Pareto\-front recovery, and input\-level coverage and prioritisation signals cannot substitute for bi\-objective configuration search\.

The geometry of𝒫∗\\mathcal\{P\}^\{\*\}depends on the choice of performance and fidelity metrics, which are modality\- and task\-dependent\. BecauseTestNavtreats these metrics as interchangeable components, the framework generalises to any setting where performance degradation and input fidelity can be defined\.

#### Limitations and future work\.

TestNavoperates over discrete, predefined perturbation families and severity levels\. We plan to extendTestNavto continuous perturbation spaces\. Whether extreme Pareto points are useful depends on the testing goal; future work should help practitioners target regions of𝒫∗\\mathcal\{P\}^\{\*\}and choose suitable search algorithms\.

## References

- Arifet al\.\(2026\)A\. Arif, T\. Hartung, E\. Botoeva, and A\. KoliousisTestifAI: tomography\-based testing for deep learning systems\.InICSE,Cited by:[§1](https://arxiv.org/html/2608.19882#S1.p2.1),[§2\.3](https://arxiv.org/html/2608.19882#S2.SS3.p1.1)\.
- Austinet al\.\(2021\)J\. Austin, A\. Odena, M\. Nye,et al\.Program synthesis with large language models\.arXiv:2108\.07732\.Cited by:[item iii](https://arxiv.org/html/2608.19882#S4.I2.i3.4)\.
- Blank and Deb \(2020\)J\. Blank and K\. DebPymoo: multi\-objective optimization in Python\.IEEE Access8,pp\. 89497–89509\.Cited by:[§3\.3](https://arxiv.org/html/2608.19882#S3.SS3.p3.1)\.
- Chandrasekaranet al\.\(2021\)R\. Chandrasekaran, B\. Khatri, V\. Garg, R\. Sharma, H\. Ahmed, and K\. MuraliCombinatorial perturbation testing for assessing the robustness of autonomous driving systems\.InICST Workshops,Cited by:[§2\.3](https://arxiv.org/html/2608.19882#S2.SS3.p1.1)\.
- Chenet al\.\(2021\)M\. Chen, J\. Tworek, H\. Jun,et al\.Evaluating large language models trained on code\.arXiv:2107\.03374\.Cited by:[item iii](https://arxiv.org/html/2608.19882#S4.I2.i3.4)\.
- Chuahet al\.\(2024\)J\. Chuah, P\. Yan, G\. Wang, and J\. HahnTowards the generation of medical imaging classifiers robust to common perturbations\.BioMedInformatics4\(2\),pp\. 889–910\.Cited by:[§1](https://arxiv.org/html/2608.19882#S1.p1.1)\.
- Debet al\.\(2002\)K\. Deb, A\. Pratap, S\. Agarwal, and T\. MeyarivanA fast and elitist multiobjective genetic algorithm: NSGA\-II\.IEEE Transactions on Evolutionary Computation6\(2\),pp\. 182–197\.Cited by:[§1](https://arxiv.org/html/2608.19882#S1.p6.1),[§2\.4](https://arxiv.org/html/2608.19882#S2.SS4.p2.1),[§4\.1](https://arxiv.org/html/2608.19882#S4.SS1.SSS0.Px3.p1.1)\.
- Denget al\.\(2024\)J\. Deng, W\. Dong, R\. Socher,et al\.Tiny ImageNet \(Stanford CS231N\)\.Note:[https://cstr\.cn/32010\.11\.sjtu\.scidata\.00000019](https://cstr.cn/32010.11.sjtu.scidata.00000019)Cited by:[item i](https://arxiv.org/html/2608.19882#S4.I2.i1.4)\.
- Detlefsenet al\.\(2022\)N\. S\. Detlefsen, J\. Borovec, J\. Schock, A\. H\. Jha, T\. Koker, L\. Di Liello, D\. Stancl, C\. Quan, M\. Grechkin, and W\. FalconTorchMetrics: measuring reproducibility in PyTorch\.Journal of Open Source Software7\(70\),pp\. 4101\.Cited by:[footnote 3](https://arxiv.org/html/2608.19882#footnote3)\.
- Dolaet al\.\(2024\)S\. Dola, R\. McDaniel, M\. B\. Dwyer, and M\. L\. SoffaCIT4DNN: generating diverse and rare inputs for neural networks using latent space combinatorial testing\.InICSE,Cited by:[§2\.3](https://arxiv.org/html/2608.19882#S2.SS3.p1.1)\.
- Fenget al\.\(2020a\)Y\. Feng, Q\. Shi, X\. Gao, J\. Wan, C\. Fang, and Z\. ChenDeepGini: prioritizing massive tests to enhance the robustness of deep neural networks\.InISSTA,Cited by:[§2\.1](https://arxiv.org/html/2608.19882#S2.SS1.p2.1)\.
- Fenget al\.\(2020b\)Z\. Feng, D\. Guo, D\. Tang, N\. Duan, X\. Feng, M\. Gong, L\. Shen, B\. Qin, T\. Liu, D\. Jiang, and M\. ZhouCodeBERT: a pre\-trained model for programming and natural languages\.InEMNLP Findings,Cited by:[§4\.1](https://arxiv.org/html/2608.19882#S4.SS1.SSS0.Px2.p2.1)\.
- Fraser and Arcuri \(2013\)G\. Fraser and A\. ArcuriWhole test suite generation\.IEEE Transactions on Software Engineering39\(2\),pp\. 276–291\.Cited by:[§2\.4](https://arxiv.org/html/2608.19882#S2.SS4.p1.1)\.
- Goodfellowet al\.\(2015\)I\. J\. Goodfellow, J\. Shlens, and C\. SzegedyExplaining and harnessing adversarial examples\.InICLR,Cited by:[§1](https://arxiv.org/html/2608.19882#S1.p1.1)\.
- Guoet al\.\(2018\)J\. Guo, Y\. Jiang, Y\. Zhao, Q\. Chen, and J\. SunDLFuzz: differential fuzzing testing of deep learning systems\.InESEC/FSE,pp\. 739–743\.Cited by:[§2\.4](https://arxiv.org/html/2608.19882#S2.SS4.p1.1)\.
- Haoet al\.\(2024\)X\. Hao, M\. Wei, Y\. Yang,et al\.Is your HD map constructor reliable under sensor corruptions?\.Advances in Neural Information Processing Systems37,pp\. 22441–22482\.Cited by:[§1](https://arxiv.org/html/2608.19882#S1.p1.1)\.
- Hendrycks and Dietterich \(2019\)D\. Hendrycks and T\. DietterichBenchmarking neural network robustness to common corruptions and perturbations\.InICLR,Cited by:[§1](https://arxiv.org/html/2608.19882#S1.p1.1),[§2\.2](https://arxiv.org/html/2608.19882#S2.SS2.p1.1),[item i](https://arxiv.org/html/2608.19882#S4.I2.i1.4)\.
- Hendryckset al\.\(2020\)D\. Hendrycks, N\. Mu, E\. D\. Cubuk, B\. Zoph, J\. Gilmer, and B\. LakshminarayananAugMix: a simple data processing method to improve robustness and uncertainty\.InICLR,Cited by:[§1](https://arxiv.org/html/2608.19882#S1.p2.1)\.
- Kimet al\.\(2019\)J\. Kim, R\. Feldt, and S\. YooGuiding deep learning system testing using surprise adequacy\.InICSE,pp\. 1039–1049\.Cited by:[§2\.1](https://arxiv.org/html/2608.19882#S2.SS1.p2.1)\.
- Maet al\.\(2018\)L\. Ma, F\. Juefei\-Xu, F\. Zhang, J\. Sun, M\. Xue, B\. Li,et al\.DeepGauge: multi\-granularity testing criteria for deep learning systems\.InASE,pp\. 120–131\.Cited by:[§2\.1](https://arxiv.org/html/2608.19882#S2.SS1.p1.1)\.
- Miettinen \(1999\)K\. MiettinenNonlinear multiobjective optimization\.Kluwer Academic Publishers\.Cited by:[§1](https://arxiv.org/html/2608.19882#S1.p5.1),[§2\.4](https://arxiv.org/html/2608.19882#S2.SS4.p1.1)\.
- Mintunet al\.\(2021\)E\. Mintun, A\. Kirillov, and S\. XieOn interaction between augmentations and corruptions in natural corruption robustness\.InNeurIPS,Cited by:[§1](https://arxiv.org/html/2608.19882#S1.p2.1)\.
- Morriset al\.\(2020\)J\. Morris, E\. Lifland, J\. Y\. Yoo, J\. Grigsby, D\. Jin, and Y\. QiTextAttack: a framework for adversarial attacks, data augmentation, and adversarial training in NLP\.InEMNLP,Cited by:[§2\.2](https://arxiv.org/html/2608.19882#S2.SS2.p1.1),[item ii](https://arxiv.org/html/2608.19882#S4.I2.i2.4)\.
- Mu and Gilmer \(2019\)N\. Mu and J\. GilmerMNIST\-C: a robustness benchmark for computer vision\.InICML UDL Workshop,Cited by:[§1](https://arxiv.org/html/2608.19882#S1.p1.1)\.
- Muşatet al\.\(2021\)V\. Muşat, I\. Fursa, P\. Newman, F\. Cuzzolin, and A\. BradleyMulti\-weather city: adverse weather stacking for autonomous driving\.InICCV Workshops,pp\. 2906–2915\.Cited by:[§1](https://arxiv.org/html/2608.19882#S1.p1.1)\.
- Nijkampet al\.\(2022\)E\. Nijkamp, B\. Pang, H\. Hayashi, L\. Tu, H\. Wang, Y\. Zhou, S\. Savarese, and C\. XiongCodeGen: an open large language model for code with multi\-turn program synthesis\.arXiv:2203\.13474\.Cited by:[item iii](https://arxiv.org/html/2608.19882#S4.I2.i3.4)\.
- Panichellaet al\.\(2015\)A\. Panichella, F\. M\. Kifetew, and P\. TonellaReformulating branch coverage as a many\-objective optimization problem\.InICST,pp\. 1–10\.Cited by:[§2\.4](https://arxiv.org/html/2608.19882#S2.SS4.p1.1)\.
- Peiet al\.\(2017\)K\. Pei, Y\. Cao, J\. Yang, and S\. JanaDeepXplore: automated whitebox testing of deep learning systems\.InSOSP,Cited by:[§2\.1](https://arxiv.org/html/2608.19882#S2.SS1.p1.1),[§2\.4](https://arxiv.org/html/2608.19882#S2.SS4.p1.1)\.
- Post \(2018\)M\. PostA call for clarity in reporting BLEU scores\.InWMT,Cited by:[footnote 3](https://arxiv.org/html/2608.19882#footnote3)\.
- Ribeiroet al\.\(2020\)M\. T\. Ribeiro, T\. Wu, C\. Guestrin, and S\. SinghBeyond accuracy: behavioral testing of NLP models with CheckList\.InACL,pp\. 4902–4912\.Cited by:[§2\.2](https://arxiv.org/html/2608.19882#S2.SS2.p1.1)\.
- Rusak and Mitzkus \(2019\)E\. Rusak and B\. MitzkusImagecorruptions: Python package to corrupt images for robustness benchmarking\.Note:[https://github\.com/bethgelab/imagecorruptions](https://github.com/bethgelab/imagecorruptions)Cited by:[item i](https://arxiv.org/html/2608.19882#S4.I2.i1.4)\.
- Szegedyet al\.\(2014\)C\. Szegedy, W\. Zaremba, I\. Sutskever, J\. Bruna, D\. Erhan, I\. Goodfellow, and R\. FergusIntriguing properties of neural networks\.InICLR,Cited by:[§1](https://arxiv.org/html/2608.19882#S1.p1.1)\.
- Touvronet al\.\(2021\)H\. Touvron, M\. Cord, A\. Sablayrolles, G\. Synnaeve, and H\. JégouGoing deeper with image transformers\.InICCV,pp\. 32–42\.Cited by:[item i](https://arxiv.org/html/2608.19882#S4.I2.i1.4)\.
- Wanget al\.\(2019\)A\. Wang, A\. Singh, J\. Michael, F\. Hill, O\. Levy, and S\. R\. BowmanGLUE: a multi\-task benchmark and analysis platform for natural language understanding\.InICLR,Cited by:[item ii](https://arxiv.org/html/2608.19882#S4.I2.i2.4)\.
- Wanget al\.\(2023\)S\. Wang, Z\. Li, H\. Qian, C\. Yang,et al\.ReCode: robustness evaluation of code generation models\.InACL,Cited by:[§2\.2](https://arxiv.org/html/2608.19882#S2.SS2.p1.1),[§3\.2](https://arxiv.org/html/2608.19882#S3.SS2.p1.1),[item iii](https://arxiv.org/html/2608.19882#S4.I2.i3.4),[§4\.1](https://arxiv.org/html/2608.19882#S4.SS1.SSS0.Px2.p1.1)\.

## Appendix

The main paper reports recall curves and AUC scores but cannot show, due to space constraints, the detailed structure of the ground\-truth Pareto fronts𝒫∗\\mathcal\{P\}^\{\*\}across benchmarks and metric choices\. This appendix provides that evidence\.

Recall that each perturbation configuration is a vector𝜽=\(θ1,θ2,θ3,θ4\)\\bm\{\\theta\}=\(\\theta\_\{1\},\\theta\_\{2\},\\theta\_\{3\},\\theta\_\{4\}\), whereθi∈\{0,…,5\}\\theta\_\{i\}\\in\\\{0,\\ldots,5\\\}gives the severity of perturbation typeTiT\_\{i\}andθi=0\\theta\_\{i\}\{=\}0means thatTiT\_\{i\}is inactive\. The*perturbation order*of a configuration is the number of active perturbations,\|\{i:θi\>0\}\|\|\\\{i:\\theta\_\{i\}\>0\\\}\|\. We useΘk\\Theta\_\{k\}to denote the subset of the multi\-perturbation space containing configurations with exactlykkactive perturbations\. For example,𝜽=\(0,5,0,0\)\\bm\{\\theta\}\{=\}\(0,5,0,0\)is aΘ1\\Theta\_\{1\}configuration: it appliesT2T\_\{2\}at severity 5, withT1T\_\{1\},T3T\_\{3\}, andT4T\_\{4\}inactive\. In contrast,𝜽=\(1,5,1,1\)\\bm\{\\theta\}\{=\}\(1,5,1,1\)is aΘ4\\Theta\_\{4\}configuration, applying all four perturbation types at severities11,55,11, and11\. Thus, higher\-order configurations correspond to compositions of more perturbation types\.

Two questions motivate the appendix:

\(i\)Do configurations in𝒫∗\\mathcal\{P\}^\{\*\}include high\-fidelity failures rather than only trivially corrupted inputs?\(ii\)Does the choice of fidelity metricρ\\uprhomatter in practice?

Figures[5](https://arxiv.org/html/2608.19882#Ax1.F5)and[6](https://arxiv.org/html/2608.19882#Ax1.F6)visualise one fixed Tiny\-ImageNet example from our image\-classification benchmark \( \) under the Pareto\-optimal configurations found using\(δ,ρSSIM\)\(\\updelta,\\uprho\_\{\\mathrm\{SSIM\}\}\)and\(δ,ρKID\)\(\\updelta,\\uprho\_\{\\mathrm\{KID\}\}\), respectively\. For this benchmark,T1T\_\{1\}is speckle noise,T2T\_\{2\}is glass blur,T3T\_\{3\}is brightness, andT4T\_\{4\}is pixelate\. Each image is labelled with the configuration𝜽\\bm\{\\theta\}and its corresponding configuration\-level scoresδ⁡\(𝜽\)\\updelta\(\\bm\{\\theta\}\)andρ⁡\(𝜽\)\\uprho\(\\bm\{\\theta\}\)\. The examples allow visual inspection of the perturbations, whileδ⁡\(𝜽\)\\updelta\(\\bm\{\\theta\}\)reports the performance degradation induced by that configuration over the test set\.

Table[3](https://arxiv.org/html/2608.19882#Ax1.T3)summarises the Pareto\-front composition for under the two fidelity metrics\. SSIM and KID yield fronts of the same size \(\|𝒫∗\|=27\|\\mathcal\{P\}^\{\*\}\|=27\) but different order distributions: SSIM places more configurations inΘ1\\Theta\_\{1\}andΘ2\\Theta\_\{2\}, whereas KID places more inΘ3\\Theta\_\{3\}\. Thus, the fidelity metric affects which degradation–fidelity trade\-offs are Pareto\-optimal\.

Figures[7](https://arxiv.org/html/2608.19882#Ax1.F7), and[8](https://arxiv.org/html/2608.19882#Ax1.F8)address the second question using 4D voxel plots\. Each plot shows where𝒫∗\\mathcal\{P\}^\{\*\}lies in the full64=1,2966^\{4\}\{=\}1\{,\}296\-configuration space, with voxels coloured by perturbation order\. For non\-vision benchmarks, the perturbation typesT1,…,T4T\_\{1\},\\ldots,T\_\{4\}follow Table[1](https://arxiv.org/html/2608.19882#S3.T1); the same four\-dimensional configuration notation is used\. Together, the plots show that Pareto\-optimal configurations include both low\-order and higher\-order perturbation combinations across modalities and fidelity metrics\.

Metric pair𝒫∗\\mathcal\{P\}^\{\*\}Θ1\\Theta\_\{1\}Θ2\\Theta\_\{2\}Θ3\\Theta\_\{3\}Θ4\\Theta\_\{4\}\(δ,ρSSIM\)\(\\updelta,\\uprho\_\{\\mathrm\{SSIM\}\}\)2791242\(δ,ρKID\)\(\\updelta,\\uprho\_\{\\mathrm\{KID\}\}\)2747142Table 3:Pareto\-front composition per metric pair for \.![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order1/01_P1-0_P2-5_P3-0_P4-0.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order1/02_P1-0_P2-4_P3-0_P4-0.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order1/03_P1-0_P2-0_P3-0_P4-5.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order1/04_P1-0_P2-0_P3-0_P4-4.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order1/05_P1-0_P2-2_P3-0_P4-0.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order1/06_P1-0_P2-0_P3-0_P4-3.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order1/07_P1-0_P2-0_P3-0_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order1/08_P1-0_P2-0_P3-0_P4-1.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order1/09_P1-0_P2-0_P3-0_P4-0.png)\(a\) 9Θ1\\Theta\_\{1\}configurations![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order2/01_P1-4_P2-5_P3-0_P4-0.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order2/02_P1-3_P2-5_P3-0_P4-0.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order2/03_P1-2_P2-5_P3-0_P4-0.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order2/04_P1-1_P2-5_P3-0_P4-0.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order2/05_P1-2_P2-4_P3-0_P4-0.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order2/06_P1-1_P2-4_P3-0_P4-0.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order2/07_P1-0_P2-2_P3-0_P4-5.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order2/08_P1-1_P2-0_P3-0_P4-5.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order2/09_P1-0_P2-0_P3-1_P4-5.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order2/10_P1-0_P2-0_P3-1_P4-4.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order2/11_P1-1_P2-2_P3-0_P4-0.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order2/12_P1-0_P2-0_P3-1_P4-3.png)\(b\) 12Θ2\\Theta\_\{2\}configurations![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order3/01_P1-1_P2-5_P3-1_P4-0.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order3/02_P1-2_P2-2_P3-0_P4-5.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order3/03_P1-1_P2-2_P3-0_P4-5.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order3/04_P1-1_P2-2_P3-0_P4-4.png)\(c\) 4Θ3\\Theta\_\{3\}configurations![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order4/01_P1-1_P2-5_P3-1_P4-1.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order4/02_P1-2_P2-2_P3-1_P4-5.png)\(d\) 2Θ4\\Theta\_\{4\}configurationsFigure 5:\(δ,ρSSIM\)\(\\updelta,\\uprho\_\{\\mathrm\{SSIM\}\}\)Pareto\-optimal configurations for one Tiny\-ImageNet example, grouped by active perturbation count\. Each image is labelled with its perturbation configuration𝜽\\bm\{\\theta\}and the corresponding configuration\-level scoresδ⁡\(𝜽\)\\updelta\(\\bm\{\\theta\}\)andρ⁡\(𝜽\)\\uprho\(\\bm\{\\theta\}\)\.![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order1/01_P1-0_P2-0_P3-0_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order1/02_P1-0_P2-0_P3-2_P4-0.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order1/03_P1-0_P2-0_P3-1_P4-0.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/ssim_chrf/order1/09_P1-0_P2-0_P3-0_P4-0.png)\(a\) 4Θ1\\Theta\_\{1\}configurations![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order2/01_P1-0_P2-0_P3-4_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order2/02_P1-2_P2-0_P3-0_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order2/03_P1-0_P2-0_P3-3_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order2/04_P1-0_P2-2_P3-0_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order2/05_P1-0_P2-0_P3-2_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order2/06_P1-0_P2-1_P3-0_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order2/07_P1-0_P2-0_P3-1_P4-2.png)\(b\) 7Θ2\\Theta\_\{2\}configurations![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order3/01_P1-0_P2-5_P3-3_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order3/02_P1-0_P2-5_P3-2_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order3/03_P1-0_P2-5_P3-1_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order3/04_P1-1_P2-0_P3-5_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order3/05_P1-3_P2-0_P3-3_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order3/06_P1-2_P2-0_P3-4_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order3/07_P1-1_P2-0_P3-4_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order3/08_P1-2_P2-0_P3-3_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order3/09_P1-0_P2-1_P3-4_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order3/10_P1-1_P2-0_P3-3_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order3/11_P1-1_P2-0_P3-2_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order3/12_P1-0_P2-1_P3-3_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order3/13_P1-0_P2-2_P3-2_P4-2.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order3/14_P1-0_P2-1_P3-2_P4-2.png)\(c\) 14Θ3\\Theta\_\{3\}configurations![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order4/01_P1-1_P2-5_P3-1_P4-1.png)![Refer to caption](https://arxiv.org/html/2608.19882v1/workshop_figures/pareto_examples/kid_bert/order4/02_P1-1_P2-5_P3-1_P4-2.png)\(d\) 2Θ4\\Theta\_\{4\}configurationsFigure 6:\(δ,ρKID\)\(\\updelta,\\uprho\_\{\\mathrm\{KID\}\}\)Pareto\-optimal configurations for one Tiny\-ImageNet example, grouped by active perturbation count\. Each image is labelled with its perturbation configuration𝜽\\bm\{\\theta\}and the corresponding configuration\-level scoresδ⁡\(𝜽\)\\updelta\(\\bm\{\\theta\}\)andρ⁡\(𝜽\)\\uprho\(\\bm\{\\theta\}\)\.\(a\) Paraphrase detection \( \)

\(b\) Code generation \(HumanEval\) \( \)

\(c\) Code generation \(MBPP\) \( \)

Figure 7:4D voxel visualisations of𝒫∗\\mathcal\{P\}^\{\*\}for non\-vision benchmarks using chrF as the fidelity metric\.\(a\) Paraphrase detection \( \)

\(b\) Code generation \(HumanEval\) \( \)

\(c\) Code generation \(MBPP\) \( \)

Figure 8:4D voxel visualisations of𝒫∗\\mathcal\{P\}^\{\*\}for non\-vision benchmarks using BERT\-F1 as the fidelity metric\.