Busca Vetorial em Produção: Grafos HNSW, Quantização SQ8/PQ/BQ e I/O de Memória

A busca vetorial em produção exige grafos multidimensionais e quantização. Sem essas otimizações, o gasto de RAM inviabiliza sistemas corporativos de inteligência artificial.

O que é o algoritmo HNSW e como ele estrutura a busca vetorial?

O algoritmo HNSW foi formalizado por Malkov & Yashunin (2018). Ele resolve a busca aproximada organizando vetores em grafos multicamadas inspirados em skip-lists.

Essa abordagem navega por espaços métricos densos sem varrer todo o conjunto de dados. Em altas dimensões (D ≥ 768), a busca exata sofre com a maldição da dimensionalidade: varrer milhões de vetores exige bilhões de operações de ponto flutuante, inviabilizando consultas em tempo real.

O HNSW divide a estrutura em L camadas discretas numeradas de 0 até l_max:

• Camadas Superiores (l > 0): Contêm poucos nós com conexões longas. Elas funcionam como rodovias expressas para cruzar grandes distâncias espaciais com poucas comparações.

• Camada Base (l = 0): Contém todos os vetores da base interligados por conexões curtas para exploração local precisa.

Hierarquia Multicamada do Grafo HNSW:

Camada 2 (Top Layer - Conexões Longas / Baixa Densidade):
  [Ponto A] --------------------------------------------> [Ponto K]
       \                                                      /
Camada 1 (Middle Layer - Densidade Intermediária):           /
  [Ponto A] --------------> [Ponto D] -----------------> [Ponto K]
       \                       \                             /
Camada 0 (Base Layer - Todos os Vetores / Conexões Curtas e Locais):
  [Ponto A] <-> [Ponto B] <-> [Ponto C] <-> [Ponto D] <-> [Ponto E] <-> [Ponto K]

A atribuição da camada máxima de cada nó segue uma distribuição geométrica com decaimento exponencial:

l = floor(-ln(unif(0, 1)) × mL)

O parâmetro multiplicador de camada é fixado como mL = 1 ÷ ln(M). Essa relação assegura que a probabilidade de atingir a camada l seja M^(-l).

Dessa forma, o algoritmo mantém a complexidade assintótica de busca em O(log N).

Como funcionam a busca gulosa e a seleção de arestas por diversidade angular?

A busca no HNSW combina roteamento guloso nas camadas superiores com busca em feixe na base. Essa mecânica localiza os vizinhos mais próximos minimizando o número total de cálculos métricos.

O algoritmo inicia no ponto de entrada global na camada superior l_max. Em cada camada intermediária, avalia os vizinhos imediatos e salta para o nó mais próximo da consulta.

Ao atingir a camada zero, comuta para uma busca em feixe parametrizada por efSearch.

Critério de Diversidade Angular (Poda de Arestas HNSW):

            [Candidato e_novo]
                 ^
                 |  dist(e_novo, e_selecionado) < dist(e_novo, base)
                 |  -> DESCARTADO (Sombra Angular)
                 v
      [e_selecionado]
           ^
            \
             \  dist(e_selecionado, base)
              \
               \
             [Nó Base]

A seleção de arestas durante a inserção adota uma heurística de diversidade angular:

• Candidatos a vizinhos são avaliados por ordem crescente de distância até o nó base.

• Um novo candidato só é conectado se estiver mais próximo da base do que de vizinhos já selecionados.

• Se um vizinho prévio estiver mais próximo do candidato do que a própria base, o candidato é descartado por sombra angular.

Esse mecanismo evita agrupamentos fechados redundantes e preserva caminhos direcionais abertos. A tabela abaixo sintetiza os hiperparâmetros essenciais do grafo:

Por que vetores brutos em FP32 saturam a largura de banda de memória DRAM?

A navegação por grafos espaciais impõe acessos aleatórios que quebram a hierarquia de cache. A cada salto no grafo, a CPU desreferencia ponteiros para nós espalhados no heap.

Em processadores atuais, executar uma instrução SIMD de produto escalar leva de 3 a 5 ciclos (~1 ns). Por outro lado, buscar dados fora do cache na DRAM consome de 60 a 90 nanossegundos.

Hierarquia de Memória vs Latência de Acesso no HNSW:

+-----------------------------+-------------------+--------------------+
| Nível de Armazenamento      | Latência de Acesso| Capacidade Típica  |
+-----------------------------+-------------------+--------------------+
| Registradores / L1 D-Cache  | 0,5 a 1,0 ns      | 32 a 48 KB / core  |
| L2 Cache Dedicado           | 3,0 a 5,0 ns      | 1 a 2 MB / core    |
| L3 Cache Compartilhado      | 15,0 a 25,0 ns    | 32 a 256 MB total  |
| DRAM (DDR5-5600)            | 60,0 a 90,0 ns    | 64 GB a 1 TB       |
| SSD NVMe (PCIe 4.0/5.0)     | 10.000 a 30.000 ns| 2 TB a 30 TB       |
+-----------------------------+-------------------+--------------------+

