CS Paper Radar

A Quantization Problem Posed by Adaptive Streaming

Yuriy A. Reznik

cs.IT ·submitted 2026-09-03 12:16 UTC · v1

Abstract

In adaptive bitrate (ABR) streaming, the delivery technology behind most Internet video, each title is encoded at several bitrates, forming an \emph{encoding ladder} of \emph{renditions}. Each client plays the highest rendition that its network bandwidth can sustain. We show that choosing the ladder is a problem of \emph{scalar quantization} of the bandwidth distribution. However, this quantization problem is of an unusual kind: the client's logic pins each quantization cell's reproduction value to the cell's \emph{left edge}, and the distortion measure is a one-sided quality loss rather than a squared error. The constraint reshapes the classical theory. The \emph{quality gap} of a ladder is the distance between its average delivered quality and the \emph{quality limit} that infinitely many renditions would attain. For optimal $n$-rendition ladders the gap $\mathcal{G}_n^*$ decays as $Θ(1/n)$, not the textbook $Θ(1/n^2)$. Moreover, with large $n$, $n\,\mathcal{G}_n^*\to C_w=\frac{1}{2}(\int\!\sqrt{p\,Q'}\,\,d B)^2$, with the limit attained when the ladder's rates follow the density $\sqrt{p\,Q'}$, which replaces Panter--Dite's $p^{1/3}$; here $p$ is the bandwidth density and $Q$ the quality--rate curve of the content. The law yields closed-form design rules: quantile rung placement, the rendition count $n(\varepsilon)\approx C_w/\varepsilon$ needed to reach tolerance $\varepsilon$, and the economic ladder size $n^*=\sqrt{λC_w/κ}$ when a rendition costs $κ$ to operate and the quality gap is priced at $λ$. The same analysis extends to the design of ladders employing different video resolutions, codecs, perceptual quality metrics, and the two-dimensional adaptation logic of modern web players.

Closest papers

Nearest neighbours by meaning across the whole index.

Information Capacity of Generative Video Compression: Quantifying the Rate-Compute Exchange at Identical Quality

cs.CV ·2026-09-23 ·Cheng Yuan, Jiawei Shao, Xuelong Li
similarity 0.63
Abstract

Under the AI Flow framework, communication networks distribute intelligence across devices, edge servers, and clouds, and computation at the receiver becomes a resource that can substitute for transmitted bits. Generative video compression (GVC) embodies this exchange by sending compact tokens with ultra-low bitrate and letting a generative decoder synthesize the video, yet how much bandwidth savings a unit of decoder compute actually achieves has never been quantified. To fill this vacancy, we model reconstruction quality as a two-factor power law in data rate and decoder compute, which fits measured DISTS of two GVC decoders with a mean error below 3%, and define the information capacity (IC) as the negative logarithmic slope along an iso-quality contour, namely the fraction of rate saved per fractional increase in compute at identical quality. IC is dimensionless and unit-invariant, thus enabling an architecture-agnostic comparison. It forms a field over the operating plane, locating where additional denoising steps are worth their cost. Across five datasets, the 14B decoder trades more compute for fewer rate about ten times more efficiently than the 1.3B decoder. IC also varies significantly across datasets, indicating imbalanced performance on the rate-compute trade-off in GVC methods.

0.13

Distributed Nash Equilibrium Seeking with Logarithmic Bit Rates over Digital Channels

eess.SY ·2026-08-12 ·Zihao Ren, Chengyang Jiang, Lei Wang, Yang Liu, Kemi Ding
theory similarity 0.59
Abstract

This paper introduces quantization techniques to reduce the communication complexity in the distributed Nash equilibrium (NE) seeking problem, achieving an exponential reduction in bit rates over digital channels. The goal of distributed NE seeking algorithms is to coordinate agents in a network game toward equilibrium through iterative message exchanges among them via a communication network. The computational complexity of this distributed algorithm critically depends on network communication overhead in the digital channel, motivating the development of communication reduction mechanism. Regarding this, we proposed some quantizers based on sparsification and uniform quantization through a general class of ultimate-boundedness-based quantizers. Based on this, we propose a Passivity-Based NE seeking Algorithm with Time-varying scaling Error state Quantization (PBA-TEQ), and show that the linear convergence can be achieved under a sufficient condition. Moreover, when employing either the scalarization quantizer or the greedy quantizer, both belonging to the ultimate-boundedness-based quantizers, within the PBA-TEQ framework, we establish a lower bound on communication complexity of $\log_2(\mathcal{O}(nd))$ bit rates per transmission to achieve unbiased linear convergence, with $n$ being the number of agents and $d$ being the dimension of the decision state of the network game. Numerical simulation examples are provided to validate our theoretical results.

0.04

Deterministic Causal Quantization with Bounded Error: Adaptive Reconstruction and Entropy bounds

cs.IT math.PR ·2026-10-20 ·Rama Cont, Massoud Heidari
theory similarity 0.58
Abstract · 41 pages

We study compression of real-valued stationary sources under a deterministic error bound: every sample must be reconstructed within a prescribed tolerance $\varepsilon$ on every input sequence. Reconstructions are causal, depending only on present and past inputs. Rates are measured by the entropy of the quantizer output, which block entropy coding can approach, and compared with the minimum rate of unrestricted block quantization under the same error constraint. A uniform scalar quantizer with cells of width $2\varepsilon$ is within one bit per sample of this minimum whenever finite-entropy scalar quantization is possible, without density, independence, or mixing assumptions. Under entropy and Sobolev regularity conditions, the gap is at most $2\mathcal{J}\varepsilon^2/(π^2\ln 2)$, where $\mathcal{J}$ is the asymptotic Fisher information per sample. Thus the cost of causal reconstruction vanishes at a quadratic rate as the tolerance decreases. A uniform grid, however, cannot adapt to the source. We construct an adaptive quantizer whose encoder and decoder maintain a common finite set of reconstruction values, updated from the transmitted symbols alone; suitable initialization reproduces any uniform grid. When its initial values are at least $\varepsilon$ apart, its rate is within two bits per sample of the minimum for every such source. For sources uniform within separated intervals of width $2\varepsilon$, storing the interval centers attains the minimum and its Shannon lower bound. Such configurations can outperform every uniform grid of the same cell width: over sources with well-separated intervals, the best uniform grid's worst-case excess rate is $1/(2\ln 2)\approx 0.72$ bit per sample.

