Resumen Técnico: Asignación de Recursos Computacionales en Búsqueda Evolutiva

Enunciado del Problema

Los sistemas de búsqueda evolutiva guiados por Modelos de Lenguaje Grande (LLM) (por ejemplo, FunSearch, AlphaEvolve, CodeEvolve) han logrado resultados de vanguardia en descubrimiento matemático y optimización combinatoria. Sin embargo, la literatura existente reporta predominantemente el único mejor resultado de un número no especificado de ejecuciones, dejando la distribución entre ejecuciones sin documentar. Además, los costos computacionales reportados varían en órdenes de magnitud, lo que dificulta evaluar la fiabilidad de una sola ejecución bajo un presupuesto fijo.

El problema central abordado es la asignación de recursos computacionales: dado un presupuesto fijo de llamadas al LLM ($C$), ¿cómo debe distribuirse este presupuesto entre profundidad (refinamiento secuencial de una sola trayectoria) y amplitud (exploración paralela de múltiples trayectorias)? Los sistemas actuales suelen fijar estos hiperparámetros (por ejemplo, tamaño de población y número de generaciones) sin una comprensión sistemática de cómo la asignación afecta el rendimiento esperado y la fiabilidad.

Metodología

1. Caracterización Empírica de la Asignación Profundidad-Amplitud

Los autores realizaron un estudio empírico sistemático en tres tareas de optimización geométrica (Empaquetado de Círculos, MinMaxDist, Triángulo de Heilbronn) y cuatro tamaños de modelo (Qwen3-1.7B a 14B, más Llama-3.1-8B). Definieron el problema de asignación como dividir el presupuesto $C$ en $T$ generaciones de $N$ hijos paralelos ($C = T \times N$).

• Envoltura Aptitud-Computación: Analizaron la relación entre la aptitud alcanzable y los FLOPs efectivos (teniendo en cuenta el tamaño del modelo y la eficiencia de la caché). Observaron que, aunque los modelos más grandes lideran con igual número de llamadas, su ordenamiento de rendimiento colapsa en gran medida cuando se mide contra los FLOPs efectivos, siempre que el par modelo-tarea sea "capaz".
• Regularidad Profundidad-Amplitud: Ajustaron un modelo bilineal paramétrico al paisaje de aptitud:
  $$\log(1 - V) = \beta_0 + a \log T + b \log N + c \log T \log N$$
  donde $V$ es la aptitud. El coeficiente de interacción $c$ determina la geometría de la asignación óptima:
  • Óptimos de Esquina ($|c| \approx 0$): Tareas como el Empaquetado de Círculos exhiben amplias mesetas donde muchas asignaciones producen resultados similares, a menudo favoreciendo la profundidad.
  • Laderas Interiores ($c < 0$): Tareas como MinMaxDist exhiben una ladera aguda donde se requiere una mezcla equilibrada de profundidad y amplitud para un rendimiento óptimo.
  • Puerta de Capacidad: Estas regularidades solo se mantienen para modelos que han cruzado un umbral de capacidad para la tarea específica; los modelos débiles no logran exhibir compensaciones estructuradas entre profundidad y amplitud.

2. BaSE: Evolución Autónoma Basada en Bandidos

Motivados por la alta varianza en los resultados de las ejecuciones (donde configuraciones idénticas producen puntuaciones finales de aptitud muy diferentes debido a la estocasticidad en el proceso de mutación del LLM), los autores propusieron BaSE.

• Mecanismo: BaSE trata la búsqueda evolutiva como un problema de Bandido Multi-Brazo (MAB). En lugar de comprometer todo el presupuesto a una sola trayectoria (Codicioso) o a un conjunto fijo de islas (Protocolo de Islas), BaSE mantiene $K$ trayectorias paralelas.
• Asignación Adaptativa: En cada paso, un algoritmo de bandido (UCB, EXP3.P o Muestreo Thompson) selecciona qué trayectoria extender con la siguiente llamada al LLM. Esto enruta dinámicamente los recursos computacionales alejándose de ejecuciones estancadas hacia las prometedoras.
• Ortogonalidad: BaSE no altera el modelo base, el prompt ni la lógica de muestreo de padres dentro de una trayectoria. Opera estrictamente a nivel de asignación de recursos entre trayectorias.

