Resumen Técnico: Descubrimiento de LLM Consciente del Presupuesto mediante la Utilidad de Frontera Calibrada por Costo

Formulación del Problema

Los modelos de lenguaje extensos (LLM) se emplean cada vez más para el descubrimiento científico y algorítmico mediante la búsqueda en tiempo de inferencia, donde las soluciones candidatas se generan, evalúan y refinan secuencialmente. En dominios como la optimización matemática, el diseño de algoritmos y el descubrimiento de programas ejecutables, los evaluadores deterministas proporcionan señales de calidad repetibles. Sin embargo, los controladores de descubrimiento adaptativos existentes suelen asignar crédito a las acciones de búsqueda basándose únicamente en el progreso del puntaje, ignorando la heterogeneidad de los costos de las acciones.

Bajo la tarificación de API basada en tokens, diferentes acciones de búsqueda incurren en costos muy distintos. Un refinamiento corto puede costar una generación de referencia, mientras que una llamada de guía de contexto largo o un reintento de código inválido puede costar seis o más. Cuando un controlador acredita una acción de alto costo y una de bajo costo por igual porque ambas producen la misma mejora en el puntaje, no tiene en cuenta el costo de oportunidad del presupuesto restante. El artículo formaliza esto como un problema de asignación a nivel de población sobre un espacio discreto de candidatos ejecutables, donde el horizonte de búsqueda efectivo está definido por un presupuesto de tokens acumulado y realizado, en lugar de un número fijo de iteraciones.

Los autores demuestvan (Proposición 1) que en instancias con costos de acción heterogéneos, un controlador "ciego al costo" —cuyo de distribución de acciones depende solo del historial de puntajes y no de los costos realizados— puede alcanzar solo una fracción evanescente del objetivo presupuestado óptimo a medida que aumentan el número de fronteras de búsqueda y las disparidades de costo.

Metodología: CostAda

Para abordar esta brecha, los autores introducen CostAda, un controlador adaptativo calibrado por costo diseñado para el descubrimiento con LLM bajo presupuestos explícitos de tokens en el lado de la búsqueda. CostAda reemplaza el crédito basado solo en el progreso por la utilidad de frontera calibrada por costo, la cual integra el progreso de la frontera local, la mejora global respecto al mejor hasta ahora, el costo de la acción realizada y el presupuesto restante.

El mecanismo central opera a través de tres controles acoplados:

1. Utilidad de Frontera Calibrada por Costo:
   La utilidad $u_t^{(k)}$ para una frontera $k$ en la iteración $t$ se define como:
   $$u_t^{(k)} = \frac{\lambda_t g_t + (1 - \lambda_t) \delta_t^{(k)}}{d_t}$$
   Donde:

   • $g_t$ es la ganancia global (mejora sobre el mejor global hasta ahora).
   • $\delta_t^{(k)}$ es la ganancia local (mejora sobre el archivo local de la frontera).
   • $\lambda_t = 1 - \rho_t$ es el peso global, condicionado a la razón de presupuesto restante $\rho_t$. A medida que el presupuesto se agota, el controlador cambia el enfoque del desarrollo local hacia la mejora global.
   • $d_t = 1 + \lambda_t^c \phi_t$ es un divisor de costo basado en el costo de paso realizado normalizado. Esto asegura que ganancias iguales de acciones costosas reciban menos crédito que las de acciones económicas.

