Resumen Técnico: Replanteando la Eficiencia en la Optimización Combinatoria Neuronal: Optimización de Preferencias por Lotes con Mamba

1. Planteamiento del Problema

La Optimización Combinatoria Neuronal (NCO) ha evolucionado desde las primeras Redes de Punteros hasta arquitecturas basadas en Transformers (por ejemplo, AM, POMO) y Redes de Flujo Generativo. Si bien estos métodos han mejorado la calidad de las soluciones, enfrentan cuellos de botella significativos en cuanto a eficiencia, particularmente en relación con la escalabilidad y la velocidad de convergencia del entrenamiento.

El artículo identifica dos fuentes primarias de ineficiencia en los trabajos de NCO existentes:

1. Paradigma de Aprendizaje: El Aprendizaje por Refuerzo (RL) en línea tradicional acopla estrechamente la generación de trayectorias (rollouts) con las actualizaciones de parámetros. Este bucle de "muestreo y luego actualización" subutiliza el paralelismo de la GPU y obliga a que cada paso de optimización dependa de una nueva generación autorregresiva, lo que conduce a una convergencia lenta y altos costos de hardware.
2. Arquitectura Neuronal: Los modelos de NCO de última generación dependen fuertemente de la arquitectura Transformer. A pesar de las optimizaciones como FlashAttention, la interacción entre tokens sigue siendo cuadrática ($O(N^2)$) respecto a la longitud de la secuencia. Esto causa explosiones de memoria y problemas de latencia en instancias de enrutamiento largas (por ejemplo, TSP con miles de nodos), limitando el despliegue práctico de NCO en problemas de gran escala.

La pregunta central abordada es: ¿Cómo podemos mejorar la eficiencia de la NCO sin sacrificar la calidad de la solución?

2. Metodología: El Marco ECO

Los autores proponen ECO, un marco orientado a la eficiencia que desacopla la generación de trayectorias de las actualizaciones de gradiente y reemplaza la arquitectura base de Transformer por una arquitectura basada en Mamba.

A. Paradigma de Optimización de Preferencias por Lotes

ECO introduce un flujo de trabajo de entrenamiento en dos etapas que cambia del RL estrictamente en línea a un paradigma "por lotes o fuera de línea en la actualización":

1. Fase I: Calentamiento Supervisado (SFT): La política se inicializa mediante el aprendizaje por imitación de comportamiento (behavior cloning) sobre soluciones de alta calidad precomputadas (generadas por LKH-3 o heurísticas). Esto proporciona una comprensión básica de las restricciones de enrutamiento y la optimalidad local.
2. Fase II: Optimización Directa de Preferencias (DPO) Iterativa: En lugar de entrenar una función de valor (Crítico) separada como en PPO, ECO utiliza DPO para optimizar la política directamente a partir de preferencias de pares.
   • Flujo de trabajo: La política actual genera un lote de soluciones candidatas. Se construyen pares de preferencia (Ganador/Perdedor) basados en la longitud del recorrido.
   • Modelo de Referencia: Un modelo de referencia ($\pi_{ref}$) se actualiza periódicamente (cada $T$ pasos) para anclar la divergencia KL, estabilizando la mejora iterativa.
   • Bootstrapping aumentado por Búsqueda Local (LS): Para prevenir el desvanecimiento de gradientes causado por márgenes de recompensa estrechos a medida que la política mejora, se aplica un operador de búsqueda local ligero (ej. 2-opt, 3-opt) a las soluciones generadas por el modelo durante el entrenamiento. La solución refinada se convierte en el "Ganador", y la salida bruta se convierte en el "Perdedor". Crucialmente, la búsqueda local nunca se utiliza en el tiempo de inferencia; sirve únicamente para construir señales de entrenamiento más fuertes que se destilan en la política neuronal.

B. Arquitectura Mixta Basada en Mamba

Para abordar la escalabilidad cuadrática de memoria de los Transformers, ECO emplea una arquitectura Mamba (Modelo de Espacio de Estado) adaptada:

1. Codificador Mamba Recurrente: Utiliza capas Mamba apiladas (configuración S6) para procesar secuencias de nodos. A diferencia de los Transformers, Mamba utiliza un modelado de secuencia de memoria lineal. Para manejar la naturaleza no equivariante a la permutación de Mamba, las entradas se canonicalizan (por ejemplo, ordenadas mediante código Morton/Z-order) antes de la codificación.
2. Decodificador S4: Utiliza capas de estilo S4 para el cómputo paralelo con profesor forzado (teacher-forced) durante el entrenamiento y actualizaciones de estado recurrentes eficientes durante la inferencia.
3. Puntuación Autorregresiva: El marco retiene el paso estándar de puntuación de candidatos autorregresivos (compatibilidad tipo puntero). Los autores señalan explícitamente que, aunque el codificador y las actualizaciones de estado recurrente se vuelven lineales, la puntuación de acciones sigue siendo cuadrática en el peor de los casos ($O(N^2)$) porque requiere comparar el estado actual contra todos los candidatos factibles. Sin embargo, la arquitectura reduce significativamente la presión de memoria del codificador y los costos del estado recurrente.

