Un LLM enseña a un planificador a funcionar con memoria polinómica y resuelve 1709 de 1890 tareas

Los planificadores clásicos se quedan sin memoria antes que sin tiempo. La búsqueda heurística guarda una lista de estados visitados, y esa lista crece de forma exponencial incluso cuando la heurística es casi perfecta. Los autores de un nuevo trabajo en arXiv proponen prescindir de ella. Con políticas escritas por un modelo de lenguaje, su procedimiento resolvió 1709 de 1890 tareas de prueba de IPC 2023 Learning Track y del conjunto Autoscale Agile. Es más que LAMA, BFWS y Levitron, y la mayoría de las tareas se resolvió en un segundo y dentro de 100 MiB.

Política con registros en lugar de lista de estados

En vez de un buscador universal, los autores enseñan a controlar la búsqueda. Para cada dominio se escribe una única especificación en forma de «política indexada». Se trata de una política generalizada con registros, donde se almacenan objetos, y con modos que fijan el orden de aplicación de las reglas. La adición clave es la regla choose. Carga un objeto en un registro y fija un punto de retroceso; basta con un solo candidato adecuado. Todas las demás reglas deben funcionar sea cual sea el resultado, y no necesitan búsqueda.

El resultado principal del trabajo es teórico. La terminación estructural excluye las ejecuciones infinitas de la política. Los autores demuestran que esa misma propiedad acota cualquier ejecución por un polinomio en el número de objetos.

De ello se deduce que la búsqueda en profundidad encuentra un plan en memoria polinómica, sea cual sea el tamaño del espacio de estados, y que la lista de estados visitados no hace falta. El precio se paga en tiempo, que es exponencial solo en la profundidad de elección, es decir, en el número de choice reales a lo largo de la ejecución. Por eso cualquier clase de tareas que resuelva una política de este tipo está en NP y, con profundidad de elección constante, en P.

Dónde entra el modelo de lenguaje

Las políticas no se escriben a mano. Las genera un modelo de lenguaje en un ciclo con contraejemplos. En cada vuelta, el ciclo certifica la terminación, comprueba la política con tareas de entrenamiento y vigila que la profundidad de elección se mantenga baja. Esta última condición es importante porque es ella la que determina cuánto tiempo consumirá la exploración. El resumen no indica qué modelo concreto se utilizó.

Las cifras del resumen

• Se resolvieron 1709 de 1890 tareas de prueba (alrededor del 90%); 181 tareas quedaron sin resolver.
• Benchmarks: IPC 2023 Learning Track y Autoscale Agile.
• Los competidores LAMA, BFWS y Levitron resolvieron menos.
• La mayoría de las tareas se resolvió en menos de un segundo y dentro de 100 MiB.
• La memoria es polinómica, sin lista de estados visitados.
• El tiempo es exponencial solo en la profundidad de elección.
• Las clases de tareas que resuelven estas políticas están en NP y, con profundidad de elección constante, en P.

Dónde puede resultar útil

El enfoque parece más sólido donde la memoria es más cara que el tiempo de procesador: planificadores embebidos, robots y sistemas que resuelven tareas del mismo tipo con entradas distintas. Hay además un hallazgo práctico en el reparto del trabajo. El modelo de lenguaje escribe un programa-política verificable, y el certificado de terminación ofrece una garantía que no tiene un plan generado directamente por el modelo. Las limitaciones también están claras. Hace falta una política para cada dominio, el aprendizaje requiere un conjunto de tareas de entrenamiento y las cifras las obtuvieron los propios autores en un preprint, sin verificación independiente. Aun así, este híbrido ya ofrece una mejora notable en memoria en benchmarks estándar de planificación.