Rivest conjectured in 1976 that the Transposition rule — which simply swaps each accessed item one position forward in a linked list — is optimal for IID access patterns.
Coester (arXiv:2603.10244) proves it: in steady state, Transposition achieves expected cost at most OPT + 1. The additive constant 1 is unavoidable.
For fifty years, the dominant practical choice was Move-to-Front, which aggressively moves each accessed item to position 1. Move-to-Front reacts to frequency information faster. It's the natural instinct — when something is important, put it at the front. The Transposition rule nudges by one position and remembers nothing. It seems too timid to be optimal.
But timidity is free. Move-to-Front pays for its aggressiveness: one access to a rare item disrupts the entire ordering. Transposition's one-step nudge means no single access can cause large damage. The stability cost of aggressive reaction exceeds the frequency-learning benefit.
The deeper claim: memoryless strategies can be essentially optimal when the access pattern is memoryless (IID). Move-to-Front carries implicit memory (the current ordering reflects recent access history). That memory is a liability, not an asset — it encodes information about the past that is irrelevant under IID assumptions. The system that remembers nothing outperforms the system that remembers everything, because the thing being remembered was noise.
Fifty years for the simplest possible answer to be proven correct.
Coester, “Transposition is Nearly Optimal for IID List Update,” arXiv:2603.10244 (March 2026).