Rewrites as Voters: Proportional Approval Voting for Conversational Search Under Topic Shifts

When a user's goal changes mid-conversation, a search system has to rewrite the latest turn ("where can I watch them?") into a standalone query. This is hardest exactly at a pivot, because the rewriter cannot tell whether "them" still refers to the old topic or to the new one. We propose to sample many candidate rewrites from different slices of the conversation history. Each rewrite is treated as a voter that simply approves or rejects documents: it approves the ones in its own top-k retrieval results. A proportional voting rule from social choice then picks the final ranked list, and that rule guarantees a substantial minority of rewrites gets represented near the top. Plain majority-style fusion does the opposite: when most samples cling to the stale topic, it buries the new interpretation.

The opportunity sits between two findings. Self-consistency decoding means sampling many answers and taking a vote. It helps in tasks with checkable answers, but Truthfulness Does Not Scale Like Reasoning shows that polling a model's own beliefs fails when its errors are correlated across samples. Conversational rewriters, meanwhile, decode once and inherit whatever bias the context induces. Moving the vote from the model's beliefs to externally retrieved evidence, and deliberately breaking the shared stale-topic bias, may let sampling help where it otherwise would not.

Core Claim

At conversation turns where the user's topic shifts, retrieval quality is limited by two things. The first is a correlated error: most sampled rewrites carry the obsolete topic. The second is an aggregation rule that rewards whatever the majority says. Two changes should give gains that are concentrated on shift turns and largely absent on continuation turns. The first is to diversify the conditioning context, so that each sample sees a different number of recent turns. The second is to aggregate with a proportional approval rule rather than rank fusion.

If the gains are uniform across turn types, or if reciprocal rank fusion matches the proportional rule, the claim is wrong. In that case the contribution reduces to "use more rewrites," which would not be new.

Mechanism

For turn $t$ we generate $N$ rewrites. Each is conditioned on the last $h$ turns, with $h$ drawn from a spread that runs from the current turn alone to the full history, and each is sampled at moderate temperature. This history-horizon diversity is a targeted version of the prompt diversity that Dipper uses against shared prompt biases. Short horizons cannot see the stale topic at all, which breaks the correlation that Denisov-Blanch et al. identify.

Each rewrite $v$ retrieves passages, and its approval set $A_v$ is its top-$k$. We then select a ranked list $W$ greedily under Proportional Approval Voting. The committee score is

$$S(W)=\sum_{v=1}^{N}\sum_{j=1}^{|A_v\cap W|}\frac{1}{j},$$

so adding a passage that rewrite $v$ approves earns $1/(m_v+1)$, where $m_v$ is the number of $v$'s approved passages already in $W$. Rewrites that are already satisfied count for less. Once the stale-topic majority has a few passages placed, the new-topic minority wins the next slots.

This is the justified-representation property studied in Justifying Groups in Multiwinner Approval Voting, which characterizes when cohesive voter groups deserve committee seats. The rule's design follows from the dichotomous-preference literature's main result: binary approvals make stable, well-defined collective choices tractable. That result is shown for coalitions in Boolean Hedonic Games and for ratio-based matching in Stable Roommate Problem with Diversity Preferences. Ties are frequent with binary votes. We break them by the rewrites' original retrieval scores, following the concern raised in Ties in Multiwinner Approval Voting that arbitrary tie-breaking can drive outcomes. Multi-winner Approval Voting Goes Epistemic and Is Approval Voting Optimal Given Approval Votes? treat approval ballots as noisy signals of a hidden ground truth. That is the right lens here, since each rewrite is a noisy guess at the user's current goal.

Relation to Prior Work

Two rewriters define the frontier, and both commit to a single query at test time. AdaCQR samples candidate rewrites with diverse beam search and scores them by reciprocal rank fusion across BM25 and dense retrievers, but it does this only to build training targets. At inference it emits one rewrite. ConvSearch-R1 trains a 3B rewriter with reinforcement learning against retrieval rank and a reasoning step, then decodes greedily.

We reuse both as the generators of our voters. We change only what happens after sampling: aggregation at test time, over evidence, with a proportionality guarantee.

RaFe turns cross-encoder reranker scores into preference pairs for training rewriters. It motivates our use of retrieval as the judge, but it works on single turns and on continuous scores. InteR loops between an LLM and BM25, and it reports that expansion drifts after a few iterations. That finding constrains our design: we do no iterative expansion, only one round of parallel rewrites.

