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^{\mathrm{\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\mathrm{/}d$ and $R=r\mathrm{/}d$, the normalized minimax error converges to $1\mathrm{/}(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 $(\pi +o(1))\mathrm{/}[4R\log (W\mathrm{/}R)]$ as $W\mathrm{/}R\to \mathrm{\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\mathrm{/}R\to \mathrm{\infty }$ and $R\log (W\mathrm{/}R)\to 0$, it gives normalized error at least $(1-o(1))\mathrm{/}[2R\log (W\mathrm{/}R)]$. Thus, our protocol is optimal within a factor of $\pi \mathrm{/}2$ in the leading constant.