Reticulados E8 e Leech para o vetor armazenado

Γ (R) = 2 \cdot 2^{- 2 R} - 2^{- 4 R}, R \geq R^{*} \approx 0, 906

Mecanismo

Depois de uma rotação que torna as coordenadas aproximadamente gaussianas, o vetor é cortado em blocos de 8 (E8) ou 24 (Leech) dimensões, e cada bloco vai para o ponto mais próximo do reticulado. Para dois vetores gaussianos comprimidos a $R$ bits por entrada, o menor erro quadrático do produto interno é

\Gamma(R)=2\cdot 2^{-2R}-2^{-4R}\qquad (R\ge R^*\approx 0{,}906)

e reticulados aninhados atingem esse limite. Abaixo de cerca de 0,9 bit por entrada, o ótimo é manter menos dimensões, o que é a contrapartida teórica de Matryoshka com 1 bit.

Teto

O ganho de forma sobre a grade inteira fica em fração de bit por dimensão. Como reforço do certificado, o raio de cobertura em taxa igual encolhe cerca de 1,41 vez com E8 e 1,73 vez com Leech (constantes clássicas, a conferir em fonte). É pouco diante da folga de 29 vezes.

Riscos

Produtos internos por tabela podem ser mais lentos que popcount e multiplica-acumula inteiros. Foi o que a Elastic mediu contra o TurboQuant.

Teste e regra de parada

Próximo teste. Encoder fixo, rotação de Hadamard e comparação em bits iguais entre int4, Extended RaBitQ e código de Voronoi em E8.

Parar se. O E8 não igualar o código escalar com pelo menos 5% menos bits entre 2 e 4 bits por dimensão, ou o núcleo por tabela for mais lento que o núcleo inteiro de 4 bits.

Discussão

O fórum ainda não foi ligado.

As discussões ficam no GitHub Discussions do repositório, via Giscus. Para ativar:

Deixe o repositório público e ative Discussions em Settings.
Crie as categorias Caminhos, Perguntas, Resultados e reproduções e Propostas novas.
Instale o app em github.com/apps/giscus.
Gere os IDs em giscus.app e preencha GISCUS em src/config.ts.