{
  "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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2610.24890",
  "author_total": 3,
  "authors": [
    {
      "name": "Krishnakumar Balasubramanian"
    },
    {
      "name": "Siddharth Bhandari"
    },
    {
      "name": "Shiva Prasad Kasiviswanathan"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/1qfehhzmzpk7v.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2610.24890",
  "fulltext_url": null,
  "id": "1qfehhzmzpk7v",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2610.24890",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "cs.IT"
    ],
    [
      "arxiv",
      "cs.LG"
    ],
    [
      "arxiv",
      "math.IT"
    ],
    [
      "openalex",
      "1702|Algorithms and Data Compression"
    ]
  ],
  "openalex": "W7223009413",
  "pdf_url": "https://arxiv.org/pdf/2610.24890",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-17",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/1qfehhzmzpk7v.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:30:57Z",
      "native_id": "2610.24890",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2610.24890"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.IT",
      "subfield": "general"
    }
  ],
  "title": "Query-Dependent Reading for Quantized Inner-Product Estimation: A Minimax Separation",
  "title_text": "Query-Dependent Reading for Quantized Inner-Product Estimation: A Minimax Separation",
  "type": "preprint",
  "updated_at": "2026-10-30T12:33:44Z",
  "url": "https://research.draconitic.com/paper/1qfehhzmzpk7v",
  "venue": "arXiv",
  "versions": []
}