Resumo Técnico: Hash de Colisão Zero com Múltiplas Probes (MPZCH)

1. Declaração do Problema

Sistemas de recomendação em grande escala dependem de tabelas de incorporação (embedding tables) para mapear características categóricas de alta cardinalidade (por exemplo, IDs de usuários, IDs de itens) em representações vetoriais densas. No entanto, à medida que o volume de IDs únicos cresce, os métodos tradicionais de indexação baseados em hash enfrentam dois desafios críticos:

1. Colisões de Incorporação: Devido a restrições de memória, o "truque de hash" mapeia múltiplos IDs distintos para o mesmo índice. Quando usuários ou itens não relacionados compartilham um vetor de incorporação, isso confunde seus significados, degradando o desempenho do modelo e a qualidade da personalização.
2. Obsolescência do Modelo e Transferência Negativa: Em ambientes dinâmicos, novos itens frequentemente colidem com slots ocupados por IDs obsoletos e desatualizados. Os métodos de hash padrão carecem de mecanismos para aposentar esses IDs antigos. Consequentemente, novos itens "herdam" incorporações pré-treinadas de entidades não relacionadas, forçando o modelo a desaprender ruído antes de convergir para sinais úteis. Essa "transferência negativa" impede a aprendizagem de representações precisas para novos recursos.

Embora o aumento do tamanho da tabela reduza a probabilidade de colisão, não é possível eliminá-las completamente devido aos limites de memória, e algoritmos de hash padrão ainda podem produzir colisões significativas mesmo com tabelas grandes.

2. Metodologia: MPZCH

Os autores propõem o Hash de Colisão Zero com Múltiplas Probes (MPZCH), um mecanismo de indexação inovador implementado como um kernel CUDA de alto desempenho. Ele combina sondagem linear (linear probing) com gerenciamento de estado auxiliar para mitigar colisões e gerenciar ativamente os ciclos de vida dos IDs.

2.1 Componentes Principais

• Tensores Auxiliares: O MPZCH mantém dois tensores ao lado da tabela de incorporação:
  • Tensor de Identidades: Registra o ID específico que ocupa cada slot (inicializado como -1). Isso permite que o kernel distinga estritamente entre slots ocupados e disponíveis.
  • Tensor de Metadados: Armazena informações auxiliares, como valores de Tempo de Vida (TTL) ou carimbos de data e hora, para orientar decisões de expulsão.
• Sondagem Linear em Duas Passagens: Para garantir consistência e prevenir armazenamento duplicado ou expulsão prematura, o kernel executa uma varredura em duas passagens para cada ID:
  1. Passagem 1 (Descoberta): Varre o intervalo de sondagem para determinar se o ID já existe. Nenhuma operação de escrita ocorre.
  2. Passagem 2 (Ação): Com base nos resultados da Passagem 1:
     • Atualização: Se o ID existir, os metadados (por exemplo, carimbo de data e hora) são atualizados.
     • Alocação: Se o ID for novo, o kernel tenta encontrar um slot vazio ou expulsar uma entrada expirada.
     • Fallback de Colisão: Se nenhum slot vazio ou expulsável for encontrado dentro do intervalo de sondagem, o sistema recorre ao slot de hash inicial (embora, com dimensionamento adequado da tabela e profundidade de sondagem, isso seja raro).

2.2 Estratégias de Expulsão e Frescor

O MPZCH introduz políticas de expulsão configuráveis para gerenciar a capacidade da tabela e garantir o frescor:

• Política TTL (Tempo de Vida): Slots são marcados como expirados se o carimbo de data e hora de seus metadados ficar abaixo do carimbo de data e hora atual do treinamento. A expulsão é preguiçosa (lazy), acionada apenas quando um novo ID requer alocação.
• Política LRU (Menos Recente Usado): O kernel varre o intervalo de sondagem para expulsar a entrada com o carimbo de data e hora mais antigo.
• Redefinição do Otimizador: Crucialmente, ao expulsar, tanto os pesos da incorporação quanto o estado do otimizador (por exemplo, momento) são redefinidos. Isso impede que novos itens herdem incorporações desatualizadas, garantindo que aprendam do zero.

2.3 Integração do Sistema

