SUNAR: Semantic Uncertainty based Neighborhood Aware Retrieval for Complex QA

Venktesh V, Mandeep Rathee, Avishek Anand

Abstract

Complex question-answering (QA) systems face significant challenges in retrieving and reasoning over information that addresses multi-faceted queries. While large language models (LLMs) have advanced the reasoning capabilities of these systems, the bounded-recall problem persists, where procuring all relevant documents in first-stage retrieval remains a challenge. Missing pertinent documents at this stage leads to performance degradation that cannot be remedied in later stages, especially given the limited context windows of LLMs which necessitate high recall at smaller retrieval depths. In this paper, we introduce SUNAR, a novel approach that leverages LLMs to guide a Neighborhood Aware Retrieval process. SUNAR iteratively explores a neighborhood graph of documents, dynamically promoting or penalizing documents based on uncertainty estimates from interim LLM-generated answer candidates. We validate our approach through extensive experiments on two complex QA datasets. Our results show that SUNAR significantly outperforms existing retrieve-and-reason baselines, achieving up to a 31.84% improvement in performance over existing state-of-the-art methods for complex QA.

Introduction: The Bounded-Recall Problem

In complex Question Answering (CQA), a single query often requires synthesizing information from multiple sources (e.g., "Who was born later, the director of film X or the screenwriter of film Y?"). Current Retrieval-Augmented Generation (RAG) systems usually follow a "retrieve-then-read" pipeline but face two major hurdles:

  1. The Bounded-Recall Problem: If the first-stage retriever (like BM25 or a dense encoder) doesn't put the necessary documents in the top results, the LLM never sees them.
  2. Context Constraints: LLMs have limited context windows. We need high recall at very small retrieval depths (e.g., the top 10 documents), but traditional methods often require looking at hundreds of documents to find the relevant ones.

Standard fixes like Pseudo-Relevance Feedback (PRF) often suffer from "query drift," where the search becomes increasingly irrelevant as it moves away from the original question.

Methodology: SUNAR Architecture

SUNAR (Semantic Uncertainty based Neighborhood Aware Retrieval) reimagines retrieval as an iterative, graph-based exploration guided by the LLM’s own internal "confidence."

Comparison of Standard CQA vs. SUNAR architecture, highlighting neighborhood-based document selection.

1. Neighborhood Aware Retrieval (NAR)

Grounded in the "clustering hypothesis"—the idea that documents semantically similar to a relevant document are likely relevant themselves—SUNAR uses a pre-computed Neighborhood Graph.

  • Offline: It builds a graph where nodes are documents and edges connect the top-$k$ nearest neighbors (using a model like ColBERTv2).
  • Online: Instead of just searching for the query, SUNAR iteratively explores the neighbors of high-scoring documents. This allows the system to "hop" to relevant documents that might not share keywords with the original query but are contextually related to intermediate findings.

2. Semantic Uncertainty Feedback (ASU)

To decide which documents to promote, it uses Answer Semantic Uncertainty (ASU). The LLM generates multiple candidate answers for a sub-question based on a batch of retrieved documents. The system groups these answers into "semantic sets" using bi-directional entailment. If the LLM produces many different, non-equivalent answers, it is "uncertain," suggesting the documents provided are likely distractors. Consistent answers imply relevant documents, which are then promoted.

Finally, a Meta Evidence Reasoner (MER) looks at the entire reasoning path and all gathered evidence at once to produce the final answer, preventing errors from cascading through the multi-hop chain.

Evaluation and Key Insights

The authors evaluated SUNAR on two rigorous complex QA benchmarks: MuSiQue (MQA) and 2WikiMultiHopQA (WQA), using a massive collection of ~569,000 documents.

One of the most clever insights is using the variance of LLM outputs as a ranking signal. Instead of asking the LLM "is this document relevant?" (which is prone to hallucination), they measure how much the LLM "wobbles." Consistency implies a solid evidentiary foundation. Furthermore, SUNAR treats retrieval as a 1-to-Many-to-Many exploration, leveraging document-to-document relationships to find evidence that the initial query was too "blind" to see.

Results

SUNAR consistently outperformed baselines like Self-Ask, ReAct, and SearchChain across multiple LLM backbones (GPT-3.5, GPT-4o-mini, Llama 3.1, and Mistral).

Performance comparison of SUNAR against baselines and the idealized upper bound on WQA and MQA datasets.
  • Performance Boost: On the MuSiQue (MQA) dataset, SUNAR achieved a score of 32.75 (cover-EM), a massive jump from the 24.84 achieved by the previous state-of-the-art (Self-Ask).
  • Closing the Gap: SUNAR significantly narrows the gap between automated systems and an "Idealized Upper Bound" (where the system is given perfectly relevant context). On WQA, it closed the performance gap from 43% down to 19%.
  • Ablation Success: Removing the ASU (uncertainty) component led to a noticeable drop in performance, proving that LLM feedback is essential for filtering out the "noise" introduced by exploring the neighborhood graph.

Conclusion and Future Work

While SUNAR achieves state-of-the-art results, generating multiple answers to estimate uncertainty is computationally expensive. The authors acknowledge the need for more efficient candidate selection to reduce the number of LLM calls. Future work also includes exploring dynamic graph updates or different types of relationship edges (e.g., temporal or hierarchical) to further enhance retrieval accuracy.

Summary updated

Abstract

Complex question-answering (QA) systems face significant challenges in retrieving and reasoning over information that addresses multi-faceted queries. While large language models (LLMs) have advanced the reasoning capabilities of these systems, the bounded-recall problem persists, where procuring all relevant documents in first-stage retrieval remains a challenge. Missing pertinent documents at this stage leads to performance degradation that cannot be remedied in later stages, especially given the limited context windows of LLMs which necessitate high recall at smaller retrieval depths. In this paper, we introduce SUNAR, a novel approach that leverages LLMs to guide a Neighborhood Aware Retrieval process. SUNAR iteratively explores a neighborhood graph of documents, dynamically promoting or penalizing documents based on uncertainty estimates from interim LLM-generated answer candidates. We validate our approach through extensive experiments on two complex QA datasets. Our results show that SUNAR significantly outperforms existing retrieve-and-reason baselines, achieving up to a 31.84% improvement in performance over existing state-of-the-art methods for complex QA.
BibTeX
@inproceedings{v2025sunar,
  author = {Venktesh V and Mandeep Rathee and Avishek Anand},
  title = {{SUNAR: Semantic Uncertainty based Neighborhood Aware Retrieval for Complex QA}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2025},
  doi = {10.18653/v1/2025.naacl-long.300},
}
Figure