💻 computer science

Sublinear Risk-Limiting Audits from Direct Ballot Selection and Statistical Ballot Manifests

This paper introduces two novel risk-limiting audit techniques—a statistical method for verifying ballot manifests with sublinear effort and a direct ballot selection approach—that significantly reduce the time and sample complexity required to audit elections, particularly those with narrow margins.

Original authors: Benjamin Fuller, Abigail Harrison, Alexander Russell

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Benjamin Fuller, Abigail Harrison, Alexander Russell

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine an election is like a massive, chaotic library where millions of people have just checked out books (cast their votes). The library's computer system (the tabulator) prints out a list saying who checked out what. But how do we know the computer didn't make a mistake, or worse, get hacked?

This is where Risk-Limiting Audits (RLAs) come in. Think of an RLA as a "spot check" that guarantees, with high statistical confidence, that the election winner is correct. If the computer is lying, the spot check is almost guaranteed to catch it.

However, doing these spot checks has two huge, expensive problems that this paper solves:

The "Inventory List" Problem: To check the books, you need a perfect list of how many books are in every single box (batch). Making this list perfectly usually means counting every single book by hand, which defeats the purpose of a quick spot check.
The "Shuffled Deck" Problem: In many modern voting machines, the order of the physical ballots is intentionally scrambled to protect voter privacy. This makes it incredibly hard to find a specific book on the shelf just because the computer list says "Book #4,502."

The authors propose two new "magic tricks" to fix these problems without needing to count every single ballot.

1. The "Weighing Scale" Trick (Statistical Manifests)

The Problem: Traditionally, to trust the inventory list (the "manifest"), you had to count every ballot in every box. If the list said a box had 100 ballots, you had to count 100 to be sure. If you were off by even a tiny bit, the whole audit could be thrown out.

The Solution: The authors suggest using a "rough estimate" first, like weighing a box of books. You know a box of 100 books weighs roughly 10 pounds. You don't need to count them to know it's roughly 100.

The Metaphor: Imagine you have 1,000 boxes of books. Instead of opening every box to count, you weigh them all. You get a "coarse" list that is 90% accurate.
The Magic: The authors created a statistical test that uses this "coarse" list to verify the computer's "perfect" list. They randomly pick a few boxes, weigh them, and then actually count the books inside just those few. If the count matches the computer's claim within a tiny margin of error, the test "bootstraps" (lifts) the rough estimate into a trusted, high-accuracy list.
The Result: You don't have to count every ballot to get a trusted list. You only count a small fraction. For a huge state like California, this cuts the time to prepare the audit list by a factor of 400.

2. The "Reverse Search" Trick (Direct Ballot Selection)

The Problem: Usually, an audit works like this: The computer says, "Check the ballot with ID #999." The auditor then has to hunt through a messy bin of thousands of shuffled ballots to find the one with ID #999. This "search" is slow and expensive.

The Solution: The authors flip the script. Instead of finding a specific ballot based on a computer ID, they just grab a random physical ballot from a box, read its ID, and then ask the computer, "What did you say this ballot voted for?"

The Metaphor: Instead of looking for a specific needle in a haystack, you just grab a handful of hay, look at the needles you found, and check if they match the list.
The Catch: If the computer is lying and has "fake" IDs (duplicate numbers) on its list that don't exist on any real ballot, this method could be tricked.
The Fix: The authors added a second statistical test to check for "fake needles." They count how often they see the same ID twice in their random grab. If duplicates are rare (which they should be), the audit is safe.
The Result: This method is much faster for small election margins (close races). For a close race in Connecticut, this method is 55% faster than the current best methods because it skips the slow "search" step entirely.

The Big Picture: Why This Matters

The paper claims that by combining these two tricks, we can audit elections much faster and cheaper, even in huge states with millions of voters.

Speed: In California, doing a full audit used to take thousands of hours just to make the inventory list. With these new methods, that time is slashed dramatically.
Efficiency: For close races (where the winner is decided by a tiny fraction of a percent), the old methods required checking so many ballots they became impractical. The new "Direct Ballot Selection" method handles these close races much better.
Flexibility: These methods work whether the ballots are in neat rows or messy, shuffled piles.

In short: The authors found a way to trust a "rough guess" of the inventory and a "random grab" of ballots, using clever math to prove that these shortcuts are just as safe as the old, slow, "count-everything" methods. This makes verifying election results faster, cheaper, and more practical for everyone.

Technical Summary: Sublinear Risk-Limiting Audits from Direct Ballot Selection and Statistical Ballot Manifests

1. Problem Statement

Risk-limiting audits (RLAs) are post-election procedures designed to provide rigorous statistical guarantees that an incorrect electoral outcome will be detected with a probability no greater than a pre-specified risk limit ( $\alpha$ ). While existing RLAs offer strong security guarantees, they face two critical bottlenecks that limit their efficiency and applicability across diverse election architectures:

The Ballot Manifest Bottleneck: Conventional RLAs require a "ballot manifest"—an accurate, software-independent accounting of the size of every physical batch of ballots. While rough estimates (e.g., via weighing) are easy to obtain, RLAs require high accuracy (errors $\delta \ll \mu$ , where $\mu$ is the election margin). Achieving this accuracy typically requires a manual hand-count of every ballot to create the manifest. This process scales linearly with the total number of ballots ( $O(N)$ ), often dominating the total audit time and negating the efficiency gains of statistical sampling.
The Indexing Bottleneck in Ballot Comparison: The most sample-efficient RLA method is "ballot comparison," which matches a randomly selected Cast Vote Record (CVR) to its physical ballot. However, this requires efficiently locating a specific physical ballot based on an identifier. In modern election architectures using voter-facing tabulators, ballots are intentionally randomized to preserve voter privacy, breaking the link between the order of CVRs and the physical order of ballots. Locating a specific ballot then requires a linear search through the batch (costly) or re-tabulation (costly), forcing jurisdictions to revert to less efficient methods like "ballot polling" or "batch comparison."

