Online Pandora's Box for Contextual LLM Cascading

Résumé Technique : La Boîte de Pandore Contextuelle en Ligne pour le Cascading de LLM

1. Formulation du Problème

Le papier traite du défi opérationnel du cascading de LLM (cascade de modèles de langage), où une organisation doit interroger séquentiellement un portefeuille d'API de Large Language Models (LLM) pour générer du contenu de haute qualité de manière rentable. Contra�irement au routage de modèle standard (sélection d'une seule API par requête), le cascading implique un processus de recherche séquentielle : le décideur (DM) interroge les API une par une, en engageant des coûts et en observant les sorties, jusqu'à ce qu'une condition d'arrêt soit remplie, moment auquel une seule sortie est sélectionnée et déployée.

Les auteurs formalisent cela comme un problème de Boîte de Pandore Contextuelle en Ligne présentant une structure distincte en deux phases :

1. Phase de Requête (Query Phase) : Le DM observe un contexte de requête $x_t$ et interroge séquentiellement des boîtes (APIs). Interroger la boîte $a$ révèle une sortie stochastique $\omega_{at}$ et engendre un coût $c_{at}$. Le DM décide de continuer les requêtes ou de s'arrêter en fonction des sorties et des coûts observés.
2. Phase de Sélection (Selection Phase) : Lors de l'arrêt, le DM sélectionne l'une des sorties interrogées pour son déploiement. Le DM n'observe que la récompense en aval $r_t$ associée à la sortie sélectionnée, et non les récompenses des sorties interrogées mais non sélectionnées.

Distinction Clé : Cela diffère des modèles classiques de la Boîte de Pandore où l'ouverture d'une boîte révèle directement sa récompense. Ici, la récompense est « médiée par la sortie » : la récompense dépend de la paire requête-sortie $(x_t, \omega_{at})$ via une fonction de récompense partagée $\mu^*$, tandis que l'hétérogénéité spécifique aux API provient uniquement des distributions de sorties et de coûts. Le feedback est partiel ; le DM apprend la fonction de récompense uniquement à partir des sorties sélectionnées, mais apprend les indices de réservation à partir de toutes les sorties interrogées.

L'objectif est de minimiser le regret cumulé sur un horizon $T$ par rapport à une politique oracle qui connaît les distributions de sortie conditionnelles, les fonctions de coût et la fonction de récompense.

2. Méthodologie

Les auteurs proposent COSMOS (COst-aware Sequential MOdel query and Selection), une politique d'apprentissage en ligne qui évite d'estimer les distributions conditionnelles complètes. Au lieu de cela, elle modélise et apprend directement les indices de réservation et la fonction de récompense en utilisant des structures paramétriques.

Composants Fondamentaux :

• Modélisation Paramétrique :
  • Fonction de Récompense : Modélisée comme une fonction linéaire généralisée : $\mu^*(x, \omega) = G(\theta^*{}^\top \phi(x, \omega))$.
  • Indices de Réservation : Modélisés comme des fonctions linéaires généralisées du contexte : $\sigma^*_a(x) = \Lambda(\rho_a^\top \psi(x))$. Ces indices sont dérivés de la politique optimale de Weitzman, satisfaisant l'équation de moment $E[(\mu^*(x, \omega) - \sigma^*_a(x))^+ | x] = E[c_a | x]$.
• Apprentissage Basé sur l'Optimisme : La politique construit des bornes supérieures optimistes pour la fonction de récompense et les indices de réservation.
  • Estimation de la Récompense : Utilise un estimateur de maximum de vraisemblance (MLE) pénalisé pour $\theta^*$ basé sur les sorties déployées, construisant des bornes supérieures de confiance (UCB) via une inégalité de martingales auto-normalisées.
  • Estimation de l'Indice : Utilise une approche de Méthode des Moments Généralisés (GMM) (plus précisément une formulation d'estimation-$M$) pour estimer $\rho_a$. La fonction de perte est construite de telle sorte que sa condition du premier ordre récupère l'analogue échantillonné de l'équation de moment de Weitzman. Cela permet d'apprendre l'indice directement à partir des paires sortie-coût interrogées sans estimer la distribution complète.
• Décomposition du Regret : Une intuition théorique clé est que, sous l'hypothèse d'optimisme, le regret par période se décompose en deux termes d'erreur indépendants :
  1. L'erreur dans l'estimation de la récompense pour la sortie sélectionnée.
  2. La somme des erreurs d'estimation des indices de réservation pour toutes les boîtes interrogées.
     Cette décomposition permet aux auteurs d'appliquer des analyses UCB standards (arguments de potentiel elliptique) à ces deux composantes séparément.

Flux de l'Algorithme (COSMOS) :

