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

• URL: http://arxiv.org/abs/2605.18670v1
• Date: Mon, 18 May 2026 17:12:11 GMT
• Title: Sublinear Risk-Limiting Audits from Direct Ballot Selection and Statistical Ballot Manifests
• Abstract summary: Risk-limiting audits (RLAs) are post-election auditing procedures that rigorously guarantee a specified maximum probability that an incorrect electoral outcome will not be detected.<n>While typical electoral procedures automatically provide rough estimates for batch sizes, even slight inaccuracies invalidate conventional RLAs.<n>We propose two new risk-limiting techniques: A statistical mechanism for ensuring that the batch sizes reported by an untrusted tabulation are, in fact, an accurate manifest and a new class of RLAs called direct ballot selection.
• Score: 47.94589114324381
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Risk-limiting audits (RLAs) are post-election auditing procedures that rigorously guarantee a specified maximum probability that an incorrect electoral outcome will not be detected. Aside from ready access to physical ballots, known RLAs require a software-independent accounting of the sizes of each ballot batch, called a ballot manifest. While typical electoral procedures automatically provide rough estimates for batch sizes, even slight inaccuracies (commensurate with the margin of the contest under audit) completely invalidate conventional RLAs (Lindeman et al., EVT 2012). Thus, establishing a sufficiently accurate manifest often requires handling every ballot and can be the dominant cost of conducting the RLA. We propose two new risk-limiting techniques: 1) A statistical mechanism for ensuring that the batch sizes reported by an untrusted tabulation are, in fact, an accurate manifest; this effectively bootstraps from a rough manifest to an accurate one with sublinear effort. 2) We propose a new class of RLAs called direct ballot selection. This method reverses the traditional comparison procedure and compares uniformly selected ballots against their cast vote records, requiring a new statistical test for identifier duplication but efficiently supporting elections without in order identifiers. These techniques reduce the complexity of RLAs across many elections. Our two main findings are as follows: 1) The time to create a manifest can be drastically reduced with a modest increase in the number of ballots sampled in the audit. At a 3% margin and a large population, there is a reduction in the overall audit time of at least an order of magnitude across methods. 2) Direct ballot selection improves over state-of-the-art polling for small margins. For Connecticut (29th in population) at a 1% margin, it beats Minerva (Security 2022) by 55% in ballot sample complexity.

Related papers

• Doing More With Less: Mismatch-Based Risk-Limiting Audits [52.25213882366808]
  One approach to risk-limiting audits (RLAs) compares randomly selected cast vote records (CVRs) to votes read by human auditors.<n>We investigate whether the total number of mismatches in the full set of CVRs exceeds the minimum number of CVR errors required for the reported outcome to be wrong.
  arXiv  Detail & Related papers  (2025-03-20T12:47:54Z)
• Efficient Lower Bounding of Single Transferable Vote Election Margins [56.12949230611067]
  Single transferable vote (STV) is a system of preferential proportional voting employed in multi-seat elections.<n>The margin of victory, or simply'margin', is the smallest number of ballots that need to be manipulated to alter the set of winners.<n>Lower bounds on the margin can also be used for this purpose, in cases where exact margins are difficult to compute.
  arXiv  Detail & Related papers  (2025-01-24T13:39:23Z)
• Efficient Weighting Schemes for Auditing Instant-Runoff Voting Elections [57.67176250198289]
  AWAIRE involves adaptively weighted averages of test statistics, essentially "learning" an effective set of hypotheses to test. We explore schemes and settings more extensively, to identify and recommend efficient choices for practice. A limitation of the current AWAIRE implementation is its restriction to a small number of candidates.
  arXiv  Detail & Related papers  (2024-02-18T10:13:01Z)
• The Decisive Power of Indecision: Low-Variance Risk-Limiting Audits and Election Contestation via Marginal Mark Recording [51.82772358241505]
  Risk-limiting audits (RLAs) are techniques for verifying the outcomes of large elections. We define new families of audits that improve efficiency and offer advances in statistical power. New audits are enabled by revisiting the standard notion of a cast-vote record so that it can declare multiple possible mark interpretations.
  arXiv  Detail & Related papers  (2024-02-09T16:23:54Z)
• Adaptively Weighted Audits of Instant-Runoff Voting Elections: AWAIRE [61.872917066847855]
  Methods for auditing instant-runoff voting (IRV) elections are either not risk-limiting or require cast vote records (CVRs), the voting system's electronic record of the votes on each ballot. We develop an RLA method that uses adaptively weighted averages of test supermartingales to efficiently audit IRV elections when CVRs are not available.
  arXiv  Detail & Related papers  (2023-07-20T15:55:34Z)
• New Algorithms and Applications for Risk-Limiting Audits [4.375873233252245]
  Risk-limiting audits (RLAs) are a significant tool in increasing confidence in the accuracy of elections. This work suggests a new generic method, called Batchcomp", for converting classical (ballot-level) RLAs into ones that operate on batches. We present an adaptation of ALPHA, an existing RLA method, to a method which applies to censuses.
  arXiv  Detail & Related papers  (2023-05-06T13:34:39Z)
• Ballot-Polling Audits of Instant-Runoff Voting Elections with a Dirichlet-Tree Model [23.14629947453497]
  Instant-runoff voting (IRV) is used in several countries around the world. It requires voters to rank candidates in order of preference, and uses a counting algorithm that is more complex than systems such as first-past-the-post or scoring rules. An even more complex system, the single transferable vote (STV), is used when multiple candidates need to be elected. There is currently no known risk-limiting audit (RLA) method for STV, other than a full manual count of the ballots.
  arXiv  Detail & Related papers  (2022-09-08T15:35:50Z)
• Auditing Ranked Voting Elections with Dirichlet-Tree Models: First Steps [23.14629947453497]
  Ranked voting systems are used in many places around the world. There is no known risk-limiting audit (RLA) method for STV other than a full hand count. We present a new approach to auditing ranked systems that uses a statistical model, a Dirichlet-tree, that can cope with high-dimensional parameters in a computationally efficient manner.
  arXiv  Detail & Related papers  (2022-06-29T13:06:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.