Resumen Técnico: Búsqueda Evolutiva Guiada por LLM para la Reformulación de Modelos de Restricciones

Planteamiento del Problema

Los problemas combinatorios son ubicuos en aplicaciones industriales, a menudo modelados mediante Programación por Restricciones (CP). Si bien los Modelos de Lenguaje de Gran Escala (LLM) han demostrado la capacidad de generar modelos de restricciones declarativos correctos a partir de lenguaje natural, la corrección por sí sola no garantiza la eficiencia. Un modelo que es semánticamente correcto puede ser computacionalmente costoso de resolver debido a elecciones de modelado subóptimas (por ejemplo, puntos de vista de variables, formulaciones de restricciones o codificaciones). La reformulación manual de estos modelos para mejorar el rendimiento del solver es un cuello de botella crítico. Los enfoques de automatización existentes suelen depender de transformaciones basadas en reglas o de añadir "streamliners" (restricciones adicionales) a una estructura de modelo fija, en lugar de realizar reformulaciones holísticas que cambien el punto de vista del modelo o las codificaciones de las variables.

Metodología

Los autores proponen un marco de búsqueda evolutiva guiada por LLM para la reformulación de modelos de restricciones orientada al rendimiento. Inspirado en el Diseño Automático de Heurísticas (AHD), el sistema genera, evalúa y selecciona iterativamente las reformulaciones de los modelos.

Flujo de Trabajo Principal

1. Inicialización: Se establece un modelo base ($B$), y se mide su rendimiento de tiempo de ejecución en un conjunto de entrenamiento ($D_{tr}$).
2. Bucle Iterativo: Para $T$ iteraciones:
   • Selección de Contexto: Una estrategia de búsqueda ($\sigma$) selecciona un subconjunto de intentos previos (razonamiento, modelo y retroalimentación) para formar el contexto del prompt ($R_t$).
   • Generación: El LLM recibe un prompt que contiene la descripción de la tarea, el modelo base, el historial de tiempo de ejecución y el contexto seleccionado. Este genera un razonamiento ($\rho_t$) y un modelo candidato ($m_t$).
   • Evaluación: El candidato se ejecuta en $D_{tr}$. El evaluador verifica la validez de la solución (asegurando que la respuesta del candidato coincida con la del modelo base para la misma instancia) y mide el tiempo de ejecución total.
   • Actualización del Historial: El intento se registra en el historial $H_t$.
3. Selección Final: Después de que la búsqueda termina, todos los modelos candidatos válidos se evalúan en un conjunto de validación separado ($D_{val}$). Se selecciona como salida final el modelo con el menor tiempo de ejecución total en $D_{val}$. Este paso es crucial para evitar el sobreajuste a las instancias de entrenamiento.

Estrategias de Búsqueda

El artículo compara diez estrategias para seleccionar el contexto $R_t$ proporcionado al LLM:

• Baselines: Sampling (sin contexto), Full-history (historial completo), Last-k (recencia) y Top-k (calidad/más rápido).
• Híbrido: Combina recencia y calidad.
• Evolución de Heurísticas (EoH): Mantiene una población de modelos y utiliza operadores específicos (por ejemplo, "enfoque distinto", "combinación compatible") para guiar la generación, con y sin retroalimentación de rendimiento.
• Retención de Perfil Diverso (PDR): Una estrategia novedosa introducida en este trabajo. PDR busca explícitamente la diversidad de comportamiento. Representa cada modelo como un vector de tiempos de ejecución normalizados a través de las instancias de entrenamiento. Utiliza la Relevancia Marginal Máxima (MMR) para seleccionar un conjunto de intentos que sean tanto rápidos (alta calidad) como conductualmente distintos (baja similitud en los perfiles de tiempo de ejecución) entre sí.

Configuración Experimental

