무작위 Hadamard Transform을 이용한 증명 가능한 양자화 (Provable Quantization with Randomized

무작위 투영 (Random Projection)에 이은 스칼라 양자화 (Scalar Quantization)를 통한 벡터 양자화 (Vector Quantization)는 유사도 검색 (Similarity Search)부터 연합 학습 (Federated Learning) 및 KV 캐시 압축 (KV Cache Compression)에 이르기까지 다양한 응용 분야를 가진 머신러닝 (Machine Learning)의 근본적인 프리미티브 (Primitive)입니다. 밀집 무작위 회전 (Dense Random Rotations)은 깔끔한 이론적 보장을 제공하지만, $Θ(d^2)$의 시간이 소요됩니다. 무작위 Hadamard Transform ($HD$)은 이 비용을 $O(d ext{ log } d)$로 줄여주지만, 그 이산적 구조 (Discrete Structure)로 인해 분석이 복잡해지며 더 약하거나 순수하게 경험적인 압축 보장으로 이어집니다. 본 연구에서는 이 접근 방식의 변형인 단일 무작위 Hadamard Transform을 이용한 디더링 양자화 (Dithered Quantization)를 연구합니다. 구체적으로, 양자화기 (Quantizer)는 입력 벡터에 $HD$를 적용하고 양자화하기 전에 무작위 스칼라 오프셋 (Random Scalar Offset)을 빼서, 무시할 수 있는 비용으로 추가적인 무작위성을 주입합니다. 우리는 이 접근 방식이 편향되지 않았으며 (Unbiased), 진정한 무작위 회전 행렬 (Random Rotation Matrices)로 달성 가능한 것과 점근적으로 일치하는 평균 제곱 오차 (Mean Squared Error, MSE) 경계값을 제공함을 증명합니다. 특히, 우리는 TurboQuant의 디더링 버전이 좌표당 $b$ 비트에서 $igl(π ext{ } ext{sqrt}(3)/2 + o(1)igr) ext{ } ext{cdot} ext{ }4^{-b}$의 평균 제곱 오차를 달성함을 증명하며, 여기서 $o(1)$ 항은 양자화 레벨 (Quantization Levels)의 수가 증가함에 따라 모든 단위 벡터 (Unit Vectors)와 모든 차원 (Dimensions)에 대해 균일하게 소멸합니다.