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

Resumo Técnico: Seleção de Evidências Otimizada por QUBO para Resposta a Perguntas com Recuperação Aumentada

Declaração do Problema

Sistemas de Geração Aumentada por Recuperação (RAG) dependem da seleção de um conjunto apropriado de passagens de evidência para condicionar a geração da resposta. No entanto, os pipelines de recuperação padrão geralmente empregam uma abordagem de "recuperar-e-reclassificar" (retrieve-then-rerank), selecionando as $k$ melhores passagens com base em pontuações de relevância individuais. Essa estratégia frequentemente falha para perguntas de múltiplos saltos (multi-hop), onde a resposta exige a combinação de informações complementares distribuídas em múltiplas passagens. Embora métodos recentes baseados em Grandes Modelos de Linguagem (LLMs) tratem a recuperação como um problema de seleção de conjuntos para abordar isso, eles introduzem altos custos computacionais e dificuldades de escalonamento. Além disso, simplesmente aumentar o número de passagens recuperadas pode degradar o desempenho devido às limitações de comprimento de contexto e ao fenômeno "perdido no meio" (lost in the middle). O desafio central é selecionar um subconjunto compacto e não redundante de passagens que satisfaça coletivamente múltiplos requisitos de informação sem depender de inferência iterativa cara de LLM para a etapa de seleção em si.

Metodologia

Os autores propõem formular a seleção de evidências como um problema de Otimização Binária Quadrática Não Restrita (QUBO). Esta abordagem introduz uma camada de otimização estruturada entre as etapas de recuperação e geração de resposta.

1. Visão Geral do Pipeline:
O framework proposto opera em cinco estágios:

• Decomposição de Requisitos: A consulta de entrada é decomposta em requisitos de informação específicos.
• Agrupamento de Candidatos: Um pool de passagens candidatas é recuperado via recuperadores padrão (esparsos, densos ou híbridos).
• Pontuação: Pontuações semânticas são atribuídas às passagens em relação à relevância, força de suporte ao requisito e redundância/complementaridade par a par.
• Formulação QUBO: Essas pontuações parametrizam uma função objetivo QUBO.
• Solver e Geração: Um solver QUBO identifica o subconjunto binário ideal de passagens, que é então passado para um modelo de linguagem downstream para a geração da resposta.

2. Formulação QUBO:
O problema é definido sobre variáveis binárias $x_i \in \{0, 1\}$, onde $x_i=1$ indica a seleção da passagem $p_i$. A função objetivo $E(x)$ é projetada para minimizar a energia (maximizar a utilidade) equilibrando vários fatores:

• Relevância e Suporte: Recompensa passagens com altas pontuações de relevância ($s_i$) e aquelas que fornecem suporte direto ou parcial aos requisitos de informação ($r_j$).
• Cobertura: Incentiva a seleção de passagens que cubram todos os requisitos de informação gerados, distinguindo entre suporte parcial e direto.
• Redundância e Complementaridade: Penaliza pares de passagens que suportam requisitos sobrepostos (redundância) e recompensa pares que suportam requisitos diferentes ou complementares.
• Compactação: Penaliza a seleção de passagens que não suportam nenhum requisito e impõe uma restrição de orçamento sobre o número total de passagens selecionadas ($K$).

O problema de otimização restrita é convertido em uma forma QUBO não restrita através da introdução de variáveis de folga (slack variables) e termos de penalidade para restrições (ex: consistência de cobertura e limites de orçamento). O objetivo final é expresso como $\min v^\top Q v$, onde $v$ é um vetor de variáveis binárias (incluindo seleção de passagem, indicadores de cobertura e variáveis de folga) e $Q$ é a matriz de coeficientes.

3. Compatibilidade de Solver:
Ao converter o problema para QUBO, a etapa de seleção torna-se compatível com vários solvers não convencionais, incluindo simulated annealing, quantum annealers, digital annealers, máquinas de Ising coerentes e algoritmos quânticos de portão (gate-model). Isso separa a lógica de seleção combinatória da síntese semântica da resposta.

