# Kendall Tau Sequence Distance: Extending Kendall Tau from Ranks to Sequences

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 May 2019.

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

- [Premise Order Matters in Reasoning with Large Language Models](https://mlsanity.com/paper/2402.08939/) (2024)
- [Cache-Craft: Managing Chunk-Caches for Efficient Retrieval-Augmented Generation](https://mlsanity.com/paper/2502.15734/) (2025)
- [Order Matters: Investigate the Position Bias in Multi-constraint Instruction Following](https://mlsanity.com/paper/2502.17204/) (2025)
- [Order Matters! An Empirical Study on Large Language Models' Input Order Bias in Software Fault Localization](https://mlsanity.com/paper/2412.18750/) (2024)
- [Multi-Source Survival Domain Adaptation](https://mlsanity.com/paper/2212.00424/) (2022)
- [AEMA: Verifiable Evaluation Framework for Trustworthy and Controlled Agentic LLM Systems](https://mlsanity.com/paper/2601.11903/) (2026)
- [Synchronizing Process Model and Event Abstraction for Grounded Process Intelligence (Extended Version)](https://mlsanity.com/paper/2505.23536/) (2025)

## Abstract (arXiv)

An edit distance is a measure of the minimum cost sequence of edit operations to transform one structure into another. Edit distance is most commonly encountered within the context of strings, where Wagner and Fischer's string edit distance is perhaps the most well-known. However, edit distance is not limited to strings. For example, there are several edit distance measures for permutations, including Wagner and Fischer's string edit distance since a permutation is a special case of a string. However, another edit distance for permutations is Kendall tau distance, which is the number of pairwise element inversions. On permutations, Kendall tau distance is equivalent to an edit distance with adjacent swap as the edit operation. A permutation is often used to represent a total ranking over a set of elements. There exist multiple extensions of Kendall tau distance from total rankings (permutations) to partial rankings (i.e., where multiple elements may have the same rank), but none of these are suitable for computing distance between sequences. We set out to explore extending Kendall tau distance in a different direction, namely from the special case of permutations to the more general case of strings or sequences of elements from some finite alphabet. We name our distance metric Kendall tau sequence distance, and define it as the minimum number of adjacent swaps necessary to transform one sequence into the other. We provide two O(n lg n) algorithms for computing it, and experimentally compare their relative performance. We also provide reference implementations of both algorithms in an open source Java library.