CS Paper Radar

Towards stratified sampling for redistricting plans

Zijian Wang, Gregory J. Herschlag, Joon-Hyeok Yim, Jonathan C. Mattingly, Anna C. Gilbert

cs.CY physics.soc-phmath.PR ·submitted 2026-09-16 14:38 UTC · v1

Abstract

Rapid algorithmic developments have accelerated the sampling of redistricting ensembles (balanced graph partitions), yet evaluating rare events and sampling complex target measures remains a core challenge due to the high-dimensional and combinatorial nature of the phase space. We address a prerequisite for stratified sampling on this space: constructing and diagnosing candidate strata with suitable coverage and overlap. We build a grammar on observed plans by clustering districts into representative ``letters'' and using them to form plan-level ``words.'' A partition of unity over these words gives a soft assignment of plans to strata and allows us to estimate stratum masses and an overlap-induced flux matrix. We demonstrate this computational pipeline using real-world congressional redistricting data from Connecticut and examine how strata learned from one target distribution behave under related distributions. The resulting construction provides a foundation for future stratified sampling on spaces of redistricting plans or balanced graph partitions. We do not implement a complete stratified sampler here; evaluating whether the proposed strata improve sampling efficiency or reduce estimator variance is left for future work.

Closest papers

Nearest neighbours by meaning across the whole index.

District Size Matters: How Seats Per District Shapes Proportionality Under STV

cs.CY physics.soc-ph ·2026-10-19 ·Daryl DeFord, Thomas Ratliff, Ellen Veomett
similarity 0.67
Abstract · 54 pages, 19 figures

We study the impact of utilizing multimember districts and Single Transferable Vote (STV) as the winner selection method on partisan proportionality. We start with detailed case studies of the upper legislative houses of Illinois, New Hampshire, and New Mexico, building ensembles of redistricting maps with mostly 2-member, mostly 3-member, and mostly 4-member districts for each state. These ensembles are constructed using two methods: building from precincts, and merging currently existing single-member districts. We also compare two ballot generation models for each experiment: a modified Bradley-Terry model and a Plackett-Luce model. We find that our ensembles of multimember districts paired with STV have results which are centered closer to partisan proportionality than when single member districts are used. However, the choice of district size affects partisan outcomes enough that this choice could be exploited by a partisan mapmaker to advantage a particular party. The findings are consistent across all combinations of district construction and ballot generation models within a single state. We then expand our study to 41 different states, obtaining consistently similar proportionality results and allowing us to empirically evaluate the two ballot generation models, as implemented in VoteKit, at a national scale.

0.22

Statistical Assessments of Representational Reforms: A Case Study from Los Angeles

cs.CY stat.AP ·2026-08-17 ·Sarah Cannon, Evan T. R. Rosenman
similarity 0.58
Abstract

Electoral reforms -- including changes to district boundaries, electoral rules, and the size of elected bodies -- are a recurrent feature of American state and municipal politics. The representational impact of such reforms is challenging to assess before they are implemented, and even well-intentioned civic reformers are often surprised by the unintended consequences of changes to the political system. We develop a statistical framework for the prospective evaluation of electoral reforms by integrating several modes of analysis: descriptive statistics of the voter file, probabilistic race and ethnicity imputation, ecological inference, and redistricting simulations via ensembles. Together, these tools provide a unified assessment of how proposed reforms affect whose voices are ultimately heard in government. We apply this framework to reforms currently being considered for the Los Angeles City Council, including increasing the number of single-member districts, adopting ranked-choice voting, and introducing multimember districts elected by proportional ranked choice voting. We find that expanding the Council alone is unlikely to substantially improve representation for underrepresented communities. In contrast, eliminating low-turnout primary elections and adopting multimember districts produce larger improvements in representational equity. Our analyses were shared with L.A.'s Charter Reform Commission via public testimony in late 2025. Although motivated by Los Angeles, the framework is broadly applicable to evaluating prospective electoral reforms across American jurisdictions.

0.23

Aggregate Disambiguation Systems

cs.AI stat.ME ·2026-08-31 ·José María Lago, Albert Castellana, Edgars Nemše
similarity 0.58
Abstract

