Query-Dependent Reading for Quantized Inner-Product Estimation: A Minimax Separation
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⊤ 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/(4R−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))/[4Rlog(W/R)] as W/R→∞. 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→∞ and Rlog(W/R)→0, it gives normalized error at least (1−o(1))/[2Rlog(W/R)]. Thus, our protocol is optimal within a factor of π/2 in the leading constant.
Related
- Four-Level Quantized Soft Information Aided Hard-Decision Decoder for Product-like Codes
- Product-Aware Deterministic Rounding for Quantized Matrix Multiplication
- Estimation with Quantized Parameter Side-Information
- Symmetry-Aware Orientation Estimation via Outer-Product Rotation Targets in YOLO26
- Ellipsoid Separation in Data-Dependent Time via Infimal Displacement Vectors
BibTeX
@misc{balasubramanian2026querydependent,
title = {{Query-Dependent Reading for Quantized Inner-Product Estimation: A Minimax Separation}},
author = {Krishnakumar Balasubramanian and Siddharth Bhandari and Shiva Prasad Kasiviswanathan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.24890},
eprint = {2610.24890},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.24890},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Query-Dependent Reading for Quantized Inner-Product Estimation: A Minimax Separation
AU - Krishnakumar Balasubramanian
AU - Siddharth Bhandari
AU - Shiva Prasad Kasiviswanathan
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2610.24890
UR - https://arxiv.org/abs/2610.24890
AB - 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))/[4Rlog(W/R)] as W/R→∞. 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→∞ and Rlog(W/R)→0, it gives normalized error at least (1−o(1))/[2Rlog(W/R)]. Thus, our protocol is optimal within a factor of π/2 in the leading constant.
ER -