Linear Quantization: From Codebooks to an Affine Gridالتكميم الخطي: من دفاتر الترميز إلى شبكة أفينية (affine)

Take the 4×4 weight matrix from last lecture and quantize it two ways to 2 bits. With K-means, each weight becomes an index between 0 and 3, and a four-entry table says index 3 means 2.00, index 2 means 1.50, and so on. With linear quantization, each weight becomes a signed code between -2 and 1, and one formula, (q - (-1)) × 1.07, turns any code back into a real number. Both versions use 2 bits per weight. The difference shows up only when the layer runs.

خذ مصفوفة الأوزان 4×4 من المحاضرة السابقة وكمّمها بطريقتين إلى 2 بت. مع K-means، يصبح كل وزن فهرسًا بين 0 و3، وجدول من أربعة مدخلات يقول إن الفهرس 3 يعني 2.00، والفهرس 2 يعني 1.50، وهكذا. ومع التكميم الخطي، يصبح كل وزن رمزًا بإشارة (signed) بين -2 و1، وصيغة واحدة هي (q - (-1)) × 1.07 تعيد أي رمز إلى عدد حقيقي. كلا النسختين تستخدم 2 بت لكل وزن. الفرق لا يظهر إلا عندما تعمل الطبقة.

The table that frames the lectureالجدول الذي يؤطّر المحاضرة

Slide 2 compares the schemes on two rows: what sits in memory, and what kind of arithmetic the processor performs. Learn it as a grid, because it is an easy short-answer question.

تقارن الشريحة 2 بين الطرق على صفّين: ما الذي يقبع في الذاكرة، وأي نوع من الحساب ينفّذه المعالج. احفظه على شكل شبكة، لأنه سؤال سهل من نوع الإجابة القصيرة.

K-means-based quantization wins on storage but not on compute. Before a multiply can happen, every index must be looked up in the Codebook, and what comes out is a float. The multiply-accumulate (MAC) that follows is a floating-point MAC, exactly as in the original model. K-means saves memory and memory traffic, and that is all it saves.

K-means quantization يتفوق في التخزين لكن ليس في الحساب. قبل أن يحدث أي ضرب، يجب البحث عن كل فهرس في الـ codebook، وما يخرج من هذا البحث عدد عشري (float). وعملية الضرب والجمع التراكمي (MAC) التي تليه هي MAC عشرية، تمامًا كما في النموذج الأصلي. K-means يوفّر الذاكرة وحركة البيانات من الذاكرة وإليها، وهذا كل ما يوفّره.

Linear quantization changes the second row too. The reason is algebraic. Every real value in a tensor is written as r = S(q - Z) with the same Scale (S) S and the same Zero point (Z) Z. In a dot product of weights and inputs, the common scale factors out of the whole sum:

التكميم الخطي يغيّر الصف الثاني أيضًا. والسبب جبري. كل قيمة حقيقية في الـ tensor تُكتب على الصورة r = S(q - Z) بنفس الـ scale S ونفس الـ zero point Z. وفي حاصل الضرب النقطي (dot product) بين الأوزان والمدخلات، يخرج الـ scale المشترك عاملًا من المجموع كله:

Everything inside the sum is integer subtraction, multiplication and addition. The floats S_W S_X are applied once per output, not once per MAC, and part 3 shows that even that single rescale can be done as an integer multiply and a bit shift. That is what makes Integer-only inference possible. A codebook gives no such shortcut: its centroids are arbitrary floats like 2.00, 1.50, 0.00 and -1.00, with no common factor and offset to pull out.

كل ما داخل المجموع عمليات طرح وضرب وجمع على أعداد صحيحة. أما القيم العشرية S_W S_X فتُطبَّق مرة واحدة لكل مخرج، لا مرة لكل MAC، والجزء 3 يبيّن أن حتى إعادة التحجيم (rescale) الوحيدة هذه يمكن تنفيذها بضرب صحيح وإزاحة بتات (bit shift). وهذا ما يجعل integer-only inference ممكنًا. أما الـ codebook فلا يقدّم اختصارًا كهذا: مراكزه أعداد عشرية عشوائية مثل 2.00 و1.50 و0.00 و-1.00، ليس لها عامل مشترك ولا إزاحة (offset) مشتركة يمكن إخراجهما.

Storage also differs a little, even at the same bit width. For the 16 example weights:

