🤖 AI

TRACE: Learning to Compute on Circuit Graphs

Le document introduit TRACE, un nouveau paradigme pour l'apprentissage de la fonctionnalité des graphes de circuits qui emploie un Transformer Hiérarchique pour capturer le flux de calcul et un objectif d'apprentissage de décalage de fonction pour découpler la prédiction globale, surpassant de manière significative les architectures existantes à travers diverses modalités de circuits.

Auteurs originaux : Ziyang Zheng, Jiaying Zhu, Jingyi Zhou, Qiang Xu

Publié 2026-06-17

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Ziyang Zheng, Jiaying Zhu, Jingyi Zhou, Qiang Xu

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Le gros problème : La calculatrice « aveugle »

Imaginez que vous essayiez d'apprendre à un ordinateur à comprendre comment fonctionne une machine complexe (comme un circuit numérique). Cette machine est composée de nombreuses petites pièces (portes logiques) connectées entre elles, transmettant l'information de l'une à l'autre.

Pendant longtemps, la meilleure façon d'enseigner cela aux ordinateurs était d'utiliser une méthode appelée MPNN (Réseaux de neurones à passage de messages). Le papier soutient que cette méthode est fondamentalement défaillante pour ce travail spécifique.

L'analogie : Le chef cuisinier aux yeux bandés
Considérez un circuit comme une recette où les ingrédients (entrées) sont mélangés par un chef (un opérateur, comme un MUX ou une porte logique).

L'ancienne méthode (MPNN) : Imaginez que le chef porte un bandeau sur les yeux. Il peut sentir les ingrédients un par un, mais il ne peut pas voir l'ordre. Si vous lui donnez du « Sel » puis du « Poivre », il les traite de la même manière que si vous lui donniez du « Poivre » puis du « Sel ». Or, dans un circuit, l'ordre compte ! Un commutateur (MUX) se comporte de manière totalement différente selon que le fil est le signal de commande ou le signal de données. L'ancienne méthode s'embrouille car elle traite les ingrédients comme un tas désordonné plutôt que comme une séquence spécifique.
L'autre ancienne méthode (Transformers) : Imaginez un chef qui voit tous les ingrédients en même temps sur une table, mais qui ne comprend pas les étapes de la recette. Il ne saisit pas le fait que l'étape 2 dépend du résultat de l'étape 1. Il essaie de deviner le plat final sans suivre le processus de cuisson.

La solution : TRACE

Les auteurs ont créé un nouveau système appelé TRACE. Il corrige les problèmes en changeant deux choses principales : la « disposition de la cuisine » (Architecture) et la « méthode d'enseignement » (Objectif d'apprentissage).

1. La nouvelle disposition de la cuisine : Le chef « étape par étape »

Au lieu du chef aux yeux bandés ou du chef confus, TRACE utilise un Transformer Hiérarchique.

