Resumo Técnico: Aprendizes Ativos como Rerankers Eficientes de PRP

Declaração do Problema

Na Geração Aumentada por Recuperação (RAG), Modelos de Linguagem de Grande Escala (LLMs) são cada vez mais empregados para reranquear documentos candidatos recuperados por um recuperador de primeira etapa. A abordagem padrão, Prompting de Ranqueamento Pares (PRP), elicita julgamentos de preferência par a par de um LLM e as agrega em uma classificação usando algoritmos de ordenação clássicos (por exemplo, BubbleSort, QuickSort, HeapSort).

No entanto, esse pipeline sofre de uma incompatibilidade estrutural. Algoritmos de ordenação assumem comparações transitivas e determinísticas, enquanto os julgamentos de LLMs são estocásticos, ruidosos e frequentemente intransitivos. Além disso, LLMs exibem efeitos de ordem significativos (viés de posição), onde trocar a ordem de apresentação dos documentos pode inverter a preferência. Para mitigar isso, o PRP padrão frequentemente emprega prompting bidirecional (duas chamadas por par), o que dobra o custo de inferência.

O problema central é que a ordenação visa recuperar uma permutação completa, ainda que, em aplicações de RAG, o objetivo seja tipicamente um subconjunto de alta qualidade dos top-$K$. Sob um orçamento estrito de chamadas de LLM (onde custo e latência são dominados pela inferência), a ordenação desperdiça recursos "polindo" uma permutação global instável em vez de focar na identificação dos itens top-$K$. Adicionalmente, a suposição de transitividade leva a classificações pouco confiáveis quando as comparações subjacentes são ruidosas.

Metodologia

Os autores reformulam o reranking PRP como um problema de aprendizado ativo focado na identificação dos melhores-$K$ itens a partir de comparações par a par ruidosas, em vez de ordenar a lista inteira.

1. Framework de Ranqueamento Ativo

Em vez de um cronograma de ordenação fixo, a abordagem proposta seleciona adaptativamente quais pares de documentos consultar para maximizar a qualidade do prefixo top-$K$ dentro de um orçamento fixo de chamadas ($B$). O framework baseia-se em três critérios:

• Objetivo Top-$K$: O algoritmo visa a identificação dos melhores-$K$ itens (identificação de prefixo) em vez de uma ordem global completa.
• Tolerância a Ruído: O método opera sob consistência de par ($p_{ij} = 1 - p_{ji}$) sem assumir uma ordem global transitiva.
• Comportamento Anytime: O sistema produz uma lista competitiva top-$K$ à medida que as comparações se acumulam.

Dois ranqueadores ativos são avaliados como substituições diretas para a ordenação:

• Mohajer (Baseado em Torneio): Baseado em Mohajer et al. (2017), este algoritmo identifica os melhores-$K$ via torneios com extração de heap. Ele concentra adaptativamente as comparações em candidatos próximos ao limite top-$K$ (fase de "aquecimento") e foca em contendores prováveis.
• PAC + Bubble (Baseado em Âncora): Baseado em Agarwal et al. (2022), este método usa um prior de custo zero (por exemplo, pontuações BM25) para definir "âncoras" e restringe as comparações a um subconjunto de candidatos (top $K \times m$). Retorna um conjunto não ordenado, que é então ordenado usando BubbleSort.

2. Oráculo de Direção Randomizada

Para abordar efeitos de ordem sem o custo do prompting bidirecional, os autores introduzem um oráculo de direção randomizada.

• Mecanismo: Para cada par $\{d_i, d_j\}$, o LLM é consultado uma única vez. A ordem de entrada é randomizada: com probabilidade $0.5$, o prompt é $(d_i, d_j)$; caso contrário, é $(d_j, d_i)$. A saída é tomada diretamente.
• Garantia Teórica: Embora chamadas individuais possam ser enviesadas por posição, a randomização garante que o estimador agregado seja recíproco em expectativa ($Pr[V_{ij}=1] = 1 - Pr[V_{ji}=1]$). Isso converte o viés sistemático de posição em ruído de média zero, permitindo uma classificação agregada não enviesada com apenas uma chamada por par em vez de duas.

Contribuições Principais

