Resumen Técnico: Computación Empírica: Prompting frente a Programación

Planteamiento del Problema

El artículo identifica un cambio de paradigma en la resolución de problemas computacionales: el paso de la programación (especificación de algoritmos y estructuras de datos precisas) al prompting (provisión de descripciones informales en lenguaje natural a Grandes Modelos de Lenguaje o agentes). Mientras que la computación tradicional se basa en procedimientos deterministas con corrección verificable y límites de complejidad bien definidos (por ejemplo, $O(n \log n)$ para ordenamiento), la "computación empírica" se basa en el muestreo de salidas de una distribución de probabilidad.

El problema central es que las capacidades y los límites de esta nueva forma de computación no pueden entenderse dentro del marco racionalista clásico de la informática. Específicamente:

1. Falta de Determinismo: Las salidas no se generan procedimentalmente, sino que son el resultado "empíricamente más probable", lo que las hace susceptibles a alucinaciones y errores que no pueden localizarse ni repararse mediante la depuración tradicional.
2. Ambigüedad en la Entrada: A diferencia de la programación, que requiere contratos formales (tipos, formatos), el prompting acepta entradas informales donde la interpretación depende del contexto y de la distribución de entrenamiento del modelo.
3. Complejidad Poco Clara: El comportamiento del tiempo de ejecución parece estar desacoplado de la complejidad computacional clásica, correlacionándose en su lugar con la tokenización y el comportamiento de inferencia del modelo.
4. Brecha de Verificación: Las técnicas de ingeniería de software (SE) existentes (análisis estático, verificación formal) no están equipadas para analizar sistemas donde no existe un programa explícito que verificar.

Metodología

Los autores realizaron experimentos preliminares para caracterizar la eficiencia y la corrección de la computación empírica en cinco problemas computacionales clásicos:

1. Ordenamiento (Sorting): Orden ascendente de números aleatorios.
2. Búsqueda (Searching): Encontrar un índice en listas ordenadas y desordenadas.
3. Subcadena Palindrómica más Larga (Longest Palindromic Substring): Encontrar la secuencia palindrómica más larga en una cadena.
4. Problema de la Suma de Subconjuntos (Subset Sum Problem - SSP): Encontrar un subconjunto de números que sumen un valor objetivo.

Configuración Experimental:

• Modelo: Los experimentos utilizaron el modelo de pesos abiertos gemma-4-26b-a4b ejecutado localmente en un MacBook Pro (M5 Pro, 48GB RAM) para eliminar la latencia de red.
• Configuraciones: Se probaron tres modos:
  • Default (Predeterminado): Temperatura = 1.0.
  • Deterministic (Determinista): Temperatura = 0.0.
  • Thinking (Pensamiento): Modo de razonamiento habilitado.
• Métricas:
  • Eficiencia: Tiempo hasta la solución y tiempo hasta la primera solución correcta.
  • Corrección: Proporción de ensayos que devuelven la respuesta matemáticamente correcta.
• Variables: Tamaño de entrada ($n$), precisión de números y representación lingüística (dígitos vs. palabras en varios idiomas: inglés, alemán, coreano, japonés, etc.).
• Verdad Fundamental (Ground Truth): Para problemas no triviales (Substring, SSP), se generaron programas simples en Python con las respuestas correctas para la validación.

Resultados Clave

1. Eficiencia vs. Complejidad Clásica

Contrario a la teoría clásica, el tiempo de ejecución de la computación empírica no sigue estrictamente la complejidad algorítmica del problema (por ejemplo, $O(n)$ vs. $O(n \log n)$).

• Escalado Lineal: Para el ordenamiento, la búsqueda y el SSP, el tiempo hasta la solución aumentó linealmente con el tamaño de la entrada ($O(n)$) en todos los modos. Los autores atribuyen esto al incremento lineal de los tokens de entrada/salida en lugar de la lógica computacional.
• Dependencia de Tokens: El tiempo tomado para incrementar un número fue comparable a predecir texto plano a partir de un hash SHA-512, lo que sugiere que el tiempo de ejecución está impulsado por la tokenización y la mecánica de inferencia, más que por la dificultad del problema.
• Costo del Modo "Thinking": Habilitar el modo de "pensamiento" (razonamiento) aumentó significamente el tiempo de ejecución (por ejemplo, hasta 275s para ordenar 150 elementos) pero mantuvo una alta corrección.

