Resumen Técnico: ALGOBENCH

Planteamiento del Problema

Los benchmarks actuales para la generación de código mediante modelos de lenguaje de gran tamaño (LLM), como HumanEval y LiveCodeBench, suelen arrojar tasas de éxito elevadas que no reflejan necesariamente capacidades genuinas de razonamiento algorítmico. Una limitación primordial es la contaminación de datos: los enunciados de problemas, editoriales y soluciones de referencia establecidos están ampliamente disponibles en los corpora de entrenamiento públicos. En consecuencia, los modelos pueden alcanzar puntuaciones altas mediante el recuerdo de patrones de solución memorizados en lugar de derivar algoritmos a partir de las restricciones. Aunque los benchmarks recientes intentan mitigar esto utilizando problemas más nuevos o difíciles (por ejemplo, LiveCodeBench, ProBench, HLCE), estos siguen siendo estáticos. Una vez publicados, sus enunciados de problemas y las soluciones generadas por modelos inevitablemente entran en los datos de entrenamiento, permitiendo que futuros modelos mejoren mediante la exposición en lugar de un razonamiento mejorado. Existe la necesidad de un benchmark que genere dinámicamente problemas donde memorizar la solución de origen sea insuficiente, obligando a los modelos a adaptar sus estrategias algorítmicas.

Metodología

Marco Central: ALGOBENCH

Los autores proponen ALGOBENCH, un marco para la construcción automática de problemas algorítmicos novedosos a partir de fuentes conocidas de programación competitiva. La filosofía central es la transformación por desplazamiento de restricciones: modificar un problema de origen de tal manera que el algoritmo de referencia original falle, requiriendo un nuevo enfoque algorítmico o una complejidad asintótica diferente.

