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

Resumen Técnico: Contabilidad de Costos para Grafos Computacionales Reactivos

Planteamiento del Problema
La interpretabilidad mecanicista y el análisis de robustez dependen en gran medida de las cargas de trabajo de "barrido" (sweep): la modificación o ablación exhaustiva de sitios candidatos dentro del grafo computacional de una red para medir su impacto causal. En los marcos de trabajo estándar (e.g., PyTorch) o en los pipelines compilados (e.g., JAX, torch.compile), estas intervenciones suelen desencadenar una recomputación completa del paso hacia adelante (forward pass) o un nuevo trazado (re-trace) del programa para cada sitio candidato. Este enfoque ignora la validez parcial, pagando un costo proporcional al tamaño total del grafo independientemente de cuán localizada sea la intervención. Aunque los motores de grafos reactivos (como NeuroDSL) mantienen grafos persistentes donde las mutaciones invalidan únicamente el "cono descendente" (downstream cone) del nodo modificado, el costo agregado de realizar un barrido exhaustivo o una secuencia de mutaciones persistentes en tales motores no había sido cuantificado. Específicamente, no estaba claro cuánto aumento de velocidad podría lograr un barrido exhaustivo sobre las recomputaciones completas independientes, cómo la distribución del peso computacional a través de la profundidad de la red afecta este aumento, y cómo se comporta el costo bajo esquemas de mutación secuenciales versus por lotes (batched).

Metodología
El artículo emplea un riguroso marco de contabilidad combinatoria basado en las propiedades estructurales de los Grafos Acíclicos Dirigidos (DAGs) y la teoría de secuencias de variación regular (índices de Karamata).

1. Fundamento Teórico: El análisis se basa en un "Teorema de Localidad Estructural" (Teorema 1), que demuestra que en un motor reactivo, una mutación en un nodo $s$ invalida exactamente el conjunto de nodos $V^+_s$ (el cono descendente) alcanzables desde $s$.
2. Modelado Agregado: Los autores modelan la red como un DAG por capas con un perfil de peso computacional $w_j$ por capa. Definen la "razón de barrido agregada" $\rho(L)$ como el costo de $S \cdot L$ recomputaciones completas independientes dividido por el costo de un barrido exhaustivo utilizando la recomputación exacta del cono.
3. Análisis Asintótico: Utilizando el teorema de Karamata para secuencias de variación regular, el artículo deriva el límite de $\rho(L)$ a medida que la profundidad de la red $L \to \infty$, parametrizado por el índice de Karamata $q$ de la distribución de costos.
4. Análisis Secuencial vs. Por Lotes: El costo de los injertos (grafts) persistentes secuenciales (donde las mutaciones no se deshacen) se analiza rastreando la unión de los conos de invalidación. El artículo distingue entre ejecución "intercalada" (evaluación completa entre injertos) y ejecución "por lotes" (todos los injertos aplicados antes de la evaluación).
5. Análisis del Paso Atrás (Backward Pass): El marco se extiende a la retropropagación definiendo el "cono ascendente" ($V^-_s$) y analizando la intersección de los conjuntos de invalidación hacia adelante y hacia atrás.
6. Validación Empírica: Todas las afirmaciones teóricas se validan contra una implementación de referencia en NeuroDSL (un motor de grafo de definición y ejecución reactiva en Julia). Las mediciones incluyen el tiempo de ejecución (wall-clock timing) para la sobrecarga del intérprete y recuentos exactos de enteros de nodos inválidos para las identidades combinatorias.

Contribuciones Clave

1. El aumento de velocidad del barrido agregado no es universal:
   El artículo demuestra que la aceleración de un barrido exhaustivo sobre las recomputaciones completas no es una constante (e.g., 2), sino que depende de la distribución de costos de la red.

