PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Mesut Ceylan, Arda Baris Basaran, Elgar Fleisch, Filipe Barata

arXiv:2610.40278v1cs.AIcs.CL

TL;DR

In extractive QA, perturbation sets need to control both how contexts are edited and how explicitly they support preserved answers. This paper introduces neighborhood elites, a quality-diversity search across those dimensions, and finds it leads other methods on the 25-pair macro, reaching 0.726 AUROC and 0.211 AUPRC lift.

  • Problem

    In extractive QA, perturbation sets need to control both context-edit type and answer-support explicitness, since answer-preserving rewrites can differ in how directly they support recovery.

    Source: §1 · p. 2

  • Method

    Neighborhood elites uses quality-diversity search to construct answer-preserving whole-passage rewrites across edit-type and answer-support descriptors.

    Source: §1 · p. 2

  • Results

    On the 25-pair macro, NE leads all other methods, reaching 0.726 AUROC and 0.211 AUPRC lift.

    Source: §4 · p. 6

  • Takeaways & Limitations

    Neighborhood coverage matters beyond rewrite count: U-ME retains more rewrites per instance than NE but covers half as many cells and scores lower.

    Source: §5 · p. 9

    The descriptor axes are a design choice rather than globally optimal, and their rule-based assignments have not been validated against human judgment.

    Source: §5 · p. 9

Abstract