Acima de 500 mil registros, o índice excede o cache L3. Como nós vizinhos não residem contiguamente na memória, a taxa de cache misses supera 75%, deixando a CPU ociosa por mais de 80% do tempo aguardando o barramento.

Como a Quantização Escalar (SQ8) reduz o uso de RAM em quatro vezes?

A Quantização Escalar (SQ8) converte números de ponto flutuante de 32 bits (FP32) em inteiros de 8 bits (INT8 ou UINT8). Essa conversão reduz o volume de dados em 4x com perda de recall inferior a 1%.

O mapeamento linear uniforme assimétrico calcula fatores de escala S e pontos zero Z para cada vetor:

S = (v_max - v_min) ÷ 255 Z = round(-v_min ÷ S) q_i = clip(round(v_i ÷ S) + Z, 0, 255)

A dequantização reconstrói o valor aproximado durante a avaliação de distâncias:

v̂_i = (q_i - Z) × S

Mapeamento Linear de FP32 para UINT8 (SQ8):

Intervalo Contínuo FP32 [v_min, v_max]
+-----------------------------------------------------------+
| -0.0842   |   0.1245   |   -0.5431  |  ...  |   0.4120    |
+-----------------------------------------------------------+
                              |
           q = round((v - min) / (max - min) * 255)
                              v
Intervalo Discreto UINT8 [0, 255] (1 Byte por Dimensão)
+-----------------------------------------------------------+
|    82     |    142     |      12    |  ...  |    238      |
+-----------------------------------------------------------+

Com inteiros de 8 bits, o processador calcula produtos escalares diretamente em registradores vetoriais.

CPUs modernas com AVX-512 VNNI / DL Boost usam a instrução _mm512_dpbusd_epi32. Ela processa 64 operações de 8 bits por ciclo de clock.

O que é Product Quantization (PQ) e como opera a distância assimétrica (ADC)?

A Product Quantization (PQ), proposta por Jégou et al. (2011), particiona o espaço vetorial de dimensão D em m subespaços ortogonais. Cada partição é quantizada por centróides K-means, alcançando compressões de 8x a 32x.

O algoritmo divide o vetor original em subvetores de tamanho d = D ÷ m. Para cada subespaço, treina-se um vocabulário com k* = 256 centróides de Voronoi.

O índice do centróide mais próximo em cada partição é armazenado em exatamente um byte (uint8_t).

Estrutura da Tabela de Lookup (LUT) no ADC:

1. Vetor de Consulta em FP32 particionado em m subvetores: y = [y_1, y_2, ..., y_m]
2. Matriz pré-calculada LUT[m][256] residente no cache L1:
   LUT[j][k] = || y_j - Centróide[j][k] ||^2

3. Avaliação de distância para o código PQ x = [c_1, c_2, ..., c_m]:
   dist_ADC(y, x) = LUT[1][c_1] + LUT[2][c_2] + ... + LUT[m][c_m]

Na consulta, o vetor de busca permanece em precisão original FP32. Esse formato é conhecido como Computação de Distância Assimétrica (ADC):

• O motor pré-calcula a distância da consulta para os 256 centróides de cada subespaço, gerando uma Lookup Table (LUT).

• Para m = 64 subespaços, a matriz LUT ocupa apenas 64 KB, cabendo integralmente no cache L1 de dados da CPU.

• A distância para qualquer vetor comprimido resume-se a m leituras na LUT somadas, sem multiplicações de ponto flutuante.

Como a Quantização Binária (BQ) utiliza instruções XOR e POPCNT em hardware?

A Quantização Binária (BQ) projeta cada dimensão em um único bit binário com base no sinal do valor (1 positivo, 0 negativo). Ela reduz o tamanho em 32x e troca aritmética por operações lógicas.

Para vetores normalizados na hiperesfera unitária (||v||_2 = 1), a similaridade angular de cosseno é proporcional à Distância de Hamming.

Esse resultado decorre do teorema de hiperplanos aleatórios de Goemans & Williamson (1995):

Sim_Cosseno(u, v) ≈ cos( π × dist_Hamming(b_u, b_v) ÷ D )

#include <immintrin.h>
#include <stdint.h>

