Technische Samenvatting: Heroverweging van Efficiëntie in Neurale Combinatorische Optimalisatie: Batched Preference Optimization met Mamba

1. Probleemstelling

Neurale Combinatorische Optimalisatie (NCO) is geëvolueerd van vroege Pointer Networks naar Transformer-gebaseerde architecturen (bijv. AM, POMO) en Generative Flow Networks. Hoewel deze methoden de oplossingskwaliteit hebben verbeterd, kampen ze met aanzienlijke efficiëntieproblemen, met name wat betreft schaalbaarheid en convergentiesnelheid tijdens de training.

Het artikel identificeert twee primaire bronnen van inefficiëntie in bestaande NCO-werken:

1. Leersparadigma: Traditionele online Reinforcement Learning (RL) koppelt trajectgeneratie (rollouts) nauw aan parameterupdates. Deze "sample-dan-update"-lus benut GPU-parallellisme onderbenut en dwingt elke optimalisatiestap om afhankelijk te zijn van verse, autoregressieve generatie, wat leidt tot trage convergentie en hoge hardwarekosten.
2. Neurale Architectuur: State-of-the-art NCO-modellen vertrouwen zwaar op de Transformer-architectuur. Ondanks optimalisaties zoals FlashAttention blijft de onderliggende token-token interactie kwadratisch ($O(N^2)$) in sequentielengte. Dit veroorzaakt een explosie van het geheugengebruik en latentieproblemen bij lange routing-instanties (bijv. TSP met duizenden knopen), wat de praktische inzetbaarheid van NCO op grootschalige problemen beperkt.

De kernvraag die wordt geadresseerd is: Hoe kunnen we de efficiëntie van NCO verbeteren zonder de oplossingskwaliteit op te offeren?

2. Methodologie: Het ECO-framework

De auteurs stellen ECO voor, een efficiëntiegericht framework dat de trajectgeneratie ontkoppelt van gradiëntupdates en de Transformer-backbone vervangt door een Mamba-gebaseerde architectuur.

A. Batched Preference Optimization Paradigma

ECO introduceert een tweetraps workflow voor training die verschuift van strikte online RL naar een "batched of offline-in-update" paradigma:

1. Fase I: Supervised Warm-up (SFT): De policy wordt geïnitialiseerd via behavior cloning op hoogwaardige, vooraf berekende oplossingen (gegenereerd door LKH-3 of heuristieken). Dit biedt een basisbegrip van routing-restricties en lokale optimaliteit.
2. Fase II: Iteratieve Directe Preference Optimization (DPO): In plaats van een aparte waarde-functie (Critic) te trainen zoals bij PPO, gebruikt ECO DPO om de policy direct te optimaliseren op basis van paarwijze voorkeuren.
   • Workflow: De huidige policy genereert een batch kandidaat-oplossingen. Voorkeursparen (Winner/Loser) worden geconstrueerd op basis van de tour-lengte.
   • Referentiemodel: Een referentiemodel ($\pi_{ref}$) wordt periodiek (elke $T$ stappen) bijgewerkt om de KL-divergentie te verankeren, wat de iteratieve verbetering stabiliseert.
   • LS-Augmented Bootstrapping: Om verdwijnende gradiënten te voorkomen die worden veroorzaakt door smalle beloningsmarges naarmate de policy verbetert, wordt een lichtgewicht Local Search (LS) operator (bijv. 2-opt, 3-opt) toegepast op door het model gegenereerde oplossingen tijdens de training. De verfijnde oplossing wordt de "Winner", en de ruwe output wordt de "Loser". Cruciaal is dat Local Search nooit wordt gebruikt tijdens de inferentie; het dient enkel om sterkere trainingssignalen te construeren die in de neurale policy worden gedestilleerd.

B. Mixed Mamba-gebaseerde Architectuur

Om de kwadratische geheugenschaalbaarheid van Transformers aan te pakken, gebruikt ECO een op maat gemaakte Mamba (State Space Model) architectuur:

1. Recurrente Mamba Encoder: Gebruikt gestapelde Mamba-lagen (S6 setting) om knoopsequenties te verwerken. In tegen tegenstelling tot Transformers gebruikt Mamba lineaire sequentiemodellering. Om de niet-permutatie-equivariante aard van Mamba aan te pakken, worden inputs gecanoniseerd (bijv. gesorteerd via Morton/Z-order code) voordat ze worden gecodeerd.
2. S4 Decoder: Gebruikt S4-stijl lagen voor parallelle teacher-forced computation tijdens de training en efficiënte recurrente state updates tijdens de inferentie.
3. Autoregressieve Scoring: Het framework behoudt de standaard autoregressieve kandidaat-scoring stap (pointer-stijl compatibiliteitsscoring). De auteurs merken expliciet op dat hoewel de encoder en de recurrente state updates lineair worden, de actie-scoring in het slechtste geval kwadratisch blijft ($O(N^2)$) omdat het de huidige staat moet vergelijken met alle haalbare kandidaten. Echter, de architectuur vermindert de druk op het encoder-geheugen en de kosten van de recurrente state aanzienlijk.

3. Belangrijkste Bijdragen

Het artikel schetst drie primaire bijdragen:

