適用於記憶體增強型人工智慧之高效能向量相似度比對技術

Abstract

隨著全球網路產生的資料指數上升，國際數據組織 (International Data Corporation, IDC) 指出，在2029年時，全球的年資料產生量將會達到527.5兆GB。同時，少量樣本學習 (Few-shot Learning, FSL) 的發展與生成式人工智慧 (Generative Artificial Intelligence, Generative AI) 及檢索增強生成 (Retrieval-Augmented Generation, RAG) 技術的興起，結合外部記憶體 (External Memory) 與向量相似度搜尋 (Vector Similarity Search, VSS) 能解決過去AI難以拓展至未學習之資料分布的問題，並減少大語言模型 (Large Language Model, LLM) 產生幻覺(Hallucination) 的可能性。因此，記憶體增強型人工智慧 (Memory-Augmented Artificial Intelligence) 與向量相似度比對已成為現代 AI 應用的核心架構。

現有的搜索系統面臨記憶體傳輸瓶頸，即使處理器的運算速度遠快於記憶體讀寫，資料的處理速度仍然會受到記憶體傳輸的頻寬所限制。傳統馮·紐曼架構 (von Neumann Architecture) 中，處理器與記憶體的分離導致了嚴重的資料傳輸瓶頸 (Memory Wall)，難以應對大量資料的檢索需求。基於記憶體內搜尋（In-Memory Search, IMS）之非馮紐曼架構(non-von Neumann Architecture) 逐漸興起，三元內容定址記憶體 (Ternary Content-Addressable Memory, TCAM) 將搜索比對單元嵌入記憶體單元中，以解決資料傳輸的瓶頸問題，並具備低功耗、低延遲以及高密度之優點，能有效提升搜索之能源效率，逐漸成為解決大規模之向量相似度搜索的關鍵技術。

在本論文中，我們的目標在於利用演算法與架構協同優化之概念，提升TCAM在向量相似度搜索中的能量效率與準確度。儘管TCAM具備高平行度的搜尋優勢，但現有的向量相似度搜索系統仍面臨三大挑戰：首先，精確比對型TCAM (Exact-Match TCAM, EX-TCAM) 需要多次迭代搜尋與極長的編碼長度，導致高延遲與面積消耗；其次，餘弦相似度 (Cosine Similarity) 與硬體可實現之漢明距離 (Hamming Distance) 或 L∞ 範數之間存在度量不一致性，造成搜索準確度下降；最後，最佳比對型TCAM (Best-Match TCAM, Best-TCAM) 需雖能達餘弦相似度搜索，但仍需使用極長之編碼，不利於邊緣裝置部署。

為了克服上述困難，本論文提出了帶狀向量相似度比對 (Banded VSS)，利用統計特徵限縮搜尋範圍以減少搜索迭代次數，並開發支援範圍對範圍 (Range-to-Range) 比對的編碼機制以縮短編碼長度;此外，本論文亦同時引入基於 L∞ 範數的訓練機制，提升向量搜索準確率，確保向量特徵與搜索行為於軟體與硬體間之一致性。此外，我們基於近似運算 (Approximate Computing) 的概念，提出了範圍保真度感知之範圍編碼 (Range Fidelity-aware Range Encoding)，利用搜尋過程中的容錯特性進行有損編碼優化 (Lossy Encoding Optimization)，在維持搜索準確率的前提下，大幅降低編碼長度與硬體成本。此外，本論文提出了分段餘弦相似度 (Segmented Cosine Similarity) 與其架構，透過對漢明距離的重新詮釋與推導，使其能有效支援高維度向量的角度比對。最終，本論文提出適用於記憶體內搜尋之向量相似度搜索架構，並在台積電 (TSMC) 28 奈米製程環境下整合記憶體內搜索模塊及數位模組，實現上述演算法於晶片實作。量測結果驗證此搜索晶片在少量樣本學習應用中，能達到極高的能源效率與準確度。

With the exponential growth of data, the international data corporation (IDC) projects that global annual data generation will reach 527.5 trillion GB by 2029. Simultaneously, the development of few-shot learning (FSL) and the rise of retrieval-augmented generation (RAG) have demonstrated that combining external memory with vector similarity search (VSS) can address the limitations of AI in handling unlearned data distributions, while reducing hallucinations in large language models (LLMs). Consequently, memory-augmented AI and VSS have become core structures for modern AI applications.

However, existing search systems face memory transmission bottlenecks. Even though processor speeds far exceed memory read/write speeds, data processing throughput remains limited by memory bandwidth. In traditional von Neumann architectures, the separation of processor and memory creates a severe “Memory Wall.” In-memory search (IMS) based on non-von Neumann architecture is emerging as a solution. Ternary content-addressable memory (TCAM) embeds comparison units directly within memory cells to resolve these bottlenecks. With advantages in energy consumption, latency, and density, TCAM enhances energy efficiency and becomes a key technology for large-scale VSS.

This dissertation aims to improve the energy efficiency and accuracy of TCAM-based VSS through algorithm-architecture co-optimization. Despite the advantages of high parallelism, existing VSS systems face three major challenges: First, Exact-Match TCAM (EX-TCAM) requires multiple iterative searches and extremely long encoding lengths, resulting in high latency and area overhead. Second, there is a metric mismatch between Cosine Similarity and hardware-realizable metrics such as Hamming Distance or the L∞ norm, causing a degradation in search accuracy. Finally, while Best-Match TCAM (Best-TCAM) can achieve cosine similarity search, it requires excessive encoding lengths that are unfavorable for deployment on edge devices.

This dissertation proposes banded VSS which utilizes statistical features to narrow the search scope, thereby reducing the number of search iterations, and develops a range encoding scheme supporting range-to-range matching to shorten codeword length. Simultaneously, we introduce an L∞ norm-based training mechanism to enhance search accuracy, ensuring consistency in search mechanisms across software and hardware. Furthermore, we propose range fidelity-aware range encoding, which utilizes the error tolerance inherent in the search process to perform lossy encoding optimization. This reduces codeword length while maintaining search accuracy. Additionally, we propose segmented cosine similarity and its corresponding framework through the reinterpretation of Hamming distance. Finally, we implement the aforementioned algorithms on a chip by integrating IMS modules and digital modules using TSMC 28nm technology. Measurement results verify that this chip achieves high energy efficiency and accuracy in FSL.