Context Selection as a QUBO: Notes Toward Quantum-Enhanced RAG

Every RAG system makes the same decision thousands of times a day: given these candidate passages and a token budget, which ones go into the prompt?

Most systems answer with top-k by cosine similarity. That's fast, but it's a poor objective. It happily selects five near-identical passages and misses the one complementary fact a multi-hop question needs.

The optimisation hiding in plain sight

What we actually want is a set of passages that is relevant, non-redundant, and fits the budget. Let xᵢ ∈ indicate whether passage i is selected. Then:

minimise   − Σᵢ rᵢ xᵢ            (reward relevance)
           + λ Σᵢ<ⱼ sᵢⱼ xᵢ xⱼ     (penalise redundancy)
           + μ (Σᵢ tᵢ xᵢ − T)²    (soft token-budget constraint)

where rᵢ is query relevance, sᵢⱼ is passage–passage similarity and tᵢ is passage length. Expand it and every term is linear or quadratic in binary variables. That's a QUBO — the native input format for quantum annealers and for QAOA on gate-model machines.

Why it's still worth studying

Problem size is naturally bounded. A re-ranking stage typically considers 20–100 candidates — within reach of today's annealers and simulable QAOA.
The objective is honest. Even if a classical solver wins, framing selection as joint optimisation beats greedy top-k. The quantum question forces a better classical baseline.
It composes. The same formulation extends to diversity across sources, citation coverage, or fairness constraints, just by adding terms.

Our experiment (EXP-014)

We compare four selectors at equal token budget on multi-hop question sets: top-k, MMR, an exact classical QUBO solver, and QAOA/annealing. We measure answer faithfulness, citation precision and redundancy — and wall-clock latency, which is the metric most papers forget.

Early observation: the formulation drives most of the quality gain; solver choice matters mainly at the edges of the budget constraint. Which is exactly the kind of result we think the field needs more of.