🤖 AI

TRACE: Learning to Compute on Circuit Graphs

Das Papier stellt TRACE vor, ein neues Paradigma zum Erlernen der Funktionalität von Schaltkreisgraphen, das einen hierarchischen Transformer zur Erfassung des Rechenflusses sowie ein Function-Shift-Lernziel zur Entkopplung der globalen Vorhersage einsetzt und dabei bestehende Architekturen über verschiedene Schaltkreismodalitäten hinweg signifikant übertrifft.

Ursprüngliche Autoren: Ziyang Zheng, Jiaying Zhu, Jingyi Zhou, Qiang Xu

Veröffentlicht 2026-06-17

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Ziyang Zheng, Jiaying Zhu, Jingyi Zhou, Qiang Xu

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Problem: Der „blinde“ Taschenrechner

Stellen Sie sich vor, Sie versuchen einem Computer beizubringen, wie eine komplexe Maschine (wie ein digitaler Schaltkreis) funktioniert. Diese Maschine besteht aus vielen kleinen Teilen (Gates), die miteinander verbunden sind und Informationen von einem zum nächsten weitergeben.

Lange Zeit war die beste Methode, um Computer dies beizubringen, eine Methode namens MPNNs (Message Passing Neural Networks). Die Arbeit argumentiert, dass diese Methode für diese spezifische Aufgabe grundlegend fehlerhaft ist.

Die Analogie: Der blind gebundene Koch
Stellen Sie sich einen Schaltkreis wie ein Rezept vor, bei dem Zutaten (Inputs) von einem Koch (einem Operator, wie einem MUX oder einem Logikgatter) gemischt werden.

Der alte Weg (MPNNs): Stellen Sie sich vor, der Koch trägt eine Augenbinde. Er kann die Zutaten zwar einzeln riechen, aber er sieht nicht die Reihenfolge. Wenn Sie ihm erst „Salz“ und dann „Pfeffer“ geben, behandelt er das genauso wie „Pfeffer“ und dann „Salz“. Aber in einem Schaltkreis spielt die Reihenfolge eine Rolle! Ein Schalter (MUX) verhält sich völlig anders, je nachdem, welches Kabel das Steuerkabel und welches das Datenkabel ist. Die alte Methode wird verwirrt, weil sie die Zutaten wie einen unordentlichen Haufen statt als eine spezifische Sequenz behandelt.
Der andere alte Weg (Transformer): Stellen Sie sich einen Koch vor, der alle Zutaten gleichzeitig auf einem Tisch sieht, aber die Schritte des Rezepts nicht versteht. Er übersieht, dass Schritt 2 von dem Ergebnis aus Schritt 1 abhängt. Er versucht, das fertige Gericht zu erraten, ohne den Kochprozess zu befolgen.

Die Lösung: TRACE

Die Autoren haben ein neues System namens TRACE entwickelt. Es behebt die Probleme, indem es zwei wesentliche Dinge ändert: das „Küchenlayout“ (Architektur) und die „Lehrmethode“ (Lernziel).

1. Das neue Küchenlayout: Der „Schritt-für-Schritt“-Koch

Anstatt des blind gebundenen Kochs oder des verwirrten Kochs verwendet TRACE einen hierarchischen Transformer.

Wie es funktioniert: Es behandelt den Schaltkreis wie einen Satz, der in einer bestimmten Reihenfolge geschrieben wurde (wie eine mathematische Gleichung: Add(Multiply(A, B), C)).
Die Analogie: Der Koch hat nun eine klare Anweisungskarte. Er schaut nicht nur auf die Zutaten; er achtet auf die Reihenfolge, in der sie ihm gereicht werden.
- Zuerst sieht er den „Operator“ (die Aktion, wie z. B. „Mischen“).
- Dann sieht er „Input 1“ (die erste Zutat).
- Dann sieht er „Input 2“ (die zweite Zutat).
Warum es hilft: Da der Koch die Reihenfolge sieht, weiß er genau, wie er sie mischen muss. Wenn im Rezept steht: „Mische Salz in Pfeffer“, macht er es anders, als wenn dort stünde: „Mische Pfeffer in Salz“. Dies ermöglicht es dem Computer, die exakte Logik des Schaltkreises zu verstehen, wobei die Hierarchie (wer von wem abhängt) und die Position jedes Kabels respektiert werden.

2. Die neue Lehrmethode: „Function Shift Learning“

Selbst mit einem guten Koch ist es schwer, den endgültigen Geschmack eines riesigen, komplexen Gerichts vorherzusagen. Manchmal interagieren Zutaten auf überraschende Weise, weil sie in früheren Schritten des Rezepts mehrfach verwendet wurden (dies wird in Schaltkreisen als „Rekonvergenz“ bezeichnet).

