CS Paper Radar

The Art of Calling the Winner by Asking Just Enough Questions: Competitive Preference Elicitation with Next-Best Queries

Nisarg Shah, Ziqi Yu

cs.GT ·submitted 2026-08-29 06:33 UTC · v1
hot direction

Abstract

We study active elicitation of agent preferences for collectively choosing among $m$ alternatives using prominent voting rules. We focus on the next-best query model, in which an agent responds to a query by revealing their next favorite alternative, and measure the competitive ratio, which is the worst-case ratio between the number of queries made by the active elicitation algorithm and the minimum number of queries needed to reveal the winning alternative(s) in hindsight. We show that sublinear competitive ratios are achievable for many positional scoring rules, whereas every Condorcet-consistent rule has competitive ratio linear in $m$. For Borda count, we develop two complementary techniques: level-wise pruning, whose analysis extends to general concave scoring rules, and multi-scale score thresholding, which gives an $O(\sqrt m)$ worst-case guarantee for Borda. We also demonstrate strong empirical performance of level-wise pruning on real data.

Closest papers

Nearest neighbours by meaning across the whole index.

Compare to Correct: Pairwise-Guided Logit Adjustment for LLM Test-Time Scaling

cs.AI ·2026-10-13 ·Cong Hua, Qianqian Xu, Zitai Wang, Zhiyong Yang, Shilong Bao +2 more
similarity 0.63
Abstract

Sampling-based test-time scaling enhances LLM reasoning by aggregating multiple reasoning paths for the same query. Existing methods use answer frequencies or path confidence to compute candidate scores, which do not explicitly characterize comparisons between competing answers. Inspired by the Condorcet principle in social choice theory, we introduce pairwise confidence comparisons between paths supporting different answers to capture answer-level comparative advantage. We combine this comparative evidence with voting support through a KL-regularized objective. Theoretically, we show that this comparative-advantage is equivalent to the adjustment to the traditional voting logits. In this way, our proposed Pairwise-Guided Logit Adjustment (PGLA) framework allows comparative evidence to compensate for weaker voting support and correct voting-based ranking errors. Experiments on 10 challenging benchmarks including mathematical reasoning, knowledge reasoning, and code generation with 7 models ranging from 1.7B to 32B parameters speak to the effectiveness of this plug-and-play term. Additional evaluations with external reward scores and online sampling further demonstrate its applicability.

0.28

Rubric-Calibrated Preferences: Cross-Query Calibration of LLM Judgments via Item Response Theory

cs.IR ·2026-09-28 ·Fabian David Schmidt, Donato Crisostomi, Carlos Lassance, Nils Reimers
benchmarkcode/data similarity 0.62
Abstract · 51 pages. Code and data: https://github.com/cohere-ai/rcp-ndcg

Rerankers decide which documents users and LLMs see, yet their standard metric, nDCG, relies on human relevance labels that are costly, sparse, noisy, and discretely graded. As rerankers approach each other in quality, nDCG on these labels therefore increasingly fails to separate them. LLM judges could supply dense labels. Relative judgments within one query tell even close candidates apart, yet their scores share no scale across queries. Absolute grades share one scale but are too coarse to distinguish documents of similar relevance. We propose Rubric-Calibrated Preferences (RCP), which combine both kinds of judgment. A listwise Bradley-Terry tournament orders each query's documents, and a rubric of yes/no criteria of increasing stringency provides an absolute standard. Item Response Theory (IRT), which scores test-takers based on their answers to common questions, then uses the shared criteria to put all queries' tournament scores on one scale. RCP's retrieval metric, RCP-nDCG, replaces nDCG's discrete labels with the resulting calibrated relevance probabilities. Against blind grades from 46 external annotators, calibration raises the correlation between a query's mean score and its mean human grade from 0.538 to 0.795. The probabilities rank a useful document above a non-useful one with probability 0.910 (AUC, chance 0.5), versus 0.651 for the benchmark labels. When the annotators' grades prefer one of two rerankers and exactly one metric agrees, that metric is RCP-nDCG in 72.4% of 185 comparisons (chance about 53%). On TREC-DL, RCP-nDCG sides with NIST assessors' grades on every reranker pair that these grades separate significantly. RCP-nDCG also resolves many of nDCG's ties and separates 1.9 times as many reranker pairs on NanoBEIR. Rubric calibration thus turns relative LLM judgments into dense relevance labels that are comparable across queries and agree with human judgment.

