突破性能瓶頸：動態(tài)超級塊剪枝如何重塑信息檢索效率

在當(dāng)今數(shù)據(jù)爆炸的時代，高效的信息檢索系統(tǒng)對于各類應(yīng)用至關(guān)重要，從搜索引擎到基于檢索增強(qiáng)的大語言模型（RAG）。隨著學(xué)習(xí)型稀疏表示模型的興起，如何在保持高檢索質(zhì)量的同時提升檢索速度成為研究熱點(diǎn)。本文深入探討一項(xiàng)革命性技術(shù)——動態(tài)超級塊剪枝（Superblock Pruning，簡稱SP），這一創(chuàng)新方法在保持高相關(guān)性的前提下，顯著提升了稀疏檢索的效率。

稀疏檢索的挑戰(zhàn)與機(jī)遇

稀疏檢索模型如BM25和學(xué)習(xí)型稀疏表示（如SPLADE、E-SPLADE等）在僅使用CPU的服務(wù)器環(huán)境中廣受歡迎，主要得益于它們能夠充分利用高效的倒排索引實(shí)現(xiàn)。傳統(tǒng)的稀疏檢索速度優(yōu)化通常采用動態(tài)秩安全索引剪枝技術(shù)，該技術(shù)能夠準(zhǔn)確跳過那些得分較低、不可能出現(xiàn)在最終top-k結(jié)果中的文檔。

近年來，基于塊的檢索方法成為研究熱點(diǎn)，這類方法將文檔分配到塊（或稱為簇）中，并利用塊級信息改進(jìn)索引遍歷順序，同時剪枝低分文檔組。然而，這些方法在處理大規(guī)模數(shù)據(jù)集時仍然面臨效率挑戰(zhàn)，尤其是當(dāng)需要保持高相關(guān)性時。

超級塊剪枝：創(chuàng)新的兩級剪枝策略

超級塊剪枝（SP）技術(shù)在現(xiàn)有基于塊的剪枝方法基礎(chǔ)上進(jìn)行了創(chuàng)新性擴(kuò)展。SP方法將一系列連續(xù)的文檔塊均勻聚合成超級塊，然后以自上而下的方式進(jìn)行在線索引遍歷。這種設(shè)計(jì)為每個超級塊分配固定數(shù)量的文檔塊，簡化了向量化和緩存優(yōu)化過程，同時提供了具有概率安全保證的兩級剪枝機(jī)制。

SP的核心創(chuàng)新在于其兩級剪枝策略：首先計(jì)算所有超級塊的邊界信息并進(jìn)行剪枝，然后再計(jì)算塊的邊界并進(jìn)行剪枝。具體來說，SP執(zhí)行以下動態(tài)剪枝步驟：

1. 對于超級塊X，計(jì)算該超級塊內(nèi)文檔的最大和平均排名分?jǐn)?shù)邊界
2. 當(dāng)超級塊的最大和平均超級塊邊界滿足特定條件時，該超級塊被剪枝
3. 對于文檔塊B，如果其邊界和滿足特定條件，則剪枝該塊
4. 對于所有未被剪枝的塊，按照其邊界和值的降序?qū)ο鄳?yīng)的文檔塊進(jìn)行排序和評分

這種方法允許SP更有效地跳過文檔塊，以排名安全或概率排名安全的方式加速檢索。剪枝一個超級塊不僅避免了計(jì)算子塊的最大分?jǐn)?shù)，還避免了對其子塊內(nèi)文檔的評分，從而大幅提升檢索效率。

理論保證與實(shí)現(xiàn)優(yōu)化

SP具有與ASC類似的排名安全μ-競爭性質(zhì)?？梢宰C明，SP的平均top-k'排名分?jǐn)?shù)與任何排名安全檢索算法R在μ因子內(nèi)相同。作為額外保障，如果我們假設(shè)文檔的排名分?jǐn)?shù)在每個超級塊內(nèi)獨(dú)立同分布，SP還提供概率安全性。

在實(shí)現(xiàn)層面，SP采用了多項(xiàng)優(yōu)化策略：

CPU緩存使用優(yōu)化

SP使用SIMD指令計(jì)算相關(guān)公式。當(dāng)順序計(jì)算所有查詢項(xiàng)的這些公式而不進(jìn)行塊跳過時，現(xiàn)代編譯器可以輕松向量化其實(shí)現(xiàn)，現(xiàn)代CPU可以有效地預(yù)取數(shù)據(jù)。然而，由于超級塊剪枝導(dǎo)致的不規(guī)則和非連續(xù)數(shù)據(jù)訪問，編譯器難以優(yōu)化塊級邊界計(jì)算。因此，SP需要顯式控制CPU緩存在計(jì)算塊級邊界時的重用模式。

SP采用了超級塊優(yōu)先的邊界和計(jì)算方式，即對每個未剪枝的超級塊，先對該超級塊內(nèi)的所有塊進(jìn)行完整評分，然后再處理下一個未剪枝的超級塊。這種方法允許在內(nèi)部循環(huán)中重用累積寄存器以獲得更好的L1緩存性能。實(shí)驗(yàn)表明，這種方式比傳統(tǒng)的項(xiàng)優(yōu)先方法最高可提速1.89倍。

實(shí)驗(yàn)評估與性能對比

研究團(tuán)隊(duì)在MS MARCO段落排名數(shù)據(jù)集上進(jìn)行了全面評估，該數(shù)據(jù)集包含880萬個英文段落。評估采用標(biāo)準(zhǔn)指標(biāo)：平均倒數(shù)排名（MRR@10）和位置1000（k=1000）或10（k=10）的召回率。所有實(shí)驗(yàn)在配備Intel i7-1260P、64GB RAM和AVX2指令的Linux系統(tǒng)上使用單線程運(yùn)行。