Das Problem: Wenn man den Koch fragt: „Wie ist der endgültige Geschmack?“, könnte er von der Komplexität überwältigt werden.
Die TRACE-Lösung: Anstatt den Koch zu fragen, das gesamte endgültige Geschmacksprofil von Grund auf vorherzusagen, bringen die Autoren ihm bei, die Differenz (den „Shift“) zwischen einer einfachen Vermutung und der echten Antwort vorherzusagen.
- Schritt A (Die einfache Vermutung): Der Koch macht eine schnelle Vermutung unter der Annahme, dass alle Zutaten unabhängig vone von einander sind (z. B. „Wenn ich 50 % Salz und 50 % Pfeffer habe, ist die Mischung 50/50“). Das ist einfach und schnell.
- Schritt B (Die echte Antwort): Die echte Antwort ist komplexer, da Salz und Pfeffer sich früher im Prozess bereits interagiert haben könnten.
- Die Aufgabe: Das Modell wird darauf trainiert, die Lücke (den „Shift“) zwischen der einfachen Vermutung und der echten Antwort zu finden.
Die Analogie: Es ist wie ein Schüler bei einer Mathearbeit. Anstatt zu versuchen, eine riesige, beängstigende Gleichung von Null an zu lösen, wird ihm beigebracht: „Hier ist eine einfache, leichte Antwort. Sag mir jetzt nur, wie viel du diese Antwort anpassen musst, um sie richtig zu bekommen.“ Dies macht das Lernen viel einfacher und genauer.

Die Ergebnisse: Ein klarer Sieg

Die Autoren haben TRACE an drei verschiedenen Arten von „Schaltsprachen“ (RTL, AIGs und Netlists) getestet und es mit allen bisherigen besten Methoden verglichen.

Das Ergebnis: TRACE hat jedes Mal gewonnen. Es war viel besser darin:
1. Zwillinge zu finden: Identifizierung von zwei Schaltkreisen, die exakt das Gleiche tun (selbst wenn sie unterschiedlich aussehen).
2. Verhalten vorherzusagen: Genau zu erraten, wie sich ein Schaltkreis unter verschiedenen Bedingungen verhalten wird.
Warum es wichtig ist: Die Arbeit zeigt, dass wir, indem wir die „Blindheit“ der alten Methoden beheben und die Lernaufgabe vereinfachen, viel intelligentere Werkzeuge zum Verständnis elektronischer Schaltkreise bauen können.

Zusammenfassung

TRACE ist eine neue Art und Weise, wie Computer lernen, wie Schaltkreise funktionieren.

Es hört auf, die Eingaben eines Schaltkreises als unordentlichen Haufen zu behandeln, und betrachtet sie stattdessen als eine geordnete Sequenz (wie einen Satz), damit es den Logikfluss versteht.
Es hört auf, zu versuchen, die gesamte komplexe Antwort auf einmal zu erraten, und lernt stat stattdessen, die kleine Differenz zwischen einer einfachen Vermutung und der Wahrheit vorherzusagen.

Diese Kombination macht es zum bisher genauesten Werkzeug für das Verständnis des „funktionalen Verhaltens“ elektronischer Schaltkreise.

Technisches Resümee: TRACE: Lernen zur Berechnung auf Schaltkreis-Graphen

1. Problemstellung

Die grundlegende Herausforderung, die mit dieser Arbeit adressiert wird, ist das Lernen zur Berechnung (Learning to Compute), definiert als die Fähigkeit, das funktionale Verhalten von Schaltkreis-Graphen präzise zu modellieren. Schaltkreis-Graphen (einschließlich Register Transfer Level (RTL)-Graphen, And-Inverter-Graphen (AIGs) und Post-Mapping-Netzlisten) erfassen den Fluss der Berechnung durch gerichtete Knoten, die Operationen und Variablen repräsentieren.

Die Autoren argumentieren, dass die dominierenden Paradigmen des Graph-Repräsentationslernens—Message Passing Neural Networks (MPNNs) und Graph Transformer—architektonisch ungeeignet für diese spezifische Aufgabe sind, was auf drei kritische Mängel zurückzuführen ist:

