Résumé technique : MAXSHAPLEY

Énoncé du problème

Les moteurs de recherche génératifs, qui utilisent des modèles de langage de grande taille (LLM) pour récupérer des documents et synthétiser des réponses directes, perturbent les structures incitatives traditionnelles pour les fournisseurs de contenu. Contrairement à la recherche traditionnelle, qui redirige les utilisateurs vers les sites web sources, la recherche générative répond souvent aux requêtes directement dans l'interface, réduisant ainsi le trafic et les revenus des créateurs de contenu originaux. De plus, les méthodes existantes pour attribuer les réponses générées à des sources spécifiques sont souvent peu fiables, facilement manipulables ou opaques.

Le défi central abordé consiste à définir un mécanisme équitable et compatible avec les incitations pour attribuer un crédit aux sources d'information en fonction de leur contribution à une réponse générée. Cette attribution doit satisfaire aux axiomes standards d'équité (Efficacité, Symétrie, Joueur nul, Additivité) tout en restant computationnellement faisable pour des pipelines de recherche sensibles à la latence. Les solutions existantes basées sur la valeur de Shapley, la référence en matière d'allocation équitable, sont computationnellement intraitables dans ce contexte car elles nécessitent généralement une énumération exponentielle des sous-ensembles de sources ou des essais d'ablation répétés, entraînant des coûts de jetons prohibitifs et une latence élevée.

Méthodologie : MAXSHAPLEY

Les auteurs proposent MAXSHAPLEY, un algorithme novateur qui calcule une attribution équitable du crédit en modélisant l'interaction entre les sources récupérées et la réponse générée comme un jeu coopératif. La méthode opère dans un cadre boîte noire, ne nécessitant que la requête, les sources récupérées et la réponse finale générée comme entrée, sans avoir besoin d'accéder aux logits internes ou aux probabilités du LLM de recherche.

La méthodologie se compose de trois étapes principales :

1. Décomposition en points clés : Un LLM d'attribution ($\Psi_A$) décompose la réponse générée $a$ en un ensemble de $n$ points clés $P = \{p_1, \dots, p_n\}$ avec des poids associés $w_j$.
2. Évaluation du soutien : Le LLM d'attribution évalue dans quelle mesure chaque source $s_i$ soutient chaque point clé $p_j$, produisant un score de soutien $v_{i,j}$. Cette étape nécessite $n \times m$ évaluations (ou moins via le regroupement par lots), où $m$ est le nombre de sources.
3. Utilité Somme-Max et calcul exact de Shapley :
   • Les auteurs définissent une nouvelle fonction d'utilité $U_{MAXSHAPLEY}$ basée sur une structure somme-max. Pour un sous-ensemble de sources $I$, l'utilité est la somme pondérée du score de soutien maximal pour chaque point clé fourni par n'importe quelle source de ce sous-ensemble :
     $$U_{MAXSHAPLEY}(I) = \sum_{j=1}^{n} w_j \cdot \max_{i \in I} v_{i,j}$$
   • Cette fonction d'utilité modélise la nature coopérative des sources (fournissant des informations complémentaires) et la nature compétitive des informations redondantes (seule la meilleure source pour un point spécifique contribue à l'utilité).
   • Crucialement, cette structure permet un calcul exact de la valeur de Shapley en temps polynomial. Le problème se décompose en $n$ « jeux max » indépendants. Pour chaque point clé, les valeurs de Shapley sont calculées en triant les scores de soutien et en effectuant un balayage linéaire, une opération de complexité $O(m \log m)$. Cela évite le coût exponentiel $O(2^m)$ de la valeur de Shapley par force brute ou la variance d'échantillonnage des approximations de Monte Carlo.

Contributions clés

1. Innovation algorithmique : L'article présente MAXSHAPLEY, un algorithme d'attribution basé sur Shapley spécifiquement conçu pour la recherche générative. Il fournit un algorithme exact et efficace de complexité $O(m \log m)$ pour le sous-problème de la fonction max de Shapley, dérivé d'une classe générale de jeux de couverture.
2. Efficacité en boîte noire : Contrairement aux méthodes antérieures d'attribution de contexte (par exemple, ContextCite, KernelSHAP) qui reposent sur des ablations de contexte répétées ou l'accès à la vraisemblance logarithique, MAXSHAPLEY ne nécessite qu'un accès boîte noire à un LLM d'attribution et évite les essais de génération répétés.
3. Validation empirique : Les auteurs démontrent que MAXSHAPLEY atteint une qualité d'attribution comparable au calcul exact de Shapley (FullShapley) et une forte corrélation avec les annotations humaines, tout en consommant une fraction des ressources computationnelles.
4. Ressources ouvertes : Les auteurs publient un code open source, des sous-ensembles de HotPotQA, MuSiQUE et MS-MARCO ré-annotés manuellement, ainsi qu'une démonstration éducative.

Résultats expérimentaux

Les auteurs ont évalué MAXSHAPLEY sur trois ensembles de données de questions-réponses multi-sauts : HotPotQA, MuSiQUE et MS-MARCO.

• Arbitrage Efficacité vs Qualité : MAXSHAPLEY atteint un indice Jaccard de 0,88 sur MuSiQUE (comparable à FullShapley) tout en n'utilisant que 5,4 % des jetons requis par FullShapley. Par rapport à KernelSHAP, la meilleure base de référence d'approximation de Shapley, MAXSHAPLEY atteint une corrélation similaire avec les annotations humaines à moins de 7 % du coût en jetons.
• Corrélation avec la vérité terrain : MAXSHAPLEY montre une forte corrélation ordinale (Kendall's $\tau_b$) avec FullShapley sur HotPotQA et MuSiQUE. Sur MS-MARCO, il atteint une corrélation modérée, bien que toutes les méthodes de Shapley aient montré une dégradation sur cet ensemble de données, probablement en raison de la nature plus bruyante du contenu source.
• Stabilité : En utilisant des jugements sémantiques localisés (notant les paires source-point clé) plutôt que des ablations complètes de réponses répétées, MAXSHAPLEY atténue l'instabilité de notation souvent observée dans les évaluations de type « LLM comme juge », où des réponses sémantiquement équivalentes reçoivent des scores différents en fonction de la formulation ou de l'ordre des sources.
• Évolutivité : La consommation de jetons pour MAXSHAPLEY évolue de manière linéaire avec le nombre de sources, tandis que KernelSHAP présente une évolution super-linéaire.

Importance et revendications

L'article affirme que MAXSHAPLEY offre une voie pratique vers une recherche générative compatible avec les incitations. En fournissant une méthode équitable, computationnellement efficace et en boîte noire pour attribuer le crédit, elle répond à l'« événement d'extinction » auquel sont confrontés les fournisseurs de contenu à l'ère des réponses générées par l'IA.

Les auteurs positionnent leur travail comme une évolution nécessaire dans l'écosystème, passant au-delà des enchères de recherche sponsorisée (qui bénéficient aux annonceurs, et non aux fournisseurs organiques) vers un modèle où les fournisseurs de contenu sont rémunérés en fonction de leur contribution réelle à l'utilité de la réponse générée. La méthode satisfait aux exigences axiomatiques de l'équité (valeurs de Shapley) tout en surmontant les barrières computationnelles qui ont rendu cette attribution inapplicable dans des contextes de recherche en temps réel. Les auteurs restent modestes, notant que si la méthode est robuste, elle opère sous une hypothèse de boîte noire et que des travaux futurs pourraient explorer une attribution en boîte blanche ou des fonctions d'utilité récompensant explicitement les preuves corroborantes provenant de multiples sources indépendantes.