ويختلف التخزين قليلًا أيضًا، حتى عند نفس عدد البتات (bit width). بالنسبة لأوزان المثال الـ 16:

For a real layer with millions of weights the side information is negligible in both schemes, so the storage row is roughly a tie. The computation row decides the matter. Integer adders and multipliers cost far less energy and silicon area than floating-point ones (recall the energy table from Lecture 05-1), and many microcontrollers and NPUs have no floating-point unit at all.

في طبقة حقيقية فيها ملايين الأوزان تكون المعلومات الجانبية (side information) مهملة في الطريقتين، لذا يكون صف التخزين متعادلًا تقريبًا. صف الحساب هو الذي يحسم الأمر. وحدات الجمع والضرب الصحيحة تستهلك طاقة ومساحة سيليكون أقل بكثير من نظيراتها العشرية (تذكّر جدول الطاقة من المحاضرة 05-1)، وكثير من المتحكمات الدقيقة (microcontrollers) ووحدات NPU لا تحتوي على وحدة أعداد عشرية (floating-point unit) أصلًا.

Start with one weight, 1.48, and a ruler whose marks are 1.07 apart. Divide by the mark spacing: 1.48 / 1.07 = 1.383. The nearest whole mark is 1. Now shift every mark number down by one so that the mark sitting on real zero is called -1. The weight lands on mark 1 + (-1) = 0. That is the whole of the forward step.

ابدأ بوزن واحد، 1.48، ومسطرة تفصل بين علاماتها مسافة 1.07. اقسم على المسافة بين العلامات: 1.48 / 1.07 = 1.383. أقرب علامة صحيحة هي 1. الآن أنقص رقم كل علامة بواحد بحيث تُسمّى العلامة الواقعة على الصفر الحقيقي -1. يقع الوزن على العلامة 1 + (-1) = 0. وهذه هي الخطوة الأمامية بكاملها.

The affine mappingالتحويل الـ affine

Linear quantization ties every integer code q to a real value r with an Affine mapping: a multiply by a scale plus a fixed offset.

يربط التكميم الخطي كل رمز صحيح q بقيمة حقيقية r عبر affine mapping: ضرب في scale مع إزاحة (offset) ثابتة.

• Scale (S) S is a floating-point number: the real distance between two neighbouring codes. In the example S = 1.07.الـ scale S عدد عشري (floating-point): هو المسافة الحقيقية بين رمزين متجاورين. في المثال S = 1.07.
• Zero point (Z) Z is an integer of the same type as the codes: the code that means real 0, since S(Z - Z) = 0 for any S. In the example Z = -1; part 2 derives it as round(q_min - r_min / S) = round(-2 + 1.08 / 1.07) = round(-0.99) = -1.الـ zero point Z عدد صحيح من نفس نوع الرموز: هو الرمز الذي يعني الصفر الحقيقي 0، لأن S(Z - Z) = 0 لأي قيمة S. في المثال Z = -1، والجزء 2 يشتقّه على أنه round(q_min - r_min / S) = round(-2 + 1.08 / 1.07) = round(-0.99) = -1.
• The codes are signed Bit width (N) integers. With N = 2, q_min and q_max are -2 and 1, so there are only 4 levels.الرموز أعداد صحيحة بإشارة (signed) بعدد بتات يحدده الـ bit width. عندما N = 2، تكون قيمتا q_min, q_max هما -2 و1، فلا يوجد إلا 4 مستويات.

The mapping is called affine rather than linear in the strict sense because of the offset Z. Its job is to give real zero an exact code. Zero padding, ReLU outputs and pruned weights are all exactly zero, and Jacob et al. require that they quantize with no error at all. Part 2 shows how to derive S and Z from r_min and r_max. Here, take them as given.

يُسمّى هذا التحويل affine وليس خطيًا (linear) بالمعنى الدقيق بسبب الإزاحة Z. مهمتها أن تعطي الصفر الحقيقي رمزًا دقيقًا (exact code). الحشو بالأصفار (zero padding) ومخرجات ReLU والأوزان المقلّمة (pruned) كلها أصفار تامة، وJacob et al. يشترطون أن تُكمَّم دون أي خطأ على الإطلاق. الجزء 2 يبيّن كيف نشتق S وZ من r_min, r_max. هنا، اعتبرهما معطيين.

The forward formula the slides leave outالصيغة الأمامية التي تتجاهلها الشرائح

