Quantize a key embedding to one bit per sketch row

The sign of a random projection keeps enough information to estimate an inner product, so a stored key costs one bit per sketch row and nothing else: no per-group scale, no zero point, no grouping. That is what makes the overhead zero.

Usage

Tqhs(k, S_mat)

Arguments

k

Key embedding.

S_mat

JL sketch matrix, m by d.

Value

List with signs, m, d, estimate.

Details

Formula: H_S(k) = sign(S k) with S an m by d standard normal matrix; zero maps to +1 so the range is {-1, +1}^m.

References

Zandieh, A., Daliri, M. & Han, I. (2024). QJL: 1-bit quantized JL transform for KV cache quantization with zero overhead. arXiv:2406.03482, definition 3.1.

Examples

V <- c(1, 2, 3, 4, 5, 6, 7, 8)
Tqhs(V, V)
#> $signs
#>  [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
#> [39] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
#> 
#> $m
#> [1] 64
#> 
#> $d
#> [1] 8
#> 
#> $estimate
#> [1] 1
#> 
#> $method
#> [1] "QJL sign quantizer H_S(k) = sign(S k)"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"