Resumen Técnico: Descubrimiento de Algoritmos con LLMs: Búsqueda Evolutiva Encuentra Aprendizaje por Refuerzo

Declaración del Problema

El descubrimiento de algoritmos eficientes para problemas complejos, particularmente en matemáticas y optimización combinatoria, ha dependido históricamente de una sustancial experiencia humana. Si bien los avances recientes en Modelos de Lenguaje Grandes (LLMs) combinados con búsqueda evolutiva (por ejemplo, el método FunSearch) han mostrado promesa en la automatización de este descubrimiento, los enfoques existentes tratan al LLM como un generador estático. Estos métodos utilizan al LLM para proponer nuevos programas basados en éxitos previos, pero no logran actualizar los parámetros internos del modelo en función de las señales obtenidas durante la exploración evolutiva. En consecuencia, pierden la oportunidad de aprovechar la naturaleza paramétrica del LLM para refinar su política de búsqueda con el tiempo, lo que potencialmente conduce a una convergencia subóptima o a una exploración ineficiente del espacio de soluciones.

Metodología: EvoTune

Los autores proponen EvoTune, un marco que integra estrechamente la búsqueda evolutiva con el Aprendizaje por Refuerzo (RL) para refinar continuamente el operador de búsqueda del LLM. El método opera en un bucle iterativo que consta de dos fases alternas:

1. Búsqueda Evolutiva (Exploración):

   • El LLM genera programas candidatos en Python (algoritmos) basados en prompts construidos a partir de programas de alta puntuación descubiertos en iteraciones anteriores.
   • Estos programas se evalúan en tareas específicas de optimización combinatoria (por ejemplo, Empaquetado de Bins, Problema del Viajante, Flatpack) para obtener puntuaciones de recompensa (típicamente el negativo de la brecha de optimalidad).
   • Los programas válidos y sus puntuaciones se almacenan en una base de datos de programas, organizada en "islas" para mantener la diversidad y prevenir una convergencia prematura.
   • La búsqueda emplea una estrategia de "arranque en frío" (bootstrapping), donde el LLM analiza las diferencias entre programas de alto rendimiento y bajo rendimiento para guiar la generación de nuevos candidatos.

2. Entrenamiento de RL (Refinamiento):

   • Periódicamente (cada $f_{RL}$ iteraciones), la política de generación del LLM ($\pi_\theta$) se actualiza utilizando los datos acumulados de la búsqueda evolutiva.
   • Los autores formulan esto como un problema de Optimización de Preferencias. Construyen un conjunto de datos de preferencias $D_{pref}$ compuesto por tripletes $(x, y^+, y^-)$, donde $x$ es el prompt, $y^+$ es un programa con una recompensa más alta y $y^-$ es un programa con una recompensa más baja.
   • El modelo se ajusta fino utilizando Optimización Directa de Preferencias (DPO). A diferencia del DPO estándar fuera de línea, EvoTune opera en un entorno fuera de política donde los datos son generados dinámicamente por el propio modelo en evolución.
   • Preservación de la Diversidad: Una elección de diseño crítica es el uso de regularización KL hacia adelante (en contraposición al más común KL hacia atrás) dentro del objetivo de DPO. Esto fomenta un comportamiento de "cobertura de masa", evitando que el modelo colapse en un solo modo y preservando la diversidad de salida esencial para una búsqueda evolutiva efectiva.

Contribuciones Clave

1. Integración de RL en la Búsqueda Evolutiva: El artículo afirma ser el primero en demostrar el potencial de integrar estrechamente la búsqueda evolutiva basada en LLM con el ajuste fino de RL en el bucle. A diferencia de los métodos anteriores que utilizan LLMs únicamente como generadores estáticos, EvoTune actualiza los pesos del modelo para aprovechar mejor los conocimientos obtenidos de la exploración.
2. Aceleración del Descubrimiento de Algoritmos: Al refinar la política de búsqueda mediante RL, el método acelera el descubrimiento de algoritmos superiores. Los experimentos en tres LLMs ajustados a instrucciones (Llama3.2 1B, Phi 3.5 Mini, Granite 3.1 2B) muestran ganancias de rendimiento consistentes sobre el método base FunSearch.
3. Alineación que Preserva la Diversidad: Los autores demuestran la ventaja de utilizar un objetivo de alineación modificado (DPO regularizado con KL hacia adelante) para preservar la diversidad de salida. Esto es crítico para las estrategias evolutivas, ya que el colapso de modos puede obstaculizar el descubrimiento de soluciones novedosas.
4. Amplia Aplicabilidad: El método se valida en diversos puntos de referencia, incluidos problemas combinatorios estándar (Empaquetado de Bins, TSP, Flatpack), desafíos reales de Google Hash Code (Optimización de Centros de Datos, Viajes de Conducción Autónoma) y tareas de regresión simbólica (LLM-SR).

