Query-Dependent Reading for Quantized Inner-Product Estimation: A Minimax Separation

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 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 (W/R)] as W/R to infinity. 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 infinity and R (W/R) to0, it gives normalized error at least (1-o(1))/[2R (W/R)]. Thus, our protocol is optimal within a factor of π/2 in the leading constant.