// Distância de Hamming para vetores de 1536 dimensões via AVX-512
uint32_t hamming_distance_avx512_1536d(const uint64_t* a, const uint64_t* b) {
    __m512i accumulator = _mm512_setzero_si512();

    for (int i = 0; i < 3; i++) {
        __m512i vec_a = _mm512_loadu_si512((const __m512i*)(a + i * 8));
        __m512i vec_b = _mm512_loadu_si512((const __m512i*)(b + i * 8));
        __m512i vec_xor = _mm512_xor_si512(vec_a, vec_b);
        __m512i vec_cnt = _mm512_popcnt_epi64(vec_xor);
        accumulator = _mm512_add_epi64(accumulator, vec_cnt);
    }
    return (uint32_t)_mm512_reduce_add_epi64(accumulator);
}

O micro-kernel em C acima calcula a distância em vetores de 1536 dimensões com três registradores de 512 bits. A instrução _mm512_xor_si512 compara 512 dimensões por ciclo, enquanto _mm512_popcnt_epi64 soma os bits diferentes.

Em produção, o BQ opera em uma esteira de busca em duas fases:

• Fase 1 (Filtragem Rápida): O grafo HNSW navega usando representações BQ de 1 bit para selecionar K × 10 candidatos.

• Fase 2 (Re-ranking Exato): Os candidatos recuperados têm suas distâncias recalculadas com precisão FP32 ou FP16 usando vetores em memória ou disco.

A tabela abaixo compara o desempenho das principais técnicas de quantização:

Como funcionam o DiskANN e os grafos Vamana em SSDs NVMe?

A arquitetura DiskANN foi desenvolvida pela Microsoft Research (2019). Ela indexa bilhões de vetores em uma única máquina mantendo o grafo e os dados em SSDs NVMe.

O DiskANN substitui o HNSW multicamada por um grafo único chamado Vamana. Ele utiliza poda com parâmetro α ≥ 1, criando atalhos que reduzem o diâmetro da rede sem exigir skip-lists.

Arquitetura em Camadas do DiskANN:

[ Memória DRAM do Host ]
  +-------------------------------------------------------------+
  |  1. Vetores Comprimidos em Memória (PQ ou SQ8)              |
  |  2. Layout de Roteamento Global (Centróides em RAM)         |
  +-------------------------------------------------------------+
                                |
             Navegação Inicial Orientada por PQ em RAM
                                |
                                v
[ Armazenamento SSD NVMe / Direct I/O (io_uring) ]
  +-------------------------------------------------------------+
  |  Setor de Disco 4KB (Nó do Grafo Vamana):                   |
  |  [ Vetor Bruto Full FP32 (1536d) | Lista de Vizinhos M ]    |
  +-------------------------------------------------------------+

A arquitetura DiskANN distribui a execução entre memória e armazenamento secundário:

• Roteamento em Memória: Os nós do grafo são navegados em DRAM através de representações compactas quantizadas em PQ.

• Setores Alinhados em Disco: Cada bloco de 4 KB no SSD NVMe armazena o vetor FP32 e a lista de adjacências de seus vizinhos.

• I/O Assíncrono com io_uring: Na vizinhança final, o motor emite leituras paralelas diretas via io_uring, buscando vetores originais para o re-ranking.

Essa arquitetura viabiliza 1 bilhão de vetores em servidores com 64 GB de RAM e SSD NVMe, mantendo latências P99 abaixo de 5 ms.

Qual a diferença arquitetural entre pgvector, Qdrant, LanceDB e Milvus?

Os principais motores de busca vetorial adotam filosofias arquiteturais distintas para balancear facilidade operacional, throughput de ingestão e escala de dados.

O pgvector integra a busca vetorial diretamente ao ecossistema ACID do PostgreSQL. Os nós do grafo HNSW residem nas páginas de 8 KB do buffer pool, e as mutações geram registros de Write-Ahead Logging (WAL).

Embora suporte tipos como halfvec (FP16) e bit (1-bit), o custo de locks relacionais e MVCC limita a taxa de ingestão concorrente.

O Qdrant é um motor vetorial nativo implementado em Rust. Ele armazena grafos e dados em memória contígua ou arquivos mapeados via mmap, empregando filtragem direta na navegação do grafo através de bitsets rápidos.

Ele suporta quantização SQ8, PQ e BQ nativas com rescore automático e consenso distribuído via protocolo Raft.

O LanceDB desacopla computação e armazenamento utilizando o formato colunar Lance, baseado em Apache Arrow. O índice opera sobre partições IVF-PQ gravadas em disco ou buckets S3, lendo trechos sem cópias intermediárias (zero-copy).

O Milvus adota uma arquitetura de microsserviços distribuídos em C++ e Go mantida pela LF AI & Data Foundation.

Ele desacopla nós de ingestão (DataNode via Kafka), nós de computação de índices (IndexNode) e nós de execução de consultas (QueryNode no motor Knowhere).

A tabela abaixo sintetiza as características de cada motor:

Como o MaxVision Code estrutura pipelines de busca semântica em código?