Slide 4 shows the weights turning into codes, but it never writes down how. Inverting r = S(q - Z) gives q = r / S + Z, which is usually not a whole number. So round it, and clamp anything that falls outside the integer range:

تعرض الشريحة 4 الأوزان وهي تتحول إلى رموز، لكنها لا تكتب أبدًا كيف يحدث ذلك. عكس الصيغة r = S(q - Z) يعطي q = r / S + Z، وهي في العادة ليست عددًا صحيحًا. لذا نقرّبها (round)، ونقصّ (clamp) أي قيمة تقع خارج مدى الأعداد الصحيحة:

Rounding r / S before adding Z works because Z is already an integer, and it keeps real 0 landing exactly on code Z. This is the form given in the Nagel et al. white paper on neural network quantization.

تقريب r / S قبل إضافة Z يصحّ لأن Z عدد صحيح أصلًا، وهو يضمن أن يقع الصفر الحقيقي 0 تمامًا على الرمز Z. هذه هي الصيغة الواردة في الورقة البيضاء (white paper) لـ Nagel et al. عن تكميم الشبكات العصبية.

Reading the 2-bit codesقراءة الرموز بطول 2 بت

The codes are stored in Two's complement. With two bits the leading bit carries weight -2 and the trailing bit carries +1, which gives the table on slide 4. The slides colour each level: blue for 1, pink for 0, orange for -1, green for -2. The simulator below also gives each of the four levels its own colour, using the site palette, with a legend under the matrices.

تُخزَّن الرموز بصيغة two's complement. مع بتين، يحمل البت الأول وزن -2 ويحمل البت الأخير وزن +1، وهذا يعطي الجدول في الشريحة 4. تلوّن الشرائح كل مستوى: الأزرق لـ 1، والوردي لـ 0، والبرتقالي لـ -1، والأخضر لـ -2. والمحاكي أدناه يعطي كذلك كل مستوى من المستويات الأربعة لونه الخاص، باستخدام ألوان الموقع، مع مفتاح ألوان تحت المصفوفات.

Slide 4 turns 16 weights into codes, then back into numbers. What comes back has only four distinct values: -1.07, 0, 1.07 and 2.14. The weights 1.48, 1.53 and 1.49 all come back as 1.07. That collapse is the price of using 2 bits.

تحوّل الشريحة 4 الأوزان الـ 16 إلى رموز، ثم تعيدها إلى أعداد. ما يعود ليس فيه إلا أربع قيم مختلفة: -1.07 و0 و1.07 و2.14. الأوزان 1.48 و1.53 و1.49 كلها تعود على أنها 1.07. هذا الانهيار هو ثمن استخدام 2 بت.

Reconstruct with the affine mapإعادة البناء بالتحويل الـ affine

The Reconstructed weights are just S(q - Z) applied to each Quantized value (q). With Z = -1, that is (q + 1) × 1.07:

الـ reconstructed weights ما هي إلا S(q - Z) مطبّقة على كل quantized value. ومع Z = -1، تصبح (q + 1) × 1.07:

• q = 1 gives 2.14, and q = 0 gives 1.07.q = 1 يعطي 2.14، وq = 0 يعطي 1.07.
• q = -1 gives 0 exactly, and q = -2 gives -1.07.q = -1 يعطي 0 بالضبط، وq = -2 يعطي -1.07.

The reconstructed matrix is [[2.14, -1.07, 1.07, 0], [0, 0, -1.07, 2.14], [-1.07, 2.14, 0, -1.07], [2.14, 0, 1.07, 1.07]]. In a real integer pipeline this matrix is never built in memory. It is the meaning of the codes, which is what we compare against the original to measure the damage.

المصفوفة المعاد بناؤها هي [[2.14, -1.07, 1.07, 0], [0, 0, -1.07, 2.14], [-1.07, 2.14, 0, -1.07], [2.14, 0, 1.07, 1.07]]. في خط معالجة صحيح حقيقي (integer pipeline) لا تُبنى هذه المصفوفة في الذاكرة أبدًا. إنها معنى الرموز، وهي ما نقارنه بالأصل لقياس حجم الضرر.

Quantization error and the S/2 boundخطأ التكميم والحد S/2

The Quantization error of each cell is the original minus the reconstruction, e = r - S(q - Z):

الـ quantization error لكل خانة هو القيمة الأصلية ناقص القيمة المعاد بناؤها، e = r - S(q - Z):