2. Corrección y Tamaño de Entrada

• Sensibilidad al Tamaño: En los modos Default y Deterministic, la corrección se degradó rápidamente a medida que aumentaba el tamaño de la entrada.
  • Para ordenar 50 enteros, la corrección cayó a ~50% (probabilidad de lanzar una moneda).
  • Para ordenar 150 enteros, la corrección cayó a ~58% (a pesar del aumento de tiempo lineal).
  • Para el problema de la Suma de Subconjuntos, la corrección se acercó a cero para listas de longitud 10.
  • Para el problema de la Subcadena, la corrección cayó a casi cero para cadenas de longitud 5.
• Resiliencia del Modo "Thinking": Cuando se habilitaron las capacidades de razonamiento, la corrección se mantuvo alta (>90%), incluso para entradas más grandes, aunque dentro de los límites de tokens/tiempo.

3. Impacto de la Representación en Lenguaje Natural

El estudio investigó cómo el lenguaje utilizado para representar los números afecta la corrección.

• Sesgo de Representación de Datos: La corrección depende fuertmente de la representación del lenguaje en los datos de entrenamiento del modelo.
• Alta vs. Baja Representación: El ordenamiento de números escritos en inglés (bien representado) arrojó una corrección >95% para un tamaño de 20. En contraste, ordenar números escritos en alemán (subrepresentado) arrojó <1% de corrección para el mismo tamaño.
• Conclusión: La computación empírica no es agnóstica al lenguaje; está sesgada hacia los lenguajes y formatos prevalentes en el corpus de entrenamiento.

4. Características de los Errores

A diferencia de los programas tradicionales donde los fallos pueden localizarse en líneas específicas de código, los errores en la computación empírica son no deterministas. El LLM podría:

• Sumar números que no están presentes en la entrada.
• Eliminar números presentes en la entrada.
• Duplicar números.
• No ordenar la lista completa.
• Truncar entradas grandes.

Contribuciones Clave

1. Definición de Computación Empírica: El artículo introduce formalmente la "computación empírica" como un campo distinto donde las soluciones se generan mediante prompting y muestreo en lugar de ejecución procedimental.
2. Caracterización Empírica: Proporciona la primera medición sistemática de la eficiencia y la corrección de los LLM resolviendo problemas algorítmicos clásicos, revelando que el tiempo de ejecución se correlaciona con la tokenización en lugar de la complejidad algorítmica.
3. Identificación de Límites: El estudio demuestra que sin modos de razonamiento, la computación empírica no escala de manera confiable con el tamaño de la entrada y es altamente sensible a la representación lingüística de las entradas.
4. Llamado a Nuevos Fundamentos de SE: Los autores argumentan que la comunidad de ingeniería de software (SE) debe desarrollar nuevas herramientas para el "análisis de programas empíricos" (razonamiento estadístico, contrafáctico o causal) para analizar, estimar y predecir la corrección de estos sistemas.

Significado y Visión

El artículo plantea que la comunidad de ingeniería de software no puede confiar en los marcos racionalistas clásicos o en las herramientas de análisis de programas existentes para garantizar la confiabilidad de la computación impulsada por IA. A medida que los LLM y los agentes se vuelven integrales para resolver problemas computacionales, el campo debe evolucionar para abordar:

• Cómo analizar la corrección en ausencia de un programa formal.
• Cómo definir y probar los límites de la computación empírica.
• Cómo mejorar la corrección para instancias de problemas específicos sin introducir regresiones.

Los autores presentan esto como un área de investigación oportuna y rica, instando al desarrollo de técnicas de "análisis de programas empíricos" para cerrar la brecha entre la naturaleza probabilística de los LLM y las exigencias rigurosas de la ingeniería de software. El artículo no pretende resolver estos problemas, sino establecer el campo y resaltar la urgente necesidad de nuevos fundamentos teóricos y prácticos.