Resumen Técnico: Más Allá de la Búsqueda en Tiempo de Inferencia

1. Enunciado del Problema

Los Modelos de Lenguaje Grandes (LLM) actuales suelen tratar la optimización combinatoria como un procedimiento en tiempo de inferencia, resolviendo cada instancia del problema por separado mediante muestreo, búsqueda o prompts repetidos. Este paradigma incurre en un "costo marginal" de razonamiento para cada nueva consulta. Los autores investigan si el Aprendizaje por Refuerzo (RL) puede trasladar este costo de razonamiento a los pesos del modelo, permitiendo la síntesis de un solver reutilizable para toda una familia de problemas en lugar de generar soluciones por instancia.

El estudio se centra en la Selección de Dependencias Sinérgicas (SDS), una variante controlada y fuertemente NP-dura del Problema de la Mochila Cuadrática. SDS está diseñada como un paisaje de optimización "engañoso" donde:

• Las señales locales contradicen la optimalidad global: Los términos de interacción cuadrática dominan los pesos lineales, provocando que las heurísticas voraces fallen.
• Restricciones estrictas de factibilidad: Las soluciones deben satisfacer límites de cardinalidad, precedencia, exclusión mutua y grupos.
• Recuperación de plantillas vs. operacionalización: Aunque los modelos base a menudo pueden recuperar la sintaxis de solvers apropiados (por ejemplo, Recocido Simulado), frecuentemente fallan al implementar la lógica ejecutable correctamente (por ejemplo, aplicando incorrectamente las reglas de aceptación).

El artículo aborda tres preguntas de investigación centrales:

1. Muro de Competencia: ¿Puede un muestreo extenso en tiempo de prueba (Best-of-N) recuperar el rendimiento de una política entrenada con RL en paisajes engañosos, o el modelo base alcanza un techo?
2. Reparación Semántica: Cuando el RL tiene éxito, ¿simplemente afina la frecuencia de soluciones correctas, o repara la lógica algorítmica ejecutable que el muestreo ingenuo no puede recuperar?
3. Síntesis de Solver Amortizada: ¿Puede la optimización en tiempo de entrenamiento destilar el razonamiento en un programa ligero y reutilizable que supere la búsqueda repetida por instancia?

2. Metodología

Los autores proponen Hero, una política ajustada utilizando Optimización de Política Relativa por Grupos (GRPO) sobre el modelo Qwen2.5-Coder-14B-Instruct. El enfoque es intencionalmente minimalista, eliminando estabilizadores comunes (por ejemplo, penalizaciones KL, anclaje a oráculo) para aislar los efectos de una receta de factibilidad primero.

Componentes Clave:

• Prompt de Sistema Estructurado: El prompt impone un bucle de razonamiento "Descomponer-Hipotetizar-Criticar". Advierte explícitamente al modelo contra las heurísticas voraces y fomenta el diseño de estrategias de búsqueda que equilibren la exploración y la explotación.
• Diseño Jerárquico de Recompensas: Una recompensa compuesta $r(o)$ prioriza el cumplimiento estructural sobre la optimalidad bruta:
  • Formato y Ejecución ($R_{exec}$): Asegura sintaxis Python válida, cumplimiento de esquemas y estructura de teoría de grafos. Crucialmente, incluye una penalización anti-ordenamiento perezoso para suprimir la tendencia del modelo preentrenado a usar heurísticas lineales voraces que ignoran las interacciones cuadráticas.
  • Optimalidad Puenteada por Factibilidad ($R_{nom}$): La señal de optimización principal está estrictamente condicionada. Si una solución viola cualquier restricción dura (cardinalidad, precedencia, etc.), la recompensa es cero, independientemente de la puntuación del objetivo. Esto obliga a la política a priorizar la satisfacción de restricciones antes de optimizar el objetivo.
• Régimen de Entrenamiento: El modelo se entrena durante 90 pasos globales en 12 GPUs NVIDIA GH200, observando solo ~4.5% de una época completa a nivel de prompt, pero generando 23,040 trazas de razonamiento.

3. Contribuciones Clave

Las contribuciones del artículo son empíricas y mecánicas, más que algorítmicas:

