One-Sided Residual Certificates for Exact Quantized Image Retrieval

Exact-score retrieval returns the same ordered top-k and numerical scores as a specified exhaustive computation. Quantized vectors can screen candidates, but their approximation errors require safe upper bounds. We study a one-sided residual certificate, denoted OARC+, which stores the positive-part residual norm for nonnegative queries, replacing the full residual norm at identical payload. The inequality is a direct consequence of Cauchy–Schwarz; the contribution is its single-scalar specialization, exact-score integration, and controlled resource comparison. Exploratory experiments on 900 Digits gallery items and 357 queries reduced mean refinements by 22.05% for pixels and 16.49% for histograms of oriented gradients (HOG). A revision-stage 4K Large Scale Dataset and Benchmark (4KLSDB) transfer evaluation used 129,484 gallery images and 2000 validation queries, with reported reductions of 46.46% for HOG and 48.71% for HOG combined with hue, saturation, and value histograms (HOG+HSV). The test split remains unused. We characterize when tighter bounds cross the stopping threshold and model the cost needed for refinement savings to offset scanning and sorting. Signed queries require a different certificate, and cached exhaustive scoring was faster on Digits. The evidence concerns certificate selectivity under fixed representations; large-gallery latency, physical input/output (I/O) savings, and confirmatory generalization remain unestablished.