Query-dependent reading improves accuracy of quantized inner product estimates
Query-Dependent Reading for Quantized Inner-Product Estimation: A Minimax Separation
Information TheoryData Structures and AlgorithmsMachine Learning
Summary
This paper looks at how to accurately estimate the inner product (a type of multiplication) of two vectors when there are limits on how much data can be stored and read. The authors find that if the reading process doesn’t depend on the query, having more storage doesn’t help improve accuracy. However, if the reading can depend on the query, extra storage really helps reduce errors substantially. They provide mathematical bounds showing how much better query-dependent reading can perform compared to query-independent approaches.
What this means in practice
- •For data compression engineers: Optimize compression schemes to reduce read cost while improving accuracy of vector similarity queries under storage limits.
- •For signal processing teams: Implement query-dependent reading to enhance performance of compressed sensing and measurement systems where storage and read bandwidth are constrained.
A theory result. No direct application yet.
Authors
Krishnakumar Balasubramanian, Siddharth Bhandari, Shiva Prasad Kasiviswanathan
Abstract
We study quantization for inner-product estimation when storage and reading have separate budgets. In the static bit-probe model [Yao, 1981], an encoder stores $w$ bits about $x$ before seeing a query $y$, and a reader probes at most $r<w$ bits to estimate $x^\top y$. Both vectors lie in the $d$-dimensional Euclidean unit ball. Protocols may be randomized, and computation is unrestricted. Performance is measured by $d$ times the worst-case mean-squared error over $x,y$, averaged over protocol randomness. First, we show that query-independent reading cannot benefit from extra storage. Any such reader is equivalent to fully reading an $r$-bit message, even when later reads depend on previously returned bits. At fixed positive rates $W=w/d$ and $R=r/d$, the normalized minimax error converges to $1/(4^R-1)$, independent of $W$. The upper bound was already known [Ordentlich and Polyanskiy, 2025]. We prove the matching lower bound for arbitrary scalar decoders, extending the result for unbiased compressors [Safaryan et al., 2020]. Then, we show that query-dependent reading makes extra storage useful. We construct a two-batch protocol using Gaussian projections and random thresholds, with asymptotic normalized error at most $(π+o(1))/[4R\log(W/R)]$ as $W/R\to\infty$. At fixed $R$, this error vanishes as storage grows, giving an unbounded advantage over query-independent reading. We also prove a finite-dimensional lower bound for arbitrary encoders, decoders, and fully branching readers. In the doubly sparse regime $W/R\to\infty$ and $R\log(W/R)\to0$, it gives normalized error at least $(1-o(1))/[2R\log(W/R)]$. Thus, our protocol is optimal within a factor of $π/2$ in the leading constant.