Principais Contribuições

• Formulação: O artigo apresenta a primeira formulação da seleção de contexto consciente de requisitos como um problema QUBO, tratando-o como um problema de seleção de subconjunto binário discreto em vez de uma tarefa de ranking ou prompting.
• Objetivo Unificado: Deriva uma função de energia única e compatível com solver que codifica conjuntamente relevância de passagem, cobertura de requisitos, força de suporte, redução de redundância, complementaridade, compactação e restrições de orçamento de seleção.
• Arquitetura Modular: Os autores propõem um pipeline que desacopla o pré-processamento semântico, a seleção de contexto combinatória e a geração de resposta, permitindo que cada componente seja substituído independentemente.
• Caminho de Hardware: O trabalho abre um caminho para o uso de hardware especializado em Ising/QUBO para a etapa de seleção, potencialmente oferecendo menor latência e eficiência energética em comparação com o reranking repetitivo baseado em LLM.

Resultados

O seletor QUBO proposto foi avaliado no cenário de distrator do HotpotQA (resposta a perguntas de múltiplos saltos) e comparado contra:

• Baselines baseados em LLM: Seletores do tipo SetR (SetR e SetRO) que usam LLMs para selecionar conjuntos de evidências diretamente.
• Baselines não-LLM: BM25, top-$k$ de relevância, Maximal Marginal Relevance (MMR), ranking léxico-semântico híbrido, cobertura gulosa (greedy coverage) e seleção aleatória.

Principais Descobertas:

• Desempenho vs. LLMs: O seletor QUBO alcançou pontuações competitivas de Exact Match (EM) e Token-F1 em relação aos seletores do tipo SetR. Especificamente, ficou dentro de 0,004 EM e 0,0064 F1 do baseline SetR. Notavelmente, o seletor QUBO alcançou a maior cobertura de requisitos entre os métodos comparados.
• Desempenho vs. Não-LLMs: O seletor QUBO igualou o melhor score de EM entre os baselines não-LLM e permaneceu próximo ao top-$k$ de relevância e ao MMR em F1, superando significativamente o BM25 e a seleção aleatória.
• Estudos de Ablação:
  • Nível de Resposta: Relevância e cobertura de requisitos foram identificadas como os maiores contribuintes para a precisão da resposta downstream. Embora o objetivo completo do QUBO inclua termos para estrutura (redundância, complementaridade), estes nem sempre se traduziram em pontuações de correspondência exata mais altas em comparação com objetivos de relevância mais simples, sugerindo um trade-off entre qualidade estrutural e métricas imediatas de resposta.
  • Nível de Conjunto: O objetivo completo do QUBO controlou com sucesso a estrutura do conjunto de evidências, selecionando subconjuntos mais compactos e de maior utilidade em comparação com variantes que removeram penalidades de redundância ou de passagens não suportadas.

Significância e Alegações

O artigo alega que a seleção de evidências de múltiplos saltos pode ser efetivamente formulada como um problema de otimização discreta estruturada. A principal significância reside na modularidade da abordagem: ela permite que a etapa de seleção combinatória, computacionalmente cara, seja transferida para solvers especializados em QUBO/Ising (clássicos ou inspirados em quantum), reservando os LLMs primariamente para medição semântica e geração de resposta.

Os autores mantêm uma postura modesta, observando que, embora não assumam um speedup quântico universal, a formulação fornece uma representação "compatível com solver" que é atraente para pipelines RAG de larga escala, onde os pools de candidatos e as interações par a par crescem com o tamanho do corpus. O trabalho sugere um direcionamento futuro onde pipelines de recuperação utilizem hardware não convencional para a etapa de seleção para alcançar menor latência e, potencialmente, melhor eficiência energética, sem sacrificar a qualidade competitiva da resposta fornecida pelos atuais métodos de seleção baseados em LLM.