CS Paper Radar

Task-Oriented Quantization for Quadratic Scheduling: Centroid Water-Filling and Power-Diagram Encoders

Joss Armstrong

cs.IT eess.SP ·submitted 2026-09-16 20:47 UTC · v1

Abstract

We distinguish two regimes in task-oriented quantization with a known deterministic oracle action. For an unconstrained interior oracle and a smooth strongly concave utility, quantizing the oracle action by vector Lloyd-Max minimizes a mean-squared-error surrogate and achieves a $β/α$ approximation to the optimal $K$-level task quantizer. The reduction is exact for isotropic quadratic loss, and the corresponding task rate--distortion function is bracketed by two ordinary rate--distortion functions. Budget-constrained quadratic scheduling is different: the oracle satisfies a variational inequality, so quantizing water-filled actions is not generally optimal. We derive the exact Lloyd-type conditions for this case. The optimal action for a quantizer cell is water-filling evaluated at the cell's conditional-mean load, and the optimal encoder partitions load space into affine power-diagram cells. Thus the correct prescription is to quantize the load and water-fill its centroid. The distinction is material whenever a cell crosses water-filling active-set boundaries.

Closest papers

Nearest neighbours by meaning across the whole index.

Task-Sufficient Contraction: Source Selection for Machine Information Interfaces

