Resumo Técnico: Clark Hash

Declaração do Problema

Sistemas de incorporação neural frequentemente exigem o armazenamento de vastas quantidades de vetores densos em ponto flutuante. Uma incorporação de frase padrão com 384 dimensões no formato f32 consome 1.536 bytes por vetor, criando custos significativos para memória, cache local, armazenamento em disco e transferência de rede. Embora métodos de compressão existentes (como quantização de produto) possam alcançar alta qualidade, eles geralmente dependem da aprendizagem de centróides, rotações ou dicionários de códigos a partir de um corpus representativo. Essas abordagens são inadequadas para cenários "online" onde os vetores chegam individualmente e devem ser armazenados imediatamente, sem acesso a um conjunto de treinamento pré-existente ou estatísticas de corpus.

Metodologia

Clark Hash é um codec determinístico e sem estado projetado para comprimir incorporações neurais sem uma fase de treinamento. Ele combina três técnicas estabelecidas: projeção esparsa e assinada de Johnson-Lindenstrauss (JL), quantização escalar fixa e pontuação assimétrica. O processo opera da seguinte forma:

1. Normalização: Para busca por cosseno, o vetor de entrada $x$ é normalizado para uma direção unitária $u = x / \|x\|_2$.
2. Projeção Esparsa e Assinada: O vetor é projetado em um espaço de esboço de dimensão inferior ($m$ dimensões) usando uma matriz aleatória esparsa $R$. Esta matriz é construída via hash de características, onde as coordenadas de entrada são mapeadas para buckets com sinais aleatórios ($\sigma \in \{-1, +1\}$). A projeção é cega aos dados e determinística dado um seed.
   • A projeção é escalonada por $\sqrt{m}$ para estabilizar as magnitudes das coordenadas para quantização.
3. Quantização Escalar Fixa: As coordenadas projetadas são limitadas a um intervalo simétrico $[-c, c]$ e quantizadas uniformemente para $b$ bits. Isso produz um código inteiro de largura fixa.
4. Pontuação Assimétrica: Os vetores de consulta permanecem no formato de ponto flutuante. Eles são projetados no mesmo espaço de esboço (sem quantização) e pontuados contra os esboços quantizados do banco de dados armazenados usando um produto interno assimétrico. Isso evita erro de quantização no lado da consulta.
5. Extensão de Produto Escalar: Para métricas de produto escalar, um canal lateral de log-norm de dois bytes é adicionado para armazenar a magnitude do vetor original, permitindo a reconstrução do produto escalar a partir da estimativa de cosseno e das normas.

A implementação é um crate Rust sem estado (clark-hash), onde as localizações dos buckets e os sinais são gerados sob demanda usando uma função de hash estilo SplitMix64 baseada no índice de entrada e em um seed.

Contribuições Principais

O artigo apresenta Clark Hash não como um novo teorema matemático, mas como um pacote de engenharia que integra conceitos existentes em uma solução compacta e sem estado. Suas contribuições primárias são:

• Codificação Online Sem Estado: A capacidade de codificar vetores individualmente sem estatísticas de corpus prévias, dicionários de códigos aprendidos ou parâmetros de calibração.
• Compressão Extrema: Na configuração padrão para incorporações de 384 dimensões, o método reduz o armazenamento de 1.536 bytes para 48 bytes (uma redução de 32x).
• Codec Determinístico: Uma representação quantizada escalar de largura fixa que permite a varredura exata de vetores comprimidos no espaço de esboço.
• Implementação: Uma implementação de referência em Rust e um conjunto de testes de benchmark disponíveis para uso público.

Resultados

O método foi avaliado em tarefas de similaridade de frases multilíngues usando 9.304 pares rotulados de 29 subconjuntos (STS17 e STS22 via MTEB). A avaliação comparou pontuações de cosseno densas contra pontuações de esboço Clark Hash usando codificadores da família MiniLM.

• Eficiência de Armazenamento: O perfil padrão ($m=96, b=4$) armazena vetores em 48 bytes.
• Correlação com Pontuações Densas:
  • No STS17 com o modelo multilíngue MultiMiniLM-L12, os esboços de 48 bytes alcançaram uma correlação de Pearson macro de 0,9099 com as pontuações de cosseno densas.
  • No STS22, a correlação atingiu 0,9460.
• Desempenho: As etapas de quantização e pontuação são computacionalmente negligenciáveis em comparação com a etapa de geração de incorporação. Por exemplo, quantizar 17.000 frases únicas levou aproximadamente 0,025 segundos, enquanto a pontuação levou 0,005 segundos.
• Dependência do Modelo: Os resultados indicam que a qualidade do esboço depende fortemente do modelo de incorporação subjacente. Quando o modelo (por exemplo, all-MiniLM-L6-v2) não era bem adequado para dados multilíngues, a linha de base densa já era fraca, e o esboço adicionou perda adicional.

Significado e Limitações

Os autores posicionam Clark Hash como um codec de armazenamento simples e um método de pontuação de esboço, afirmando explicitamente que não é um substituto para índices de vizinho mais próximo aproximado (ANN) (como HNSW) ou quantizadores aprendidos (como Quantização de Produto).

• Significado: Oferece uma solução prática para cenários que exigem armazenamento compacto e determinístico de incorporações onde os vetores chegam online e nenhum conjunto de treinamento está disponível. Preserva uma grande parte do comportamento de pontuação densa (alta correlação de Pearson) quando o modelo de incorporação se ajusta bem aos dados.
• Limitações:
  • Não se adapta ao corpus, potencialmente resultando em qualidade inferior a métodos aprendidos com o mesmo orçamento de bytes.
  • Não é um índice ANN; o FlatIndex incluído realiza varreduras exatas no espaço de esboço, o que pode não escalar para conjuntos de dados de produção massivos sem estruturas de indexação adicionais.
  • A dimensão fixa do esboço não pode preservar cada par em um fluxo ilimitado; os usuários devem ajustar parâmetros ($m, b, s, c$) com base em seus objetivos de qualidade específicos.

Em conclusão, Clark Hash fornece um "método pequeno" para armazenar incorporações neurais que troca a adaptação específica ao corpus pela simplicidade sem estado e eficiência extrema de armazenamento.