Resumo Técnico: TRACE: Aprendendo a Computar em Grafos de Circuitos

1. Definição do Problema

O desafio fundamental abordado por este trabalho é o aprendizado de computação (learning to compute), definido como a capacidade de modelar com precisão o comportamento funcional de grafos de circuitos. Grafos de circuitos (incluindo grafos de Transferência de Registrador para Nível (RTL), Grafos de Porta-e-Inversor (AIGs) e netlists pós-mapeamento) capturam o fluxo de computação através de nós direcionados que representam operações e variáveis.

Os autores argumentam que os paradigmas dominantes de aprendizado de representação de grafos — Redes Neurais de Passagem de Mensagens (MPNNs) e Transformers de Grafos — são arquiteturalmente incompatíveis para esta tarefa específica devido a três falhas críticas:

1. As MPNNs Falham ao Modelar Interações de Entrada: As MPNNs dependem de agregadores invariantes à permutação (ex: soma, média) que combinam mensagens de vizinhos de forma independente. Isso impede o modelo de capturar interações específicas de operadores e sensíveis à posição. Por exemplo, um multiplexador (MUX) onde $MUX(S, A, B) \neq MUX(A, S, B)$ não pode ser modelado corretamente porque a ordem das entradas é perdida durante a agregação.
2. Transformers Vanilla são Agenes de Hierarquia: Transformers padrão achatam o grafo em uma sequência, destruindo a estrutura hierárquica explícita e as dependências intermediárias necessárias para modelar a computação passo a passo (ex: falhando em capturar a dependência de $f(g(a,b), c)$ sobre o resultado intermediário $g(a,b)$).
3. Transformers com Máscara de Arestas Herdam Limitações de MPNN: Transformers que utilizam máscaras de atenção para respeitar a topologia do grafo frequentemente reduzem-se a somas ponderadas (semelhante às Redes de Atenção de Grafos), herdando a incapacidade de modelar interações precisas e não lineares entre múltiplas entradas.

Além disso, existe um desafio mais profundo em capturar funções globais que emergem de topologias complexas, particularmente dependências reconvergentes. Em circuitos, a função global de um nó pode diferir significativamente de uma simples aproximação local que assume independência de entrada. Métodos anteriores que supervisionam diretamente a função global agrupam implicitamente esses efeitos contextuais complexos em embeddings, tornando difícil para os modelos distinguir dependências funcionais verdadeiras de correlações espúrias.

2. Metodologia

Os autores propõem o TRACE (Transformer for Reasoning about Algebraic and Computational Expressions), um novo paradigma consistindo em dois componentes principais: um esqueleto (backbone) arquiteturalmente sólido e um objetivo de aprendizado principiado.

2.1 Esqueleto de Transformer Hierárquico

Para resolver as falhas arquiteturais de modelos anteriores, o TRACE utiliza um Transformer Hierárquico que espelha o fluxo passo a passo da computação.

• Computação de Nível Lógico: Os nós são processados nível por nível com base em sua profundidade lógica topológica. As Entradas Primárias (PIs) estão no nível 0.
• Representação de Notação Prefixada: Inspirado na notação prefixada, cada etapa de computação em um nível lógico específico é representada como uma sequência ordenada: [operador, entrada_1, entrada_2, ...].
• Codificação Sensível à Posição: Um codificador Transformer processa essas sequências com codificações posicionais. Isso permite que o modelo capture interações específicas de operadores e a consciência de posição (ex: distinguindo o sinal de controle das entradas de dados em um MUX).
• Processamento Recursivo: O embedding de um nó operador é atualizado com base na saída do Transformer para o primeiro token de sua sequência. Este embedding atualizado serve então como entrada para os operadores subsequentes no próximo nível lógico.
• Eficiência: Ao contrário de grafos gerais com distribuições de grau de cauda longa, grafos de circuitos possuem graus de entrada pequenos e limitados, evitando o overhead quadrático de memória tipicamente associado a Transformers.

2.2 Aprendizado de Deslocamento de Função (FSL)

Para abordar a dificuldade de prever funções globais complexas diretamente, o TRACE introduz o Aprendizado de Deslocamento de Função (Function Shift Learning), um objetivo de aprendizado inovador que desacopla o problema.

