SUNAR : Semantic Uncertainty based Neighborhood Aware Retrieval for Complex QA (2025)

Abstract: Complex question-answering (QA) systems face significant challenges in retrieving and reasoning over information that addresses multifaceted 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. Our code and data are anonymously available at https://anonymous.4open.science/r/SUNAR-8D36/.

## introduction open-domain complex question answering (cqa) has emerged as a critical challenge in natural language processing, demanding systems to comprehend, reason, and synthesize information over multiple queries and from multiple sources. while effective for simpler queries, traditional retrieveand-reason pipelines struggle with the multifaceted nature of complex qa tasks. complex qa systems typically involve multiple stages: query understanding, retrieval of relevant documents, and a reasoning phase that may or may not leverage large language models (llms). however, the effectiveness of these systems is typically bounded by the recall of the retrieval stage. specifically, if relevant documents are missed during this stage, they cannot be incorporated later, leading to a decline in overall system performance. this bounded-recall problem is more prominent in complex question answering where the initial question comprises multiple sub-questions that necessitate a retrieval for each sub-question @xcite . failing to retrieve relevant documents to answer a sub-question, causes cascading failures that result in suboptimal performance of cqa systems. furthermore, the limited context windows of llms necessitate a focus on recall at smaller retrieval depths. existing retrieval literature primarily focuses on improving precision at higher retrieval depths by either employing re-rankers @xcite , or using improving the llm-reasoning by using self-correction mechanisms and decomposition strategies @xcite @xcite . while these efforts led to notable improvements in performance in comparison to the standard open-domain qa baselines, the recall problem still persists as shown in figure 1 . in this paper, we propose a novel method to bridge the recall gap by employing llm feedback to guide the retrieval process. our method is grounded on the clustering hypothesis, a wellknown concept in information retrieval, that states that documents that are semantically similar to a relevant document tend to answer the same query @xcite . recently in the ir literature, there have been initial attempts to exploit this idea to improve retrieval using better assessments from a re-ranker @xcite @xcite . we propose a neighborhood aware retrieval procedure that judiciously explores related documents of the initially retrieved documents leveraging the interim feedback of llm-based answering system based on semantic uncertainty of potential answers. in our approach, sunar (semantic uncertainty based neighborhood aware retrieval) we first compute a neighborhood graph based on semantic similarities between documents. during the query processing phase, we judiciously explore the neighborhood graph of the retrieved documents to use in the llm prompt as context. central to our method is the hypothesis that better document rankings correlate with lower uncertainty in the llm-generated answer candidates. we quantify this uncertainty and use it as feedback to promote or penalize documents during retrieval dynamically. by integrating llm-based signals into the neighborhood aware retrieval process, we effectively bootstrap the retrieval of relevant context, enhancing the overall system performance. we conduct extensive experiments on two opendomain complex qa datasets to evaluate our approach. our results show significant improvements over existing retrieve-and-reason baselines, with an increase in performance of up to 20% on wqa and up to 31.84% on mqa. to contextualize our performance, we close the performance gap with an idealized upper bound from 43% to 19% on wqa foot_0 . our experiments also show that sunar can be retrofitted to llm-based reasoning approaches @xcite , to improve their performance further. ## methodology the common approach to performing open-domain qa tasks typically follows a two-step process: retrieval of relevant contexts, followed by a reasoning or qa step using those retrieved contexts. this is exemplified by traditional rag pipelines @xcite . for simpler or direct questions, this method is often sufficient. however, complex questions tend to consist of multiple subquestions, which requires more advanced query understanding steps, such as decomposing the main question into sub-questions prior to retrieval. in this context, given a complex question @xmath0, the decomposition process can be formally defined as: de(q, a) = {(sq 1 , r 1 , sa 1 ), . . . , (sq k , r k , sa k )} where @xmath1,a) represents the number of subquestions, (sq i , sa i ) is the pair of sub-question and corresponding answer, and r i is a list of top-l ranked documents (with @xmath2. after decomposing the complex question into sub-questions, the retrieval step is followed by a ranking phase, typically performed by a fine-tuned model. this ranking is critical due to the limited input budget of large language models (llms), which restricts the amount of information they can process at once. the ranking helps prioritize the most relevant documents for the final reasoning step. finally, in the reasoning phase, the llm processes the ranked and retrieved contexts to generate the final answer. in this work, algorithm 1 the sunar algorithm input: initial retrieved list r, batch size b, re-ranking budget c, document graph g output: re-ranked pool r + 1: r + ← ∅ ▷ re-ranking results 2: c ← r ▷ candidate pool 3: n ← ∅ ▷ neighbor pool 4: do 5: b ← score(top b from c, subject to c) 6: {sa1...sam} ← ϕ(pllm (sq1, b)) 7: {ac1..acs} ← σ(sa1..sam) ▷ clustering 8: 9: b ← rescore(b,1/s) ▷ rescore batch 10: r + ← r + ∪ b ▷ add batch to results 11: 12: // discard batches 13: r ← r \ b 14: n ← n \ b 15: n ← n ∪ (neighbours(b, g) \ r + ) 16: 17: //alternate r and n 18: ## experimental setup we answer the following research questions: rq i. can nar improve the recall for better complex qa? rq ii. can llm-guided nar improve overall complex qa performance compared to existing state-of-the-art? rq iii. how well does sunar work across different llm substrates and with different reasoning approaches? datasets: we experiment on well-known qa datasets that require compositional reasoning, namely musique (mqa) @xcite and 2wikimultihopqa (wqa) @xcite . it has been observed that multi-hop datasets like hot-method mqa wqa methods (w/o query understanding) zero-shot-cot @xcite 8.62 30.42 few-shot-cot @xcite 15.02 32.83 few-shot-cot +prf @xcite 16.69 35.55 sunarr (ours) 21.32 40.96 methods (w/ query understanding) self-rag @xcite 17.80 35.25 react @xcite 21.41 43.25 decomp @xcite 21.01 44.08 ircot @xcite 24.12 42.01 searchain @xcite 21.72 44.42 self-ask +prf @xcite 20.28 44.58 self-ask @xcite 24 potqa @xcite do not necessitate connected reasoning and can be answered using single hop @xcite . however, mqa and wqa are designed in a manner that mandates compositional/multi-step reasoning. following @xcite , we employ the 2-hop questions from mqa leading to 1252 questions for evaluation. for wqa we evaluate on the sampled 1200 questions following self-ask @xcite . combining the contexts with distractors from mqa and wqa following the setup of @xcite results in a corpus of 569461 documents. ## limitations although sunar offers significant performance improvements over existing off-the-shelf rag pipelines, there are a few limitations that offer avenues for future work. though nar is based on the philosophy of adaptive retrieval which is more efficient than exhaustive re-ranking, a more principled selection of candidates for ranking in line 18 of algorithm 1 with early stopping criterion could make it more efficient. we defer this for future work as it is beyond the scope of current work. for instance, the llm based feedback now relies on computing semantic sets, which serve as a proxy for consistency in llm answers for a given set of evidences. more principled conformal prediction based approaches could be adopted to calibrate llm confidence for answers generated and use the measure for penalizing/promoting documents. we also defer this for future work. ## ethical considerations and risks we primarily propose a novel uncertainty based neighborhood aware retrieval approach for complex qa tasks. we use only publicly available qa datasets from wikipedia that do not contain private or harmful information. while we employ llms for qa systems in our experiments, we do not prompt them in a format that would elicit harmful or biased information. all our prompts are reported in appendix f. our tool is intended to enhance answering engines to aid users in their complex questions.