Evaluación de Modelos de Lenguaje Grandes en Problemas NP-Hard: El Impacto de la Persistencia de Estado

La resolución de problemas de optimización NP-hard es un desafío fundamental en la computación, con aplicaciones que van desde la logística hasta el diseño de redes. Tradicionalmente, estos problemas se abordan con algoritmos heurísticos, metaheurísticas o programación entera, que requieren un diseño cuidadoso y a menudo un conocimiento profundo del dominio. Con el advenimiento de los Large Language Models (LLMs), surge la pregunta de si estos modelos pueden abordar eficazmente la complejidad inherente a los problemas NP-hard, no solo generando código para solucionadores, sino también razonando sobre el espacio de búsqueda y las estrategias de optimización.

Este artículo explora la capacidad de los LLMs para resolver un problema de diseño de red de fibra óptica (KIRO), un caso concreto de problema NP-hard. La tesis central es que, si bien los LLMs avanzados como Claude Fable 5 pueden exhibir una 'inteligencia' sorprendente en la generación de soluciones de alta calidad, las características de control de flujo y persistencia de estado, como el modo '/goal', no garantizan una mejora consistente. De hecho, pueden amplificar decisiones subóptimas, llevando a un rendimiento promedio peor a pesar de ganar más ensayos individuales. Esto subraya la diferencia entre la capacidad de generar una solución y la capacidad de optimizar iterativamente en un espacio de búsqueda complejo.

Arquitectura del Sistema

El sistema evaluado consiste en un entorno de ejecución de modelos de lenguaje (Harbor 0.1.43, Docker) que interactúa con diferentes LLMs (Claude Fable 5, Opus 4.8, Sonnet 5; GPT-5.6 Sol, Terra, Luna). La interacción se realiza a través de interfaces de línea de comandos (CLI) que exponen funcionalidades como el modo '/goal'.

El problema KIRO es un problema de optimización combinatoria que implica conectar puntos de distribución y terminales en una red de fibra, formando bucles redundantes y ramas cortas, minimizando la longitud total del cable. Las restricciones incluyen que cada torre debe aparecer exactamente una vez y que la inversión de un segmento de cable puede cambiar su costo. El espacio de búsqueda es combinatoriamente explosivo, con un límite inferior de aproximadamente 10^1223 para una configuración restringida.

La implementación del modo '/goal' difiere entre los modelos. En Claude Code, se implementa como un 'Stop hook' a nivel de sesión, donde un modelo evaluador separado (Haiku por defecto) juzga la condición y el progreso basándose únicamente en la transcripción de la conversación. Este evaluador no tiene acceso a herramientas ni archivos. En contraste, Codex trata el 'goal' como un estado persistente del hilo, almacenado en SQLite. El modelo de trabajo recibe herramientas (create_goal, get_goal, update_goal) para gestionar el objetivo. Si el hilo queda inactivo, Codex inyecta un turno de continuación con el objetivo y una auditoría de finalización. Esta diferencia fundamental significa que Claude delega la finalización a un modelo externo con visión limitada, mientras que Codex permite que el modelo de trabajo declare la finalización y tiene acceso a archivos y herramientas, lo que le permite 'calificar su propio trabajo'.

Fundamentos Teóricos

El problema KIRO es una instancia de un problema NP-hard, específicamente relacionado con el diseño de redes y problemas de ruteo con restricciones, que caen dentro de la clase de problemas de optimización combinatoria. Estos problemas han sido objeto de estudio intensivo en la investigación de operaciones y la ciencia de la computación desde hace décadas. El concepto de NP-hard fue formalizado por Stephen Cook en su seminal paper de 1971, "The Complexity of Theorem-Proving Procedures", que introdujo la clase NP-completa y demostró que el problema de satisfacibilidad booleana (SAT) es NP-completo. Esto sentó las bases para entender la intratabilidad computacional de una vasta gama de problemas.

La búsqueda de soluciones aproximadas o heurísticas para problemas NP-hard es un campo activo de investigación, con algoritmos como Simulated Annealing (Kirkpatrick et al., 1983), Genetic Algorithms (Holland, 1975) o Ant Colony Optimization (Dorigo et al., 1991) siendo ejemplos clásicos. La evaluación de cómo los LLMs abordan estos problemas se conecta con la investigación en inteligencia artificial y razonamiento automatizado, explorando si la capacidad de los LLMs para generar y manipular texto puede traducirse en una capacidad efectiva para explorar espacios de búsqueda complejos y aplicar estrategias de optimización. La observación de que una característica de persistencia puede empeorar el rendimiento promedio a pesar de ganar más ensayos individuales resuena con los desafíos de la exploración de espacios de búsqueda no convexos, donde las heurísticas locales pueden quedar atrapadas en mínimos locales, un concepto bien conocido en la optimización numérica y combinatoria.