LLM ensina planejador a funcionar com memória polinomial e resolve 1709 de 1890 tarefas

Os planejadores clássicos esbarram no limite de memória antes do limite de tempo. A busca heurística guarda uma lista de estados visitados, e essa lista cresce exponencialmente, mesmo quando a heurística é quase perfeita. Os autores de um novo trabalho no arXiv propõem dispensar essa lista. Com políticas escritas por um modelo de linguagem, o procedimento deles resolveu 1709 de 1890 tarefas de teste do IPC 2023 Learning Track e do conjunto Autoscale Agile. É mais do que LAMA, BFWS e Levitron resolveram, e a maioria das tarefas coube em um segundo e 100 MiB.

Política com registradores no lugar da lista de estados

Em vez de uma busca universal, os autores ensinam o controle da busca. Para cada domínio, escreve-se uma especificação na forma de uma "política indexical". Trata-se de uma política generalizada com registradores, que guardam objetos, e com modos, que definem a ordem de aplicação das regras. A adição central é a regra choose. Ela carrega um objeto em um registrador e define um ponto de retorno, e basta um candidato adequado. Todas as demais regras precisam funcionar com qualquer resultado e não exigem busca.

O principal resultado do trabalho é teórico. A terminação estrutural exclui execuções infinitas da política. Os autores mostram que ela também limita qualquer execução a um polinômio no número de objetos. Daí decorre que a busca em profundidade encontra um plano em memória polinomial, qualquer que seja o tamanho do espaço de estados, e a lista de estados visitados deixa de ser necessária. O preço é pago em tempo, que é exponencial apenas na profundidade de escolha, ou seja, no número de choices reais ao longo da execução. Por isso, qualquer classe de tarefas resolvida por uma política desse tipo está em NP e, com profundidade de escolha constante, está em P.

Onde entra o modelo de linguagem

As políticas não são escritas à mão. Um modelo de linguagem as gera em um ciclo com contraexemplos. A cada rodada, o ciclo certifica a terminação, testa a política nas tarefas de treino e verifica se a profundidade de escolha continua pequena. Esta última condição importa porque é ela que determina quanto tempo a busca exaustiva vai consumir. O resumo do artigo não informa qual modelo foi usado.

Os números do resumo

• Foram resolvidas 1709 de 1890 tarefas de teste (cerca de 90%); 181 tarefas ficaram sem solução.
• Benchmarks: IPC 2023 Learning Track e Autoscale Agile.
• Os concorrentes LAMA, BFWS e Levitron resolveram menos tarefas.
• A maioria das tarefas foi resolvida em menos de um segundo e dentro de 100 MiB.
• A memória é polinomial, sem lista de estados visitados.
• O tempo é exponencial apenas na profundidade de escolha.
• As classes de tarefas resolvidas por essas políticas estão em NP e, com profundidade de escolha constante, em P.

Onde isso pode ser útil

A abordagem parece mais forte onde a memória custa mais do que o tempo de processador: em planejadores embarcados, em robôs e em sistemas que resolvem tarefas do mesmo tipo com entradas diferentes. Há também um achado prático na divisão de trabalho. O modelo de linguagem escreve um programa-política verificável, e o certificado de terminação oferece uma garantia que um plano gerado diretamente pelo modelo não tem. As limitações também são claras. É preciso uma política para cada domínio, o treinamento exige um conjunto de tarefas de treino, e os números vêm dos próprios autores, em um preprint, sem verificação independente. Ainda assim, esse híbrido já entrega um ganho perceptível de memória em benchmarks padrão de planejamento.