2. Decisiones de Control Conscientes del Presupuesto:

   • Intensidad de Exploración Local: La amplitud de muestreo alrededor de una frontera se ajusta según su utilidad suavizada. Una utilidad alta conduce a un refinamiento de baja intensidad; una utilidad baja activa una exploración más amplia. Crucialmente, la razón de presupuesto restante $\rho_t$ suprime la exploración costosa a medida que el presupuesto se acerca a su agotamiento.
   • Asignación de Fronteras: El controlador asigna el presupuesto futuro a las fronteras basándose en la ganancia global por costo realizado ($r_t^{(k)} = g_t / d_t$). Las fronteras que solo mejoran frente a archivos locales débiles no reciben crédito de asignación. Una regla de límite superior de confianza (UCB) equilibra la explotación de fronteras de alto rendimiento con la exploración de aquellas submuestreadas, regulada por el presupuesto restante.
   • Intervención de Táctica Presupuestada: Las guías de nivel superior (por ejemplo, llamadas de "guía" o "táctica") se compran solo cuando se cumplen ciertos predicados de evidencia: (1) el presupuesto restante puede costear la guía más una reserva para pruebas; (2) hay una ausencia sostenida de progreso global (estancamiento) o un gasto acumulado de bajo rendimiento; y (3) no hay una ventana de consolidación activa. Esto evita intervenciones costosas cerca del horizonte a menos que sean estrictamente necesarias.

Contribuciones Clave

1. Formulación del Problema y Límite Teórico: El artículo formaliza el descubrimiento con LLM bajo presupuestos explícitos de tokens en el lado de la búsqueda y demuestra que las estrategias de crédito ciegas al costo pierden el objetivo presupuestado en entornos de costos heterogéneos.
2. Utilidad de Frontera Calibrada por Costo: Los autores introducen un principio de crédito que condiciona el progreso al costo de la acción realizada y al presupuesto restante, asegurando que el costo de oportunidad de cada acción sea explícito.
3. Controlador CostAda: Una instanciación de este principio que coordina la exploración local con control de presupuesto, la asignación de fronteras consciente del costo y la intervención de táctica presupuestada.
4. Validación Empírica: Experimentos extensos que demuestran que CostAda logra una eficiencia de presupuesto y una calidad de solución final superiores en comparación con las líneas base de vanguardia.

Resultados Experimentales

Los autores evaluaron CostAda contra AdaEvolve (una línea base consciente del progreso) y EvoX (un controlador de evolución de estrategia) a través de ocho bancos de pruebas (que abarcan empaquetamiento geométrico, geometría extremal, combinatoria aditiva y optimización de programas ejecutables) utilizando dos modelos base: GLM-5 y GPT-5.4.

• Eficiencia: CostAda alcanza la calidad del presupuesto total de la línea base más fuerte con al menos la mitad del presupuesto en 12 de 16 pares de banco de pruebas–modelo base.
• Calidad Final: A través de ambos modelos base, CostAda logra la media de calidad final más alta en los ocho bancos de pruebas.
• Trayectoria del Presupuesto: Al llegar a un cuarto del presupuesto, el puntaje promedio normalizado de CostAda supera el promedio del presupuesto total de la línea base más fuerte. Alcanza el Área Bajo la Curva (AUC) normalizada más alta en 15 de 16 pares de banco de pruebas–modelo base.
• Estabilidad: CostAda demuestra una menor varianza en los resultados en comparación con las líneas base, particularmente en bancos de pruebas como Circle Packing Rect bajo GLM-5.

Significado y Reivindicaciones

El artículo afirma que CostAda cambia fundamentalmente la forma en que se gestionan los recursos de búsqueda en el descubrimiento impulsado por LLM. Al tratar el costo realizado y el presupuesto restante como entradas de control activas en lugar de variables de contabilidad post-hoc o simples reglas de parada, CostAda alinea la estrategia de búsqueda con la realidad económica de la tarificación basada en tokens.

Los autores sostienen que su enfoque preserva la calidad de la solución final mientras mejora significativamente la eficiencia del presupuesto. Los resultados sugieren que la calibración de costos es esencial para escalar el descubrimiento con LLM, ya que ignorar la heterogeneidad de costos conduce a una asignación de recursos subóptima que no puede recuperarse simplemente suavizando las señales de progreso. El trabajo demuestra que un controlador puede navegar eficazmente el compromiso entre exploración y explotación cuando el "costo" de una acción es tan variable como la "ganancia" que produce.