When a request to a language model is underspecified, the strongest current fix is to ask the user a clarifying question. Methods such as Active Task Disambiguation with LLMs choose that question by sampling many candidate solutions, imagining how the user would answer each candidate question, and picking the question whose answer is expected to rule out the most candidates. This works well: GPT-3.5 accuracy on HumanEval rises from 44% to 85% over four clarification rounds. It is also slow. Every turn the model regenerates all its candidate solutions and runs one simulated-answer call for every candidate-question pair, so the cost per turn grows with the product of the two counts. At the same time, the cheapest and most common signal in real interaction gets thrown away. The user looks at an answer and says "no, not that." DRIFT reports that such dissatisfaction signals are far more abundant than explicit approval.
This note proposes treating a shown-and-rejected candidate as a query in its own right, and an unusually cheap one. Suppose the model keeps a pool of candidate programs or SQL queries across turns instead of resampling them. Then a rejection of candidate $c$ can be scored against every other candidate by executing them and checking whether they behave like $c$. That costs no language-model calls and no simulated answers. The agent chooses each turn between asking a clarifying question and showing its current best guess, picking whichever is expected to remove the most uncertainty per unit of wall-clock time and user effort. It regenerates candidates only when rejections have emptied the pool, and it conditions the regeneration on what was rejected. It stops when the remaining belief is concentrated enough, not after a fixed number of turns. The claim is that this gives a strictly better accuracy-versus-latency curve than resample-every-turn information-gain methods, with equal or fewer user turns.
Core Claim
Information-gain query selection, which scores a question by how much it is expected to shrink uncertainty over possible intended solutions, has been studied almost entirely with questions as the only action and fresh candidate pools at every turn. Negative feedback has been studied almost entirely as a training signal or a ranking heuristic. We claim the two meet at one mechanism. A rejection is an observation whose likelihood under each hypothesis can be computed by program execution, so it updates a persistent candidate pool almost for free. That makes "show the current best guess" a competitive action whenever belief is already somewhat concentrated. Choosing actions by expected information gain divided by expected cost then lowers per-turn latency, because most turns skip question generation and answer simulation. It also lowers total turns, because late-stage turns stop asking bisecting questions when one guess would likely succeed.
Concretely, the agent holds weighted hypotheses $\{(y_i, w_i)\}_{i=1}^N$, where each $y_i$ is a candidate program or query. For a shown candidate $c$, the probability of rejection under hypothesis $y_i$ is $$p(\text{reject} \mid c, y_i) = \epsilon + (1 - 2\epsilon)\,\big(1 - \mathrm{agree}(c, y_i)\big),$$ where $\mathrm{agree}(c, y_i)$ is the fraction of generated test inputs on which $c$ and $y_i$ produce the same output, and $\epsilon$ is a small rate of user error. Because the likelihood is soft, a rejection lowers the weight of near-equivalent candidates in proportion to how alike they behave. Candidates that merely look similar are not wiped out with it, which avoids the over-penalization of neighboring valid solutions that the file flags as an open problem for negative feedback. The agent picks the action $$a^* = \arg\max_{a}\ \frac{\mathrm{EIG}(a)}{\kappa_{\text{model}}(a) + \lambda\,\kappa_{\text{user}}(a)},$$ where $\mathrm{EIG}(a)$ is the expected entropy reduction over the weighted pool, $\kappa_{\text{model}}$ is the measured wall-clock cost of the action, $\kappa_{\text{user}}$ is a reading or answering cost for the user, and $\lambda$ trades the two off. For a show action, $\mathrm{EIG}$ is the binary entropy of the probability that $c$ is accepted, computable exactly from the weights. For a question action it requires simulated answers, as in prior work. The agent stops and emits its top candidate once the total weight of the top behavioral-equivalence cluster exceeds a threshold $\tau$.
Relation to Prior Work
Several papers supply the method for estimating information gain. Active Task Disambiguation with LLMs computes it from sampled programs and simulated answers but resamples each turn, uses only positive answers, and explicitly leaves the stopping rule unsolved. BED-LLM adds a Rao-Blackwellized estimator and pairs a prior over hypotheses with a likelihood of each answer, gaining 37.4 points on 20 Questions. It maintains its pool by in-context filtering rather than an explicit likelihood for rejections, and it chooses greedily among questions only. We reuse its likelihood pairing and add rejection observations, a cost denominator, and pool persistence. Interactive Text-to-SQL via Expected Information Gain cuts estimation cost from $O(NM)$ to $O(N)$ by exploiting the structure of SQL syntax trees. Our savings come from avoiding regeneration and answer simulation instead, so they do not depend on a grammar, though execution equivalence does require runnable outputs. SAGE-Agent already penalizes turns with a cost model and reports 54% fewer API calls, but its beliefs live over API parameter schemas and it cannot use rejected outputs.
Two papers motivate the negative-feedback side. MMR-BERT shows that conditioning question selection on rejected clarifications helps on Qulac, raising intent MRR to 0.248. It does so with a dissimilarity heuristic that cannot say how much uncertainty remains. DRIFT shows dissatisfaction signals are abundant and informative, but uses them only offline for preference training.
The stopping question is constrained by two results. Entrospect stops refinement when successive answers have embedding cosine similarity above 0.9. It obtains a 10x runtime cut on HaluEval, but notes that an overconfident model stops on wrong answers. VERINA shows refinement loops that thrash without converging. Our stopping rule uses posterior mass over behaviorally distinct candidates, so it can tell "the model keeps saying the same thing" apart from "the remaining candidates agree on behavior."
One result partly contradicts the proposal. Sequential Bayesian Search shows that questions splitting probability mass in half are the efficient choice. A "show one guess" action splits off only one candidate's mass, so pure bisection theory says show actions are wasteful. That conclusion holds when actions cost the same and belief is diffuse. We expect show actions to win only once one cluster holds a large share of the mass, or when cost asymmetry is large. Measuring where this crossover falls is part of the contribution.
Research Program
We build the agent on open-weight models in the 8B to 32B range, plus GPT-4o-class APIs for comparability. Execution checks use test inputs generated once per task and cached. Pool maintenance runs entirely on these executions.
When the effective sample size of the weights drops below $N/4$, the agent regenerates candidates. It prompts the model with the rejected candidates as explicit exclusions, then discards any new sample that behaves identically to a rejected one. Survivors join the pool at prior weight times their rejection likelihoods.
Costs are measured, not assumed. $\kappa_{\text{model}}$ is taken from logged wall-clock time per action type on fixed hardware. For $\kappa_{\text{user}}$, we use token length of what the user must read as a proxy, and we validate this proxy in a small human study described under Proposed Experiments. The analysis characterizes, as a function of pool entropy, when show actions are chosen, and checks that against the bisection argument above.
Baselines
The naive reference points are two fixed-budget policies. One is single-pass generation with no interaction. The other is "show and resample": show the top candidate, append any rejection to the context as text, and regenerate, which is what an off-the-shelf chat model does.
The strongest existing method is Active Task Disambiguation's full information-gain selection with fresh sampling each turn. Its reported result is 85% HumanEval accuracy after four clarification turns with GPT-3.5, from a 44% base. On Text-to-SQL, the strongest competitor is the syntax-tree information-gain method, at 76.6% execution accuracy on the Spider ambiguous subset and 86.88% exact match on AmbiQT join ambiguity. On 20 Questions it is BED-LLM. For BED-LLM the file gives only the 37.4-point average gain over direct prompting and no absolute success rate, so we rerun it.
We also include MMR-BERT-style dissimilarity selection over rejected outputs as the strongest heuristic negative-feedback method. Its Qulac intent MRR is 0.248.
All baselines are reimplemented on the same base model, the same simulated user, and the same turn budget. Each baseline gets the same tuning budget over its sample counts $N$ and $M$, so every method is compared as a full accuracy-versus-cost curve, not at one setting.
Beating the strongest baseline means one of two things. Either we reach its four-turn accuracy with at least 2x lower median wall-clock time and no more user turns, or we exceed its accuracy at matched wall-clock time, in both cases across three seeds.
Four ablations isolate the ingredients. The first removes pool persistence by resampling every turn but keeping rejection likelihoods. The second removes show actions. The third removes the cost denominator. The fourth replaces the posterior-mass stopping rule with Entrospect's cosine rule.
Why not just…?
Why not just append rejections to the context and let the model resample? This is the default behavior and costs nothing to build. Its weakness is that a rejection then changes only the prompt. The model can and does regenerate behaviorally equivalent candidates, and nothing tells it how much uncertainty is left. That is the gap MMR-BERT's authors also leave open. The "show and resample" baseline measures this directly. If its curve matches ours, the persistent pool is unnecessary and we would say so.
Why not just use fewer samples in standard information-gain selection? BED-LLM reports holding performance with as few as 15 hypotheses, so shrinking $N$ and $M$ is a real threat. It may recover most of the latency savings without any new machinery. We handle this by sweeping $N$ and $M$ for every baseline and comparing entire curves. The proposal survives only if its curve dominates the best small-sample setting, and the no-persistence ablation shows how much of the gain is just "fewer samples."
Why not just use the MMR-style dissimilarity penalty? It is cheap and already shown to help on Qulac. However, it measures surface similarity rather than behavior and has no stopping signal. On code and SQL, two candidates can differ in text while being equivalent, or look alike while differing. We compare directly against it on all three task families.
Why not train a policy end to end, as SAGE-Agent does with reinforcement learning? A learned policy could absorb the cost trade-off implicitly. It needs structured schemas or reward design per domain and offers no calibrated stopping. Our selection rule needs no training. A learned variant is a natural follow-up once the cost-aware objective is shown to matter.
Proposed Experiments
Task families. We evaluate three settings. The first is HumanEval and APPS with docstrings made ambiguous as in Active Task Disambiguation. The second is the Spider ambiguous subset and AmbiQT, using execution equivalence over database instances. The third is 20 Questions, where agreement reduces to entity identity.
Simulated users. An LLM user holds the hidden ground-truth solution and answers questions or accepts and rejects shown candidates. Its error rate $\epsilon$ is injected at 0, 5%, and 15% to test robustness.
Metrics. We record final accuracy, user turns, language-model calls, decoded tokens, median and 90th-percentile wall-clock time per task, and the rate of premature stops on wrong answers.
Decisive checks.
The first check is the Pareto comparison against the strongest baseline described above.
The second is a crossover analysis. We plot the fraction of show actions against pool entropy and test whether shows dominate only below an entropy level predicted by the bisection argument. If shows are chosen at high entropy and still win, the user-cost proxy is likely miscalibrated.
The third is a stopping-rule test. At equal average turns, the posterior-mass rule should produce fewer confident-wrong stops than the cosine rule, specifically on cases where the base model is overconfident. These cases are identified as tasks where greedy decoding is wrong but sampled candidates agree.
The fourth is a small human study with about 20 programmers on 30 HumanEval tasks. It checks whether reading-length cost tracks actual time to accept or reject a program, and whether real users find show-heavy dialogs acceptable.
If the persistent pool fails to beat the tuned small-sample baseline on wall-clock time, the latency claim is wrong. In that case the remaining contribution is the calibrated, rejection-aware stopping rule alone.
References
- Active Task Disambiguation with LLMs
- DRIFT: Learning from Abundant User Dissatisfaction in Real-World Preference Learning
- BED-LLM: Intelligent Information Gathering with LLMs and Bayesian Experimental Design
- Interactive Text-to-SQL via Expected Information Gain for Disambiguation
- Structured Uncertainty guided Clarification for LLM Agents
- Asking Clarifying Questions Based on Negative Feedback in Conversational Search
- Entrospect: Information-Theoretic Self-Reflection Elicits Better Response Refinement of Small Language Models
- VERINA: Benchmarking Verifiable Code Generation
- Sequential Bayesian Search