La búsqueda de vecinos más cercanos aproximados (ANN) en espacios vectoriales de alta dimensión es un problema fundamental en la computación, crítico para sistemas como los de Recuperación Aumentada por Generación (RAG). Los métodos tradicionales, como Product Quantization (PQ), a menudo requieren una fase de entrenamiento intensiva y reconstrucciones del índice a medida que el corpus crece, lo que introduce latencia y complejidad operativa. TurboVec aborda esto implementando TurboQuant, un algoritmo de cuantificación de vectores "data-oblivious" que no requiere entrenamiento explícito ni reconstrucciones, permitiendo la ingesta online y la persistencia incremental. Esto es crucial en escenarios donde la privacidad, la memoria o la latencia son restricciones primarias, ofreciendo una alternativa a soluciones que dependen de servicios gestionados o de índices con fases de entrenamiento costosas.
El desafío subyacente es cómo comprimir vectores de alta dimensión de manera que se minimice la distorsión de la distancia y se permita una búsqueda eficiente. La compresión es vital para reducir el footprint de memoria, que puede ser prohibitivo para grandes corpus con vectores float32. La eficiencia de búsqueda requiere aprovechar las arquitecturas de hardware modernas, específicamente las extensiones SIMD, para realizar operaciones de producto escalar a alta velocidad. TurboVec integra estos dos aspectos, combinando un esquema de cuantificación teóricamente sólido con implementaciones de kernel de bajo nivel optimizadas para arquitecturas x86 y ARM.
Arquitectura del Sistema
TurboVec se construye alrededor del algoritmo TurboQuant, que comprime vectores de alta dimensión utilizando una serie de transformaciones. Primero, los vectores se normalizan para convertirlos en direcciones unitarias en una hiperesfera. Luego, se aplica una rotación ortogonal aleatoria a todos los vectores, lo que transforma la distribución de coordenadas a una Beta conocida, que converge a una Gaussiana N(0, 1/d) en altas dimensiones. Esta propiedad es clave porque permite precomputar un codebook óptimo mediante el algoritmo de Lloyd-Max, sin necesidad de datos de entrenamiento.
Para mejorar la precisión, TurboVec implementa una calibración per-coordenada (TQ+) que ajusta las cuantiles empíricas de cada coordenada a los centroides del codebook, y una renormalización de longitud que corrige el sesgo del producto escalar introducido por la cuantificación. Los vectores cuantificados se empaquetan en bits para maximizar la compresión (ej. de 6144 bytes a 384 bytes para un vector de 1536 dimensiones a 2 bits). La búsqueda se realiza rotando la query una vez y luego puntuando directamente contra los valores del codebook utilizando kernels SIMD escritos a mano (NEON SDOT/SMMLA en ARM, AVX-512 VNNI y vpermb en x86, con fallbacks a AVX2 y escalar). Estos kernels están optimizados para el diseño de empaquetamiento de nibble-LUT, similar a FAISS FastScan. La persistencia del índice es incremental, utilizando fsync y renombramiento atómico para garantizar la seguridad ante fallos, permitiendo actualizaciones rápidas de solo los cambios.
Flujo de Ingesta y Cuantificación de Vectores
- 1 Vector Input Vectores float32 de alta dimensión (ej. (n, dim))
- 2 Normalización Se extrae la norma (longitud) y se almacena; el vector se convierte en unitario.
- 3 Rotación Aleatoria Multiplicación por una matriz ortogonal aleatoria predefinida.
- 4 Calibración (TQ+) Ajuste opcional per-coordenada a los centroides del codebook.
- 5 Cuantificación Lloyd-Max Cada coordenada se mapea a un entero pequeño (0-3 para 2-bit, 0-15 para 4-bit).
- 6 Empaquetamiento de Bits Enteros pequeños se empaquetan densamente en bytes.
- 7 Renormalización de Longitud Se calcula y almacena un escalar para corregir el sesgo del producto escalar.
- 8 Índice Cuantificado Vector comprimido almacenado en memoria/disco.
Flujo de Búsqueda de Vecinos Cercanos
- 1 Query Vector Input Vector float32 de consulta
- 2 Rotación de Query La query se rota con la misma matriz ortogonal.
- 3 Filtro (Opcional) Aplicación de allowlist/bitmask para restringir candidatos.
- 4 Búsqueda SIMD Kernel SIMD (NEON/AVX-512) puntúa directamente contra el codebook.
- 5 Corrección de Puntuación Se aplica el escalar de renormalización de longitud a cada puntuación.
- 6 Resultados Top-K Se devuelven los k vectores más cercanos (puntuaciones e IDs).
| Capa | Tecnología | Justificación |
|---|---|---|
| compute | Rust | Lenguaje de implementación principal para el rendimiento de bajo nivel y la seguridad de memoria. Permite la creación de kernels SIMD optimizados. vs C++ |
| compute | Python Bindings | Proporciona una interfaz de alto nivel para la integración con ecosistemas de ML/RAG (LangChain, LlamaIndex, Haystack, Agno). vs Java Bindings, Go Bindings |
| compute | SIMD Intrinsics (NEON, AVX-512, AVX2) | Optimización de kernels de búsqueda para aprovechar el paralelismo a nivel de instrucción en CPUs ARM y x86, reduciendo drásticamente la latencia de búsqueda. vs OpenCL/CUDA (GPU), Scalar Fallback Detección de características en tiempo de ejecución para seleccionar el kernel más avanzado disponible. |
| storage | Filesystem (fsync, atomic rename) | Mecanismo de persistencia incremental y crash-safe para el índice, permitiendo actualizaciones rápidas y duraderas. vs Base de datos embebida (SQLite), Almacenamiento en la nube (S3) |
Trade-offs
Ganancias
- ▲▲ Consumo de memoria
- ▲ Velocidad de búsqueda
- ▲ Latencia de ingesta/actualización
- ▲ Complejidad operativa (sin entrenamiento/reconstrucción)
- ▲ Privacidad (local, air-gapped)
Costes
- △ Precisión (recall) en baja dimensionalidad o muy bajas bit-widths (mitigado por TQ+)
from turbovec import TurboQuantIndex
index = TurboQuantIndex(dim=1536, bit_width=4)
index.add(vectors)
scores, indices = index.search(query, k=10)
index.write("my_index.tv")
loaded = TurboQuantIndex.load("my_index.tv")
index.sync("my_index.tv")import numpy as np
from turbovec import IdMapIndex
idx = IdMapIndex(dim=1536, bit_width=4)
idx.add_with_ids(vectors, np.array([1001, 1002, 1003], dtype=np.uint64))
allowed = np.array([1001, 1003], dtype=np.uint64)
scores, ids = idx.search(query, k=10, allowlist=allowed)
idx.remove(1002)Fundamentos Teóricos
El algoritmo TurboQuant se basa en principios de la teoría de la información y la cuantificación escalar. La idea de que, tras una rotación aleatoria, las coordenadas de un vector de alta dimensión siguen una distribución predecible, es una aplicación del teorema del límite central y propiedades de las distribuciones en espacios de alta dimensión. La cuantificación de Lloyd-Max, utilizada para generar el codebook, es un algoritmo clásico para la cuantificación escalar óptima que minimiza el error cuadrático medio, desarrollado por S. P. Lloyd en 1957 y J. Max en 1960. La conexión con la teoría de la distorsión-tasa de Shannon es explícita, ya que TurboQuant logra una distorsión dentro de un factor de 2.7x del límite inferior teórico.
La renormalización de longitud, que corrige el sesgo del producto escalar, se inspira en trabajos como RaBitQ (SIGMOD 2024), que aborda la cuantificación de vectores de alta dimensión con límites de error teóricos. La optimización de los kernels SIMD para la búsqueda se basa en técnicas de bajo nivel exploradas en la literatura de procesamiento de señales y computación de alto rendimiento, incluyendo el uso de instrucciones específicas de la arquitectura para productos escalares y lookups de tablas. La eficiencia de la búsqueda en TurboVec se beneficia de la investigación en índices de vectores aproximados, donde FAISS (Johnson et al., 2017) ha sido un referente importante, y TurboVec adapta algunas de sus técnicas de empaquetamiento y puntuación.