- A busca baseada em embeddings de vetor único é rápida e eficiente, mas recentemente modelos multivetoriais como o ColBERT passaram a oferecer significado mais rico e maior precisão com vários vetores por token
- A abordagem multivetorial aumenta fortemente o volume de computação e o custo de busca devido a cálculos complexos de similaridade, como a Chamfer similarity, tornando-se um obstáculo para buscas em tempo real em larga escala
- O MUVERA, proposto pela equipe de pesquisa do Google, compacta a informação multivetorial em vetores de tamanho fixo (FDE, Fixed Dimensional Encoding), permitindo busca ultrarrápida com MIPS (Maximum Inner Product Search) baseada em vetor único e posterior reordenação
- A abordagem é independente dos dados e oferece base teórica (garantia de erro de aproximação da Chamfer similarity), alcançando mais de 90% de redução de latência e mais de 10% de melhora em recall em relação ao PLAID
- O FDE também oferece suporte a compressão (redução de memória em 32x), e a implementação open source e o artigo já foram publicados, o que a torna adequada para adoção em serviços reais de busca, recomendação e NLP
A evolução dos modelos de embedding e da recuperação de informação
- Modelos de embedding baseados em deep learning são uma ferramenta central para encontrar rapidamente informações relevantes em grandes conjuntos de dados (documentos, imagens, vídeos etc.) a partir de consultas do usuário (por exemplo: “qual a altura do Everest”)
- Ao converter cada ponto de dado em um embedding de vetor único, o sistema é projetado para que dados semanticamente semelhantes tenham estruturas vetoriais numericamente parecidas
- Usando o cálculo de similaridade por produto interno entre vetores, é possível obter alto desempenho de busca com algoritmos de MIPS (Maximum Inner Product Search)
- No entanto, modelos multivetoriais recentes como o ColBERT vêm ganhando atenção por sua maior precisão de busca e capacidade de capturar relações complexas
A adoção dos modelos multivetoriais e seus limites
- Modelos multivetoriais representam cada ponto de dado como um conjunto de múltiplos vetores de embedding
- Eles usam funções de similaridade compostas, como a Chamfer similarity, para capturar com precisão informações e relações que os vetores únicos tradicionais não conseguiam representar
- Graças a isso, tornam possível uma recuperação de informação mais precisa e recomendações de documentos mais relevantes
- Como desvantagem, o aumento do número de embeddings e a complexidade do cálculo de similaridade elevam bastante os recursos computacionais exigidos pela busca
- aumento do número de vetores por token → grande aumento em computação e memória
- operações não lineares (multiplicação de matrizes) são indispensáveis → busca sublinear (ultrarrápida) baseada em vetor único torna-se inviável
- em serviços de larga escala, custo e latência disparam
MUVERA: revolucionando a busca multivetorial com FDE
- O artigo “MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings” propõe um novo algoritmo para superar esse problema de eficiência
- O MUVERA converte a informação multivetorial em um único vetor FDE, aproveitando a infraestrutura já existente de índices/servidores MIPS para realizar busca rápida de candidatos
- Geração de FDE: converte os conjuntos multivetoriais de consulta e documento em vetores de tamanho fixo (FDE) por meio de um mapeamento independente dos dados
- Busca MIPS: armazena o FDE de todos os documentos em um índice MIPS e usa o FDE da consulta para localizar candidatos em altíssima velocidade
- Reordenação com garantia de precisão: aplica a operação multivetorial original, como a Chamfer similarity, apenas aos documentos candidatos, entregando o resultado final com reordenação precisa
- O FDE pode ser aplicado independentemente do conjunto de dados e também é vantajoso em ambientes dinâmicos, como streaming
Base teórica
- Inspirado em algoritmos geométricos avançados, como probabilistic tree embedding, o FDE aproxima fortemente a similaridade multivetorial
- O espaço de embedding é particionado aleatoriamente, e a similaridade aproximada é calculada quando os vetores de consulta/documento ficam na mesma seção
- O artigo apresenta teoria e dados experimentais que garantem a aproximação dentro de uma faixa de erro da Chamfer similarity
Resultados experimentais e desempenho
- O desempenho do MUVERA foi validado em vários grandes datasets de IR, incluindo o benchmark BEIR
- em comparação com o PLAID e outros métodos existentes, alcançou recall médio 10% maior
- redução de mais de 90% na latência de busca
- para o mesmo recall, o número de documentos candidatos baseado em FDE foi reduzido em 5 a 20 vezes em relação aos métodos anteriores
- boa compatibilidade com técnicas adicionais de compressão, como Product Quantization (redução de memória em 32x)
- A praticidade da busca multivetorial melhora significativamente, tornando-a adequada para aplicações de busca, recomendação e NLP em larga escala
Conclusão e aplicações
- O MUVERA é uma abordagem inovadora para acelerar a busca multivetorial ao nível da busca por vetor único
- A implementação open source (link do GitHub), o artigo e os resultados experimentais já estão disponíveis publicamente
- Uma alternativa prática para aumentar a eficiência da busca multivetorial em motores de busca, sistemas de recomendação e processamento de linguagem natural
- Com pesquisas e otimizações futuras, espera-se que possa ser aplicada de forma ainda mais ampla em diferentes setores
1 comentários
Comentários no Hacker News
Compartilha a experiência recente de adicionar o Muvera ao Weaviate e os links do blog e do podcast. Menciona que, na abordagem multi-vector no estilo ColBERT, o custo explode quando se faz embedding por token. Por exemplo, em vez de um vetor tradicional de 768 dimensões, isso pode crescer para 16.640 dimensões ou mais, o que se torna um peso irrealista em várias situações. O Muvera converte vários vetores em um único vetor de dimensão fixa, geralmente com menos dimensões, que pode ser usado diretamente em qualquer índice ANN. Como usa um vetor único, também permite aplicar algoritmos existentes e várias técnicas de quantização, economizando memória. Ao contrário do PLAID, não exige uma estrutura de índice específica nem hipóteses de clustering, o que também traz a vantagem de menor latência
Menciona uma tendência recente de se afastar da abordagem de fazer mean-pooling para gerar um único embedding. Como lidar com embeddings por token individualmente gera vetores demais, aponta a necessidade de uma forma adequada de reduzi-los. Esse método faz clustering dos embeddings de token em partições arbitrárias, aplica mean-pooling em cada grupo e depois concatena tudo em um embedding de tamanho fixo. Como uma comparação totalmente multi-vector é difícil em termos de performance, eles fazem clustering em k vetores e concatenam para permitir comparação com ferramentas e desempenho de vetor único. No fim, como o número de partições é fixo, isso produz um efeito de clustering de embeddings de token no estilo k-means. Também sugere que, se os tokens fossem clusterizados dinamicamente, poderia haver embeddings com número variável de componentes e talvez resultados melhores
Compartilha a experiência de que esse método foi muito sensível a hiperparâmetros e, em seus experimentos, não conseguiu desempenho parecido com o maxsim
Entendeu que o Muvera calcula o FDE (Fixed Dimensional Embedding) da consulta e então procura FDEs semelhantes no dataset do modelo, e pergunta se, nesse caso, também seria necessário calcular todos os FDEs do mesmo tamanho para o modelo inteiro
Diz que não conhece bem essa área, mas pergunta se consultas com embeddings neurais funcionam da mesma forma que uma query SQL que retorna todos os nomes de uma tabela, ou se os resultados acabam sendo mais ambíguos
Resume a abordagem como uma tentativa de comprimir essencialmente vários embeddings em um só, ou seja, um “embedding de embeddings”, para reduzir dimensionalidade e melhorar performance. Como vários embeddings contêm informações muito sobrepostas, considera que, se for possível comprimi-los em um só, o valor adicional trazido pelos embeddings extras provavelmente é baixo. Se a performance for parecida, questiona se isso poderia ser representado sem perda do ponto de vista da teoria da informação
Pergunta qual é a diferença em relação ao método tradicional de feature hash, que reduz vários embeddings a um só, e se técnicas de redução de dimensionalidade de vetor único, como UMAP, poderiam ajudar