CS Paper Radar

How Much Does Random Rotation Help GPTQ? Sharp Worst-Case Rate Gaps in the High-Rate Regime

Runguo Li

cs.IT cs.LG ·submitted 2026-11-01 07:30 UTC · v1

Abstract

GPTQ is Babai's nearest-plane algorithm on the lattice of the Cholesky factor of the layer's input second moment $Σ$. In the high-rate, entropy-coded regime it needs $\tfrac12\log_2(\AM/\GM)$ of its Cholesky pivots more bits than WaterSIC, which is within $0.255$ bit of the rate-distortion limit for every $Σ$; random rotations close most of this gap in practice, and Ordentlich and Polyanskiy asked for the worst-case gap between rotated GPTQ and WaterSIC. We show that after a Haar rotation the $k$-th pivot converges almost surely, uniformly in $k\geδn$ and over spectra $ν$ of bounded condition number, to $1/S_ν(-k/n)$, a classical formula from the theory of Lyapunov exponents, and use it to answer the question. Over spectra with condition number $κ$ the worst rotated gap is $\tfrac12\log_2κ-\log_2\lnκ+\tfrac12-\tfrac1{\ln2}+o(1)$ bits, attained only by two-point spectra, just $\tfrac12\log_2\lnκ+O(1)$ bits below the worst case without rotation, so rotation cannot replace waterfilling in general. It nearly can on real layers: rotation cuts the cost of an $η$-fraction of outlier eigenvalues of size $μ$ from about $ημ$ to $η^2μ/2$ to leading order, but cannot remove spectral spread on a logarithmic scale; for non-Gaussian weights it also adds a weight-side rate cost, which we characterize exactly under a standard high-rate assumption. On $96$ Hessians of Qwen3 and Llama-3.1 the rotated gap has median $0.04$ bit and maximum $0.36$ bit, against $2$--$5$ bits in the worst case for the same condition numbers, and the limit matches it to within $0.009$ bit.

Comment
28 pages, 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Rapid mixing of Potts Glauber dynamics throughout uniqueness

cs.DM math.PRmath-ph ·2026-10-30 ·Antonio Blanca, Reza Gheissari, Heehyun Park, Xusheng Zhang
hot direction similarity 0.62
Abstract

Sampling from the ferromagnetic $q$-state Potts model is a fundamental problem in statistical physics and approximate counting. Although computationally hard in the worst case, sampling is expected to be efficient throughout the high-temperature uniqueness regime of the model using the natural single-site Glauber dynamics. We establish fast mixing bounds for every $q$, in the full high-temperature regimes in the two central graph families on $n$ vertices. (1) For every $Δ\ge 3$, the Potts Glauber dynamics mixes in $n\operatorname{polylog}(n)$ steps with high probability on a uniformly random $Δ$-regular graph for all $β<β_u(q,\mathbb T_Δ)$ where $β_u(q,\mathbb T_Δ)$ is the uniqueness threshold on the $Δ$-regular tree; (2) For every $d\ge 2$, the Potts Glauber dynamics has inverse spectral gap $n^{1+o(1)}$ on cubes or tori in $\mathbb Z^d$ for all $β<β_c(q,\mathbb Z^d)$ where $β_c(q,\mathbb Z^d)$ is the critical point on $\mathbb Z^d$. Both temperature thresholds are sharp as the Glauber dynamics slows down exponentially above them. These results overcome the challenge of bounding mixing times without access to correlation decay bounds in the presence of pinnings (i.e., without spectral independence or strong spatial mixing). For this purpose, our proof introduces a new dichotomy principle: throughout the high-temperature regime, any initial spin distribution is either such that its pinnings ensure good correlation decay, or Glauber dynamics escapes from that distribution quickly. We expect this kind of dichotomy to have further applications. As a demonstration, we also develop its analog for random-cluster dynamics and use it to prove that Swendsen-Wang dynamics on random $Δ$-regular graphs mixes in $O(\log n)$ time throughout uniqueness. The results in this paper were arrived at with the assistance of ChatGPT 5.6 and 6.

0.23

A subquadratic upper bound for the mixing time of the Thorp shuffle

cs.DS math.PR ·2026-10-03 ·Yunjiang Jiang
theory similarity 0.56
Abstract · 31 pages