MPNNs scheitern an der Modellierung von Input-Interaktionen: MPNNs verlassen sich auf permutationsinvariante Aggregatoren (z. B. Summe, Mittelwert), die Nachrichten von Nachbarn unabhängig voneinander kombinieren. Dies verhindert, dass das Modell positionsbewusste, operatorspezifische Interaktionen erfasst. Beispielsweise kann ein Multiplexer (MUX), bei dem $MUX(S, A, B) \neq MUX(A, S, B)$ gilt, nicht korrekt modelliert werden, da die Reihenfolge der Eingänge während der Aggregation verloren geht.
Vanilla Transformer sind hierarchie-agnostisch: Standard-Transformer flachen den Graphen zu einer Sequenz ab, wodurch die explizite hierarchische Struktur und die zwischengeschalteten Abhängigkeiten zerstört werden, die zur Modellierung schrittweiser Berechnungen erforderlich sind (z. B. das Versagen bei der Erfassung der Abhängigkeit von $f(g(a,b), c)$ vom Zwischenergebnis $g(a,b)$ ).
Edge-Masked Transformer erben die Einschränkungen von MPNNs: Transformer, die Attention-Masks verwenden, um die Graph-Topologie zu respektieren, reduzieren sich oft auf gewichtete Summen (ähnlich wie Graph Attention Networks), wodurch die Unfähigkeit zur Modellierung präziser, nicht-linearer Interaktionen zwischen mehreren Eingängen fortbesteht.

Darüber hinaus besteht eine tiefergehende Herausforderung in der Erfassung globaler Funktionen, die aus komplexen Topologien hervorgehen, insbesondere rekonvergente Abhängigkeiten. In Schaltkreisen kann die globale Funktion eines Knotens erheblich von einer einfachen lokalen Approximation abweichen, die eine Unabhängigkeit der Eingänge annimmt. Vorherige Methoden, die direkt auf der globalen Funktion supervisieren, bündeln diese komplexen kontextuellen Effekte implizit in Embeddings, was es für Modelle schwierig macht, zwischen wahren funktionalen Abhängigkeiten und spuriösen Korrelationen zu unterscheiden.

2. Methodik

Die Autoren schlagen TRACE (Transformer for Reasoning about Algebraic and Computational Expressions) vor, ein neues Paradigma, das aus zwei Kernkomponenten besteht: einem architektonisch fundierten Backbone und einem prinzipienbasierten Lernziel.

2.1 Hierarchischer Transformer-Backbone

Um die architektonischen Mängel früherer Modelle zu lösen, verwendet TRACE einen hierarchischen Transformer, der den schrittweisen Fluss der Berechnung widerspiegelt.

Logik-Level-Berechnung: Knoten werden Ebene für Ebene basierend auf ihrer topologischen Logiktiefe verarbeitet. Primäre Eingänge (PIs) befinden sich auf Level 0.
Präfix-Notation-Repräsentation: Inspiriert von der Präfix-Notation wird jeder Berechnungsschritt auf einer spezifischen Logik-Ebene als geordnete Sequenz dargestellt: [Operator, Input_1, Input_2, ...].
Positionsbewusste Kodierung: Ein Transformer-Encoder verarbeitet diese Sequenzen mit Positional Encodings. Dies ermöglicht es dem Modell, operatorspezifische Interaktionen und Positionsbewusstsein zu erfassen (z. B. die Unterscheidung zwischen dem Steuersignal und den Dateneingängen in einem MUX).
Rekursive Verarbeitung: Das Embedding eines Operator-Knotens wird basierend auf dem Transformer-Output des ersten Tokens seiner Sequenz aktualisiert. Dieses aktualisierte Embedding dient dann als Input für nachfolgende Operatoren in der nächsten Logik-Ebene.
Effizienz: Im Gegensatz zu allgemeinen Graphen mit Long-Tail-Gradverteilungen weisen Schaltkreis-Graphen kleine, begrenzte In-Degrees auf, was den quadratischen Speicher-Overhead verhindert, der typischerweise mit Transformern assoziiert wird.

2.2 Function Shift Learning (FSL)

Um die Schwierigkeit der direkten Vorhersage komplexer globaler Funktionen zu adressieren, führt TRACE das Function Shift Learning ein, ein neuartiges Lernziel, das das Lernproblem entkoppelt.

Globale Funktion ( $y_{global}$ ): Die wahre Wahrscheinlichkeit, dass ein Knoten den Wert logisch-1 annimmt, welche alle Abhängigkeiten (einschließlich Rekonvergenz) berücksichtigt. Die direkte Berechnung ist teuer ( $O(2^k)$ ).
Lokale Funktion ( $y_{local}$ ): Eine einfache Approximation unter der Annahme der Unabhängigkeit der Eingänge. Sie ist recheneffizient ( $O(1)$ ), scheitert aber an der wahren Charakteristik in Gegenwart von Rekonvergenz.
Function Shift ( $y_{FSL}$ ): Das Modell wird darauf trainiert, nur die Diskrepanz zwischen der globalen und der lokalen Funktion vorherzusagen:
$y_{FSL} = y_{global} - y_{local}$
Training: Das Modell wird darauf trainiert, den Function Shift mittels eines L1-Loss zu regredieren. Der wahre Shift wird vorab aus den Trainingsdaten berechnet.
Inferenz: Während der Inferenz wird die globale Funktion iterativ rekonstruiert. Für jeden Knoten sagt das Modell den Shift voraus, welcher zur lokalen Funktion (berechnet unter Verwendung der geschätzten globalen Funktionen seiner Vorgänger) addiert wird, um die endgültige globale Schätzung zu erhalten.

