Research map / Learning theory and algorithms / Prediction and decision losses
Model Reconstruction Using Counterfactual Explanations: A Perspective From Polytope Theory
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives polytope-theory query-complexity bounds for reconstructing a model from one-sided counterfactual explanations and proposes Counterfactual Clamping Attack (CCA), a loss that clamps counterfactual predictions near 0.5 to reduce decision boundary shift.
Problem
Model reconstruction (extraction) of a black-box classifier using only one-sided counterfactual explanations, where existing methods suffer decision boundary shift and theoretical guarantees on query complexity are lacking.
Approach
Uses the fact that counterfactuals lie close to the target decision boundary: a clamped loss trains the surrogate so counterfactuals are pushed to probability k (≤1) rather than treated as ordinary labeled points, with theory from random polytope approximation and CPWL geometry giving query-complexity bounds.
Key results
- On real-world datasets with 400 queries and architecture-known surrogate, CCA achieves e.g. DCCC test fidelity 99±0.9 vs 89±8.9 for Baseline.
- CCA matches or beats Baseline across Adult Income, COMPAS, DCCC and HELOC, under both known and unknown surrogate architectures.
- Across counterfactual generators on HELOC, CCA improves fidelity over Baseline in most settings (e.g., MCCF L2 n=100: 95 vs 91 on test data).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CCA instead of Baseline | Model reconstruction with one-sided counterfactuals · Adult Income test, model 0 | fidelity: 91$\pm$3.2 -> 94$\pm$3.2 | Helped |
| Use CCA instead of Baseline | Model reconstruction with one-sided counterfactuals · COMPAS test, model 0 | fidelity: 92$\pm$3.2 -> 96$\pm$2.0 | Helped |
| Use CCA instead of Baseline | Model reconstruction with one-sided counterfactuals · DCCC test, model 0 | fidelity: 89$\pm$8.9 -> 99$\pm$0.9 | Helped |
| Use CCA instead of Baseline | Model reconstruction with one-sided counterfactuals · HELOC test, model 0 | fidelity: 91$\pm$4.7 -> 96$\pm$2.2 | Helped |
| Replace CCA loss with binary cross-entropy using labels 0, 1 and 0.5 (ablation) | Counterfactual Clamping Attack · Experiments comparing alternate loss functions | fidelity | Hurt |
| Decrease the target model's Lipschitz constant | CCA model reconstruction · Datasets used in the Lipschitz-constant experiment | fidelity | Helped |
| Increase the target model's Lipschitz constant | CCA model reconstruction · Datasets used in the Lipschitz-constant experiment | fidelity | Hurt |
| Use CCA instead of Baseline across counterfactual generation methods | HELOC model reconstruction · HELOC test and uniform; MCCF, DiCE, 1-Nearest-Neighbor, ROAR and C-CHVAE | fidelity | Mixed |
Surprising findings
- Counterfactual generators other than closest MCCF (e.g., DiCE, 1-NN) often produce counterfactuals deep inside the favorable region, yet CCA still performs well.
- C-CHVAE counterfactuals give lower fidelity overall, and CCA is not uniformly better there (uniform-data fidelity drops from 85 to 78 at n=200).
Limitations
- Exact characterization of k(epsilon) and v_i(epsilon) is lacking, so bounds are not fully explicit.
- Local Lipschitz continuity may not hold for models such as decision trees.
- Analysis is restricted to binary classification.
Experimental setup
Datasets: Adult Income COMPAS DCCC HELOC make_moons synthetic
Benchmarks: Adult Income COMPAS DCCC HELOC synthetic 2-D make_moons
Metrics: fidelity
Baselines: Baseline (counterfactuals as ordinary labeled points) DualCFX DiCE C-CHVAE ROAR
Builds on: Counterfactual-based model extraction (Aïvodji et al. / Baseline attack) DualCFX Minimum Cost Counterfactuals (MCCF) random polytope approximation
Closest papers by meaning
- Faithful Model Explanations through Energy-Constrained Conformal Counterfactuals (AAAI 2024 · similarity 0.90)
- A New Approach to Backtracking Counterfactual Explanations: A Unified Causal Framework for Efficient Model Interpretability (ICML 2025 · similarity 0.89)
- LeapFactual: Reliable Visual Counterfactual Explanation Using Conditional Flow Matching (NeurIPS 2025 · similarity 0.88)
- Counterfactual Graphical Models: Constraints and Inference (ICML 2025 · similarity 0.87)
- Promoting Counterfactual Robustness through Diversity (AAAI 2024 · similarity 0.87)
- Generating Likely Counterfactuals Using Sum-Product Networks (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.