Resumen Técnico: Escalamiento del Verificador Agéntico para Programación Competitiva

Declaración del Problema

Aunque los Modelos de Lenguaje de Gran Escala (LLMs) han demostrado capacidades sólidas en la síntesis de programas, frecuentemente tienen dificultades para resolver problemas de programación competitiva correctamente en un solo intento. Una estrategia común para mejorar la precisión es el escalamiento en tiempo de inferencia (test-time scaling), donde se muestrean múltiples soluciones candidatas y un verificador selecciona la mejor.

Los métodos de verificación existentes enfrentan limitaciones significativas en el contexto de la programación competitiva:

1. Generación de Casos de Prueba Completos: Generar casos de prueba completos (entradas + salidas de verdad fundamental) suele ser tan difícil como resolver el problema original, lo que lo hace computacionalmente costoso e poco fiable.
2. Ejecución Solo con Entradas: Enfoques recientes generan únicamente entradas válidas y seleccionan soluciones basadas en el acuerdo de las salidas (votación). Sin embargo, estos métodos suelen depender del muestreo de entradas aleatorias.
3. Ineficiencia del Muestreo Aleatorio: El espacio de entradas válidas en la programación competitiva es vasto, pero solo una pequeña fracción es "discriminativa" (es decir, capaz de exponer diferencias de comportamiento entre soluciones correctas e incorrectas). Los experimentos preliminares del artículo demuestran que escalar el número de entradas aleatorias produce rendimientos decrecientes y no logra cerrar la brecha de rendimiento respecto a los casos de prueba de verdad fundamental.

Metodología: Verificador Agéntico

Los autores proponen el Verificador Agéntico, un agente basado en LLM diseñado para razonar activamente sobre los comportamientos de los programas y buscar entradas de prueba altamente discriminativas que expongan discrepancias entre las soluciones candidatas.

Mecanismo Central

En lugar del muestreo aleatorio ciego, el verificador participa en una interacción de múltiples turnos con un entorno de ejecución de código:

1. Formulación de la Tarea: Dado un problema $Q$ y un par de soluciones candidatas $(C_a, C_b)$, el objetivo del agente es generar un programa generador de entradas $G$ que produzca una entrada válida $x$ donde $Exec(C_a, x) \neq Exec(C_b, x)$.
2. Bucle de Interacción: El agente propone iterativamente entradas, ejecuta las soluciones candidatas, inspecciona la retroalimentación (errores de tiempo de ejecución, salidas) y refina sus hipótesis para descubrir contraejemplos.
3. Estrategia de Selección: En el momento de la inferencia, el verificador entrenado genera entradas de prueba dirigidas para pares de soluciones candidatas. Estas entradas se utilizan en una estrategia de votación basada en la ejecución para seleccionar la solución final.

Pipeline de Entrenamiento

El verificador se entrena mediante un pipeline escalable de tres etapas:

1. Síntesis de Datos a Gran Escala: Los autores construyen un conjunto de datos de problemas de programación competitiva con soluciones etiquetadas. Para los problemas que carecen de casos de prueba de verdad fundamental, sintetizan suites de pruebas de alta calidad utilizando un mecanismo de votación por mayoría basado en consenso a través de múltiples soluciones de referencia para garantizar la fiabilidad.
2. Ajuste Fino por Rechazo (Rejection Fine-Tuning): Utilizando un modelo profesor fuerte (Qwen3-235B), recolectan trayectorias exitosas de interacción de múltiples turnos donde el agente genera con éxito entradas que distinguen las soluciones. El modelo base se ajusta finamente sobre estas trayectorias de alta calidad, enmascarando los prompts iniciales y la retroalimentación para aprender patrones de interacción efectivos.
3. Aprendizaje por Refuerzo Agéntico (RL): El verificador se optimiza aún más utilizando GRPO (Optimización de Política Relativa de Grupo). La función de recompensa es dispersa y basada en resultados:
   • $+1$: Entrada válida que distingue las dos soluciones.
   • $0$: Entrada válida que no distingue (las soluciones coinciden).
   • $-1$: Entrada inválida o generador vacío.
     El currículo de entrenamiento prioriza los pares de "negativos difíciles" donde las entradas que distinguen son raras, fomentando que el agente aprenda comportamientos de generación dirigidos.

Contribuciones Clave

1. Análisis Empírico: El artículo demuestra empíricamente que la generación de entradas aleatorias es altamente ineficiente para la verificación basada únicamente en la ejecución de entradas, revelando una brecha de rendimiento sustancial en comparación con las entradas de prueba discriminativas.
2. Verificador Agéntico: Introducción de un agente que genera activamente entradas de prueba altamente discriminativas mediante la interacción de múltiples turnos, yendo más allá del muestreo estático o aleatorio.
3. Pipeline de Entrenamiento Escalable: Un nuevo pipeline que combina síntesis de datos, ajuste fino por rechazo y aprendizaje por refuerzo agéntico para entrenar al verificador.
4. Escalamiento en Tiempo de Inferencia: Demostración de que el método propuesto se beneficia continuamente del aumento de la computación en tiempo de inferencia, escalando efectivamente tanto con el número de soluciones candidatas como con el número de entradas generadas.

Resultados Experimentales

El enfoque fue evaluado en cinco benchmarks de programación competitiva (USACO, LiveCodeBench, OJBench, ICPC-Eval y un nuevo benchmark de CodeForces) utilizando dos modelos de política (Qwen3-30B y Qwen3-235B).

• Ganancias de Rendimiento: El Verificador Agéntico superó consistentemente a los fuertes baselines, incluyendo la generación de entradas aleatorias, la generación de casos de prueba por modelos (CodeT, CodeRM) y la selección basada en modelos de recompensa.
  • Logró ganancias absolutas de +10–15% en la precisión Best@k sobre los fuertes baselines basados en ejecución.
  • En el subconjunto "Hard" de OJBench, el verificador entrenado de 30B mejoró el rendimiento en un +34.1% sobre el baseline, superando significativamente a un modelo de 235B zero-shot.
• Comportamiento de Escalamiento: A diferencia de los baselines que mostraron una saturación temprana, el Verificador Agéntico exhibió un claro comportamiento de escalamiento en tiempo de inferencia, con un rendimiento que mejora de manera constante a medida que aumenta el número de entradas de prueba.
• Zero-Shot vs. Entrenado: Los LLMs zero-shot proporcionaron cierta mejora, pero el verificador entrenado específicamente para la tarea superó significativamente a ellos, incluso cuando el modelo entrenado era 7 veces más pequeño que su contraparte zero-shot.

Significado y Reivindicaciones

El artículo sostiene que la efectividad de la votación basada en la ejecución está determinada principalmente por la calidad discriminativa de las entradas de prueba, más que por su mera cantidad.

Más allá de mejorar la selección Best-of-N, los autores destacan una implicación más amplia: las suites de pruebas de los benchmarks son verificadores imperfectos. Las suites de pruebas fijas cubren solo una parte limitada del espacio de entradas válidas, lo que conduce a falsos positivos donde soluciones incorrectas pasan todas las pruebas del benchmark. El Verificador Agéntico puede exponer activamente estos fallos mediante el descubrimiento de contraejemplos dirigidos. Por lo tanto, los autores posicionan al verificador no meramente como una herramienta de reordenamiento, sino como un mecanismo complementario de verificación de corrección que puede expandir la cobertura de entradas y mitigar el ruido inducido por los benchmarks en la evaluación de código a gran escala.