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

Sintesi Tecnica: Contabilità dei Costi per Grafi Computazionali Reattivi

Problematica
L'interpretabilità meccanicistica e l'analisi della robustezza si basano pesantemente su carichi di lavoro di tipo "sweep": l'esaurimento di patching o ablazione di siti candidati all'interno del grafo computazionale di una rete neurale per misurarne l'impatto causale. Nei framework eager standard (es. PyTorch) o nelle pipeline compilate (es. JAX, torch.compile), questi interventi tipicamente innescano una ricalcolazione completa del passaggio forward (o una nuova tracciatura del programma) per ogni sito candidato. Questo approccio ignora la validità parziale, pagando un costo proporzionale all'intera dimensione del grafo indipendentemente da quanto l'intervento sia localizzato. Sebbene i motori a grafi reattivi (come NeuroDSL) mantengano grafi persistenti dove le mutazioni invalidano solo il "cono a valle" del nodo modificato, il costo aggregato di un esauriente sweep o di una sequenza di mutazioni persistenti su tali motori è rimasto non quantificato. Nello specifico, non era chiaro quanto di accelerazione un esauriente sweep potrebbe ottenere rispetto a ricalcolazioni complete indipendenti, come la distribuzione del peso computazionale attraverso la profondità della rete influenzi tale accelerazione, e come il costo si comporti sotto programmi di mutazione sequenziali rispetto a quelli batch.

Metodologia
Il documento impiega un rigoroso framework di contabilità combinatoria basato sulle proprietà strutturali dei Grafi Aciclici Diretti (DAG) e sulla teoria delle sequenze regolarmente variabili (indici di Karamata).

1. Fondazione Teorica: L'analisi si basa su un "Teorema di Località Strutturale" (Teorema 1), che dimostra che in un motore reattivo, una mutazione in un nodo $s$ invalida esattamente l'insieme dei nodi $V^+_s$ (il cono a valle) raggiungibili da $s$.
2. Modellazione Aggregata: Gli autori modellano la rete come un DAG a strati con un profilo di peso computazionale $w_j$ per strato. Definiscono il "rapporto di sweep aggregato" $\rho(L)$ come il costo di $S \cdot L$ ricalcolazioni complete indipendenti diviso per il costo di uno sweep esaustivo tramite ricalcolo esatto del cono.
3. Analisi Asintotica: Utilizzando il teorema di Karamata per le sequenze regolarmente variabili, il documento deriva il limite di $\rho(L)$ al crescere della profondità della rete $L \to \infty$, parametrizzato dall'indice di Karamata $q$ della distribuzione dei costi.
4. Analisi Sequenziale vs. Batch: Il costo di innesti persistenti sequenziali (dove le mutazioni non vengono annullate) viene analizzato tracciando l'unione dei coni di invalidazione. Il documento distingue tra esecuzione "interleaved" (valutazione completa tra gli innesti) ed esecuzione "batch" (tutti gli innesti applicati prima della valutazione).
5. Analisi del Passaggio Backward: Il framework viene esteso alla backpropagation definendo il "cono a monte" ($V^-_s$) e analizzando l'intersezione degli insiemi di invalidazione forward e backward.
6. Validazione Empirica: Tutte le affermazioni teoriche sono validate contro un'implementazione di riferimento in NeuroDSL (un motore a grafo reattivo "define-and-run" in Julia). Le misurazioni includono il tempo di esecuzione (wall-clock) per l'overhead dell'interprete e il conteggio esatto di nodi invalidi per le identità combinatorie.

Contributi Chiave