cs.IT cs.LG ·2026-10-06 ·Joss Armstrong
similarity 0.61
Abstract · 19 pages, 1 figure, 1 table. An earlier version was first posted on Zenodo in September 2026 (v1: doi:10.5281/zenodo.22834532; all versions:…

A declared task can sometimes certify a reduced source before a downstream encoder, codebook, rate, distortion target, or optimizer is chosen. This paper studies when one such reduction preserves the complete downstream problem family, a property termed Task-Sufficient Contraction. The reduced source is fixed by the task before the later operating point is selected. An exact contraction allows the later problem to be solved on that source with the same result as if the full source had been retained. For a machine with a fixed set of possible actions and a fixed loss, the paper identifies a consumer-specific source by merging states only when every available action has the same regret in both. For finite action sets, replacing the richer source by this reduced source preserves the complete one-step rate-regret curve, even though the reduction is fixed before the distortion target is chosen. A second result gives an exact characterization for quadratic loss on affine feasible-action sets: the canonical reduced source is the projection onto the directions in which feasible actions can differ. Under a fixed energy budget, this becomes centered load, while retaining only the optimal water-filled action is too coarse. Earlier Information Bottleneck, semantic rate-distortion, and goal-oriented quantization results are then used to distinguish exact, architecture-conditioned, approximate, failed, and corrected contractions. The framework suggests a way for heterogeneous machines to exchange what a receiving task needs without first aligning their full internal representations.

0.32

Task-Aware QUBO Allocation for Mixed-Precision Quantization

cs.LG cs.CV ·2026-09-04 ·Osama Orabi, Artur Zagitov, Hadi Salloum, Viktor A. Lobachev, Yaroslav Kholodov
similarity 0.58
Abstract · Substantially revised version with expanded experiments, additional architectures and baselines, robustness analysis, and updated presentati…

Mixed-precision quantization requires discrete allocation of weight and activation bit-widths, followed by recovery of the selected network. We develop a task-aware quadratic unconstrained binary optimization (QUBO) surrogate with separate weight and activation profiles, a bit-operation (BOP) cost, and selected structural priors. QUBO provides a network-wide allocation that can be refined through direct validation-based PROTES search. On a compact NAFBlock-based denoiser, the refined route achieves 37.192 dB after LSQ+ at 4.035\% routed-layer BOPs, versus 37.092 dB at 4.101\% for a HAWQ-style baseline. The repeated-search primary experiment shows that LSQ+ largely closes the quality gap between QUBO allocation and expensive direct refinement. An additional restoration architecture retains a larger recovered gain, indicating that refinement's value depends on architecture and recovery. We evaluate quality, achieved cost, routing stability and optimization expense together. Deployment measurements characterize a fake-quantized floating-point implementation; BOP reductions describe analytical allocation savings.

0.12

Quantum Annealing for Resource Allocation in Next-Generation Wireless Communication Networks: A QUBO Modeling Guide

cs.IT ·2026-10-09 ·Nguyen Xuan Tung, Le Tung Giang, Mai Dinh Cong, Pham Dang Anh Duc, Nguyen Hoang Viet +2 more
published similarity 0.57
Abstract · 16 pages, 5 figures, and 7 tables. Accepted by OJ-COMS

Quantum annealing (QA) offers a physics-inspired approach for such subproblems by mapping them onto an Ising Hamiltonian, which is algebraically equivalent to a Quadratic Unconstrained Binary Optimization (QUBO) model executable on quantum annealers or hybrid solvers. However, their practical employment in wireless systems critically depends on the specific problem formulation, on the particular variable encoding, constraint handling, solver selection, hardware embedding, and fair benchmarking. This paper develops wireless-oriented QUBO modeling guidelines for QA-assisted resource allocation. We first present a beginner-friendly toy example in which a terrestrial-aerial resource-allocation problem with a fractional signal-to-interference-plus-noise ratio (SINR) maximization objective is reformulated into a two-bit QUBO via Boolean interpolation, converted into an Ising representation, and decoded back into a wireless scheduling decision. The same scheduling is applicable to UAV, aircraft, satellite, and terrestrial links in SAGIN systems. We then review the QA foundations and solver ecosystems, including binary quadratic, discrete quadratic, constrained quadratic, and hybrid models from the perspective of NG wireless optimization. Furthermore, we discuss both binary and discrete encoding, penalty-based constraint conversion, embedding overhead, solution decoding, and feasibility verification. A QUBO Compatibility Index is introduced as a lightweight diagnostic metric for assessing the associated QUBO formulation readiness, rather than a predictor of runtime or solution quality. Finally, a case study on max-min uplink power control in cell-free massive MIMO illustrates how a fairness-oriented wireless problem can be discretized, constrained, converted into the concept of a QUBO, and evaluated against classical baselines. A host of key challenges and future directions are also discussed.

0.23

Entropy-Constrained Adaptive Stochastic Quantization

cs.LG cs.AIcs.DScs.IT ·2026-08-10 ·Ran Ben Basat, Yaniv Ben-Itzhak, Michael Mitzenmacher, Shay Vargaftik
similarity 0.56
Abstract

Adaptive stochastic quantization (ASQ) is a recently introduced quantization approach that optimizes the Mean Squared Error (MSE) for a given input while preserving unbiasedness. It is designed to alleviate the communication and memory bottlenecks of modern data and machine learning workloads, including model, gradient, and KV-cache compression and nearest-neighbor search. Further, practical systems can then compress quantized data with a lossless entropy encoder. However, existing unbiased methods, including ASQ, choose their quantization values without considering this later encoding stage, leaving accuracy on the table. We formulate the Entropy Constrained Adaptive Stochastic Quantization (ECASQ) problem, which jointly selects adaptive quantization values to minimize MSE under an entropy budget and an unbiasedness constraint. We give an optimal dynamic program with $O(sd^2)$ time and $O(d^2)$ space for a length-d vector and at most s quantization values, and a GPU-friendly approximate dynamic program with $O(sd^2)$ time and $O(d)$ space. The approximation guarantees that the solution has an MSE no larger than the optimal solution that uses one fewer bit of entropy per entry. We also provide an iterative refinement procedure for the approximation solution that, in our experiments, yields near-optimal results while retaining a substantial speed advantage over our solver for the optimal solution.

0.34

On Partial Optimality in QUBO via Quadratic Posiform Autarkies

cs.DM math.OC ·2026-10-14 ·Lucas Fabian Naumann, Bjoern Andres
similarity 0.55
Abstract · 8 pages, 0 figures

Partially optimal assignments (also called persistencies) allow combinatorial optimization problems to be reduced by fixing a subset of variables to values consistent with at least one optimal solution. For the quadratic unconstrained binary optimization (QUBO) problem, such assignments can be computed efficiently via autarkies of quadratic posiforms. However, the largest autarky domain and thus the number of fixed variables can depend on the specific posiform representation. We show that every quadratic posiform with the greatest possible constant term (the roof-dual bound) yields the largest autarky domain obtainable from any quadratic posiform. By computing such a roof-dual-optimal quadratic posiform and a corresponding autarky with largest domain in polynomial time, one can therefore attain the maximum partial optimality obtainable by quadratic posiform autarkies in polynomial time. This justifies the computation of roof-dual-optimal quadratic posiforms and corresponding autarkies in popular polynomial-time algorithms and establishes that finding additional partial optimality in QUBO requires going beyond autarkies of quadratic posiforms.

0.25

From Attention Sensitivity to Layer Role: Revisiting Mixed-Precision Quantization of Transformers

cs.LG cs.AI ·2026-09-28 ·Nafiseh HosseinpourFardi, Negar Alihadi, Mahmoudreza Babaei, Milad Hosseini, Adrian Weller
similarity 0.54
Abstract · 28 pages, 2 figures, 13 tables. Nafiseh HosseinpourFardi and Negar Alihadi contributed equally

Most post-training quantization pipelines fit each weight matrix to its pretrained counterpart, one matrix at a time. Whether that proxy tracks what an attention block actually computes, or how errors in the Q, K and V projections compound inside the softmax, is rarely checked. We write the objective on the attention output instead, over all three projections at once, and reuse it throughout the pipeline. JAB defines one scalar loss over the joint Q, K, V weights of a block, evaluated against the block's real causally-masked attention output, and uses it twice: to fit the quantized weights (GPTQ warm start, then STE with learnable scales), and to score the block for a multiple-choice knapsack allocation. On attention-only quantization of Mistral-7B this works. At 3 bits JAB recovers 77-90% of the gap between uniform GPTQ and full precision, and its sensitivity estimate tracks an oracle costing 73 forward passes to within a fraction of a point. It stops working once MLP layers enter the allocation. A role-aware offset rule needing no sensitivity estimate at all beats JAB on GPT-2's MLP and on the full Mistral-7B model: with a 3-bit floor it quantizes 96.4% of the weights to 4.5 bits per parameter at 6.933 perplexity, within 4.4% of full precision (6.643) at 3.56x compression, against 7.158 for JAB at the same budget. Which matrix a weight sits in matters more than any sensitivity estimate we computed. Two things came out sideways. Block-local reconstruction is an unreliable proxy for end-to-end perplexity: one run improved a block's own objective 4.6x while perplexity rose 32x, which is why every allocation here is validated end-to-end. And on attention-only quantization, fine-tuning moved weights farther from their pretrained values while pulling attention outputs closer, with net gains. Post-training seems to recover attention behavior, not weights.

0.23

AGQ: Action-Guided Ultra-Low-Bit Quantization for Vision-Language-Action Models

cs.CV cs.AI ·2026-10-21 ·Xuhong Qiu, Zhuoyu Wu, Qiawei Zheng, Wenhui Ou, Wenqi Fang +1 more
code/data similarity 0.54
Abstract · 3 figures, 3 tables. Code and experimental results: https://github.com/Qiuxu00/AGQ

Vision-language-action (VLA) models enable robots to perform tasks specified through natural-language instructions, but their large weight footprint challenges deployment on memory-constrained onboard platforms. Ultra-low-bit quantization reduces this footprint, yet preserving task performance and controlling weight recovery costs remain challenging. We propose Action-Guided Quantization, which combines action sensitivity with a measured proxy for weight recovery cost to allocate matrix bitwidths under storage budgets. Per-channel calibration compensates for quantization error, while a uniform bitwidth within each matrix preserves regular layouts. Bit-dependent grouped lossless coding reduces resident weight storage, and block-wise recovery limits temporary buffers. On LIBERO, AGQ achieves 92.7% task success at W3, exceeding AWQ and GPTQ by 1.2 and 3.7 percentage points, respectively, and retains 70.5% success at W2.5. An asymmetric configuration, denoted W1.5$^{*}$, uses W4 vision weights and a parameter-weighted average of 1.5 bits for language weights. With lossless coding, it achieves $6.10\times$ complete-model compression relative to BF16 while retaining 25.5% task success. Code and experimental results are available at https://github.com/Qiuxu00/AGQ

0.16

BARQ: Balanced Codebook Refinement for Low-Bit LLM Quantization

cs.LG ·2026-10-03 ·Chenhang Cui, Xu Xie, Linrui Xu, Xiaohao Liu, Xingyu Zhu +2 more
theorycode/datahot direction similarity 0.53
Abstract · Code: https://github.com/chenhangcuisg-code/BARQ

As large language models (LLMs) grow in parameter count, model storage and parameter memory traffic have become major bottlenecks to efficient deployment. Codebook-based weight quantization reduces these costs, but imbalanced nearest-codeword assignments during fitting can leave some codewords insufficiently updated, limiting effective codebook utilization. To address this limitation, we propose Balanced Assignment Refinement for Quantization (BARQ), which improves quantization quality through balanced fitting of existing codebooks. Specifically, we first compute joint soft assignments between weight blocks and codewords through entropically regularized optimal transport with uniform marginals and curvature-weighted reconstruction costs, ensuring equal positive fitting mass for every codeword in the exact solution. We then refine the codewords through an assignment-weighted barycentric update, which we prove minimizes the fitting objective for fixed assignments. For finite Sinkhorn iterations, the implemented update retains this optimality provided all codeword masses exceed the denominator floor. Finally, we discard the soft assignments and use the refined codebook for standard hard nearest-codeword encoding, with our analysis establishing sufficient conditions for reducing hard-quantization distortion and evaluation loss. Across multiple LLMs, BARQ achieves lower perplexity and higher mean zero-shot accuracy than the evaluated baselines at comparable bit budgets. The code is available at https://github.com/chenhangcuisg-code/BARQ.

0.42