Resultados Experimentales

Los autores evaluaron EvoTune frente a una línea base estilo FunSearch (búsqueda evolutiva sin entrenamiento de modelo) en múltiples tareas y modelos:

• Ganancias de Rendimiento: EvoTune logró consistentemente puntuaciones de recompensa finales más altas (brechas de optimalidad más bajas) para los 50 programas descubiertos superiores en comparación con la línea base. La brecha de rendimiento a menudo se amplió a medida que aumentaba el presupuesto de muestreo, lo que sugiere que presupuestos más grandes amplifican las ventajas del método.
• Generalización: Los programas evolucionados demostraron robustez en conjuntos de validación perturbados y conjuntos de prueba extraídos de la misma distribución, lo que indica que las políticas aprendidas generalizan más allá de las instancias específicas vistas durante el entrenamiento.
• Puntos de Referencia del Mundo Real:
  • En la tarea de Optimización de Centros de Datos de Google Hash Code, EvoTune logró una puntuación de 418, superando la puntuación humana superior de 407 y superando a la línea base FunSearch (414).
  • En tareas de Regresión Simbólica (LLM-SR), EvoTune superó a la línea base evolutiva y, notablemente, superó a las líneas base que utilizan modelos más grandes o propietarios (por ejemplo, Mixtral 8x7B, GPT-3.5-turbo) mientras utilizaba un modelo más pequeño (Phi-3.5 Mini, 3.8 mil millones de parámetros).
• Estudios de Ablación:
  • KL hacia adelante vs. KL hacia atrás: Los experimentos confirmaron que la regularización KL hacia adelante produce recompensas más altas y un mayor número de soluciones únicas en comparación con el KL hacia atrás, validando la importancia de la preservación de la diversidad.
  • RL Alternativo: Los autores probaron ReSTEM (Ajuste Fino Supervisado en salidas de alta puntuación) como alternativa a DPO. Los resultados indicaron que DPO superó consistentemente a ReSTEM y fue menos sensible al ajuste de hiperparámetros.

Significado y Afirmaciones

El artículo posiciona a EvoTune como un paso significativo hacia adelante en el diseño automatizado de algoritmos al abordar la "Lección Amarga" (Sutton, 2019), que argumenta que la búsqueda y el aprendizaje son sinérgicos. Los autores afirman que:

• Sinergia: La búsqueda genera nuevos datos, mientras que el aprendizaje destila patrones de esos datos para guiar la exploración futura de manera más efectiva.
• Eficiencia: Integrar RL permite que el sistema vaya más allá de simplemente aumentar la puntuación promedio de una población; guía activamente la búsqueda evolutiva hacia soluciones superiores (medido por el rendimiento top-k) mientras mantiene la diversidad requerida para la innovación.
• Escalabilidad: El método demuestra potencial para escalar a entornos del mundo real, como lo demuestra su éxito en problemas complejos y no sintéticos como la optimización de centros de datos y el modelado de tensión-deformación.

Los autores reconocen modestamente las limitaciones, señalando que sus experimentos se realizaron con modelos que van desde 1B hasta 3.8 mil millones de parámetros y que se necesita una mayor escalabilidad del tamaño del modelo y de los presupuestos de muestreo para comprender plenamente el potencial del método. También destacan la compensación entre los costos computacionales adicionales de la fase de entrenamiento de RL y las ganancias en la eficiencia de inferencia y la calidad de la solución.