1. L'accelerazione dello sweep esaustivo non è universale:
   Il documento dimostra che l'accelerazione di uno sweep esaustivo rispetto alle ricalcolazioni complete non è una costante (es. 2) ma dipende dalla distribuzione dei costi della rete.

   • Se il peso computazionale è concentrato vicino all'output (pesante in output, indice $q$), l'accelerazione converge a $(q+2)/(q+1)$.
   • Se il peso è concentrato vicino all'input (pesante in input), l'accelerazione converge a $q+2$.
   • Solo nel caso di profondità uniforme ($q=0$), l'accelerazione converge esattamente a 2.
   • Raffinamento del Tempo di Esecuzione: Tenendo conto di un overhead fisso dell'interprete (misurato come $\beta \approx 0.0054$ ms/nodo), il limite pratico del wall-clock per grafi uniformi scende a $\approx 1.79$, strettamente al di sotto del limite combinatorio di 2.

2. Costo Esatto di Mutazioni Sequenziali e Batch:

   • Sequenziale (Interleaved): Per una sequenza di $K$ innesti persistenti, il costo totale è la somma dei costi isolati più un termine di sovraconto $\Delta(\pi) \ge 0$. Questo sovraconto dipende dall'ordine di inserimento $\pi$ e dal numero di innesti applicati a siti che sono a valle di siti precedentemente innestati. Il costo è minimizzato applicando gli innesti in ordine "dal più superficiale al più profondo" (shallowest-first) e massimizzato con l'ordine "dal più profondo al più superficiale" (deepest-first).
   • Batch: Se tutti gli innesti sono applicati prima di qualsiasi valutazione, il costo è indipendente dall'ordine ed è sub-additivo. Esso equivale alla dimensione dell'unione di tutti i coni a valle più i nuovi nodi, strettamente minore della somma dei costi isolati se alcuni siti sono comparabili.

3. Il Gap di Località Backward:
   Il documento dimostra che il teorema di località ha un riflesso esatto per il passaggio backward (coni a monte). Tuttavia, su architetture prive di lunghe connessioni skip (es. stack Transformer sequenziali standard), il cono a monte di una mutazione copre quasi l'intero grafo. Di conseguenza, l'accelerazione aggregata di uno sweep esaustivo sotto backpropagation collassa a 1. Questo risultato delimita precisamente l'utilità della località reattiva: essa si applica pienamente all'analisi causale al tempo di inferenza (activation patching, circuit discovery), ma non offre alcun miglioramento di velocità aggregato per i sweep in modalità training su architetture sequenziali.

4. Validazione Empirica a Tolleranza Zero:
   Il documento valida le proprie tesi su NeuroDSL con tolleranza zero per le identità combinatorie e la convergenza per i limiti asintotici:

   • I rapporti di sweep misurati su grafi reali convergono ai limiti previsti per quattro profili di costo non uniformi.
   • I rapporti in modalità training collassano a 1 al tasso previsto.
   • Tutti i 18 costi sequenziali per singolo innesto e i totali batch corrispondono esattamente alle previsioni in forma chiusa attraverso diversi ordini di inserimento.

Significatività e Rivendicazioni
Il documento sostiene di fornire il primo conto dei costi esatto e in forma chiusa per i carichi di lavoro a grafi reattivi, sostituendo l'assunzione euristica che "ogni intervento costa un intero passaggio" con precise identità combinatorie.

• Stabilisce che l'efficienza degli strumenti di interpretabilità meccanicistica (come l'activation patching) è una funzione del profilo di profondità-peso della rete, non solo della reattività del motore.
• Chiarisce il confine operativo dei motori reattivi: essi forniscono significativi miglioramenti di velocità per l'analisi causale al tempo di inferenza, ma non accelerano la ricerca esaustiva in tempo di training su architetture sequenziali standard.
• Offre una guida pratica per l'implementazione: il batching delle mutazioni elimina l'overhead dipendente dall'ordine, ed è necessario che i livelli del compilatore rimuovano l'overhead dell'interprete ($\beta$) per raggiungere i limiti teorici di accelerazione combinatoria.

Gli autori dichiarano esplicitamente che questi risultati derivano dalle proprietà del motore NeuroDSL e dal modello specifico di invalidazione del "cono a valle". Non pretendono che questi risultati si applichino a framework che non mantengono flag di validità persistenti o ad architetture con lunghe connessioni skip che violano le assunzioni di stratificazione del modello di costo.