LoRe: Adaptive Interaction-Evaluation Routing with Per-Step Interaction Budgets for Iterative Graph Solvers

Riepilogo Tecnico: LoRe – Instradamento Adattivo di Interazione-Valutazione per Risolutori Grafici Iterativi

1. Enunciato del Problema

I risolutori neurali iterativi per l'ottimizzazione combinatoria (CO), in particolare quelli basati su modelli di diffusione (ad es. DIFUSCO) e Reti Neurali su Grafi (GNN), affrontano un collo di bottiglia critico di scalabilità. Sebbene questi modelli raggiungano prestazioni elevate in compiti come il Massimo Insieme Indipendente (MIS) e il Problema del Commesso Viaggiatore (TSP), il loro costo di inferenza è dominato dalla valutazione ripetuta e densa delle topologie di interazione (ad es. tutti gli archi o le coppie di fattori) ad ogni passo di raffinamento.

Questa "scansione completa del supporto" comporta costi computazionali che scalano come $O(T|A|)$ e un utilizzo di memoria di picco che cresce linearmente con la dimensione dell'insieme di interazioni $|A|$. Di conseguenza, istanze su larga scala spesso superano i limiti di memoria dell'hardware (Out-Of-Memory, o OOM) o comportano latenze inaccettabili. Le soluzioni esistenti presentano un dilemma:

• Riduzione dei passi (ad es. Distillazione): Riduce il tempo totale ma non diminuisce la memoria di picco richiesta per passo.
• Sparsificazione Statica (ad es. grafi kNN fissi): Riduce la memoria per passo ma non riesce a catturare la natura dipendente dallo stato dei conflitti combinatori. Nel raffinamento iterativo, i "punti caldi" di alto conflitto o incertezza si spostano nel tempo; un supporto sparso fisso inevitabilmente trascura le interazioni diventate critiche, portando all'accumulo di errori e alla deriva della traiettoria.

2. Metodologia: Il Protocollo LoRe

Ispirandosi alle metodologie computazionali della fisica della materia condensata—specificamente alla Teoria del Campo Medio Dinamica a Cluster (C-DMFT)—gli autori propongono LoRe (Local Recompute). LoRe è un wrapper di inferenza senza addestramento, integrabile immediatamente, che impone un budget di valutazione delle interazioni per passo.

Invece di valutare tutte le interazioni, LoRe instrada dinamicamente il calcolo verso un sottoinsieme variabile nel tempo di interazioni ($M_t$), approssimando il resto. Questo implementa una decomposizione Cluster-Bagno:

• Il Cluster ($M_t$): Un sottoinsieme dinamicamente selezionato di interazioni ad alto conflitto (archi o coppie di fattori) che vengono valutate esattamente ad ogni passo.
• Il Bagno ($A \setminus M_t$): Le interazioni omesse il cui influsso è approssimato tramite un segnale globale leggero di richiamo, impedendo che il cluster locale si disconnetta dallo stato globale.

Componenti Tecnici Chiave:

1. Instradamento Dinamico: Ad ogni passo $t$, LoRe identifica un sottoinsieme $M_t$ tale che $|M_t| \le \rho|A|$, dove $\rho$ è un rapporto di budget fisso. La selezione si basa su un punteggio proxy $s_{t,a}$ che priorizza:
   • Incertezza degli Estremi: Interazioni in cui gli stati dei nodi sono indecisi (ad es. $x_i \approx 0.5$).
   • Instabilità Temporale: Interazioni in cui gli stati dei nodi sono cambiati significativamente rispetto al passo precedente.
   • Scheletro Statico: Un piccolo insieme fisso di archi strutturalmente importanti (ad es. nodi ad alto grado) viene mantenuto per garantire stabilità strutturale.
   • L'insieme $M_t$ viene aggiornato ogni $R$ passi per tracciare i punti caldi in deriva.
2. Richiamo Globale (Opzionale): Per approssimare l'influsso del "Bagno" omesso, viene calcolato un segnale globale a basso costo $g_t$ tramite pooling su $A \setminus M_t$. Questo segnale è accoppiato al cluster tramite un'interpolazione ponderata sulla copertura priva di parametri, agendo come una correzione di campo medio.
3. Operatore con Budget: L'operatore denso standard $T_t$ è sostituito da un operatore con budget $\tilde{T}_t$ che esegue la valutazione esatta solo su $M_t$ e applica il termine di richiamo per il resto. Il post-processing (proiezione/riparazione) rimane identico alla baseline per garantire un confronto equo.

3. Contributi Chiave

