GPTQ-2D: 세제곱 시간 복잡도의 양방향 적응형 반올림

GPTQ-2D: Cubic-Time Two-Sided Adaptive Rounding

GPTQ 또는 Babai의 가장 가까운 평면 알고리즘과 같은 적응형 반올림 방법은 이차 메트릭 하에서 실수 행렬을 정수로 변환합니다. 이러한 방법들은 고정된 순서대로 각 요소를 하나씩 처리하며, 각 반올림 오류를 아직 처리되지 않은 요소로 삼각행렬 피드백 매트릭스를 통해 전파합니다. 본 연구에서는 이와 대칭인 양방향 버전을 다룹니다. 여기서 고정된 비특이 행렬 기저가 잔차 행렬의 왼쪽과 오른쪽에 모두 작용하며, 일반적인 일방향 경우는 항등 행렬을 오른쪽 기저로 사용하는 특수한 경우입니다. 행렬을 벡터화하면 양방향 목표는 이차 메트릭으로 변환되며, 그 Gram 행렬은 Kronecker 곱 형태를 가집니다. 따라서 1차원 알고리즘이 그대로 적용되지만, 행렬 차원에 대해 4차 시간 복잡도를 갖습니다. 본 연구에서는 동일한 반올림 결과를 생성하면서 세제곱 시간 복잡도를 가지는 GPTQ-2D를 제시합니다. GPTQ-2D는 대각선 위 항과 아래 항을 독립적으로 처리하며, 동일한 대각선 위에 있는 요소들은 병렬로 반올림됩니다.

Adaptive rounding methods such as GPTQ, or equivalently Babai's nearest plane algorithm, round a real matrix to integers under a quadratic metric. They process the entries in a fixed order, one at a time, propagating each rounding error to the entries not yet processed through a triangular feedback matrix. We study the two-sided version of this task, in which fixed nonsingular basis matrices act on both the left and the right of the residual; the familiar one-sided case is the special case of an identity right basis. Vectorizing the matrix turns the two-sided objective into a quadratic metric whose Gram matrix is a Kronecker product, so the one-dimensional algorithm applies verbatim, but takes quartic time in the matrix dimension. We present GPTQ-2D, which produces the identical rounded matrix in cubic time. It rounds the entries anti-diagonal by anti-diagonal; entries on the same anti-diagonal are independent and are rounded in parallel.