Resumen Técnico: LLaMEA-SAGE

Declaración del Problema

El Diseño de Algoritmos Automatizado (AAD, por sus siglas en inglés) utilizando Modelos de Lenguaje de Gran Escala (LLMs) ha emergido como un paradigma prometedor para el descubrimiento de algoritmos de optimización directamente desde prompts de lenguaje natural. Sin embargo, los enfoques basados en LLM actuales, como LLaMEA, dependen casi exclusivamente de la retroalimentación de aptitud (rendimiento en benchmarks) para guiar la búsqueda evolutiva. Este bucle de retroalimentación de "caja negra" deja una cantidad sustancial de información dentro del código generado sin utilizar. En consecuencia, las estrategias de búsqueda suelen tener dificultades para equilibrar la exploración y la explotación en espacios de código grandes y heterogéneos, lo que conduce al estancamiento prematuro o al uso ineficiente de consultas costosas a LLMs. Además, existe una comprensión limitada sobre cómo mejorar sistemáticamente los algoritmos generados por LLM tras la generación inicial y cómo estas mejoras se comparan con los métodos de vanguardia (SOTA) bajo benchmarks controlados.

Metodología: LLaMEA-SAGE

El artículo propone LLaMEA-SAGE, un marco que integra retroalimentación de Inteligencia Artificial Explicable (XAI) estructurada en el proceso de diseño de algoritmos evolutivos de LLaMEA. El mecanismo central consiste en extraer características estructurales del código de los algoritmos candidatos y utilizarlas para guiar las mutaciones subsecuentes.

1. Extracción de Características Estructurales

Cada algoritmo candidato se representa como código Python ejecutable. El sistema analiza el código mediante un Árbol de Sintaxis Abstracta (AST) para construir un grafo dirigido. A partir de este grafo, el sistema extrae un conjunto rico de características, que incluyen:

• Estadísticas de teoría de grafos: Conteos de nodos/aristas, estadísticas de grado (media, varianza, entropía), profundidad del árbol, coeficientes de agrupamiento y métricas basadas en rutas (diámetro, camino corto promedio).
• Indicadores de complejidad: Complejidad ciclomática, conteo de tokens de funciones y conteos de parámetros agregados a través de las funciones.

2. Modelado Sustituto Basado en Archivo

Durante el proceso evolutivo, todas las soluciones evaluadas, sus puntuaciones de aptitud y sus características de código extraídas se almacenan en un archivo. Una vez alcanzado un tamaño mínimo de archivo, se entrena un modelo de árbol de regresión potenciado por gradiente (XGBoost) para aproximar la relación entre las características del código y la aptitud observada. Este modelo sustituto aprende relaciones no lineales entre la estructura algorítmica y el rendimiento.

3. IA Explicable (SHAP) para la Guía

Para derivar instrucciones accionables, el sistema aplica SHAP (SHapley Additive exPlanations) al modelo sustituto entrenado. Los valores SHAP cuantifican la contribución de cada característica a la aptitud predicha. Se selecciona la característica con la mayor atribución absoluta, y el signo de su valor SHAP determina si el valor de la característica debe aumentarse o disminuirse para mejorar el rendimiento.

4. Prompting de Mutación Guiada

La guía estructural se traduce en una instrucción de lenguaje natural que aumenta el prompt de mutación estándar proporcionado al LLM. Por ejemplo, si el análisis sugiere que aumentar la complejidad ciclomática correlaciona con un mejor rendimiento, el prompt se modifica a: "Basado en el análisis del archivo, intente aumentar la complejidad ciclomática total de la solución".
Crucialmente, esta guía sesga la generación del LLM hacia regiones estructurales empíricamente beneficiosas sin imponer restricciones sintácticas rígidas o plantillas predefinidas, preservando la expresividad del LLM.

Contribuciones Clave

1. Marco LLaMEA-SAGE: La propuesta de un mecanismo novedoso que guía el AAD utilizando retroalimentación impulsada por características derivadas de AST y análisis de complejidad, mediada por un modelo sustituto y análisis SHAP.
2. Benchmarking Sistemático: Una comparación experimental exhaustiva contra métodos de diseño de heurísticas basados en LLM de vanguardia, específicamente MCTS-AHD (Búsqueda en Árbol de Monte Carlo para el Diseño de Heurísticas de Algoritmos) y LHNS (Búsqueda de Vecindad de Heurística impulsada por LLM), junto con la línea base vanilla de LLaMEA.
3. Validación Empírica: Demostración de que la guía estructurada mejora la calidad y la robustez de los algoritmos en benchmarks de caja negra, respaldada por un análisis extensivo utilizando Grafos de Evolución de Código (CEG) y pruebas estadísticas.