3. Contribuciones Clave

El artículo describe tres contribuciones principales:

1. Primer Solucionador de NCO basado en Mamba: Los autores presentan el primer solucionador de NCO basado en Mamba, proporcionando una descomposición de complejidad que muestra que Mamba reduce la escalabilidad de memoria del codificador y los costos del estado de decodificación recurrente, aunque la puntuación de candidatos autorregresiva simple sigue siendo cuadrática.
2. Marco Orientado a la Eficiencia: Una integración novedosa de una arquitectura Mamba adaptada, un flujo de optimización de preferencias por lotes en dos etapas (SFT + DPO iterativo) y una estrategia de bootstrapping guiada por búsqueda local para estabilizar el entrenamiento y amplificar los márgenes de preferencia.
3. Análisis Empírico Exhaustivo: Casos de estudio extensos en TSP y CVRP demostrando que ECO logra un rendimiento neuronal óptimo o competitivo con ganancias de eficiencia sustanciales, particularmente en instancias de gran escala. El análisis incluye descomposición de complejidad, pruebas de sensibilidad a la permutación y estudios de ablación sobre cada componente del diseño.

4. Resultados Experimentales

Los experimentos se realizaron en TSP ($N \in \{200, 500, 1000, 5000\}$) y CVRP ($N \in \{100, 200, 500, 1000\}$) utilizando una única GPU NVIDIA A800.

• Calidad de la Solución: ECO logra resultados óptimos o competitivos entre los baselines neuronales (AM, POMO, LEHD, CNF, GFlowNet-HBG) en la mayoría de las escalas.
  • En TSP5000, ECO logra una brecha del 5.49%, mientras que los baselines basados en Transformer (AM, POMO) sufren una degradación severa con brechas que superan el 70-89%.
  • En CVRP1000, ECO logra una brecha del 2.87%, superando o igualando a otros métodos neuronales.
• Escalabilidad y Memoria:
  • Memoria: El baseline de Transformer dispara errores de Fuera de Memoria (OOM) en $N \approx 7000$ en una GPU de 80GB debido a la memoria de atención cuadrática. ECO mantiene un crecimiento de memoria casi lineal, manteniéndose dentro de los límites incluso en $N=10,000$ (aprox. 40GB).
  • Throughput (Rendimiento): ECO mantiene un throughput de inferencia significativamente mayor en secuencias largas comparado con los Transformers, ya que puede utilizar lotes más grandes sin alcanzar los límites de memoria.
• Eficiencia de Entrenamiento:
  • ECO converge mucho más rápido que los baselines estándar en línea.
  • Comparando DPO con PPO usando el mismo backbone de Mamba, ECO logra una calidad comparable (brecha de 4.84% vs 4.88% en TSP1000) pero reduce el tiempo de entrenamiento de 34.5 horas a 10.2 horas.
• Análisis de Componentes:
  • Bootstrapping de LS: Eliminar la guía de LS aumenta la brecha de TSP1000 de 4.84% a 9.55%, confirmando que la LS proporciona una señal de entrenamiento más fuerte que se destila en la política.
  • Calentamiento SFT: Entrenar sin SFT conduce a la inestabilidad y la divergencia, confirmando la necesidad de una política inicial competente.
  • Arquitectura: Reemplazar Mamba con Transformer bajo el mismo objetivo de DPO aumenta la brecha (5.47% vs 4.84%) y el tiempo de entrenamiento, probando que el beneficio arquitectónico es independiente del objetivo de optimización.

5. Significado y Reivindicaciones

El artículo afirma que ECO representa un paso significativo hacia los solucionadores de enrutamiento neural escalables y prácticos al abordar la brecha de "eficiencia" que ha sido ampliamente ignorada en favor de la calidad de la solución.

• Afirmaciones Modestas sobre Linealidad: Los autores son explícitos al señalar que ECO no hace que toda la inferencia constructiva sea lineal en $N$. El beneficio es específico: reduce la escalabilidad de memoria del codificador y los costos del estado recurrente, y mejora la utilización del hardware mediante kernels de escaneo y actualizaciones por lotes. El paso final de puntuación de acciones sigue siendo cuadrático.
• Entrenamiento vs. Inferencia: Un hallazgo clave es que la búsqueda local es estrictamente un mecanismo de tiempo de entrenamiento. Las ganancias de rendimiento de ECO sobre las versiones abladas se atribuyen a la mejora de los parámetros de la red aprendidos de las señales guiadas por LS, no al post-procesamiento en la inferencia.
• Conciencia del Hardware: El trabajo demuestra que combinar arquitecturas conscientes del hardware (Mamba) con paradigmas de entrenamiento eficientes (DPO por lotes) permite que los modelos de NCO escalen a miles de nodos en hardware de consumo o en una sola GPU, donde los modelos tradicionales basados en atención fallan debido a las restricciones de memoria.

En conclusión, ECO proporciona una dirección sólida para el enrutamiento neural escalable al unificar un backbone de memoria lineal con un flujo de aprendizaje de preferencias por lotes estable, logrando una calidad de solución competitiva con perfiles de memoria y throughput notablemente mejores.