🤖 machine learning

The Complexity of Verifying Feedforward Neural Networks in Quantised Settings

Este artículo establece el panorama de la complejidad computacional para la verificación de redes neuronales feedforward en entornos cuantizados, demostrando que la verificación sigue siendo NP-completa para redes con precisión aritmética fija bajo especificaciones tanto lineales como de vectores de bits, al tiempo que proporciona nuevos límites superiores para redes cuantizadas dinámicamente bajo especificaciones de vectores de bits.

Autores originales: Eric Alsmann, Martin Lange, Marco Sälzer

Publicado 2026-05-29

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Eric Alsmann, Martin Lange, Marco Sälzer

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que tienes un robot muy inteligente (una Red Neuronal de Alimentación Directa) que toma decisiones, como reconocer un gato en una foto o dirigir un coche autónomo. Antes de dejar que este robot actúe en el mundo real, debemos estar 100% seguros de que no cometerá un error peligroso. Este proceso se llama verificación.

Durante mucho tiempo, los científicos intentaron verificar estos robots fingiendo que estaban hechos de matemáticas perfectas de precisión infinita (como usar una regla que puede medir hasta el tamaño de un átomo, para siempre). Pero en el mundo real, las computadoras no son perfectas. Utilizan aritmética cuantizada, que es como usar una regla que solo tiene marcas cada milímetro. Tienes que redondear las cosas, y a veces te quedas sin espacio (desbordamiento).

Este artículo plantea una gran pregunta: ¿Cambiar de "matemáticas perfectas" a "matemáticas del mundo real, redondeadas" hace que sea mucho más difícil probar que el robot es seguro?

Aquí está el desglose de sus hallazgos, utilizando algunas analogías cotidianas:

1. Los Tres Tipos de Robots

Los autores examinaron tres formas diferentes en que se construyen estos robots:

El Robot Ideal (FNN Racional): Construido con matemáticas perfectas de precisión infinita.
El Robot Pre-Cuantizado (FNN Cuantizado): Construido desde el principio utilizando la "regla de milímetro" (matemáticas de ancho finito).
El Robot Convertido (Cuantizado Dinámicamente): Un robot perfecto que forzamos a usar la "regla de milímetro" después de que ya fue entrenado.

2. Los Dos Tipos de Reglas de Seguridad

Para verificar si el robot es seguro, le damos reglas. El artículo examina dos tipos de libros de reglas:

Las Reglas Lineales (LP): Son reglas simples y de línea recta. Piensa en ellas como un letrero de tráfico que dice: "Si la velocidad es inferior a 50, estás seguro". Estas reglas son fáciles de visualizar como una forma suave y convexa.
Las Reglas de Vectores de Bits (BV): Son reglas complejas a nivel de "bit". Piensa en ellas como un sistema de seguridad que verifica interruptores específicos dentro del cerebro de la computadora. "Si el bit 3 está encendido Y el bit 7 está apagado, pero el bit 2 está encendido, entonces es un problema". Estas pueden describir formas muy irregulares, complejas y no lineales.

3. Los Hallazgos Principales: ¿Es más difícil?

Escenario A: Reglas Simples (Restricciones Lineales)

El Resultado: No, no es más difícil.
Ya sea que el robot sea perfecto o utilice la "regla de milímetro", y ya sea que las reglas sean simples o complejas, verificar la seguridad sigue siendo NP-completo.

La Analogía: Imagina intentar encontrar una llave específica en un cajón gigante y desordenado. Ya sea que las llaves estén hechas de oro (matemáticas perfectas) o de plástico (matemáticas redondeadas), y ya sea que el cajón esté organizado o caótico, la dificultad de encontrar la llave no cambia. Sigue siendo un problema "difícil", pero es del mismo nivel de dificultad que antes.
Por qué esto importa: Significa que no necesitamos inventar computadoras completamente nuevas y súper potentes para verificar robots del mundo real. Las herramientas que ya tenemos para matemáticas perfectas pueden adaptarse para matemáticas del mundo real sin volverse exponencialmente más lentas.

Escenario B: Reglas Complejas (Restricciones de Vectores de Bits)

El Resultado: Depende del "tamaño del cerebro" del robot.

Si el robot ya está construido con la "regla de milímetro": Verificar la seguridad sigue siendo NP-completo (misma dificultad que antes).
Si tomamos un robot perfecto y lo forzamos a usar la "regla de milímetro" (Cuantización Dinámica): Esto se vuelve mucho más difícil. Salta a PSPACE-completo.
- La Analogía: Imagina que tienes una receta perfecta (el robot perfecto). Ahora, tienes que cocinarla en una cocina pequeña con un conjunto específico y limitado de ollas y sartenes (la aritmética de ancho finito). Si solo usas las ollas limitadas desde el principio, está bien. Pero si intentas traducir la receta perfecta a la cocina limitada mientras cocinas, el número de formas posibles en que las cosas pueden salir mal explota. Tienes que mantener un registro de tantos "qué pasaría si" (como alinear números de diferentes tamaños) que la memoria requerida para verificarlos todos crece masivamente.

