Otimização do NVIDIA CAGRA no Milvus: uma abordagem híbrida GPU-CPU para uma indexação mais rápida e consultas mais baratas

À medida que os sistemas de IA passam das experiências para a infraestrutura de produção, as bases de dados vectoriais já não lidam com milhões de embeddings. Os biliões são agora rotina e as dezenas de biliões são cada vez mais comuns. A esta escala, as escolhas algorítmicas afectam não só o desempenho e a recordação, mas também se traduzem diretamente no custo da infraestrutura.

Isto leva a uma questão central para implementações em grande escala: como escolher o índice certo para fornecer uma recuperação e latência aceitáveis sem deixar que a utilização de recursos de computação fique fora de controlo?

Os índices baseados em gráficos, como NSW, HNSW, CAGRA e Vamana, tornaram-se a resposta mais amplamente adotada. Ao navegar em grafos de vizinhança pré-construídos, estes índices permitem uma pesquisa rápida do vizinho mais próximo à escala de mil milhões, evitando a pesquisa de força bruta e a comparação de cada vetor com a consulta.

No entanto, o perfil de custos desta abordagem é desigual. Consultar um grafo é relativamente barato; construí-lo não é. Construir um gráfico de alta qualidade requer cálculos de distância em grande escala e refinamento iterativo em todo o conjunto de dados - cargas de trabalho que os recursos tradicionais da CPU lutam para lidar de forma eficiente à medida que os dados crescem.

O CAGRA da NVIDIA aborda esse gargalo usando GPUs para acelerar a construção de gráficos por meio de paralelismo massivo. Embora isso reduza significativamente o tempo de construção, contar com GPUs para a construção de índices e para o atendimento de consultas introduz restrições de custo e escalabilidade mais altas em ambientes de produção.

Para equilibrar estes compromissos, o Milvus 2.6.1 adopta um design híbrido para os índices GPU_CAGRA: As GPUs são usadas apenas para a construção de gráficos, enquanto a execução de consultas é executada em CPUs. Isso preserva as vantagens de qualidade dos gráficos construídos por GPU e, ao mesmo tempo, mantém o serviço de consulta escalonável e econômico - o que o torna especialmente adequado para cargas de trabalho com atualizações de dados pouco frequentes, grandes volumes de consulta e sensibilidade estrita a custos.

O que é o CAGRA e como ele funciona?

Os índices vetoriais baseados em grafos geralmente se enquadram em duas categorias principais:

• Construção iterativa de grafos, representada pelo CAGRA (já suportado no Milvus).

• Construção de gráficos baseada em inserção, representada pelo Vamana (atualmente em desenvolvimento no Milvus).

Essas duas abordagens diferem significativamente em seus objetivos de projeto e fundamentos técnicos, tornando cada uma adequada para diferentes escalas de dados e padrões de carga de trabalho.

O NVIDIA CAGRA (CUDA ANN Graph-based) é um algoritmo nativo da GPU para pesquisa aproximada do vizinho mais próximo (ANN), concebido para construir e consultar gráficos de proximidade em grande escala de forma eficiente. Ao aproveitar o paralelismo da GPU, o CAGRA acelera significativamente a construção de gráficos e oferece desempenho de consulta de alto rendimento em comparação com abordagens baseadas em CPU, como o HNSW.

O CAGRA é construído com base no algoritmo NN-Descent (Nearest Neighbor Descent), que constrói um grafo de k vizinhos mais próximos (kNN) por meio de refinamento iterativo. Em cada iteração, os vizinhos candidatos são avaliados e actualizados, convergindo gradualmente para relações de vizinhança de maior qualidade em todo o conjunto de dados.

Depois de cada ronda de refinamento, o CAGRA aplica técnicas adicionais de poda do gráfico - como a poda de desvio de 2 saltos - pararemover arestas redundantes, preservando a qualidade da pesquisa. Essa combinação de refinamento e poda iterativos resulta em um gráfico compacto, mas bem conectado, que é eficiente para percorrer no momento da consulta.

Através do refinamento e da poda repetidos, o CAGRA produz uma estrutura de grafo que suporta uma pesquisa do vizinho mais próximo de alta recuperação e baixa latência em grande escala, o que o torna particularmente adequado para conjuntos de dados estáticos ou actualizados com pouca frequência.

Etapa 1: Construindo o gráfico inicial com NN-Descent

O NN-Descent é baseado em uma observação simples, mas poderosa: se o nó u é vizinho de v e o nó w é vizinho de u, então w muito provavelmente também é vizinho de v. Esta propriedade transitiva permite que o algoritmo descubra os verdadeiros vizinhos mais próximos de forma eficiente, sem comparar exaustivamente cada par de vectores.

