Cobweb: Enhanced Generation Diversity for Black-box Fairness Testing

Black-box fairness testing aims to reveal potential discriminatory behaviors in deployed AI models by generating individual discriminatory instances, thereby safeguarding trustworthiness in socially critical domains such as smart education and talent recruitment. However, existing approaches often suffer from limited instance space coverage due to their reliance on local neighborhood searches around predefined seed instances, leading to poor diversity and suboptimal exploration. To address these limitations, we propose Cobweb, a novel black-box fairness testing framework that combines genetic algorithms with explicit region-guided generation and multiobjective evolutionary search. First, the initial population is constructed via spatial uniform initialization to maximize instance diversity through pairwise distance optimization. Second, we introduce an explicit region-guided strategy and design a dualobjective optimization mechanism, which concurrently optimizes for both individual discrimination and spatial sparsity, enabling outward search into low-density regions. These mechanisms jointly improve Cobweb s ability to generate diverse and spatially representative discriminatory instances. Extensive experiments on seven benchmark tabular datasets demonstrate that Cobweb achieves significant improvements over state-of-the-art baselines, with gains in effectiveness (~ 1.6 ), efficiency (~ 2.9 ) on average under fixed query budgets. In particular, Cobweb consistently achieves higher scores in three complementary diversity metrics, confirming its superior exploratory capability. Retraining target models with Cobwebgenerated instances leads to an average reduction of 57% in individual fairness violations, confirming the practical value of our approach.