from arXiv · show

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 \emph{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.

1 INTRODUCTION

Neighborhood elites (NE) uses quality-diversity search to build answer-preserving context neighborhoods across edit types and levels of answer support. The introduction reports that these structured neighborhoods improve failure detection over alternative constructors and decoder sampling.

Introduction

  • Because wrong answers can propagate through LLM pipelines and stated confidence is poorly aligned with accuracy, UQ estimates trust from signals other than the model’s self-report.Prediction-variability methods can use model outputs in black-box settings; perturbation-based methods vary the input while preserving its answer, and semantic entropy compares predictions by meaning.Source: §1 · pp. 1–2
  • Existing perturbation methods apply rewrite rules individually, leaving set composition to the generator and failing to control both context edits and how explicitly the context supports the unchanged answer.Support can become less direct when a rewrite uses a referring expression or spreads it across several sentences, increasing the demands on the QA model.Source: §1 · p. 2
  • NE improves failure detection over every other constructor in at least 24 of 25 dataset–model pairs, reaching 0.726 AUROC and 0.211 AUPRC lift over the base rate.The evaluation spans five extractive-QA datasets and five instruction-tuned LLMs.Source: §1 · p. 2
  • NE uses QD search to steer an editor toward empty cells defined by edit type and answer support, admitting rewrites only after a deterministic check confirms the requested edit.Rewrites compound along a lineage: each inherits an edited context and applies another answer-preserving edit, reaching contexts unavailable through a single edit of the original.Source: §1 · p. 2
  • The proposed neighborhood formulation covers three edit types and four answer-support levels, with rewrite coordinates determined by deterministic rules rather than a model judging its own output.The authors characterize this as the first perturbation set for UQ built by QD search to cover a space declared in advance.Source: §1 · p. 2
  • NE exceeds semantic entropy over decoder samples by 0.074 AUROC and 0.062 AUPRC lift; as neighborhoods grow from three rewrites to seven, NE gains 0.100 AUROC versus 0.030 for decoder sampling.The comparison uses the same uncertainty measure, predictions, and instances.Source: §1 · p. 3

2 METHOD

The method builds a finite archive of answer-preserving context rewrites, then uses a fixed QA model’s disagreement across them as an uncertainty signal. Neighborhood Elites organizes rewrites across edit type and support explicitness while MAP-Elites searches for diverse, high-quality candidates.

2.1 PROBING A QA MODEL BY PERTURBING ITS CONTEXT

  • The method queries a fixed QA model on answer-preserving rewrites and treats disagreement among its predictions as uncertainty.Predictions are grouped into semantic-equivalence classes, and dispersion across classes gives the per-instance score.Source: §2.1 · p. 3, §2.3 · p. 5
  • The neighborhood is a finite archive of validated rewrites spanning a 3 × 4 space of edit types and support explicitness, not a sample from a known distribution.Membership requires answer preservation; semantically closer rewrites receive more neighborhood mass, while coverage across descriptor cells is the search goal.Source: §2.1 · p. 3

2.2 CONSTRUCTING THE NEIGHBORHOOD WITH TARGETED MAP-ELITES

  • Neighborhood Elites uses an editor LLM to produce rewrites and MAP-Elites to organize exploration, retaining the highest-scoring valid rewrite in each cell.The search objective combines semantic closeness, surface edit magnitude, and fluency; answer preservation is an admission gate, not a ranking term.Source: §2.2 · pp. 3–5
  • Search seeds cells with edits to the original context, then targets empty cells or mutates a parent’s edit program so changes can accumulate across a lineage.The question, gold answer set, and original context stay fixed for answer preservation; each offspring must change its parent while keeping the original answer recoverable.Source: §2.2 · p. 4

2.3 FROM NEIGHBORHOOD DISAGREEMENT TO AN UNCERTAINTY SCORE

  • The uncertainty score is discrete semantic entropy over prediction-class proportions, separating disagreement in meaning from surface variation without model probabilities.Because it uses only the prediction multiset, the score does not depend on the gold answer or which constructor built the neighborhood.Source: §2.3 · p. 5

3 EXPERIMENTAL SETUP

The experiments compare answer-preserving neighborhood constructors and original-context uncertainty scores under a fixed QA evaluation setup spanning five extractive benchmarks and five frozen instruction-following LLMs.

Editor and QA LLMs

  • Five frozen LLMs—Gemma3-12B, OLMo2-13B-Instruct, Phi4-14B, Mistral-Nemo-12B, and Falcon3-10B-Instruct—evaluate neighborhoods generated by a fixed Qwen3-8B editor.All models are inference-only, with inference settings held fixed across experiments.Source: §3 · p. 5

Datasets

  • The evaluation uses 1,000 examples each from SQuAD v1.1, Quoref, NewsQA, MRQA Natural Questions, and AdversarialQA, shared across constructors.Reference answers are normalized into a common specification for answer-preserving validation.Source: §3 · p. 5

Neighborhood constructors

  • Free-form paraphrasing, untargeted MAP-Elites, and static bucket sampling compare against NE by omitting its archive, verification, or evolutionary search mechanisms.The comparators share NE’s editor and answer-preservation gate; U-ME evolves candidates without enforcing inheritance, while SBS proposes from the original context and places candidates after generation.Source: §3 · pp. 5–6

Original-context metrics

  • NLL, predictive entropy, and decoder semantic entropy score uncertainty from the original context; DSE uses as many decoder samples as NE has archived rewrites.Decoder samples use temperature 0.7 and top-p 0.95; DSE holds the measure, prediction count, and instances fixed against NE, varying whether predictions come from decoder resampling or context rewrites. Predictive entropy follows Malinin & Gales (2021) as used by Kuhn et al. (2023), and DSE follows Farquhar et al. (2024).Source: §3 · p. 6

Grouping answers by meaning

  • Semantic entropy groups answers by meaning using bidirectional entailment from a frozen DeBERTa-v3-base-mnli-fever-anli model, following Kuhn et al. (2023).This groups mutually entailing answers into semantic-equivalence classes rather than treating surface-form differences as disagreement.Source: §3 · p. 6

Evaluation metrics

  • Failure detection is evaluated with AUROC and AUPRC lift, treating incorrect original-context predictions as failures and subtracting the pool’s failure rate from AUPRC.AUROC measures ranking of failures above correct predictions; AUPRC lift accounts for differences in failure rates across scoring pools.Source: §3 · p. 6

4 RESULTS

Neighborhood elites (NE) delivers the strongest macro-averaged failure detection and spreads rewrites more broadly across edit-type and answer-support cells than the other constructors. Its advantage persists across neighborhood sizes, though it does not lead every pairwise comparison.

4 RESULTS

  • NE reaches 0.726 AUROC and 0.211 AUPRC lift on the 25-pair macro, ahead of every other method; untargeted search (U-ME) trails by 0.062 AUROC and 0.060 AUPRC lift.Across constructors, detection spans 0.621–0.726, compared with 0.652–0.676 for original-context scores; AUPRC lift spans 0.113–0.211 and 0.130–0.149, respectively.Source: §4 · p. 6, Table 1 · p. 7
  • NE leads 74 of 75 constructor comparisons and 57 of 75 original-context comparisons, but trails U-ME on Natural Questions with OLMo2-13B.It leads U-ME in 24 of 25 pairs, trailing by 0.004 AUROC and 0.016 AUPRC lift on that pair; the 19 negative AUROC differences and all 14 negative AUPRC differences cluster on Natural Questions and NewsQA.Source: §4 · pp. 6–7, Figure 3 · p. 7
  • NE occupies a mean of 4.43 of 12 cells per neighborhood, versus 2.33 for U-ME, 2.00 for SBS, and 0.98 for FP.NE reaches four or more cells on 0.658 of instances and averages 4.43 rewrites per instance; U-ME averages 5.90 rewrites.Source: §4 · p. 7, Table 2 · p. 8
  • NE and SBS reach every descriptor-space cell, whereas U-ME and FP concentrate almost exclusively on style rewrites.NE’s largest cell is style rewriting with discourse-mediated support (0.55 of instances), while its smallest is reordering with direct support (0.22); direct support is the least reached level for every constructor.Source: §4 · p. 8, Figure 4 · p. 8
  • At K=5, NE reaches 0.765 AUROC and 0.282 AUPRC lift, leading both other constructors in AUROC in all 25 pairs through K=5.The gaps over U-ME and FP widen from K=3 to K=5; original-context scores do not move with K.Source: §4 · p. 8

5 DISCUSSION AND CONCLUSION · APPENDIX CONTENTS · A RELATED WORK

Neighborhood Elites (NE) improves failure detection by probing answer-preserving rewrites across a designed space of edit types and support explicitness. The discussion also describes practical requirements, limitations, reproducibility resources, and how this approach differs from related work.

5 DISCUSSION AND CONCLUSION

  • NE’s AUROC gain rises 0.100 from K=3 to 7, versus 0.047 for FP and 0.030 for decoder sampling; it leads sampling by 0.074 AUROC and 0.062 AUPRC lift.NE’s advantage over sampling is tighter on Natural Questions and NewsQA, where every constructor covers the fewest cells. NE uses greedy decoding, while decoder resampling requires temperature 0.7.Source: Table 3 · p. 9, §5 · p. 9
  • Reliable NE search requires deterministic gates for duplicate rewrites and whether edits realize their requested type, plus targeting empty descriptor cells.Without checks, 0.17 of retained rewrites are duplicates and only 0.27 realize the requested type; detection improves from the 8B to 14B editor but not beyond, while it keeps improving as neighborhoods grow.Source: §5 · p. 9
  • The results are limited by a design-selected descriptor space, 12 cells, heuristic or rule-based axes without human validation, and constructor differences that prevent attributing gains to one mechanism.NE also uses ten prompt strategies, compared with two for untargeted search and one for each other constructor; the editor’s unseeded sampling limits bit-for-bit reproducibility.Source: §5 · pp. 9–10

REPRODUCIBILITY STATEMENT · APPENDIX CONTENTS

  • The appendix specifies constructors, gates, cell assignment, objectives, schedulers, prompts, fixed settings, data preparation, scoring, and evaluation procedures.Because editor generations lack a fixed per-call seed, each run’s archive is treated as a fixed artifact for reported numbers.Source: REPRODUCIBILITY STATEMENT · p. 10, APPENDIX CONTENTS · pp. 14–15

AI USE STATEMENT

  • Generative AI assisted with manuscript editing, research-code implementation, and verification; the authors reviewed the content, ran the experiments, and take responsibility for the manuscript and claims.Source: AI USE STATEMENT · p. 10

A RELATED WORK

  • Prior UQ methods use model probabilities, verbal or self-judged confidence, sampled-output agreement, or input perturbations, whose rewrites may lack edit coverage and answer-preservation guarantees.The related work notes that answer preservation may otherwise be checked only after generation rather than enforced during construction.Source: A RELATED WORK · pp. 15–16
  • Unlike robustness suites, this work retains answer-preserving edits and uses prediction disagreement for post-hoc uncertainty; unlike prior QD applications, it seeks answer-invariant rewrites rather than inputs that break models.The edit types themselves are not claimed as new.Source: §5 · p. 9, A RELATED WORK · p. 16

B FURTHER RESULTS · B.1 DETECTION ON MATCHED INSTANCES AND EQUAL NEIGHBORHOOD SIZE

This further-results section evaluates constructors on matched instances with equal neighborhood sizes, documenting how the eligible set changes with K and how semantic-entropy comparisons are estimated and reported.

B.1 DETECTION ON MATCHED INSTANCES AND EQUAL NEIGHBORHOOD SIZE

  • Matched eligibility requires shared instances, identical original predictions and failure labels, and at least K valid rewrites from every constructor; each receives exactly K predictions per example.A separate matched set is built for each dataset, QA model, and K, and the eligible set shrinks as K grows.Source: §B.1 · p. 16
  • For each K, 2,000 repeats independently redraw neighborhood predictions, recompute uncertainty and AUROC/AUPRC, and report means with empirical 2.5th–97.5th percentile intervals.Paired constructor differences are summarized across repeats and deemed reliably positive when P(∆>0) ≥ 0.975.Source: §B.1 · pp. 16–17
  • K=3 is the default because it yields the largest matched set and is the most conservative point for the method; the K sweep shows comparison behavior as resolution increases.Results are macro-averaged over 25 dataset–model pairs, with incorrect original-context predictions as the positive class.Source: §B.1 · p. 17

B FURTHER RESULTS

  • 15,730 observations qualify at K=3 versus 2,273 at K=7; NewsQA’s matched set shrinks elevenfold, and the surviving examples shift toward harder datasets.The base rate is the mean of the 25 per-pair failure rates and does not fall monotonically as K increases.Source: Table 4 · p. 17, §B.1 · p. 17

B.1 DETECTION ON MATCHED INSTANCES AND EQUAL NEIGHBORHOOD SIZE

  • Tables 5 and 6 report per-pair paired semantic-entropy ∆AUROC and ∆AUPRC, respectively, for FP, U-ME, and NE at K=3.AUPRC differences are described as noisier than rank-based AUROC differences because AUPRC depends on the base rate.Source: Table 5 · p. 18, Table 6 · p. 19
  • Tables 7 and 8 report semantic-entropy failure-detection AUROC and AUPRC across K, macro-averaged over 25 dataset–model pairs with 95% subselection percentile intervals.Source: Table 7 · p. 19, Table 8 · p. 20

B.2 FAILURE DETECTION PER DATASET–MODEL PAIR · B.3 ARCHIVE DIAGNOSTICS

Across dataset–model pairs, NE is rarely worse than its comparators on the reported paired AUROC and AUPRC differences. Archive diagnostics clarify how rewrites and descriptor-space coverage are counted, including a pronounced scarcity of U-ME distractors.

B.2 FAILURE DETECTION PER DATASET–MODEL PAIR

  • Only 19 of 150 paired AUROC differences and 14 of 150 paired AUPRC differences are against NE across the 25 dataset–model pairs.Each difference compares methods on instances they share under the min K = 2 requirement; it is not a difference between separately pooled levels.Source: Table 9 · p. 21, Table 10 · p. 22

B.3 ARCHIVE DIAGNOSTICS

  • Table 11 distinguishes editor-call proposals, retained rewrites, distinct rewrites, realized edit types, and occupied descriptor cells.Editor calls include rejected proposals; distinct removes exact repeats, and realized type matches the requested edit wherever the realization gate is on. Rewrites-by-type totals equal retained counts except for 5,799 U-ME rewrites without a resolvable realized type.Source: §B.3 · p. 22, Table 11 · p. 23
  • Across datasets and QA models, U-ME produced just 47 scored distractors versus 55,187 style rewrites, so its table omits the distractor column.An empty Table 11 cell means fewer than 100 rewrites, too few to estimate a rate; unlike Figure 4, it does not mean the region was never reached or indicate difficulty.Source: §B.3 · p. 22
  • Table 12 reports mean occupied descriptor cells per neighborhood by dataset, with standard deviations in brackets, over each dataset’s 1,000 instances.Source: Table 12 · p. 23
  • Figure 5 reports, for each descriptor-space cell, the proportion of 5,000 instances whose neighborhood contains at least one rewrite there.Source: Figure 5 · p. 24

B.4 DETECTION WITH AND WITHOUT A MINIMUM NEIGHBORHOOD SIZE · B.5 SENSITIVITY TO EDITOR SIZE

Across 25 dataset–model pairs, restricting evaluation to instances with at least two rewrites improves all three neighborhood constructors while leaving original-context scores unchanged. Results also vary by dataset and QA model, with low-rewrite instances explaining much of the full-archive gap; the editor-size section distinguishes its evaluation populations.

B.4 DETECTION WITH AND WITHOUT A MINIMUM NEIGHBORHOOD SIZE

  • With at least two rewrites, NE gains 0.023 AUROC and 0.022 lift; free paraphrasing gains 0.016 and 0.003 for untargeted search, while original-context scores remain unchanged.The minimum is definitional: semantic entropy requires more than one prediction to define a partition. The restricted comparison uses the same 21,920 instances for NE, predictive entropy (PE), and decoder semantic entropy (DSE).Source: Table 14 · p. 25, Table 13 · p. 25, §B.4 · p. 25
  • NE leads on SQuAD v1.1, Quoref, and AdversarialQA under both populations, while likelihood scores lead on Natural Questions and on full-archive NewsQA.On NewsQA, imposing the minimum raises NE from 0.647 to 0.687, against 0.691 for length-normalised likelihood; the cited passage attributes both exceptions to the share of instances with fewer than three rewrites.Source: §B.4 · p. 25, Table 15 · p. 26, Table 16 · p. 26
  • NE leads on four of five QA models on full archives and all five under the minimum, while decoder semantic entropy reaches 0.538 AUROC on Gemma3-12B.The share of instances with fewer than three rewrites is 18.5–18.6% across models, versus 5.6–37.7% across datasets; on Gemma3-12B, decoder resampling leaves answers unchanged while context rewriting separates failures.Source: §B.4 · p. 25, Table 17 · p. 26, Table 18 · p. 27
  • Against the three original-context scores, NE’s mean AUROC margin is comparable but less consistent, holding in 18 to 21 of 25 pairs.The comparison is pair by pair on instances shared by each method.Source: §B.4 · p. 26, Table 19 · p. 27
  • NE’s low-rewrite instances fail more often: 0.462 at one rewrite and 0.460 at two, versus 0.330 at three or more.NE has 4,401 such instances among 23,739 scored; semantic entropy assigns the same minimum score to all 1,819 single-rewrite instances, placing the hardest cases at the most confident end of the ranking. The full-archive cost is largest on NewsQA and Natural Questions and negligible on AdversarialQA and SQuAD v1.1.Source: §B.4 · pp. 26–27, Table 20 · p. 27, Table 21 · p. 27

B.5 SENSITIVITY TO EDITOR SIZE

  • The editor-size analysis compares Qwen3-8B, 14B, and 32B using each editor’s full archive and its subset with at least two rewrites or samples.Figure 6 instead uses the 21,031 instances where NE retains at least two rewrites at all three editor sizes, so its differences are not the same as the table comparisons.Source: §B.5 · p. 28

B.5.1 DETECTION ACROSS THE THREE EDITOR SIZES

With editor size increasing from 8B to 14B, NE detection improves, but it does not improve further at 32B, even as neighborhoods continue to grow.

B.5.1 DETECTION ACROSS THE THREE EDITOR SIZES

  • Neighborhoods grow from 4.97 rewrites per instance at 8B to 5.91 at 14B and 6.46 at 32B, while the 8B-to-14B AUROC gains vary across datasets.The gains are 0.0483 on Natural Questions, 0.0256 on NewsQA, 0.0191 on AdversarialQA, 0.0093 on SQuAD v1.1, and 0.0088 on Quoref; from 14B to 32B, four datasets lose AUROC and AdversarialQA gains 0.0009.Source: §B.5.1 · p. 28
  • +0.0222 [0.0135, 0.0316] mean AUROC and +0.0294 [0.0178, 0.0409] AUPRC lift from 8B to 14B; from 14B to 32B, changes are −0.0055 [−0.0121, 0.0010] AUROC and −0.0095 [−0.0186, −0.0008] AUPRC lift.Figure 6 compares NE on 21,031 instances with at least two retained rewrites at all three editor sizes.Source: Figure 6 · p. 28, §B.5.1 · p. 28

B.5.2 THE 14B EDITOR

This section reports failure-detection comparisons using the Qwen3-14B editor across full and restricted archives, with additional breakdowns by dataset, QA model, and method pair.

Overall

  • Table 22 compares failure detection across all 25 dataset–model pairs on the full archives, macro-averaged.U-ME has no 14B run and is absent from these tables.Source: Table 22 · p. 28, §B.5.2 · p. 28

By QA model

  • Tables 26 and 27 present the comparison by QA model, macro-averaged over the five datasets.Source: §B.5.2 · p. 28

Overall

  • Table 23 reports results for instances with at least two rewrites or samples; NE, PE, and DSE share the same 23,224 instances.Source: §B.5.2 · p. 28, Table 23 · p. 29

By dataset

Pair by pair

  • Tables 28 and 29 compare NE with each other method pairwise on the instances shared by the two methods.Source: §B.5.2 · p. 29

B.5.3 THE 32B EDITOR … C.6 SEARCH AND SCHEDULER

This section describes how rewrite variation is partitioned and how answer-preserving rewrites are classified, validated, scored, and searched to populate a quality-diversity archive. It also outlines the neighborhood constructors and descriptor axes, along with the scope of additional editor and QA evaluations.

B.5.3 THE 32B EDITOR

  • With the Qwen3-32B editor, the comparison covers NE against three original-context scores and includes no constructor comparison or minimum-rewrite tables.Tables also provide dataset, QA-model, and pairwise cuts, but the supplied passages do not report their cell values.Source: §B.5.3 · p. 29, Table 30 · p. 31, Table 31 · p. 31

B.5.4 THE THREE EDITORS SIDE BY SIDE

  • Across the three editor scales, NLL’s scorable population increased from 24,984 to 24,993 to 25,000, while coverage rose for every method.The original-context scores do not use the editor, but are evaluated on the population each run makes scorable.Source: §B.5.4 · p. 30, Table 34 · p. 32

B.6 WITHIN-NEIGHBORHOOD AND BETWEEN-NEIGHBORHOOD VARIATION

  • Edit-magnitude within-neighborhood variance shares were 0.75 for NE, 0.35 for U-ME, and 0.23 for FP; their m=3 ranges were 0.308, 0.09, and 0.061, respectively.On the K=3 matched pool of 15,730 instances, the corresponding shares were 0.77, 0.39, and 0.23, and ranges were 0.32, 0.10, and 0.06.Source: Figure 7 · p. 33, §B.6 · p. 33

C.1.1 NEIGHBORHOOD ELITES (NE)

  • NE targets archive cells, mutates an eligible parent toward the selected cell, and admits rewrites only when strict validation confirms the requested edit and answer preservation.The original context remains the validity reference, and verified edit types make the archive’s rewrite-type axis a behavior label.Source: §C.1.1 · pp. 34–35

C.1.2 UNTARGETED MAP ELITES (U-ME)

  • U-ME evolves rewrites without targeting cells and uses a weaker gate, so its rewrite-type coordinate records the requested type rather than verified behavior.Parents guide rather than constrain offspring; validation checks answer recoverability but omits edit-type realization and uniqueness.Source: §C.1.2 · p. 35

C.1.3 FREE FORM PARAPHRASING (FP)

  • FP draws independent paraphrases from the original context without an archive, parent mutation, coverage objective, or competitive admission.It uses the same strict answer-preservation gate and is matched in size and construction cost to its paired hard archive.Source: §C.1.3 · pp. 36–37

C.1.4 STATIC BUCKET SAMPLING (SBS)

  • SBS cycles requested edit types in independent proposals from the original context, then validates and places survivors without targeting cells or evolving lineage.Its strict gate verifies edit type, making that coordinate a behavior label; the design isolates the evolutionary component of NE.Source: §C.1.4 · p. 37

C.2 DESCRIPTOR SPACE D AND CELL ASSIGNMENT

  • The descriptor space crosses three edit types with four support-explicitness levels; edit type is requested and verified for hard methods, while support is measured from the output.Support categories distinguish direct, paraphrastic, discourse-mediated, and multi-sentence evidence; prompt strategy is not a descriptor.Source: §C.2 · p. 38, §C.2.2 · p. 39

C.2.2 SUPPORT-EXPLICITNESS AXIS S

  • The support-explicitness coordinate assigns rewrites to multi sentence, discourse mediated, direct, or paraphrastic buckets using support-window and sentence-feature checks.The primary support sentence is selected using the edit’s flagged location when available, otherwise the first sentence containing the answer; the window can include neighboring sentences.Source: §C.2.2 · p. 39

C.2.3 CELL ASSIGNMENT AND COMPETITION

  • Each occupied cell keeps one elite: a valid candidate fills an empty cell or replaces its incumbent only with a strictly greater search-objective score.Candidates from different prompt strategies compete in the same cell when their rewrite type and measured support bucket match.Source: §C.2.3 · p. 40

C.3 EDITOR AND EDIT PROGRAMS

  • The editor receives the question, gold answer, base context, and original-context reference, and an edit program pairs a requested rewrite type with a prompt strategy.The type determines the descriptor coordinate, while the strategy steers realization but is not a coordinate; candidates landing in the same cell compete.Source: §C.3 · pp. 40–41

C.4 DETERMINISTIC GATES

  • A rewrite enters the archive only after deterministic, model-independent checks reject empty, unchanged, duplicate, answer-losing, or unrealized edits.NE and FP use STRICTVALID, which includes answer preservation and edit-type realization; U-ME uses VALID, which omits the realization guard.Source: §C.4 · pp. 41–42

C.4.1 ANSWER-PRESERVING VALIDATION

  • Answer-preserving validation checks lexical recoverability of a required AnswerSpec group, but does not guarantee that unrelated source facts remain intact.The editor’s expected answer is logged but does not determine admission.Source: §C.4.1 · p. 42

C.4.2 EDIT-TYPE REALIZATION GUARD

  • The realization guard verifies that the requested edit type was performed, making the type coordinate a verified behavior label for guarded rewrites, not a guarantee of semantic faithfulness.The U-ME omits this guard and files by requested type alone.Source: §C.4.2 · p. 42

C.5 SEARCH OBJECTIVE

  • The search objective ranks only gate-passing rewrites, favoring surface variation and fluency while remaining close to the original meaning.It does not decide admissibility or enter uncertainty assessment; its components include edit magnitude, a deterministic fluency proxy, and BERTScore F1 semantic closeness.Source: §C.5 · p. 43

C.6 SEARCH AND SCHEDULER

  • Each evaluation consumes one attempt, and NE, U-ME, and SBS use 25 attempts per example while FP uses up to 50.All four reuse the same editor and gates; they differ in how they choose the next edit program and store accepted contexts.Source: §C.6 · pp. 43–44

C.6.1 ONE EVALUATION … D PREDICTION AND UNCERTAINTY SCORING

The methods specify how candidate rewrites are evaluated and scheduled across three neighborhood constructors, then how a frozen QA model’s answers on each archive are converted into an uncertainty score. NE uses staged search, while U-ME evolves rewrites generationally and FP appends independent paraphrases.

C.6.1 ONE EVALUATION

  • Accepted candidates pass deterministic gates and are inserted sequentially: archive-based constructors assign them to descriptor cells, while FP appends them to a flat list.An archive cell is filled when empty or replaced only when the candidate’s search-objective score is strictly higher.Source: §C.6.1 · p. 44

C.6.2 TARGETED STAGED SCHEDULER (NE)

  • NE uses bootstrap, coverage, and fitness stages; with B = 25 and r = 5, at most 20 evaluations precede a protected reserve that can pass unused capacity to fitness.Bootstrap attempts one candidate per rewrite-type/strategy pair, up to ten attempts with the ten strategies.Source: §C.6.2 · p. 44
  • Coverage targets the least-attempted actionable empty cell, choosing an eligible high-scoring parent and a compatible least-attempted strategy.Coverage ends when no empty cell is actionable, five consecutive attempts fail to fill a new cell, or the fitness-reserve boundary is reached.Source: §C.6.2 · p. 44
  • Fitness improvement cycles through archived rewrites from weakest objective score upward, attempting a compatible strategy and replacing an occupant only on a strictly higher score.Candidates are ultimately placed by their measured descriptors, so a best-effort attempt may land in a different cell than its target.Source: §C.6.2 · p. 44

D PREDICTION AND UNCERTAINTY SCORING

  • The frozen QA model answers each archived rewrite, but not the original context, once under a fixed prompt with greedy decoding; the first cleaned answer line is the prediction.Excluding the original prevents the answer whose correctness is being detected from entering the uncertainty signal.Source: D PREDICTION AND UNCERTAINTY SCORING · p. 45
  • Predictions are grouped first by normalized exact answer, then by bidirectional entailment from a frozen NLI model; connected components form semantic answer classes.The NLI model sees question-conditioned answer statements, not the context, gold answer, or failure label.Source: D PREDICTION AND UNCERTAINTY SCORING · p. 46

E EVALUATION PROTOCOL · F CONFIGURATION · G EDITOR PROMPT TEMPLATES

The evaluation protocol defines how answer failures and neighborhood uncertainty are scored, while the fixed configuration and editor prompts specify how rewrites are produced and controlled.

E EVALUATION PROTOCOL

  • Failure means an original-context prediction fails a permissive cascade of exact, normalized, containment, or bidirectional-entailment matching against any accepted gold answer.The cascade treats paraphrases of a gold answer as correct rather than inflating the failure set.Source: E EVALUATION PROTOCOL · p. 46
  • AUROC and AUPRC are macro-averaged across 25 dataset–model pairs; AUPRC is reported as lift over each pair’s base rate, with paired differences assessed by 2000 bootstrap replicates.The bootstrap resamples instances within each pair; reported SD, MIN, and MAX describe variation across pairs, not precision of the mean.Source: E EVALUATION PROTOCOL · pp. 46–47
  • Each pair contributes 1000 instances, and a method scores an instance only when it has at least two predictions, the minimum needed to define semantic entropy.No subselection is applied unless a table says otherwise; the restriction follows from semantic entropy’s definition, while original-context scores are defined on one prediction.Source: E EVALUATION PROTOCOL · p. 47

F CONFIGURATION

  • One configuration is held constant across datasets and QA models, with Table 39 listing settings for the editor, support-explicitness rule, fitness score, gates, and search.The passage identifies the configuration’s components but does not provide their values.Source: F CONFIGURATION · p. 47, Table 39 · p. 48

G EDITOR PROMPT TEMPLATES

  • The MAP-Elites prompt uses an A → B → C structure: A is the original validity reference, B is the context being rewritten, and C is the requested child.The query-specific edit program pairs a rewrite type with a prompt strategy, while the editor is instructed to preserve the fixed answer and its supporting evidence.Source: G EDITOR PROMPT TEMPLATES · p. 49
  • For offspring, the prompt specifies a parent-to-child edit delta, and the requested rewrite type takes precedence if it conflicts with the strategy guidance.When a parent is provided, the child must differ from it after Unicode and whitespace normalization.Source: G EDITOR PROMPT TEMPLATES · pp. 49–50
  • The broad edit contracts require adding an irrelevant distractor, reordering complete sentences, or rewriting substantive wording or syntax.Ten strategies supply mutation-magnitude guidance; examples include distractors near the answer, adjacent or global reordering, and direct support consolidation.Source: G EDITOR PROMPT TEMPLATES · pp. 50–51
  • The FP uses a separate fixed paraphrase prompt that rewrites the original context directly, without a parent, A → B → C structure, inheritance block, or per-strategy guidance.It shares the four-line output contract; only the edited context is consumed downstream, while the expected answer is checked against the gold answer but does not gate admission.Source: G EDITOR PROMPT TEMPLATES · pp. 51–52

H DATASETS

The study evaluates five extractive QA datasets spanning Wikipedia, coreference, news, naturally occurring information-seeking, and adversarial questions. Shared sampling and a uniform answer specification support consistent comparisons across datasets.

H DATASETS

  • Five extractive QA datasets span Wikipedia questions, coreference, news, naturally occurring information seeking, and model-adversarial questions; Table 40 reports their sampled-example statistics.The datasets are SQuAD v1.1 [Rajpurkar et al., 2016], Quoref [Dasigi et al., 2019], NewsQA [Trischler et al., 2017], Natural Questions from MRQA [Fisch et al., 2019], and AdversarialQA [Bartolo et al., 2020].Source: H DATASETS · p. 52, Table 40 · p. 53
  • Each constructor is evaluated on the same randomly sampled 1,000 answerable examples per dataset, with examples containing an empty context, question, or answer excluded.Sampling is without replacement using global seed 7, and all included samples have at least one gold answer.Source: H DATASETS · p. 52
  • A uniform answer specification treats any listed gold-answer string as correct, enabling answer-preservation checks and failure labels to apply consistently across datasets.The specification is created before validation or scoring, and matching follows the normalization described in Appendix D.Source: H DATASETS · p. 52
  • Per-dataset original-context accuracy is reported in Appendix B.7 to provide a failure-detection base rate for each dataset.Source: H DATASETS · p. 52

I GUARANTEES AND LIMITATIONS

The paper distinguishes properties enforced by construction from those it deliberately does not certify. Rewrite admission is independent of the QA model, while some labels are verified and meaning preservation, proxy quality, and bit-for-bit reproducibility are not guaranteed.

Guarantees and limitations

  • Every archived rewrite passes deterministic admission gates independent of the QA model; BERTScore ranks valid rewrites but cannot admit invalid ones.BERTScore can affect which valid rewrite is retained within a cell, not whether it passes admission.Source: I GUARANTEES AND LIMITATIONS · p. 53
  • NE, SBS, and FP verify that rewrites realize their requested edit type, whereas U-ME labels rewrite type by request alone.The rewrite-type axis is therefore a verified label for NE, SBS, and FP, but not for U-ME.Source: I GUARANTEES AND LIMITATIONS · p. 53
  • Meaning preservation, distractor irrelevance, objective quality, and bit-for-bit reproducibility are not certified.Support explicitness tracks cue location rather than preserved meaning; inserted distractors are checked only as new sentences, and ranking objectives are surface proxies. The editor uses no fixed per-call seed, so results are computed on each run’s archive as a fixed artifact; prompt-imposed properties are reported as requested, not verified.Source: I GUARANTEES AND LIMITATIONS · p. 53

Related papers

Loading 2610.40278v1…