Vals.ai: 10 agentes IA crean C-HD, más rápido que Dijkstra

¿Qué es C-HD y en qué mejora a Dijkstra?

En 15 horas y 733 mensajes en una pizarra compartida, 10 agentes de Claude Opus 5.5 desarrollaron C-HD, un nuevo algoritmo para calcular caminos más cortos en grafos dirigidos que mejora la cota asintótica del clásico algoritmo de Dijkstra en un régimen específico de densidad. El resultado, anunciado por Vals.ai y verificado formalmente en Lean (un asistente de demostración matemática que comprueba cada paso de la prueba), se suma a una cadena de avances firmados por sistemas de IA en septiembre de 2026.

El problema de los caminos más cortos es uno de los más estudiados en computación: dado un grafo con vértices y aristas ponderadas, encontrar la ruta de menor coste desde un origen a cualquier otro destino. El algoritmo de Dijkstra, publicado en 1956, lo resuelve en O(m + n log n) usando colas de prioridad como el Fibonacci heap (una estructura de datos que mantiene accesible de forma eficiente el vértice de menor distancia pendiente). En 2025 y 2026 aparecieron mejoras marginales a esa cota. C-HD entra con un límite superior más ajustado en un rango concreto:

O(n + m + m · log(2 + m/(n+1)) + m^(1/3) · (n·log(n+2))^(2/3))

🤖 La IA no es solo para leer sobre ella

En la comunidad la aplicamos: automatización, agentes IA y herramientas reales para emprender, no solo para informarte.

👥 Aplicarla en la comunidad

Cuando el grafo tiene aproximadamente m ≈ n^(4/3) aristas —una densidad típica de redes reales como la web o grafos sociales—, esa expresión se simplifica a Õ(n^(4/3)), frente a Õ(n^(4/3) log n) de Dijkstra. La diferencia es polilogarítmica: al duplicar el tamaño del grafo, la ventaja se multiplica por una potencia de log n. En palabras del propio artículo, C-HD hace menos trabajo total en grafos suficientemente grandes y densos, aunque no conoce de antemano el orden en que visitará los vértices.

¿Cómo funciona C-HD sin entrar en la prueba formal?

El algoritmo combina búsquedas acotadas por prioridades con un manejo cuidadoso de aristas improductivas. La idea intuitiva, según Vals.ai:

Comienza en el origen y expande un frente de vértices.
Ejecuta búsquedas locales acotadas siguiendo aristas salientes.
Los vértices recién descubiertos cuentan hacia el límite de búsqueda, incluso como hojas no exploradas.
Usa los árboles de búsqueda resultantes como pivotes para organizar el trabajo recursivo.

Para entradas fuera del rango certificado de densidad, el equipo añadió Bellman-Ford como respaldo. Bellman-Ford es un algoritmo clásico distinto a Dijkstra, con peor cota asintótica pero más robusto en grafos pequeños o dispersos.

Dos matices importantes: las constantes en la construcción formal son enormes, y Vals.ai aclara que no se midió el rendimiento en grafos reales grandes. Es un avance teórico, no un speedup práctico demostrado.

¿Por qué importan más los 10 agentes que el algoritmo en sí?

Lo más relevante para founders y equipos técnicos no es la cota exacta, sino cómo se creó. Vals.ai lanzó 10 agentes de Claude Opus 5.5 con acceso a una pizarra de mensajes compartida y un prompt largo y específico: mejorar sustancialmente la cota teórica para caminos exactos en grafos dirigidos con pesos reales no negativos, respaldado por una prueba completa en Lean.

Los agentes tenían roles iniciales pero podían reorganizarse, compartir descubrimientos, retarse mutuamente y reasignar esfuerzo según avanzaba la investigación. En 15 horas tenían el algoritmo, la prueba y el veredicto del kernel de Lean. El paquete completo (código Lean, paper informal y registros de verificación) está disponible en github.com/spicylemonade/c-hd-proof.

