Cómo la Búsqueda Evolutiva Bidireccional mejora la automejora de los LLM

El cuello de botella del muestreo en la automejora de los LLM

Los modelos de lenguaje de gran tamaño (LLM) y los sistemas agentivos pueden resolver tareas complejas de razonamiento, pero su automejora depende de generar muestras de alta calidad. Durante el entrenamiento, mejores muestras permiten un post-entrenamiento más efectivo; en inferencia, impulsan el escalado en tiempo de prueba. Los métodos de muestreo dominantes —best-of-N y búsqueda en árbol— comparten dos limitaciones fundamentales.

Primero, dependen de señales de verificación dispersas, típicamente retroalimentación binaria o de grano grueso, que ofrecen poca orientación durante la búsqueda. Segundo, construyen candidatos extendiendo trayectorias de forma autorregresiva, confinando la exploración a regiones con una masa de probabilidad sustancial del modelo. En problemas difíciles, las soluciones correctas a menudo se encuentran en regiones de baja probabilidad que estos métodos raramente alcanzan. Este artículo presenta un marco que aborda ambos problemas simultáneamente.

Búsqueda Evolutiva Bidireccional: Un nuevo marco

La Búsqueda Evolutiva Bidireccional (BES) acopla una búsqueda evolutiva hacia adelante con un proceso de descomposición de objetivos hacia atrás. La búsqueda hacia adelante aumenta la expansión autorregresiva estándar con operadores evolutivos que recombinan trayectorias parciales, generando candidatos más allá de la distribución típica del modelo. La búsqueda hacia atrás descompone recursivamente la tarea original en subobjetivos verificables, produciendo retroalimentación intermedia densa que guía la búsqueda hacia adelante.

Este diseño bidireccional permite a BES descubrir soluciones que ni la expansión pura ni la búsqueda con recompensa dispersa pueden alcanzar, haciéndolo efectivo tanto para la generación de muestras de post-entrenamiento como para la resolución de problemas en tiempo de inferencia.

Búsqueda hacia adelante: Operadores evolutivos más allá de la expansión autorregresiva

La búsqueda hacia adelante mantiene una población de trayectorias parciales (nodos). En cada paso, aplica uno de cinco operadores: expansión (muestreo de nuevos pasos desde la política) o uno de cuatro operadores evolutivos inspirados en la recombinación biológica.

• Combinación fusiona los sufijos de dos trayectorias más allá de un prefijo compartido.
• Eliminación remueve un paso interior para producir un candidato más corto.
• Translocación trasplanta un solo paso de una trayectoria a otra.
• Cruce empalma el prefijo de una trayectoria con la cola de otra.

Los padres se seleccionan mediante una distribución de Boltzmann sobre las puntuaciones hacia atrás (y puntuaciones de pares para operadores de dos padres), con un recocido de temperatura que va de la exploración a la explotación. Estos operadores permiten que la búsqueda reestructure y recombine trayectorias existentes, generando candidatos que ningún despliegue de política único podría producir.

Búsqueda hacia atrás: Retroalimentación densa mediante descomposición de objetivos

La búsqueda hacia atrás construye un árbol de objetivos con raíz, solicitando recursivamente a la política que descomponga la tarea de nivel superior en subobjetivos más finos. Cada subobjetivo $g$ viene con un verificador local $V_g(x,n) \in [0,1]$ que prueba qué tan bien un nodo candidato $n$ lo aborda.

La puntuación de un nodo se calcula recursivamente:

$s(n,g) = \alpha \cdot V_g(x,n) + (1-\alpha) \cdot \frac{1}{|\text{ch}(g)|} \sum_{g' \in \text{ch}(g)} s(n,g')$

donde $\alpha$ equilibra las contribuciones del padre y los hijos. Para los subobjetivos hoja, $s(n,g) = V_g(x,n)$. Si un objetivo se satisface completamente, la puntuación se cortocircuita a 1. Para operadores de dos padres, una puntuación de par $s(n_a, n_b)$ usa el máximo de las salidas del verificador de los dos padres, favoreciendo candidatos complementarios que cubren diferentes partes del árbol de objetivos.

Esta señal densa e interpretable guía la selección de padres incluso cuando ningún candidato ha resuelto completamente el problema, mejorando drásticamente la eficiencia de la búsqueda.

