🤖 machine learning

Rethinking Efficiency in Neural Combinatorial Optimization: Batched Preference Optimization with Mamba

O artigo apresenta o ECO, um framework de Otimização Combinatória Neural eficiente que combina uma espinha dorsal Mamba com eficiência de memória a um pipeline de Otimização de Preferência Direta desacoplado e em lote, guiado por busca local durante o treinamento, para alcançar desempenho superior e utilização de hardware nos tarefas TSP e CVRP.

Autores originais: Zhenxing Xu, Zeyuan Ma, Weidong Bao, Yan Zheng, Chongshuang Hu, Ji Wang, Zhiguang Cao

Publicado 2026-07-21

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

Autores originais: Zhenxing Xu, Zeyuan Ma, Weidong Bao, Yan Zheng, Chongshuang Hu, Ji Wang, Zhiguang Cao

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você é um mestre chef tentando organizar um banquete massivo para milhares de convidados. Você tem uma lista de ingredientes (os "nós") e um conjunto de regras: deve visitar cada ingrediente exatamente uma vez, carregar apenas o que seu carrinho pode comportar e levar tudo de volta à cozinha o mais rápido possível. Este é o mundo da Otimização Combinatória. Durante décadas, os humanos usaram receitas engenhosas e feitas à mão (algoritmos) para resolver esses quebra-cabeças, mas elas são lentas e muitas vezes precisam que um especialista humano as ajuste para cada novo banquete.

Recentemente, cientistas começaram a ensinar computadores a aprender essas receitas por conta própria usando Redes Neurais. Pense nessas redes como aprendizes ansiosos que observam milhares de exemplos e tentam adivinhar o melhor próximo passo. No entanto, há um problema: treinar esses aprendizes é incrivelmente caro. É como pedir a eles que cozinhem uma refeição completa, provem, joguem fora e comecem do zero milhões de vezes apenas para aprender um novo truque. Esse processo é tão lento e faminto por memória que frequentemente trava o computador antes que o aprendiz se torne bom. A grande questão para os pesquisadores tem sido: Podemos ensinar esses chefs de IA a serem tão bons quanto, mas muito mais rápidos e menos desperdiçadores?

Este artigo introduz um novo framework chamado ECO (Efficient Combinatorial Optimization) que diz "sim". Os autores propõem um truque de mágica em duas partes para acelerar o processo sem perder a qualidade. Primeiro, eles mudam o estilo de aprendizado. Em vez de o aprendiz cozinhar, provar e aprender um prato de cada vez em um ciclo caótico, o ECO permite que o aprendiz cozinhe um lote inteiro de refeições, compare-as e depois aprenda com as melhores de uma só vez. Eles chamam isso de "Otimização de Preferência em Lote" (Batched Preference Optimization). É como um professor mostrando a um aluno dez redações diferentes, apontando a melhor e a pior e dizendo: "Veja a diferença? Aprenda com isso", em vez de corrigir uma redação, esperar o aluno reescrevê-la e depois corrigir a próxima.

Segundo, eles atualizam o cérebro do aprendiz. A maioria dos modelos de IA usa uma arquitetura "Transformer", que é como um bibliotecário que tem que ler cada livro em uma estante para encontrar uma conexão entre duas páginas específicas. Se a estante ficar muito longa (milhares de ingredientes), o bibliotecário fica sobrecarregado e fica sem memória. O ECO substitui isso por uma estrutura Mamba. Imagine o Mamba como um scanner super eficiente que lê a estante em um fluxo suave e contínuo, lembrando apenas do que precisa para manter o controle. Isso permite que o sistema lide com banquetes massivos (milhares de nós) sem que o computador trave.

Os autores testaram isso em dois problemas clássicos: o Problema do Caixeiro Viajante (encontrar a rota mais curta para visitar muitas cidades) e o Problema de Roteamento de Veículos (entregar pacotes para muitos clientes com espaço limitado no caminhão). Eles descobriram que o ECO é incrivelmente rápido. Em um problema com 5.000 cidades, o ECO resolveu o conjunto de teste em apenas 2,5 minutos, enquanto outros métodos neurais levaram muito mais tempo, e solvers exatos tradicionais levaram horas. Crucialmente, os autores mostram que o ECO não está apenas "trapaceando" ao usar uma "busca local" (um ajuste rápido) durante o teste final; a IA aprendeu os truques por conta própria durante o treinamento.

O artigo sugere que, ao combinar este novo estilo de aprendizado "em lote" com o cérebro eficiente Mamba, podemos treinar a IA para resolver enormes e complexos problemas de roteamento muito mais rápido do que antes, economizando tempo e poder computacional. Os resultados mostram que o ECO é competitivo com, e muitas vezes melhor do que, os melhores métodos de IA existentes, especialmente quando os problemas se tornam muito grandes. No entanto, os autores fazem questão de notar que, embora o "cérebro" (o codificador) tenha se tornado mais eficiente, a etapa final de escolher o próximo movimento ainda exige um trabalho pesado, portanto, todo o processo não é perfeitamente linear, mas é uma melhoria massiva em relação aos métodos antigos.

