Résumé technique : Les apprenants actifs en tant que réordonnanceurs PRP efficaces

Énoncé du problème

Dans la génération augmentée par récupération (RAG), les grands modèles de langage (LLM) sont de plus en plus utilisés pour réordonner les documents candidats récupérés par un récupérateur de première étape. L'approche standard, l'incitation au classement par paires (PRP), sollicite des jugements de préférence par paires auprès d'un LLM et les agrège en un classement à l'aide d'algorithmes de tri classiques (par exemple, BubbleSort, QuickSort, HeapSort).

Cependant, ce pipeline souffre d'un décalage structurel. Les algorithmes de tri supposent des comparaisons transitives et déterministes, alors que les jugements des LLM sont stochastiques, bruyants et souvent intransitifs. De plus, les LLM présentent des effets d'ordre significatifs (biais de position), où le changement de l'ordre de présentation des documents peut inverser la préférence. Pour atténuer cela, le PRP standard utilise souvent une incitation bidirectionnelle (deux appels par paire), ce qui double le coût d'inférence.

Le problème central est que le tri vise à retrouver une permutation complète, alors que dans les applications RAG, l'objectif est typiquement un sous-ensemble de haute qualité de top-$K$. Dans le cadre d'un budget strict d'appels LLM (où le coût et la latence sont dominés par l'inférence), le tri gaspille des ressources à « polir » une permutation globale instable plutôt qu'à se concentrer sur l'identification des éléments du top-$K$. De plus, l'hypothèse de transitivité conduit à des classements peu fiables lorsque les comparaisons sous-jacentes sont bruyantes.

Méthodologie

Les auteurs reformulent le réordonnancement PRP comme un problème d'apprentissage actif axé sur l'identification des meilleurs éléments $K$ à partir de comparaisons par paires bruyantes, plutôt que sur le tri de la liste entière.

1. Cadre de classement actif

Au lieu d'un calendrier de tri fixe, l'approche proposée sélectionne de manière adaptative quelles paires de documents interroger pour maximiser la qualité du préfixe top-$K$ dans le cadre d'un budget d'appels fixe ($B$). Le cadre repose sur trois critères :

• Objectif Top-$K$ : L'algorithme vise l'identification des meilleurs éléments $K$ (identification du préfixe) plutôt qu'un ordre global complet.
• Tolérance au bruit : La méthode fonctionne sous la cohérence par paires ($p_{ij} = 1 - p_{ji}$) sans supposer un ordre global transitif.
• Comportement « Anytime » : Le système produit une liste top-$K$ compétitive à mesure que les comparaisons s'accumulent.

Deux classeurs actifs sont évalués en tant que remplacements directs pour le tri :

• Mohajer (basé sur les tournois) : Basé sur Mohajer et al. (2017), cet algorithme identifie les meilleurs éléments $K$ via des tournois avec extraction par tas. Il concentre de manière adaptative les comparaisons sur les candidats proches de la frontière du top-$K$ (phase de « démarrage ») et se concentre sur les prétendants probables.
• PAC + Bubble (basé sur les ancres) : Basé sur Agarwal et al. (2022), cette méthode utilise une a priori à coût nul (par exemple, les scores BM25) pour définir des « ancres » et restreint les comparaisons à un sous-ensemble de candidats (top $K \times m$). Elle renvoie un ensemble non ordonné, qui est ensuite trié à l'aide de BubbleSort.

2. Oracle à direction randomisée

Pour remédier aux effets d'ordre sans le coût de l'incitation bidirectionnelle, les auteurs introduisent un oracle à direction randomisée.

• Mécanisme : Pour chaque paire $\{d_i, d_j\}$, le LLM est interrogé une seule fois. L'ordre d'entrée est randomisé : avec une probabilité de 0,5, l'invite est $(d_i, d_j)$ ; sinon, c'est $(d_j, d_i)$. La sortie est prise directement.
• Garantie théorique : Bien que les appels individuels puissent être biaisés par la position, la randomisation garantit que l'estimateur agrégé est réciproque en espérance ($Pr[V_{ij}=1] = 1 - Pr[V_{ji}=1]$). Cela convertit le biais systématique de position en un bruit à moyenne nulle, permettant un classement agrégé non biaisé avec un seul appel par paire au lieu de deux.

Contributions clés