Natural-language tasks can elicit different verdicts from protocol-following evaluators that receive the same declared information. We study aggregate disambiguation systems (ADSs). Given a task and a candidate solution, each evaluator casts a binary vote on whether the solution should be accepted, and the system aggregates the votes of a finite panel. The target is protocol reproducibility relative to an explicitly declared evaluator reference, not semantic truth. We separate fixed finite censuses, probabilistic evaluator populations, and growing-census limits, since their endpoint laws and guarantees are not interchangeable. In the population setting, we use finite samples to estimate how often a finite panel reaches the same decision as the declared evaluator population. We provide a lower confidence bound on the fraction of candidate solutions for which the disagreement probability is at most a chosen tolerance. The calculation accounts separately for sampling candidate solutions and sampling evaluators. The construction permits arbitrary dependence among columns induced by shared evaluator rows and uses exact binomial intervals at the evaluator layer and an exact one-sided binomial inversion at the generator layer. Simulations check the implementation against known population coverages and expose power limitations.

0.27

Tilted Mondrian: Triage and Mitigation of Fine-grained Disparities in Conformal Prediction

cs.LG stat.ML ·2026-10-17 ·Ziang Gao, Pengqi Liu, Archer Yi Yang, Mouloud Belbahri, Jesse C. Cresswell +1 more
similarity 0.57
Abstract

Fairness in conformal prediction is often pursued through Mondrian calibration, which provides finite-sample coverage guarantees separately across groups. These guarantees, however, are coarse: substantial disparities can remain within finer strata. This coarse-to-fine fairness issue raises two questions: how severe can such disparities be, and how can they be mitigated? Aggregate disparities can depend on how groups are distributed across strata. For severity assessment, we introduce propensity standardization to examine the effect of population composition, and show how group composition can induce disagreement between aggregate and finer-stratum comparisons. For mitigation, we develop Tilted Mondrian to improve fairness compared to group-Mondrian at a finer level without additional model training. Tilted Mondrian retains groupwise coverage guarantees and mitigates coverage and prediction set size disparities within finer strata. Finally, we derive a method-agnostic bound that quantifies how much reduction in finer-stratum coverage disparity can be achieved.

0.21

Target-Stratified Fair Range Summaries: Improved Fair $\varepsilon$-Nets and Geometric Hitting Sets

cs.DS cs.DM ·2026-09-17 ·Mingchao Zhou, Lei Zhao, Zhipeng Cai, Zhao Zhang
theory similarity 0.57
Abstract

Compact summaries are a key tool for approximate query processing over large datasets. For range-query workloads, an $\varepsilon$-net provides a small summary that hits every sufficiently large range. However, classical $\varepsilon$-nets only guarantee range validity and do not control the group composition of the selected tuples. As a result, the summary may be range-valid but poorly representative, which can propagate imbalance to downstream query results. Motivated by recent work on fair $\varepsilon$-nets and fair geometric hitting sets \cite{dehghankar2025fair}, we study fairness-aware range summaries under prescribed target group ratios. Different from previous sample-and-repair approach, we propose a target-stratified sampling method. For demographic parity (in which the ratio of fairness is determined by group proportion), our sample size is $O(A_{\varepsilon})$, coinciding with the standard $\varepsilon$-net bound, improving previous bound of $O\!\left(A_\varepsilon\log\frac{k}{\varphi}\right)$. For custom-ratio targets (in which the ratio of fairness is determined by manually defined proportion), our sample size is $O(A_Γ)$, where $Γ$ is a parameter measuring the gap between the customized ratio and the demographic parity; we prove that this dependence on $Γ$ is unavoidable, with a worst-case lower bound of $Ω(Γ/\varepsilon)$. Using our target-stratified sampling method, we could improve the previous approximation ratio for the fair geometric hitting set problem by a logarithmic factor, and making use of this result, we could in turn improve the size of custom-ratio fair $\varepsilon$-net. Experiments on real and synthetic datasets demonstrate that our method constructs smaller fair summaries than existing approaches, scales to large datasets and fine-grained group constraints, and improves downstream range query processing.

0.19

CLIPPER: Replayable Shortlisted Optimization for Repeated Spatial Coverage Planning

cs.RO cs.CGcs.DS ·2026-08-27 ·Julian Teusch, Jörg Philipp Müller, Monika Sester
published similarity 0.54
Abstract · Accepted at ACM SIGSPATIAL 2026. 6 pages, 2 figures, 2 tables

