Recuperación por dentro: ANN, HNSW e IVF

Quinta entrega de la serie, y la más técnica del bloque de fundamentos. En la anterior quedó dicho que un índice vectorial deja de ser exacto a cambio de ser rápido. Aquí se ve cómo: qué estructura tiene el índice, qué parámetros lo gobiernan y qué se paga exactamente por cada punto de recall que se gana.

Por qué la búsqueda exacta no llega

La búsqueda exhaustiva —comparar la consulta con todos los vectores— es sencilla de razonar: coste lineal en el número de vectores y en la dimensión. Con N vectores de d dimensiones, cada consulta cuesta del orden de N·d multiplicaciones y sumas.

Con N = 100.000 y d = 768 eso son unos 77 millones de operaciones, que en hardware moderno se resuelven en unos pocos milisegundos. Con N = 50.000.000 son 38.000 millones de operaciones por consulta, y ya no hay presupuesto de latencia que lo aguante.

El problema es que en dimensiones altas no existen los atajos clásicos. Los índices espaciales tradicionales —árboles k-d, árboles de bolas— funcionan bien con dos, tres o diez dimensiones y degeneran a partir de unas decenas: con 768 dimensiones acaban visitando prácticamente todos los nodos, con la sobrecarga añadida del árbol. Es la maldición de la dimensionalidad: en un espacio de dimensión alta las distancias tienden a igualarse y particionar el espacio deja de discriminar.

La salida fue renunciar a la garantía. La búsqueda aproximada de vecinos más próximos (ANN, approximate nearest neighbor) no promete devolver los k vecinos verdaderos, sino la mayoría de ellos, la mayor parte de las veces, mucho más rápido. La medida de esa promesa es el recall del índice: qué fracción de los k vecinos exactos aparece realmente en el resultado.

La escala del beneficio: un índice ANN bien configurado suele visitar del orden de una milésima o una diezmilésima de los vectores del corpus manteniendo un recall alto. Ese es el orden de magnitud que hace viable un RAG sobre decenas de millones de fragmentos.

HNSW: un grafo navegable por capas

HNSW (Hierarchical Navigable Small World) es el índice más extendido en sistemas RAG, y está implementado en casi todos los motores, incluida la extensión vectorial de PostgreSQL.

La idea de partida es construir un grafo donde cada vector es un nodo conectado a sus vecinos aproximados. Buscar consiste en entrar por un punto cualquiera y moverse, en cada paso, al vecino más cercano a la consulta, hasta que ninguno mejora. Es una búsqueda voraz, y funciona porque en un grafo de este tipo —de «mundo pequeño»— hay caminos cortos entre puntos lejanos.

El adjetivo jerárquico añade lo que lo hace eficiente: no hay un grafo, hay varias capas. La superior contiene muy pocos nodos y enlaces muy largos; cada capa inferior contiene más nodos y enlaces más cortos; la capa cero contiene todos. La búsqueda empieza arriba, donde cuatro saltos cubren medio espacio, y va bajando: cada capa refina la posición que dejó la anterior. Es la intuición de una lista de saltos, llevada a un grafo.

Parámetros de HNSW

M es el número máximo de conexiones por nodo en las capas superiores (en la capa cero suele permitirse el doble). Determina la densidad del grafo. Un M alto da más caminos alternativos y por tanto mejor recall, a costa de más memoria —cada enlace ocupa— y de un grafo más caro de recorrer. Valores habituales van de 8 a 64; subir de 32 rara vez compensa salvo en corpus muy grandes o de distribución difícil.

ef_construction es el tamaño de la lista de candidatos que se mantiene al insertar cada nodo nuevo. Cuanto mayor, mejor elegidos quedan sus vecinos y mejor es la calidad del grafo resultante. Sólo afecta al tiempo de construcción y a la calidad permanente del índice: no cuesta nada en consulta. Es el parámetro donde más sentido tiene ser generoso, porque se paga una vez.

ef_search es el tamaño de la lista de candidatos durante la búsqueda. Es el mando de recall en tiempo de consulta, y el único que se puede ajustar sin reconstruir nada. Tiene que ser al menos igual a k. Subirlo aumenta el recall y la latencia de forma bastante suave, lo que permite calibrarlo contra un objetivo concreto: se mide el recall real frente a una búsqueda exhaustiva sobre una muestra y se sube hasta alcanzar el nivel deseado.

El punto débil de HNSW es la memoria: el grafo entero, con todos sus enlaces, vive normalmente en RAM junto con los vectores, y en corpus grandes eso domina el coste por delante del cómputo. El segundo son los borrados: eliminar nodos sin degradar el grafo es complicado, y varios motores optan por marcarlos y limpiarlos en una compactación posterior, de modo que el espacio no se recupera de inmediato.

IVF: dividir el espacio en celdas

IVF (Inverted File) parte de otra idea. Antes de indexar, se agrupan los vectores en nlist grupos mediante un algoritmo de agrupamiento, típicamente k-medias. Cada grupo tiene un centroide, y cada vector se asigna a la celda de su centroide más cercano. El índice es, literalmente, una lista de qué vectores hay en cada celda.

