Resumen Técnico: Búsqueda de Árboles de Conceptos Contrastivos para el Descubrimiento de Algoritmos Asistido por LLM

Planteamiento del Problema

El descubrimiento de algoritmos asistido por Modelos de Lenguaje de Gran Escala (LLM) opera como un proceso de optimización iterativo y de caja negra, donde un LLM propone programas candidatos y un evaluador externo proporciona retroalimentación sobre la tarea. Si bien los paradigmas recientes (por ejemplo, FunSearch, AlphaEvolve) han redescubierto o mejorado con éxito soluciones a problemas combinatorios (como los problemas de tipo Erdős), estos dependen en gran medida de actualizaciones evolutivas impulsadas por el fitness (aptitud). En estos sistemas existentes, la selección de los padres se determina por el rendimiento bruto (fitness) de los programas, y la búsqueda procede como un paseo sobre el linaje de programas ordenados por su desempeño.

Una limitación crítica de este enfoque es que el espacio de programas permanece débilmente estructurado. Incluso cuando están restringidos por un LLM, los algoritmos generados suelen carecer de nociones claras de localidad, variación suave o estructura compositiva que puedan ser explotadas por algoritmos de búsqueda. En consecuencia, la guía se deriva principalmente de señales de fitness bruto y del prior implícito del LLM, en lugar de un entendimiento explícito y aprendido de qué componentes semánticos de los algoritmos son realmente útiles. Este artículo aborda la pregunta abierta de cómo explotar al máximo la representación interna del espacio de programas del LLM para mejorar la eficiencia y la interpretabilidad de la búsqueda.

Metodología: Búsqueda de Árboles de Conceptos Contrastivos (CCTS)

Los autores presentan la Búsqueda de Árboles de Conceptos Contrastivos (CCTS), un marco que desplaza la guía de la búsqueda desde el fitness bruto hacia un espacio de conceptos semánticos jerárquico y aprendido. La hipótesis central es que los algoritmos pueden describirse mediante un espacio de conceptos semánticos subyacente organizado como una jerarquía, donde los nodos representan conceptos y las aristas codifican la refinación o especialización.

1. Representación de Conceptos y Construcción del Árbol

• Extracción de Características: Cada programa candidato $x$ se mapea a una representación de características semánticas $b = \Phi(x)$, extraída mediante el uso de prompts para que el LLM genere una lista de conceptos relevantes.
• Estructura Jerárquica: Estos conceptos se organizan en un árbol de conceptos con raíz. Un vector de concepto $b$ es un vector indicativo donde las activaciones son cerradas por ancestros (activar un concepto hijo implica activar todos sus ancestros). El árbol es dinámico y crece a medida que se descubren nuevos conceptos durante la búsqueda.

2. Aprendizaje Contrastivo de la Utilidad de los Conceptos

En lugar de seleccionar padres basándose únicamente en su puntuación de fitness, CCTS aprende qué conceptos están asociados empíricamente con un alto rendimiento mediante un enfoque contrastivo:

• Partición: El archivo de programas evaluados se particiona en subconjuntos "buenos" ($y_i \ge \tau_t$) y "malos" ($y_i < \tau_t$) basados en un umbral de rendimiento.
• Ajuste del Modelo: Se ajustan dos modelos probabilísticos, $\hat{p}_{\eta^+}(b)$ y $\hat{p}_{\eta^-}(b)$, a las distribuciones de características de los subconjuntos buenos y malos, respectivamente. Los autores utilizan un enfoque de tipo Estimador de Parzen Estructurado por Árbol (TPE) con un modelo de Bernoulli jerárquico factorizado. Este modelo asume la independencia condicional de las características dado su padre en la jerarquía.
• Puntuación de la Razón de Verosimilitud: Se calcula una puntuación de razón de verosimilitud (log-utilidad de concepto) para cada programa:
  $$\log w(b) = \log \hat{p}_{\eta^+}(b) - \log \hat{p}_{\eta^-}(b)$$
  Esta puntuación cuantifica con qué fuerza un conjunto específico de conceptos distingue las soluciones de alto rendimiento de las de bajo rendimiento.

3. Selección de Padres y Dinámica de Búsqueda

