ListK : Semantic ORDER BY and LIMIT K with Listwise Prompting
Jason Shin, Jiwon Chang, Fatemeh Nargesian · 2026
Read ListK : Semantic ORDER BY and LIMIT K with Listwise Prompting by Jason Shin, Jiwon Chang, Fatemeh Nargesian (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-17223.txt.
Introduction
Shin, Chang, and Nargesian present ListK, a framework that speeds up semantic ORDER BY and LIMIT K queries. Such queries use language models to sort rows by meaning, and current methods are slow. ListK combines partial listwise rankings with several sorting schemes: tournaments, multi pivot quickselect and quicksort, and a Monte Carlo filter. A query optimizer picks among them based on the target recall. The authors report that ListK halves latency at nearly no cost to recall or ranking quality.
Catalog record
| CREATOR | Jason Shin, Jiwon Chang, Fatemeh Nargesian |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 72458 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.17223
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
ListK : Semantic ORDER BY and LIMIT K with Listwise Prompting Jason Shin, Jiwon Chang, Fatemeh Nargesian 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 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. Left box shows a listwise prompt that shows the documents to the LLM, and the LLM answers with a full ranking. Right box shows a diagram of data flow from document corpus to an optional filtered subset through the tournament filter. Then, the full corpus or a filtered subset flows through either tournament top-K to yield sorted top-K, or through listwise quickselect to yield an unordered top-K which is then sorted by listwise quicksort. Figure 1 . A visualization of our overall strategy. (Left) An example of how listwise prompting is used to extract rankings from an LLM. (Right) Four physical plans supported by ListK : LMPQSelect/Sort and LTTopK with optional LTFilter . Left box shows a listwise prompt that shows the documents to the LLM, and the LLM answers with a full ranking. Right box shows a diagram of data flow from document corpus to an optional filtered subset through the tournament filter. Then, the full corpus or a filtered subset flows through either tournament top-K to yield sorted top-K, or through listwise quickselect to yield an unordered top-K which is then sorted by listwise quicksort. Algorithm Purpose (Non-)Determinism Prompting # of LLM calls LTTopK select+sort deterministic listwise \displaystyle\frac{1}{L-1}\cdot(N-1)+(K-1)\cdot\log(N/L) (Section 4.1.1 ) LMPQSelect selection Las Vegas listwise \displaystyle\frac{(P+1)}{(L-P)(P-1+(K/N)^{P+1}+(1-K/N)^{P+1}}\cdot N+O(1) (Theorem 3 ) LMPQSort sorting Las Vegas listwise \displaystyle\frac{1}{(L-P)\cdot\log(P+1)}\cdot N\log(N/L)+O(N) (Theorem 5 ) LTFilter pre-filter Monte Carlo listwise N/L (Section 4.1.4 ) LOTUSTopK select+sort Las Vegas pairwise 2.5N+K\log K ( 20 ; 9 ; 10 ) Table 1 . Summary of algorithms that we study compared to prior art. 1. Introduction 1.1. Semantic ORDER BY and Top-K With the recent proliferation of large language models (LLMs), it is now possible to express query objectives using natural language. This allows us to perform data analytics on semi-structured or unstructured documents and multimodal data. Semantic Operators While there are many different ways of integrating LLMs into data analytics systems, one promising method is semantic operators (SemOps) ( 19 ) . Semantic operators parameterize various SQL clauses with natural language to improve expressivity. SemOps are a large improvement over User-defined Functions (UDFs). SemOps are high-level “transparent” logical operators, because the natural language clauses are embedded in the query and therefore visible to the DBMS. On the other hand, LLM UDFs are “opaque” and written in an imperative language, with calls to external models. As such, these UDFs admit a more limited scope of optimizations. Academic and industrial implementations of SemOps support a variety of logical and physical operators ( 20 ; 12 ; 16 ; 7 ; 3 ; 4 ) . In this paper, we focus on the semantic top-K operator. Semantic Top-K Operator Semantic top-K queries are critical in any application where there are more items than a human can process. It encompasses finding the top items ( K=1,2,\ldots ) as well as ORDER BY query for full sort. Henceforth, when we refer to top-K, it is a shorthand that refers to both scenarios. We give two examples below. SELECT * FROM science_papers ORDER BY "The paper is relevant to my project on the topic of ... extending prior works by ... using techniques like ...." LIMIT 20; SELECT \* FROM resumes ORDER BY "The candidate is the top selection with our open role ... which has the following job description: ...."; In both cases, the queries are ranking and returning unstructured documents by their relevance to complex user priorities that can only be accurately described using natural language. Hence, the in-database support of semantic top-K operators is the ideal tool for these tasks. While these queries can generally be applied to items of structured or unstructured data types, following our previous examples, we refer to database items as documents. 1.2. LLM Prompting Paradigms There are three major prompting paradigms for ranking documents using LLMs: pointwise, pairwise, and listwise ( 2 ) . Pointwise prompting In this case, an LLM is prompted to assign a ranking score to each document. While LLMs are capable of interpreting user intent for ranking, they are often unreliable at generating zero-short pointwise scores ( 30 ) . As a result, methods designed for pointwise UDF rankers ( 1 ) require extensive calibration of scores and are not suitable for semantic top-K queries. Pairwise and listwise prompting In listwise prompting and its special case of pairwise prompting for list size of two , an LLM is instructed to rank input documents based on their relevance to the user’s query. Figure 1 shows a prompt template and the corresponding output by the LLM. The state-of-the-art technique for the semantic top-K operator, LOTUS ( 20 ) , resorts to the pairwise prompting method, using general-purpose LLMs. Simply put, LOTUS embeds pairwise ranking prompts in a quicksort algorithm to get a sorted list of documents. This incurs a large number of LLM invocations for large datasets. On the other hand, listwise prompting is especially promising for its efficiency: it implicitly returns information about a log-linear number of pairwise comparisons. Therefore, the information content per token of listwise ranking is higher than that of pairwise ranking. Specialized listwise rankers General-purpose LLMs are poor at listwise ranking. We show this in our experiments (Section 5 ). They also exhibit a systematic positional bias, where the LLM’s output rank is highly correlated with the ordering of documents in the input ( 2 ) . This is because the standard pre- and post-training objectives are not well-suited for ranking tasks. A line of work in the IR community fine-tunes small language models as specialized rankers ( 21 ; 2 ; 22 ) , which can rank a small set of documents (e.g., 20) at a time with high accuracy. To decrease token usage and improve the efficiency of semantic top-K operators, we adopt these specialized listwise rankers. Doing so requires adapting existing sorting algorithms to the listwise ranking model. Challenges of adopting listwise rankers for semantic top-K While the aforementioned listwise rankers serve