Resumen Técnico: HeuriGym: Un Benchmark Agéntico para Heurísticas Creadas por LLM en Optimización Combinatoria

Declaración del Problema

Las metodologías de evaluación actuales para los Modelos de Lenguaje de Gran Escala (LLM) enfrentan una crisis dual al evaluar sus capacidades de resolución de problemas. Primero, los benchmarks objetivos basados en verdades fundamentales (p. ej., AIME, HumanEval) dependen de preguntas de respuesta cerrada que son susceptibles de contaminación de datos y saturación de rendimiento, fallando al no reflejar escenarios del mundo real donde las soluciones no son únicas ni predefinidas. Segundo, las evaluaciones subjetivas basadas en la preferencia de un juez (p. ej., Chatbot Arena) introducen una alta varianza y a menudo priorizan factores superficiales sobre la calidad del razonamiento sustantivo.

Existe una brecha crítica en evaluar si los LLM pueden ir más allá del reconocimiento de patrones para exhibir una verdadera ingenuidad en la resolución de problemas en flujos de trabajo de ingeniería complejos e iterativos. Específicamente, los benchmarks existentes luchan por evaluar la capacidad de diseñar heurísticas novedosas para problemas de optimización combinatoria (CO), los cuales requieren navegar vastos espacios de soluciones, adherirse a restricciones estrictas y adaptar estrategias basadas en la retroalimentación de la ejecución.

Metodología

Los autores presentan HeuriGym, un marco agéntico diseñado para evaluar la capacidad de los LLM para generar, ejecutar e iterativamente refinar algoritmos heurísticos para problemas de optimización combinatoria.

Visión General del Marco

HeuriGym opera a través de un bucle agéntico interactivo que consta de tres etapas:

1. Descripción del Problema: El LLM recibe un prompt estructurado que contiene un trasfondo en lenguaje natural, una formalización matemática del objetivo y las restricciones, y formatos específicos de archivos de entrada/salida. A diferencia del trabajo previo que proporciona implementaciones parciales o andamiajes, HeuriGym solo proporciona la interfaz de la función, requiriendo que el LLM diseñe las estructuras de datos y los algoritmos desde cero.
2. Ejecución y Verificación: El código generado se compila o interpreta dentro de un entorno de sandbox. Un verificador de dominio específico comprueba la satisfacción de las restricciones (p. ej., preservación de dependencias), mientras que un evaluador calcula el costo basado en el objetivo de optimización.
3. Refinamiento Iterativo: Los registros de ejecución, los resultados de la verificación y las métricas de rendimiento de un pequeño conjunto de demostración se anexan al prompt. Este bucle de retroalimentación permite al LLM depurar errores, corregir violaciones de restricciones y refinar sus estrategias heurísticas a lo largo de múltiples iteraciones.

Construcción del Benchmark

El benchmark comprende nueve problemas de optimización combinatoria que abarcan sistemas informáticos, logística y biología computacional (p. ej., programación de operadores, mapeo tecnológico, emparejamiento de tripulación de aerolíneas, diseño de secuencias de proteínas).

• Criterios de Selección: Los problemas fueron seleccionados para tener una exposición limitada en la literatura (menos de 1,000 citas para el artículo más citado) para minimizar los riesgos de memorización. Presentan especificaciones de lenguaje natural bien definidas, espacios de solución extensos y casos de datos escalables.
• Conjunto de Datos: Cada problema incluye un pequeño conjunto de demostración (~5 instancias) para prompting de pocos disparos (few-shot) y refinamiento iterativo, y un conjunto de evaluación más grande (docenas de instancias) para pruebas finales.

Métricas de Evaluación

Para abordar las limitaciones de las métricas estándar como PASS@k, los autores proponen:

