Por que varrer tudo custa tão caro?: explicação detalhada com exemplos (RAG)

1. Visão geral

No pipeline RAG (Retrieval-Augmented Generation), o passo de retrieval geralmente é fazer matching entre os vetores da pergunta e vetores de centenas de milhares de passages. A forma mais simples — comparar sequencialmente cada vetor — sempre produz resultados corretos, mas o custo aumenta linearmente com o tamanho dos dados. Este artigo explica por que “comparar tudo” é caro, como o Inverted-File Index (IVF) reduz custos através de clustering, e o preço que você paga ao aceitar resultados aproximados. Após a leitura, você saberá implementar um flat index e um IVF index simples em Java, medir o trade-off entre velocidade e recall, e saber quando deve — ou não — usar approximate search.

2. O problema: Flat Index e complexidade O(n)

2.1. Como funciona flat search

Flat index (ou brute-force search) compara a query com todos os vetores no conjunto de dados, depois seleciona os vetores com as pontuações mais altas (geralmente cosine similarity ou dot product). Não há nenhuma etapa de filtragem intermediária.

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));
    }
}

A cada chamada de search, o loop implícito dentro de stream() precisa calcular cosine com todos os passages. Se o conjunto de dados tem n vetores e cada vetor tem d dimensões, o custo de cada query é O(n × d). Dobrar o número de passages dobra o número de comparações — este é exatamente o significado de “O(n)”.

Observação: Flat search retorna resultados “exatos” — ou seja, absolutamente corretos de acordo com a fórmula de distância que você escolheu. Mas “exato” não significa que o passage contenha a resposta correta semanticamente. Precisão geométrica e precisão semântica são duas coisas diferentes.

2.2. Medindo como o custo aumenta com o tamanho dos dados

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);
    }
}

Resultados ilustrativos em uma máquina de desenvolvimento (os números reais dependem do hardware, mas a tendência sempre se mantém):

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

Os dados aumentam 10 vezes, o tempo aumenta quase 10 vezes — exatamente como previsto por O(n). Com um milhão de passages e muitas queries por segundo, esse custo se acumula muito rapidamente. Esta é a razão pela qual flat index não escala bem para sistemas RAG em produção.

3. Solução: Inverted-File Index (IVF)

3.1. A ideia de clustering

IVF reduz custos não comparando com todos os vetores. Em vez disso:

1. Ao construir o índice, execute clustering (geralmente k-means) para encontrar os “centroides” que representam cada grupo de vetores próximos.
2. Cada vetor no conjunto de dados é atribuído ao grupo cujo centroide está mais próximo.
3. Ao buscar, selecione apenas alguns grupos cujos centroides estão mais próximos da query, depois compare apenas com vetores nesses grupos.

Imagine um milhão de passages divididos em 1000 grupos. Se você verificar apenas 10 grupos, compara cerca de 10.000 passages em vez de um milhão — reduzindo o custo em quase 100 vezes.

3.2. O parâmetro nprobe

O número de grupos verificados é chamado de nprobe. Verificar mais grupos geralmente melhora o recall (a taxa de encontrar os resultados corretos), mas também aumenta o custo. Este é o parâmetro que você ajustará diretamente em produção.

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 encontra os k centroides mais próximos da query — este é exatamente onde nprobe entra em ação ao chamar search(query, topK, nprobe). A parte de construção de índice (constructor) roda uma vez, a parte de busca roda a cada query — é por isso que IVF é muito mais rápido no momento da consulta.

Observação: O exemplo acima usa centroides pré-fornecidos (amostrados dos dados) para manter o código simples. Na prática, você precisa executar k-means real (múltiplas iterações de atualização de centroide) para que os grupos tenham boa qualidade — bibliotecas como FAISS, Milvus ou pgvector já fazem esse trabalho para você.

3.3. Integração prática com pgvector

Se você está usando PostgreSQL com a extensão pgvector, os conceitos de IVF e nprobe aparecem diretamente em SQL:

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

SET ivfflat.probes = 10;

lists é equivalente ao número de clusters ao construir o índice, probes é equivalente ao nprobe quando você faz uma query. Você não precisa implementar k-means você mesmo — basta entender os trade-offs para escolher números sensatos.

4. Trade-off: recall vs. velocidade

IVF é um tipo de approximate nearest neighbor (ANN). Ele troca precisão absoluta para ganhar velocidade. O problema é: os clusters são formados a partir de distâncias matemáticas, não a partir de limites temáticos “bem arrumados” da forma como os humanos classificam documentos.

Um exemplo concreto em RAG: uma cláusula sobre “reembolso quando um voo é atrasado” pode estar mais próxima do cluster de vetores de documentos de seguros do que do cluster “política de despesas comerciais” — embora, tematicamente, um funcionário procure por ela na documentação de despesas. Se nprobe verificar apenas o cluster “política de despesas”, a resposta correta é completamente perdida, mesmo que exista nos dados.

4.1. Teste verificando recall diminuindo com nprobe

class IvfIndexTest {

    @Test
    void nprobe_baixo_pode_perder_resultado_certo() {
        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); // = varrer tudo, equivalente a flat

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

approxManyProbes varre todos os 40 clusters, então o resultado corresponde exatamente ao flat search — este é o baseline para confirmar que IVF não tem erros lógicos. approxFewProbes verifica apenas 1 cluster, e o último assert confirma que o resultado é diferente do caso exato — ilustrando o risco de perder recall quando nprobe é muito baixo.

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

Quando nprobe é baixo, o índice não apenas retorna menos resultados do que deveria, mas também pode perder passages importantes que estão “desalinhados com o cluster” — exatamente como no exemplo de seguro/despesas comerciais acima.

5. Quando usar flat, quando usar IVF

• Use flat search quando: o conjunto de dados é pequeno (algumas dezenas de milhares de passages ou menos), ou você precisa de precisão absoluta para fins de auditoria/conformidade, ou está em fase de prototipagem e não quer ajustar mais parâmetros.
• Use IVF (ou HNSW) quando: o conjunto de dados é grande (centenas de milhares a milhões de passages), a latência de query é um fator crítico (chatbot, busca em tempo real), e você aceita recall abaixo de 100% em troca de velocidade.

Observação: Não escolha nprobe muito baixo apenas porque o benchmark de velocidade fica bonito. Meça o recall em um conjunto de perguntas real do seu sistema RAG — uma resposta perdendo contexto importante é pior do que uma query um pouco mais lenta.

Um padrão comum em produção: use IVF (ou HNSW) para recuperar rapidamente os top-100 candidatos com recall aceitável, depois use uma etapa de reranking (cross-encoder ou flat search no pequeno conjunto de 100 candidatos) para compensar a precisão perdida. Dessa forma você mantém a velocidade do ANN enquanto ainda melhora a qualidade dos resultados finais.

6. Conclusão

Flat search é absolutamente preciso, mas o custo aumenta linearmente com o número de passages — não escala quando seu RAG precisa servir milhões de documentos. IVF resolve esse problema através de clustering e do parâmetro nprobe, trocando parte do recall para ganhar velocidade. O preço é que os clusters de vetores não correspondem aos limites temáticos do jeito que os humanos entendem, então passages importantes às vezes ficam “perdidos” em clusters que não são verificados. Entender bem esse trade-off ajuda você a escolher o índice certo, ajustar os parâmetros corretamente, e saber quando precisa adicionar uma etapa de reranking para compensar a precisão.