Resumo Técnico: Repensando a Eficiência em Otimização Combinatória Neural: Otimização de Preferência em Lote com Mamba

1. Definição do Problema

A Otimização Combinatória Neural (NCO) evoluiu das primeiras Redes de Ponteiros (Pointer Networks) para arquiteturas baseadas em Transformer (ex: AM, POMO) e Redes de Fluxo Generativo. Embora esses métodos tenham melhorado a qualidade das soluções, eles enfrentam gargalos de eficiência significativos, particularmente no que diz respeito à escalabilidade e à velocidade de convergência do treinamento.

O artigo identifica duas fontes primárias de ineficiência nos trabalhos de NCO existentes:

Paradigma de Aprendizado: O Aprendizado por Reforço (RL) online tradicional acopla estritamente a geração de trajetórias (rollouts) com as atualizações de parâmetros. Esse ciclo de "amostragem-então-atualização" subutiliza o paralelismo da GPU e força cada etapa de otimização a depender de uma nova geração autorregressiva, levando a uma convergência lenta e altos custos de hardware.
Arquitetura Neural: Os modelos de NCO de última geração dependem fortemente da arquitetura Transformer. Apesar de otimizações como o FlashAttention, a interação entre tokens permanece quadrática ( $O(N^2)$ ) em relação ao comprimento da sequência. Isso causa explosão de memória e problemas de latência em instâncias de roteamento longas (ex: TSP com milhares de nós), limitando a implantação prática de NCO em problemas de larga escala.

A questão central abordada é: Como podemos melhorar a eficiência da NCO sem sacrificar a qualidade da solução?

2. Metodologia: O Framework ECO

Os autores propõem o ECO, um framework orientado à eficiência que desacopla a geração de trajetórias das atualizações de gradiente e substitui o backbone Transformer por uma arquitetura baseada em Mamba.

A. Paradigma de Otimização de Preferência em Lote (Batched Preference Optimization)

O ECO introduz um fluxo de trabalho de treinamento em duas etapas que muda do RL online estrito para um paradigma de "lote ou offline-na-atualização":

Fase I: Aquecimento Supervisionado (SFT): A política é inicializada via clonagem de comportamento em soluções pré-computadas de alta qualidade (geradas por LKH-3 ou heurísticas). Isso fornece uma compreensão básica das restrições de roteamento e da otimalidade local.
Fase II: Otimização Direta de Preferência (DPO) Iterativa: Em vez de treinar uma função de valor (Crítico) separada como no PPO, o ECO usa DPO para otimizar a política diretamente a partir de preferências pareadas.
- Fluxo de Trabalho: A política atual gera um lote de soluções candidatas. Pares de preferência (Vencedor/Perdedor) são construídos com base no comprimento do tour.
- Modelo de Referência: Um modelo de referência ( $\pi_{ref}$ ) é atualizado periodicamente (a cada $T$ passos) para ancorar a divergência KL, estabilizando a melhoria iterativa.
- Bootstrapping Aumentado por LS: Para evitar o desaparecimento de gradientes causado por margens de recompensa estreitas conforme a política melhora, um operador de busca local (LS) leve (ex: 2-opt, 3-opt) é aplicado às soluções geradas pelo modelo durante o treinamento. A solução refinada torna-se o "Vencedor", e a saída bruta torna-se o "Perdedor". Crucialmente, a busca local nunca é usada no tempo de inferência; ela serve apenas para construir sinais de treinamento mais fortes que são destilados na política neural.

B. Arquitetura Mista Baseada em Mamba

Para abordar a escalabilidade quadrática de memória dos Transformers, o ECO emprega uma arquitetura Mamba (Modelo de Espaço de Estados) customizada:

Codificador Mamba Recorrente: Utiliza camadas Mamba empilhadas (configuração S6) para processar sequências de nós. Diferente dos Transformers, o Mamba utiliza modelagem de sequência de memória linear. Para lidar com a natureza não-permutação-equivariante do Mamba, as entradas são canonicalizadas (ex: ordenadas por código Morton/Z-order) antes da codificação.
Decodificador S4: Utiliza camadas do tipo S4 para computação paralela de teacher-forcing durante o treinamento e atualizações de estado recorrentes eficientes durante a inferência.
Pontuação Autorregressiva: O framework mantém a etapa padrão de pontuação de candidatos autorregressivos (compatibilidade de estilo pointer). Os autores observam explicitamente que, embora o codificador e as atualizações de estado recorrente tornem-se lineares, a pontuação de ação permanece quadrática no pior caso ( $O(N^2)$ ) porque requer a comparação do estado atual contra todos os candidatos viáveis. No entanto, a arquitetura reduz significativamente a pressão de memória do codificador e os custos do estado recorrente.

