Scalable Audit and Mitigation of Intersectional Fairness Bugs in VLMs with Combinatorial Interaction Testing

Intersectionality analysis is critical for fairness, since individuals hold multiple and overlapping identities whose intersections shape how they are perceived and treated, bringing distinct disadvantages as well as privileges. This matters even more for algorithmic systems such as Vision-Language Models (VLMs), which increasingly serve as auditors of other models, or as backbones of downstream applications. However, VLM fairness is often evaluated one axis at a time, leaving failures that emerge only in higher-order intersectional subgroups undetected: we frame this problem as intersectional fairness bugs. Such bugs remain hard to find: the number of attribute combinations grows combinatorially, making it prohibitively expensive to collect and label data for every subgroup. We propose a scalable and tunable audit for VLMs built on Combinatorial Interaction Testing (CIT) from software testing. Given a set of parameters and their potential values, CIT aims to test all interactions between at most $t$ parameters, instead of testing all combinations of parameter values, thus controlling the combinatorial explosion. Using CIT in conjunction with diffusion-based synthesis, we show that it is possible to both audit VLMs for intersectional fairness bugs and mitigate them by focusing on specific hard subgroups or augmenting training data with synthetic images representative of subgroups. Our empirical evaluation of CIT-based audit and mitigation shows that 1) 60 subgroup accuracies on synthetic images correlate with those on real images for four VLMs (Pearson $r=0.59$–$0.84$; Spearman $\rho =0.56$–$0.77$), and 2) when fine-tuning CLIP, audit-guided data allocation improves the mean accuracy of the worst 10% of subgroups (${\mathrm{CVaR}}_{0.1}$) by up to 4.0 pp under small budgets, and mixing CIT images into real images improves it by up to 2.2 pp under tail data scarcity.