Let $n=2^d$. We prove that the worst-start total-variation mixing time of the full labelled Thorp shuffle satisfies, for every fixed $0<\varepsilon<1$, \[ t_{\mathrm{mix}}(\varepsilon) \le C_* d^{5/3}+O_\varepsilon\!\left(d^{4/3}\log(d+2)\right), \qquad C_*=5.1536951454\ldots . \] Time is measured in ordinary Thorp shuffles. This improves the previously published full-deck upper bound $O(d^3)$ of Morris. The geometric starting point is elementary: label the $n=2^d$ positions by binary strings. One physical Thorp shuffle is a random swap layer on one coordinate matching of the $d$-dimensional cube, followed by a deterministic cyclic rotation of the coordinates. In a rotating frame that deterministic rotation disappears, so $d$ successive physical shuffles become one \emph{sweep}: one independent random swap layer in each coordinate direction. The proof then combines five ingredients. First, a collision-graph representation and negative dependence give pointwise smoothing for ordered marked cards. Second, an entropy argument is sharpened by moving an endpoint moment up to the critical exponent $β_c=\log_2(3/2)$, yielding an entropy-preparation clock $s^2/(2\log(3/2))+O(s\log s)$. Third, exact multiplicities in the ordered $h$-tuple permutation representation amplify marked-card bounds into Fourier operator and energy estimates on low representation levels. Fourth, entropy truncation produces a positive mixture whose regular component retains the marked-card budget. Finally, only two long blocks need this entropy regularization: a shorter third block is used solely for additional low-level smoothing. Optimizing the three block lengths gives the constant above.

0.57

Gaussian Difference Dynamics: Breaking the $2^{n/2}$ Barrier for the Shortest Vector Problem and Discrete Gaussian Sampling

cs.DS cs.CR ·2026-11-03 ·Yiming Gao, Xuyuan Han, Honggang Hu
similarity 0.56
Abstract

We give classical randomized algorithms in a word RAM model that break the $2^{n/2}$ barrier for both discrete Gaussian sampling (DGS) and the Shortest Vector Problem (SVP). For every fixed $α>1$, shifted DGS on arbitrary lattices at width $σ\geαη_{1/2}(L)$ takes $$ (3/2)^{n/2+o(n)}\text{ time} \qquad\text{and}\qquad (4/3)^{n/2+o(n)}\text{ space}. $$ These bounds match the Becker--Ducas--Gama--Laarhoven (BDGL) heuristic sieving exponents. At widths at least $3η_{1/2}(L)/2$, the same total cost suffices for an entire batch of $\lfloor(4/3)^{n/2}\rfloor$ samples jointly close to independent target Gaussians. For SVP on arbitrary lattices, our algorithm returns a shortest nonzero vector with high probability in $$ 2^{0.4130n+o(n)}\text{ time} \qquad\text{and}\qquad 2^{0.3138n+o(n)}\text{ space}. $$ As a corollary, we obtain centered DGS at every width with the same exponents, answering a question of Stephens-Davidowitz (SODA 2016). We introduce Gaussian difference dynamics (GDD), a framework for tracking expected counts and pairwise clustering of vectors through repeated differencing. A closed recursion for the first two counting moments controls these quantities relative to a Gaussian reference, without requiring independence within intermediate lists. Accurate moment bounds let us extract a Gaussian sample by weighted selection, while the weaker bounds needed to establish a shortest vector representation allow us to retain more differences. We perform these transitions on thin spherical shells, where the Gaussian rejection weights can be renormalized at subexponential cost. For batch sampling, we combine this geometry with the double rejection technique of Doulgerakis and Laarhoven to control the joint distribution of outputs while reusing vectors.

0.50

Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry

cs.CC quant-phcond-mat.dis-nncs.DS+1 ·2026-09-30 ·Leo Zhou, Noah Shutty, Mark Sellke, Stephen P. Jordan
theoryhot direction similarity 0.54
Abstract · 44 pages, 1 figure, 3 tables

We apply Decoded Quantum Interferometry (DQI) to sample from the Gibbs measures of classical Ising spin Hamiltonians. We show that this Gibbs sampling problem reduces to a quantum decoding problem, and the temperature achievable by DQI is determined by the performance of decoding algorithms. We then focus on the task of Gibbs sampling for classical Ising $k$-spin glasses (or Max-$k$-XORSAT) on random Erdős-Rényi hypergraphs with average degree $D\ge k$. In a temperature range beginning asymptotically at the predicted dynamical phase transition, $β_{\rm dyn}(k,D) = \sqrt{(2\ln k)/D}\times [1+o_{k\to\infty}(1)]$, we show that shattering and disorder chaos form a topological barrier that obstructs many algorithms, including Glauber dynamics and any algorithm whose output distribution is "stable" under perturbations of the input. In contrast, we prove that this barrier can be broken both by a classical algorithm based on Prange's method, and by DQI equipped with a quantum decoder. For example, when $D=αk$ with fixed $α>1$, both Prange's algorithm and DQI can sample at any inverse temperature $β< \tanh^{-1}(1/α)$ for sufficiently large $k$, well beyond the dynamical threshold $β_{\rm dyn} \sim \sqrt{2\ln k / (αk)}$. Therefore, our results show that DQI can overcome topological barriers that obstruct stable algorithms.

0.62

Improved rapid phase ordering for Ising dynamics on random regular graphs

cs.DS math.PRmath-ph ·2026-10-20 ·Zhangsong Li, Allan Sly
similarity 0.54
Abstract · 59 pages, 3 figures