0.28

Algebraic Retrieval: Composable Search for Agents

cs.IR ·2026-09-16 ·Damian Delmas
code/data similarity 0.61
Abstract · 5 pages, 1 figure. Code and reproducible examples: https://github.com/algebraicretrieval/algebraicretrieval

Algebraic Retrieval lets AI agents compose search strategies at query time. Relevance criteria, eligibility constraints, and ranking preferences can be expressed together in a mathematical query. The query surface exposes available operations, so an agent can combine them for the question at hand and revise a program after inspecting results. We evaluate execution parity, not agent behavior or retrieval quality. Building on Programmatic Embedding Modulation (PEM), which exposes vector and score arithmetic during retrieval, we demonstrate contrastive scoring, candidate-pool reranking, and weighted ranking as composable queries, alongside executable SQL and PyTerrier counterparts. On the public 11,429-document Vaswani fixture, each program's implementations select the same document set with score differences below 1e-6; one tied pair orders differently across scoring paths.

0.48

Re$^3$Rank: Listwise Reranking with Reasoning-Conditioned Retrieval Heads

cs.CL ·2026-11-02 ·Ruiyi Yan, Zhuoyuan Mao, Yugo Murawaki, Yiwen Guo
similarity 0.60
Abstract

Attention-based rerankers score each candidate by the attention mass that retrieval heads route to it from the question, but the question, serving as a fixed query, carries limited information for locating relevant evidence. We propose Re$^3$Rank, a listwise reranker built on reasoning-conditioned retrieval heads (RRHeads). A generator first writes a reasoning trace over the question and the candidates, and a scorer then uses the trace tokens as the attention query of a few selected RRHeads, reading relevance as continuous scores. We present a straight-through estimator to propagate the ranking loss through the discrete trace, so that the generator and the scorer can be trained jointly for ranking. Averaged over 9 benchmarks, Re$^3$Rank outperforms 11 baseline rerankers: our 4B variant exceeds the strongest baseline by 3.11 NDCG@10 points on average, and even our 0.6B variant surpasses rerankers with up to 32B parameters.

0.15

Every Clause Counts: Instruction-Following Reranking by Multiplying Small, Answerable Questions

cs.IR cs.CL ·2026-11-02 ·S. M. Mahbub Uddin Ahmed, Abdullah Al Musaddiq
benchmark similarity 0.59
Abstract

People often attach instructions to their search queries, asking for pages written for beginners, documents in a certain language or official sources only. Most rerankers were trained to judge topical relevance and treat such instructions as a few extra words. On the InfoSearch benchmark, even GPT-4o used as a list-wise reranker reaches an average WISE (Weighted Instruction Sensitivity Evaluation) of only 33.5. We present DMReranker (Decision-Model Reranker), a zero-shot reranker that splits an instructed query into a topic and a short list of typed clauses. A small judge model answers one narrow question per clause, and the answer probabilities are multiplied into a single score. Nothing is trained, and the configuration was frozen before the test runs. Reranking the same top-100 candidates as the published baselines, DMReranker reaches a macro WISE of 50.9 over all six InfoSearch dimensions while keeping original-mode nDCG@10 at 82.9. It trails GPT-4o on the stricter SICR (Strict Instruction Compliance Ratio) metric, 19.2 against 32.1. We show that this gap follows from how a product of probabilities behaves when SICR compares raw scores across runs. Computed from ranks, our SICR is 67.0. On the same judge, splitting the instruction raises WISE from 32.9 to 47.6 over a single combined question, while raw-score SICR falls. Scoring all six dimensions cost about $10 at list price.

0.16

Beyond Confidence: Test-Time Scaling for Multi-Turn Search Agents via Retrieval Grounding

