A compact record of missing data, near its counting floor
How many times fewer payload bits the Elias–Fano record of missing positions needed (geometric mean; the mark is where the two forms are equal)
Sparse test cases, against the bitmap or the ranges: 2.654x
All test cases, against the ranges: 2.364x
All test cases, against the bitmap: 1.792x
One dense test case, against the bitmap: 0.996x
Payload bits only, counted on the lab’s own test cases; headers are not counted, and below the mark the bitmap was smaller.
In the lab's bit accounting, a standard compact code for the positions of missing data needed fewer bits than a dense bitmap or a list of ranges on its sparse test cases, and slightly more than the bitmap on its dense ones
What it does not claim
It counts bits on paper, for the lab's own test cases; no receiver, card or protocol implementation was run. The advantage holds only when few positions are missing; with many missing, a plain bitmap is as small or smaller. The code is not new, and its closeness to the floor is a known property of it: nothing here is a new lower bound on what any acknowledgment form needs.
The limits, in the lab’s words:
The certificate ships dominance_foil — a theorem PROVING the unconditional claim FALSE — plus a worked counter-case (W=64, g=32) where the dense competitor wins 64 bits to 128.
Bit counts were NOT independently re-derived this pass beyond the axiom audit.
Still open, per the grader: the accounting is payload-only and header-inclusive deployed accounting has not been done, so "the deployed sparse-gap encoder" has been narrowed to "the modeled Elias-Fano sparse-gap payload".
Excerpts, word for word from the published file, where the full text can be read.
When data arrives out of order, a receiver tells the sender which pieces are still missing. Two common ways to write that down are a dense bitmap, one bit for every position in the window, and a list of ranges, as the acknowledgment frames of QUIC use. When only a few pieces are missing, a third way can be shorter: list the missing positions with Elias–Fano coding, a long-published compact code for sorted numbers. The lab counted the bits each form needs on test cases of its own, and checked in Lean how close the Elias–Fano form comes to the fewest bits any encoding could use.
What it shows
In this model: the payload bits each form needs to record which positions in a window are still missing, counted by the lab's accounting code on test cases committed with that code. Headers are not counted, and nothing was sent over a network.
On the three test cases where few positions are missing, the Elias–Fano form needed fewer bits than the dense bitmap by a geometric mean of 2.654x, and fewer than the list of ranges by the same factor. Over all of the lab's test cases, including two where many positions are missing, the geometric means are 1.792x against the bitmap and 2.364x against the ranges.
Where it loses
On the two dense test cases the bitmap was slightly smaller: the ratio was 0.996x on one of them, and the claim below gives the other. The lab's certificate also carries a worked case, quoted on this page with the limits, in which the bitmap needs half the bits. Which form wins depends on how many positions are missing.
The counting floor
To tell apart every possible set of missing positions, an encoding needs a minimum number of bits, set by counting those sets. A Lean theorem in the lab's code bounds the Elias–Fano payload to within 3 bits per missing position of that floor, for every window size and number of gaps. Elias showed long ago that this code comes closer still, as the survey cited below explains, so the Lean proof re-checks a looser form of a known property by machine.
Why it matters, and to whom
For teams that design transport engines on network cards, the record of missing data is part of what each connection costs, in memory on the card and in bits on the wire. On the lab's sparse test cases, writing down only the few missing positions made that record smaller than a bitmap by the factor above, in payload bits. When losses are common, a bitmap is as small or smaller, and the choice should follow the loss pattern a deployment actually sees.
Why now
Transports for AI clusters spread one transfer over many network paths, as the Falcon announcement cited below describes for Google's hardware transport. Data then arrives out of order more often, and each receiver keeps a longer record of what is missing, so the size of that record matters more than it did when one path carried each transfer.
How it was checked
The lab's code counts the bits of each form on each committed test case and writes the ratios into a certificate. A Lean file in the lab's code holds the bound against the counting floor, and the same certificate carries a theorem showing that the advantage over the bitmap does not hold without a condition on how sparse the gaps are. As the lab's limits quoted on this page say, the bit counts were not counted again independently.
How to reproduce
The measured results name the lab's command, which builds its checker and regenerates the certificate, and the commit it was read at. Anyone with access to the lab's code can rerun it. The lab's code is not public yet. The lab's claim is published here word for word, and the sentences of its limits quoted on this page are published with their place in the lab's file. Each is listed with its hash in the site's receipt manifest.
The counting floor, and the bound
In words: there are W choose g ways to pick g missing positions out of W, so an encoding E that tells every such set apart needs at least the base-two logarithm of that number, in bits. That is the counting floor, and it is classical. The second line is the bound the lab's Lean file proves for the Elias–Fano payload, for every W and g: at most the floor plus three bits for each gap. It is a looser form of a known property of this code, checked by machine; it is not a new lower bound.
The result, in the lab’s exact words
Read it with this condition: "our encoder" is the lab's implementation of Elias–Fano coding, a published code cited below, applied to the positions of missing data; the code is not the lab's own. "Falcon's dense bitmap" and "QUIC SACK ranges" are the lab's bit-count models of a one-bit-per-position bitmap, the form the lab attributes to Falcon, Google's hardware transport, and of the acknowledgment ranges of QUIC. No Falcon or QUIC implementation was run, and only payload bits are counted, not headers.
The modeled Elias-Fano sparse-gap payload sits within 3 bits per gap of the machine-checked counting floor floor(log2 C(W,g)), proven in Lean for all W and g. On the five committed fixtures the payload accounting gives geometric means of 1.792x against Falcon's dense bitmap and 2.364x against QUIC SACK ranges -- but those five include two DENSE-regime fixtures on which our encoder is slightly WORSE than the dense bitmap (0.996x and 0.992x). Over the three SPARSE-regime fixtures alone the geometric means are 2.654x and 2.654x. The 1.792x figure is a five-fixture number, not a sparse-fixture one.
Quoted word for word from the lab’s published claim and limits.
Prior art
- Sebastiano Vigna, "Quasi-Succinct Indices" (arXiv, 2012; Web Search and Data Mining conference, 2013): describes Elias–Fano coding and cites Elias's proof that it comes within half a bit per element of the optimal representation
- Iyengar and Thomson (editors), "QUIC: A UDP-Based Multiplexed and Secure Transport" (IETF RFC 9000, 2021): the acknowledgment frames whose ranges are one of the two forms compared
- Lenoski and Dukkipati, "Google opens Falcon, a reliable low-latency hardware transport, to the ecosystem" (Google Cloud blog, 2023): the hardware transport whose acknowledgment form the lab models as a dense bitmap; the post itself does not describe the bitmap
Evidence
- The measured results behind this page, read from the lab’s own files at a named version.
- The lab’s current claim and limits, word for word.
- Every file this site publishes.