• Muestreo Sesgado: Los padres se seleccionan del archivo con una probabilidad proporcional a su puntuación de razón de verosimilitud. Esto sesga la búsqueda hacia programas que contienen combinaciones de conceptos asociados empíricamente con la mejora.
• Mecanismo de Exploración: Para evitar la convergencia prematura y fomentar el descubrimiento de nuevos conceptos, CCTS incorpora un mecanismo de exploración ligero. Esto incluye:
  • Prios Beta: Suavizado de conteos para asegurar que los conceptos recién descubiertos nunca tengan una probabilidad de cero.
  • Sesgo de Novedad: Penalización de conceptos que han sido probados frecuentemente, favoreciendo regiones poco exploradas del árbol de conceptos.
  • Estrategia de Mezcla: Una mezcla de explotación (basada en el modelo contrastivo aprendido) y exploración (basada en la novedad) guía la selección de conceptos para inyectar en el prompt del LLM para la generación de los hijos.

Principales Contribuciones

1. Estructura Semántica Explícita: El artículo propone hacer explícita la estructura latente del espacio de algoritmos mediante el aprendizaje de un árbol de conceptos jerárquico, yendo más allá del espacio de programas no estructurado utilizado en los algoritmos evolutivos estándar.
2. Guía Contrastiva: Introduce un marco estadístico contrastivo que aprende a identificar qué conceptos priorizar y, crucialmente, qué conceptos evitar, en lugar de solo rastrear qué programas funcionan mejor.
3. Interpretabilidad: El método produce árboles de conceptos interpretables y específicos de la tarea que revelan la estructura semántica explorada durante la búsqueda, ofreciendo información sobre las estrategias algorítmicas que se están descubriendo.
4. Validación Sintética: Los autores construyen un entorno sintético controlado con un "árbol maestro" de conceptos y utilidades de verdad fundamental (ground-truth). Esto les permite validar que CCTS recupera la estructura semántica subyacente y que la dinámica de búsqueda observada es impulsada por el aprendizaje de las utilidades de los conceptos y no por artefactos específicos del LLM.

Resultados Experimentales

Los autores evaluaron CCTS en un banco de problemas de combinatoria de tipo Erdős, incluyendo empaquetamiento de círculos (circle packing), la conjetura de Kakeya aritmética, el problema del triángulo de Heilbronn y el problema de los cuadrados en un cuadrado.

• Ganancias de Rendimiento: CCTS alcanzó consistentemente puntuaciones más altas y una mejora más rápida en comparación con las estrategias de referencia (Uniforme, Codiciosa y selección $k$-élite) en múltiples tareas.
• Mecanismo de Mejora: El análisis reveló que las ganancias de rendimiento son impulsadas en gran medida por aprender qué conceptos evitar. Las ejecuciones exitosas identificaron un conjunto similar de conceptos de alta utilidad que las ejecuciones infructuosas, pero demostraron una capacidad significativamente mejor para suprimir conceptos de baja utilidad (perjudiciales). Esto sugiere que CCTS estabiliza la búsqueda al reducir la exploración improductiva causada por correlaciones engañosas en el prior inicial del LLM.
• Validación Sintética: En el entorno sintético, las utilidades de los conceptos aprendidas mostraron una fuerte correlación ($r=0.94$) con las utilidades del profesor de verdad fundamental, confirmando que el método recupera eficazmente representaciones semánticas significativas.
• Dependencia de la Estructura: Se encontró que el equilibrio óptimo entre exploración y explotación depende de la estructura del árbol de conceptos subyacente (por ejemplo, la razón de ramificación), lo que sugiere que las estrategias de búsqueda deben adaptarse a la topología específica del espacio del problema.

Significado y Reivindicaciones

El artículo afirma que CCTS aborda un desajuste fundamental en el descubrimiento de algoritmos asistido por LLM actual: los algoritmos de alta puntuación no necesariamente generan descendientes fuertes porque el fitness es un mal indicador de la evolucionabilidad en un espacio débilmente estructurado. Al desplazar la selección del fitness bruto hacia la evidencia semántica de mejora, CCTS permite que la búsqueda opere en un espacio de conceptos donde la distancia, la recombinación y la dirección de la búsqueda son significativas.

Los autores posicionan este trabajo como un avance metodológico hacia un descubrimiento de algoritmos más confiable y escalable. Enfatizan que, si bien los resultados actuales demuestran mejoras relativas sobre las líneas de base en benchmarks específicos, la contribución principal es la demostración de cómo las estructuras de conceptos semánticos explícitas y compatibles con humanos pueden hacer que el descubrimiento automatizado sea más transparente, controlable y eficiente. El trabajo sugiere que los sistemas futuros deberían centrarse en aprender y explotar estas jerarquías semánticas latentes en lugar de depender únicamente de señales de fitness de caja negra.