2. Methodology

The authors propose two novel techniques to address these bottlenecks, enabling sublinear audit efficiency across a wider spectrum of election configurations.

A. Statistical Accuracy Testing for Ballot Manifests

Instead of requiring a full hand-count to establish a manifest, the authors propose a statistical "bootstrapping" mechanism.

Coarse Manifest: Auditors start with a "coarse" manifest obtained via low-effort bulk methods (e.g., weighing), which provides batch sizes accurate to within a large factor $\Delta$ (e.g., 10%).
Statistical Verification: The auditor uses the coarse manifest to sample batches with probability proportional to their reported (tabulated) sizes. For each sampled batch, the auditor performs a precise hand-count to verify the true size.
Certification: A statistical test determines if the tabulated sizes are sufficiently close to the true sizes for the vast majority of the ballot population. If the test passes, the coarse manifest is "upgraded" to a statistically guaranteed, high-accuracy manifest without counting every ballot. This reduces the cost of manifest creation from $O(N)$ to a sublinear function of $N$ .

B. Direct Ballot Selection (DBS)

For election architectures where ballots lack in-order identifiers (preventing standard ballot comparison), the authors propose "Direct Ballot Selection."

Reversed Procedure: Unlike standard comparison audits (which pick a CVR and find the ballot), DBS picks a physical ballot uniformly at random from a batch, reads its imprinted identifier, and compares it against the corresponding CVR.
Duplicate Detection Challenge: This reversal introduces a new risk: an adversary could manipulate the CVR table by including identifiers that do not correspond to any physical ballot (or duplicating identifiers), thereby evading detection.
Statistical Solution: The authors introduce a new statistical test for identifier uniqueness. By sampling ballots and checking for duplicate or missing identifiers, the audit can bound the "excess identifier multiplicity rate." If duplicates are sufficiently rare, the audit maintains its risk limit.
Complexity: The sample complexity of DBS is asymptotically $O\left(\frac{\log(1/\alpha)}{\mu}\right) + O\left(\sqrt{\frac{N \log(1/\alpha)}{\mu}}\right)$ . The second term (uniqueness testing) scales with $\sqrt{N}$ , derived from the "birthday paradox," which is significantly more efficient than the linear search required by traditional methods in these architectures.

3. Key Contributions

Statistical Manifest Bootstrapping: A method to transform a low-accuracy, coarse manifest into a high-accuracy, statistically certified manifest with sublinear effort. This eliminates the need for exhaustive hand-counting to establish the manifest.
Direct Ballot Selection (DBS): A new class of RLAs that reverses the standard comparison logic to accommodate voter-facing tabulators with randomized ballot orders. This method avoids linear searches and re-tabulation.
Duplicate Identifier Testing: A novel statistical test integrated into the audit to detect and bound the risk of identifier duplication or omission, ensuring the risk limit holds even when sampling physical ballots directly.
Unified Framework: The integration of these techniques allows for a flexible audit strategy where the choice of method (polling, comparison, or DBS) can be made after the election based on the observed margin, rather than requiring pre-election infrastructure decisions.

4. Results

The authors evaluated their techniques using simulations based on US election data (including states like California, Florida, Georgia, and Connecticut) and various margin sizes.

Manifest Efficiency:
- For a 3% margin in California (16M ballots), using a statistically accurate manifest reduced the total audit time by a factor of 400 for comparison audits and 20 for polling audits compared to creating a full manual manifest.
- For Direct Ballot Selection, the reduction was a factor of 8, as the method still depends on $N$ (though reduced to $\sqrt{N}$ ) for uniqueness testing, whereas comparison/polling depend linearly on $N$ for manifest creation.
Sample Complexity and Time:
- Small Margins: For a 1% margin in Connecticut, Direct Ballot Selection reduced the required ballot sample size by 55% compared to state-of-the-art polling methods (Minerva/Providence).
- Congressional Districts: For margins between 0.5% and 1%, DBS improved upon polling by over 75% in sample complexity.
- Scalability: The techniques allow the audit time to scale with the margin $\mu$ rather than being dominated by the fixed cost of manifest creation. For example, in a 2% margin race in Georgia, audit time dropped from 4,000 hours to 1,200 hours by using a statistical manifest.

5. Significance and Claims

The paper claims that these techniques provide a "striking reduction in the complexity of RLAs across a wide swath of election configurations and margins."

Sublinear Efficiency: The primary significance is achieving sublinear efficiency in the total audit effort. By decoupling the need for a perfect manifest from the need for a full hand-count, and by enabling efficient comparison audits in randomized environments, the authors argue that RLAs can be practically deployed in large-scale elections without prohibitive time costs.
Software Independence: The methods maintain the core RLA property of software independence. The statistical tests for manifest accuracy and identifier uniqueness rely on physical ballot counts and simple checks, requiring no trust in the tabulation software's internal logic.
Practical Applicability: The authors emphasize that these methods can be immediately incorporated into existing stratified RLA frameworks. Jurisdictions can dynamically choose the most efficient method (polling, comparison, or DBS) based on the specific margin of the contest, optimizing resource allocation without sacrificing security guarantees.

The paper concludes that while asymptotic statements provide intuition, the explicit numerical results demonstrate that these techniques make high-assurance auditing feasible for large-population jurisdictions and tight margins where previous methods were either too slow (due to manifest creation) or too sample-intensive (due to polling inefficiencies).