acceptodds
Under review as a conference paper at ICLR 2027

Certified Stopping for Fixed-Codebook Quantization

Abstract

When pairwise refinement stops in fixed-codebook quantization, how much joint improvement remains possible? We develop a certified stopping framework that separates conditional search, certificate optimization, and relaxation strength, connecting each source of uncertainty to the computation that can reduce it. A budgeted pair oracle maintains a feasible incumbent and a valid conditional lower bound after any number of finite branch scores. A globally valid curvature split extends these bounds to the coupled quadratic. Optimizing signed block curvature and the anchor recovers a block-moment relaxation when and every block codebook has full affine span. Its certified optimization interval decomposes exactly into restricted-master and finite-separation terms. On eight exactly enumerable six-coordinate restrictions of captured GPT-2 reconstruction objectives, one pair-fixed point remains above the finite optimum, while four objectives retain strictly positive block-moment relaxation gaps after certificate optimization. Across all eight stored rational objectives, the optimized certificate is tighter than continuous-box and fixed-curvature controls. The hierarchy distinguishes when to score more candidates, improve the conic state, or change the relaxation.

Primary area:
optimization
Keywords:
LLM quantization, fixed codebooks, discrete optimization, optimality certificates, semidefinite relaxation, pair search

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_a5tiOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper aims to find a certificate that suggest a fixed-codebook quantization is close enough to optimal, particularly for pairwise refinement. It addresses the weaknesses of a certificate and the quantization result as certificate gap (gap between the lower bound and the actual relaxed value), relaxation gap (gap introduced by constraint relaxation) and finite suboptimality (the actual error between the optimal solution and the obtained result). Then, it provides a pairwise optimization method that updates 2 variables at the same time with pruning using a budget concept. Next, the paper argues that the optimization target can be decomposed and captures pairwise improvement while keeping the estimate a valid lower bound as the certificate.

Critical strengths
  1. The paper provides a sound theory support on the algorithm
  2. The experiment results show significant improvement in the certificate for small cases
Critical weaknesses
  1. The introduction did not give a good enough background, which makes it difficult for researchers new to the field to follow the work.
  2. The experiments cover only cases with 6 coordinates and 8 possible values. More experiments on the algorithm behavior on larger cases are recommended.
Questions for authors

Is pairwise refinement some well-established method in the literature, or a method proposed in this paper? The introduction seems to describe it as an existing method, but there is no citation for that, and the branch searching with budget seem to be describing a pairwise algorithm.

1 comment
AuthorsOpenReview ↗

For Reviewer a5ti

Pairwise refinement is an existing block-coordinate optimization approach: it changes two codebook entries while holding the remaining coordinates fixed. Section 7 and Appendix K discuss the relevant coordinate-refinement literature, including QuantEase and CDQuant. Our contribution at this step is an anytime pair oracle that returns both a feasible incumbent and a valid conditional lower bound after an arbitrary finite score budget. The lazy implementation needs at most min⁡(L,k+2)\min(L,k+2) lower-bound evaluations after kk finite scores, as established in Theorem 2.

Stopping at a pairwise fixed point, however, does not rule out improvement across pairs. The global certificate addresses that remaining question. In the first QKV example, every move within the selected pairs has nonnegative increment, yet a change across two different pairs improves the objective by 2.80714×10−52.80714\times10^{-5}. Section 5 retains that coupling in a valid global lower bound. Its primal–dual interval also quantifies the remaining improvement available from optimizing the chosen certificate family. This connects the pair oracle, global bound and stopping decision through the same objective.

To check the global bound against an exact optimum, the study uses eight six-coordinate restrictions, each with 86=262,1448^6=262{,}144 configurations, allowing exhaustive verification of the finite optimum. The local-oracle benchmark covers 24,576 captured pair-row instances. On all eight restrictions, we also compared single-coordinate, pair and merged-block certificates. Pair bounds are strictly stronger than single-coordinate bounds in seven cases, and merging two pairs improves three of the four cases with a certified relaxation gap. In the attention-output example, the current feasible objective is zero. At tolerance 10−810^{-8}, the pair certificate leaves the decision unresolved, while the merged-block certificate certifies stopping.

