- 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
- The paper provides a sound theory support on the algorithm
- The experiment results show significant improvement in the certificate for small cases
Critical weaknesses
- The introduction did not give a good enough background, which makes it difficult for researchers new to the field to follow the work.
- 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.
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) lower-bound evaluations after k 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−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,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−8, the pair certificate leaves the decision unresolved, while the merged-block certificate certifies stopping.