Resultados Experimentales

Los autores evaluaron LLaMEA-SAGE a través de dos experimentos primarios utilizando la caja de herramientas de benchmarking IOH-BLADE.

Experimento 1: Comparación Controlada (SBOX-COST)

• Configuración: Comparó LLaMEA vanilla contra LLaMEA-SAGE en un subconjunto de la suite SBOX-COST (10 dimensiones, 5 instancias).
• Hallazgos: LLaMEA-SAGE logró un mejor rendimiento más rápido que el LLaMEA vanilla, particularmente en las etapas tempranas del proceso evolutivo. Aunque ambos métodos alcanzaron un rendimiento final similar dentro del presupuesto, el enfoque guiado mostró menos varianza entre ejecuciones.
• Significancia Estadística: LLaMEA-SAGE mostró una mejora promedio de 11.1 unidades de Área Bajo la Curva de Convergencia (AUC) con un gran tamaño de efecto (Cliff's $\delta$ = 0.60). Sin embargo, debido al número limitado de ejecuciones independientes (5 semillas), la diferencia no alcanzó significancia estadística ($p=0.44$).
• Análisis de Comportamiento: Los Grafos de Evolución de Código revelaron que la guía sesgó con éxito la exploración estructural. Notablemente, el prompt de "refinar" (refine) llevó a un aumento en la complejidad del código cuando se aplicaba la guía, mientras que el prompt de "nuevo aleatorio" (random new) a menudo ignoraba la guía o resultaba en una menor complejidad.

Experimento 2: Benchmark de Gran Escala (MA-BBOB)

• Configuración: Evaluado en la suite Many Affine BBOB (MA-BBOB), un estándar para competencias GECCO, comparando LLaMEA-SAGE contra LLaMEA vanilla, MCTS-AHD y LHNS.
• Hallazgos: LLaMEA-SAGE superó consistentemente a todos los baselines, incluyendo los métodos SOTA MCTS-AHD y LHNS. Alcanzó niveles de aptitud que el LLaMEA vanilla no pudo alcanzar incluso después del presupuesto de evaluación completo.
• Eficiencia: En términos de uso de tokens, LLaMEA-SAGE fue marginalmente más costoso que el LLaMEA vanilla, pero significativamente más eficiente que MCTS-AHD (que consulta al LLM múltiples veces por solución).
• Generalización: La validación final en instancias no vistas (diferentes dimensiones e instancias de problemas) mostró que el mejor algoritmo descubierto por LLaMEA-SAGE superó a otros algoritmos diseñados automáticamente y al ganador de la competencia MA-BBOB 2025 en tareas de 10 y 20 dimensiones, aunque no superó al ganador de la competencia ajustado para la tarea de 5 dimensiones para la cual fue optimizado específicamente.

Significancia y Reivindicaciones

El artículo afirma que LLaMEA-SAGE logra cerrar la brecha entre la estructura del código y la retroalimentación de rendimiento comprensible para humanos en el diseño de algoritmos automatizado. Al traducir señales estructurales en lenguaje natural, el método proporciona un sesgo inductivo basado en datos que dirige la evolución impulsada por LLM sin restringir la capacidad creativa del modelo.

Los autores enfatizan que incluso las correlaciones imperfectas y ruidosas derivadas de las características del código son suficientes para sesgar beneficiosamente la exploración en las etapas iniciales del AAD. El trabajo demuestra que las señales derivadas del código pueden mejorar efectivamente la eficiencia y la estabilidad del descubrimiento de algoritmos, ofreciendo una alternativa escalable y libre de plantillas a los enfoques existentes centrados en heurísticas.

Limitaciones y Trabajo Futuro

Los autores señalan modestamente varias limitaciones:

• Dependencia de LLM: Los experimentos se realizaron con un único backend de LLM (GPT-5-mini), aunque un ablativo preliminar con Gemini mostró tendencias consistentes.
• Alcance: La evaluación se limitó a la optimización de caja negra continua en dimensiones moderadas; la generalización a clases de problemas de alta dimensión, ruidosos o fundamentalmente diferentes sigue siendo una pregunta abierta.
• Análisis Estático: El conjunto de características actual captura solo propiedades estructurales estáticas, ignorando el comportamiento de ejecución dinámica o los efectos de interacción durante las ejecuciones de optimización.

Se propone como trabajo futuro combinar características estructurales con descriptores de tiempo de ejecución, explorar la guía adaptativa de múltiples características e integrar el mecanismo en otros marcos de AAD basados en LLM.