¿Por qué buscar todo cuesta tanto?: explicación detallada con ejemplos (RAG)

1. Descripción general

En el pipeline RAG (Retrieval-Augmented Generation), el paso de retrieval suele consistir en emparejar el vector de la pregunta con los vectores de cientos de miles de pasajes. El enfoque más simple — comparar secuencialmente cada vector — siempre da resultados correctos pero el costo aumenta linealmente con el tamaño de los datos. Este artículo explica por qué “buscar todo” es costoso, cómo Inverted-File Index (IVF) reduce el costo mediante clustering, y el precio que pagas al aceptar resultados aproximados. Después de leer, podrás escribir por ti mismo un flat index e un IVF index simple en Java, medir el equilibrio entre velocidad y recall, y saber cuándo debes — o no debes — usar búsqueda aproximada.

2. El problema: Flat Index y complejidad O(n)

2.1. Cómo funciona flat search

Flat index (o brute-force search) compara la query con todos los vectores del conjunto de datos, luego selecciona aquellos con puntuaciones más altas (generalmente cosine similarity o dot product). No hay pasos de filtrado intermedios.

public record Passage(String id, float[] vector) {}

public class FlatVectorIndex {

    private final List<Passage> passages;

    public FlatVectorIndex(List<Passage> passages) {
        this.passages = passages;
    }

    public List<Passage> search(float[] query, int topK) {
        return passages.stream()
                .sorted(Comparator.comparingDouble(p -> -cosine(query, p.vector())))
                .limit(topK)
                .toList();
    }

    private double cosine(float[] a, float[] b) {
        double dot = 0, na = 0, nb = 0;
        for (int i = 0; i < a.length; i++) {
            dot += a[i] * b[i];
            na += a[i] * a[i];
            nb += b[i] * b[i];
        }
        return dot / (Math.sqrt(na) * Math.sqrt(nb));
    }
}

Cada vez que llamas a search, el bucle implícito dentro de stream() debe calcular cosine con todos los passages. Si el conjunto de datos tiene n vectores y cada vector tiene d dimensiones, el costo de cada query es O(n × d). Duplica el número de pasajes, duplica el número de comparaciones — ese es el significado de “O(n)”.

Nota: Flat search da resultados “exactos” — es decir, completamente correctos según la fórmula de distancia que elijas. Pero “exacto” no significa que el pasaje contenga una respuesta correcta en sentido semántico. La precisión geométrica y la precisión semántica son dos cosas diferentes.

2.2. Medir el aumento de costo con el tamaño de datos

public static void main(String[] args) {
    for (int n : List.of(10_000, 100_000)) {
        var passages = TestData.generatePassages(n, 128, 42);
        var index = new FlatVectorIndex(passages);
        float[] query = TestData.randomVector(128, 7);

        long start = System.nanoTime();
        index.search(query, 5);
        long elapsedMs = (System.nanoTime() - start) / 1_000_000;

        System.out.printf("n=%d -> %d ms%n", n, elapsedMs);
    }
}

Resultado ilustrativo en una máquina de desarrollo (los números reales dependen del hardware, pero la tendencia siempre se mantiene):

n=10000  -> 18 ms
n=100000 -> 176 ms

Los datos aumentan 10 veces, el tiempo aumenta casi 10 veces — exacto con la predicción O(n). Con un millón de pasajes y muchas queries por segundo, este costo se acumula muy rápido. Esta es la razón por la que flat index no escala bien para sistemas RAG en producción.

3. Solución: Inverted-File Index (IVF)

3.1. Idea de clustering

IVF reduce el costo al no comparar con todos los vectores. En su lugar:

1. Al construir el índice, ejecutar clustering (generalmente k-means) para encontrar los “centroides” que representan cada grupo de vectores cercanos.
2. Cada vector del conjunto de datos se asigna al grupo cuyo centroide está más cerca.
3. Al buscar, solo seleccionar algunos grupos cuyos centroides estén más cerca de la query, luego comparar solo con vectores dentro de esos grupos.

Imagina un millón de pasajes divididos en 1000 grupos. Si solo escaneas 10 grupos, comparas alrededor de 10.000 pasajes en lugar de todo el millón — reduciendo el costo casi 100 veces.

3.2. El parámetro nprobe

El número de grupos escaneados se llama nprobe. Escanear más grupos generalmente mejora el recall (la tasa de encontrar los resultados correctos) pero también aumenta el costo. Este es un parámetro que ajustarás directamente en producción.

public class IvfIndex {

    private final List<float[]> centroids;
    private final Map<Integer, List<Passage>> buckets = new HashMap<>();

    public IvfIndex(List<Passage> passages, List<float[]> centroids) {
        this.centroids = centroids;
        for (Passage p : passages) {
            int cluster = nearestCentroidIndex(p.vector());
            buckets.computeIfAbsent(cluster, k -> new ArrayList<>()).add(p);
        }
    }

    public List<Passage> search(float[] query, int topK, int nprobe) {
        List<Integer> clusters = nearestCentroidIndices(query, nprobe);
        return clusters.stream()
                .flatMap(c -> buckets.getOrDefault(c, List.of()).stream())
                .sorted(Comparator.comparingDouble(p -> -cosine(query, p.vector())))
                .limit(topK)
                .toList();
    }

    private int nearestCentroidIndex(float[] v) {
        return nearestCentroidIndices(v, 1).get(0);
    }

    private List<Integer> nearestCentroidIndices(float[] v, int k) {
        return IntStream.range(0, centroids.size())
                .boxed()
                .sorted(Comparator.comparingDouble(i -> -cosine(v, centroids.get(i))))
                .limit(k)
                .toList();
    }