On the goal-shift side, IACM-RL marks overwritten parameters as stale inside a tool-calling agent. AgentChangeBench shows that strong models recover slowly after goal shifts. Both motivate the problem, but neither touches open-vocabulary retrieval. Our method does not decide which interpretation is stale. It hedges proportionally, which suits retrieval because a ranked list can hold both interpretations. Self-Consistency Preference Optimization trains toward self-consistent outputs. We stay entirely at test time.

Research Program

We first build the turn-type stratification. In TopiOCQA, every turn is grounded in a Wikipedia passage. We label a turn as a shift turn when its gold passage comes from a different article than the previous turn's, and as a continuation turn otherwise. We then measure the stale-topic correlation directly: across $N$ temperature-only samples, what fraction of rewrites retrieve nothing from the gold article, and how does that fraction change under horizon diversity? This replicates the correlated-error analysis of Denisov-Blanch et al. in a grounded setting.

We then run the full pipeline with ConvSearch-R1 and AdaCQR as rewriters, BM25 and ANCE as retrievers, $N \in \{4, 8, 16\}$, and $k \in \{5, 10, 20\}$. We report MRR, Recall@10, and Recall@100, stratified by turn type. End-to-end answer F1 comes from a fixed Fusion-in-Decoder reader. QReCC serves as a second benchmark with fewer topic switches. There we expect small gains, which works as a built-in control.

Baselines

The naive reference point is the ALLHISTORY dense retrieval setup from TopiOCQA. It concatenates the whole conversation as the query, and the paper reports 55.8 test F1 with Fusion-in-Decoder.

The strongest single-query competitors are AdaCQR and ConvSearch-R1 decoded greedily. AdaCQR reports MRR 32.8 on TopiOCQA with ANCE and MRR 52.4 on QReCC with BM25. ConvSearch-R1 reports a relative gain of over 10% MRR@3 over prior methods; we found no reported absolute figure for it on Lacuna. We run both from released or reproduced checkpoints on identical retrieval indexes. Beating them means a statistically significant MRR gain on TopiOCQA shift turns while staying within noise on continuation turns.

The strongest multi-query competitor is reciprocal rank fusion over the same $N$ rewrites. It receives the same samples, the same retrieval depth, and its fusion constant tuned on the development set with the same budget we give $k$. A second fusion competitor retrieves the union of the rewrites' results and reranks it with a BGE-style cross-encoder, as in RaFe, under the same candidate pool.

The ablation that isolates our ingredient is plain approval counting. It uses the same binary ballots and ranks passages by number of approvals, without the $1/j$ discount. A second ablation removes horizon diversity and samples by temperature alone.

Why not just…?

Why not just fuse the rewrites with reciprocal rank fusion? This is the real threat. Rank fusion over query variants is a well-known method, and averaged over all turns it may tie with our rule. Rank fusion sums per-voter scores, so a passage favored by a stale majority accumulates support without any saturation. The proportional rule saturates each voter. The prediction is therefore specific: the two rules should match on continuation turns and diverge on shift turns, and more so when the stale-sample fraction is between roughly a third and two thirds. If they match on shift turns too, we drop the proportionality claim and report the result as a negative.

Why not just train a better single rewriter? ConvSearch-R1 already optimizes against retrieval reward, yet it must still commit to one interpretation at an ambiguous pivot. The stratified analysis shows whether its errors cluster on shift turns. If its shift-turn performance already matches its continuation-turn performance, there is nothing for voting to fix, and the experiment will show that.

Why not just rerank the union with a cross-encoder? A cross-encoder scores passages against a query, but at a pivot the query itself is the ambiguous object. The reranker has to be given one rewrite or the raw history, which reintroduces the commitment problem. The two methods also combine naturally, with the cross-encoder reordering within the proportional committee. We test both alone and together, so a reranker that dominates on its own would be visible.

Why not just raise the temperature? Denisov-Blanch et al. show that more samples from the same biased distribution do not help when the errors are correlated. The temperature-only ablation, together with the stale-fraction measurement, tests whether horizon diversity, rather than the sample count, is what breaks the correlation.

Decisive Checks

The idea succeeds if three things hold. Horizon diversity lowers the stale-sample fraction on shift turns. Proportional approval beats both rank fusion and plain approval counting on shift-turn MRR, with no loss on continuation turns. The gain carries through to TopiOCQA answer F1 above the 55.8 ALLHISTORY reference at matched reader and retrieval cost.

A compute-matched comparison, in which each method gets the same total number of generated tokens and retrieval calls, guards against the gain being simply more compute. Rewrites are short, so even $N=16$ costs far less than self-consistency over full reasoning chains.