cs.AI ·2026-08-25 ·Hyunho Kook, Junhyuk So, Tianyu Fu, Haizhong Zheng, Beidi Chen
top venue similarity 0.59
Abstract · Accepted to EMNLP 2026 Findings

Confidence-based voting aggregates parallel LLM rollouts by weighting each with internal signals such as token log probabilities, and has been actively studied for single-turn reasoning. However, modern LLMs increasingly act as multi-turn search agents that retrieve and condition on external documents. In this paper, we show that confidence-based voting transfers poorly to this multi-turn setting, and identify the underlying failure reason as copy inflation: when retrieved documents are appended to an agent's context, tokens copied from those documents receive systematically inflated log probabilities. This flattens confidence scores within each question and weakens the resulting weighted vote. To address this issue, we propose Retrieval-Grounded Voting (RGV), which scores each rollout by the lexical overlap between its final answer and the documents it retrieved. By computing the signal outside the contaminated context, RGV sidesteps both token log probabilities and additional LLM calls. Across four search-agent benchmarks and five LLMs, RGV consistently outperforms confidence-based voting, with gains of up to +5.4% accuracy and +35% on minority-correct questions, where the correct answer appears in only 1-2 of 8 rollouts.

0.45

Social Learning of Ranking: Getting the Top Right despite Local Herding

cs.DS ·2026-10-11 ·Shahrzad Haddadan, Jie Gao
hot direction similarity 0.59
Abstract

In sequential learning, a group of agents sequentially receives a noisy private signal and observes the predictions of prior agents to estimate a hidden ground truth. While extensively studied for binary signals, we formalize and analyze sequential learning when the hidden ground truth is an ordering of $n$ items, and both private signals and inferences involve pairwise comparisons. A key focus in sequential learning is herding, where agents disregard their private signals to follow the crowd. We show that, while local herding in our model may lead agents to make incorrect pairwise inferences, the global hidden order can still be approximated. Specifically, by aggregating all pairwise comparison outputs, the highest-ranked items can be retrieved. We investigate top-$k$ retrieval across three scenarios: (1) passive aggregation, where information is gathered from the social learning process without intervention; (2) strategic selection, where agents choose their pairwise comparisons dynamically; and (3) aggregation with stubborn nodes, where a very small set of stubborn agents, who base their inferences solely on their private signals, join the mechanism. With query complexity as the number of agents needed for a high-probability estimation, we propose top-$k$ retrieval algorithms with query complexities sublinear in $O(n^2)$, the total number of pairs.

0.34

ZooWork-ShopRanker: An Open, Preference-Aligned E-Commerce Reranker

cs.CL ·2026-09-25 ·Siqiao Xue, Shuxuan Liu, Ning Hu
benchmarkcode/data similarity 0.58
Abstract · project page: \url{https://serendipityoneinc.github.io/look-bench-page/shoprank-bench.html}

Open rerankers trained for general web retrieval transfer imperfectly to e-commerce, where ranking decisions depend not only on topical relevance but also on user preferences, product constraints, and comparative product fit. These preference signals are difficult to supervise at scale: real search traffic provides authentic queries and candidates but no clean pairwise labels. We present ZooWork-ShopRanker, a family of e-commerce rerankers (0.6B, 4B, and 8B) aligned to judge-labeled shopping preference. Training pairs are labeled by a panel of reasoning large language models (LLMs) from different families acting as a preference oracle, with position-debiased judgments and agreement tiers, and the rerankers are trained on these labels. The aligned 8B flagship then serves as a distillation teacher for the efficient 4B and 0.6B models, which are fit to its scores and sharpened on judged pairs. To measure progress, we introduce ShopRank-Bench, a contamination-limited benchmark of ~10,000 private-traffic preference pairs in both text formats, tiered by how many judge families committed to each label. ZooWork-ShopRanker-8B and -4B significantly outperform the strongest open reranker baseline, every model significantly beats its own un-aligned base, and ZooWork-ShopRanker-0.6B beats its size peer; the gains hold in both formats and extend to common MTEB benchmarks. We release the models and the dual-format ShopRank-Bench to facilitate further research.

0.50