Round-to-nearest picks the closest level, and neighbouring levels are S apart, so a value that is not clipped is never more than half a step from its level. For every such value, |e| ≤ S/2 = 0.535. The worst cell is 1.53: it divides to 1.430, rounds down to code 0, and comes back as 1.07, an error of 0.46. That is close to the bound, because 1.53 sits near the midpoint 1.605 between 1.07 and 2.14. The two zeros have error 0, as promised by the exact zero point.

التقريب إلى الأقرب (round-to-nearest) يختار أقرب مستوى، والمستويات المتجاورة تفصل بينها مسافة S، لذا فالقيمة التي لم تُقصّ (not clipped) لا تبعد أبدًا عن مستواها أكثر من نصف خطوة. لكل قيمة كهذه، |e| ≤ S/2 = 0.535. أسوأ خانة هي 1.53: قسمتها تعطي 1.430، فتُقرَّب للأسفل إلى الرمز 0، وتعود على أنها 1.07، بخطأ قدره 0.46. وهذا قريب من الحد، لأن 1.53 تقع قرب نقطة المنتصف 1.605 بين 1.07 و2.14. والصفران خطؤهما 0، كما يضمن الـ zero point الدقيق.

More than half a step beyond either end level, clamping takes over and the error grows with the distance. Nagel et al. call this clipping error, as opposed to rounding error. A wider range means less clipping but a larger S and more rounding error. Choosing the range is the central trade-off in linear quantization.

عندما تبتعد القيمة أكثر من نصف خطوة خارج أيّ من المستويين الطرفيين، يتولى القصّ (clamping) الأمر ويكبر الخطأ مع المسافة. يسمّي Nagel et al. هذا خطأ القصّ (clipping error)، في مقابل خطأ التقريب (rounding error). المدى الأوسع يعني قصًّا أقل، لكنه يعني S أكبر وخطأ تقريب أكبر. اختيار المدى هو المفاضلة (trade-off) المحورية في التكميم الخطي.

Why the top level is 2.14 and not 2.12لماذا المستوى الأعلى 2.14 وليس 2.12

The largest weight is r_max = 2.12, yet the top level is 2.14, and the bottom level -1.07 sits just above r_min = -1.08. Two roundings cause this. The exact scale is 3.20 / 3 = 1.0667, which the slides round to 1.07. The exact offset would be -0.99, but the zero point must be an integer so that real zero stays exact, so it is rounded to -1. Together these shift and stretch the grid slightly, so it covers [-1.07, 2.14] instead of [-1.08, 2.12]. The cost is tiny: -1.08 still reconstructs with an error of only -0.01, well within S/2.

أكبر وزن هو r_max = 2.12، ومع ذلك فالمستوى الأعلى هو 2.14، والمستوى الأدنى -1.07 يقع فوق r_min = -1.08 بقليل. السبب عمليتا تقريب. الـ scale الدقيق هو 3.20 / 3 = 1.0667، وتقرّبه الشرائح إلى 1.07. والإزاحة الدقيقة كانت ستكون -0.99، لكن الـ zero point يجب أن يكون عددًا صحيحًا ليبقى الصفر الحقيقي دقيقًا، لذا يُقرَّب إلى -1. معًا، تُزيح هاتان العمليتان الشبكة وتمطّانها قليلًا، فتغطي [-1.07, 2.14] بدلًا من [-1.08, 2.12]. والكلفة ضئيلة: -1.08 ما زالت تُعاد بناؤها بخطأ قدره -0.01 فقط، وهو أقل بكثير من S/2.

Try it at other bit widthsجرّبه بأعداد بتات أخرى

The simulator below runs the same matrix through the same formulas. At 2 bits it reproduces slide 4 cell for cell. Slide up to 8 bits, the INT8 format used in deployment, and watch S shrink by roughly half per extra bit, the levels multiply, and the error heatmap fade.

المحاكي أدناه يمرّر المصفوفة نفسها عبر الصيغ نفسها. عند 2 بت يعيد إنتاج الشريحة 4 خانةً بخانة. حرّك المؤشر حتى 8 بت، وهي صيغة INT8 المستخدمة في النشر (deployment)، وراقب S وهي تتقلص إلى النصف تقريبًا مع كل بت إضافي، والمستويات وهي تتضاعف، وخريطة الخطأ الحرارية (heatmap) وهي تبهت.