4. El Misterio de los Números de Punto Flotante

El artículo también examinó los números de punto flotante (la forma estándar en que las computadoras manejan los decimales, como 3.14).

Exponente Fijo: Si el rango de números es fijo (como una regla con una longitud máxima fija), la dificultad se mantiene manejable (PSPACE).
Punto Flotante General: Si el rango puede cambiar drásticamente, la dificultad podría saltar aún más (NEXPTIME).
La Analogía: En matemáticas de punto flotante, los números pueden ser muy pequeños o muy grandes. Para sumarlos, la computadora tiene que "alinearlos" primero (como alinear los puntos decimales). Si los números son de tamaños muy diferentes, la computadora debe almacenar en búfer una gran cantidad de datos para realizar esta alineación. Los autores descubrieron que este paso de "alineación" es lo que hace que el problema sea potencialmente mucho, mucho más difícil de resolver.

Resumen

El artículo esencialmente dice:

Buenas noticias: Para el tipo más común de verificación de seguridad (reglas lineales), cambiar a matemáticas del mundo real, redondeadas, no hace que la tarea sea imposible. Sigue siendo del mismo nivel de dificultad que las matemáticas perfectas teóricas.
Malas noticias: Si estás utilizando reglas muy complejas a nivel de bits en un robot perfecto que estás forzando a usar matemáticas redondeadas, la tarea se vuelve significativamente más difícil (PSPACE).
Lo desconocido: Si utilizas matemáticas de punto flotante estándar con rangos salvajes, la tarea podría ser aún más difícil, pero los autores no están 100% seguros todavía; solo saben que es al menos tan difícil como el nivel "PSPACE".

En resumen: La cuantización (redondeo) no rompe la verificación para reglas simples, pero sí hace que los escenarios complejos y dinámicos sean mucho más costosos computacionalmente.

Resumen Técnico: La Complejidad de Verificar Redes Neuronales Feedforward en Entornos Cuantizados

Enunciado del Problema

El artículo investiga la complejidad computacional de verificar formalmente Redes Neuronales Feedforward (FNN) en entornos cuantizados. Si bien el problema de alcanzabilidad para FNNs que operan sobre aritmética de valores reales (pesos racionales) está establecido como NP-completo, las implementaciones prácticas dependen de aritmética de ancho finito (por ejemplo, números de punto flotante de 64 bits o números de punto fijo). Este cambio introduce efectos de cuantización como redondeo, desbordamiento y subdesbordamiento.

Los autores abordan una posible brecha en la comprensión: ¿el paso de la aritmética de valores reales idealizada a la aritmética discreta de ancho finito aumenta la complejidad computacional de la verificación? Además, examinan cómo cambia la complejidad basándose en:

Formalismos de Especificación: Restricciones de Programación Lineal (LP) versus lógicas de Vectores de Bits (BV) (que permiten razonamiento no lineal a nivel de bit).
Definición de la Red: Si la FNN se define con pesos racionales exactos (FNN Racional) o con pesos pre-cuantizados (FNN Cuantizada).
Codificación de Parámetros: Si el ancho de bits de la aritmética se proporciona como parte de la entrada en unario (realista para tamaños de registros de hardware) o binario (realista para especificaciones decimales).

Metodología

Los autores formalizan cinco problemas de decisión de alcanzabilidad distintos, denotados como REACH, que varían según el tipo de aritmética y el lenguaje de especificación:

REACHQ(LP): FNNs Racionales con especificaciones LP (configuración estándar).
REACHF(LP): FNNs Cuantizadas (pesos ya en aritmética de ancho finito) con especificaciones LP.
REACHF(BV): FNNs Cuantizadas con especificaciones de Vectores de Bits.
REACH(F, LP): FNNs Racionales donde la aritmética de ancho finito objetivo $F$ es parte de la entrada (cuantización dinámica) con especificaciones LP.
REACH(F, BV): FNNs Racionales con cuantización dinámica y especificaciones de Vectores de Bits.

Enfoque Analítico:

