Cost Accounting for Reactive Computational Graphs: Exhaustive Sweeps, Sequential Mutation, and the Backward-Locality Gap

Resumo Técnico: Contabilidade de Custos para Grafos Computacionais Reativos

Problema
A interpretabilidade mecanística e a análise de robustez dependem fortemente de cargas de trabalho de "varredura" (sweep): o processo exaustivo de realizar patches ou ablações em candidatos a sítios dentro do grafo computacional de uma rede neural para medir seu impacto causal. Em frameworks eager padrão (ex: PyTorch) ou pipelines compilados (ex: JAX, torch.compile), essas intervenções tipicamente disparam uma recomputação completa da passagem direta (ou um novo rastreamento do programa) para cada candidato a sítio. Essa abordagem ignora a validade parcial, pagando um custo proporcional ao tamanho total do grafo, independentemente de quão localizada seja a intervenção. Embora motores de grafos reativos (como o NeuroDSL) mantenham grafos persistentes onde mutações invalidam apenas o "cone descendente" (downstream cone) do nó modificado, o custo agregado de realizar uma varredura exaustiva ou uma sequência de mutações persistentes em tais motores permaneceu não quantificado. Especificamente, não estava claro quanto de aceleração uma varredura exaustiva poderia alcançar em relação a recomputações completas independentes, como a distribuição do peso computacional através da profundidade da rede afeta essa aceleração, e como o custo se comporta sob cronogramas de mutação sequenciais versus em lote (batched).

Metodologia
O artigo emprega um rigoroso framework de contabilidade combinatória fundamentado nas propriedades estruturais de Grafos Acíclicos Dirigidos (DAGs) e na teoria de sequências de variação regular (índices de Karamata).

1. Fundamentação Teórica: A análise baseia-se em um "Teorema de Localidade Estrutural" (Teorema 1), que prova que, em um motor reativo, uma mutação em um nó $s$ invalida exatamente o conjunto de nós $V^+_s$ (o cone descendente) alcançáveis a partir de $s$.
2. Modelagem Agregada: Os autores modelam a rede como um DAG em camadas com um perfil de peso computacional $w_j$ por camada. Eles definem a "razão de varredura agregada" $\rho(L)$ como o custo de $S \cdot L$ recomputações completas independentes dividido pelo custo de uma varredura exaustiva usando a recomputação exata do cone.
3. Análise Assintótica: Usando o teorema de Karamata para sequências de variação regular, o artigo deriva o limite de $\rho(L)$ conforme a profundidade da rede $L \to \infty$, parametrizado pelo índice de Karamata $q$ da distribuição de custo.
4. Análise Sequencial vs. Em Lote: O custo de enxertos (grafts) persistentes sequenciais (onde as mutações não são desfeitas) é analisado rastreando a união dos cones de invalidação. O artigo distingue entre execução "intercalada" (avaliação completa entre enxertos) e execução "em lote" (todos os enxertos aplicados antes da avaliação).
5. Análise do Passo de Retropropagação: O framework é estendido à retropropagação ao definir o "cone ascendente" ($V^-_s$) e analisar a interseção dos conjuntos de invalidação direto e inverso.
6. Validação Empírica: Todas as afirmações teóricas são validadas contra uma implementação de referência no NeuroDSL (um motor de grafo reativo define-and-run em Julia). As medições incluem o tempo de execução (wall-clock) para o overhead do intérprete e contagens exatas de inteiros de nós inválidos para identidades combinatórias.

Principais Contribuições

1. A Aceleração da Varredura Agregada Não é Universal:
   O artigo prova que a aceleração de uma varredura exaustiva sobre recomputações completas não é uma constante (ex: 2), mas depende da distribuição de custo da rede.

• Se o peso computacional estiver concentrado próximo à saída (pesada na saída, índice $q$), a aceleração converge para $(q+2)/(q+1)$.
• Se o peso estiver concentrado próximo à entrada (pesada na entrada), a aceleração converge para $q+2$.
• Somente no caso de profundidade uniforme ($q=0$) a aceleração converge exatamente para 2.
• Refinamento de Tempo de Execução: Ao considerar o overhead fixo do intérprete (medido como $\beta \approx 0,0054$ ms/nó), o teto prático de tempo de execução para grafos uniformes cai para $\approx 1,79$, estritamente abaixo do limite combinatório de 2.

2. Custo Exato de Mutações Sequenciais e em Lote:

• Sequencial (Intercalada): Para uma sequência de $K$ enxertos persistentes, o custo total é a soma dos custos isolados mais um termo de excesso $\Delta(\pi) \ge 0$. Esse excesso depende da ordem de inserção $\pi$ e do número de enxertos aplicados a sítios que estão a jusante (downstream) de sítios previamente enxertados. O custo é minimizado aplicando enxertos na ordem "mais rasa primeiro" e maximizado na ordem "mais profunda primeiro".
• Em Lote: Se todos os enxertos forem aplicados antes de qualquer avaliação, o custo é independente da ordem e subaditivo. Ele equivale ao tamanho da união de todos os cones descendentes mais os novos nós, sendo estritamente menor que a soma dos custos isolados se houver sítios comparáveis.

3. O Gap de Localidade do Passo de Retropropagação:
   O artigo prova que o teorema de localidade possui um espelho exato para o passo de retropropagação (cones ascendentes). No entanto, em arquiteturas sem conexões de salto (skip connections) longas (ex: pilhas de Transformers sequenciais padrão), o cone ascendente de uma mutação cobre quase todo o grafo. Consequentemente, a aceleração agregada de uma varredura exaustiva sob retropropagação colapsa para 1. Este resultado delimita precisamente a utilidade da localidade reativa: ela se aplica plenamente a varreduras de tempo de inferência (patching de ativação, descoberta de circuitos), mas não oferece aceleração agregada para varreduras de modo de treinamento em arquiteturas sequenciais.

4. Validação Empírica de Tolerância Zero:
   O artigo valida suas afirmações no NeuroDSL com tolerância zero para identidades combinatórias e convergência para limites assintóticos:

• As razões de varredura medidas em grafos reais convergem para os limites previstos para quatro perfis de custo não uniformes.
• As razões de modo de treinamento colapsam para 1 na taxa prevista.
• Todos os 18 custos sequenciais por enxerto e os totais em lote coincidem exatamente com as previsões de forma fechada em diferentes ordens de inserção.

Significância e Alegações
O artigo afirma fornecer a primeira contabilidade de custo exata e de forma fechada para cargas de trabalho de grafos reativos, substituando a suposição heurística de que "cada intervenção custa uma passagem completa" por identidades combinatórias precisas.

• Estabelece que a eficiência das ferramentas de interpretabilidade mecanística (como o activation patching) é uma função do perfil de peso de profundidade da rede, não apenas da reatividade do motor.
• Esclarece o limite operacional dos motores reativos: eles fornecem acelerações significativas para análise causal em tempo de inferência, mas não aceleram buscas exaustivas em tempo de treinamento em arquiteturas sequenciais padrão.
• Oferece orientação prática para implementação: o agrupamento (batching) de mutações elimina o overhead dependente da ordem, e camadas de compilação que removam o overhead do intérprete ($\beta$) são necessárias para atingir os limites teóricos de aceleração combinatória.

Os autores declaram explicitamente que estes resultados derivam das propriedades do motor NeuroDSL e do modelo específico de invalidação de "cone descendente". Eles não alegam que estes resultados se apliquem a frameworks que não mantêm flags de validade persistentes ou a arquiteturas com conexões de salto longas que violem as suposições de camada do modelo de custo.