La barrière théorique pour les agents neurosymboliques
Les agents d'IA modernes, construits sur des principes neurosymboliques, utilisent de plus en plus l'infrastructure de recherche comme mémoire externe. La chaîne de raisonnement est alors compilée non pas en un simple ensemble de mots-clés, mais en requêtes booléennes profondément imbriquées avec négations et branchements. De telles requêtes semblent naturelles pour un programmeur, mais pour un index inversé classique, elles constituent un défi sérieux.
Un récent préprint d'Amir Aavani sur arXiv (2601.18747, dernière version du 17 août 2026) montre que le problème ne vient pas de la paresse des développeurs de moteurs de recherche. L'auteur formalise le langage de requêtes L_R, représenté sous forme de graphe orienté acyclique, et prouve rigoureusement : l'évaluation d'une telle requête sur un index est un problème P-complet. Autrement dit, en général, ce processus ne pourra probablement pas être efficacement parallélisé sur de nombreux cœurs — à moins que les classes P et NC ne s'avèrent égales, ce que la plupart des théoriciens considèrent comme extrêmement improbable.
Ce travail touche à plusieurs domaines à la fois — la recherche d'information, l'intelligence artificielle, la théorie de la complexité, le traitement du langage naturel et les bases de données. Ce n'est pas un hasard : le problème se situe à l'intersection de l'IA et des technologies de recherche classiques.
Deux approches traditionnelles et leurs faiblesses
Lorsqu'une requête est exécutée sur un index inversé, on utilise généralement l'une des deux stratégies : le traitement itératif par document (Document-at-a-Time) ou la matérialisation des listes intermédiaires par terme (Term-at-a-Time). Chacune a son « squelette dans le placard ».
- Document-at-a-Time repose sur des itérateurs avec état qui progressent dans les listes triées de documents. Il s'avère que ces itérateurs sont structurellement limités à la classe de schémas NC¹. Si la logique de la requête contient des branches reconvergentes — c'est-à-dire plusieurs chemins du graphe convergeant vers un même nœud —, le dépliage naïf de ces branches en arbre conduit à une explosion exponentielle : la complexité atteint dans le pire cas O(2^{|Q|}), où |Q| est la taille de la requête.
- Term-at-a-Time tente de résoudre le problème autrement : chaque nœud de la requête est matérialisé sous forme de liste de documents. Mais pour calculer la négation logique, cette approche doit connaître tout l'univers des documents |U| afin de comprendre quels documents n'entrent pas dans le résultat. Il en résulte une pénalité Ω(|U|) — ce qu'on appelle le balayage universel. Pour de grandes collections, cela signifie en pratique parcourir toute la base pour un seul « non ».
Ainsi, chacune des deux méthodes classiques remplit son rôle limité, mais sur des requêtes DAG non monotones, elles butent soit sur le temps, soit sur l'espace. Jusqu'à présent, on considérait que c'était le prix inévitable à payer pour l'expressivité.
L'algorithme ComputePN
Amir Aavani propose une manœuvre de contournement — un algorithme déterministe ComputePN, spécialement conçu pour les données creuses. L'idée clé est de séparer la négation logique de la matérialisation de tout l'univers. Au lieu de construire la liste complète de « tous les documents qui n'existent pas », ComputePN utilise une représentation duale de chaque nœud : la paire « positif-négatif » stocke à la fois ce qui entre dans le résultat et ce qui est garanti de ne pas y entrer.
Cette approche permet de ne prendre en compte que les documents actifs — ceux qui participent réellement aux calculs. Les résultats intermédiaires sont mémorisés directement sur le graphe de la requête, de sorte que les mêmes sous-expressions ne sont pas recalculées plusieurs fois. La complexité finale est estimée à O(|Q| · |U_active|), où U_active est l'ensemble des documents concernés, et non tout l'univers.
En pratique, cela signifie que les cas lourds avec négations et branches convergentes cessent d'être fatals. Si la collection réelle est vaste, mais que la requête ne touche qu'une petite partie de celle-ci, ComputePN reste efficace.
Ce que cela signifie pour les moteurs de recherche et l'IA
La conclusion principale de ce travail n'est pas que parcourir un index inversé est fondamentalement impossible à accélérer. Plutôt l'inverse : l'auteur montre comment calculer nativement des requêtes P-complètes, en évitant les deux principaux pièges — le dépliage combinatoire de l'arbre et le balayage de tous les documents pour la négation.
Pour les systèmes hybrides neurosymboliques, c'est un signal important. Les agents LLM génèrent des requêtes de plus en plus sophistiquées, et le backend de recherche doit pouvoir les servir sans dégradation catastrophique. La P-complétude théorique reste un avertissement pour les développeurs d'architectures parallèles, mais ComputePN montre qu'une implémentation logicielle soignée peut contourner les pires scénarios.
Cependant, il reste encore beaucoup de travail avant que l'algorithme n'apparaisse dans les systèmes de production. Le schéma proposé exige une gestion minutieuse des représentations duales et de la mémorisation au niveau d'un véritable moteur de recherche. Mais le fait que le problème ait enfin reçu une base théorique rigoureuse est en soi important : désormais, les développeurs savent au moins à quelle complexité ils ont affaire et quelles techniques fonctionnent réellement.
