Coverage, Not Averages: Semantic Stratification for Trustworthy Retrieval Evaluation

1. Problem Statement

The paper identifies a critical flaw in current Retrieval-Augmented Generation (RAG) evaluation methodologies: the reliance on aggregate metrics (e.g., mean nDCG) derived from heuristically constructed query sets.

• Hidden Bias: Standard benchmarks (like BEIR) assume query homogeneity, but real-world query distributions are structurally heterogeneous.
• Coverage Gaps: Empirical analysis reveals that standard evaluation sets often fail to cover significant semantic regions of the document corpus. High-volume semantic clusters (e.g., specific medical methodologies) may receive zero or negligible query coverage.
• Consequences:
  • Biased Estimates: Aggregate metrics are dominated by overrepresented regions, masking systematic failures in underrepresented but prevalent domains.
  • Misleading Confidence: Standard variance estimation (e.g., bootstrapping) is invalid because it ignores the structural heterogeneity of the query space, leading to overly optimistic uncertainty estimates.
  • Unstable Decision Making: System selection based on aggregate scores can be arbitrary, as small changes in query distribution can flip rankings between models.

2. Methodology: Semantic Stratification Framework

The authors propose Semantic Stratification, a framework that treats retrieval evaluation as a stratified statistical estimation problem. The goal is to ensure explicit coverage across the corpus's semantic and structural dimensions.

A. Theoretical Formalization

• Retrieval Regimes: The query space $Q$ is partitioned into distinct regimes $\{S_k\}$ based on semantic and structural properties.
• Statistical Model: The true performance $\mu$ is defined as a weighted sum of regime-level means: $\mu = \sum w_k \mu_k$.
• Bias Analysis: The paper proves that if a regime $S_k$ is missing from the evaluation set ($\hat{w}_k = 0$), the bias is irreducible regardless of dataset size. Aggregate metrics obscure these gaps.

B. Practical Implementation (Three-Step Process)

1. Corpus-Level Semantic Structure Construction:

   • Entity Extraction: Uses an LLM to extract atomic, normalized semantic entities (name + description) from documents.
   • Semantic Graph: Constructs a graph where nodes are entities and edges represent semantic similarity (via cosine similarity of embeddings).
   • Clustering: Applies the Leiden algorithm to the graph to identify coherent semantic communities (clusters). Each document is associated with the clusters containing its entities.

2. Query Stratification:
   The framework defines regimes along two axes:

   • Semantic Strata: Directly derived from the corpus-level semantic clusters.
   • Structural Strata: Defined by two signals characterizing retrieval difficulty:
     • Relevance Dispersion ($\Delta$): Measures how widely relevant documents for a query are spread across different semantic clusters. High dispersion implies ambiguous/broad needs.
     • Query-Document Semantic Alignment ($J$): Measured via Jaccard similarity between query entities and relevant document entities. Low alignment implies a semantic mismatch.
   • These signals create a $3 \times 3$ grid (Low/Med/High) for each semantic stratum, creating distinct difficulty regimes.

3. Evaluation Dataset Curation:

   • Coverage-Aware Generation: An iterative process generates new queries to fill "coverage gaps."
   • Algorithm: The system identifies underrepresented strata (based on entity clusters, dispersion, and alignment), samples seed documents, and uses an LLM to generate queries targeting those specific gaps.
   • Verification: Generated queries and their relevance judgments ($qrels$) are verified by LLMs to ensure quality and alignment with the target stratum.

3. Key Contributions

1. Problem Identification: Formalized the issue of structural heterogeneity in retrieval evaluation, demonstrating that ignoring it leads to biased metrics and misleading confidence intervals.
2. Methodological Framework: Introduced Semantic Stratification, a coverage-aware framework grounded in corpus structure (entity-based clustering) that guarantees evaluation across semantic and structural regimes.
3. Empirical Validation: Validated the framework across multiple datasets (NFCorpus, FiQA, SciDocs) and retrieval methods (Dense, Sparse, Hybrid), showing that stratified evaluation reveals failure modes invisible to aggregate metrics.

4. Experimental Results & Insights

Experiments were conducted on BEIR datasets (NFCorpus, FiQA, SciDocs) using Dense (text-embedding-3-large), Sparse (BM25), and Hybrid retrieval.

• Coverage Gaps: Standard benchmarks leave 40–50% of semantic regions untested.
  • Example: In NFCorpus, 182 semantic clusters (containing 1,700+ documents on statistical methods) had zero evaluation queries in the original benchmark.
  • Impact: Stratified evaluation increased Minimum Semantic Coverage (MSC) from ~51% to 90% and Sufficient Corpus Coverage (SCC) from 11% to 53%.
• Performance Heterogeneity:
  • Performance varies significantly across strata (up to 3x difference).
  • Structural Signals: Relevance dispersion ($\Delta$) primarily impacts ranking quality (nDCG), while semantic alignment ($J$) primarily impacts coverage (Recall).
• Failure Mode Diagnosis: Stratified evaluation exposed specific failure patterns:
  • Semantic-Lexical Disconnect: Queries about locations (e.g., "Arkansas") were judged relevant to documents discussing research in that location, even if the name never appeared in the text (unanswerable by retrieval alone).
  • Register Mismatch: Colloquial queries (e.g., "Raw Food Diet Myths") failed against scientific documents due to vocabulary gaps.
  • Zero-Query Blind Spots: Retrieval performance on "Statistical Methods" was found to be significantly lower than aggregate scores suggested, while "Cancer Cell Lines" performed well but was previously untested.
• Decision Stability: When comparing two embedding models, the "winner" flipped depending on the aggregation method (Query-weighted mean vs. Macro-average). Stratified evaluation makes these trade-offs explicit, allowing practitioners to choose based on actual priorities (e.g., caring equally about all semantic regions).

5. Significance

• Trustworthy Evaluation: Moves the field away from "black box" aggregate scores toward transparent, interpretable performance profiles.
• Systematic Diagnosis: Enables developers to pinpoint why a system fails (e.g., specific semantic domains or structural difficulties) rather than just knowing that it fails.
• Better Decision Making: Provides a robust basis for selecting retrieval systems by exposing the risks of deploying models that perform well on benchmarks but fail in underrepresented, high-risk domains.
• Reproducibility: The authors commit to releasing the stratified datasets and code to support future research in coverage-aware evaluation.

In summary, the paper argues that coverage is more important than averages. By structuring evaluation around the inherent semantic and structural complexity of the corpus, researchers can build more reliable, trustworthy, and actionable RAG systems.