Operational requirements developed with the City of Braunschweig frame municipal micromobility planning under geofenced exclusions, mandatory retained sites, spacing rules, and area-level caps. Each policy edit requires a new feasible plan; full-set greedy takes tens of seconds per alternative at city scale. We present CLIPPER (Constraint-exact Low-latency Iterative Planning with Pooled Evaluation and Replay). It forms bounded candidate pools but recomputes exact current gains and checks every active constraint before selection. Coverage from each candidate alone sets the initial order. Offline full-set scans measure gains omitted by the pool; online, a conservative bound triggers expansion or audit. CLIPPER-F gives each proposal group the same number of candidate slots. Across Braunschweig, Munich, and Berlin, its mean coverage over complete chains stays within 0.245 percentage points of full-set greedy under the same policy, with 13.6--28.9 times lower mean rollout time. CLIPPER-A instead distributes one shared candidate budget across the groups. Under its coverage-prioritized policy, it uses 9--15% of full-set greedy's rollout time under the same policy, with mean gaps of 1.82 percentage points in Braunschweig, 0.12 in Munich, and 0.27 in Berlin. Together, CLIPPER enables rapid, replayable comparison of recorded city-scale planning states while enforcing every encoded model constraint.

0.70

Learning Stratified Policies for Inference-Time Objectives

cs.LG cs.AI ·2026-11-17 ·Mridul Mahajan, Xuezhou Zhang, Aldo Pacchiano
similarity 0.54
Abstract

Inference-time scaling improves the performance of large language models by sampling multiple responses and evaluating their collective utility. However, many existing approaches obtain these samples by repeatedly sampling from a single policy. In this work, we study if the sample budget at inference time can instead be allocated across a population of policies. We introduce stratified policies, where each of $k$ learned policies contributes one response to a $k$-sample inference-time objective. We realize this policy population using separate LoRA adapters on a shared language model backbone and optimize it for pass@$k$. We theoretically motivate the approach by analyzing the linear setting; a population of LoRAs can achieve zero best-of-$k$ approximation error in settings where every single LoRA has strictly positive prediction error. Empirically, we demonstrate that stratified policies consistently improve pass@$k$ over a single-policy baseline across multiple reasoning tasks. Overall, our results highlight how distributing samples across complementary policies can be a more effective use of sample budget than repeated i.i.d. sampling from a single policy at inference time.

0.16

Chopthin-Consensus Power Sampling: A Diversity-Preserving Approach to LLM Decoding

cs.CL cs.AIstat.ML ·2026-09-10 ·Minoo Ahmadi, Seyedarmin Azizi, Erfan Baghaei Potraghloo, Mehdi Kamal, Massoud Pedram
theorycode/data similarity 0.53
Abstract · Accepted at the COLM 2026 Workshop on Efficient Reasoning

Inference-time power sampling via Sequential Monte Carlo (SMC) can substantially improve large language model (LLM) reasoning without requiring post-training. However, many existing SMC approaches rely on equal-weight resampling, which can aggressively prune low-weight trajectories, discarding potentially correct reasoning paths and degrading the genealogical diversity of the search space. To address this, we introduce Chopthin-Consensus Power Sampling (CCPS). Our method applies the Chopthin resampler to LLM decoding: rather than equalizing weights and forcing unnecessary particle duplication, it enforces an upper bound on the ratio between the largest and smallest weights and carries the unequal weights forward. This targeted intervention preserves a richer set of distinct reasoning paths, keeps the weighted SMC approximation unchanged in conditional expectation, and guarantees a lower bound on the post-resampling effective sample size (ESS). To fully exploit this enriched population, we employ a semantic-majority selection mechanism that merges token-identical final trajectories, clusters semantically equivalent answers, and returns the answer supported by the largest number of distinct trajectories. Evaluating across three open-weight models and five reasoning benchmarks, we show that Chopthin increases oracle coverage in 13 of 15 settings. Combined with semantic-majority selection, CCPS matches or exceeds the final-answer accuracy of the Power-SMC baseline in 14 of 15 settings, delivering absolute gains of up to 10.6 percentage points. These findings demonstrate that diversity-preserving resampling and diversity-aware selection are complementary mechanisms for training-free LLM reasoning. Code is available at github.com/MinooAhmadii/chopthin-consensus-power-sampling.

0.35