• Formulazione Concettuale: Il documento formalizza il budgeting dell'operatore per passo per i risolutori grafici iterativi, stabilendo un quadro per vincolare gli inviluppi computazionali e di memoria all'interno di ogni passo di raffinamento senza alterare l'orizzonte del risolutore o i parametri del backbone.
• Il Protocollo LoRe: Introduzione di un wrapper di runtime senza addestramento che implementa la decomposizione Cluster-Bagno ispirata alla fisica. Induce sparsità temporale dell'operatore tramite instradamento dinamico e dipendente dallo stato, anziché sparsificazione spaziale statica.
• Contabilità Auditabile: Gli autori stabiliscono un protocollo di contabilità end-to-end del tempo reale completamente inclusivo. Tutte le metriche riportate (tempo e memoria) includono i passi di diffusione, l'overhead di instradamento e il post-processing, fornendo un benchmark trasparente per l'inferenza vincolata dalle risorse.
• Validazione Empirica: Dimostrazione che l'instradamento dinamico supera significativamente forti alternative statiche a budget pari, estendendo le scale di inferenza fattibili e fornendo sostanziali accelerazioni mantenendo la qualità della soluzione.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti sul Massimo Insieme Indipendente (MIS) e sul Problema del Commesso Viaggiatore (TSP) utilizzando il codice DIFUSCO e checkpoint pre-addestrati.

• Scalabilità e Fattibilità di Memoria (MIS):

  • LoRe estende l'inferenza fattibile oltre 3× rispetto al limite OOM della baseline.
  • A $n=15.000$ nodi (la scala più grande in cui la baseline è fattibile), LoRe raggiunge un'accelerazione di 8,16× e riduce la memoria GPU di picco di ~12× (da 86,7 GB a 7,32 GB) mantenendo la qualità della soluzione (Retention $\approx$ 1,01).
  • La baseline fallisce (OOM) a $n=20.000$, mentre LoRe rimane fattibile fino a $n=50.000$.

• Generalizzazione Cross-Task (TSP):

  • LoRe raggiunge un'accelerazione di ~15× a $n=1.000$ e una riduzione della memoria di 44×.
  • La qualità della soluzione (lunghezza del tour) rimane competitiva con la baseline (Retention 0,94–1,01 attraverso le scale).
  • Il metodo si generalizza al TSP senza re-addestramento, utilizzando lo stesso checkpoint addestrato in modo denso.

• Validazione del Meccanismo (Ablazione):

  • Esperimenti controllati che confrontano LoRe con supporti statici (maschere fisse) e strategie dinamiche greedy confermano che il re-instradamento dipendente dallo stato è essenziale. I supporti statici non riescono a tracciare i conflitti in deriva, portando a saturazione precoce e incapacità di trovare soluzioni fattibili.
  • L'approccio ibrido di LoRe (scheletro statico + punti caldi dinamici) si dimostra più stabile della selezione greedy puramente dinamica.

• Robustezza:

  • Spostamenti di Topologia Zero-Shot: LoRe mantiene un'accelerazione di ~8× e una riduzione della memoria di ~12× attraverso le famiglie di grafi Erdős–Rényi (ER), Barabási–Albert (BA) e Watts–Strogatz (WS) senza re-addestramento.
  • Sensibilità agli Iperparametri: Il metodo è largamente insensibile agli iperparametri; una singola configurazione ($\rho=0,08, R=10$) funziona efficacemente su diversi compiti e densità di grafi.

5. Significato e Affermazioni

Il documento afferma che LoRe affronta un collo di bottiglia fondamentale nel deployment di risolutori neurali iterativi per l'ottimizzazione combinatoria su larga scala. Spostando il paradigma dalla "valutazione densa" all'"instradamento dinamico consapevole del budget", LoRe trasforma il profilo di scalabilità di questi risolutori.

• Praticità: Consente la soluzione di istanze di problemi attualmente non fattibili a causa di vincoli di memoria (OOM), spostando efficacemente il confine di ciò che è risolvibile su hardware standard.
• Efficienza: Fornisce sostanziali accelerazioni del tempo reale (fino a 15×) e riduzioni della memoria (fino a 44×) senza richiedere re-addestramento del modello o cambiamenti architetturali.
• Generalità: In quanto wrapper integrabile, è agnostico rispetto al paradigma e può essere applicato a vari risolutori iterativi (ad es. T2TCO, COExpander) e compiti (MIS, TSP) con minima adattamento.

Gli autori concludono che LoRe fornisce un meccanismo rigoroso e senza addestramento per imporre vincoli di risorse per passo, rendendo i risolutori neurali iterativi fattibili per sistemi decisionali reali su larga scala dove latenza e memoria sono vincoli vincolanti.