0.27

Adaptive Quantization Preserves Fast Rates for TD Learning over Rate-Limited Channels

cs.LG ·2026-11-09 ·Sreejeet Maity, Aritra Mitra
theory similarity 0.58
Abstract

Motivated by reinforcement learning subject to communication constraints, we study a policy evaluation problem with linear function approximation over a rate-limited channel. In our setup, an agent interacting with an unknown environment (modeled as a Markov Decision Process) transmits quantized estimates of a temporal-difference (TD) learning update direction to a server over a finite-capacity channel. Our goal is to investigate to what extent one can preserve the statistical convergence rates achievable when the channel has infinite capacity. To that end, we propose a new algorithm called Batched Adaptively Quantized TD (BAQ-TD), which uses batching to reduce the variance of the transmitted information, and adaptive quantization to encode innovations. We prove a high-probability finite-time error bound for BAQ-TD, and show that, above a certain finite channel capacity, BAQ-TD preserves the convergence rate of unquantized TD up to logarithmic factors. Specifically, for a $d$-dimensional value function parameter, we establish that transmitting a total of $\mathcal{O}(d \log(T))$ bits over a horizon of length $T$ suffices to achieve the order-optimal rate of $\tilde{\mathcal{O}}(1/T)$, marking an exponential improvement in communication-complexity over prior work.

0.25

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

cs.IT cs.DScs.LG ·2026-10-17 ·Krishnakumar Balasubramanian, Siddharth Bhandari, Shiva Prasad Kasiviswanathan
theory similarity 0.56
Abstract · 66 pages

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.

0.19

Lower Bounds for Adaptive Relaxed Locally Decodable Codes via the Capped Horvitz--Thompson Estimator

cs.CC cs.IT ·2026-11-03 ·Guy Goldberg, Tom Gur, Sidhant Saraogi
theory similarity 0.56
Abstract

We prove a nearly optimal lower bound on the blocklength of general relaxed locally decodable codes (RLDCs), extending the result of [GGS26] to nonlinear encodings and adaptive decoders with two-sided error. Namely, we show that any $q$-query RLDC $C\colon \{0,1\}^k \to \{0,1\}^n$ must satisfy $n = k^{1+Ω(1/q)}$, closely matching the upper bound of $n = k^{1+O(1/q)}$ by Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (STOC 2004). Our proof reduces showing RLDC lower bounds to estimating the output distribution of adaptive decoders. To this end, we introduce a capped Horvitz--Thompson estimator with uniformly bounded discrete derivatives on the $p$-biased cube. We establish its concentration of measure via self-bounding inequalities and control the downward bias induced by capping through a spreadness argument.

0.22

Optimal compression with quantum retrieval

cs.DS quant-phcs.IRcs.IT ·2026-10-05 ·Shyam Dhamapurkar, Mohit Garg, Manaswi Paraashar, Jaikumar Radhakrishnan
similarity 0.55
Abstract · 13 pages, 3 figures

We consider the following data compression problem. Given a string $x \in \{0,1\}^m$ of Hamming weight at most $n$, compress it into a shorter string $y \in \{0,1\}^s$ so that any bit $x_i$ of $x$ can be retrieved without any error using at most $t$ quantum queries to the standard oracle encoding of $y$. If queries are allowed to be adaptive we show how optimal compression up to a logarithmic factor can be achieved. If the queries are required to be made non-adaptively, we show schemes whose space is optimal in its dependence on $m$ except for a logarithmic factor, and is at most quadratically worse when compared to the optimum in its dependence on $n$.

0.12

Quantization Beyond Uniform Bit Allocation

cs.IR cs.DB ·2026-08-19 ·K. S. Sreeramji, Sabyasachi Basu, Ravishankar Krishnaswamy, Kirankumar Shiragur, Yujia Wang
published similarity 0.55
Abstract · Accepted at the 2nd Workshop on Vector Databases (VecDB), part of 52nd International Conference on Very Large Data Bases (VLDB 2026)

Quantization is a fundamental technique to handle the growing sizes of embeddings generated by modern models. Existing quantization schemes are largely embedding agnostic and allocate bits uniformly across dimensions. However, recent models produce embeddings with significant geometric structure. In this work, we investigate whether a variable bit allocation scheme can improve quantization quality under a fixed memory budget. We propose a simple variable bit allocation framework that partitions an embedding into contiguous buckets and allocates storage non-uniformly across them. Using a greedy allocation strategy, we instantiate this framework for both Product Quantization (PQ) and Scalar Quantization (SQ). We perform a series of experiments on embeddings known to have the Matryoshka property (MRL), and consistently observe that non-uniform allocations outperform uniform baselines at identical storage budgets. The largest improvements occur in the low-bit regime, where uniform allocation is particularly inefficient for MRL embeddings. At the same compression rates, variable allocation improves recall by up to 8\% for PQ and up to 18\% for SQ. Our results suggest a new direction for structure-aware compression and indexing techniques for large-scale retrieval systems.

0.25