用列表式提示优化语义排序与取前K，速度翻倍且不损失精度。
ListK: Semantic ORDER BY and LIMIT K with Listwise Prompting
- 基于列表级打分器设计多种快速排序算法组合。
- 相比之前方法，延迟减半，召回率和NDCG几乎不变。
- 适合需要高效处理非结构化数据的数据库应用者。
语义操作符通过抽象大语言模型调用，简化对半结构化、非结构化及多模态数据的分析。尽管已有诸多研究优化各类语义操作符，但现有语义 ORDER BY（全排序）与 LIMIT K（前K）方法仍表现不佳。本文提出 ListK 框架，在不牺牲准确性的前提下显著降低语义排序与取前K的延迟。受微调列表级排序器启发，我们研究了多种结合部分列表级打分的排序算法，包括：1）确定性列表级锦标赛（LTTopK），2）拉斯维加斯与无依赖并行的多轴心快速选择/排序（LMPQSelect, LMPQSort），3）基础蒙特卡洛列表级锦标赛过滤器（LTFilter）。其中，多轴心快速选择/排序首次在此被系统研究。整体框架提供基于目标召回率的查询优化器，以最小化延迟。我们给出理论分析用于参数调优，并为查询优化器提供成本估算。实验表明，ListK 在帕累托前沿上全面领先，相较先前方法延迟减半，召回率与 NDCG 几乎无损。
原文摘要 · Abstract (English)
Semantic operators abstract large language model (LLM) calls in SQL clauses. It is gaining traction as an easy method to analyze semi-structured, unstructured, and multimodal datasets. While a plethora of recent works optimize various semantic operators, existing methods for semantic ORDER BY (full sort) and LIMIT K (top-K) remain lackluster. Our ListK framework improves the latency of semantic ORDER BY ... LIMIT K at no cost to accuracy. Motivated by the recent advance in fine-tuned listwise rankers, we study several sorting algorithms that best combine partial listwise rankings. These include: 1) deterministic listwise tournament (LTTopK), 2) Las Vegas and embarrassingly parallel listwise multi-pivot quickselect/sort (LMPQSelect, LMPQSort), and 3) a basic Monte Carlo listwise tournament filter (LTFilter). Of these, listwise multi-pivot quickselect/sort are studied here for the first time. The full framework provides a query optimizer for combining the above physical operators based on the target recall to minimize latency. We provide theoretical analysis to easily tune parameters and provide cost estimates for query optimizers. ListK empirically dominates the Pareto frontier, halving latency at virtually no cost to recall and NDCG compared to prior art.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。