1. Reformulação do Reranking: O artigo estabelece que o reranking PRP é melhor modelado como aprendizado ativo orçado a partir de comparações ruidosas em vez de ordenação determinística.
2. Ranqueadores Ativos: Os autores demonstram que ranqueadores ativos (especificamente o algoritmo Mohajer) são substituições diretas eficazes para algoritmos de ordenação em regimes com restrição de chamadas, melhorando significativamente a qualidade top-$K$.
3. Oráculo Eficiente: A introdução do oráculo de direção randomizada reduz o custo de lidar com efeitos de ordem em 50% (uma chamada versus duas) enquanto mantém a imparcialidade agregada.
4. Validação Empírica: Experimentos extensivos mostram que ranqueadores ativos alcançam NDCG@10 mais alto com menos chamadas em comparação com baselines de ordenação de última geração.

Resultados

Experimentos foram conduzidos em tarefas TREC DL2019/2020 e estilo BEIR usando modelos Flan-T5-L/XL e Qwen.

• Regime com Restrição de Chamadas ($B \approx 200\text{--}450$):
  • Mohajer supera significativamente as baselines de ordenação. No TREC DL2019/2020 com Flan-T5-XL em $B=300$ chamadas, Mohajer alcançou 66,09 NDCG@10 comparado a 56,42 para BubbleSort (um ganho de +9,7 pontos).
  • Ranqueadores ativos atingem qualidade competitiva com até 7$\times$ menos chamadas que o QuickSort.
• Impacto do Oráculo de Direção Randomizada:
  • Para baselines de ordenação, o oráculo randomizado melhora a qualidade cobrindo mais pares no mesmo orçamento (por exemplo, BubbleSort melhorou de 56,4 para 62,0 em $B=300$).
  • Para ranqueadores ativos, o efeito é mais pronunciado. Mohajer com o oráculo randomizado atingiu sua qualidade máxima (68,0) em $B=250$, enquanto a versão bidirecional exigiu $B=450$ para atingir um teto similar (66,96). Isso representa uma redução de 44% nas chamadas necessárias para atingir o desempenho máximo.
• Orçamentos Elevados: Quando o orçamento é grande o suficiente ($B \ge 500$) para permitir refinamento global, algoritmos de ordenação (como HeapSort) podem alcançar ou superar ligeiramente ranqueadores ativos, pois o custo de polir a permutação completa torna-se acessível.
• Eficiência End-to-End: Em pipelines completos de RAG, ranqueadores ativos (Mohajer + Randomizado) reduziram chamadas médias por tarefa de ~941 (BubbleSort) para 232, mantendo ou melhorando o NDCG@10.

Significado e Alegações

O artigo argumenta que, para praticantes implantando PRP em pipelines de RAG, a estratégia ótima depende do orçamento de chamadas disponível:

• Orçamentos Baixo a Moderado: Ranqueamento ativo (especificamente Mohajer) com um oráculo de direção randomizada é a escolha superior, oferecendo resultados top-$K$ de alta qualidade com latência e custo significativamente menores.
• Orçamentos Muito Baixos: A ordenação pode ser preferível se o orçamento estiver abaixo do limite de "aquecimento" (aproximadamente 100 chamadas para $N=100, K=10$), onde algoritmos ativos ainda não convergiram.
• Orçamentos Muito Elevados: A ordenação torna-se viável novamente, pois o refinamento global compensa.

Os autores afirmam que sua abordagem fornece uma "receita simples" para reranking eficiente: use Mohajer com o oráculo randomizado quando o orçamento exceder o limite de aquecimento, e recorra à ordenação apenas quando os orçamentos forem extremamente pequenos ou grandes o suficiente para justificar o refinamento global. O trabalho destaca que o custo dominante no PRP é a própria chamada de LLM, e otimizar o cronograma dessas chamadas (via aprendizado ativo) produz retornos maiores do que otimizar apenas o modelo comparador.

Limitações

Os autores notam várias limitações:

• O estudo assume um comparador par a par de LLM confiável; os resultados podem variar com o design do prompt ou famílias de modelos.
• Métricas de custo contam chamadas de LLM, mas omitem sobrecargas de nível de sistema (agrupamento, latência de rede); estimativas de latência são limites superiores sequenciais.
• O benefício teórico do prompting de direção randomizada para algoritmos adaptativos é observado empiricamente, mas não totalmente provado.
• O método PAC depende de um hiperparâmetro ($m$) para o tamanho do pool de candidatos, que não foi abalado sistematicamente.
• APIs reais de LLM podem violar a suposição de independência condicional das saídas do oráculo devido a estados ocultos ou cache.