Principled and Scalable Diversity-Aware Retrieval via Cardinality-Constrained Binary Quadratic Programming

Título

Recuperação Consciente de Diversidade Principiada e Escalável via Programação Quadrática Binária com Restrição de Cardinalidade

1. Problema

A recuperação aumentada por geração (RAG) enfrenta um desafio fundamental: os métodos padrão de recuperação top-k tendem a selecionar passagens semanticamente redundantes, desperdiçando a janela de contexto limitada dos Grandes Modelos de Linguagem (LLMs). Embora métodos existentes como MMR (Maximal Marginal Relevance) e DPP (Processos Pontuais Determinantal) tentem mitigar isso, eles possuem limitações críticas:

• MMR: Utiliza um algoritmo ganancioso que não oferece garantias de aproximação para funções submodulares não monótonas e possui complexidade temporal linear em relação ao número de passagens recuperadas ($O(knd)$), tornando-se um gargalo de escalabilidade.
• DPP: A inferência exata é NP-difícil. As aproximações existentes têm complexidade super-linear ou quartica em relação a $k$, e o parâmetro de trade-off entre relevância e diversidade é difícil de interpretar e ajustar.

À medida que os LLMs suportam janelas de contexto maiores, a necessidade de recuperar um número maior de passagens diversas ($k$ elevado) exacerba esses problemas de eficiência.

2. Metodologia

Os autores propõem uma formulação principiada do problema de recuperação diversificada como um Programa Quadrático Binário com Restrição de Cardinalidade (CCBQP).

• Formulação do Objetivo: O objetivo é maximizar uma função que equilibra a relevância para a consulta e a diversidade semântica entre as passagens selecionadas, controlada por um parâmetro de trade-off interpretável $\theta \in [0, 1]$. A função objetivo penaliza a similaridade cosinética total entre os pares selecionados.
• Relaxação Contínua Apertada: Reconhecendo que o CCBQP é NP-difícil, os autores propõem uma relaxação contínua não convexa e apertada. Eles demonstram teoricamente que, sob condições realistas (como a ausência de vetores perfeitamente anti-alinhados no espaço de embeddings), o relaxamento é "apertado" (tight), ou seja, os maximizadores globais do problema relaxado contínuo são integrais (binários), eliminando a necessidade de etapas de arredondamento.
• Análise da Paisagem de Otimização: A análise teórica revela que a paisagem de otimização do problema relaxado é benigna: todos os pontos estacionários que não são maximizadores locais são pontos de sela estritos com curvatura positiva explícita. Além disso, todos os maximizadores locais são integrais.
• Algoritmo de Otimização (Frank-Wolfe):
  • Utilizam o algoritmo Frank-Wolfe com busca de linha exata (Exact Line Search).
  • Otimização de Desempenho: Para evitar o gargalo do cálculo de Lipschitz (que seria catastrófico devido à alta dimensionalidade dos embeddings), eles utilizam a busca de linha exata, que possui solução de forma fechada para funções quadráticas.
  • Aceleração via Esparsidade: Otimizam a multiplicação matriz-vetor explorando a esparsidade do vetor de direção, reduzindo a complexidade de $O(nd)$ para $O(kd)$ em etapas específicas, resultando em uma escalabilidade sub-linear em relação a $k$ na prática.

3. Principais Contribuições

1. Formulação do Problema: Introdução de uma formulação CCBQP para recuperação em RAG que balanceia explicitamente relevância e diversidade através de um parâmetro $\theta$ interpretável.
2. Análise Teórica: Desenvolvimento de uma relaxação contínua não convexa com garantias de que a solução ótima é integral, juntamente com uma análise de convergência e da paisagem de otimização que garante a ausência de ótimos locais espúrios não integrais.
3. Algoritmo Escalável: Proposta de um algoritmo baseado em Frank-Wolfe com busca de linha exata e otimizações de implementação que oferecem aceleração significativa.
4. Avaliação Empírica: Demonstração experimental de superioridade em relação aos baselines (MMR e DPP) tanto na qualidade da recuperação quanto na eficiência computacional.

4. Resultados Experimentais

Os experimentos foram conduzidos nos conjuntos de dados ASQA e QAMPARI com tamanhos de recuperação $k \in \{25, 50, 100\}$.

• Eficiência (RQ1): O método proposto exibe uma escalabilidade sub-linear em relação a $k$, enquanto o MMR escala linearmente e o DPP super-linearmente.
  • Para $k=100$, o método proposto foi 2,4x a 22,9x mais rápido que o MMR.
  • A latência por consulta caiu de >850 ms (MMR/DPP) para 40-180 ms.
• Qualidade de Recuperação (RQ2): O método domina consistentemente a fronteira de Pareto de relevância-diversidade. Ele consegue manter alta relevância (Recall) enquanto maximiza a diversidade (medida por ILAD - Intra-List Average Distance), superando os baselines que sacrificam recall global para satisfazer restrições locais de diversidade.
• Qualidade de Geração (RQ3): Experimentos end-to-end com LLMs (Llama-3.1-8B) mostraram que a recuperação diversificada melhora consistentemente a qualidade da geração (F1), especialmente quando o parâmetro $\theta$ é ajustado para um regime prático ($\theta \ge 0.5$). A diversidade excessiva ($\theta$ muito baixo) pode prejudicar a precisão ao remover fatos de base, mas um equilíbrio moderado traz ganhos consistentes sobre a recuperação top-k padrão.

5. Significado e Conclusão

Este trabalho oferece uma solução robusta e escalável para o problema de redundância semântica em sistemas RAG. Ao reformular o problema como um CCBQP e resolver através de uma relaxação contínua com garantias teóricas e um algoritmo Frank-Wolfe otimizado, os autores superam as limitações de escalabilidade e interpretabilidade dos métodos atuais (MMR e DPP).

A capacidade de recuperar grandes volumes de passagens diversas com baixa latência torna essa abordagem essencial para pipelines de RAG modernos que utilizam janelas de contexto massivas, permitindo que os LLMs acessem informações mais completas e variadas sem comprometer o desempenho de inferência.