• SOLVEs@i: Rastrea la probabilidad de resolver un problema con restricciones dentro de $i$ iteraciones, midiendo el éxito al pasar por tres etapas: Ejecución (Etapa I), Generación de Solución (Etapa II) y Verificación (Etapa III).
• Índice de Calidad-Rendimiento (QYI): Una métrica unificada definida como la media armónica de la Calidad (qué tan cerca está la solución de una línea base experta) y el Rendimiento (la proporción de instancias que pasan la verificación).
  • $Calidad = \frac{1}{\hat{N}} \sum \min(1, \frac{c^*_n}{c_n})$, donde $c_n$ es el costo del LLM y $c^*_n$ es el costo experto.
  • $Rendimiento = \frac{\hat{N}}{N}$, donde $\hat{N}$ es el número de soluciones verificadas.
  • $QYI = \frac{(1 + \beta^2) \cdot Calidad \cdot Rendimiento}{(\beta^2 \cdot Calidad) + Rendimiento}$ (con $\beta=1$).

Resultados Clave

Los autores evaluaron nueve modelos de última generación (incluyendo GPT-o4-mini-high, Gemini-2.5-Pro, DeepSeek-R1 y variantes de LLaMA) en el benchmark HeuriGym.

• Brecha de Rendimiento: Incluso los modelos de primer nivel luchan por alcanzar un rendimiento de nivel experto. El modelo con mejor desempeño, Gemini-2.5-Pro, logró un puntaje QYI de aproximadamente 0.62, indicando que sus soluciones son, en promedio, solo un 60% tan efectivas como las heurísticas creadas por expertos. Otros modelos puntuaron significativamente más bajo (p. ej., LLaMA-3.3 y LLaMA-4-Maverick por debajo de 0.30).
• Mejora Iterativa: Aumentar el número de iteraciones mejora significativamente el rendimiento. Por ejemplo, la tasa de éxito de GPT-o4-mini-high (SOLVEIII) aumentó del 53.2% en la iteración 1 al 74.8% en la iteración 10, resaltando la importancia del refinamiento iterativo.
• Modos de Fallo: El análisis reveló tipos de fallos comunes, incluyendo APIs alucinadas, lógica algorítmica incorrecta, malentendidos de las restricciones y tiempos de espera agotados (timeouts).
• Marcos Evolutivos: Los marcos de búsqueda evolutiva estándar (p. ej., ReEvo, HSEvo) se desempeñaron pobremente en comparación con el modelo base, fallando a menudo al incorporar la retroalimentación de ejecución de manera efectiva y rompiendo el contexto a través de las iteraciones.

Significancia y Contribuciones

El artículo reclama tres contribuciones primarias:

1. Una Suite de Benchmark de Código Abierto: Una colección de nueve problemas de optimización combinatoria realistas y de alto impacto que evalúan el razonamiento de múltiples pasos y las capacidades de diseño algorítmico, yendo más allá de los patrones memorizados.
2. Un Marco Agéntico de Extremo a Extremo: Un sistema que soporta la generación de soluciones, verificación automatizada y refinamiento iterativo, sirviendo como banco de pruebas para técnicas de prompting avanzadas y estrategias evolutivas.
3. Perspectivas Empíricas: Un estudio exhaustivo que revela que los LLM actuales, a pesar de sus capacidades de razonamiento, enfrentan limitaciones persistentes en el uso de herramientas, planificación y razonamiento adaptativo cuando se aplican a problemas científicos y de ingeniería complejos del mundo real.

Los autores posicionan a HeuriGym como un paso necesario para guiar el desarrollo de los LLM hacia una resolución de problemas más efectiva y realista en dominios donde las soluciones óptimas son tratables solo para instancias pequeñas y donde el descubrimiento de heurísticas es esencial. El benchmark tiene como objetivo exponer la brecha entre las capacidades actuales de los modelos y las demandas de los flujos de trabajo de ingeniería prácticos, fomentando el desarrollo de modelos capaces de una genuina invención de heurísticas en lugar de un mero reconocimiento de patrones.