Improving BM25 Code Retrieval Under Fixed Generic Tokenization: Adaptive q-Log Odds as a Drop-In BM25 Fix

ملخص تقني: تحسين استرجاع الأكواد باستخدام BM25 في ظل التجزئة العامة الثابتة

1. بيان المشكلة

في أنظمة استرجاع الأكواد المعززة بالاسترجاع (RAG)، تظهر نقطة فشل حرجة عندما يكون ملف المصدر ذو الصلة غائباً عن السياق المسترجع. يحدث هذا غالباً في أنظمة "التجزئة العامة الثابتة" (frozen generic tokenization)، حيث يتم بناء فهرس BM25 بواسطة بنية تحتية للبحث (مثل Lucene أو Elasticsearch أو Tantorant) باستخدام محلل (analyzer) مضبوط للغات الطبيعية بدلاً من الأكواد. وغالباً ما لا يستطيع الممارسون تعديل هذا المحلل.

تحت هذه القيود، يفشل نظام BM25 القياسي في التمييز بشكل كافٍ بين معرفات الأكواد الفريدة (مثل handleWebSocketUpgrade) والرموز (tokens) الشائعة والمتكررة. يستخدم نموذج حساب التردد العكسي (IDF) القياسي لـ Robertson–Spärck-Jones (RSJ) دالة لوغاريتمية: $\log((N - n_t + 0.5)/(n_t + 0.5))$. ولأن اللوغاريتم ينمو ببطء، فإنه "يقلل من الفصل" في ذيل التوزيع. فالرمز الذي يظهر في ملف واحد فقط ($df=1$) والرمز الذي يظهر في 50 ملفاً يحصلان على أوزان IDF تختلف بمقدار ثابت صغير بدلاً من اختلاف بمقدار رتبة عشرية كاملة. ونتيجة لذلك، فإن الملفات "الذهبية" التي تحتوي على معرفات فريدة غالباً ما يتم ترتيبها أدنى من ملفات "المشتتات" التي تشترك في عدد قليل من الرموز الشائعة وغير الفريدة، مما يملأ نافذة سياق الوكيل (agent) بأكواد غير ذات صلة.

2. المنهجية: q-Log Odds التكيفية

تقترح الورقة حلاً "جاهز للاستخدام" (drop-in fix) يعدل فقط اللوغاريتم الخارجي لحساب IDF الخاص بـ BM25، مع ترك تشبع التردد الطرفي (term-frequency saturation) والتجزئة دون تغيير.

• التحويل: استبدل المؤلفون اللوغاريتم القياسي بـ لوغاريتم Tsallis q-log (أو $q$-log)، المعرف بـ:
  $$\ln_q(x) = \frac{x^{1-q} - 1}{1 - q}$$
  ويصبح الـ IDF الجديد:
  $$idf_{RSJ}^q(t) = \ln_q\left(\frac{N - n_t + \delta}{n_t + \delta}\right)$$
  حيث $\delta = 0.5$.

• الخصائص الرياضية:

  • استعادة BM25: عند $q=1$، يستعيد التحويل نموذج BM25 التقليدي تماماً عبر قاعدة لوبيتال ($\lim_{q \to 1} \ln_q(x) = \log x$).
  • تضخيم قانون القوة (Power-Law Amplification): عندما تكون $q < 1$، يعمل التحويل كتحويل Box-Cox لـ RSJ odds بمعامل $\lambda = 1-q$. وفي حالة الرموز شديدة الندرة ($n_t \ll N$)، ينمو الـ IDF كقانون قوة ($x^{1-q}$)، مما يضخم بشكل كبير وزن الـ hapaxes (الكلمات التي ظهرت مرة واحدة فقط، $df=1$) مقارنة بالرموز الأقل ندرة.
  • التشبع: عندما تكون $q > 1$، يتشبع الـ IDF، مما يؤدي فعلياً إلى إلغاء القدرة على التمييز للرموز النادرة.

• التنفيذ: تتطلب الطريقة تمريرة واحدة فقط فوق مصفوفة الدرجات المتفرقة (sparse score matrix) عند تحميل الفهرس لإعادة تحجيم عمود الـ IDF. وتظل سرعة الاستعلام دون تغيير.

3. المساهمات الرئيسية