We study Glauber dynamics for the Ising model on random $d$-regular graphs with $n$ vertices at low temperature, in the regime $β\geq C/d$ where $C,d$ are sufficiently large constants. In this regime, the full mixing time is exponential in $n$, because of the bottleneck between the two dominant phases: configurations with a majority of plus spins and configurations with a majority of minus spins. We show that, for sufficiently large $d$, if the dynamics is initialized with an excess of at least $ε_{C,d} n$ plus spins over minus spins, then it quasi-equilibrates in time $O(\log n)$ to the Gibbs measure conditioned on positive magnetization. In addition, the required bias $ε_{C,d}$ can be chosen so that $ε_{C,d}\to 0$ as $d,C\to\infty$. Previous bound of \cite{GSS25+} in the Ising and large-$d$ setting required $β\gtrsim (\log d)/d$. A key difficulty is that, even from the all-plus initialization, one must control the propagation of negative information in spacetime in a low-temperature model with strong local correlations. We address this by developing a new bootstrap approach to proving subcriticality of disagreement clusters under the grand coupling.

0.32

Learning Finite-Memory Binary Sources

cs.IT math.PR ·2026-10-29 ·Maciej Skorski
similarity 0.53
Abstract

Estimating biased finite-memory sources from a single trajectory is a fundamental problem with practical impact, for example in estimating entropy for cryptography. We study order-$d$ binary sources whose conditional probabilities have bias at most $ε$, and establish *sharp* sample complexity bounds: relative accuracy $γ$ with confidence $1-δ$ needs $γ^{-2}\,(\tfrac12-ε)^{-d}\,(\log d+\log\tfrac1δ)$ samples up to constants depending on $ε$, with matching upper and lower bounds and no dependence on mixing time or spectral gap. The proof rests on a sharp bound on expected hitting times of the sliding-window (de Bruijn) chain, which stay of order $1/π(w)$ uniformly in $d$ exactly when $ε<\tfrac3{10}$, and on majorization of the window masses by those of independent biased coins. Applied to published entropy-source validations, the bounds show that their trace lengths may be underpowered: $10^6$ bits cannot resolve all transitions of an $8$-bit model to better than about $4.5\%$ relative error.

0.17

Near-Optimal Oracle Bounds for Isotropic Rounding

cs.DS ·2026-10-05 ·Yang P. Liu, Richard Peng, Alicia Stepin, Colin Tang
theory similarity 0.53
Abstract

We give optimal bounds, up to polylogarithmic factors, for rounding convex bodies to near-isotropic position. A convex body $B(0,r)\subseteq K\subseteq B(0,R)$ in $\R^n$ can be rounded using $\Ot(n^3)$ membership queries; the upper bound extends to logconcave distributions. We prove a matching $\Omegat(n^3)$ lower bound, even when $R/r=n^{O(1)}$. The key lemma states that if $B(0,1)\subseteq K$ and $\Cov(\Unif(K))\preceqκI_n$, with $κ\ge1$, then approximate uniform sampling from an initial density bounded by a constant times the uniform density uses $\Ot(n^2\sqrtκ)$ expected membership queries. We prove this by simulating reflected kinetic dynamics using the analysis of Eberle and Lörler~\cite{EL26:journal}. Combining this sampler with the ideas of Jia, Laddha, Lee, and Vempala~\cite{JLLV26:journal} for rounding well-rounded bodies yields our $\Ot(n^3)$ query rounding algorithm. We also give a counterexample to an ellipsoid-growth conjecture from previous papers on this topic.

0.48

A positive resolution of the gap-entropy conjecture

cs.LG stat.ML ·2026-09-09 ·P. M. Aronow, Nathan Kallus, Patrick Lopatto
theory similarity 0.53
Abstract

We prove the gap-entropy conjecture for fixed-confidence best-arm identification with independent unit-variance Gaussian arms, means in $[0,1]$, and a unique optimal arm. For each suboptimal arm $i$, let $Δ_i=μ_*-μ_i$ be its gap from the optimal mean, and write $H=\sum_{i\ne *}Δ_i^{-2}$. Let $p_r$ be the fraction of $H$ contributed by arms with $2^{-(r+1)}<Δ_i\le2^{-r}$, and let $\mathrm{Ent}(I)=\sum_{r:p_r>0} p_r\log(1/p_r)$. Among all algorithms that identify the optimal arm with probability at least $1-δ$ on every Gaussian instance, the optimal expected number of samples on a given instance, averaged over all permutations of the arm labels, is within absolute constant factors of $H(\log(1/δ)+\mathrm{Ent}(I))$. Moreover, there is an algorithm, independent of the instance, whose expected number of samples is bounded by a constant multiple of this quantity plus $g^{-2}\log\log(e^e/g)$, where $g=\min_{i\ne *}Δ_i$ is the gap to the closest competitor.

0.51