• Integração com TorchRec: O MPZCH é projetado para integração perfeita com a biblioteca TorchRec da Meta. Os tensores de identidade e metadados são particionados por linhas (row-wise sharded) através dos ranks para corresponder à tabela de incorporação, garantindo que todas as operações permaneçam locais ao particionamento sem sincronização complexa entre ranks.
• Otimização de Inferência: Durante a publicação do modelo, o tensor de metadados é omitido para reduzir o tamanho do modelo, e o tensor de identidades é congelado. O serviço de inferência torna-se estritamente apenas leitura, fornecendo consultas determinísticas e eficientes.
• Atualizações em Streaming: O sistema suporta treinamento online com atualizações em streaming, garantindo que o tensor de identidades permaneça consistente com as modificações nas linhas de incorporação.

3. Contribuições Principais

1. Garantia de Colisão Zero: Ao combinar dimensionamento adequado da tabela com profundidades de sondagem configuráveis, o MPZCH elimina efetivamente as colisões de incorporação para incorporações de usuários, uma façanha difícil de alcançar com hash padrão.
2. Gerenciamento Ativo do Ciclo de Vida: Diferentemente de tabelas hash estáticas, o MPZCH aposenta ativamente IDs obsoletos e redefine estados de otimizador, abordando diretamente o problema da "transferência negativa" e aprimorando a frescor do modelo.
3. Implementação de Alto Desempenho: O algoritmo é implementado como um kernel CUDA personalizado que lida com dezenas de milhares de IDs em paralelo. Os benchmarks mostram que a sobrecarga da sondagem linear é insignificante (a latência permanece estável mesmo com profundidade de sondagem aumentada), mantendo QPS de treinamento e latência de inferência comparáveis aos métodos existentes.
4. Lançamento de Código Aberto: A solução foi lançada dentro da biblioteca de código aberto TorchRec.

4. Resultados Experimentais

Os autores avaliaram o MPZCH por meio de rigorosos testes A/B online e benchmarks offline:

• Taxas de Colisão: Em experimentos com 150 milhões de IDs de usuários únicos, o MPZCH alcançou zero colisões com um tamanho de tabela de 200 milhões (capacidade de 1,33x) e profundidade de sondagem de 256. Em contraste, o hash Sigrid de base manteve uma taxa de colisão de ~30% mesmo com um tamanho de tabela triplo da cardinalidade do ID.
• Incorporações de Usuário (Classificação de Vídeo): Implantado em um modelo de classificação de vídeo em produção atendendo 3 bilhões de usuários ativos mensais. A eliminação de colisões resultou em melhorias estatisticamente significativas na Entropia Normalizada (NE) para 14 dos 17 tarefas de previsão, incluindo Compartilhamento (+0,38%) e Duração de Visualização de Vídeo (+0,12%).
• Incorporações de Itens (Recuperação de Vídeo): Integrado a um modelo de recuperação baseado em HSTU com expulsão baseada em TTL (24h para Posts, 72h para Proprietários).
  • Desempenho: Novos vídeos (postados dentro de 48 horas) tiveram um aumento de 0,83% em impressões.
  • Qualidade Semântica: A análise t-SNE revelou que o MPZCH melhorou significativamente o agrupamento (clustering) de incorporações para vídeos do mesmo criador. A similaridade intra-criador aumentou de 0,66% para 0,91% para posts do mesmo dia (+38% de aumento relativo).
  • Estabilidade de Aprendizagem: As trajetórias de incorporação tornaram-se mais suaves e consistentes, eliminando as flutuações voláteis observadas no modelo de base causadas por colisões de hash.

5. Significado

O artigo postula que o MPZCH oferece uma solução de dupla vantagem para sistemas de recomendação modernos. Primeiro, ao garantir um ambiente livre de colisões, eleva a qualidade da incorporação e a precisão das previsões, removendo interferência estocástica. Segundo, ao introduzir mecanismos ativos de expulsão e redefinição de otimizador, aprimora fundamentalmente a frescor da incorporação, permitindo que os modelos se adaptem rapidamente a distribuições de dados em mudança sem crescimento ilimitado de memória. Os autores concluem que essas melhorias empíricas tanto na frescor quanto na qualidade do modelo validam o MPZCH como uma solução robusta para recomendadores em grande escala.