Garantías teóricas: Escapando de la capa de entropía

El artículo proporciona dos motivaciones teóricas. Primero, bajo suposiciones suaves (sorpresa por paso acotada, dependencia de pasos decreciente y correlación total de bloque lineal), el Teorema 4.4 demuestra que la búsqueda solo por expansión está confinada a una estrecha capa de entropía $A_\epsilon(T) = \{y : |-\log P(y) - H_T| \le \epsilon T\}$, cuyo tamaño es como máximo $\exp(H_T + \epsilon T)$. En contraste, los operadores evolutivos que recombinan bloques de trayectorias independientes producen candidatos con log-probabilidad esperada estrictamente más allá de esta capa, con una fracción positiva escapando de ella.

Segundo, el Teorema 4.5 muestra que la descomposición de subobjetivos hacia atrás produce una reducción exponencial en la complejidad de muestreo. La búsqueda solo terminal requiere $\Omega(1/\prod_i p_i)$ candidatos para encontrar una solución completa, mientras que la búsqueda guiada hacia atrás necesita solo $O(p_{\min}^{-1} \log(m/\delta))$ para recolectar evidencia para todos los $m$ subobjetivos. En el caso simétrico $p_i = p$, la razón es $\Omega(p^{-(m-1)} / \log(m/\delta))$, exponencial en el número de subobjetivos.

Post-entrenamiento e inferencia: mejoras experimentales

Se evaluó BES tanto en tareas de post-entrenamiento como de inferencia.

Post-entrenamiento. En razonamiento lógico (Knights-and-Knaves), GRPO y MaxRL mostraron poca mejora, mientras que BES aumentó de forma constante la precisión de validación (Figura 3). En razonamiento multi-salto (MuSiQue), BES superó sustancialmente a GRPO y Tree-GRPO en dos escalas de modelo (Tabla 1).

Método	Precisión (%)	# Búsqueda válida	# Acciones válidas	Tasa de finalización
Llama-3.2-3B-Instruct
Modelo base	4.0	–	–	–
+ GRPO	2.1 (-1.9)	0.84	0.20	0.64
+ Tree-GRPO	3.9 (-0.1)	1.50	2.14	0.64
+ BES	7.0 (+3.0)	2.31	3.29	0.97
Llama-3.1-8B-Instruct
Modelo base	6.6	–	–	–
+ GRPO	5.6 (-1.0)	1.46	1.83	0.37
+ Tree-GRPO	7.4 (+0.8)	0.65	1.36	0.71
+ BES	10.4 (+3.8)	2.11	3.05	0.94

Inferencia. En tres bancos de pruebas de resolución de problemas abiertos (Circle Packing, Heilbronn Convex), BES superó a todos los marcos de código abierto tanto en rendimiento promedio como en el mejor caso, con menor varianza (Tabla 2).

Estrategia	Circle Packing (Cuad.)	Circle Packing (Rect.)	Heilbronn (Convex)
	Prom.	Mejor	Prom.
OpenEvolve	2.531	2.541	2.267
GEPA	2.613	2.628	2.326
ShinkaEvolve	2.464	2.541	2.335
BES	2.623	2.632	2.349

Ablación, coste y conclusión

Un estudio de ablación en razonamiento lógico confirmó que tanto los operadores de evolución como la búsqueda hacia atrás contribuyen a las mejoras de BES (Figura 4). Eliminar cualquiera de los componentes redujo el rendimiento, aunque ambas ablaciones aún superaron a GRPO y MaxRL.

El análisis de costes mostró que BES añade menos del 30 % de sobrecarga de tiempo real respecto a Tree-GRPO, a la vez que ofrece una precisión y un comportamiento de búsqueda sustancialmente mejores. En problemas abiertos, BES incurrió en un coste adicional modesto de API ($14–$19 por ejecución) en comparación con ShinkaEvolve ($12–$13), pero alcanzó valores objetivo consistentemente más altos.

En resumen, BES aborda los desafíos gemelos de la verificación dispersa y la exploración confinada mediante una búsqueda evolutiva bidireccional. Al acoplar la recombinación hacia adelante con la descomposición de objetivos hacia atrás, descubre soluciones de alta calidad que eluden los métodos existentes, permitiendo mejoras consistentes tanto en post-entrenamiento como en inferencia a través de diversos dominios de razonamiento.