Resultados Clave

1. Regularidades Empíricas

• Colapso de Capacidad: Para modelos capaces, la envoltura de rendimiento está determinada por los FLOPs efectivos y no solo por el tamaño del modelo.
• Geometría Dependiente de la Tarea: La división óptima entre profundidad y amplitud no es universal; depende de la "familia algorítmica" de la tarea (por ejemplo, si la solución requiere una biblioteca específica como scipy o una construcción analítica específica).
• Estocasticidad: Incluso con asignación fija, las ejecuciones individuales varían significativamente. Algunas ejecuciones convergen a alta aptitud, mientras que otras se estancan temprano debido a fijarse en una familia algorítmica subóptima.

2. Rendimiento de BaSE

• Mejora de la Aptitud Media: En 8 celdas (modelo, tarea), BaSE mejoró la mejor aptitud media en un 12.3% sobre las líneas base más fuertes del protocolo de islas (por ejemplo, OpenEvolve, CodeEvolve, ShinkaEvolve) sin cambiar el modelo ni el prompt.
• Ganancias en Fiabilidad: Las ganancias más significativas se observaron en configuraciones de alta varianza. Por ejemplo, en la tarea del Triángulo de Heilbronn con Llama-3.1-8B, los métodos sin BaSE a menudo fallaron en producir soluciones válidas (aptitud $\approx 0$), mientras que BaSE (Muestreo Thompson) logró una aptitud media de 0.4387.
• Eficiencia de Muestra: BaSE alcanzó umbrales de aptitud objetivo significativamente más rápido (menos generaciones y FLOPs) que las líneas base codiciosas o de asignación fija. Por ejemplo, en MinMaxDist, UCB alcanzó un umbral de 0.95 en 92 generaciones, mientras que la línea base codiciosa requirió 485.
• Ablación: Tamaños moderados de grupo de brazos ($K \in \{5, 10, 20\}$) proporcionaron el mejor equilibrio entre diversidad y profundidad de refinamiento.

Significado y Afirmaciones

El artículo afirma que la asignación de recursos computacionales es una palanca distinta y crítica para mejorar la búsqueda evolutiva guiada por LLM, separada de la escalabilidad del modelo o la ingeniería de prompts.

• Asignación vs. Ingeniería: Los autores enfatizan que sus mejoras no se deben a prompts o modelos mejores. De hecho, señalan que algunas líneas base (como ShinkaEvolve) lograron puntuaciones altas en tareas específicas en parte debido a pistas inducidas por el prompt (por ejemplo, sugerir scipy.optimize), mientras que BaSE logra ganancias puramente mediante el enrutamiento adaptativo de recursos.
• Fiabilidad: La contribución principal es desplazar el enfoque del reporte de "mejor caso" al rendimiento "esperado". BaSE proporciona una ganancia en fiabilidad, asegurando que un practicante sea menos propenso a desperdiciar un presupuesto fijo en una trayectoria que ya se ha estancado.
• Complementariedad: BaSE se presenta como complementario a los mecanismos existentes dentro de la ejecución (como el muestreo de padres). Puede superponerse a protocolos existentes (Codicioso, Isla) para mejorar aún más el rendimiento, particularmente en configuraciones inestables o de alta varianza.

El trabajo concluye que, aunque la capacidad del modelo establece el techo de lo que es alcanzable, la asignación gobierna qué tan eficientemente un método se acerca a ese techo, y la asignación adaptativa mediante bandidos es una estrategia robusta para la búsqueda con presupuesto finito.