3. Kernbeiträge

Architektonische Ausrichtung: Die Einführung eines hierarchischen Transformers, der die permutationsinvariante Aggregation durch positionsbewusste, sequenzbasierte Verarbeitung ersetzt und somit den computationalen Fluss von Schaltkreis-Graphen originalgetreu widerspiegelt.
Entkoppeltes Lernziel: Der Vorschlag des Function Shift Learning, das die komplexen kontextuellen Effekte der Rekonvergenz (den "Shift") von der einfachen lokalen Approximation isoliert und so die Lernaufgabe vereinfacht.
State-of-the-Art Performance: Der Nachweis, dass dieses kombinierte Paradigma bestehende MPNNs und Graph Transformer über diverse Schaltkreis-Modalitäten hinweg deutlich übertrifft.

4. Experimentelle Ergebnisse

Die Autoren evaluierten TRACE auf drei Schaltkreis-Modalitäten (RTL, AIG, PM Netlists) über zwei Aufgabentypen hinweg: kontrastives Lernen und prädiktive Aufgaben.

4.1 Kontrastive Aufgaben

In Retrieval-Aufgaben (Identifizierung funktional äquivalenter Schaltkreise) übertraf TRACE alle Baselines konsistent:

RTL: Erreichte 94,45 % Recall@1 (gegenüber ~88 % beim nächstbesten Modell).
AIG: Erreichte 92,68 % Recall@1 (gegenüber ~88 % beim nächstbesten Modell).
PM Netlist: Erreichte 90,81 % Recall@1 (gegenüber ~86 % beim nächstbesten Modell).
Bemerkenswert ist, dass viele Graph-Transformer-Baselines (z. B. GraphGPS, SGFormer) bei AIGs und PM Netlists unter schwerwiegender Leistungsdegradation oder Out-of-Memory (OOM) Fehlern litten, während TRACE stabil blieb.

4.2 Prädiktive Aufgaben

In Aufgaben zur Vorhersage knotenbasierter Eigenschaften (Wahrscheinlichkeit für Logik-1, Ähnlichkeit, Transitionswahrscheinlichkeit) erzielte TRACE den niedrigsten mittleren absoluten Fehler (MAE) und die höchsten $R^2$ -Werte:

Kombinatorische AIG: MAE von 0,015 für die Logik-1-Wahrscheinlichkeit (gegenüber 0,027 für DeepGate4).
Sequenzielle AIG: MAE von 0,009 für die Logik-1-Wahrscheinlichkeit und 0,005 für die Transitionswahrscheinlichkeit.
PM Netlists: MAE von 0,013 für die Logik-1-Wahrscheinlichkeit (gegenüber 0,048 für GraphSAGE).

4.3 Ablation und Analyse

Function Shift Learning: Das Entfernen von FSL verschlechterte die Leistung signifikant. Beispielsweise erhöhte das Entfernen von FSL bei der Vorhersage der PM-Netlist-Wahrscheinlichkeit den MAE von 0,013 auf 0,036 (eine relative Fehlersteigerung von 63,9 %).
Fehlerakkumulation: Analysen über die Logik-Level hinweg zeigten, dass TRACE selbst bei tiefen Logik-Leveln eine stabile Leistung beibehält, was auf Robustheit gegenüber der Fehlerakkumulation während des iterativen Inferenzprozesses hindeutet.

5. Bedeutung

Das Paper behauptet, dass TRACE einen neuen Stand der Technik für die Schaltkreis-Analyse etabliert und darüber hinaus ein robusteres und architektonisch fundierteres Paradigma für das Lernen auf Schaltkreis-Graphen bietet. Durch die Adressierung der fundamentalen Diskrepanz zwischen Standard-Graph-Lernarchitekturen und der Natur der Berechnung (insbesondere Positionsbewusstsein und Hierarchie) zeigt TRACE, dass die Abstimmung des Inductive Bias des Modells auf die Problemstruktur entscheidend ist, um das funktionale Verhalten zu erfassen. Die Arbeit dient als Beweis für die Wirksamkeit der Entkopplung lokaler Approximationen von globalen kontextuellen Shifts, was zu einer überlegenen Generalisierung über verschiedene EDA-Domänen hinweg führt.