1. Reformulation du réordonnancement : L'article établit que le réordonnancement PRP est mieux modélisé comme un apprentissage actif budgétisé à partir de comparaisons bruyantes plutôt que comme un tri déterministe.
2. Classeurs actifs : Les auteurs démontrent que les classeurs actifs (spécifiquement l'algorithme Mohajer) sont des remplacements directs efficaces pour les algorithmes de tri dans les régimes contraints par les appels, améliorant considérablement la qualité du top-$K$.
3. Oracle efficace : L'introduction de l'oracle à direction randomisée réduit le coût de gestion des effets d'ordre de 50 % (un appel contre deux) tout en maintenant l'absence de biais agrégé.
4. Validation empirique : De nombreuses expériences montrent que les classeurs actifs atteignent un NDCG@10 plus élevé avec moins d'appels par rapport aux bases de référence de tri les plus avancées.

Résultats

Des expériences ont été menées sur des tâches TREC DL2019/2020 et de style BEIR en utilisant les modèles Flan-T5-L/XL et Qwen.

• Régime contraint par les appels ($B \approx 200\text{--}450$) :
  • Mohajer surpasse significativement les bases de référence de tri. Sur TREC DL2019/2020 avec Flan-T5-XL à $B=300$ appels, Mohajer a atteint 66,09 NDCG@10 contre 56,42 pour BubbleSort (un gain de 9,7 points).
  • Les classeurs actifs atteignent une qualité compétitive avec jusqu'à 7 fois moins d'appels que QuickSort.
• Impact de l'oracle à direction randomisée :
  • Pour les bases de référence de tri, l'oracle randomisé améliore la qualité en couvrant plus de paires au même budget (par exemple, BubbleSort est passé de 56,4 à 62,0 à $B=300$).
  • Pour les classeurs actifs, l'effet est plus prononcé. Mohajer avec l'oracle randomisé a atteint son pic de qualité (68,0) à $B=250$, tandis que la version bidirectionnelle nécessitait $B=450$ pour atteindre un plafond similaire (66,96). Cela représente une réduction de 44 % du nombre d'appels nécessaires pour atteindre les performances maximales.
• Hauts budgets : Lorsque le budget est suffisamment élevé ($B \ge 500$) pour permettre un raffinement global, les algorithmes de tri (comme HeapSort) peuvent rattraper ou légèrement dépasser les classeurs actifs, car le coût de polissage de la permutation complète devient abordable.
• Efficacité de bout en bout : Dans les pipelines RAG complets, les classeurs actifs (Mohajer + Randomized) ont réduit le nombre moyen d'appels par tâche de ~941 (BubbleSort) à 232, tout en maintenant ou en améliorant le NDCG@10.

Importance et affirmations

L'article soutient que pour les praticiens déployant PRP dans des pipelines RAG, la stratégie optimale dépend du budget d'appels disponible :

• Budgets faibles à modérés : Le classement actif (spécifiquement Mohajer) avec un oracle à direction randomisée est le choix supérieur, offrant des résultats top-$K$ de haute qualité avec une latence et un coût nettement inférieurs.
• Budgets très faibles : Le tri peut être préférable si le budget est inférieur au seuil de « démarrage » (environ 100 appels pour $N=100, K=10$), où les algorithmes actifs n'ont pas encore convergé.
• Budgets très élevés : Le tri redevient viable car le raffinement global devient rentable.

Les auteurs affirment que leur approche fournit une « recette simple » pour un réordonnancement efficace : utiliser Mohajer avec l'oracle randomisé lorsque le budget dépasse le seuil de démarrage, et revenir au tri uniquement lorsque les budgets sont extrêmement faibles ou suffisamment élevés pour justifier un raffinement global. Le travail met en évidence que le coût dominant dans PRP est l'appel LLM lui-même, et que l'optimisation du calendrier de ces appels (via l'apprentissage actif) produit des rendements supérieurs à l'optimisation du modèle comparateur seul.

Limites

Les auteurs notent plusieurs limites :

• L'étude suppose un comparateur LLM par paires fiable ; les résultats peuvent varier selon la conception des invites ou les familles de modèles.
• Les métriques de coût comptent les appels LLM mais omettent les surcharges au niveau du système (regroupement, latence réseau) ; les estimations de latence sont des bornes supérieures séquentielles.
• L'avantage théorique de l'incitation à direction randomisée pour les algorithmes adaptatifs est observé empiriquement mais pas entièrement prouvé.
• La méthode PAC repose sur un hyperparamètre ($m$) pour la taille du pool de candidats, qui n'a pas été systématiquement ablaté.
• Les API LLM réelles peuvent violer l'hypothèse d'indépendance conditionnelle des sorties de l'oracle en raison d'états cachés ou de mise en cache.