Para un founder, la cifra relevante es otra: el costo de producir investigación matemática con rigor formal está cayendo a escala de producto interno. Una demostración así solía requerir meses de un equipo especializado en teoría de grafos y verificación formal; ahora, una pizarra compartida y un modelo frontier.

¿Qué relación tiene este avance con el resultado de OpenAI en Navier-Stokes?

Vals.ai cita explícitamente el caso de OpenAI como inspiración. El 8 de septiembre de 2026, OpenAI anunció que unos 10.000 agentes concurrentes resolvieron un caso de las ecuaciones de Navier-Stokes —uno de los siete Problemas del Milenio del Clay Mathematics Institute— en aproximadamente 88 horas, seguidas de otras 17 horas para formalizar y verificar el resultado en Lean con GPT-6 Astra. En total, según OpenAI, los agentes intercambiaron 4,9 millones de mensajes y generaron unos 300.000 millones de tokens de salida entre todos los problemas intentados, según reportó Unite.AI.

La diferencia de escala es de tres órdenes de magnitud (10 agentes vs. 10.000), pero el patrón es el mismo: pizarra compartida, roles intercambiables, verificación formal al final. El matemático Terence Tao advirtió días antes del anuncio de OpenAI sobre un riesgo que aplican a ambos casos: cuando sistemas autónomos generan demostraciones a esa escala, el proceso iterativo de descubrimiento —los callejones sin salida, los intermedios creativos— puede quedar fuera de la vista pública. Se publica el resultado, pero el aprendizaje que produjo los insights se pierde.

The Journal, que cubrió el anuncio, lo resumió así: «esto no fue un chatbot sentándose a tener un momento newtoniano bajo el manzano. Pareció más una organización computacional de investigación».

¿Qué significa esto para tu startup?

Tres lecturas prácticas para founders que no se dedican a la investigación algorítmica pura:

La verificación formal de tu código crítico ya no es ciencia ficción. Las mismas herramientas que usaron Vals.ai y OpenAI —Lean, agentes con acceso a código y documentación— son aplicables a invariantes de seguridad en contratos inteligentes, a kernels de sistemas embebidos o a la lógica de liquidación en fintech. Tu próximo auditor de seguridad podría ser un enjambre de agentes.
El talento matemático caro se vuelve opcional para problemas puntuales. No necesitás contratar un equipo permanente de PhDs en teoría de grafos para explorar una cota teórica: podés lanzar 10 agentes en una pizarra por 15 horas y obtener un resultado revisable. Para startups que enfrentan problemas de optimización combinatoria o NP-duros, el costo de explorar estos caminos baja drásticamente.
La velocidad de iteración sube, pero perdés aprendizaje organizacional. Si los agentes hacen todo el camino y solo entregan la respuesta final, tu equipo no internaliza los porqués. Diseñá los proyectos para que los humanos revisen los pasos intermedios, no solo el resultado.

¿Qué puedes hacer esta semana en tu empresa?

Mapea qué partes de tu producto admiten verificación formal barata. Si trabajás con reglas de negocio críticas (precios, antifraude, liquidación), un agente con acceso a Lean puede auditar invariantes que hoy revisás manualmente. Empezá con un caso piloto pequeño, no con todo el sistema.
Monta tu propio experimento con agentes en pizarra. No necesitás una herramienta sofisticada: una pizarra de mensajes compartida basta para que varios agentes colaboren. Lanzá 3-5 agentes de Claude o GPT-6 contra un problema concreto de tu backlog de ingeniería y medí cuánto tardan. Vals.ai lo hizo con 10; podés empezar con menos.
Pide a tus agentes que documenten los caminos fallidos. Vals.ai les pidió explícitamente registrar failed approaches para que otros no repitieran errores. Tao tiene razón sobre lo que se pierde con sistemas totalmente autónomos: el proceso. Forzá a tus agentes a dejar registro de los intermedios, no solo de la respuesta.