1. Observer le contexte $x_t$.
2. Construire les estimations optimistes $\hat{\sigma}_{at}$ et $\hat{\mu}_t$.
3. Ordonner les boîtes par ordre décroissant de $\hat{\sigma}_{at}$.
4. Interroger séquentiellement les boîtes. Arrêter les requêtes sur la boîte $k$ si la récompense optimiste maximale des sorties interrogées dépasse l'indice optimiste de la boîte suivante.
5. Sélectionner la boîte interrogée ayant la plus haute estimation de récompense optimiste.
6. Observer la récompense réalisée et mettre à jour les estimateurs.

3. Contributions Clés

1. Nouvelle Formulation de Modèle : Le papier introduit un modèle de Boîte de Pandore contextuelle en ligne spécifiquement conçu pour le cascading de LLM. Il capture la structure critique de feedback « médié par la sortie » où les récompenses ne sont observées que pour les sorties déployées, se distinguant des cadres classiques où les récompenses sont révélées lors de l'inspection.
2. Modélisation Directe des Indices : Au lieu d'apprendre des distributions conditionnelles complexes de sorties et de coûts, les auteurs proposent de modéliser directement les indices de réservation via des structures paramétriques. Ceci est réalisé via une approche d'estimation-$M$ basée sur la GMM qui exploite la condition de moment définissant l'indice optimal.
3. Garanties de Regret : Le papier fournit des bornes de regret formelles pour la politique COSMOS.
   • Régime de Récompense Connue : Si la fonction de récompense est connue (ex: via des données hors ligne), la politique atteint une borne de regret de $\tilde{O}(A m \sqrt{T})$, où $A$ est le nombre d'APIs et $m$ est la dimension de la carte de caractéristiques de l'indice.
   • Régime de Récompense Inconnue : Lorsque la fonction de récompense doit être apprise en ligne, la politique atteint une borne de regret de $\tilde{O}([d + A(m + \sqrt{dm})]\sqrt{T})$, où $d$ est la dimension de la carte de caractéristiques de la récompense.
   • Ces bornes améliorent les résultats existants de la Boîte de Pandore contextuelle (ex: $\tilde{O}(T^{5/6})$) en exploitant les hypothèses de courbure locale pour atteindre le taux optimal de $\tilde{O}(\sqrt{T})$.

4. Résultats et Hypothèses

Les résultats théoriques reposent sur plusieurs conditions de régularité :

• Hypothèse 1 & 2 (Indices) : La fonction de lien $\Lambda$ est lisse et strictement croissante ; la fonction de perte présente une courbure locale autour de l'indice réel (garantissant que l'équation de moment traverse zéro avec une pente bornée).
• Hypothèse 3 & 4 (Récompense) : La fonction de récompense suit un modèle linéaire généralisé avec un lien $G$ strictement croissant ; les récompenses appartiennent à une famille exponentielle canonique.
• Hypothèse 5 (Anti-concentration) : Garantit que les caractéristiques des sorties sélectionnées (utilisées pour l'apprentissage de la récompense) sont suffisamment informatives pour contrôler l'erreur d'estimation des indices (qui dépendent des sorties interrogées). Cela empêche un « décalage » entre les données utilisées pour apprendre la récompense et celles utilisées pour apprendre les indices.

Le papier prouve que sous ces conditions, la politique COSMOS atteint un regret cumulé de $\tilde{O}(\sqrt{T})$ dépendant de la dimension.

5. Signification et Revendications

Le papier affirme être le premier à formuler le cascading de LLM comme un problème de Boîte de Pandore contextuelle en ligne avec requête et sélection conjointes, fournissant des garanties de regret formelles. Il comble le fossé entre les méthodes de cascading de LLM heuristiques (comme FrugalGPT) et la théorie rigoureuse de l'apprentissage en ligne.

La signification réside dans :

• Pertinence Pratique : Il traite du compromis réel entre coût d'inférence et qualité de sortie dans le déploiement de LLM, offrant une manière fondée sur des principes pour gérer les requêtes d'API séquentielles.
• Avancement Théorique : Il étend la littérature de la Boîte de Pandore aux contextes avec feedback médié par la sortie et développe un nouvel algorithme d'apprentissage combinant les techniques de GMM et d'UCB pour gérer la structure de feedback spécifique du cascading de LLM.
• Efficacité : En modélisant directement les indices de réservation plutôt que les distributions complètes, l'approche est plus efficace sur le plan computationnel et statistique pour des contextes de haute dimension.

Les auteurs notent que leur travail suppose une structure de requête séquentielle standard et des modèles paramétriques, laissant les extensions vers les contextes non paramétriques, le requêtage par lots (batched querying) et l'ensemble de sorties (output ensembling) comme directions futures.