Riepilogo Tecnico: Ripensare l'Efficienza nella Combinatorial Optimization Neurale: Batched Preference Optimization con Mamba

1. Definizione del Problema

L'Ottimizzazione Combinatoria Neurale (NCO) si è evoluta dalle prime Pointer Networks a architetture basate su Transformer (es. AM, POMO) e Generative Flow Networks. Sebbene questi metodi abbiano migliorato la qualità delle soluzioni, affrontano significativi colli di bottiglia in termini di efficienza, in particolare per quanto riguarda la scalabilità e la velocità di convergenza dell'addestamento.

Il documento identifica due fonti primarie di inefficienza nei lavori NCO esistenti:

1. Paradigma di Apprendimento: Il tradizionale Reinforcement Learning (RL) online accoppia strettamente la generazione di traiettorie (rollout) con gli aggiornamenti dei parametri. Questo ciclo "campiona-e-aggiorna" sottoutilizza il parallelismo delle GPU e costringe ogni passo di ottimizzazione a dipendere da una nuova generazione autoregressiva, portando a una convergenza lenta e ad alti costi hardware.
2. Architettura Neurale: Le architetture NCO allo stato dell'arte si affidano pesantemente all'architettura Transformer. Nonostante le ottimizzazioni come FlashAttention, l'interazione token-token sottostante rimane quadratica ($O(N^2)$ rispetto alla lunghezza della sequenza). Ciò causa un'esplosione della memoria e problemi di latenza su istanze di routing a lungo termine (es. TSP con migliaia di nodi), limitando l'implementazione pratica della NCO su problemi su larga scala.

La domanda centrale affrontata è: Come possiamo migliorare l'efficienza della NCO senza sacrificare la qualità della soluzione?

2. Metodologia: Il Framework ECO

Gli autori propongono ECO, un framework orientato all'efficienza che scinde la generazione delle traiettorie dagli aggiornamenti dei gradienti e sostituisce l'architettura Transformer con un'architettura basata su Mamba.

A. Paradigma di Batched Preference Optimization

ECO introduce un flusso di lavoro di addestramento in due fasi che passa da un rigoroso RL online a un paradigma "batch o offline-in-update":

1. Fase I: Supervised Warm-up (SFT): La policy viene inizializzata tramite behavior cloning su soluzioni pre-calcolate di alta qualità (generate da LKH-3 o euristiche). Questo fornisce una comprensione fondamentale dei vincoli di routing e dell'ottimalità locale.
2. Fase II: Iterative Direct Preference Optimization (DPO): Invece di addestrare una funzione di valore (Critic) separata come in PPO, ECO usa DPO per ottimizzare direttamente la policy partendo da preferenze a coppie.
   • Workflow: La policy corrente genera un batch di soluzioni candidate. Le coppie di preferenza (Vincitore/Perdente) sono costruite in base alla lunghezza del tour.
   • Modello di Riferimento: Un modello di riferimento ($\pi_{ref}$) viene aggiornato periodicamente (ogni $T$ passi) per ancorare la divergenza KL, stabilizzando il miglioramento iterativo.
   • LS-Augmented Bootstrapping: Per prevenire la scomparsa dei gradienti causata dai margini di ricompensa ristretti man mano che la policy migliora, un operatore di ricerca locale (LS) leggero (es. 2-opt, 3-opt) viene applicato alle soluzioni generate dal modello durante l'addestramento. La soluzione raffinata diventa il "Vincitore", mentre l'output grezzo diventa il "Perdente". Fondamentalmente, la ricerca locale non viene mai utilizzata durante l'inferenza; serve solo a costruire segnali di addestramento più forti che vengono distillati nella policy neurale.

B. Architettura Mista Basata su Mamba

Per affrontare la scalabilità quadratica della memoria dei Transformer, ECO impiega un'architettura Mamba (State Space Model) personalizzata:

1. Encoder Mamba Ricorrente: Utilizza strati Mamba impilati (impostazione S6) per elaborare le sequenze di nodi. A differenza dei Transformer, Mamba utilizza la modellazione di sequenze a memoria lineare. Per gestire la natura non-permutazione-equivalente di Mamba, gli input vengono canonizzati (es. ordinati tramite codice Morton/Z-order) prima della codifica.
2. Decoder S4: Utilizza strati in stile S4 per il calcolo parallelo con teacher-forcing durante l'addestramento e aggiornamenti dello stato ricorrente efficienti durante l'inferenza.
3. Scoring Autoregressivo: Il framework mantiene lo standard passaggio di scoring dei candidati autoregressivi (compatibilità stile-pointer). Gli autori notano esplicitamente che, sebbene l'encoder e gli aggiornamenti dello stato ricorrente diventino lineari, lo scoring delle azioni rimane quadratico nel caso peggiore ($O(N^2)$) perché richiede il confronto dello stato corrente contro tutti i candidati fattibili. Tuttavia, l'architettura riduce significativamente la pressione della memoria dell'encoder e i costi dello stato ricorrente.

3. Contributi Chiave

