SUNAR: Semantic Uncertainty based Neighborhood Aware Retrieval for Complex QA

Venktesh V, Mandeep Rathee, Avishek Anand

Abstract

Complex Question Answering (CQA) often requires multi-hop reasoning across multiple documents. Current Retrieval-Augmented Generation (RAG) systems frequently fail due to the "bounded-recall" problem, where missing a single piece of evidence breaks the reasoning chain. We present SUNAR, a framework that integrates neighborhood-aware graph exploration with LLM-based semantic uncertainty estimates. SUNAR achieves significant performance improvements, notably a 31.84% boost over state-of-the-art methods on challenging benchmarks.

Introduction

The "Retrieve-and-Reason" pipeline is the standard for modern QA. However, in Complex QA (CQA), the reasoning stage is limited by the quality of the initial retrieval. If a retriever fails to surface even one necessary document for a multi-hop query, the Large Language Model (LLM) cannot recover the answer. This "bounded-recall" problem is the primary bottleneck in CQA.

Methodology: The SUNAR Framework

SUNAR (Semantic Uncertainty based Neighborhood Aware Retrieval) addresses retrieval limitations through three core innovations:

1. Neighborhood Aware Retrieval (NAR)

NAR leverages the "clustering hypothesis"—the idea that semantically similar documents are often relevant to the same queries. SUNAR constructs an offline document-neighborhood graph. During retrieval, it iteratively explores the neighbors of high-scoring documents, bridging the gap when a document's text doesn't perfectly match the query but is semantically related to other relevant evidence.

2. Answer Semantic Uncertainty (ASU)

To filter out distractors, SUNAR uses the LLM to generate multiple candidate answers for a sub-query based on a specific document. High semantic variance (uncertainty) among these answers suggests the document is noisy or irrelevant. Conversely, consistent answers signal a high-quality document.

3. Meta Evidence Reasoner (MER)

MER serves as a post-hoc correction layer, analyzing the entire reasoning path and all gathered evidence simultaneously to mitigate cascading errors from earlier steps.

The SUNAR architecture compared to standard CQA pipelines, highlighting the neighborhood-based selection process.

Experimental Evaluation

SUNAR was evaluated on two multi-hop QA benchmarks: MuSiQue (MQA) and 2WikiMultiHopQA (WQA), using a corpus of over 560,000 documents.

Key Results

SUNAR consistently outperformed established baselines such as Self-Ask, ReAct, and Searchain. On the MuSiQue dataset, SUNAR achieved a score of 32.75 (cover-EM), a substantial improvement over the 24.84 achieved by Self-Ask.

Comprehensive performance comparison of SUNAR against various baseline methods on MQA and WQA datasets.

The framework also demonstrated significant recall improvements. On MQA, SUNAR's Recall@10 reached 0.459, nearly doubling the 0.240 achieved by standard retrieval methods. Furthermore, the approach proved LLM-agnostic, showing gains across models like GPT-4o-mini, Llama 3.1, and Mistral v0.2.

Discussion and Limitations

While SUNAR provides a robust solution to the recall gap, it introduces higher computational costs due to the multiple LLM calls required for the ASU component. Additionally, the offline neighborhood graph requires updates as the corpus evolves. Future research may focus on more efficient uncertainty estimation techniques, such as conformal prediction, to reduce latency.

Conclusion

SUNAR demonstrates that improving retrieval recall at small depths is more impactful for CQA than simply scaling model size. By combining graph-based proximity with semantic uncertainty, SUNAR effectively overcomes the bounded-recall problem in multi-hop reasoning.

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