Comment ça marche : Il traite le circuit comme une phrase écrite dans un ordre spécifique (comme une équation mathématique : Ajouter(Multiplier(A, B), C)).
L'analogie : Imaginez que le chef possède maintenant une fiche d'instructions claire. Il ne se contente pas de regarder les ingrédients ; il regarde l' ordre dans lequel ils lui sont donnés.
- D'abord, il voit l'« Opérateur » (l'action, comme « Mélanger »).
- Ensuite, il voit l'« Entrée 1 » (le premier ingrédient).
- Puis, il voit l'« Entrée 2 » (le deuxième ingrédient).
Pourquoi cela aide : Parce que le chef voit l'ordre, il sait exactement comment les mélanger. Si la recette dit « Mélanger le Sel dans le Poivre », il le fera différemment de « Mélanger le Poivre dans le Sel ». Cela permet à l'ordinateur de comprendre la logique exacte du circuit, en respectant la hiérarchie (qui dépend de qui) et la position de chaque fil.

2. La nouvelle méthode d'enseignement : « L'apprentissage par décalage de fonction » (Function Shift Learning)

Même avec un bon chef, prédire le goût final d'un plat géant et complexe est difficile. Parfois, les ingrédients interagissent de manière surprenante parce qu'ils ont été utilisés dans plusieurs étapes plus tôt dans la recette (ce qu'on appelle la « reconvergence » dans les circuits).

Le problème : Si vous demandez au chef : « Quel est le goût final ? », il peut être submergé par la complexité.
La correction de TRACE : Au lieu de demander au chef de prédire l'intégralité du goût final à partir de zéro, les auteurs lui apprennent à prédire la différence (le « décalage » ou « shift ») entre une estimation simple et la vraie réponse.
- Étape A (L'estimation simple) : Le chef fait une estimation rapide en supposant que tous les ingrédients sont indépendants (ex : « Si j'ai 50 % de sel et 50 % de poivre, le mélange est à 50/50 »). C'est facile et rapide.
- Étape B (La vraie réponse) : La vraie réponse est plus complexe car le sel et le poivre ont pu interagir plus tôt dans le processus.
- La tâche : Le modèle est entraîné pour trouver l'écart (le « décalage ») entre l'estimation simple et la vraie réponse.
L'analogie : C'est comme un étudiant passant un examen de mathématiques. Au lieu d'essayer de résoudre une équation massive et effrayante en partant de zéro, on lui enseigne : « Voici une réponse simple et facile. Maintenant, dis-moi juste de combien tu dois ajuster cette réponse pour qu'elle soit correcte. » Cela rend l'apprentissage beaucoup plus facile et précis.

Les résultats : Une victoire claire

Les auteurs ont testé TRACE sur trois types différents de « langages » de circuits (RTL, AIG et Netlists) et l'ont comparé à toutes les meilleures méthodes précédentes.

Le résultat : TRACE a gagné à chaque fois. Il était bien meilleur pour :
1. Trouver des jumeaux : Identifier deux circuits qui font exactement la même chose (même s'ils se présentent différemment).
2. Prédire le comportement : Prédire avec précision comment un circuit va se comporter sous différentes conditions.
Pourquoi c'est important : Le papier montre qu'en corrigeant la « cécité » des anciennes méthodes et en simplifiant la tâche d'apprentissage, nous pouvons construire des outils beaucoup plus intelligents pour comprendre les circuits électroniques.

Résumé

TRACE est une nouvelle façon pour les ordinateurs d'apprendre comment fonctionnent les circuits.

Il arrête de traiter les entrées du circuit comme un tas désordonné et commence à les traiter comme une séquence ordonnée (comme une phrase), afin de comprendre le flux logique.
Il arrête d'essayer de deviner toute la réponse complexe d'un coup et apprend plutôt à prédire la petite différence entre une estimation simple et la vérité.

Cette combinaison en fait l'outil le plus précis à ce jour pour comprendre le « comportement fonctionnel » des circuits électroniques.

Résumé Technique : TRACE : Apprendre à calculer sur des graphes de circuits

1. Énoncé du problème

Le défi fondamental abordé par ce travail est l'apprentissage du calcul (learning to compute), défini comme la capacité à modéliser avec précision le comportement fonctionnel des graphes de circuits. Les graphes de circuits (incluant les graphes de transfert de registres (RTL), les graphes d'And-Inverter (AIG) et les réseaux post-mappage) capturent le flux de calcul à travers des nœuds dirigés représentant des opérations et des variables.

Les auteurs soutiennent que les paradigmes dominants de l'apprentissage de représentation sur graphes — les réseaux de neurones à passage de messages (MPNN) et les Transformers de graphes — sont architecturalement inadaptés à cette tâche spécifique en raison de trois défauts critiques :

Les MPNN ne parviennent pas à modéliser les interactions d'entrée : Les MPNN reposent sur des agrégateurs invariants par permutation (ex: somme, moyenne) qui combinent les messages des voisins de manière indépendante. Cela empêche le modèle de capturer des interactions spécifiques à l'opérateur et sensibles à la position. Par exemple, un multiplexeur (MUX) où $MUX(S, A, B) \neq MUX(A, S, B)$ ne peut pas être modélisé correctement car l'ordre des entrées est perdu lors de l'agrégation.
Les Transformers classiques sont dépourvus de conscience hiérarchique : Les Transformers standards aplatissent le graphe en une séquence, détruisant la structure hiérarchique explicite et les dépendances intermédiaires nécessaires pour modéliser un calcul étape par étape (par exemple, l'incapacité à capturer la dépendance de $f(g(a,b), c)$ vis-à-vis du résultat intermédiaire $g(a,b)$ ).
Les Transformers à masquage d'arêtes héritent des limitations des MPNN : Les Transformers utilisant des masques d'attention pour respecter la topologie du graphe se réduisent souvent à des sommes pondérées (similaires aux réseaux d'attention sur graphes), héritant ainsi de l'incapacité à modéliser des interactions précises et non linéaires entre plusieurs entrées.

De plus, un défi plus profond réside dans la capture des fonctions globales qui émergent de topologies complexes, particulièrement les dépendances de reconvergence. Dans les circuits, la fonction globale d'un nœud peut différer considérablement d'une simple approximation locale supposant l'indépendance des entrées. Les méthodes précédentes qui supervisent directement la fonction globale regroupent implicitement ces effets contextuels complexes dans les plongements (embeddings), ce qui rend difficile pour les modèles de distinguer les véritables dépendances fonctionnelles des corrélations spécieuses.

2. Méthodologie

Les auteurs proposent TRACE (Transformer for Reasoning about Algebraic and Computational Expressions), un nouveau paradigme composé de deux éléments clés : un squelette (backbone) architecturalement sain et un objectif d'apprentissage fondé sur des principes.

2.1 Squelette de Transformer Hiérarchique

Pour résoudre les défauts architecturaux des modèles précédents, TRACE utilise un Transformer Hiérarchique qui reflète le flux de calcul étape par étape.

Calcul au niveau logique : Les nœuds sont traités niveau par niveau selon leur profondeur logique topologique. Les entrées primaires (PI) se situent au niveau 0.
Représentation en notation préfixée : Inspiré de la notation préfixée, chaque étape de calcul à un niveau logique spécifique est représentée comme une séquence ordonnée : [opérateur, entrée_1, entrée_2, ...].
Encodage sensible à la position : Un encodeur Transformer traite ces séquences avec des encodages positionnels. Cela permet au modèle de capturer des interactions spécifiques à l'opérateur et une sensibilité à la position (ex: distinguer le signal de commande des entrées de données dans un MUX).
Traitement récursif : Le plongement d'un nœud opérateur est mis à jour en fonction de la sortie du Transformer pour le premier jet (token) de sa séquence. Ce plongement mis à jour sert ensuite d'entrée pour les opérateurs suivants du niveau logique suivant.
Efficacité : Contrairement aux graphes généraux ayant des distributions de degrés à longue traîne, les graphes de circuits possèdent des degrés d'entrée faibles et bornés, ce qui évite la surcharge de mémoire quadratique typiquement associée aux Transformers.

2.2 Apprentissage du Décalage de Fonction (FSL - Function Shift Learning)

Pour remédier à la difficulté de prédire directement des fonctions globales complexes, TRACE introduit le Function Shift Learning, un objectif d'apprentissage novateur qui découple le problème.

Fonction Globale ( $y_{global}$ ) : La véritable probabilité qu'un nœud soit à l'état logique-1, qui prend en compte toutes les dépendances (y compris la reconvergence). Calculer cela directement est coûteux ( $O(2^k)$ ).
Fonction Locale ( $y_{local}$ ) : Une simple approximation supposant l'indépendance des entrées. Elle est efficace en termes de calcul ( $O(1)$ ) mais échoue à capturer le comportement réel en présence de reconvergence.
Décalage de Fonction ( $y_{FSL}$ ) : Le modèle est entraîné à prédire uniquement l'écart entre la fonction globale et la fonction locale :
$y_{FSL} = y_{global} - y_{local}$
Entraînement : Le modèle est entraîné pour effectuer une régression sur le décalage de fonction en utilisant une perte L1. Le décalage réel est pré-calculé à partir des données d'entraînement.
Inférence : Lors de l'inférence, la fonction globale est reconstruite de manière itérative. Pour chaque nœud, le modèle prédit le décalage, qui est ajouté à la fonction locale (calculée à l'aide des fonctions globales estimées de ses prédécesseurs) pour obtenir l'estimation globale finale.

3. Contributions Clés

Alignement Architectural : L'introduction d'un Transformer Hiérarchique qui remplace l'agrégation invariante par permutation par un traitement basé sur des séquences sensibles à la position, reflétant fidèlement le flux de calcul des graphes de circuits.
Objectif d'Apprentissage Découplé : La proposition du Function Shift Learning, qui isole les effets contextuels complexes de la reconvergence (le "décalage") de l'approximation locale simple, simplifiant ainsi la tâche d'apprentissage.
Performances de l'État de l'Art : La démonstration que ce paradigme combiné surpasse nettement les MPNN et les Transformers de graphes existants à travers diverses modalités de circuits.

4. Résultats Expérimentaux

Les auteurs ont évalué TRACE sur trois modalités de circuits (RTL, AIG, PM Netlists) sur deux types de tâches : l'apprentissage contrastif et les tâches prédictives.

4.1 Tâches Contrastives

Dans les tâches de recherche (identifier des circuits fonctionnellement équivalents), TRACE a systématiquement surpassé tous les modèles de référence :

RTL : A atteint 94,45 % de Recall@1 (contre environ 88 % pour le meilleur modèle suivant).
AIG : A atteint 92,68 % de Recall@1 (contre environ 88 % pour le meilleur modèle suivant).
PM Netlist : A atteint 90,81 % de Recall@1 (contre environ 86 % pour le meilleur modèle suivant).
Notamment, de nombreux modèles de référence de type Graph Transformer (ex: GraphGPS, SGFormer) ont souffert d'une dégradation sévère des performances ou d'erreurs de type dépassement de mémoire (OOM) sur les AIG et les PM Netlists, alors que TRACE est resté stable.

4.2 Tâches Prédictives

Dans les tâches de prédiction de propriétés au niveau du nœud (probabilité de logique-1, similarité, probabilité de transition), TRACE a obtenu les erreurs absolues moyennes (MAE) les plus basses et les scores $R^2$ les plus élevés :

AIG Combinatoire : MAE de 0,015 pour la probabilité de logique-1 (contre 0,027 pour DeepGate4).
AIG Séquentiel : MAE de 0,009 pour la probabilité de logique-1 et 0,005 pour la probabilité de transition.
PM Netlists : MAE de 0,013 pour la probabilité de logique-1 (contre 0,048 pour GraphSAGE).

4.3 Ablation et Analyse

Function Shift Learning : Le retrait du FSL a considérablement dégradé les performances. Par exemple, sur la prédiction de probabilité des PM Netlists, le retrait du FSL a augmenté la MAE de 0,013 à 0,036 (une augmentation relative de l'erreur de 63,9 %).
Accumulation d'Erreur : L'analyse à travers les niveaux logiques a montré que TRACE maintient des performances stables même à des niveaux logiques profonds, indiquant une robustesse face à l'accumulation d'erreurs durant le processus d'inférence itératif.

5. Signification

L'article affirme que TRACE établit un nouvel état de l'art pour l'analyse de circuits et, plus largement, fournit un paradigme plus robuste et architecturalement sain pour l'apprentissage sur les graphes de circuits. En traitant le décalage fondamental entre les architectures standards d'apprentissage sur graphes et la nature du calcul (spécifiquement la sensibilité à la position et la hiérarchie), TRACE démontre qu'aligner le biais inductif du modèle avec la structure du problème est crucial pour capturer le comportement fonctionnel. Ce travail sert de preuve de concept montrant que le découplage des approximations locales des décalages contextuels globaux conduit à une généralisation supérieure à travers divers domaines de l'automatisation de la conception électronique (EDA).