Pourquoi un Top-K ne fixe pas le coût d’un retrieval hybride

Top-K et coût sont deux questions

Un moteur hybride combine souvent les listes d’un retriever dense et d’un retriever lexical avec Reciprocal Rank Fusion. On choisit alors une profondeur L pour chaque liste et un Top-K à retourner. Cette convention donne une taille de sortie, mais elle ne donne pas nécessairement une borne fiable sur le nombre d’éléments à lire : un document peut apparaître plus loin dans une liste et modifier l’ordre du résultat fusionné.

Le preprint Top-K Is Not a Budget for Hybrid Retrieval présente DiBud, pour « Direct Budgeting ». Le système reçoit directement un budget d’accès. Il lit progressivement les listes, borne les contributions encore inconnues et renvoie le préfixe de classement qu’il peut certifier comme exact lorsque le budget est atteint.

Certifier un préfixe

Pour chaque document observé, DiBud conserve une borne inférieure et une borne supérieure de score RRF. Une contribution non lue est bornée par la contribution maximale qu’elle pourrait encore apporter. Un document est émis seulement si sa borne inférieure dépasse les bornes de tous les concurrents, y compris ceux qui n’ont pas encore été vus.

Le résultat n’est donc pas toujours un Top-20 complet. Il peut être un préfixe exact plus court, dont l’ordre correspond au classement obtenu si les listes complètes avaient été consultées. La politique de lecture choisit ensuite le canal qui réduit le mieux l’incertitude courante, tout en respectant le budget.

Ce que rapportent les auteurs

Les expériences rejouent 770 requêtes sur cinq ensembles, avec un RRF de contribution 1/(59 + r). Le coût pour terminer un Top-20 est très variable. Pour TREC-DL 2019, la médiane est de 311 accès, le 95^e percentile de 196 410 et le maximum de 3 533 518. Avec un budget de 2048 accès, la lecture sélective certifie en moyenne 45,05 positions parmi les 100 premières, contre 41,77 pour une lecture équilibrée, soit +7,86 %.

Après calibration pour conserver 95 % de la qualité, les requêtes de test gardent entre 95,05 % et 97,68 % du nDCG@20 moyen, avec 65,92 % à 99,53 % d’accès en moins selon l’ensemble. Ces résultats concernent le protocole et les index étudiés ; ils ne constituent pas une garantie de latence pour un autre système.

Lecture éditoriale

La distinction est précieuse pour un RAG en production. On peut promettre un budget d’accès et accepter une quantité de contexte variable, au lieu de promettre simultanément un Top-K fixe et un coût constant. La sortie doit alors porter son niveau de certification : un préfixe exact de quatre documents n’a pas le même sens qu’une liste heuristique de vingt documents.

Cette approche invite aussi à mesurer la longue traîne. Une moyenne de latence peut cacher quelques requêtes extrêmement coûteuses. Le budget protège le pire cas, mais il faut décider ce que fait l’application lorsque le préfixe est trop court : demander une reformulation, afficher une réponse prudente ou déclencher une recherche plus lente.

Limites à garder

DiBud est étudié sur deux canaux et un score RRF déterministe. La qualité retenue dépend d’une calibration préalable, des corpus, des jugements et de la définition du budget. Une certification du rang ne prouve pas que les documents sont pertinents pour l’utilisateur.

Source et périmètre

Source principale : arXiv:2609.15143v1 · PDF. Les mesures sont celles du preprint ; la proposition de contrat de sortie est une interprétation éditoriale.