# What If, But Privately: Private Counterfactual Retrieval

arXiv: https://arxiv.org/abs/2508.03681 · HTML: https://mlsanity.com/paper/2508.03681/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 54 references that are in the map.
- First posted on arXiv 5 Aug 2025.

## Builds on (most cited first, 30 of 30)

- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [FACE: Feasible and Actionable Counterfactual Explanations](https://mlsanity.com/paper/1909.09369/) (2019)
- [NICE: An Algorithm for Nearest Instance Counterfactual Explanations](https://mlsanity.com/paper/2104.07411/) (2021)
- [Robust Counterfactual Explanations for Tree-Based Ensembles](https://mlsanity.com/paper/2207.02739/) (2022)
- [Model extraction from counterfactual explanations](https://mlsanity.com/paper/2009.01884/) (2020)
- [Robust Counterfactual Explanations for Neural Networks With Probabilistic Guarantees](https://mlsanity.com/paper/2305.11997/) (2023)
- [A Survey on the Robustness of Feature Importance and Counterfactual Explanations](https://mlsanity.com/paper/2111.00358/) (2021)
- [DualCF: Efficient Model Extraction Attack from Counterfactual Explanations](https://mlsanity.com/paper/2205.06504/) (2022)
- [On the Privacy Risks of Algorithmic Recourse](https://mlsanity.com/paper/2211.05427/) (2022)
- [The privacy issue of counterfactual explanations: explanation linkage attacks](https://mlsanity.com/paper/2210.12051/) (2022)
- [Model Reconstruction Using Counterfactual Explanations: A Perspective From Polytope Theory](https://mlsanity.com/paper/2405.05369/) (2024)
- [Differentially Private Counterfactuals via Functional Mechanism](https://mlsanity.com/paper/2208.02878/) (2022)
- [Private Retrieval, Computing and Learning: Recent Progress and Future Challenges](https://mlsanity.com/paper/2108.00026/) (2021)
- [The Capacity of Private Information Retrieval](https://mlsanity.com/paper/1602.09134/) (2016)
- [The Capacity of Robust Private Information Retrieval with Colluding Databases](https://mlsanity.com/paper/1605.00635/) (2016)
- [The Capacity of Private Information Retrieval from Coded Databases](https://mlsanity.com/paper/1609.08138/) (2016)
- [The Capacity of Symmetric Private Information Retrieval](https://mlsanity.com/paper/1606.08828/) (2016)
- [Multi-Message Private Information Retrieval: Capacity Results and Near-Optimal Schemes](https://mlsanity.com/paper/1702.01739/) (2017)
- [Privacy-Preserving Algorithmic Recourse](https://mlsanity.com/paper/2311.14137/) (2023)
- [Capacity-Achieving Private Information Retrieval Codes with Optimal Message Size and Upload Cost](https://mlsanity.com/paper/1808.07536/) (2018)
- [Semantic Private Information Retrieval](https://mlsanity.com/paper/2003.13667/) (2020)
- [The Capacity of Private Information Retrieval from Byzantine and Colluding Databases](https://mlsanity.com/paper/1706.01442/) (2017)
- [Private Information Retrieval Through Wiretap Channel II: Privacy Meets Security](https://mlsanity.com/paper/1801.06171/) (2018)
- [The Capacity of Private Information Retrieval with Eavesdroppers](https://mlsanity.com/paper/1804.10189/) (2018)
- [The Capacity of Private Information Retrieval from Uncoded Storage Constrained Databases](https://mlsanity.com/paper/1805.04104/) (2018)
- [Private Information Retrieval in Graph Based Replication Systems](https://mlsanity.com/paper/1812.01566/) (2018)
- [The Capacity of Private Information Retrieval from Heterogeneous Uncoded Caching Databases](https://mlsanity.com/paper/1902.09512/) (2019)
- [Asymmetric X-Secure T-Private Information Retrieval: More Databases is Not Always Better](https://mlsanity.com/paper/2305.05649/) (2023)
- [Private Information Retrieval on Multigraph-Based Replicated Storage](https://mlsanity.com/paper/2501.17845/) (2025)

## Abstract (arXiv)

Transparency and explainability are two important aspects to be considered when employing black-box machine learning models in high-stake applications. Providing counterfactual explanations is one way of catering this requirement. However, this also poses a threat to the privacy of the institution that is providing the explanation, as well as the user who is requesting it. In this work, we are primarily concerned with the user's privacy who wants to retrieve a counterfactual instance, without revealing their feature vector to the institution. Our framework retrieves the exact nearest neighbor counterfactual explanation from a database of accepted points while achieving perfect, information-theoretic, privacy for the user. First, we introduce the problem of private counterfactual retrieval (PCR) and propose a baseline PCR scheme that keeps the user's feature vector information-theoretically private from the institution. Building on this, we propose two other schemes that reduce the amount of information leaked about the institution database to the user, compared to the baseline scheme. Second, we relax the assumption of mutability of all features, and consider the setting of immutable PCR (I-PCR). Here, the user retrieves the nearest counterfactual without altering a private subset of their features, which constitutes the immutable set, while keeping their feature vector and immutable set private from the institution. For this, we propose two schemes that preserve the user's privacy information-theoretically, but ensure varying degrees of database privacy. Third, we extend our PCR and I-PCR schemes to incorporate user's preference on transforming their attributes, so that a more actionable explanation can be received. Finally, we present numerical results to support our theoretical findings, and compare the database leakage of the proposed schemes.