O CAGRA usa o NN-Descent como seu algoritmo principal de construção de grafos. O processo funciona da seguinte forma:

1. Inicialização aleatória: Cada nó começa com um pequeno conjunto de vizinhos selecionados aleatoriamente, formando um grafo inicial aproximado.

2. Expansão de vizinhos: Em cada iteração, um nó reúne os seus vizinhos actuais e os vizinhos destes para formar uma lista de candidatos. O algoritmo calcula as semelhanças entre o nó e todos os candidatos. Uma vez que a lista de candidatos de cada nó é independente, estes cálculos podem ser atribuídos a blocos de threads GPU separados e executados em paralelo a uma escala maciça.

3. Atualização da lista de candidatos: Se o algoritmo encontrar candidatos mais próximos do que os actuais vizinhos do nó, troca os vizinhos mais distantes e actualiza a lista kNN do nó. Ao longo de várias iterações, este processo produz um gráfico kNN aproximado de qualidade muito superior.

4. Verificação da convergência: À medida que as iterações avançam, ocorrem menos actualizações de vizinhos. Quando o número de conexões atualizadas cai abaixo de um limite definido, o algoritmo pára, indicando que o gráfico efetivamente se estabilizou.

Como a expansão de vizinhos e a computação de similaridade para nós diferentes são totalmente independentes, o CAGRA mapeia a carga de trabalho NN-Descent de cada nó para um bloco de thread de GPU dedicado. Esse projeto permite um paralelismo maciço e torna a construção de gráficos muito mais rápida do que os métodos tradicionais baseados em CPU.

Etapa 2: podando o gráfico com desvios de 2 saltos

Após a conclusão do NN-Descent, o gráfico resultante é preciso, mas excessivamente denso. O NN-Descent mantém intencionalmente vizinhos candidatos extras, e a fase de inicialização aleatória introduz muitas arestas fracas ou irrelevantes. Como resultado, cada nó geralmente acaba com um grau duas vezes - ou até várias vezes - maior do que o grau desejado.

Para produzir um grafo compacto e eficiente, o CAGRA aplica a poda de desvio de 2 saltos.

A ideia é simples: se o nó A pode alcançar o nó B indiretamente através de um vizinho partilhado C (formando um caminho A → C → B), e a distância deste caminho indireto é comparável à distância direta entre A e B, então a aresta direta A → B é considerada redundante e pode ser removida.

Uma das principais vantagens desta estratégia de poda é que a verificação da redundância de cada aresta depende apenas da informação local - as distâncias entre os dois pontos finais e os seus vizinhos partilhados. Como cada aresta pode ser avaliada independentemente, a etapa de poda é altamente paralelizável e se encaixa naturalmente na execução em lote da GPU.

Como resultado, o CAGRA pode podar o gráfico de forma eficiente em GPUs, reduzindo a sobrecarga de armazenamento em 40-50%, preservando a precisão da pesquisa e melhorando a velocidade de travessia durante a execução da consulta.

GPU_CAGRA em Milvus: o que há de diferente?

Embora as GPUs ofereçam grandes vantagens de desempenho para a construção de gráficos, os ambientes de produção enfrentam um desafio prático: Os recursos da GPU são muito mais caros e limitados do que os das CPUs. Se a construção de índices e a execução de consultas dependerem exclusivamente de GPUs, vários problemas operacionais surgirão rapidamente:

• Baixa utilização de recursos: O tráfego de consultas é muitas vezes irregular e intermitente, deixando as GPUs inactivas durante longos períodos e desperdiçando a dispendiosa capacidade de computação.

• Alto custo de implantação: Atribuir uma GPU a cada instância de serviço de consulta aumenta os custos de hardware, mesmo que a maioria das consultas não utilize totalmente o desempenho da GPU.

• Escalabilidade limitada: O número de GPUs disponíveis limita diretamente o número de réplicas de serviço que pode executar, restringindo a sua capacidade de escalar com a procura.

• Flexibilidade reduzida: Quando a criação e a consulta de índices dependem de GPUs, o sistema fica vinculado à disponibilidade de GPUs e não pode mudar facilmente as cargas de trabalho para CPUs.

Para resolver estas restrições, o Milvus 2.6.1 introduz um modo de implementação flexível para o índice GPU_CAGRA através do parâmetro adapt_for_cpu. Este modo permite um fluxo de trabalho híbrido: O CAGRA usa a GPU para construir um índice gráfico de alta qualidade, enquanto a execução da consulta é executada na CPU - normalmente usando o HNSW como algoritmo de pesquisa.

