Exact Paired-Permutation Testing for Structured Test Statistics

Ran Zmigrod, Tim Vieira, Ryan Cotterell

Introduction

In Natural Language Processing (NLP), determining whether System A is significantly better than System B is a fundamental task. The paired-permutation test is widely regarded as the gold standard for this purpose because it makes no assumptions about the underlying data distribution. However, calculating the exact p-value for a dataset of size $N$ requires summing over $2^N$ possible permutations—a task that becomes computationally impossible for even small datasets. For a dataset of just 100 sentences, the number of permutations exceeds the number of atoms in the observable universe.

To circumvent this, researchers typically rely on Monte Carlo (MC) approximations, which sample a subset of permutations. While practical, MC methods introduce "approximation noise," leading to inconsistent p-values across different runs. This paper introduces a breakthrough: an exact algorithm that is not only mathematically precise but also significantly faster than standard approximations.

Methods: From Combinatorics to Convolutions

The core insight of this work is that for "structured" test statistics—those that are additively decomposable, such as accuracy or $F_1$ components—the problem can be reframed. The probability mass function (PMF) of a sum of independent random variables is the convolution of their individual PMFs. Essentially, the paired-permutation test asks for the distribution of a sum of independent "stay-or-swap" decisions.

The p-value calculation as a sum over the tail of the test statistic's distribution.

The authors propose two primary algorithmic approaches to solve these convolutions:

  1. Dynamic Programming (DP): A $O(GN^2)$ method that builds the distribution step-by-step.
  2. Fast Fourier Transform (FFT): By performing convolutions in the frequency domain using a divide-and-conquer strategy, the complexity is reduced to $O(GN \log GN \log N)$, where $G$ represents the range of the test statistic.

Experimental Evaluation

The algorithms were tested using simulated comparisons between part-of-speech (POS) taggers. Data was drawn from the Universal Dependency (UD) English test set, with realistic system performance statistics generated using the Stanza NLP library. The researchers focused on measuring the runtime efficiency of their exact methods against varying levels of Monte Carlo sampling ($K$).

Key Results: Exact is Faster

The most surprising finding is that the exact FFT-based test often outperforms approximate methods in terms of raw speed. Usually, exact algorithms are considered the "slow but correct" option; here, they are both faster and more accurate.

Runtime comparison between exact FFT-based testing and Monte Carlo approximations.
  • 10x Speedup: On a dataset of 10,000 sentences, the FFT-based exact test was ten times faster than a Monte Carlo simulation with 20,000 samples.
  • Real-time Efficiency: For $N=10,000$, the exact test completes in approximately 0.1 seconds on a modern processor (Apple M1 Max).
  • Scalability: While the DP approach is efficient for standard dataset sizes (up to ~8,000 sentences), the FFT approach scales significantly better as dataset sizes increase.

Discussion and Limitations

While this framework represents a major step forward, some constraints remain. The algorithm currently requires test statistic components to be integer-valued. Metrics using floating-point weights would require scaling and rounding, which could introduce minor errors. Additionally, complex metrics like $F_1$ require multi-dimensional convolutions, which increases computational overhead as the number of dimensions grows.

Despite these limitations, the ability to perform exact significance testing efficiently marks a shift in how NLP researchers can validate their results, moving away from noisy approximations toward deterministic, reproducible science.

Code Availability: The authors have released their implementation at github.com/rycolab/paired-perm-test.

Summary updated

Abstract

Significance testing—especially the paired-permutation test—has played a vital role in developing NLP systems to provide confidence that the difference in performance between two systems (i.e., the test statistic) is not due to luck. However, practitioners rely on Monte Carlo approximation to perform this test due to a lack of a suitable exact algorithm. In this paper, we provide an efficient exact algorithm for the paired-permutation test for a family of structured test statistics. Our algorithm runs in 𝒪(G N (log GN )(log N)) time where N is the dataset size and G is the range of the test statistic. We found that our exact algorithm was 10x faster than the Monte Carlo approximation with 20000 samples on a common dataset
BibTeX
@inproceedings{zmigrod2022exact,
  author = {Ran Zmigrod and Tim Vieira and Ryan Cotterell},
  title = {{Exact Paired-Permutation Testing for Structured Test Statistics}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2022},
  url = {https://openreview.net/forum?id=mWf182ixxX},
}

Loading related content...

Figure