Distortion of an inner-product score under TurboQuant_prod

The 1/d in the bound means the inner-product distortion falls with DIMENSION as well as with bits. expected_max is a Gaussian-tail ESTIMATE of the largest of n_keys errors, not a bound from the paper.

Usage

Scoredist(b, d, query_norm = 1, n_keys = 1)

Arguments

b

Bits per coordinate.

d

Key dimension.

query_norm

||q||_2 of the query.

n_keys

Number of keys scored against.

Value

List with variance, rms, lower_bound, ratio, expected_max, b, d, n_keys.

Details

Formula: D_prod <= sqrt(3) pi^2 ||q||^2 / d . 4^-b (Theorem 2); rms = sqrt(D_prod); expected max ~= rms sqrt(2 log n)

References

Zandieh et al., arXiv:2504.19874, Theorem 2 and Theorem 3. The expected_max figure is the standard Gaussian maximum approximation and is NOT from the paper.

Examples

Scoredist(b = 5L, d = 5L)
#> $variance
#> [1] 0.0033388
#> 
#> $rms
#> [1] 0.05778235
#> 
#> $lower_bound
#> [1] 0.0001953125
#> 
#> $ratio
#> [1] 17.09466
#> 
#> $expected_max
#> [1] 0.05778235
#> 
#> $b
#> [1] 5
#> 
#> $d
#> [1] 5
#> 
#> $n_keys
#> [1] 1
#> 
#> $method
#> [1] "Score distortion, arXiv:2504.19874 Theorems 2 and 3"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"