• Benchmarks: Ocho problemas de satisfacción de CSPLib (por ejemplo, Asignación de Cola, Secuenciación de Coches, Matrices de Cobertura).
• Modelo: DeepSeek V4 Flash (contexto de 1M de tokens).
• Solver: OR-Tools CP-SAT a través de CPMpy.
• Métricas: Media Geométrica (GM) de las aceleraciones (speedups) en instancias de prueba no vistas ($D_{test}$), utilizando PAR2 (tiempo de ejecución promedio penalizado) para los tiempos de espera (timeouts).

Contribuciones Clave

1. Marco Evolutivo: Una adaptación de AHD específicamente para la reformulación de modelos completos de modelos de CP declarativos, permitiendo que el LLM cambie puntos de vista, variables y codificaciones, no solo que añada restricciones.
2. Retención de Perfil Diverso (PDR): Una estrategia de selección de contexto que aplica MMR a los vectores de tiempo de ejecución por instancia. Retiene intentos que son rápidos pero exhiben comportamientos de resolución distintos, con el objetivo de diversificar el espacio de búsqueda más allá de las métricas simples de recencia o calidad.
3. Evaluación Sistemática: Una comparación exhaustiva de diez estrategias de búsqueda a través de ocho problemas, demostrando que la retención de un contexto diverso supera a las estrategias que retienen únicamente los más recientes o los más rápidos.
4. Selección Basada en Validación: La introducción de un paso de selección de modelo final basado en validación (frecuentemente ausente en los pipelines de AHD) se muestra como un factor que mejora consistentemente el rendimiento en datos no vistos y mitiga el sobreajuste.

Resultados

• Ganancias de Rendimiento: La búsqueda evolutiva produce aceleraciones sustanciales en las instancias de prueba no vistas. La mejor estrategia (PDR) logró una media geométrica de aceleración de 2.26× en todos los problemas, con instancias específicas mostrando ganancias de hasta 250.7× (en Matrices de Cobertura).
• La Diversidad Importa: Las estrategias que mantienen un contexto diverso (PDR, EoH con retroalimentación) generalmente superan a aquellas que dependen únicamente de la recencia (Last-1) o la calidad (Top-1). PDR superó a la estrategia de calidad únicamente Top-5 por un factor de 1.30×.
• Modelos Completos vs. Streamliners: El enfoque propuesto de reformulación de modelo completo superó significativamente a un baseline adaptado que solo genera streamliners aditivos (StreamLLM-single), el cual logró solo un 1.02× de aceleración.
• Eficiencia de Costos: Mientras que Sampling generó la mayor cantidad de tokens, Full-history se mantuvo rentable debido al almacenamiento en caché de KV. PDR ofreció la mayor aceleración con un costo menor que Sampling.
• Fiabilidad: Ninguno de los modelos seleccionados devolvió respuestas inválidas o resultados de insatisfacción falsos en las instancias de prueba. La selección basada en validación filtró con éxito los candidatos que se sobreajustaban a los datos de entrenamiento.

Significancia y Reivindicaciones

El artículo afirma que la reformulación iterativa guiada por LLMs puede automatizar el descubrimiento de modelos de restricciones de alto rendimiento, logrando aceleraciones significativas sin intervención humana. Destaca que la diversidad de comportamiento en el contexto de búsqueda es un factor crítico para el éxito, superando las métricas tradicionales como la recencia o la velocidad bruta.

Los autores señalan modestamente que, aunque los resultados son prometedores, el estudio se limita a un solo LLM, una única configuración de solver y ocho problemas de satisfacción específicos. Sugieren que trabajos futuros podrían explorar problemas de optimización, diferentes solvers y el uso de retroalimentación más explícita del solver (por ejemplo, conteos de conflictos, profundidad del árbol de búsqueda) para refinar aún más las métricas de diversidad. El trabajo se posiciona como un paso hacia la automatización del "santo grial" del modelado de restricciones, yendo más allá de la mera corrección hacia una automatización orientada al rendimiento.