Nesta configuração, as GPUs são usadas onde fornecem o maior valor - construção de índice rápida e de alta precisão - enquanto as CPUs lidam com cargas de trabalho de consulta em grande escala de uma forma muito mais económica e escalável.

Como resultado, essa abordagem híbrida é particularmente adequada para cargas de trabalho em que:

• As actualizações de dados são pouco frequentes, pelo que as reconstruções de índices são raras

• O volume de consultas é elevado, exigindo muitas réplicas económicas

• A sensibilidade aos custos é elevada e a utilização de GPU deve ser rigorosamente controlada

Compreensão adapt_for_cpu

No Milvus, o parâmetro adapt_for_cpu controla a forma como um índice CAGRA é serializado para o disco durante a construção do índice e como é desserializado para a memória no momento do carregamento. Ao alterar essa configuração no momento da construção e no momento do carregamento, o Milvus pode alternar de forma flexível entre a construção de índice baseada em GPU e a execução de consulta baseada em CPU.

Diferentes combinações de adapt_for_cpu em tempo de construção e tempo de carga resultam em quatro modos de execução, cada um projetado para um cenário operacional específico.

Tempo de construção (adapt_for_cpu)	Tempo de carregamento (adapt_for_cpu)	Lógica de execução	Cenário recomendado
verdadeiro	verdadeiro	Construir com GPU_CAGRA → serializar como HNSW → desserializar como HNSW → consulta à CPU	Cargas de trabalho sensíveis ao custo; serviço de consultas em grande escala
verdadeiro	falso	Construir com GPU_CAGRA → serializar como HNSW → desserializar como HNSW → consulta à CPU	As consultas subsequentes voltam para a CPU quando ocorrem incompatibilidades de parâmetros
falso	verdadeiro	Construir com GPU_CAGRA → serializar como CAGRA → deserializar como HNSW → consulta à CPU	Mantém o índice CAGRA original para armazenamento enquanto permite uma pesquisa temporária na CPU
falso	falso	Construir com GPU_CAGRA → serializar como CAGRA → desserializar como CAGRA → consulta à GPU	Cargas de trabalho de desempenho crítico em que o custo é secundário

Nota: O mecanismo adapt_for_cpu suporta apenas conversão unidirecional. Um índice CAGRA pode ser convertido em HNSW porque a estrutura do grafo CAGRA preserva todas as relações de vizinhança de que o HNSW necessita. No entanto, um índice HNSW não pode ser convertido de volta para CAGRA, pois não possui as informações estruturais adicionais necessárias para a consulta baseada em GPU. Como resultado, as definições de tempo de construção devem ser selecionadas cuidadosamente, tendo em consideração a implementação a longo prazo e os requisitos de consulta.

Colocando GPU_CAGRA à prova

Para avaliar a eficácia do modelo de execução híbrido - usando GPUs para construção de índices e CPUs para execução de consultas - realizamos uma série de experiências controladas em um ambiente padronizado. A avaliação se concentra em três dimensões: desempenho da construção do índice, desempenho da consulta e precisão da recuperação.

Configuração experimental

As experiências foram realizadas em hardware padrão da indústria, amplamente adotado, para garantir que os resultados permanecem fiáveis e amplamente aplicáveis.

• CPU: Processador MD EPYC 7R13 (16 cpus)

• GPU: NVIDIA L4

1. Desempenho da construção do índice

Comparamos o CAGRA construído na GPU com o HNSW construído na CPU, sob o mesmo grau de gráfico alvo de 64.

Principais conclusões

• O CAGRA da GPU constrói índices de 12 a 15 vezes mais rápido que o HNSW da CPU. Tanto no Cohere1M quanto no Gist1M, o CAGRA baseado em GPU supera significativamente o HNSW baseado em CPU, destacando a eficiência do paralelismo da GPU durante a construção do gráfico.

• O tempo de construção aumenta linearmente com as iterações NN-Descent. À medida que o número de iterações aumenta, o tempo de construção cresce de forma quase linear, reflectindo a natureza de refinamento iterativo do NN-Descent e proporcionando um compromisso previsível entre o custo de construção e a qualidade do gráfico.

2. Desempenho da consulta

Nesta experiência, o gráfico CAGRA é construído uma vez na GPU e depois consultado usando dois caminhos de execução diferentes:

• Consulta na CPU: o índice é desserializado para o formato HNSW e pesquisado na CPU

• Consulta na GPU: a pesquisa é executada diretamente no gráfico CAGRA utilizando a passagem baseada na GPU

