# Exact Paired-Permutation Testing for Structured Test Statistics

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 22 references that are in the map.
- First posted on arXiv 3 May 2022.

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

- [Stanza: A Python Natural Language Processing Toolkit for Many Human Languages](https://mlsanity.com/paper/2003.07082/) (2020)
- [A Statistical Analysis of Summarization Evaluation Metrics using Resampling Methods](https://mlsanity.com/paper/2104.00054/) (2021)
- [Better than Average: Paired Evaluation of NLP Systems](https://mlsanity.com/paper/2110.10746/) (2021)

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

- [Do Androids Know They're Only Dreaming of Electric Sheep?](https://mlsanity.com/paper/2312.17249/) (2023)
- [Stronger Random Baselines for In-Context Learning](https://mlsanity.com/paper/2404.13020/) (2024)
- [Translate Smart, not Hard: Cascaded Translation Systems with Quality-Aware Deferral](https://mlsanity.com/paper/2502.12701/) (2025)
- [A Framework for Bidirectional Decoding: Case Study in Morphological Inflection](https://mlsanity.com/paper/2305.12580/) (2023)
- [Delving into Multilingual Ethical Bias: The MSQAD with Statistical Hypothesis Tests for Large Language Models](https://mlsanity.com/paper/2505.19121/) (2025)
- [Accurate and Efficient Statistical Testing for Word Semantic Breadth](https://mlsanity.com/paper/2605.08048/) (2026)

## Abstract (arXiv)

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 O(GN (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.