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

Risk-limiting audits (RLAs) rigorously guarantee a specified maximum probability that an incorrect electoral outcome will not be detected. Efficient RLA methods require a software-independent count of the ballots in each batch, called a ballot manifest. While electoral procedures can efficiently provide rough estimates for batch sizes, even slight inaccuracies can invalidate conventional RLAs (Lindeman et al., EVT 2012). Thus, establishing a sufficiently accurate manifest often requires handling every ballot in the election and can dominate the cost of conducting an RLA. We propose two new risk-limiting techniques. The first is a statistical test that checks a trusted, coarse manifest against an untrusted, tabulator-supplied manifest to certify that the aggregate error is small; this bounds both the error in the reported ballot total and the distortion of the ballot-sampling distribution. The second is a new approach for election architectures that do not efficiently index ballots by identifier, as is typical of voter-facing tabulators. We call this approach direct ballot selection: it reverses the traditional comparison procedure by selecting physical ballots uniformly and comparing them to their corresponding cast vote records. This method also incorporates a new statistical test to check for identifier duplication. These techniques reduce the effort required to conduct RLAs. Our two main findings are: 1) Manifest creation time can be reduced, for California at a 3% margin, our model indicates that the overall audit time for comparison, polling, and direct selection audits is reduced by factors of approximately 438, 27, and 10, respectively and 2) Direct ballot selection improves over state-of-the-art polling for small margins. For Connecticut at a 1% margin, it requires 55% fewer ballots than the Minerva (Security 2021) and Providence (Security 2023) ballot polling methods.