CS Paper Radar

Aggregate Disambiguation Systems

José María Lago, Albert Castellana, Edgars Nemše

cs.AI stat.ME ·submitted 2026-08-31 13:55 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Learning Stratified Policies for Inference-Time Objectives

cs.LG cs.AI ·2026-11-17 ·Mridul Mahajan, Xuezhou Zhang, Aldo Pacchiano
similarity 0.61
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

A Model of Diverse Sampling from Language Models

cs.LG cs.AIcs.CLcs.FL+1 ·2026-11-18 ·Manuel Prada-Corral, Yahya Emara, Timothy J. O'Donnell, Ryan Cotterell, Tim Vieira
publishedtheory similarity 0.60
Abstract · NeurIPS 2026 paper

Language models often produce high-quality individual samples but poor sets, with repeated samples clustering around the same semantic modes. We formalize diverse generation as sampling a size-$K$ subset of complete strings from a determinantal point process (DPP), where the likelihood encodes item quality, and the embedding geometry encodes repulsion between similar outputs. Exact inference over all strings is intractable, so we propose PoolDPP: draw a finite candidate pool from a tractable proposal, importance-weight the candidates toward the target quality, and run a $K$-DPP sampler on the induced pool kernel; a greedy MAP variant provides deterministic selection. We prove a finite-sample bound with an explicit constant: the KL divergence between the sampler's output and the target $K$-DPP decays as O(1/N) in the pool size. Empirically, PoolDPP extends the quality--diversity frontier on open-ended generation and the precision--recall frontier on ambiguous text-to-SQL (Ambrosia), and on mathematical reasoning (GSM8K), it raises diversity at about the same pass@$K$.

0.33

BARS: Budget-Aware Sequential Sampling with Refusal for Majority Identification under Unknown Distributions

cs.AI ·2026-11-10 ·Shenxi Liu, Yiwei Li, Mingyang Zhao, Yuhang Tian, Kan Li
similarity 0.60
Abstract · 23 pages (17 pages without appendix), 7 tables, 8 figures

Repeated sampling with majority selection is an effective means of enforcing self-consistency in large language models. Recently, a variant has also been introduced that terminates early to save costs when the output distribution is favorable. But it still cannot yield a correct confidence estimate from the answer distribution. For this issue, we formalize this as majority identification under an unknown distribution with a budget and a target error rate, and propose BARS, a sequential rule certifying the top-two gap and returning an early stop, a budgeted majority vote, or a refusal when feasibility cannot be established. A refusal is a statement about the rule and its budget, not a claim that a question is unanswerable, and it tells practitioners when to widen the budget or switch models. A certified mode carries proven bounds on the joint answering error and on refusing an instance the budget could handle, while a practical mode, used in our experiments, replaces them with empirical calibration. On synthetic instances drawn from known distributions over thousands of seeds, the difficulty-driven behavior is recovered and the price of the certified mode is measured.On GSM8K the practical mode draws 22.3\% fewer samples than fixed-8 sampling over the same pool, refused questions included, at the cost of declining 18.8\% of the questions. On MATH, it greatly improves the accuracy of its output answers into 82.5\% at the cost of honestly refusing to answer half of the difficult questions that the model itself is unable to solve.

0.23

More Correct Mass, Worse Answers: Why Power Sampling Can Fail and How to Fix It

cs.LG ·2026-08-14 ·Haohui Yang, Jiaxing Sun, Xiujun Ma
similarity 0.58
Abstract · 16 pages, 8 figures, 1 table. Haohui Yang and Jiaxing Sun contributed equally. Xiujun Ma is the corresponding author

Power Sampling sharpens a language model's distribution over complete generation trajectories, offering a verifier-free way to improve reasoning at inference time. It also has the potential to serve as a general-purpose front end for a broad range of downstream sampling methods. However, we uncover a striking paradox: Power Sampling can drive more probability mass toward correct trajectories while degrading the downstream inference it is intended to enhance. Using self-consistency as a representative case, we observe accuracy drops of up to 18.5 percentage points across models and reasoning benchmarks. We trace this paradox to two mismatches. Dose mismatch arises because a fixed exponent induces drastically different amounts of distributional change across problems. Coverage mismatch arises because global sharpening concentrates mass on a narrow set of dominant paths: high pass@k, often interpreted as evidence of preserved diversity, can therefore coexist with the loss of broad reasoning-path support required for downstream aggregation, search, and selection. Guided by this diagnosis, we replace uniform trajectory exponentiation with a deformation-controlled, support-preserving Power target that calibrates sharpening across problems while limiting the suppression of moderate-probability paths. In a same-budget instantiation with weighted self-consistency, the repaired sampler reverses the losses caused by global Power and outperforms standard multi-sample inference across reasoning benchmarks.

