Résumé Technique : Raisonnement sur les Graphes de Connaissances sans Encodeur via la Récupération de Chemins Hyperdimensionnels

1. Énoncé du Problème

Les systèmes de Question-Réponse sur les Graphes de Connaissances (KGQA) suivent généralement un paradigme « récupérer puis raisonner », où des chemins de relations candidats reliant les entités thématiques aux réponses potentielles sont générés, puis classés pour sélectionner la chaîne de raisonnement la plus plausible. Les approches de pointe actuelles souffrent de deux inefficacités principales :

1. Inadéquation Chemin-Requête (Path-Query Mismatch) : De nombreux systèmes s'appuient sur des encodeurs neuronaux (ex: Transformers, GNN) ou des opérateurs de liaison insensibles à l'ordre. Ceux-ci échouent souvent à distinguer les séquences de relations ayant des directions ou des ordres différents (ex: confondre $r_1 \to r_2$ avec $r_2 \to r_1$), ce qui conduit à la sélection de chemins superficiellement liés mais sémantiquement désalignés.
2. Scoring par LLM par Candidat : Pour résoudre l'ambiguïté, de nombreux pipelines invoquent séquentiellement des Grands Modèles de Langage (LLM) pour noter chaque chemin candidat. Cela entraîne une latence élevée, des coûts en jetons (tokens) importants et une surcharge de mémoire GPU, car le nombre d'appels au LLM augmente linéairement avec la taille de l'ensemble de candidats. De plus, ce processus séquentiel est difficile à paralléliser et sujet à l'instabilité.

L'article soutient que les solutions existantes sacrifient l'efficacité et la transparence au profit de la précision, nécessitant un cadre capable de maintenir une haute fidélité de raisonnement tout en éliminant la charge computationnelle du codage neural répété et du scoring par LLM.

2. Méthodologie : PathHD

Les auteurs proposent PathHD (HyperDimensional Path Retrieval), un cadre sans encodeur qui couple l'Informatique Hyperdimensionnelle (HDC) à un appel unique de LLM. Le pipeline se compose de quatre étapes : Plan $\to$ Encode $\to$ Retrieve $\to$ Reason.

2.1 Initialisation et Encodage des Hypervecteurs

PathHD opère dans un espace de Représentation Réduite Holographique Généralisée (GHRR).

• Représentation des Symboles : Chaque relation atomique (et optionnellement chaque entité) est mappée vers un hypervecteur $v_x$ de dimension $d$. Ces vecteurs sont construits comme des vecteurs par blocs de matrices unitaires : $v_x = [A(x)_1; \dots; A(x)_D]$, où chaque bloc $A(x)_j \in U(m)$.
• Propriétés : Ces vecteurs sont échantillonnés une seule fois et restent fixes (aucun paramètre appris). L'utilisation de matrices unitaires garantit que les symboles sont presque orthogonaux, concentrant la similitude à mesure que la dimensionnalité augmente.
• Encodage de la Requête : La requête est encodée soit en appliquant le même liage GHRR à un schéma de relation sélectionné (basé sur un plan), soit en projetant un embedding de phrase (ex: SBERT) dans l'espace HDC via une application linéaire aléatoire fixe.

2.2 Liage GHRR et Composition de Chemins

Pour représenter un chemin de relations multi-sauts $z = (r_1, \dots, r_\ell)$, PathHD utilise un opérateur de liage par blocs non commutatif ($\otimes$) :
$$v_z = v_{r_1} \otimes v_{r_2} \otimes \dots \otimes v_{r_\ell}$$
où $X \otimes Y = [X_1 Y_1; \dots; X_D Y_D]$.

• Sensibilité à l'Ordre : Parce que la multiplication matricielle est non commutative ($X_j Y_j \neq Y_j X_j$), l'hypervecteur résultant préserve l'ordre spécifique et la directionnalité de la séquence de relations. Cela distingue les chemins comme $r_1 \to r_2$ de $r_2 \to r_1$, traitant ainsi le problème d'inadéquation chemin-requête.
• Déliage Approximatif : La structure permet le déliage approximatif des relations individuelles, favorisant l'interprétabilité.

2.3 Récupération via Similitude par Blocs

Les chemins candidats sont instanciés à partir du Graphe de Connaissances (KG) et encodés en hypervecteurs. La récupération est effectuée en calculant la similitude cosinus par blocs entre l'hypervecteur de la requête $v_q$ et les hypervecteurs des chemins candidats $v_z$ :
$$\text{sim}(X, Y) = \frac{1}{D} \sum_{j=1}^D \frac{\Re \langle X_j, Y_j \rangle_F}{\|X_j\|_F \|Y_j\|_F}$$