• Si el peso computacional está concentrado cerca de la salida (pesado en la salida, índice $q$), la aceleración converge a $(q+2)/(q+1)$.
• Si el peso está concentrado cerca de la entrada (pesado en la entrada), la aceleración converge a $q+2$.
• Solo en el caso de profundidad uniforme ($q=0$), la aceleración converge exactamente a 2.
• Refinamiento de Tiempo de Ejecución: Al contabilizar la sobrecarga fija del intérprete (medida como $\beta \approx 0.0054$ ms/nodo), el techo práctico de tiempo de ejecución para grafos uniformes cae a $\approx 1.79$, estrictamente por debajo del límite combinatorio de 2.

2. Costo Exacto de Mutaciones Secuenciales y por Lotes:

• Secuencial (Intercalada): Para una secuencia de $K$ injertos persistentes, el costo total es la suma de los costos aislados más un término de sobreconteo $\Delta(\pi) \ge 0$. Este sobreconteo depende del orden de inserción $\pi$ y del número de injertos aplicados a sitios que están aguas abajo de los sitios previamente injertados. El costo se minimiza aplicando los injertos en orden de "menor profundidad primero" y se maximiza con "mayor profundidad primero".
• Por Lotes (Batched): Si todos los injertos se aplican antes de cualquier evaluación, el costo es independiente del orden y subaditivo. Es igual al tamaño de la unión de todos los conos descendentes más los nodos nuevos, estrictamente menor que la suma de los costos aislados si algún sitio es comparable.

3. La Brecha de Localidad del Paso Atrás (Backward-Locality Gap):
   El artículo demuestra que el teorema de localidad tiene un espejo exacto para el paso atrás (conos ascendentes). Sin embargo, en arquitecturas sin conexiones de salto (skip connections) largas (e.g., pilas de Transformers secuenciales estándar), el cono ascendente de una mutación cubre casi todo el grafo. En consecuencia, la aceleración agregada de un barrido exhaustivo bajo la retropropagación colapsa a 1. Este resultado delimita precisamente la utilidad de la localidad reactiva: se aplica plenamente a los barridos de tiempo de inferencia (parcheo de activaciones, descubrimiento de circuitos), pero no ofrece aceleración agregada para los barridos de modo de entrenamiento en arquitecturas secuenciales.

4. Validación Empírica de Tolerancia Cero:
   El artículo valida sus afirmaciones en NeuroDSL con tolerancia cero para las identidades combinatorias y la convergencia de los límites asintóticos:

• Las razones de barrido medidas en grafos reales convergen a los límites predichos para cuatro perfiles de costo no uniformes.
• Las razones en modo de entrenamiento colapsan a 1 a la tasa predicha.
• Todos los 18 costos secuenciales por injerto y los totales por lotes coinciden exactamente con las predicciones de forma cerrada en diferentes órdenes de inserción.

Significancia y Reivindicaciones
El artículo afirma proporcionar la primera contabilidad de costos exacta y de forma cerrada para cargas de trabajo de grafos reactivos, reemplazando la suposición heurística de que "cada intervención cuesta un paso completo" con identidades combinatorias precisas.

• Establece que la eficiencia de las herramientas de interpretabilidad mecanicista (como el parcheo de activaciones) es una función del perfil de peso de profundidad de la red, no solo de la reactividad del motor.
• Clarifica el límite operativo de los motores reactivos: proporcionan aumentos de velocidad significativos para el análisis causal en tiempo de inferencia, pero no aceleran las búsquedas exhaustivas en tiempo de entrenamiento en arquitecturas secuenciales estándar.
• Ofrece orientación práctica para la implementación: el procesamiento por lotes de las mutaciones elimina la sobrecarga dependiente del orden, y se requieren capas de compilación que eliminen la sobrecarga del intérprete ($\beta$) para alcanzar los límites teóricos de aceleración combinatoria.

Los autores declaran explícitamente que estos resultados se derivan de las propiedades del motor NeuroDSL y del modelo específico de invalidación de "cono descendente". No afirman que estos resultados se apliquen a marcos que no mantengan banderas de validez persistentes o a arquitecturas con conexiones de salto largas que violen los supuestos de capas del modelo de costo.