The Power of Two-Choice Linear ProbingAmir Azarmehr, Michael A. Bender, William Kuszmaul, Rose SilverFOCS 2026 · arXiv 2610.00688 · tested 2 days after release
Read paper

Does two-choice linear probing hold up?

Mostly, yes.

At 99% full, greedy two-choice lookup averaged 5.797400 slot probes, versus 51.024915 for the ordered one-choice control across five seeds. That is 8.8× fewer probes for successful lookup in this test; it does not establish a CPU speedup.

2 confirmed3 fine print1 checking1 withdrawn

The idea, in 6 seconds

1 spot per car0avg walk
2 spots per car0avg walk
Filling up0% full
MEASURED RESULT · 99% FULL · FIVE SEEDS51.024915 → 5.797400SUCCESSFUL LOOKUP SLOT PROBES

The verdicts

Tap any card

Watch the gap open up

Mean successful-lookup probes, n = 2²⁰, 5 seeds. Shaded = min–max.

Fill it up yourself

Mean probes, 1,048,576 slots, 5 runs. Bar length is log-scaled.

99%

Number = how many spots the computer checks. Fewer is faster.

Lab notebook

Expert view

n = 2²⁰ unless noted · 5 seeds · 1 probe = 1 slot read

Fig. 1 Scaling with 1/ε

Fig. 2 Calibration vs Knuth (1962)

Baseline (unordered LP) means vs asymptotic ½(1+ε⁻¹) and ½(1+ε⁻²). Whiskers: seed min–max. Points on y = x mean the harness measures correctly.

Fig. 3 Seed-to-seed spread, α = 0.99

Each dot is one seed's mean successful probes; bar = mean. Label = coefficient of variation across seeds.

Fig. 4 Blind replication

Rust, 3 seedsPython (blind), 30 seeds, min–max
Both at n = 2¹⁶. Python written from the paper text only, without reading the Rust code.

Fig. 5 Local growth exponent

Least-squares slope of log probes vs log ε⁻¹ over ε ∈ [0.01, 0.1]. Theory: single choice Θ(ε⁻¹) → 1. Greedy O(ε⁻ᶜ), c unknown (paper conjectures c > ½). Non-greedy O(log ε⁻¹) → slope tends to 0 only asymptotically.

Table 1 Results at α = 0.99

cargo run -p bench --release -- \
  --tables baseline,ordered1,greedy2,nongreedy2,evict2,evictheur \
  --seeds 1,2,3,4,5 --output results/full_probes.csv

How we checked

6 of 7 done · last one is yours

Case 001 / findings / 2 October 2026

What the measurements show

Answer: Our independent implementation supports the paper's central two-choice result at the tested sizes. At 99% load in a table of 1,048,576 slots, the ordered one-choice control took 51.024915 probes per successful lookup, while greedy two-choice took 5.797400, averaged equally across five seeds. The ratio is 8.8013, shown elsewhere on this page as 8.8×. For absent keys the corresponding means were 51.416321 and 10.252075 probes. A probe is one table-slot read, so these are operation counts, not elapsed time.

The original paper, The Power of Two-Choice Linear Probing, is by Amir Azarmehr, Michael A. Bender, William Kuszmaul, and Rose Silver. The ideas and theorems are theirs. Kael Research built and measured the implementations independently on 2 October 2026; the authors had not reviewed this report at publication.

Five-seed means at 99% load; 1,048,576 slots. Full precision in the CSV.
ImplementationSuccessful probesUnsuccessful probesMean max successful
Classic baseline52.1010745249.26341525888.0
Ordered one-choice51.02491551.416321329.0
Greedy two-choice5.79740010.25207522.4
Non-greedy two-choice26.66522236.695984111.0
Eviction construction variant13.61812723.147021118.2
Our eviction heuristic6.7772839.62569629.6

Download the complete benchmark CSV (all loads, seeds, methods and metrics). The two-choice result was also rebuilt independently in Python from the paper text: at 99% load and 65,536 slots, greedy two-choice averaged 5.725 successful and 10.163 unsuccessful probes across 30 seeds. The scale and random streams differ, so these are agreement in behavior, not identical experiments.

How we tested

We listed the testable claims before running benchmarks, implemented the paper's methods and a fair ordered one-choice control, then checked correctness before speed. The primary benchmark used 1,048,576 slots, loads from 50% through 99%, and five seeds. Each run verified all inserted keys and 10,000 absent keys. We calibrated classic linear probing against Knuth's known formulas and repeated the core comparison in a blind Python implementation using 30 independent seeds at 65,536 slots. This makes a second implementation error less likely, but cannot prove the paper's asymptotic theorems.

The measured non-greedy method took 26.665222 successful probes at 99% load. Its theorem gives better asymptotic growth as the free fraction approaches zero; the finite table we could run did not reach that regime. The paper's proven eviction scheme has a very high switch-on threshold. Our evict2 is a construction variant and does not implement every Section 7 lookup rule. Our separate practical eviction heuristic averaged 6.777283 successful probes at 99% load; this is our heuristic, not a measured performance claim for the paper's exact proven construction.

The full-table 2.2 figure

At 100% load with 100,000 slots, an offline ordered-table rebuild averaged 2.1590 probes for present keys and 4.7909 for absent keys across three seeds. An optional one-bit-per-home bitmap changed those to 2.0801 and 3.8833 at its hit-minimizing setting. The offline result reaches the paper's approximate 2.2 figure for successful lookups only. It says nothing about an unknown hit/miss mixture or how cheaply an online insertion algorithm could construct the same layout. The 2.1590 result is pending a second independent review.

Download the selected round-two per-seed CSV. The online dart heuristic's comparable seed reported 11.05 successful and 14.16 unsuccessful probes. Comparing that to the offline rebuild isolates a possible benefit of global rearrangement, but omits its construction cost.

Timing limit: the first wall-clock readings came from a busy laptop shared by other jobs. At 99% load, the preliminary successful-lookup times were 276 ns for classic probing, 481 ns for ordered one-choice, and 306 ns for greedy two-choice. These are preliminary timings and cannot support a CPU-speed verdict. We are re-timing them on a quiet machine.

Limitations and corrections

The experiments cover finite capacities, specific pseudo-random hash streams, and chosen implementations. Theory concerns expectations under ideal random hashing as the free fraction shrinks. Five benchmark seeds help show repeatability, but cannot establish universal performance or every tail behavior. Probe counts omit metadata reads, cache effects, construction work and some insertion costs. The non-greedy crossover estimate in the interactive card is an extrapolation with substantial uncertainty, not an observed threshold.

An agent initially claimed a bug in the paper's Section 7 query rule. Review found it had incorrectly carried over a free-slot stopping rule from the greedy method; the default rule in the paper does not stop there. A literal check found every inserted key. We withdrew the claim before publication and record it in the public corrections log. One possible editorial typo remains, but we make no bug claim. Read how we test papers and browse all cases.

Got a paper? We'll test it.

Paper: Amir Azarmehr, Michael A. Bender, William Kuszmaul, Rose Silver, “The Power of Two-Choice Linear Probing”, FOCS 2026 (PDF). All credit for the ideas belongs to the authors; the implementations and measurements here are ours. Prototype, run on 2 Oct 2026, not yet reviewed by the authors.