Author
Jason Shin
Advisors and Committe Members
Fatemeh Nargesian, Hangfeng He, Michael Scott
Abstract
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 top-K remain lackluster. Semantic top-K operators have applications in search and information retrieval scenarios where the user’s intent is a ranking function expressed with a natural language query. Our ListK framework improves the latency of semantic top-K at no cost to accuracy. First, we adopt fine-tuned listwise ranker models as opposed to the pairwise prompting paradigm of prior art. Second, we design several novel algorithms that best aggregate listwise rankings. These include: 1) a deterministic listwise tournament algorithm (LTTopK), 2) Las Vegas and embarrassingly parallel listwise multi-pivot quickselect/sort algorithms (LMPQSelect, LMPQSort), 3) a basic Monte Carlo listwise tournament filter algorithm (LTFilter), and 4) a deterministic listwise filter algorithm based on the median of medians algorithm (MFilter). The full framework provides a query optimizer for combining the above physical top-K operators that minimizes the number of LLM calls utilized by each query. 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.
Poster
