One way to see what a trained classifier "wants" is to run it backwards. You freeze the model, start from random inputs, and use gradient descent on the inputs until the model outputs a chosen decision, such as "loan approved." The resulting "canonical" inputs show which features the model rewards. LUCID used this to audit models on UCI Adult and COMPAS. Its central finding was that an Adult income model looked racially biased under ordinary output metrics, but its internal logic favored "Male" and "Married" and was neutral on race.
That conclusion rests on inputs that nobody constrained to be possible. Gradient descent on a one-hot encoded record can produce a person who is 0.4 married and 0.7 never-married, or a 19-year-old with a doctorate. The audit's verdict may therefore describe regions of input space the model never sees. We propose to make the backward search respect the structure of real data. We add penalty terms that are zero on valid inputs and positive on invalid ones, and adapt their weights during the search. We then test whether the audit's conclusions survive this change, whether they recover biases we plant on purpose, and whether they carry from tabular records to medical images.
Core Claim
Our claim is that unconstrained canonical inversion gives audit conclusions that are partly artifacts of infeasible inputs. Enforcing validity through an adaptive penalty removes those artifacts without the collapse that a large fixed penalty causes. Here "artifact" means a bias verdict that appears only because the search visited impossible inputs. "Collapse" means every canonical input converging to the most common real record, which leaves the audit blind.
The penalty design comes from quantum and annealing optimization, where the problem is the same: a solver for unconstrained problems has to be made to respect hard constraints. That literature encodes "exactly one of these is on" as a quadratic penalty. Adiabatic Quantum Graph Matching with Permutation Matrix Constraints does this for the rows and columns of permutation matrices, and lattice protein Hamiltonians do it for chain connectivity and non-overlap. The same literature documents the tuning problem that constrains our design. If the penalty weight is too small, the solver ignores the constraint to lower its objective (QuantumQUBO Agent). If it is too large, the weight flattens the objective landscape so that good and mediocre feasible solutions look alike (Optimizing the Production of Test Vehicles Using Hybrid Constrained Quantum Annealing).
In an audit, the flattened landscape is exactly the collapse failure. We borrow the fix that subgradient and Lagrangian adiabatic methods and federated fair learning with an augmented Lagrangian use: per-constraint multipliers that grow only on constraints that stay violated. None of these works applies the idea to searching over inputs of a frozen model. The federated work constrains model training, not an audit.
Concretely, for a frozen classifier $f$, target decision $y^*$ and input $x$, we solve
$$\min_x \; -\log p_f(y^* \mid x) \;+\; \sum_k \mu_k c_k(x) \;+\; \frac{\rho}{2}\sum_k c_k(x)^2 ,$$
The terms are defined as follows. Each $c_k(x)$ measures violation of one validity rule and is zero exactly when the rule holds. For a categorical block $j$ it is $\sum_i x_{ji} - 1$, as in the permutation-row penalty. For each coordinate that must end up at 0 or 1 it is the term $x_i(1 - x_i)$, which vanishes only at 0 or 1 and so pushes the search toward integral values. For logical implications and range rules mined from the training data it is a hinge function. For images it is the reconstruction error of an autoencoder trained on real scans. The $\mu_k$ are multipliers, updated after each inner solve by $\mu_k \leftarrow \mu_k + \rho\, c_k(x)$. $\rho$ is a quadratic weight that increases only when total violation stalls.
Research Program
The first component is a constraint compiler for tabular data. It turns the schema and mined rules into the $c_k$ terms. The schema supplies categorical blocks and bounds. The mined rules are implications that hold with zero exceptions in training data, for example across marital-status and relationship fields in Adult.
The second component is the solver loop. It runs many random restarts to form a canonical set for each target decision. Its outputs are rounded, and a sample counts as valid only if it satisfies every rule exactly after rounding.
The third component is an audit readout. For each protected attribute and each suspected proxy, it reports the skew of the canonical set relative to the real population. It also reports the model's sensitivity when that attribute is flipped inside the canonical set.
For images, we invert in the latent space of an autoencoder trained on source-domain fundus data. The validity terms are latent density and reconstruction error. We read demographics off canonical images with an attribute predictor trained on real data, and we measure that predictor's error so the image audit's noise floor is explicit.
The cross-modality question is whether one constraint interface, with a single solver and a single multiplier schedule, works without retuning on both sparse one-hot records and continuous image latents. The file's evidence suggests that a fixed weight will not. Some Optimizers are More Equal finds that optimization dynamics that matter for fairness differ across settings, and fixed-penalty fairness regularizers such as the FairCLIP optimal-transport term have to be tuned per task. We treat "no retuning across data types" as a hypothesis to test, not an assumption.
Baselines
The naive reference point is no inversion at all: slice metrics on the held-out test set, meaning per-group positive rates and gaps. This is what LUCID argues against. It must be included because, if it already recovers planted biases, inversion adds nothing.
The strongest existing method for the same question is unconstrained LUCID. It will be run on the same frozen models with the same number of restarts and gradient steps. For realism, the competitor is LUCID-GAN, a conditional tabular GAN whose realism comes from a Wasserstein critic. It gets the same data and the same wall-clock budget, including GAN training time.
LUCID and LUCID-GAN report qualitative preferences only. There is no reported numerical result on Lacuna for either on Adult or COMPAS, so we will reproduce both rather than quote figures.
Two ablations isolate the key ingredient, which is adaptive weighting. The first is fixed-weight penalties over a grid of weights, given the same total compute as the adaptive schedule. The second is projected gradient descent, which projects each categorical block onto the probability simplex after every step.
Beating the baselines means three things. First, after rounding, a higher fraction of canonical inputs is fully valid than under LUCID. Second, canonical inputs are closer to real data than LUCID's, and no worse than LUCID-GAN's, measured by nearest-neighbor distance and by a classifier trained to tell canonical from real. Third, planted-bias recovery is strictly better than the best grid-searched fixed weight, measured by rank correlation between injected effect size and measured skew.
A positive control is a model trained with FairContrast, which reports 84.4% accuracy and a demographic parity gap of 0.0255 on Adult. A trustworthy auditor should report little sex skew for this model.
Why not just…?
Why not just round or project the unconstrained LUCID output onto valid values? For independent categorical blocks, projection is cheap and may match our method, so we report it as its own baseline. The concern is coupled rules. Projecting one block at a time can still produce records that break implications across fields. A single post-hoc rounding can also land in a region where the model's decision flips. We will measure what fraction of rounded LUCID samples still receive the target decision. If projection matches us on both validity and recovery, the contribution shrinks to coupled-rule handling, and we will say so.
Why not just use a generative model, as LUCID-GAN does? A GAN enforces realism only statistically and says nothing about any single sample obeying a hard rule. It also requires training a separate generator per dataset and data type. On images, a GAN prior could be the stronger competitor. We therefore compare on validity rate, on recovery, and on whether GAN canonical sets under-represent rare but valid subgroups. That last failure is the mode-collapse analogue of the flattened landscape.
Why not just grid-search a fixed penalty weight? This is a real threat on any single dataset. Our claim is that no single weight works across Adult, COMPAS and image latents, and that per-dataset search needs planted-bias labels, which real audits lack. We will report the best fixed weight chosen with hindsight on each dataset. We will also report the weight chosen on one dataset and applied to another. The adaptive method must match the first and beat the second.
Proposed Experiments
The decisive test uses planted biases. On Adult, COMPAS, German Credit and Heritage Health, we train models on relabeled data. In the relabeled data, the outcome depends by a known, varied amount on a protected attribute or on a proxy, such as marital status standing in for sex. The label is untouched in a control condition. An audit is correct if its measured skew ranks the planted effects correctly. Unconstrained inversion should mis-rank the effects when the planted dependence sits in rule-coupled fields. If it does not, Gap 1 in the file is illusory for tabular data.
The second test re-examines LUCID's own Adult finding: race-neutral internal logic with a male and married skew. We ask whether that finding survives feasibility, and how it changes under the adaptive schedule.
The third test addresses cross-modality predictive validity. On Harvard-FairDomain20k, FairDomain reports that the racial disparity in optic cup segmentation "nearly triple[s]" from En-face to SLO imaging. We audit glaucoma classifiers trained on the source domain and ask whether subgroup skew in the canonical sets predicts which subgroups' AUC drops most on the target domain. We compare this against source-domain slice gaps as the predictor. We add Harvard-GF as a second imaging set with balanced racial groups.
Across all experiments, the solver hyperparameters are fixed once, on German Credit, and never retuned. The failure condition is clear. If feasibility-constrained audits recover planted biases no better than grid-searched fixed penalties or projection, and fail to predict the domain-shift disparity better than slice metrics, then the adaptive-penalty machinery is not earning its complexity.
References
- LUCID: Exposing Algorithmic Bias through Inverse Design
- Adiabatic Quantum Graph Matching with Permutation Matrix Constraints
- Construction of model Hamiltonians for adiabatic quantum computation and its application to finding low-energy conformations of lattice protein models
- QuantumQUBO Agent: Automating Quadratic Unconstrained Binary Optimization (QUBO) Formulation Generation from Natural Language
- Optimizing the Production of Test Vehicles Using Hybrid Constrained Quantum Annealing
- A subgradient approach for constrained binary optimization via quantum adiabatic evolution
- Solving constrained quadratic binary problems via quantum adiabatic evolution
- Fairness-aware Federated Minimax Optimization with Convergence Guarantee
- Some Optimizers are More Equal: Understanding the Role of Optimizers in Group Fairness
- FairCLIP: Harnessing Fairness in Vision-Language Learning
- LUCID-GAN: Conditional Generative Models to Locate Unfairness
- FairContrast: Enhancing Fairness through Contrastive learning and Customized Augmenting Methods on Tabular Data
- FairDomain: Achieving Fairness in Cross-Domain Medical Image Segmentation and Classification
- Harvard Glaucoma Fairness: A Retinal Nerve Disease Dataset for Fairness Learning and Fair Identity Normalization