O MaxVision Code emprega uma arquitetura híbrida que combina busca vetorial densa com busca léxica BM25 e re-ranking neural. Essa abordagem garante precisão em símbolos exatos de código e ampla cobertura semântica.

Em agentes de código, a busca puramente semântica falha em identificadores literais de funções e variáveis, enquanto a busca textual clássica ignora conceitos descritos em linguagem natural.

Pipeline de Recuperação em Duas Etapas do MaxVision Code:

[ Consulta / Intenção do Agente ]
       |
       +---------------------------------------+
       |                                       |
       v                                       v
[ Ramo Denso: HNSW + SQ8 / BQ ]     [ Ramo Esparso: BM25 / Tantivy ]
       |                                       |
       | Recupera Top-50 Vetorial              | Recupera Top-50 Léxico
       |                                       |
       +-------------------+-------------------+
                           |
                           v
          [ Fusão RRF (Reciprocal Rank Fusion) ]
                           |
                           v
              [ Top-30 Candidatos Fundidos ]
                           |
                           v
        [ Re-Ranker Neural Local / FlashAttention ]
                           |
                           v
          [ Top-5 Trechos Finais de Contexto ]

A esteira de recuperação implementa os seguintes passos:

• Geração Paralela de Candidatos: A consulta é despachada para um índice HNSW com SQ8 e para um índice BM25 invertido.

• Fusão por Ranks Recíprocos (RRF): Os resultados são combinados pela fórmula Score_RRF(d) = ∑_{m} 1 ÷ (60 + rank_m(d)). Essa soma equilibra a pontuação entre os canais densos e esparsos.

• Re-ranking Neural: Os 30 melhores candidatos passam por um modelo local de cross-encoder. Ele seleciona os 5 trechos mais relevantes para o prompt final.

Essa pipeline reduz o tempo até o primeiro token (Time To First Token - TTFT) e maximiza a precisão de contexto fornecida aos agentes.

Conclusão e checklist de engenharia para indexação vetorial em produção

Dimensionar índices vetoriais em produção exige equilibrar memória RAM, largura de banda e latência da aplicação através de diretrizes objetivas:

• Para bases até 1 milhão de vetores no PostgreSQL: Utilize pgvector com tipo halfvec ou SQ8. Configure maintenance_work_mem para 2 GB e ajuste hnsw.ef_search = 100 nas consultas.

• Para microsserviços de baixa latência (5k a 25k QPS): Adote Qdrant com quantização BQ ou SQ8 e re-ranking automático com vetores mapeados em mmap.

• Para volumes acima de 100 milhões de vetores: Utilize LanceDB com partições IVF-PQ em SSD NVMe ou implementações baseadas em DiskANN.

• Sempre implemente recuperação híbrida (Denso + BM25 via RRF): A combinação de grafos HNSW com indexação léxica previne alucinações. Ela garante a captura de identificadores exatos em bases de código.

Perguntas Frequentes (FAQ)

Como o algoritmo HNSW evita mínimos locais durante a busca?

O HNSW utiliza busca multicamada inspirada em skip-lists. As camadas superiores possuem arestas longas que atravessam grandes distâncias no espaço métrico, posicionando o ponto de entrada próximo ao cluster correto antes de descer para as conexões curtas e densas da camada base.

Por que a busca em grafos HNSW causa alta taxa de cache misses na CPU?

A navegação por saltos em grafos vetoriais impõe acessos estocásticos à memória. Como os vetores dos nós vizinhos raramente residem de forma contígua no heap, cada cálculo métrico força buscas que excedem o L3 cache, transformando a latência de DRAM no principal gargalo de execução.

Quando vale a pena utilizar Binary Quantization (BQ) em vez de SQ8?

A quantização binária é ideal para modelos com alta dimensionalidade (D ≥ 1024) e cenários que exigem vazão extrema (acima de 10.000 QPS). Ela reduz o consumo de memória em 32x e utiliza instruções SIMD como XOR e POPCNT para filtragem rápida, exigindo uma segunda fase de re-ranking exato para preservar o recall acima de 98%.

Qual a principal diferença arquitetural entre pgvector e Qdrant?

O pgvector opera como extensão do PostgreSQL acoplada ao subsistema de páginas de 8 KB, MVCC e WAL, sendo ideal para simplificar a infraestrutura até 1 milhão de vetores. O Qdrant é um motor nativo em Rust que opera com vetores contíguos em memória ou mmap, suportando filtragem de metadados integrada diretamente no grafo e alcançando throughput até dez vezes superior.

Como o DiskANN viabiliza busca vetorial em bilhões de vetores sem saturar a DRAM?

O DiskANN utiliza o grafo plano Vamana armazenado em SSDs NVMe e mantém apenas centróides e vetores quantizados em memória RAM. As consultas utilizam leituras assíncronas em disco para carregar somente as listas de vizinhos dos nós visitados durante a travessia.