Memory-Efficient Activation Checkpointing with Sliding Window and Hirschberg's Algorithm for 0/1 Knapsack Solving in PyTorch

Imagine que você está tentando assar o bolo mais delicioso e complexo do mundo, mas tem apenas uma cozinha minúscula e apertada. Você tem uma receita que exige que você acompanhe cada um dos ingredientes misturados, cada mudança de temperatura e cada movimento de batedeira para que possa reverter perfeitamente o processo mais tarde e ver como o bolo ficou. O problema é que sua bancada de cozinha (a memória do seu computador) é pequena demais para anotar tudo isso. Se você tentar escrever tudo, a bancada transborda e você tem que parar de assar. Este é o luta diária dos cientistas que treinam modelos massivos de inteligência artificial. Eles precisam se lembrar de muitos passos para ensinar a IA, mas seus computadores ficam sem espaço. Para resolver isso, eles usam um truque inteligente chamado "checkpointing de ativação". Em vez de anotar cada um dos passos, eles escolhem os mais importantes para salvar e concordam em refazer os menos importantes mais tarde. É como decidir quais fotos manter em um pequeno álbum de fotos e quais você pode se dar ao luxo de tirar novamente se esquecer delas. O objetivo é fazer todo o processo de assar o bolo caber nessa cozinha minúscula sem perder a magia da receita.

Por muito tempo, o programa de computador PyTorch, que muitos cientistas de IA usam para construir esses modelos, tinha uma maneira específica de decidir quais passos salvar. Ele tratava a decisão como um quebra-cabeça clássico chamado "Problema da Mochila 0/1". Imagine que você é um trilheiro com uma mochila que só pode carregar um certo peso. Você tem uma lista de itens, cada um com um peso e um valor (o quanto ele ajuda você). Você quer escolher os itens que proporcionem o maior valor sem quebrar sua mochila. O método padrão do PyTorch para resolver este problema era como tentar escrever todas as combinações possíveis de itens em uma folha de papel gigante. Embora este método fosse perfeito e encontrasse a resposta absoluta, a folha de papel ficava tão grande que a memória do computador explodia, fazendo o programa travar. Os pesquisadores descobriram que, se tivessem apenas 100 itens para escolher, a folha de papel necessária seria tão grande que exigiria 304 gigabytes de espaço, muito mais do que os 64 gigabytes disponíveis em sua máquina. Era uma solução perfeita que simplesmente não cabia na sala.

Neste artigo, o autor introduz uma nova maneira mais inteligente de resolver este quebra-cabeça, que ele chama de dp_knapsack_sliding_hirschberg. Em vez de tentar escrever toda aquela folha de papel gigante de uma só vez, eles usam um truque de "janela deslizante". Imagine que você está lendo um livro longo, mas tem apenas uma lupa pequena que pode mostrar duas páginas por vez. Você desliza a lupa pela página, olhando para duas páginas, depois as próximas duas, e assim por diante. Dessa forma, você só precisa manter duas páginas em sua mente em qualquer momento, economizando um enorme espaço mental. No entanto, apenas olhar para duas páginas não é suficiente para lembrar de toda a história; você precisa saber quais itens específicos escolher. Para corrigir isso, eles combinam a janela deslizante com uma estratégia antiga e inteligente chamada "algoritmo de Hirschberg". Pense nisso como um jogo de "dividir para conquistar". Em vez de tentar resolver todo o problema da mochila de uma só vez, eles dividem a lista de itens ao meio. Eles resolvem a metade esquerda, depois a metade direita e, então, descobrem como combinar as duas melhores soluções. Eles fazem isso recursivamente, decompondo o problema em partes cada vez menores até que possam resolvê-lo facilmente, tudo isso usando uma quantidade mínima de memória.

Os resultados deste novo método são impressionantes. O autor testou o método em um computador com 64 gigabytes de RAM. Enquanto o método antigo travava ao tentar resolver um problema com apenas 100 itens, o novo método resolveu com sucesso um problema com 2.000 itens, usando um pico de 58,4 gigabytes de memória. Isso significa que o computador agora pode lidar com um problema 20 vezes maior do que antes sem ficar sem espaço. Além disso, o novo método não é apenas um poupador de memória; é também mais rápido. Em seus testes, ele rodou de 25% a 28% mais rápido que o método antigo. O autor mediu isso executando o mesmo quebra-cabeça 1.000 vezes em uma máquina específica e descobriu que o novo solver superou consistentemente o antigo em velocidade. Crucialmente, ao contrário de outros métodos de "correção rápida" que adivinham a resposta e podem estar ligeiramente errados, este novo método ainda encontra a solução exata e perfeita todas as vezes. É tão preciso quanto o método antigo, mas muito mais eficiente.

O artigo confirma que esta nova abordagem não é apenas uma teoria; ela foi integrada com sucesso ao software PyTorch e está disponível na versão 2.10. O autor mostra que, ao usar esta combinação de janelas deslizantes e divisão e conquista, eles podem resolver o gargalo de memória que estava impedindo os modelos de IA de crescerem. Eles não afirmam que este é o único modo de resolver o problema, nem sugerem que funcione para todo tipo de quebra-cabeça de computador, mas para a tarefa específica de decidir quais passos da IA salvar, é uma atualização comprovada, exata e altamente eficiente. O artigo descarta a ideia de que o método antigo seja suficiente para modelos grandes, mostrando claramente que ele falha quando o número de itens fica muito alto. Em vez disso, eles oferecem uma solução que mantém a precisão perfeita do método antigo enquanto remove o travamento de memória, permitando que os cientistas assem bolos de IA maiores e mais complexos em suas cozinhas minúsculas.