3. Principais Contribuições

O artigo delineia três contribuições primárias:

Primeiro Solver de NCO baseado em Mamba: Os autores introduzem o primeiro solver de NCO baseado em Mamba, fornecendo uma decomposição de complexidade mostrando que o Mamba reduz a escalabilidade de memória do codificador e os custos de estado de decodificação recorrente, embora a pontuação de ação autorregressiva simples permaneça quadrática.
Framework Orientado à Eficiência: Uma integração inovadora de uma arquitetura Mamba customizada, um pipeline de otimização de preferência em lote de duas etapas (SFT + DPO Iterativo) e uma estratégia de bootstrapping guiada por busca local para estabilizar o treinamento e amplificar as margens de preferência.
Análise Empírica Abrangente: Estudos de caso extensos em TSP e CVRP demonstrando que o ECO alcança desempenho neural de melhor ou competitivo, com ganhos substanciais de eficiência, particularmente em instâncias de grande escala. A análise inclui decomposição de complexidade, testes de sensibilidade de permutação e estudos de ablação de cada componente de design.

4. Resultados Experimentais

Experimentos foram conduzidos em TSP ( $N \in \{200, 500, 1000, 5000\}$ ) e CVRP ( $N \in \{100, 200, 500, 1000\}$ ) usando uma única GPU NVIDIA A800.

Qualidade da Solução: O ECO alcança resultados de melhor ou competitivos entre as linhas de base neurais (AM, POMO, LEHD, CNF, GFlowNet-HBG) na maioria das escalas.
- No TSP5000, o ECO alcança um gap de 5,49%, enquanto os baselines baseados em Transformer (AM, POMO) sofrem degradação severa com gaps superiores a 70-89%.
- No CVRP1000, o ECO alcança um gap de 2,87%, superando ou igualando outros métodos neurais.
Escalabilidade e Memória:
- Memória: O baseline Transformer dispara erros de Out-Of-Memory (OOM) em $N \approx 7000$ em uma GPU de 80GB devido à memória de atenção quadrática. O ECO mantém um crescimento de memória quase linear, permanecendo dentro dos limites mesmo em $N=10.000$ (aprox. 40GB).
- Throughput: O ECO sustenta um throughput de inferência significativamente maior em sequências longas comparado aos Transformers, pois pode utilizar lotes maiores sem atingir limites de memória.
Eficiência de Treinamento:
- O ECO converge muito mais rápido do que os baselines online padrão.
- Comparando DPO com PPO usando o mesmo backbone Mamba, o ECO alcança qualidade comparável (gap de 4,84% vs 4,88% no TSP1000), mas reduz o tempo de treinamento de 34,5 horas para 10,2 horas.
Análise de Componentes:
- Bootstrapping por LS: Remover a orientação por LS aumenta o gap do TSP1000 de 4,84% para 9,55%, confirmando que o LS fornece um sinal de treinamento mais forte que é destilado na política.
- Aquecimento por SFT: Treinar sem SFT leva à instabilidade e divergência, confirmando a necessidade de uma política inicial competente.
- Arquitetura: Substituir Mamba por Transformer sob o mesmo objetivo de DPO aumenta o gap (5,47% vs 4,84%) e o tempo de treinamento, provando que o benefício arquitetônico é independente do objetivo de otimização.

5. Significância e Alegações

O artigo afirma que o ECO representa um passo significativo em direção a solvers de roteamento neurais escaláveis e práticos, abordando a lacuna de "eficiência" que tem sido amplamente negligenciada em favor da qualidade da solução.

Alegações Modestas sobre Linearidade: Os autores são explícitos ao dizer que o ECO não torna toda a inferência construtiva linear em $N$ . O benefício é específico: ele reduz a escalabilidade de memória do codificador e os custos de estado recorrente, além de melhorar a utilização do hardware via kernels de scan e atualizações em lote. A etapa final de pontuação de ação permanece quadrática.
Treinamento vs. Inferência: Uma descoberta chave é que a busca local é estritamente um mecanismo de tempo de treinamento. Os ganhos de desempenho do ECO sobre as versões abladas são atribuídos a parâmetros de rede melhorados aprendidos a partir de sinais guiados por LS, não a pós-processamento na inferência.
Consciência de Hardware: O trabalho demonstra que combinar arquiteturas conscientes de hardware (Mamba) com paradigmas de treinamento eficientes (DPO em lote) permite que modelos de NCO escalem para milhares de nós em hardware de nível de consumo ou em uma única GPU, onde os modelos tradicionais baseados em atenção falham devido a restrições de memória.

Em conclusão, o ECO fornece uma direção sólida para o roteamento neural escalável ao unificar um backbone de memória linear com um pipeline de aprendizado de preferência em lote estável, alcançando uma qualidade de solução competitiva com perfis de memória e throughput marcadamente melhores.