Reviewer_eH4AOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper asks a practical-sounding question: when pairwise refinement of a quantized weight row on a fixed grid stops improving, how much better could a joint change still be? The authors argue that "stopped" can mean three different things (p.1). The lower bound may not be fully optimized, the relaxation behind it may be loose, or the returned codeword may not be the true optimum. They organize these as L≤vmom≤F∗≤F(x^)L \le v_{mom} \le F^* \le F(\hat{x}) (Fig. 2), with each gap suggesting a different next step. The technical pieces are:

  • a budgeted pair oracle with valid conditional bounds (Thm 1–2);
  • a global lower bound from splitting the curvature into a block-diagonal part and a PSD remainder (Thm 3);
  • an identification of the optimized bound with a block-moment SDP relaxation (Prop 4);
  • an exact decomposition of the certified interval (Eq. 10).

The validation uses eight 6-coordinate restrictions of GPT-2 first-block reconstruction objectives, small enough to enumerate all 868^6 codewords. In one case a pair-fixed point is not optimal, and in four a relaxation gap remains after the certificate is optimized. The appendix adds kernel timings and 3-bit GPT-2 perplexity studies. My main concern is whether the certificate is useful anywhere beyond problems that enumeration already solves.

Critical strengths
  1. The math results are carefully verified against exhaustive enumeration. Floating-point issues are handled with outward rounding and rational repair of the SDP output (App. D.3–D.4), there is an independent verifier, and negative downstream results are reported in full.
  2. The paper makes a useful distinction between kinds of "stopped". Separating certificate optimization, relaxation error and finite suboptimality (Fig. 2, Eq. 10) is clarifying, and the exhaustive cases show that each occurs on real objectives. In the captured QKV example, a gap of 8.29×10−58.29 \times 10^{-5} splits into 2.81×10−52.81 \times 10^{-5} of achievable improvement and 5.49×10−55.49 \times 10^{-5} of relaxation gap (pp.5–6). I also appreciated that the paper keeps objective-level certification apart from model quality, noting that "lower reconstruction error can accompany worse perplexity" (p.9). This distinction is what I learned from the paper, although Weakness 1 explains why it is not yet actionable.
Critical weaknesses
  1. The certificate is only computed where it is not needed, and its practical value is not shown. Every global certificate is for a 6-coordinate restriction with all other coordinates frozen (Sec. 6.1), where enumerating 262,144 codewords is exact and cheap, and all eight cases come from one model. No full-row certificate or SDP cost is reported; the paper itself says the examples "establish neither large-scale SDP efficiency nor model-quality gains" (p.21). More fundamentally, the three-way diagnosis needs F∗F^*, which is known here only because the problems are tiny. The paper acknowledges that "the component gaps are not generally separately observable" (Fig. 2) and that on larger problems "these two contributions generally remain unresolved" (p.9). At realistic scale, the rule therefore reduces to the familiar test F(x^)−L≤ϵF(\hat{x}) - L \le \epsilon.

    The cost and quality evidence does not close this gap. The lazy pair oracle is 55–6×6\times faster than sorting a full bound table, but slightly slower than a direct conditional scan at 3 bits (p.8). The timed float64 version is not itself a certificate (p.28), and the global oracle and the SDP solves are not timed. Pair refinement adds about 0.15% beyond CD3 in calibration loss (p.8). Its 3-bit perplexity is worse than GPTQ (Frantar et al., 2023) in all four settings of Tab. 6, and it wins only under an alternative target that the paper calls exploratory and that "was selected on the discovery draw" (p.35). In a single-layer control, QuIP# (Tseng et al., 2024) reaches about half the calibration error of pair repair (Tab. 25). The paper's main promise, an actionable stopping rule for quantization, is therefore never tested in a setting where it could change a decision. This is the main reason for my rating.

  2. The novelty is limited, closely related work is missing, and the most informative comparisons are not run. Thm 3 is a 2×22 \times 2-block version of separable underestimators, which the paper builds on (Buchheim & Traversi, 2018). The paper itself describes Prop 4 as "a finite-block specialization" of the known relation between quadratic convex reformulation and SDP bounds (Billionnet et al., 2008; p.16). Closely related work is not cited: Buchheim & Wiegele (2013) on SDP relaxations for non-convex quadratic mixed-integer programs, Dong (2016) on adaptive diagonal perturbations, and Kuzmin et al. (2023), who already computed lower bounds on per-layer quantization error for real layers. The abstract's claim that the certificate is tighter than the continuous-box and fixed-curvature controls holds by construction: the box value lies below the moment value, and the fixed-curvature choice μI\mu I belongs to the optimized family (p.7). The comparisons that would show what pair blocks actually buy are missing. These are a scalar-diagonal bound, i.e. the Shor relaxation (Shor, 1987), and merged blocks on the four cases with a relaxation gap; Corollary 5 shows that merging cannot weaken the certificate. Once this is taken into account, I don't see any interesting findings beyond the conceptual distinction above.

