acceptodds
Withdrawn from ICLR 2027

Neighborhood Elites: Quality-Diversity Search for Uncertainty Quantification in Question Answering

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Large language models (LLMs) are increasingly capable, yet they produce wrong answers indistinguishable from correct ones. In question answering (QA), such an error propagates unnoticed into downstream tasks. Perturbation-based uncertainty quantification (UQ) addresses this by probing a model over a set of input rewrites and reading uncertainty from how much its predictions vary. Yet this set is usually built generically, by free paraphrasing, token-level perturbation, or adversarial search. Such rewrites leave two things uncontrolled that matter in QA: what kind of change is made to the context, and how explicitly the context supports the answer. When neither is controlled, the composition of the set is determined by the generator rather than by design, and the estimate inherits whatever that generator happens to produce. Quality-diversity (QD) search is built to cover a predefined exploration space, so we recast input perturbation as a QD problem and propose neighborhood elites (NE), a neighborhood constructor that spreads answer-preserving rewrites across two axes, the kind of edit and the explicitness of support. We compare NE against three other neighborhood constructors, holding the editor, QA model, uncertainty measure and search objective fixed, and against three scores read from the original context. Across five extractive-QA datasets and five instruction-tuned LLMs, NE improves failure detection against every other constructor in at least 24 of the 25 dataset-model pairs, reaching 0.726 AUROC and 0.211 AUPRC lift over the base rate. Additionally, NE detects failure better than semantic entropy computed over decoder samples, by 0.074 AUROC and 0.062 AUPRC lift, and this advantage widens as the neighborhood grows.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
uncertainty estimation, question answering, quality diversity, failure detection

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_UXoxOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper explores a strategy for quantifying uncertainty in a model's QA extractive QA response using prompt perturbations. The authors argue that current perturbation-based UQ algorithms appear to rely on unsophisticated strategies for generating perturbations (new prompts). The key contribution is the use of an evolutionary search-based strategy to generate diverse prompts. For that, they hand-design a space of 12 different “types” of perturbations (based on a 3x4 combination of the type of prompt rewrite and how explicitly the answer is supported in the rewrite). The authors then use a search strategy called MAP-Elites to fill this 12D space, retaining high-quality prompts based on a fitness function defined by semantic closeness from x, surface edit magnitude from x, and fluency. At the end, the different retained prompts are used to generate answers, and the semantic entropy over their induced answer distribution is taken as the uncertainty score. Results show better discriminative performance across extractive QA datasets and models than Semantic Entropy and other self-created QD variants.

Critical strengths

None

Critical weaknesses

Key Weakness 1: Evaluation Issues & Missing Baselines

W11: Methods are evaluated on different samples (see Table 1). As the authors write (L325-326), a method is scored if it has ≥ 2 predictions “where semantic entropy is defined”. Semantic Entropy is also defined at 1 prediction, namely SE=0. I do not see any reason to exclude these cases.

W12: Compute Costs are not transparent / very high: The method has the following steps, as I understand them, to create 1 potential candidate: Editor (Creating a new prompt based on the parent), Feasibility (three gates) + Search Objective Evaluation. As we run this (many?) times - I can’t find a number for how often this is run exactly- this seems very costly. In this spirit, comparing Semantic Entropy with only as many samples as the archive holds in the end (L278/288) is probably a very unfair comparison in terms of compute budget. A similar concern here is that while SE can reuse the cached prompt and only needs to sample new generations, the proposed method must create a new prompt (which is costly if the answer is short relative to the prompt).

W13: Missing Baselines: The authors themselves position the paper as pertubation based UQ (which is clearly correct) yet do not evaluate similar works e.g. SPUQ [1]. Similarly, many other UQ baselines are easily accessible with e.g. LM-Polygraph [2]

W14: The editor (proposing a new prompt) gets the gold answer, as it should be preserved across rewrites (L199—201). At inference time, the gold answer is not available, as if I had it, I would not need to solve the task.

Consequence of assessment: In its current form, the results are not trustworthy, and as such I can not conclude an advantage of the method.

Key Weakness 2: Very Hard to Read Manuscript

