Smallest sketch size meeting an inner-product distortion target

The bound says how wide the sketch must be, and the answer does not mention the embedding dimension at all. Cost per token is fixed once the accuracy target is fixed, so a long context does not cost more per key.

Usage

Tqdist(eps, delta)

Arguments

eps: Relative distortion target.
delta: Failure probability.

Value

List with m_min, m_real, estimate, eps, delta.

Details

Formula: with m >= (4/3)(1 + eps)/eps^2 log(2/delta), Pr[|Prod(q,k) - <q,k>| > eps ||q|| ||k||] <= delta.

References

Zandieh, A., Daliri, M. & Han, I. (2024). arXiv:2406.03482, lemma 3.5.

Examples

V <- c(1, 2, 3, 4, 5, 6, 7, 8)
Tqdist(V, V)
#> $m_min
#> [1] 2 0 0 0 0 0 0 0
#> 
#> $m_real
#> [1]  1.8483925  0.0000000 -0.2402756 -0.2888113 -0.2932130 -0.2848254 -0.2727103
#> [8] -0.2599302
#> 
#> $estimate
#> [1] 2 0 0 0 0 0 0 0
#> 
#> $eps
#> [1] 1 2 3 4 5 6 7 8
#> 
#> $delta
#> [1] 1 2 3 4 5 6 7 8
#> 
#> $method
#> [1] "QJL inner-product distortion bound"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"