1. Identificación de un Muro de Competencia: Bajo prompts idénticos, el muestreo Best-of-64 del modelo base se satura en una brecha del 28.7% respecto al Solver Virtual Óptimo (VBS). A pesar de recuperar plantillas de solvers superficialmente apropiadas (por ejemplo, el 21.9% de los códigos base únicos se asemejan al Recocido Simulado), el modelo base falla al operacionalizarlos correctamente.
2. Demostración de Reparación Semántica: La política entrenada con RL (Hero) converge a una plantilla de Recocido Simulado consciente de restricciones en el 99.8% de las salidas factibles. Repara el "Error del Mejor Global" prevalente en las muestras del modelo base, donde la lógica de aceptación compara incorrectamente a los vecinos con el mejor global en ejecución en lugar del estado actual. Esta corrección permite un comportamiento de recocido real.
3. Validación de la Síntesis de Solver Amortizada:
   • Rendimiento: Hero logra una brecha del 5.0% respecto al VBS, superando significativamente al modelo base y a heurísticas clásicas como la Búsqueda Local (brecha del 10.0%).
   • Eficiencia: Hero es 91 veces más barato en costo de ejecución/búsqueda post-generación en comparación con el costo acumulativo de la evaluación Best-of-64.
   • Reutilización: Una evaluación de "compilar una vez" muestra que un solver único congelado generado por semilla permanece altamente competitivo (tasa de aprobación del 97.87%, brecha del 4.34%) cuando se reutiliza sin cambios en todo el conjunto de pruebas, demostrando que el modelo sintetiza un artefacto reutilizable en lugar de un generador por instancia.

4. Resultados y Ablaciones

• Rendimiento Principal: Hero logra una tasa de aprobación del 97.8% y una brecha del 5.0% respecto al VBS. Supera la línea base ShinkaEvolve actualizada (que utiliza modelos propietarios potentes en el momento del despliegue) y se acerca al rendimiento de CP-SAT (brecha del 1.0%) mientras es 6.3 veces más rápido en ejecución.
• Estudios de Ablación:
  • Andamiaje Estructural: Eliminar la recompensa estructural (ordenamiento anti-perezoso y verificaciones de estructura de grafos) hace colapsar el rendimiento a una brecha del 34.7%, ya que el modelo vuelve a heurísticas voraces frágiles.
  • Puerta de Factibilidad: Reemplazar la puerta de factibilidad dura con una penalización suave degrada significativamente el rendimiento (tasa de aprobación del 57.4% frente al 97.8%), confirmando que la puerta dura es necesaria para prevenir el colapso de modos hacia soluciones inválidas.
  • Oráculo/Diversidad: Agregar anclaje a oráculo o penalizaciones de diversidad degrada el rendimiento, sugiriendo que la retroalimentación dispersa y basada primero en la factibilidad es más efectiva que la conformación densa de resultados en este dominio.
• Generalización:
  • Sin Olvido Catastrófico: El modelo mantiene capacidades generales de codificación (HumanEval Pass@1: 80.9% frente a 82.3% del Base).
  • Transversal de Dominios: Aplicar la misma receta a la Programación de Tareas en Taller (JSSP) produce resultados positivos (tasa de aprobación del 99.3%, brecha del 6.12%), aunque los autores señalan que esto es evidencia más estrecha de transferencia en lugar de prueba de robustitud agnóstica al dominio.

5. Significado y Afirmaciones

El artículo afirma demostrar que el RL puede mover un LLM de código de un régimen de búsqueda por instancia a la síntesis de solver reutilizable. El significado radica en el hallazgo de que el RL actúa no meramente como un "afinador de distribución" (mejorando la eficiencia de encontrar soluciones existentes), sino como un compilador funcional que repara la lógica ejecutable (por ejemplo, corrigiendo la regla de aceptación de Metropolis) que el muestreo ingenuo no puede recuperar de manera fiable.

Los autores enfatizan que este éxito depende de un andamiaje disciplinado y basado primero en la factibilidad en lugar de una receta universal. El método depende de decisiones de diseño específicas, como la puerta de factibilidad dura y las penalizaciones estructurales, y es sensible a la normalización de recompensas. El trabajo sugiere que, para paisajes de optimización complejos y engañosos, el "razonamiento" requerido para construir un solver puede destilarse en los pesos del modelo, creando un artefacto desplegable que es significativamente más eficiente que la búsqueda repetida en tiempo de inferencia.