1. q-Log RSJ-odds IDF: هو تشويه لمعامل واحد لـ BM25 IDF يستعيد BM25 تماماً عند $q=1$ ويعمل كمضخم لقانون القوة للرموز النادرة عندما تكون $q < 1$.
2. حدود الأداء المثالية (Oracle Performance Bounds): على مجموعة بيانات CoIR CodeSearchNet الخاصة بلغة Go (182 ألف مستند) مع تجزئة عامة ثابتة، أدى ضبط $q$ عند $0.05$إلى تحسين NDCG@10 من **0.2575 إلى 0.4874** (زيادة نسبية قدرها +89.3$p \le 10^{-4}$) مع عدم وجود أي انعكاس في الإشارة في 10,000 عينة من إعادة أخذ العينات (bootstrap resamples).
3. المتنبئ المتكيف مع المجموعة (Corpus-Adaptive Predictor): متنبئ مغلق الصيغة، خالٍ من التسميات (label-free)، وهو $q_{pred} = 1 - 7.28 \cdot h_{tok}$ (حيث $h_{tok}$ هي كثافة الـ hapax) والذي يقدر قيمة $q$ المثلى من إحصائيات المجموعة وحدها. يحقق هذا المتنبئ استعادة قدرها 0.72 في اختبار "ترك لغة واحدة واستبعادها" (leave-one-language-out)، ويعود بشكل صحيح إلى $q \approx 1$ للمجموعات التي يكون فيها BM25 مثالياً بالفعل (مثل Python).
4. استبعاد أثر المجزئ (Tokenizer Ablation): توضح الدراسة أن المكاسب في الأداء من $q$-IDF تعتمد بشكل كبير على المجزئ (tokenizer). فعند استخدام مجزئ مدرك للمعرفات (يقوم بتقسيم handleWebSocketUpgrade إلى رموز فرعية)، تنهار المكاسب الإضافية من $q$-IDF. وهذا يؤكد أن قيمة الطريقة تكمن في حالة "المجزئ الثابت".
5. الوكلاء المرجعيون (Agent-Relevant Proxies): تظهر الطريقة مكاسب كبيرة في Recall@K-tokens (كفاءة نافذة السياق)، مما يزيد من احتمالية ظهور الملف الذهبي ضمن ميزانية 8 آلاف رمز من 48.1% إلى 68.8% في لغة Go.

4. النتائج التجريبية

• الكود مقابل النص: تحقق الطة مكاسب هائلة في مجموعات الأكواد ذات ذيول المعرفات الكثيفة (Go, Java, Ruby) ولكنها تحقق مكاسب تقترب من الصفر في النصوص الطبيعية (مجموعات BEIR) ولغة Python.
  • Go: $q_{opt} = 0.05$، زيادة في NDCG@10 بنسبة +89.3%.
  • Java/Ruby: مكاسب إيجابية ملحوية ($q_{opt} \approx 0.70-0.90$).
  • Python: $q_{opt} = 1.00$. المعرفات في Python غالباً ما تكون كلمات تشبه القواميس تُعاد استخدامها عبر الملفات؛ الإشارة تكمن في فئات الـ $df$ المتوسطة، والتي يعالجها الـ log-IDF القياسي بشكل مثالي. التباعد عن $q=1$ يشوه هذه الفئات.
  • BEIR (النص): لا توجد مكاسب معنوية؛ حيث تنهار الطريقة لتصبح BM25 لأن الـ $q$ المثالي يقع عند 1 أو أعلى.
• التوسع (Scaling): تتناسب مكاسب الأداء طردياً مع حجم المجموعة. في لغة Go، تزداد المكسب المطلق من +0.061 عند 1 ألف مستند إلى +0.227 عند 182 ألف مستند.
• المقارنة المرجعية (Baselines): تفوق نموذج $q$-log على نماذج إعادة تحجيم الـ $idf_\gamma$ البسيطة ونماذج Divergence-from-Randomness (DFR-DPH)، والتي تفشل في استرجاع الأكواد بسبب سوء معايرة تطبيع التردد الطرفي (term-frequency normalization).

5. الأهمية والنطاق

تضع الورقة هذا العمل ليس كبديل للتجزئة الصحيحة، بل كتدخل ضروري عندما تمنع القيود البنيوية ذلك.

• الفائدة العملية: بالنسبة للممارسين الذين يستخدمون مجموعات بحث مدارة (Elasticsearch, OpenSearch) حيث يكون المحلل (analyzer) ثابتاً، تقدم هذه الطة تغييراً بسيطاً (سطر واحد) في حساب IDF يمكنه مضاعفة فعالية استرجاع الأكواد تقريباً دون الحاجة لإعادة الفهرسة أو تغيير المجزئ.
• الآلية: ينبع التحسن من تضخيم الـ hapaxes ذات الـ $df=1$ (المعرفات الفريدة مثل handleWebSocketUpgrade)، وهي المميّزات الأساسية في استرجاع الأكود والتي يتم تسطيحها بواسطة التوزين اللوغاريتمي القياسي.
• القيود: يذكر المؤلفون صراحة أنه إذا كان المشغل يتحكم في المجزئ، فإن أفضل نهج هو استخدام محلل مدرك للمعرفات والإبقاء على $q=1$. إن دمج $q$-IDF فوق تجزئة مدركة للمعرفات يعطي نتائج ضئيلة أو سلبية. كما أن الطريقة تعتمد على اللغة؛ فهي لا تقدم أي فائدة (وقد تسبب تراجعاً طفيفاً) في اللغات ذات كثافة الـ hapax المنخفضة مثل Python أو PHP عند النطاق الكامل.

باختار، تحدد الورقة نمط فشل محدد في استرجاع الأكواد تحت ظروف التجزئة الثابتة، وتوفر حلاً رياضياً متيناً ومنخفض التكلفة ومتكيفاً، يستعيد القدرة التمييزية للمعرفات الفريدة دون الحاجة لتغيير المجزئ أو إعادة الفهرسة.