References:

  • Billionnet, A., Elloumi, S., and Plateau, M.-C. Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations. RAIRO Operations Research, 2008.
  • Buchheim, C. and Traversi, E. Quadratic combinatorial optimization using separable underestimators. INFORMS Journal on Computing, 2018.
  • Buchheim, C. and Wiegele, A. Semidefinite relaxations for non-convex quadratic mixed-integer programming. Mathematical Programming, 2013.
  • Dong, H. Relaxing nonconvex quadratic functions by multiple adaptive diagonal perturbations. SIAM Journal on Optimization, 2016.
  • Frantar, E., Ashkboos, S., Hoefler, T., and Alistarh, D. GPTQ: Accurate post-training quantization for generative pre-trained transformers. ICLR, 2023.
  • Kuzmin, A., Nagel, M., van Baalen, M., Behboodi, A., and Blankevoort, T. Pruning vs quantization: Which is better? NeurIPS, 2023.
  • Shor, N. Z. Quadratic optimization problems. Soviet Journal of Computer and Systems Sciences, 1987.
  • Tseng, A., Chee, J., Sun, Q., Kuleshov, V., and De Sa, C. QuIP#: Even better LLM quantization with Hadamard incoherence and lattice codebooks. ICML, 2024.
Questions for authors
  1. Requested experiment: can you certify at least one full GPT-2 row (d=768d = 768), or else the largest subproblem within reach? Please report LL, U−LU - L, the SDP size, solver iterations, time and memory, and compare with D=ρID = \rho I and the Shor relaxation (Shor, 1987). This is the experiment most likely to change my assessment.
  2. Requested experiment: on the four cases with a relaxation gap, how much do merged blocks (for example triples, following Corollary 5) and 1×11 \times 1 blocks change the gap, and at what cost?
  3. Clarification: how large are the gaps in Tab. 1 compared with the row or layer reconstruction loss, and with the objective at the initial codeword? Would they ever change a stopping decision in practice?
  4. Clarification: does the moment solution help find better codewords, for instance by rounding it in the case where the pair-fixed point is suboptimal? If not, what does the relaxation offer beyond diagnosing the gap?
  5. Clarification: how exactly do Prop 4 and Eq. (10) differ from Buchheim & Wiegele (2013) and Dong (2016), and how does the work relate to Kuzmin et al. (2023)?

References:

  • Buchheim, C. and Wiegele, A. Semidefinite relaxations for non-convex quadratic mixed-integer programming. Mathematical Programming, 2013.
  • Dong, H. Relaxing nonconvex quadratic functions by multiple adaptive diagonal perturbations. SIAM Journal on Optimization, 2016.
  • Kuzmin, A., Nagel, M., van Baalen, M., Behboodi, A., and Blankevoort, T. Pruning vs quantization: Which is better? NeurIPS, 2023.
  • Shor, N. Z. Quadratic optimization problems. Soviet Journal of Computer and Systems Sciences, 1987.
2 comments

Thank you for the response and for running the block comparison on all eight objectives. The results show that Corollary 5 matters in practice, and I would encourage you to move these results into the main text.

I also agree with your point on Eq. (10). The width U−LU - L indicates when the current certificate family is nearly exhausted, so my statement that the rule reduces to the familiar test F(x^)−L≤ϵF(\hat{x}) - L \le \epsilon was too strong. As the Discussion itself notes, however, on larger problems the finite suboptimality and the relaxation gap "generally remain unresolved" (p.9), so the full diagnosis still needs F∗F^*.

On novelty, I did not claim that a prior result implies your guarantees. My point rests on the paper's own description of Proposition 4 as "a finite-block specialization" (p.16), and on Theorem 3 building on separable underestimators (Buchheim & Traversi, 2018). The technical step beyond known results is small, so the value of the paper depends on showing that the certificate is useful in practice. I would still recommend discussing Buchheim & Wiegele (2013), Dong (2016) and Kuzmin et al. (2023) in the related work.