Principais conclusões

• A taxa de transferência da pesquisa da GPU é de 5 a 6 vezes maior que a da CPU. Tanto no Cohere1M como no Gist1M, a travessia baseada em GPU proporciona QPS substancialmente mais elevados, realçando a eficiência da navegação paralela em grafos nas GPUs.

• A recordação aumenta com as iterações NN-Descent e depois atinge um patamar. À medida que o número de iterações de construção cresce, a recuperação melhora tanto para consultas em CPU quanto em GPU. No entanto, para além de um certo ponto, as iterações adicionais produzem ganhos decrescentes, indicando que a qualidade do gráfico convergiu em grande medida.

3. Precisão da recuperação

Nesta experiência, tanto o CAGRA como o HNSW são consultados na CPU para comparar a recuperação em condições de consulta idênticas.

Principais conclusões

O CAGRA alcança maior recall do que o HNSW em ambos os conjuntos de dados, mostrando que, mesmo quando um índice CAGRA é construído na GPU e desserializado para pesquisa na CPU, a qualidade do gráfico é bem preservada.

O que vem a seguir: Escalonando a construção de índices com a Vamana

A abordagem híbrida GPU-CPU da Milvus oferece uma solução prática e econômica para as cargas de trabalho atuais de pesquisa vetorial em larga escala. Ao construir gráficos CAGRA de alta qualidade em GPUs e atender consultas em CPUs, ele combina a construção rápida de índices com a execução de consultas escalonável e acessível - particularmenteadequada para cargas de trabalho com atualizações pouco frequentes, altos volumes de consulta e restrições rígidas de custo.

Em escalas ainda maiores - dezenasou centenas de milhares de milhões de vectores -a própria construção deíndicestorna-se o gargalo. Quando o conjunto de dados completo não cabe mais na memória da GPU, o setor normalmente recorre a métodos de construção de gráficos baseados em inserção, como o Vamana. Em vez de construir o gráfico de uma só vez, o Vamana processa os dados em lotes, inserindo novos vectores de forma incremental, mantendo a conetividade global.

Seu pipeline de construção segue três etapas principais:

1. Crescimento geométrico do lote - começando com pequenos lotes para formar um esqueleto do gráfico, depois aumentando o tamanho do lote para maximizar o paralelismo e, finalmente, usando grandes lotes para refinar os detalhes.

2. Inserção gulosa - cada novo nó é inserido navegando a partir de um ponto de entrada central, refinando iterativamente o seu conjunto de vizinhos.

3. Actualizações de arestas para trás - adição de ligações inversas para preservar a simetria e garantir uma navegação eficiente no grafo.

A poda é integrada diretamente no processo de construção utilizando o critério α-RNG: se um candidato a vizinho v já estiver coberto por um vizinho existente p′ (ou seja, d(p′, v) < α × d(p, v)), então v é podado. O parâmetro α permite um controlo preciso da esparsidade e da precisão. A aceleração da GPU é conseguida através do paralelismo em lote e do escalonamento geométrico do lote, estabelecendo um equilíbrio entre a qualidade do índice e o rendimento.

Em conjunto, estas técnicas permitem às equipas lidar com o rápido crescimento de dados e actualizações de índices em grande escala sem se depararem com limitações de memória da GPU.

A equipa da Milvus está a desenvolver ativamente o suporte da Vamana, com um lançamento previsto para o primeiro semestre de 2026. Fique atento.

Tem dúvidas ou quer um mergulho profundo em qualquer recurso do Milvus mais recente? Junte-se ao nosso canal Discord ou arquive problemas no GitHub. Você também pode reservar uma sessão individual de 20 minutos para obter insights, orientações e respostas às suas perguntas por meio do Milvus Office Hours.

Saiba mais sobre os recursos do Milvus 2.6

• Apresentando Milvus 2.6: Pesquisa Vetorial Acessível em Escala de Bilhões

• Apresentando a função Embedding: Como o Milvus 2.6 agiliza a vetorização e a busca semântica

• JSON Shredding no Milvus: Filtragem JSON 88,9x mais rápida com flexibilidade

• Desbloqueando a verdadeira recuperação em nível de entidade: Novas capacidades de Array-of-Structs e MAX_SIM em Milvus

• MinHash LSH em Milvus: A arma secreta para combater duplicatas em dados de treinamento LLM

• Leve a compressão vetorial ao extremo: como o Milvus atende a 3× mais consultas com o RaBitQ

• Os benchmarks mentem - os bancos de dados vetoriais merecem um teste real

• Substituímos o Kafka/Pulsar por um Woodpecker para o Milvus