QUBO-Optimized Evidence Selection for Retrieval-Augmented Question Answering with Unconventional Solvers

Research Approach

Retrieval-Augmented Generation (RAG) systems often struggle with multi-hop questions because standard top-k retrieval methods prioritize individual passage relevance over the collective utility of a set of passages. To address this, the authors propose a modular pipeline that treats evidence selection as a combinatorial optimization problem. By decomposing a query into specific information requirements, the system constructs a QUBO objective function that balances relevance, requirement coverage, support strength, redundancy, and compactness. This formulation allows the selection process to be offloaded to specialized hardware—such as quantum annealers or Ising machines—separating the heavy lifting of context selection from the semantic task of answer generation.

Methodology

The core of the method is the construction of a QUBO matrix that encodes the relationships between candidate passages and query requirements. Each passage is represented by a binary variable, and the objective function includes:

• Linear terms: Rewards for relevance and requirement support, and penalties for selecting irrelevant passages.
• Quadratic terms: Penalties for redundancy (based on overlapping requirements) and rewards for complementarity (selecting passages that cover different requirements).
• Constraints: Slack variables are used to enforce a strict context budget and ensure that requirements are only marked as 'covered' if the corresponding evidence is selected.

Once the QUBO instance is solved, the resulting binary configuration identifies the optimal subset of passages, which is then passed to a downstream language model to generate the final answer.

This work provides a bridge between high-level RAG pipelines and low-level discrete optimization. By casting evidence selection as a QUBO problem, the authors enable the use of unconventional, energy-efficient hardware for the most computationally intensive part of the retrieval process. This modularity suggests a future where LLMs are reserved for complex reasoning and generation, while the combinatorial task of filtering large document corpora is handled by specialized solvers, potentially reducing latency and costs in large-scale RAG deployments.