# Local permutation tests for conditional independence

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Dec 2021.

## Built on by (most cited first, 23 of 23)

- [Signature Kernel Conditional Independence Tests in Causal Discovery for Stochastic Processes](https://mlsanity.com/paper/2402.18477/) (2024)
- [Practical Kernel Tests of Conditional Independence](https://mlsanity.com/paper/2402.13196/) (2024)
- [A unified framework for dataset shift diagnostics](https://mlsanity.com/paper/2205.08340/) (2022)
- [Conditional independence testing under misspecified inductive biases](https://mlsanity.com/paper/2307.02520/) (2023)
- [Interpretable Machine Learning for Discovery: Statistical Challenges & Opportunities](https://mlsanity.com/paper/2308.01475/) (2023)
- [Doubly Robust Conditional Independence Testing with Generative Neural Networks](https://mlsanity.com/paper/2407.17694/) (2024)
- [On the Hardness of Conditional Independence Testing In Practice](https://mlsanity.com/paper/2512.14000/) (2025)
- [On the Limitations of Fractal Dimension as a Measure of Generalization](https://mlsanity.com/paper/2406.02234/) (2024)
- [Efficient Ensemble Conditional Independence Test Framework for Causal Discovery](https://mlsanity.com/paper/2509.21021/) (2025)
- [Double Machine Learning Based Structure Identification from Temporal Data](https://mlsanity.com/paper/2311.06012/) (2023)
- [General Frameworks for Conditional Two-Sample Testing](https://mlsanity.com/paper/2410.16636/) (2024)
- [A survey of some recent developments in measures of association](https://mlsanity.com/paper/2211.04702/) (2022)
- [The Limits of Assumption-free Tests for Algorithm Performance](https://mlsanity.com/paper/2402.07388/) (2024)
- [Deep Nonparametric Conditional Independence Tests for Images](https://mlsanity.com/paper/2411.06140/) (2024)
- [Causal Deepsets for Off-policy Evaluation under Spatial or Spatio-temporal Interferences](https://mlsanity.com/paper/2407.17910/) (2024)
- [A Fast Kernel-based Conditional Independence test with Application to Causal Discovery](https://mlsanity.com/paper/2505.11085/) (2025)
- [Toward Scalable and Valid Conditional Independence Testing with Spectral Representations](https://mlsanity.com/paper/2512.19510/) (2025)
- [Empirically Calibrated Conditional Independence Tests](https://mlsanity.com/paper/2602.21036/) (2026)
- [Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information](https://mlsanity.com/paper/2411.11516/) (2024)
- [Optimal structure learning and conditional independence testing](https://mlsanity.com/paper/2507.05689/) (2025)
- [Restricted Block Permutation for Two-Sample Testing](https://mlsanity.com/paper/2512.00668/) (2025)
- [Cross-Entropy Risk Estimation for Language Models: Inconsistency Must Be Dense, and the Holdout Method Is No Exception](https://mlsanity.com/paper/2608.15798/) (2026)
- [Decoupled Causal Discovery](https://mlsanity.com/paper/2609.23535/) (2026)

## Abstract (arXiv)

In this paper, we investigate local permutation tests for testing conditional independence between two random vectors X and Y given Z. The local permutation test determines the significance of a test statistic by locally shuffling samples which share similar values of the conditioning variables Z, and it forms a natural extension of the usual permutation approach for unconditional independence testing. Despite its simplicity and empirical support, the theoretical underpinnings of the local permutation test remain unclear. Motivated by this gap, this paper aims to establish theoretical foundations of local permutation tests with a particular focus on binning-based statistics. We start by revisiting the hardness of conditional independence testing and provide an upper bound for the power of any valid conditional independence test, which holds when the probability of observing collisions in Z is small. This negative result naturally motivates us to impose additional restrictions on the possible distributions under the null and alternate. To this end, we focus our attention on certain classes of smooth distributions and identify provably tight conditions under which the local permutation method is universally valid, i.e. it is valid when applied to any (binning-based) test statistic. To complement this result on type I error control, we also show that in some cases, a binning-based statistic calibrated via the local permutation method can achieve minimax optimal power. We also introduce a double-binning permutation strategy, which yields a valid test over less smooth null distributions than the typical single-binning method without compromising much power. Finally, we present simulation results to support our theoretical findings.