TESTNAV Uses Pareto Search to Find Compositional Robustness Failures 2.15x Faster Than Search-Based Baselines

arXiv 2608.19882·medium signalXBlueskyLinkedInCopy link

Real inputs carry multiple simultaneous corruptions, but compositional robustness testing faces combinatorial blowup and wastes budget on combinations that produce unrealistically degraded inputs with no diagnostic value. TESTNAV frames it as bi-objective optimization, maximizing performance degradation while preserving input fidelity via modality-specific metrics (SSIM and KID for vision, chrF and BERT-F1 for language and code), and approximates the Pareto front with NSGA-II. Across four benchmarks spanning vision, natural language and code generation it recovers Pareto fronts up to 2.15x faster than search-based baselines while touching 35.8%-89.3% of a perturbation space defined by four dimensions at six severity levels each.