This is where my main concern remains. As your response states, full-row solver costs, row-loss-normalized gaps and the reconstruction gains from moment rounding are still unmeasured. The stopping decision that the merged bound changes is on a six-coordinate restriction, where enumerating all codewords already gives the exact answer. Until a certificate is computed on a full row, or on a subproblem beyond the reach of enumeration, at a reported cost, and is used to stop or to allocate compute in the quantization pipeline, the paper's practical claim remains untested. I therefore keep my rating.

AuthorsOpenReview ↗

Beyond-enumeration experiments: certified stopping and measured costs

We have now completed the beyond-enumeration stopping experiment requested in your comment. We use all eight captured GPT-2 rows, with 24 and 32 active coordinates per row and eight actual stored FP32 codewords per coordinate: approximately 4.72e21 and 7.92e28 possible assignments. All remaining coordinates are fixed at their quantized values, with their full contribution retained in the objective. We compare the continuous box, scalar finite-domain moments, joint pair moments, and a nested four-coordinate merge on the same objectives and feasible incumbents. All 64 final certificates passed independent exact-rational checks.

The tighter bounds change actual stopping decisions. Pair certificates strictly exceed the scalar relaxation's verified upper value in 16/16 cases and reduce the incumbent-to-bound gap by a median 19.9%. At a common tolerance of 0.5% of the initial full-row reconstruction loss, the scalar certificate stops 5/16 cases; joint block certificates raise this to 9/16. All four additional stops occur among the 14 cases outside the pilot row. These are fresh sequential runs: each visited certificate is computed and independently checked before use, and a certified stop actually skips subsequent certificate work and cross-pair search. At 0.1% and 1%, the corresponding certified early-stop counts are 2/16 and 14/16. No finite optimum is computed or supplied to the controller.

We now report costs and row-loss-normalized gaps alongside these decisions. On CPU, the median cost of computing, repairing, fully separating, and independently verifying one scalar/pair/merged certificate is 2.61/5.63/6.93 seconds. At 0.5%, the complete controller run, including initial search and every visited stage, takes a median 7.71 seconds across all 16 cases, with a range of 1.18-32.37 seconds; source-row preparation is reported separately. The guarantee applies to the active subproblem while other row coordinates remain fixed, and its gap is normalized by the original complete row loss.

Moment rounding also gives measurable reconstruction gains. With a frozen verified pair witness, matched counts of 17 candidates and the same per-candidate local-repair budget, it improves the feasible objective over the no-moment control in 4/16 cases, by 0.120%-0.224% of the initial complete row loss, with ties in the other 12. Separately costed conditional-expectation rounding improves 5/16 cases, reaching 0.233%. We retain the common incumbent and evaluate actual finite codewords throughout; the moment primal value is never used as a reconstruction result.

The new experiments also sharpen the diagnosis without F*. Let v1 be the pair relaxation value, [L1,U1] its verified interval, and L2 another valid lower bound for the same finite problem. Then F*_A-v1 >= L2-U1. The merged lower bound exceeds the pair upper value in 15/16 new cases, certifying a positive pair relaxation gap without enumeration. Moreover, when U1-L1 is small and B-U1>epsilon, further optimization of that family cannot certify the fixed incumbent at tolerance epsilon. This gives actionable information from B,L,U even when a complete numerical decomposition is unavailable.

We will bring the eight-objective block comparison and this costed stopping study into the main text, and explicitly discuss Buchheim-Wiegele (2013), Dong (2016), and Kuzmin et al. (2023). The scalar finite-domain moment relaxation is included as the established control, so the new comparison directly isolates what joint block information contributes. Our contribution connects signed finite-block curvature and a budgeted finite oracle to a master/separation interval that remains valid at finite computation budgets. The added results demonstrate its practical consequence: additional certified stopping decisions and usable reconstruction improvements on problems beyond enumeration, at a reported cost. We believe this directly addresses the remaining practical-utility concern and warrants reconsideration of the rating.

Reviewer_x5qZOpenReview ↗
Rating
1
Confidence
1
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies fixed-codebook quantization and how to give a certified stopping rule. However, this paper is difficult to follow:

  1. It does not contain any reference in the introduction section, which makes it difficult to know which parts were studied before and how this work compares to the existing works.

  2. It does not clear what is the relation between each sections. It introduce different optimization atsks in different sections, however, their interation is not presented clearly.

Critical strengths

None, since it is difficult for me to follow the paper.

Critical weaknesses

See the summary part. I do not think this paper can be accepted in ICLR since it is difficult to follow.

Questions for authors

See the summary part.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.