SP與三種最先進(jìn)的基于塊的檢索算法進(jìn)行了比較：BMP、Seismic和ASC。實(shí)驗(yàn)結(jié)果表明，在高相關(guān)性預(yù)算要求下，SP在SPLADE和E-SPLADE上的表現(xiàn)顯著優(yōu)于這些基線方法。

SPLADE模型上的性能比較

在SPLADE上的排名安全搜索中，SP比BMP在k=10時快32%，在k=1000時快25%。與ASC相比，SP在k=10和k=1000時都快約3.3倍。對于99%的召回預(yù)算，SP比BMP快至多2.9倍，比Seismic快3.3倍，比ASC快9.1倍。

上圖展示了SP和BMP在塊大小b從128減小到8時的總延遲（上圖）和成本細(xì)分（下圖）。當(dāng)b變小時，BMP能夠獲得更緊密的邊界和，但塊過濾開銷增加。SP在評估小塊的同時減少了塊和超級塊過濾的開銷。

超級塊剪枝的有效性

實(shí)驗(yàn)數(shù)據(jù)顯示，即使在安全搜索（μ=1）情況下，SP也能剪枝24%的超級塊（k=10）。隨著μ減小，超級塊級別的剪枝量顯著增加，而被剪枝的塊數(shù)量大致相同。這是因?yàn)閴K對其內(nèi)部文檔形成了緊密邊界；SP能夠避開不太可能包含相關(guān)文檔的塊組，從而減少計(jì)算塊邊界和的開銷。

在100%概率安全性（η=1）下，即使在μ=0.4（k=1000）時，對Dev集、DL 19和DL 20的相關(guān)性指標(biāo)影響也可忽略不計(jì)，盡管當(dāng)μ=0.4時召回率開始下降。相比之下，即使在BMP中使用低估計(jì)閾值也會導(dǎo)致相關(guān)性大幅下降。

E-SPLADE模型上的性能

在E-SPLADE上，SP在不同高相關(guān)性召回預(yù)算下的表現(xiàn)也優(yōu)于其他基線，比Seismic快至多16倍，比BMP快1.4倍。

超級塊剪枝的優(yōu)勢與局限

與現(xiàn)有方法相比，SP具有以下顯著優(yōu)勢：

1. 更高效的塊跳過：與BMP相比，SP利用其超級塊結(jié)構(gòu)快速跳過大量塊，同時提供額外的η保障以確保概率安全性。
2. 更好的緩存利用：與Anytime Ranking、ASC和Seismic相比，SP能夠處理更多的塊數(shù)量，并通過緩存優(yōu)化的超級塊剪枝克服額外開銷，自然導(dǎo)致更緊密的邊界估計(jì)。
3. 高相關(guān)性保證：在保持高相關(guān)性的同時顯著提升檢索速度，特別適合對檢索質(zhì)量要求較高的應(yīng)用場景。

然而，SP也存在一些局限性：

1. 額外空間成本：與BMP相比，SP需要額外空間來維護(hù)每個超級塊的最大和平均項(xiàng)權(quán)重。在MS MARCO評估中，當(dāng)c=64、b=8時，額外空間約為2GB；當(dāng)b=16時，額外空間約為1GB。
2. 靜態(tài)索引剪枝的缺失：與Seismic不同，SP沒有利用靜態(tài)索引剪枝，這可能在某些情況下限制其性能。

應(yīng)用場景與未來展望

SP技術(shù)特別適合需要高相關(guān)性的應(yīng)用場景。對于此類應(yīng)用，建議將η設(shè)置接近1.0，并將μ從0.4變化到1。檢索是大規(guī)模搜索系統(tǒng)和基于檢索增強(qiáng)的大語言模型（如RAG）的關(guān)鍵組件，在低成本CPU上實(shí)現(xiàn)高相關(guān)性的快速檢索可以產(chǎn)生積極影響。

未來研究方向包括：

1. 探索靜態(tài)索引剪枝、自定義摘要和文檔鄰近圖等技術(shù)與SP的結(jié)合
2. 研究SP與索引壓縮方案的結(jié)合
3. 開發(fā)針對輸入復(fù)雜性的動態(tài)縮放策略
4. 整合自適應(yīng)推理深度控制以在推理期間平衡效率和安全性能

結(jié)論

動態(tài)超級塊剪枝（SP）是一種創(chuàng)新的動態(tài)剪枝方案，除標(biāo)準(zhǔn)塊級別外，還在超級塊級別進(jìn)行剪枝，并設(shè)計(jì)為利用CPU緩存局部性。實(shí)驗(yàn)評估表明，在SPLADE上99%或更高的召回預(yù)算下，SP比Seismic快2.3倍至3.8倍，比ASC快3.2倍至9.4倍，比BMP快至多2.9倍。對于安全搜索，SP比BMP快至多1.3倍。

隨著信息檢索需求的不斷增長和大語言模型對高效檢索系統(tǒng)的依賴加深，SP技術(shù)有望在未來發(fā)揮更加重要的作用，特別是在需要在保持高相關(guān)性的同時提高檢索效率的場景中。

參考資料

論文:???https://arxiv.org/abs/2504.17045??

GitHub：???https://github.com/thefxperson/hierarchical_pruning??

本文轉(zhuǎn)載自???頓數(shù)AI????，作者：可可