• Scoring : Un score calibré peut être appliqué, incorporant un terme d'Inverse Document Frequency (IDF) pour pénaliser les schémas fréquents ainsi qu'une pénalité de longueur.
• Élagage (Pruning) : Tous les candidats sont scorés en parallèle (complexité $O(Nd)$) et une étape d'élagage Top-K sélectionne les chemins les plus prometteurs. Cela élimine le besoin d'encodeurs neuronaux ou de scoring séquentiel par LLM lors de la récupération.

2.4 Raisonnement en un Seul Passage (One-Shot)

Au lieu de scorer chaque chemin individuellement, PathHD effectue une unique adjudication par LLM :

1. Les chemins Top-K sont linéarisés en énoncés de langage naturel.
2. Un seul prompt est envoyé au LLM contenant la question originale et les chemins candidats Top-K.
3. Le LLM produit la réponse finale, cite l'indice du chemin de support, et fournit une brève justification.
   Cela découple la récupération de la génération, garantissant que le LLM se concentre uniquement sur des candidats de haute qualité.

3. Principales Contributions

1. Récupérateur Sensible à l'Ordre et Sans Encodeur : PathHD introduit une méthode pour encoder des séquences de relations en hypervecteurs utilisant un liage GHRR non commutatif. Cela permet un scoring entièrement parallèle, en $O(Nd)$, sans encodeurs neuronaux appris ou prompts par chemin, tout en préservant les informations directionnelles critiques.
2. Adjudication Efficace en un Seul Passage : Le cadre remplace les multiples appels de scoring par LLM par une étape d'adjudication unique sur les chemins Top-K récupérés. Cela réduit considérablement l'utilisation des jetons, la latence et les coûts d'API tout en maintenant l'interprétabilité grâce aux chemins cités.
3. Validation Complète : Les auteurs fournissent des expériences étendues sur WebQSP, CWQ et GrailQA, démontrant une précision compétitive avec des bases de référence solides. Ils incluent également des études d'ablation confirmant la supériorité du liage GHRR sur les opérateurs commutatifs (ex: XOR, produit de convolution circulaire) et analysent l'impact de l'élagage Top-K.

4. Résultats Expérimentaux

Évalué sur des benchmarks basés sur Freebase (WebQSP, CWQ, GrailQA), PathHD démontre les points suivants :

• Précision : PathHD atteint l'état de l'art sur Hits@1 pour WebQSP (86.2) et GrailQA (92.4 F1 sur le split IID), et reste compétitif sur CWQ (71.5 Hits@1), égalant ou dépassant des agents LLM complexes à plusieurs étapes (ex: RoG, KG-Agent) qui utilisent 3 à 12 appels de LLM.
• Efficacité : En utilisant le scoring dans l'espace vectoriel et un seul appel de LLM, PathHD réduit la latence de bout en bout de 40 à 60 % par rapport aux bases de référence à multiples appels.
• Utilisation des Ressources : Le mécanisme de récupération sans encodeur réduit l'utilisation de la mémoire GPU de 3 à 5$\times$ par rapport aux méthodes nécessitant des encodeurs neuronaux pour chaque candidat.
• Ablations :
  • Opérateur de Liage : Le GHRR (non commutatif) surpasse significativement les liaisons commutatives (XOR, produit élément par élément) et les autres variantes HDC (FHRR, HRR), validant la nécessité de la sensibilité à l'ordre.
  • Adjudication : Un seul appel de LLM sur les chemins Top-K donne de meilleurs résultats que la sélection vectorielle pure, particulièrement pour résoudre les égalités proches ou les subtils désalignements de contraintes.
  • Élagage : La sélection de $K=3$ candidats offre le meilleur compromis entre précision et latence.

5. Signification et Revendications

L'article affirme que PathHD démontre que des représentations hyperdimensionnelles soigneusement conçues peuvent servir de substrat efficace et sans entraînement pour le raisonnement KG-LLM.

• Optimisation du Compromis : PathHD atteint un équilibre solide entre précision, efficacité et interprétabilité. Il évite le « prix élevé » des encodeurs neuronaux et des appels de LLM répétés tout en maintenant un raisonnement fidèle ancré dans le KG.
• Scalabilité : La mise à l'échelle linéaire du calcul avec la dimensionnalité et l'élimination des appels de LLM par candidat rendent l'approche hautement scalable pour de grands ensembles de candidats.
• Fidélité : En fournissant des chemins explicites et cités comme justifications, le système améliore la transparence et permet une analyse d'erreur plus facile par rapport au raisonnement "boîte noire" des LLM.

Les auteurs positionnent PathHD non pas comme une nouvelle avancée théorique dans les Architectures Symboliques Vectorielles (VSA), mais comme une application pratique montée montrant que l'HDC peut remplacer les scoreurs neuronaux appris dans les systèmes KG-LLM, offrant une alternative viable pour un raisonnement efficace et transparent. Des travaux futurs sont suggérés pour appliquer cela à des graphes spécifiques au domaine (ex: biomédical) et à des tâches au-delà de la QA.