0.44

Towards stratified sampling for redistricting plans

cs.CY physics.soc-phmath.PR ·2026-09-16 ·Zijian Wang, Gregory J. Herschlag, Joon-Hyeok Yim, Jonathan C. Mattingly, Anna C. Gilbert
similarity 0.58
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.

0.27

ReSolve: Reusing Candidate Reasoning through Selective Generative Moderation

cs.AI ·2026-10-01 ·Bangji Yang, Jiajun Fan, Hongbo Ma, Xi Zhu, Weizhi Zhang +4 more
similarity 0.57
Abstract · Corrected a typo in an author's name. No changes to the paper content

Sampling multiple solutions spends computation on intermediate deductions and unfinished arguments as well as final answers. We introduce ReSolve, a training-free inference procedure that reuses this candidate reasoning through selective generative moderation. An answer-distribution controller invokes a model to examine existing derivations when candidates disagree or lack a parseable answer, then incorporates the generated solution into a bounded loop. Under Hybrid scoring on 130 competition-mathematics problems evaluated with two independently sampled candidate pools, ReSolve obtains 100 and 99 correct answers, compared with 91 and 92 for voting over the same four candidates, with no correct-to-incorrect changes relative to that vote in either pool. Eight-sample self-consistency obtains 94 and 96 correct answers while consuming substantially more tokens; ReSolve uses 46.3% and 47.2% fewer tokens in the two evaluations. A controlled ablation removes visible derivations while retaining answer keys, vote counts, and the per-state output-cap rule, reducing accuracy from 100 to 93 correct despite increasing computation. Selective and always-on Uniform moderation both solve 97 problems, while selectivity reduces moderation tokens by approximately 54% and total pipeline tokens by 6.2%. These results support candidate reasoning as reusable inference computation. They do not establish an accuracy advantage over additional sampling or a distinct benefit from specialized route instructions.

0.20

Which Answers Agree? Evaluating Self-Consistency from Incomplete Logs

cs.LG ·2026-10-19 ·Zhengtao Gui, Zexi Chen, Weining Shen
similarity 0.57
Abstract · 20 pages, 2 figures, including appendices

Self-consistency answers a question by generating multiple responses and selecting the most frequent answer. Its evaluation requires both correctness labels and information about which responses agree; correctness labels alone generally determine neither voting accuracy nor the benefit of additional votes. For tasks in which all correct responses map to the same normalized answer, we derive sharp accuracy bounds using classical stochastic majorization, refined by abstention counts and answer-category limits. We also derive sharp bounds on accuracy changes across voting budgets that share a response pool. When answer-category counts are available, we introduce Plurality-U, a count-based dynamic program that exactly averages voting accuracy over all fixed-size subsets, eliminating finite-pool Monte Carlo error. On 1,403,520 stored outputs from recent reasoning models in Scorio Lite and Scorio Trace, recording abstention counts and answer options cuts the width of SuperGPQA accuracy intervals by more than half. For moving from 9 to 17 votes, our bounds reduce interval width by a median of 77.7% on SuperGPQA and 72.3% on 14 GPQA and Adaptive-Consistency pools, compared with a baseline that combines separate accuracy bounds. Exact computation has lower paired median runtime than 2,000-subset Monte Carlo in 14 of 15 tested pool-budget settings. These results clarify what incomplete logs can establish and provide an exact evaluation procedure when answer counts are retained.

0.38

Social Choice Foundations for Simulation-Augmented Generation

cs.GT cs.AIcs.LG ·2026-09-29 ·Sonja Kraiczy, Smitha Milli, Ratip Emin Berker, Avinandan Bose, Brandon Amos +4 more
top venuetheory similarity 0.57
Abstract · Accepted at NeurIPS 2026

Simulation-augmented generation (SAGE) is a recent technical proposal in which models simulate individuals' viewpoints at inference time in order to provide more representative answers to contentious user queries. A core challenge for SAGE is making inference-time simulation efficient without sacrificing representation quality. We introduce the first formalization of this problem, based upon an axiom from proportional clustering known as metric proportional justified representation+ (mPJR+) which is the strongest proportionality axiom known to always be satisfiable by centroid-based clustering. We prove that to proportionally represent the viewpoints of a population of $n_H$ humans on a given prompt, we need only create simulations of $n \ll n_H$ individuals, and at inference time, need only dynamically route to $k \ll n$ of those simulations based upon the prompt. This twofold reduction still yields approximate proportional representation guarantees for the entire population. Empirically, across two domains-political questions and personal advice-our proposed routing algorithm achieves higher mPJR+ satisfaction rates than $k$-means-based or random selection baselines.

0.68