    private double cosine(float[] a, float[] b) {
        double dot = 0, na = 0, nb = 0;
        for (int i = 0; i < a.length; i++) {
            dot += a[i] * b[i];
            na += a[i] * a[i];
            nb += b[i] * b[i];
        }
        return dot / (Math.sqrt(na) * Math.sqrt(nb));
    }
}

nearestCentroidIndices encuentra los k centroides más cercanos a la query — aquí es donde nprobe tiene efecto cuando llamas a search(query, topK, nprobe). La parte de construcción del índice (constructor) se ejecuta una vez, la parte de búsqueda se ejecuta para cada query — esa es la razón por la que IVF es mucho más rápido en tiempo de consulta.

Nota: El ejemplo anterior usa centroides precalculados (muestreados de los datos) para mantener el código breve. En la práctica, necesitas ejecutar k-means real (múltiples iteraciones actualizando centroides) para obtener grupos de buena calidad — librerías como FAISS, Milvus o pgvector ya lo hacen por ti.

3.3. Integración práctica con pgvector

Si estás usando PostgreSQL con la extensión pgvector, los conceptos de IVF y nprobe aparecen directamente en SQL:

CREATE INDEX ON passages USING ivfflat (embedding vector_cosine_ops)
WITH (lists = 1000);

SET ivfflat.probes = 10;

lists equivale al número de clusters al construir el índice, probes equivale a nprobe en la query. No necesitas escribir k-means tú mismo — solo necesitas entender el equilibrio para elegir números razonables.

4. Equilibrio: recall vs. velocidad

IVF es una forma de approximate nearest neighbor (ANN). Intercambia precisión absoluta por velocidad. El problema es: los clusters se forman a partir de distancias matemáticas, no de límites temáticos “limpios” de la forma en que los humanos clasifican documentos.

Ejemplo concreto en RAG: una cláusula sobre “reembolso cuando un vuelo se retrasa” puede estar más cerca del cluster vectorial de documentos de seguros que del cluster “política de gastos de viaje” — aunque temáticamente, un empleado lo buscaría en documentos de viaje. Si nprobe solo escanea el cluster “política de gastos”, la respuesta correcta se pierde completamente, aunque exista en los datos.

4.1. Prueba de cómo recall disminuye con nprobe

class IvfIndexTest {

    @Test
    void testNprobeBasoPuedePerderResultados() {
        var passages = TestData.generatePassages(2000, 64, 42);
        var centroids = TestData.sampleCentroids(passages, 40, 42);
        var ivf = new IvfIndex(passages, centroids);
        var flat = new FlatVectorIndex(passages);

        float[] query = passages.get(1337).vector();

        var exact = flat.search(query, 5);
        var approxFewProbes = ivf.search(query, 5, 1);
        var approxManyProbes = ivf.search(query, 5, 40); // = escanea todo, equivalente a flat

        assertThat(approxManyProbes).containsExactlyInAnyOrderElementsOf(exact);
        assertThat(approxFewProbes).isNotEqualTo(approxManyProbes);
    }
}

approxManyProbes escanea los 40 clusters completos así que los resultados coinciden exactamente con flat search — este es el baseline para confirmar que IVF no tiene errores lógicos. approxFewProbes solo escanea 1 cluster, y la última assertion confirma que el resultado es diferente del caso exacto — ilustra el riesgo de perder recall cuando nprobe es demasiado bajo.

exact            = [p1337, p0892, p0456, p1890, p0023]
approxFewProbes  = [p1337, p0456, p0901, p0234]   // solo 4 resultados, faltan p0892, p1890
approxManyProbes = [p1337, p0892, p0456, p1890, p0023]

Cuando nprobe es bajo, el índice no solo devuelve menos resultados de los correctos, sino que también puede perder pasajes importantes que quedan “fuera del cluster” — exactamente como el ejemplo de seguros/gastos de viaje arriba.

5. Cuándo usar flat, cuándo usar IVF

• Usa flat search cuando: el conjunto de datos es pequeño (decenas de miles de pasajes o menos), o necesitas precisión absoluta para auditoría/compliance, o estás en fase de prototipo y aún no quieres ajustar parámetros.
• Usa IVF (o HNSW) cuando: el conjunto de datos es grande (cientos de miles a millones de pasajes), la latencia de query es factor crítico (chatbot, búsqueda en tiempo real), y aceptas recall menor del 100% para ganar velocidad.

Nota: No elijas nprobe demasiado bajo solo porque los benchmarks de velocidad se ven bien. Mide el recall con un conjunto de preguntas reales del sistema RAG — una respuesta con contexto importante faltante es peor que una query lenta por algunos ms.

Un patrón común en producción: usar IVF (o HNSW) para obtener rápidamente los top-100 candidatos con recall aceptable, luego usar un paso de rerank (cross-encoder o flat search en el pequeño conjunto de 100 candidatos) para recuperar la precisión perdida. Este enfoque mantiene la velocidad de ANN mientras mejora la calidad del resultado final.

6. Conclusión

La búsqueda plana es completamente exacta pero el costo aumenta linealmente con el número de pasajes — no escala cuando tu RAG debe servir millones de documentos. IVF resuelve esto mediante clustering y el parámetro nprobe, intercambiando parte del recall por velocidad. El precio a pagar es que los clusters vectoriales no coinciden con los límites temáticos como los humanos los entienden, así que pasajes importantes a veces quedan “perdidos” en clusters que no se escanean. Entender bien este equilibrio te ayuda a elegir el índice correcto, ajustar los parámetros correctamente, y saber cuándo necesitas un paso de rerank adicional para recuperar precisión.