# TESTNAV: Pareto-Guided Search for Compositional Robustness Testing

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 35 references that are in the map.
- First posted on arXiv 20 Aug 2026.

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

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Benchmarking Neural Network Robustness to Common Corruptions and Perturbations](https://mlsanity.com/paper/1903.12261/) (2019)
- [A Call for Clarity in Reporting BLEU Scores](https://mlsanity.com/paper/1804.08771/) (2018)
- [CodeBERT: A Pre-Trained Model for Programming and Natural Languages](https://mlsanity.com/paper/2002.08155/) (2020)
- [Beyond Accuracy: Behavioral Testing of NLP models with CheckList](https://mlsanity.com/paper/2005.04118/) (2020)
- [AugMix: A Simple Data Processing Method to Improve Robustness and Uncertainty](https://mlsanity.com/paper/1912.02781/) (2019)
- [CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis](https://mlsanity.com/paper/2203.13474/) (2022)
- [Going deeper with Image Transformers](https://mlsanity.com/paper/2103.17239/) (2021)
- [DeepXplore: Automated Whitebox Testing of Deep Learning Systems](https://mlsanity.com/paper/1705.06640/) (2017)
- [pymoo: Multi-objective Optimization in Python](https://mlsanity.com/paper/2002.04504/) (2020)
- [DeepGauge: Multi-Granularity Testing Criteria for Deep Learning Systems](https://mlsanity.com/paper/1803.07519/) (2018)
- [MNIST-C: A Robustness Benchmark for Computer Vision](https://mlsanity.com/paper/1906.02337/) (2019)
- [Guiding Deep Learning System Testing using Surprise Adequacy](https://mlsanity.com/paper/1808.08444/) (2018)
- [ReCode: Robustness Evaluation of Code Generation Models](https://mlsanity.com/paper/2212.10264/) (2022)
- [On Interaction Between Augmentations and Corruptions in Natural Corruption Robustness](https://mlsanity.com/paper/2102.11273/) (2021)
- [DLFuzz: Differential Fuzzing Testing of Deep Learning Systems](https://mlsanity.com/paper/1808.09413/) (2018)
- [Is Your HD Map Constructor Reliable under Sensor Corruptions?](https://mlsanity.com/paper/2406.12214/) (2024)
- [TestifAI: Tomography-Based Testing for Deep Learning Systems](https://mlsanity.com/paper/2608.18900/) (2026)

## Abstract (arXiv)

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.