Cet article fournit une analyse théorique de la recherche en contexte, la modélisant comme une inférence approximative sur des traces de raisonnement où le modèle de base définit une distribution a priori et l'auto-réflexion fournit un retour pour les mises à jour a posteriori. Les auteurs étudient la complexité d'échantillonnage au moment de l'inférence qui en résulte, définie comme le nombre d'essais séquentiels nécessaires pour atteindre une probabilité de succès élevée.
- Lorsque les réflexions localisent de manière fiable les erreurs précoces, la recherche en contexte produit des améliorations exponentielles par rapport au modèle de base, résolvant des problèmes avec des taux de réussite à zéro échantillon exponentiellement petits en utilisant uniquement un nombre polynomial d'essais séquentiels.
- Si cette propriété échoue, conditionner sur les essais passés n'offre aucun avantage asymptotique par rapport à l'échantillonnage parallèle.
- Ces gains sont robustes et apprenables : des mises à jour a posteriori approximatives suffisent, et l'entraînement par entropie croisée sur les rollouts de recherche récupère le comportement requis avec une complexité d'échantillonnage polynomiale.
- Sous une abstraction par étapes du renforcement learning avec récompenses vérifiables, l'extension de politique optimale implémente la même règle de rééquilibrage a posteriori.
Les auteurs valident les prédictions qualitatives clés de la théorie sur de vrais grands modèles de raisonnement.