1. Eerste Mamba-gebaseerde NCO Solver: De auteurs introduceren de eerste NCO-solver gebaseerd op Mamba, waarbij een complexiteitsdecompositie wordt getoond die aantoont dat Mamba de geheugenschaal van de encoder en de kosten van de recurrente decoding-state vermindert, hoewel naïeve autoregressieve kandidaat-scoring kwadratisch blijft.
2. Efficiëntie-georiënteerd Framework: Een nieuwe integratie van een op maat gemaakte Mamba-architectuur, een tweetraps batched preference optimization pipeline (SFT + Iterative DPO), en een door local search geleide bootstrapping-strategie om de training te stabiliseren en de preference margins te versterken.
3. Uitgebreide Empirische Analyse: Uitgebreide casestudy's op TSP en CVRP tonen aan dat ECO de beste of concurrerende neurale prestaties bereikt met aanzienlijke efficiëntiewinsten, met name op grote instanties. De analyse omvat complexiteitsdecompositie, permutatie-gevoeligheidstests en ablatie-studies op elk ontwerpcomponent.

4. Experimentele Resultaten

Experimenten werden uitgevoerd op TSP ($N \in \{200, 500, 1000, 5000\}$) en CVRP ($N \in \{100, 200, 500, 1000\}$) met een enkele NVIDIA A800 GPU.

• Oplossingskwaliteit: ECO behaalt de beste of concurrerende resultaten onder de neurale baselines (AM, POMO, LEHD, CNF, GFlowNet-HBG) over de meeste schalen.
  • Op TSP5000 bereikt ECO een gap van 5,49%, terwijl Transformer-gebaseerde baselines (AM, POMO) ernstige degradatie vertonen met gaps boven de 70-89%.
  • Op CVRP1000 bereikt ECO een gap van 2,87%, waarmee het andere neurale methoden evenaart of overtreft.
• Schaalbaarheid en Geheugen:
  • Geheugen: De Transformer-baseline triggert Out-Of-Memory (OOM) fouten bij $N \approx 7000$ op een 80GB GPU vanwege kwadratische attention-geheugen. ECO behoudt een bijna lineaire geheugengroei en blijft binnen de limieten, zelfs bij $N=10.000$ (ongeveer 40GB).
  • Doorvoer: ECO behoudt een aanzienlijk hogere inferentie-doorvoer op lange sequenties vergeleken met Transformers, omdat het grotere batches kan gebruiken zonder de geheugenlimieten te raken.
• Trainings-efficiëntie:
  • ECO convergeert veel sneller dan standaard online baselines.
  • Bij het vergelijken van DPO met PPO met dezelfde Mamba-backbone, bereikt ECO een vergelijkbare kwaliteit (4,84% vs 4,88% gap op TSP1000) maar vermindert het de trainingstijd van 34,5 uur naar 10,2 uur.
• Componentanalyse:
  • LS Bootstrapping: Het verwijderen van de LS-begeleiding verhoogt de TSP1000 gap van 4,84% naar 9,55%, wat bevestigt dat LS een sterker trainingssignaal levert dat in de policy wordt gedestilleerd.
  • SFT Warm-up: Training zonder SFT leidt tot instabiliteit en divergentie, wat de noodzaak van een competente initiële policy bevestigt.
  • Architectuur: Het vervangen van Mamba door een Transformer onder hetzelfde DPO-doel verhoogt de gap (5,47% vs 4,84%) en de trainingstijd, wat bewijst dat het architecturale voordeel onafhankelijk is van het optimalisatiedoel.

5. Betekenis en Claims

Het artikel claimt dat ECO een belangrijke stap vormt richting schaalbare, praktische neurale routing-solvers door de "efficiëntie"-kloof aan te pakken die grotendeels is genegeerd ten gunste van oplossingskwaliteit.

• Bescheiden Claims over Lineariteit: De auteurs zijn expliciet over het feit dat ECO niet de volledige constructieve inferentie lineair maakt in $N$. Het voordeel is specifiek: het vermindert de geheugenschaal van de encoder en de kosten van de recurrente state, en verbetert de hardware-utilisatie via scan kernels en batched updates. De uiteindelijke actie-scoring stap blijft kwadratisch.
• Training versus Inferentie: Een belangrijke bevinding is dat local search strikt een mechanisme tijdens de training is. De prestatiewinsten van ECO over geablateerde versies worden toegeschreven aan verbeterde netwerkparameters geleerd van LS-geleide signalen, niet aan post-processing tijdens de inferentie.
• Hardware Bewustzijn: Het werk demonstreert dat het combineren van hardware-bewuste architecturen (Mamba) met efficiënte trainingsparadigma's (Batched DPO) het mogelijk maakt voor NCO-modellen om te schalen naar duizenden knopen op consumer-grade of single-GPU hardware, waar traditionele attention-gebaseerde modellen falen door geheugenbeperkingen.

Concluderend biedt ECO een sterke richting voor schaalbare neurale routing door een lineair-geheugen backbone te verenigen met een stabiele, batched preference-learning pipeline, waarbij een concurrerende oplossingskwaliteit wordt bereikt met aanzienlijk betere geheugen- en doorvoerprofielen.