1. Operadores de Transformación
El marco emplea diez operadores de transformación basados en reglas para generar variantes ($q'$) a partir de problemas de origen ($q$). Estos incluyen:

• Escalado de Restricciones (CS): Aumentar los límites de entrada (e.g., $N \le 2000 \to N \le 2 \times 10^5$).
• Estático-a-Dinámico (SD): Convertir problemas estáticos en dinámicos (e.g., añadir operaciones de actualización).
• Perturbación del Objetivo (OP): Cambiar la meta de optimización.
• Inyección de Trampa Greedy (GT): Introducir restricciones que invaliden las heurísticas voraces (greedy), requiriendo programación dinámica.
• Otros operadores incluyen Acoplamiento de Restricciones, Expansión de Casos Borde, Cambio de Requisito de Salida y transformaciones más amplias como el Envoltorio del Mundo Real (Real-World Wrapping) y Cambio de Estructura de Grafo.

2. Puertas de Calidad (Quality Gates)
Para asegurar la validez y prevenir la trivialidad, los problemas generados deben pasar cuatro puertas automatizadas:

• Puerta 1 (Rechazo de la Solución Antigua): La solución de referencia original ($a^*$) debe fallar en el nuevo problema (produciendo WA, TLE o MLE).
• Puerta 2 (Verificación de la Nueva Solución): Una nueva solución de referencia ($\hat{a}^*$) debe ser verificada contra un oráculo de fuerza bruta en entradas pequeñas.
• Puerta 3 (No Paráfrasis): El enunciado generado debe ser suficientemente distinto al de origen (TextSim $< \tau_{text}$).
• Puerta 4 (Certificación de Complejidad): La nueva solución debe satisfacer la complejidad de tiempo y espacio objetivo.

3. Verificador de Complejidad Determinista
Un verificador de tres capas evalúa las soluciones enviadas para distinguir entre corrección funcional y optimalidad algorítmica:

• Capa 1 (Análisis Estático de AST): Analiza el código para estimar la complejidad de tiempo/espacio basada en el anidamiento de bucles, recursión y estructuras de datos.
• Capa 2 (Verificación de Etiquetas de Algoritmo): Comprueba la evidencia estructural de los algoritmos esperados (e.g., propagación perezosa para árboles de segmento) y la ausencia de los prohibidos.
• Capa 3 (Escalado de Tiempo de Ejecución Calibrado): Ejecuta las soluciones en tamaños de entrada crecientes para ajustar un modelo de tiempo de ejecución $T(n) = cn^\alpha (\log n)^\gamma$. Las soluciones son penalizadas si el exponente ajustado excede el objetivo por más de 0.15.

Métricas de Evaluación

Más allá del estándar pass@k, ALGOBENCH introduce métricas conscientes de la complejidad:

• OPTT/OPTS: Tasas de envíos que son correctos y cumplen con la complejidad de tiempo/espacio objetivo.
• TRAPRATE: La fracción de envíos incorrectos que reutilizan estructuralmente el algoritmo de origen (indicando la "trampa de la solución antigua").
• GAPT (Brecha de Eficiencia): Mide la brecha entre el exponente de tiempo de ejecución ajustado y el exponente objetivo.
• CONSENS: Mide la caída de rendimiento a medida que aumenta la magnitud de las restricciones.
• $\Delta_{gen}$: La caída de rendimiento desde los problemas de origen hacia las variantes generadas.

Contribuciones Clave

1. Marco de Trabajo: Introducción de ALGOBENCH, un pipeline automático para generar problemas trazables pero algorítmicamente distintos.
2. Transformación y Validación: Diseño de diez operadores de transformación y un sistema de control de calidad de cuatro puertas que asegura que los problemas generados rechacen las soluciones antiguas y requieran una nueva complejidad.
3. Dataset de Benchmark: Construcción de un benchmark con 598 variantes aceptadas (420 utilizadas en los experimentos principales) derivadas de 300 problemas de origen (Codeforces, AtCoder, Kattis, LeetCode Hard), completas con metadatos, soluciones de referencia y oráculos de fuerza bruta.
4. Métricas: Propuesta de métricas (OPTT, OPTS, TRAPRATE, GAPT, CONSENS) que evalúan la idoneidad asintótica, no solo la corrección funcional.
5. Hallazgos Empíricos: Evaluación de siete LLMs a través de seis estrategias de prompting, demostrando que el rendimiento se degrada significativamente en las variantes generadas y que muchas soluciones "correctas" fallan en los requisitos de complejidad.

Resultados Experimentales

Caída de Rendimiento y Adaptación

• Brecha de Generalización: Los modelos muestran una fuerte disminución en su rendimiento al pasar de los problemas de origen a las variantes de ALGOBENCH. Los modelos antiguos cayeron de un promedio de 85.1% de pass@1 en las fuentes a un 53.6% en las variantes. Incluso los modelos de frontera más recientes (GPT-5.4, Claude Opus 4.5) cayeron un 33.3%.
• Desajuste de Complejidad: Existe una brecha significativa entre pass@k y OPTT. Por ejemplo, GPT-4o logró un 72.7% de pass@5 pero solo un 63.6% de OPTT, lo que indica que muchas soluciones aprobadas utilizaron algoritmos subóptimos.
• Riesgos de Recuperación: La Generación Aumentada por Recuperación (RAG) utilizando los problemas de origen como contexto a menudo aumentó el TRAPRATE. Para Gemini 2.5 Flash, el RAG aumentó la tasa de trampa del 3.6% al 30.0%, sugiriendo que la recuperación ancla a los modelos a la solución original (ahora inválida).

Análisis de Errores

El análisis de 400 envíos fallidos reveló que los fallos son predominantemente algorítmicos en lugar de de nivel de implementación:

• Trampa de la Solución Antigua (42.3%): El modelo implementó el algoritmo de origen, pasando los ejemplos públicos pero fallando en las pruebas de trampa ocultas.
• Demasiado Lento (21.8%): El modelo identificó el enfoque correcto pero no logró las optimizaciones necesarias (e.g., fallar al cambiar de $O(N^2)$ a $O(N \log N)$).
• Errores de Implementación: Representaron solo el 9.0% de los fallos.

Sensibilidad y Contaminación

• Sensibilidad a las Restricciones: El rendimiento se degradó bruscamente a medida que aumentaban los límites de entrada (e.g., $N=10K \to 50K$), precisamente donde las soluciones cuadráticas agotan el tiempo.
• Efecto de Contaminación: Los modelos funcionaron significativamente mejor en los problemas de origen más antiguos (2020) en comparación con los más nuevos (2024), lo que sugiere memorización. Sin embargo, esta brecha se redujo para las variantes de ALGOBENCH, que se mantuvieron consistentemente difíciles independientemente del año de publicación del problema de origen.

Significado y Reivindicaciones

El artículo afirma que ALGOBENCH evalúa una capacidad distinta de los benchmarks de código estándar: la capacidad de adaptar el razonamiento algorítmico a restricciones novedosas en lugar de depender de plantillas memorizadas.

• Más allá de la Corrección Funcional: El benchmark demuestra que las altas tasas de éxito en conjuntos de datos estáticos no garantizan la idoneidad asintótica. Muchos modelos producen soluciones que son funcionalmente correctas pero algorítmicamente ineficientes.
• Robustez frente a la Memorización: Al generar automáticamente problemas donde la solución de origen falla, ALGOBNECH mitiga el riesgo de contaminación por datos de entrenamiento, proporcionando una medida más fiable del verdadero razonamiento algorítmico.
• Valor Diagnóstico: El marco identifica modos de fallo específicos (e.g., la incapacidad de transicionar de Greedy a DP, o fallar al manejar actualizaciones dinámicas) que quedan ocultos en los benchmarks tradicionales.

Los autores concluyen que los LLM actuales luchan cuando las plantillas familiares son insuficientes, y que el progreso futuro en el razonamiento algorítmico requiere benchmarks que exijan una adaptación genuina en lugar de un simple emparejamiento de patrones.