Al buscar, se compara la consulta sólo con los nlist centroides, se eligen las nprobe celdas más prometedoras y se hace búsqueda exhaustiva dentro de ellas. Si hay 4.096 celdas y se exploran 16, se está mirando aproximadamente el 0,4% del corpus.

El fallo característico de IVF es el vector que cae cerca de una frontera entre celdas: su vecino verdadero puede estar en la celda de al lado, que no se ha explorado. Subir nprobe mitiga precisamente eso. Una regla operativa razonable para elegir nlist es situarlo en el orden de la raíz cuadrada del número de vectores, y calibrar nprobe midiendo recall.

Frente a HNSW, IVF consume mucha menos memoria de estructura, se construye más rápido y encaja mejor con corpus que cambian mucho, pero suele necesitar explorar más vectores para alcanzar el mismo recall. También tiene una fragilidad propia: los centroides se calculan con los datos que había al entrenar el índice. Si el corpus cambia de naturaleza —entra un dominio nuevo, otro idioma— las celdas dejan de repartir bien y el recall cae. Reentrenar el índice es la solución, y es una operación que hay que tener prevista.

Cuantización: comprimir los vectores

Los índices reducen cuántos vectores se comparan. La cuantización reduce cuánto ocupa y cuánto cuesta cada comparación. Son técnicas ortogonales y se combinan.

Cuantización escalar. Cada componente pasa de coma flotante de 32 bits a un entero de 8 bits. Divide por cuatro la memoria y acelera las comparaciones, con una pérdida de recall que en la mayoría de corpus es pequeña. Es la opción por defecto razonable cuando la memoria empieza a apretar: buena relación entre lo que se ahorra y lo que se pierde.

Cuantización de producto (PQ). El vector se parte en m subvectores y cada uno se sustituye por el identificador del centroide más parecido de un pequeño diccionario aprendido para esa porción. Un vector de 768 dimensiones puede quedar en 96 bytes o menos, factores de compresión de uno o dos órdenes de magnitud. La contrapartida es una pérdida de precisión notable, que obliga a la estrategia habitual: recuperar más candidatos de los necesarios con los vectores comprimidos y reordenarlos después con los vectores originales, leídos de disco. A eso se le llama rescoring, y sin él PQ rara vez da resultados aceptables.

Cuantización binaria. Cada componente se reduce a un bit según su signo. La compresión es extrema y la comparación se convierte en una distancia de Hamming, que el procesador resuelve con instrucciones de conteo de bits. Sólo funciona con modelos de embeddings cuyos vectores toleren esa reducción —no todos lo hacen— y siempre acompañada de rescoring. Cuando encaja, la ganancia en memoria es enorme; cuando no, el recall se hunde. Hay que medirlo sobre el propio corpus, no darlo por bueno.

Tabla de parámetros

El triángulo recall, latencia, memoria

Todo lo anterior se reduce a un compromiso de tres vértices del que no se escapa: se puede mejorar cualquiera de los tres a costa de al menos uno de los otros.

La forma sensata de moverse por él es fijar primero lo que no es negociable: un presupuesto de latencia dado por el producto —del que la búsqueda vectorial sólo consume una parte, porque el generador se lleva la mayoría— y uno de memoria dado por la factura. Con esos dos fijos, se maximiza el recall.

Y ese recall hay que medirlo, no estimarlo. El procedimiento es sencillo y casi nadie lo hace: se toman unos cientos de consultas representativas, se resuelven con búsqueda exhaustiva sobre el corpus real para obtener la verdad, y se compara con lo que devuelve el índice configurado. Ese número es el que permite decidir si ef_search está bajo o si la cuantización cuesta más de lo que ahorra.

Dos advertencias para cerrar. La primera: nada de esto importa por debajo de unos cientos de miles de vectores, donde la búsqueda exhaustiva es exacta y suficientemente rápida, y un índice aproximado sólo añade parámetros que ajustar y una fuente de error que no se tenía. La segunda: el recall del índice tiene un techo de utilidad. Ganar los últimos puntos casi nunca cambia la respuesta final, porque el fragmento que entra en el puesto veinte no iba a llegar al prompt de todos modos. Si las respuestas son malas con recall alto, el problema está en el troceado, en el modelo de embeddings o en la estrategia de recuperación.

Qué viene ahora

Con los fragmentos ya recuperados queda montarlos en un prompt que el modelo lea como es debido. La siguiente entrega trata la anatomía de esa plantilla: la instrucción de fidelidad, en qué orden colocar los fragmentos y por qué el orden importa, cómo deduplicar, cómo repartir el presupuesto de tokens, cómo pedir citas verificables y qué hacer cuando no se ha recuperado nada suficientemente bueno.

Si prefieres leerlo todo de golpe y en orden, los tres libros gratuitos de los que nace esta serie están disponibles en PDF y EPUB: RAG para tu negocio (nivel básico), RAG por dentro (intermedio) y RAG en producción (avanzado).

Aviso de contenido generado con inteligencia artificial.
Este artículo ha sido redactado con la asistencia de sistemas de inteligencia artificial y revisado antes de su publicación. Se informa de ello de forma expresa en cumplimiento de la normativa vigente sobre transparencia en el uso de IA.