Límites Inferiores de Complejidad: Los autores utilizan reducciones desde problemas conocidos como difíciles (por ejemplo, 3SAT) para establecer la NP-dureza y la PSPACE-dureza. Demuestran que los "artefactos" estándar utilizados para codificar lógica booleana en FNNs (usando activaciones ReLU) siguen siendo válidos incluso bajo aritmética de ancho finito, siempre que la aritmética pueda representar enteros pequeños y fracciones como $1/2$ .
Límites Superiores de Complejidad:
- Para especificaciones LP, los autores se basan en el límite polinomial de los tamaños de solución en la programación lineal (Teorema 1) para mostrar que un testigo (vector de entrada) puede ser adivinado y verificado en tiempo polinomial.
- Para especificaciones BV con cuantización dinámica, los autores emplean Autómatas Finitos No Deterministas Succintos (NFA). Construyen autómatas que representan la relación entrada-salida de la FNN cuantizada y las fórmulas de especificación. El espacio de estados de estos autómatas es exponencialmente grande pero se describe de forma compacta (succinta).
- Distinguen entre aritmética de punto fijo y punto flotante. Para punto flotante, señalan que la aritmética general requiere desplazamientos de alineación que dependen de la diferencia de exponentes. Si el ancho del exponente es ilimitado (dado en binario), el tamaño del búfer de alineación se vuelve exponencial, lo que potencialmente rompe los límites PSPACE. Restringen sus pruebas de límite superior PSPACE a casos donde el ancho del exponente es constante.

Contribuciones y Resultados Clave

El artículo establece un panorama de complejidad integral, resumido en la Tabla 1 del texto:

1. Especificaciones de Programación Lineal (LP)

REACHQ(LP): Reafirmado como NP-completo (citando a Sälzer y Lange, 2021).
REACHF(LP): Probado como NP-completo. Los autores muestran que incluso con pesos pre-cuantizados, el problema permanece en NP porque el tamaño de entrada del testigo es polinomial en relación con el tamaño de la red.
REACH(F, LP): Probado como NP-completo. Incluso cuando los parámetros de ancho de bits son parte de la entrada (cuantización dinámica), el problema permanece NP-completo. Los autores argumentan que el tamaño del testigo permanece acotado polinomialmente en relación con el tamaño de la entrada, independientemente de si los anchos de bits se codifican en unario o binario.

2. Especificaciones de Vectores de Bits (BV)

REACHF(BV): Probado como NP-completo. Para redes ya cuantizadas, el uso de lógica de vectores de bits no aumenta la complejidad más allá de NP.
REACH(F, BV) (Punto fijo y Punto flotante con ancho de exponente constante): Probado como PSPACE-completo.
- Límite Inferior: Coincide con el resultado de PSPACE-dureza establecido previamente por Henzinger et al. (2021).
- Límite Superior: Los autores proporcionan el primer límite superior PSPACE coincidente. Lo logran reduciendo el problema al problema de no vacuidad de NFA representados de forma succinta.
REACH(F, BV) (Punto flotante general): El problema es PSPACE-duro y se encuentra dentro de NEXPTIME.
- Los autores señalan que para la aritmética de punto flotante general (donde el ancho del exponente es variable y se da en binario), el paso de alineación en la suma/multiplicación requiere un tamaño de búfer que depende de la diferencia de exponentes. Esto impide la construcción de un NFA succinto con tamaño de descripción polinomial, dejando el límite superior exacto abierto (actualmente NEXPTIME).

Significado y Afirmaciones

El artículo afirma resolver un "malentendido generalizado" con respecto a la complejidad de la verificación de FNNs cuantizadas, abordando específicamente los resultados de Henzinger et al. (2021).

Clarificación de los Impulsores de la Complejidad: Los autores argumentan que el salto de NP a PSPACE observado en trabajos anteriores no es causado por la cuantización en sí misma, sino por la combinación de cuantización dinámica (donde la aritmética es parte de la entrada) y el uso de especificaciones de Vectores de Bits. Para especificaciones lineales estándar, la cuantización no aumenta la clase de complejidad; permanece NP-completa.
Viabilidad de Herramientas: Los resultados sugieren que desarrollar herramientas de verificación sólidas para FNNs cuantizadas utilizando especificaciones lineales es factible sin sobrecarga asintótica en comparación con los solucionadores de valores reales existentes, ya que ambos permanecen NP-completos.
Límites Superiores para BV: El artículo complementa la conocida PSPACE-dureza de la verificación cuantizada dinámica con especificaciones BV estableciendo la PSPACE-completitud para aritmética de punto fijo y de punto flotante con exponente acotado.
Problemas Abiertos: Los autores identifican modestamente que para la aritmética de punto flotante general con exponentes ilimitados, el requisito de alineación puede empujar el problema más allá de PSPACE (hacia NEXPTIME), y sigue siendo una pregunta abierta si se puede probar un límite inferior coincidente.

En conclusión, el artículo proporciona una clasificación rigurosa que muestra que, si bien las especificaciones de vectores de bits en redes dinámicamente cuantizadas introducen complejidad PSPACE, el caso estándar de restricciones lineales en redes cuantizadas conserva la NP-completitud del caso racional.