提出高效确定性前缀检索方案，实测能效降低308倍。
Deterministic Retrieval at Scale: Optimal-Space LCP Indexing and 308x Energy Reduction on Modern GPUs
- 基于前缀树构建索引，空间复杂度仅O(N×L)
- 在2000万条数据上实现308倍能效提升
- 适合对结果确定性要求高的场景如金融、医疗
我们研究在长度为L的N个序列上进行确定性Top-k前缀检索（以最长公共前缀相似性为准）。证明了在单元探针模型下存在紧致的Ω(N)空间下界，并提出一种基于三叉树的索引结构，使用O(N×L)空间，查询时间O(L+k)。相比成对展开（Θ(N²)）在大规模下会因内存溢出而崩溃，本方法保持线性内存。随后引入热感知逻辑（TAL），将前缀结构转化为范围扫描。硬件测试显示，在2000万项范围扫描基准上，每查询能耗从4.46焦降至0.0145焦（降低308倍），95%延迟从37.5毫秒降至0.114毫秒（降低329倍），且长时间运行下仍维持近峰值利用率（~99%）。该方案提供了在近似方法不可接受的场景中可用的确定性检索基础。
原文摘要 · Abstract (English)
We study deterministic top-k retrieval under Longest Common Prefix (LCP) similarity for N sequences of length L. We prove a tight Omega(N) space lower bound (cell-probe model) and present a trie-based index using O(N*L) space with O(L+k) query time. We contrast this with pairwise materialization (Theta(N^2)), which hits a practical OOM wall at scale, while our indexed approach remains O(N) in memory. We then introduce Thermal-Aware Logic (TAL), which turns prefix structure into range-bounded scans. In hardware measurements, TAL reduces energy per query by 308x (0.0145 J vs 4.46 J) and cuts p95 latency by 329x (0.114 ms vs 37.5 ms) on a 20M-item range-scan benchmark, while sustaining near-peak utilization (~99%) under long runs. The result is a deterministic retrieval primitive with receipts in regimes where approximate methods are unacceptable.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。