Il documento delinea tre contributi primari:

1. Primo Solutore NCO basato su Mamba: Gli autori introducono il primo solutore NCO basato su Mamba, fornendo una decomposizione della complessità che mostra come Mamba riduca la scalabilità della memoria dell'encoder e i costi dello stato di decodifica ricorrente, sebbene lo scoring dei candidati autoregressivo ingenuo rimanga quadratico.
2. Framework Orientato all'Efficienza: Un'integrazione innovativa di un'architettura Mamba personalizzata, un pipeline di ottimizzazione delle preferenze a due fasi (SFT + Iterative DPO) e una strategia di bootstrapping guidata dalla ricerca locale per stabilizzare l'addestramento e amplificare i margini di preferenza.
3. Analisi Empirica Esaustiva: Casi di studio estesi su TSP e CVRP dimostrano che ECO raggiunge prestazioni neurali migliori o competitive con guadagni di efficienza sostanziali, particolarmente su istanze di grandi dimensioni. L'analisi include decomposizione della complessità, test di sensibilità alla permutazione e studi di ablazione su ciascun componente del design.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su TSP ($N \in \{200, 500, 1000, 5000\}$) e CVRP ($N \in \{100, 200, 500, 1000\}$ utilizzando una singola GPU NVIDIA A800.

• Qualità della Soluzione: ECO raggiunge i risultati migliori o competitivi tra i baseline neurali (AM, POMO, LEHD, CNF, GFlowNet-HBG) nella maggior parte delle scale.
  • Su TSP5000, ECO raggiunge un gap del 5,49%, mentre i baseline basati su Transformer (AM, POMO) soffrono di un degrado severo con gap superiori al 70-89%.
  • Su CVRP1000, ECO raggiunge un gap del 2,87%, superando o eguagliando altri metodi neurali.
• Scalabilità e Memoria:
  • Memoria: Il baseline Transformer innesca errori Out-Of-Memory (OOM) a $N \approx 7000$ su una GPU da 80GB a causa della memoria dell'attenzione quadratica. ECO mantiene una crescita della memoria quasi lineare, rimanendo entro i limiti anche a $N=10.000$ (circa 40GB).
  • Throughput: ECO sostiene un throughput di inferenza significativamente più alto su sequenze lunghe rispetto ai Transformer, poiché può utilizzare batch più grandi senza colpire i limiti di memoria.
• Efficienza dell'Addestramento:
  • ECO converge molto più velocemente degli standard baseline online.
  • Confrontando DPO con PPO con lo stesso backbone Mamba, ECO ottiene una qualità comparabile (gap del 4,84% vs 4,88% su TSP1000) ma riduce il tempo di addestramento da 34,5 ore a 10,2 ore.
• Analisi dei Componenti:
  • Bootstrapping LS: Rimuovere la guida LS aumenta il gap di TSP1000 dal 4,84% al 9,55%, confermando che la LS fornisce un segnale di addestramento più forte che viene distillato nella policy.
  • Warm-up SFT: L'addestramento senza SFT porta a instabilità e divergenza, confermando la necessità di una policy iniziale competente.
  • Architettura: Sostituire Mamba con Transformer sotto lo stesso obiettivo DPO aumenta il gap (5,47% vs 4,84%) e il tempo di addestramento, provando che il beneficio architettonico è indipendente dall'obiettivo di ottimizzazione.

5. Significato e Rivendicazioni

Il documento afferma che ECO rappresenta un passo significativo verso i solutori di routing neurali scalabili e pratici, affrontando il gap di "efficienza" che è stato ampiamente trascurato a favore della qualità della soluzione.

• Rivendicazioni Modeste sulla Linearità: Gli autori sono espliciti nel dire che ECO non rende l'intero processo di inferenza costruttiva lineare in $N$. Il beneficio è specifico: riduce la scalabilità della memoria dell'encoder e i costi dello stato ricorrente, e migliora l'utilizzo dell'hardware tramite kernel di scan e aggiornamenti in batch. Lo step finale di scoring delle azioni rimane quadratico.
• Addestramento vs Inferenza: Una scoperta chiave è che la ricerca locale è un meccanismo strettamente di addestramento. I guadagni di prestazione di ECO rispetto alle versioni ablate sono attribuiti ai parametri della rete migliorati appresi dai segnali guidati da LS, non al post-processing durante l'inferenza.
• Consapevolezza dell'Hardware: Il lavoro dimostra che combinare un'architettura consapevole dell'hardware (Mamba) con paradigmi di addestramento efficienti (Batched DPO) permette ai modelli NCO di scalare a migliaia di nodi su hardware di classe consumer o su singola GPU, dove i modelli tradizionali basati su attenzione falliscono a causa dei vincoli di memoria.

In conclusione, ECO fornisce una direzione solida per il routing neurale scalabile, unificando un backbone a memoria lineare con una pipeline di apprendimento delle preferenze a batch stabile, raggiungendo una qualità della soluzione competitiva con profili di memoria e throughput marcatamente migliori.