• Função Global ($y_{global}$): A verdadeira probabilidade de um nó ser lógica-1, que contabiliza todas as dependências (incluindo reconvergência). Calcular isso diretamente é caro ($O(2^k)$).
• Função Local ($y_{local}$): Uma aproximação simples assumindo independência de entrada. É computacionalmente eficiente ($O(1)$), mas falha em capturar o comportamento real na presença de reconvergência.
• Deslocamento de Função ($y_{FSL}$): O modelo é treinado para prever apenas a discrepância entre a função global e a local:
  $$y_{FSL} = y_{global} - y_{local}$$
• Treinamento: O modelo é treinado para regredir o deslocamento de função usando uma perda L1. O deslocamento real (ground truth) é pré-computado a partir dos dados de treinamento.
• Inferência: Durante a inferência, a função global é reconstruída iterativamente. Para cada nó, o modelo prevê o deslocamento, que é adicionado à função local (calculada usando as funções globais estimadas de seus predecessores) para gerar a estimativa global final.

3. Principais Contribuições

1. Alinhamento Arquitetural: A introdução de um Transformer Hierárquico que substitui a agregação invariante à permutação pelo processamento baseado em sequências e sensível à posição, espelhando fielmente o fluxo computacional de grafos de circuitos.
2. Objetivo de Aprendizado Desacoplado: A proposta do Aprendizado de Deslocamento de Função, que isola os efeitos contextuais complexos da reconvergência (o "deslocamento") da simples aproximação local, simplificando a tarefa de aprendizado.
3. Desempenho de Estado da Arte: A demonstração de que este paradigma combinado supera substancialmente as MPNNs e os Transformers de Grafos existentes em diversas modalidades de circuitos.

4. Resultados Experimentais

Os autores avaliaram o TRACE em três modalidades de circuitos (RTL, AIG, PM Netlists) em dois tipos de tarefas: aprendizado contrastivo e tarefas preditivas.

4.1 Tarefas Contrastivas

Em tarefas de recuperação (identificar circuitos funcionalmente equivalentes), o TRACE superou consistentemente todos os modelos de base:

• RTL: Alcançou 94,45% de Recall@1 (contra ~88% para o segundo melhor).
• AIG: Alcançou 92,68% de Recall@1 (contra ~88% para o segundo melhor).
• PM Netlist: Alcançou 90,81% de Recall@1 (contra ~86% para o segundo melhor).
• Notavelmente, muitos baselines de Transformer de Grafos (ex: GraphGPS, SGFormer) sofreram degradação severa de desempenho ou erros de Out-Of-Memory (OOM) em AIGs e PM Netlists, enquanto o TRACE permaneceu estável.

4.2 Tarefas Preditivas

Em tarefas de predição de propriedades de nível de nó (probabilidade de Lógica-1, similaridade, probabilidade de transição), o TRACE alcançou o menor Erro Médio Absoluto (MAE) e os maiores escores de $R^2$:

• AIG Combinacional: MAE de 0,015 para probabilidade de Lógica-1 (contra 0,027 do DeepGate4).
• AIG Sequencial: MAE de 0,009 para probabilidade de Lógica-1 e 0,005 para probabilidade de transição.
• PM Netlists: MAE de 0,013 para probabilidade de Lógica-1 (contra 0,048 do GraphSAGE).

4.3 Ablação e Análise

• Aprendizado de Deslocamento de Função: Remover o FSL degradou significativamente o desempenho. Por exemplo, na predição de probabilidade de PM Netlist, remover o FSL aumentou o MAE de 0,013 para 0,036 (um aumento de erro relativo de 63,9%).
• Acúmulo de Erro: A análise através dos níveis lógicos mostrou que o TRACE mantém um desempenho estável mesmo em níveis lógicos profundos, indicando robustez contra o acúmulo de erro durante o processo de inferência iterativa.

5. Significância

O artigo afirma que o TRACE estabelece um novo estado da arte para análise de circuitos e, de forma mais ampla, fornece um paradigma mais robusto e arquiteturalmente sólido para aprender em grafos de circuitos. Ao abordar o descompasso fundamental entre as arquiteturas padrão de aprendizado de grafos e a natureza da computação (especificamente a consciência de posição e a hierarquia), o TRACE demonstra que alinhar o viés indutivo do modelo com a estrutura do problema é crítico para capturar o comportamento funcional. O trabalho serve como uma prova de conceito de que o desacoplamento de aproximações locais de deslocamentos contextuais globais leva a uma generalização superior através de diversos dom domains de automação de projeto eletrônico (EDA).