W21: The paper is poorly written at many parts:

  • In general, it has heavy tail-tale signs of pure AI-generated text (Many small paragraphs, technical terms used before being introduced, result section mainly stating numbers of tables and figures instead of setting them in context).
  • The introduction e.g., first starts with a related work section of UQ, not even focusing on perturbation-based UQ (starts in paragraph 4)
  • At times, it uses terms not yet introduced (e.g., L60 QD algorithms; (I don’t think these are generally widely known). L082: descriptor space, L088: one cell, L093/94 two axes: four levels of answer support. L156: MAP-Elites (Again, I don’t think MAP-Elite is a term everyone knows except those who worked with QD algorithms).
  • L129 Vicinal risk minimization does not seem really related to this problem. Rather, some background on evolutionary methods and MAP-Elites would be helpful.

Consequence of assessment: It is hard to follow the paper even though the actual content is quite simple and could be well presented and as such does not meet standard of an A* publication.

References:

[1] https://arxiv.org/pdf/2403.02509

[2] https://arxiv.org/abs/2311.07383

Questions for authors

Q1 - Improve Experiments

  • (See W11) Please provide the evaluation on an equal amount of samples and clarify why omitting SE=0 samples should be valid.
  • (See W12) Please provide (1) What are the costs (e.g., how many LLM calls vs. deterministic rules) to create 1 candidate? (2) How long does this strategy run on average, and what is the total cost in the end? (3) If it is significantly higher than the number of calls used to approximate SE, please run a baseline with compute-adjusted SE.
  • (See W13) Please include especially other perturbation-related baselines (SPUQ).
  • (See W14) Please clarify the use of the gold answer and explain how the method would work if you did not have access to it.

Positive results and clarification on these issues could slightly affect my assessment

Q2 - Better Manuscript

In my opinion, the manuscript needs a significant rewrite, which is not possible in the rebuttal period. As such, this caps my potential change of assessment of Q1 at (2-Weak Reject).

Reviewer_EZXTOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper presents a perturbation-based uncertainty quantification method (NE) for detecting incorrect answers in LLM-based question answering. It employs quality-diversity search and an editor LLM to construct answer-preserving context rewrites across two dimensions (edit type and answer-support explicitness). It then computes semantic entropy over the QA model's predictions on these rewrites to estimate uncertainty. The authors present experiments on five QA datasets and five LLMs to demonstrate its performance.

Critical strengths

The paper introduces a novel application of quality-diversity search to systematically construct diverse context rewrites for uncertainty quantification.

The experiments cover five QA datasets and five LLMs, demonstrating consistent improvements in failure detection across multiple settings.

Critical weaknesses

First, the paper's presentation can be significantly improved. The methodology section (2) lacks a mathematical formulation of the problem and of the proposed approach. I found it very difficult to understand the proposed methodology in its current form.  For example, I need to understand QE search first in order to understand Section 2.1, but QD search is described in the middle of Section 2.1. Further, QD search I is described informally and I found it difficult to understand accurately. "Rewrites" is mentioned many times in Section 2, but I can not fully understand rewrites until I read Appendix C.3 and H (e.g., rewrites are dependent on answer specification that is further dependent on gold answers). There are several other places I have difficulty reading if I do not read the appendix. 

Second, the statement that the uncertainty measure “sees neither the gold answer nor which constructor built the neighborhood” does not establish that the estimator is gold-independent.  Appendix H defines the answer specification as a representation of the dataset’s gold answers (Lines 2795 - 2802). Appendix C.3 also directly states that the editor receives “the question q and its gold answer y.” (Lines 2146-2147). The uncertainty measure is defined based on neighborhood (a distribution over answer-preserving rewrites), and rewrites are dependent on answer specification, which is dependent on gold answers.  This raises a fundamental concern about the method's applicability to realistic inference settings, where gold answers are typically unavailable. The authors should clarify this limitation and investigate whether comparable uncertainty-estimation performance can be achieved without access to gold answers during neighborhood construction.

Third, in Appendix C.4.1, the authors state, “We require the gold answer to remain recoverable from the edited context.” However, how can this requirement be enforced in practical inference settings where gold answers are unavailable? The proposed validation procedure appears to rely on access to the gold-answer specification, raising concerns about its applicability in real-world uncertainty estimation.

Fourth, Appendix C.4.1 uses a deterministic lexical check to verify answer preservation. However, the presence of the gold-answer string in a rewritten context does not necessarily guarantee that the context still semantically supports that answer. How do the authors ensure that the rewrites genuinely preserve answer correctness rather than merely retaining the answer string?

Fifth, the paper’s own related-work section (Page 15) identifies SPUQ and Inv-Entropy as relevant input-perturbation methods, but the experimental neighborhood comparisons are custom controls. A direct comparison with a strong relevant prior method would strengthen the external significance of the result.

Sixth, although the empirical results are promising, they lack evidence that QD search or coverage targeting is the principal source of the improvement. 

Seventh, the authors state in the abstract: "Additionally, NE detects failure better than semantic entropy computed over decoder samples, by 0.074 AUROC and 0.062 AUPRC lift, and this advantage widens as the neighborhood grows." While decoder semantic entropy is a well-established UQ baseline, it does not necessarily represent the current state of the art. The two methods reviewed in the related work section, along with the following two methods (refs. 1 and 2), are more recent baselines. References

Lastly, no source code is provided to support replication of the results, given the complexity of the proposed neighborhood construction, validation, and evaluation procedures

References

  1. Li Z, Shen S, Yang W, Jin R, Chen H, Ren J. Enhancing uncertainty quantification in large language models through semantic graph density. In The 41st Conference on Uncertainty in Artificial Intelligence, 2025 Jul 11.

  2. Vashurin R, Goloburda M, Ilina A, Rubashevskii A, Nakov P, Shelmanov A, Panov M. Cocoa: A minimum bayes risk framework bridging confidence and consistency for uncertainty quantification in LLMs. Advances in Neural Information Processing Systems. 2026 Apr 23;38:106236-81.

Questions for authors

The authors may address some of my weaknesses as described above.

Reviewer_DRNtOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper flags wrong answers of an extractive QA model from the semantic entropy of its answers on a neighborhood of rewritten contexts. The method, Neighborhood Elites (NE), gets the rewrites from a MAP-Elites quality-diversity (QD) search that steers an LLM editor across edit types and how explicitly the answer is supported. Fixed rules check that each rewrite keeps the gold answer and makes the requested edit. On five QA datasets and five open models, the authors report that NE beats other ways of building the neighborhood and decoder-sampled semantic entropy.

Critical strengths
  1. The constructor comparison is well controlled. All constructors share the editor, answer check, uncertainty measure and instances, and every paired difference is reported with intervals. NE wins almost all of them.

  2. The editor diagnostics are useful beyond this work. Without a check, most rewrites kept by the untargeted search lack the requested edit, and checking this with deterministic rules is a clean fix.

Critical weaknesses
  1. The neighborhoods are built with the gold answer, which is not available at test time, and the paper does not discuss this. The gold answer appears in the editor prompt as the "Fixed original answer" (appendix G). The admission gate checks that it survives, and the support-explicitness level is measured around it. A failure is an original prediction that differs from the gold answer. A rewrite that makes the gold evidence more explicit can pull such a prediction back to gold, which creates disagreement exactly on the failures. Section 3 says the only difference from decoder-sampled semantic entropy (DSE) is the source of variation, but DSE and the likelihood baselines never see the gold answer. So the comparison does not show that context variation carries more failure signal than decoder sampling.

  2. It is unclear how large the gain is and where it comes from. NE makes about two dozen whole-passage editor calls per instance before its KK QA calls, while DSE draws only KK short samples. Yet the paper reports no token counts or run times and never runs DSE at a matched budget. It also runs neither SPUQ nor Inv-Entropy, two perturbation methods it cites. A good part of the margin over DSE comes from one model. DSE is close to chance on gemma3-12b, and by my computation from table 9, removing that model cuts the mean AUROC gain by more than a third. NE also has ten prompt strategies and the other constructors one or two. Its gain over static bucket sampling (SBS) may come from this strategy registry rather than the QD search.

Questions for authors
  1. What replaces the gold answer at test time in the editor prompt, the answer gate and the support-explicitness rule? I recommend to report table 1 with the QA model's own answer on the original context in its place.
  2. On failure instances, how often do NE's neighborhood predictions equal the gold answer, by strategy and compared with free paraphrasing?
  3. How many tokens and how much wall-clock time does each method use per instance, editor included?
  4. Could you add DSE at matched compute, with more samples and a temperature sweep that includes T=1.0T = 1.0, and also run SPUQ or Inv-Entropy?
  5. SBS cycling through all ten NE strategies, without targeting or lineage, might show whether the gain comes from the QD search or the strategy registry.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.