UQE: A Query Engine for Unstructured Databases
Authors: Hanjun Dai
Bethany Yixin Wang
Xingchen Wan
Bo Dai
Sherry Yang
Azade Nova
Pengcheng Yin
Phitchaya Mangpo Phothilimthana
Charles Sutton
Dale Schuurmans
Venue: NeurIPS 2024 poster (2024)
Keywords: unstructured data
sampling and optimization
database
language models
Primary area: machine_learning_for_other_sciences_and_fields
TL;DR: a query engine that leverages advances in sampling, online learning and foundation models for effective unstructured data analytics

Abstract: Analytics on structured data is a mature field with many successful methods.
However, most real world data exists in unstructured form, such as images and conversations.
We investigate the potential of Large Language Models (LLMs) to enable unstructured data analytics.
In particular, we propose a new Universal Query Engine (UQE) that directly interrogates and draws insights from unstructured data collections.
This engine accepts queries in a Universal Query Language (UQL), a dialect of SQL that provides full natural language flexibility in specifying conditions and operators.
The new engine leverages the ability of LLMs to conduct analysis of unstructured data, while also allowing us to exploit advances in sampling and optimization techniques to achieve efficient and accurate query execution.
In addition, we borrow techniques from classical compiler theory to better orchestrate the workflow between sampling methods and foundation model calls.
We demonstrate the efficiency of UQE on data analytics across different modalities, including images, dialogs and reviews, across a range of useful query types, including conditional aggregation, semantic retrieval and abstraction aggregation.

UQE: A Query Engine for Unstructured Databases
Hanjun Dai , Bethany Yixin Wang Xingchen Wan Bo Dai q, Sherry Yang', Azade Noval, Pengeheng Yin!, Phitchaya Mangpo Phothilimthanal;
Charles Sutton', Dale Schuurmans
Google DeepMind Google Cloud 8 University of Alberta
Georgia Institute of Technology
Abstract
Analyties structured data is mature field with many successful methods. However, most real world data exists in unstructured form, such as images and conversations. We investigate the potential of Large Language Models (LLMs) to enable unstructured data analytics. In particular, we propose new Universal Query Engine (UQE) that directly interrogates and draws insights from unstruc- tured data collections. This engine accepts queries in a Universal Query Language (UQL), dialect of SQL that provides full natural language ficxibility in specifying conditions and operators. The new engine leverages the ability of LLMs to con- duct analysis of unstructured data, while also allowing us exploit advances sampling and optimization techniques to achieve efficient and accurate query exe- cution. In addition, we borrow techniques from classical compiler theory better orchestrate the workflow between sampling methods and foundation model calls. We demonstrate the efficiency UQE on data analytics across different modali- ties, including images, dialogs and reviews, across range of useful query types, including conditional aggregation, semantic retrieval and abstraction aggregation.
Introduction
Data analysis
13 is essential for making well founded decisions and enabling businesses and society to function more effectively. Relational databases 112 32) and the Structured Query Language (SQL. 7 have delivered huge successes in structured data management and analysis. Typically, such data is collected and organized in pre-defined schema [14], where the data properties and relationships have been pre-specified, and downstream analysis is restricted this schema.
In most real-world applications, however, data exists in unstructured formats, such as images, documents and audio recordings. Without preprocessing such data into structured forms, traditional SQL engines can only support limited queries. Preprocessing, including document entity retreival 45 and form understanding 42). also require training on downstream tasks given predefined taxonomy. This naturally motivates the question we consider in this paper:
How
perform unstructured data analysis in flexible and efficient way?
In the literature, full-text search engines 200 support scalable regexp-matte matching search on unstructured data, but this becomes infeasible for more complex semantic reasoning queries. Retrieval-Augneee
Generation (RAG) 339 24 [8] allows question answering on a subset of related data, but is not directly applicable generic analytical tasks with aggregation and semantic queries that spans over an entire large database. Recent advances Large Language Models (LLMs) [4] 2 unlock the ability to perform flexible question answering, especially with recent long- cong-context models (33). However, setting aside the cost per query, data analytics can still challenging for LLMs without fine-tuning 25 or few-shot demonstrations
9 even given structured tables.
"work done while Phitchaya Mangpo Phothilimthana was at Google DeepMind. Correspondence hadai and wyixinggoogle. 38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

structured
unstructured columns
columns
rating
review_text
reason
sentiment
SELECT movid
Interstellar
Very ertartaning..
Funis woten.
positve
SELECT "the reason why"
FROM indb www.oovveeeeeeee reviews WHERE rating
FROM www.iooiievriieeeee
Clitter
ho papaccuufal sit...
Sed. negalive
WHERE "the review sentinent is negative"
Source Codle
tels, brach meddng......
posilive
concrete calumns
vittual columns
Figure 1: Illustration of unstructured data analysis defined in Section 2
Recently, a promising line of work considered marrying LLMs with programming frameworks [88. where logical or arithmetic operations are offloaded to program interpreters 017. A most relevant example for analytics and table understanding tasks is Cheng et al. [Α]. which augments classical SQL semantics with LLMs as user-defined functions (UDF). While promising, the execution of such SQL programs that embed LLM calls still requires sweeping over the entire database, which is too costly for large collections of unstructured content. To overcome this barrier, we leverage the synergy between LLMs and programmatic execution to define an Unstructured Query Language (UQL) that augments SQL for flexible semantic queries, with focus improving scalability and efficiency.
key observation is that the efficiency of classical SQL engines relies on (1) indexing structures that avoid the need to scan the entire database, and (2) a compilation system that determines the best execution order for operations. Based on these ideas, we propose the Unstructured Query Engine (UQE), which refines and extends this design principle to unstructured data analytics. To achieve similar effect to indexing, UQE casts the problem as learning to search or sample, seeking to avoid a full database scan with statistically sound methods. Additionally, compilation system is developed that determines the best execution order and operator combination for different clauses in a UQL query, with the goal of minimizing LLM calls while preserving query semantics.
As part of this project, we have created four new benchmark datasets, with both text and image modalities, along with three common analytic tasks. Compared to baseline methods, such as long- context LLMs and embedding based retrieval, UQE achieves significant improvements terms of the accuracy and cost reduction on these benchmarks.
2 Problem
Before defining the problem we are solving, we first establish the terminology and notation we will use throughout the paper. A concrete illustration of the following terms is given in Figure []
Table database: We define table T (Tr) as an unordered of [T| N rows, where each row T = [Tr,1, T..,..., Tr.M] is an array of M elements such that M is the total number of columns in the table. Each can consist of elements Ti, of heterogeneous types (e.g., datetime, float, enum) with different modalities (e.g., text, image), while elements in each column T.j must be of the same format and modality.
Structured data: A column T.j is structured w.r.t. a query if it can be accessed quantitatively, such as by algebraic operations over numeric data, comparison over string labels with predefined vocabulary (e.g., categorical labels), datetime functions, etc..
Unstructured data: A column T.j is unstructured if query cannot access it using standard quantitative access. Typically, such column does not belong to a predefined taxonomy. Examples include text (e.g., dialogs), images, videos, and other forms of data that usually require semantic understanding and preprocessing before performing any algebraic operations.
Concrete column: A column is concrete if already exists in the table.
Virtual column: A column is virtual if it does not already exist in the table, but query is able to operate on it. Conceptually, one needs to derive (partial rows of) these columns by processing the data from concrete columns. In our work, we bypass this step by creating such columns lazily and selectively, which is the key to achieving efficiency and performance gains.
SQL engines can perform analytic queries on databases by manipulating structured data in concrete columns. The focus of this paper is to propose a new query engine that can perform analytics on databases with both structured and unstructured data, with queries that operate over both concrete and virtual columns. Standard analytics tasks that we seek to enable over unstructured data are:

---

perform aggregation operations on sub-table filtered by condition. Semantic retrieval: collect relevant rows specified by semantic filters.
Conditional aggregation:
Abstraction and aggregation: group the rows based on abstractions and then performs aggregation.
Since optimizing queries structured data within concrete columns is well-studied, focus instead on techniques for handling queries on unstructured data over virtual columns. However, the UQE implementation also supports operations over structured data within concrete columns. In the following, unless stated otherwise, the term unstructured databases refer to databases containing both structured and unstructured data.
3 Unstructured query language
First, we need to formally define the query language, UQL, that talks to the unstructured databases. The idea of defining a natural query language for unstructured data is not completely new (e.g.. Cheng et al. [1]] even though UQL has richer semantics), nor is the specific syntax or design of UQL the main focus of this paper. However, need to define the scope of queries that the engine handle, and breakdown the semantic meaning of each clause.
3.1 UQL semanties
We assume a basic familiarity of SQL, upon which UQL is based. UQL can be considered to be a dialect of SQL that has augmented functionalities for handling unstructured and virtual column queries. The SQL clauses that we support in UQL., along with necessary modifications to support unstructured semantic queries, are described as follows.
SELECT is mapping function that maps the operand (usually a row or collection of rows in grouped query) new row of elements. In traditional SQL, this mapping is usually subset selection over concrete columns, or algebraic operators over those columns. UQL provides additional semantic mapping capability as:
SELECT "the attribute specified by natural language" AS attribute_ _ame
For example, one can write SELECT "the sentiment of the movie review" over an unstruc- tured movie review column, and retrieve "positive" or "negative" as structured output.
FROM specifies the source of the table. In SQL one can additionally specify table joins, but we limit our attention to sourcing from single table in this paper.
WHERE intrinsically specifies a binary classifier over rows, which is used to retrieve a subset of the database. In addition to comparator operators structured columns, also allow semantic specifications in the form of:
WHERE "the row satisfies some natural language specifications"
The predicates in WHERE organized in disjunctive normal form (DNF) with AND and OR syntax, so a user can arbitrarily express predicates over concrete and virtual columns.
GROUP BY partitions the table into groups, where within each group share the same attributes over the keys being grouped by. UQL allows partitioning over virtual columns via natural language:
GROUP BY "the abstraction criteria specified in natural language"
Similar WHERE, multiple criteria, with the resulting partition corresponding to grouping by tuple of these keys.
GROUP BY both concrete and virtual columns by concatenating
We also reuse other clauses from SQL including: ORDER BY, which simply inherits the SQL semanties to rank the resulting rows according specific concrete column. most analytics tasks, sorting is applied over structured columns with well defined ordering comparators. LIMIT is applicd during processing in the form of LIMIT num_rowa which limits the number of output rows.
We rely on the ability of an LLM to perform intra-row semantic understanding and analysis tasks. For example, we assume that LLMs are able correctly judge the specification in WHERE for single row. Similarly, LLMs should be able to extract the information specified by SELECT GROUP BY for single row. We build programmatic functionality on top of this fundamental ability of LLMSs to handle analytics for large databases.
Assumptions:
3

---

SELECT reason, (+) as count FROM movie_reviews
SELECT agent_name, "reason to cancel" FROM sellineecustmmer ceaatome_seevice__re service_ WHERE "the customer asked to cancel the flight"
WHERE movie_year 2020 GROUP BY "the reason why the review is positive" AS reason
ORDER BY ticket_price
LIMIT 100
Figure 2: Aggregation (left) v.s. Non-aggregation (right) queries written UQL.
3.2 UQL queries
A UQL query is a composition of clauses that can be categorized as an aggregation or a non- aggregation, illustrated Figure Aggregation queries perform a summary on groups of aggregated rows, such as COUNT the number of rows, or summarize a common attribute in a group of rows defined in GROUP BY above). Non-aggregation queries perform operations on individual rows, which usually means the rows can be processed in parallel. A UQL query will only belong to one of the above two types and we do consider nested queries for now. The query type determines how UQE will optimize and execute the query.
Unstructured Query Engine
One straightforward way run UQL to use an interpreter that executes queries imperatively. Cheng et al. [II] implements an engine in this form, which is able to handle tables of relatively small size. By analogy, this is similar to executing an SQL program using linear database scan. While is valid, the latency and cost are prohibitive and generally prevent scaling to real world scenarios.
There (at least) two key techniques in SQL databases for making query execution efficient:
Indexing, which organizes concrete columns via data structures for fast search with sublinear cost. Compilation, which considers alternative query plans and executes the most efficient one.
UQL queries over virtual columns pose challenges in both indexing and compilation. In this section, we present effective approaches to indexing (Section[4.1) and compilation (Section 4.2) for unstructured databases, along with the implementation details of low-level primitives (Section 4.2.2
4.1 Indexing
Executing traditional SQL queries over indexed columns can made efficient by avoiding an entire database scan to find the relevant rows to process. However, for UQL queries over virtual columns, it hard to predict or predefine an index that can enable efficient searching, since these columns are not concrete and defined via arbitrary natural language specifications.
Our first key contribution to introduce a proxy for "indexing" that allows one to leverage the intrinsic semantic content of a virtual column to efficiently execute queries without scanning the entire database. The main idea is to use statistically sound sampling techniques approximately retrieve relevant rows for processing. Based on the two types of queries defined in Section 3.2 we develop corresponding "indexing" counterparts.
4.1.1 Unbiased estimation for aggregation queries
We use a simple query to illustrate the idea of unbiased estimation to obtain query result without scanning over entire virtual column.
SELECT COUNT (+) count FROM movie_reviee WHERE "the review is positive"
Given row Te (a natural language movie review), it is relatively easy for LLM tell whether it satisfies the WHERE condition. If we use f (Ti, cond) + {0, to represent the LLM's classification of whether row To satisfies the conditions specified in cond, then the goal is to estimate the quantity
(1) There are many approaches that can be used to estimate the finite sum in the above equation, with different tradeoffs between bias and variance. One unbiased but potentially high variance estimator is to simply use Monte Carlo samples from a uniform distribution over 1 1...N. N. A typical technique for reducing variance is to importance sampling with proposal p, according to
ΣN f(T,, cond) = " (T., cond) = NEE [f cond)]
(ie(....N) [T, cond)) E. No. fT,, cond) Eixp fTr, cond) A theoretically optimal proposal p is given follows:
(2)

---

Algorithm 1 Stratified sampling for unbiased aggregation
Embed each row T; e, using multi-modal embedding over the unstructured columns of Ti
K i=1 into K disjoint groups {C C& S {1 [1....V .... where &t can be a predefined constant or automatically selected [48]. Each group has size [C&] and Σ |Cal = N.
Cluster the embeddings }
We use c: (1...N) N + {1 ... K} denote the cluster index of each row.
Perform stratified sampling over these groups and obtain samples S S [1...NN
Then we can obtain the following estimator for the expectation:
|Cato)
(I..I....)) [f cond)] = |S|
Σ
f(Ti, cond), where wA = Ejes (c(i) Ic(i) = c[i]]
(3)
Ejes wy 18
Algorithm 2
Online active learning for non aggregation retrieval
1. Embed each row T; as é., using multi-modal embedding over the unstructured columns of Tj
2. Maintain ğ(i) that approximates [(T,, cond). Initialize j(i) x (0, 1) uniformly.
Maintain the collection of sampled rows S at step / 0.
4. At step t, obtain batch St of samples where S, arg ma..s. Eies, 9(1) + c,, observe fTT, cond) for each sample S;; Update S t S U St-
5. Fit 9 with samples and corresponding observations from S. Go to step if [S] < B or return the positive samples found in S.
The optimal proposal distribution p that minimizes the variance of estimation in Eq is x f(T,, cond), which achieves zero variance.
Proposition 1
Prop I Jindicates that an ideal proposal should sample rows that have positive ff with equal probability. while sampling negative rows with zero probability. However, given that f is the response of an LLM it is expensive to execute over all rows, forcing us to consider efficient approximations.
Stratified sampling leverages the ability partition a population into homogeneous subpopulations. As shown in [ a good proposal p. should predict whether a row Ti satisfies the target property cond. To trade-off between cost and variance reduction, we propose Algorithm I normalize the importance weights wy to further reduce the estimation variance.
In Eq we
be used for other aggregation operations such SUM and AVERAGE, including GROUP BY, and allowing concrete columns as operands as well. However, some aggregations such MAX does not admit such estimator. UQE in this case can only provide estimates with greater effort. We discuss limitations in Section 7
Extension The above estimator
4.1.2 Online learning for non-aggregation queries
A non-aggregation query can be viewed as a search problem where we want to find a relevant subset of rows to process. As before, we begin with a concrete example: SELECT dialog ID FROM dialogs WHERE "the customer is unhappy with the agent's manner" In practice, we aim to identify as many rows as possible that satisfy the given condition while adhering to budget constraints (e.g.. the total number of tokens allowed to expense). This can be formulated as an online learning problem: given the token budget (or approximately, the number of LLM calls over individual rows, denoted as B), we seek to balance exploration (to better understand the semantic landscape of all rows) with exploitation (to maximize recall). Drawing inspiration from Bayesian optimization. which employs surrogate model learned on-the-fly to inform sequential we use cheap proxy 9 as a surrogate for fT,, cond). At each step f. we re-train with the observed data and select its maximizer to query in the next step. See Algorithm [ Here we use random noise 6, to allow some degree of exploration that decays with t. Compared to the typical max onner-product search method prevalent in RAG systems, we rely on the online learning to adjust the beliefs, instead of solely relying on predefined embedding similarities.
decision- -aaiiig [36] 19 22].
4.2 Compilation
Classically, the goal of a compiler is to translate a high level program to low-level machine code, maintaining exact execution results with improved execution speed. Such a lowering process is usually accompanied by optimizations egg., fusing, selecting the optimal instructions, and kernel optimizations. Our goal is similar: we would like compile high-level UQL into low-level machine code, with the distinction that the "machine" is an LLM, and the "low-level code" is the orchestration of prompt calls to the LLM. Given that the primary bottleneck is the LLM API calls, we attempt to maintain the execution semantics while minimizing the cost of LLM calls, as in Figure 3
5

---

high-level optinization (e.g] algebralc simllfictton. CSE, DCE)
lowering, low-llevel optimication (eig: nisrution selecton scheduingg register allocation)
High level
generation
High-euel Lakoram ond)
Low level
Assembly (tecuRric Perretto
Input Program
lowering, low-level opúmization
high-lauel optimization obt: min token, count
obj madsof
bias exploration explotation
code generation
MUCK (h te enter "retee lntoy
Lou-lovel
obj max
accurayy
HM
Highhineel IR janeptinneee
High-level mote
Sungeer
Prompt Orchestration (1N2)
Foundation Model
Irput: Query
INMGRE
LIVIT
AdG WHIFS
</>
XDG
SELECCT
Barps erfddmcc
piret
celinizaiio
Figure UQL compiler, in analogy to typical C++ program compiler.
4.2.1
Planning
Lowering a query into sequences of concrete execution units is a planning problem: The action space includes the order of clause execution, well ways to fuse clauses execute together. The objective is to minimize the (estimated) LLM cost. Figuring out the best decomposition and combination is usually an NP-hard problem. Fortunately, the number of clauses is very limited for single query, so we can enumerate possible combinations of ordering and fusions with little overhead.
The outcome of planning is specification of sequence of kernel executions. The input and output of each kernel can be one of the following:
Concrete table: standard table with only concrete columns. Stochastic table: the outcome unbiased sampling of a table. Importance weights will be attached to each row of the table, and the operation (e.g., SUM, AVG) on this table takes weights into account.
In the following 3 sections we will explain the building blocks of the compiler, including the kernel implementation, the cost estimation and final instantiation in detail.
4.2.2 Kernel implementation
Each kernel is an standalone execution unit that reads and produces a (stochastic) table.
SELECT on structured columns is straightforward. When operating on unstructured columns, prompt the LLM to extract semantic attributes from the input data. If several extractions share the same source column, we can also group these together into a single prompt to reduce cost.
WHERE takes a logical formula in disjunctive normal form, such that each conjunction can contain predicates over both unstructured and structured columns. One optimization make in this case is to perform evaluations over the structured columns first, then simplify (e.g., remove a conjunction any of the structured column evaluates to false) the logical formula. Any remaining predicates over unstructured columns are then executed on the table filtered by predicates over structured columns.
GROUP BY first gathers a representative subset of rows from the table, then calls an LLM to extract a taxonomy (i.e., the description of each cluster) for a cluster abstraction. Then the taxonomy used to classify rows sampled according to the methods defined in Section 4.1 Finally, each row is classified into one of the clusters with the corresponding cluster description in the taxonomy.
Other standard kernels like ORDER BY are implemented as-is since they are efficient to execute.
Kernel fusion: Certain clauses can be fused together to achieve significant efficiency gains.
WHERE + LIMIT can be terminated earlier for non-aggregation queries, once the number of rows specified by LIMIT are retrieved. This is particularly useful for rare event finding.
SELECT + GROUPBY when executed together, the semantic attribute extraction of SELECT and taxonomy classification in GROUPBY can be done in the same LLM call to save cost. GROUPBY WHERE can share the same sampling proposal for the aggregation queries.
When and how to fuse clauses relies on the planning technique introduced in Section 4.2.1

---

4.2.3 Cost estimation for each kernel
We only consider the cost of calling the I.M,, as this dominates the overall cost per query. Assuming the length of each row in the unstructured data is more or less uniform across rows, then the cost is proportional to the number of rows that fed to the LLM, which we use as the surrogate for estimation.
SELECT maps each row, hence the cost is [T] for the table T fed to SELECT.
GROUP BY consists of two steps, where taxonomy construction consumes a subset of the input table T. and classification runs [T] LLM calls in parallel.
WHERE depends on the proposal p. In practice we set a budget B and try to minimize the variance of unbiased estimator or maximize the recall in online learning, as explained in Section 4.1 Whenever clauses are fused together, each implementation responsible for providing reasonable cost estimate. For example when SELECT and GROUP BY are fused, the estimated cost is the same as GROUP alone, as the classification stage of GROUP BY shares the input tokens with SELECT.
4.2.4 Instantiation of kernels
The last step of compilation is to generate the machine specific code (e.g., x86 assembly code) from the intermediate representations (IR). For UQE, this is the process of generating the LLM-specific prompts. For example, when GPT is deployed as the "machine", a system prompt like "You are a helpful assistant" will be added to the queries. This step also sets the correct context (e.g., the correct struuctured/unstrucuurrd column to associate to, the description of the databases) for the LLM. When such information is not available, one can also leverage the LLM to provide good suggestion.
5 Related work
While the unstructured data analytics engine is relatively new, there are several related works in the context of unstructured data query and analysis. Approaches like pattern or regexp matching [20] is scalable but not feasible for complex semantic reasoning. RAG [24] [8] based approaches rely on the retrieval quality and is not directly suitable for aggregation queries over entire database.
LLMs 4 2 33
but are still not depict the ability of table analytics [15] to some extent 9 25
reliable for large unstructured database analytics yet.
Our work is closely related to neural symboilic approaches for unstructured data analytics. Early attempts in this line aim to design specialized neural architectures with inductive biases (e.g., attention) to capture a particular form of operation (e.g., filtering a list of objects based on a natural language predicate by their attention scores) 43 29 31. Those differentiable neural "operators" can then be chained together to model more compositional queries, and trained end-to-end using gradient descent. Another direction, in line with our work, is to augment symbolic programs with learnable operators parameterized by neural networks [0O]. Those programs are often modeled as discrete latent variables, which can be hard optimize. In contrast, UQE leverages predictions from LLMs as supervision to train an efficient proxy query model in an online fashion. Similar to UQF, some recent work [T 38 also adopts L.MS as fuzzy query operators. However, the generated programs treat LLMs as an UDF in a SQL program, which can be very expensive to execute on large databases. Our UQE implements similar but augmented semantics with the focus on the cost efficiency and scalability. Liu et al. (26) optimizes a similar query engine from the system perspective like cache optimization and deduplication, while our work mainly considers algorithmic improvements and is considered as an approximate query engine (28). These system and algorithm optimizations are actually orthogonal and can be beneficial to jointly consider both for future works.
also leverages models talking to databases. but mainly for semantic parsing purpose. While it also leverages the advances in LLMS [4 31 33), the execution is still on pure SQL and thus is not suitable for unstructured databases. There are also works on leveraging formal query languages better query LLMs [34] 6), with the focus on controllability of the LLM itself rather than performing analytics on external unstructured data.
In a distantly related topic, text2SQ [7 46 21 35
Experiments
We benchmark the accuracy and incurred cost of UQE multimodal unstructured data analytics tasks, with the goal to show and understand when and why UQE can improve accuracy while keeping the cost low. Since the unstructured database analytics is relatively new task, we construct and compare against several baseline approaches, on a set of tasks created from existing datasets.
7

---

Table 1: Conditional aggregation results on benchmark datasets. We report the relative error and the average cost per query. "gpt-4o is 50% cheaper than gpt-4-turbo so we double its budget of tokens; we use -laude-3-haike as the backend L.L..
Methods
Benchmarks
Conditions
lo-gpt-4-turbo
le-elaude-3-opus
UDF
UQE
IMDB
sent iment__ posittie
49.02% 4 21.23%
56.05% E 14.69%
13.67%
6.24%
5.75%
3.43%
Average cost per query
S0.37
$0.61
$0.01
$0.01
ABCD
account, account_accees acccess
69.25% 32.82%
27.28% + 17.05%
18.99%
9.83%
11.75% =: 9.78%
single, _tt_e_____________eeee_eeeeeee__ wwt.mmteerrrrrr query
78.42% + 9.36%
23.39% + 16.14%
26.95% = 26%
12.32%
+ 10.53%
Average cost per query
$0.38
$0.63
$0.01
$0.01
boox
47.58% + 15.24%
54,40% + 13.37%
10.15%
7.64%
4.98%
2.26
AirDialog
no_ flight
47.92% +: 21 62%
53.88% +: 15.77%
21.08% = 16.78%
8.78%
8.12%
no_ reservvattioo
50.54%
21.86%
57.49% 13.08%
21.19%
12.10%
7.23%
5.40%
Average cost per query
$0.21
$0.36
$0.01
$0.01
le-gpt-4o
le-gpt-4-tubo
UDt-
UQE-gpt-lo
Clevr
obj cou_tount < opheres 3
22.46%
19.35%
48.15% i: 41.2%%
31.04%
25.15%
9.55 8.35%
35.72%
14.95%
91.09%
20.08%
19.35% + 13.81%
15.14% +: 10.71 %
Average cost per query
$0.33*
$0.33
$0.20
$0.20
Table 2: Semantic retrieval results on several benchmark dataset. We report the Fl score of the retrieved rows and the average cost per query. We run 8 independent queries and report the average FI and its standard deviation. The result of MIPS is deterministic, so no standard deviation is reported.
Methods
Benchmarks
Conditions
le-gpt-4-turbo
lc-claude-3-ope
UDF
MIPS
UQE
IMDB
sentiment centiment_positiive Average cost per query
positiive
0.397 0.041
0.556
0,066
0.505
0.030
0.875
0.978
0.003
S0.38
$0.63
$0.02
$0
$0.02
ABCD
account account_access
0.045 = 0.033
0,080 = 0.023
0.076 = 0.017
0.961
0.940
0.019
single_iten iitittttmuurrryy
0.023 0.021
0.082 0.030
0.065
0.017
0.266
0.935
0.006
Average cust per query
0
$1.23
$0.03
$0
$0.03
book
0.327 1: 0.0667
0.585 :: 0.025
0,342 1: 0.031
0.930
0.979
0.010
AirDialog
no_ no_fhight ro_reeervation
0.066 0.037
0.228 : 0.068
0,144 0.034
0.867
0.928
0.018
0.156 0.075
0.297 0.043
0.145 0.042
0.965
0.969
0.004
cancel
0.006 = 0.009
0.013 = 0.008
0.013 = 0.009
0,066
0.741 + 0.205
Average cost per query
$0.43
0.77
$0.01
2 $0
$0.01
obj_ count # spheres 3
0.058 0.026
0.066 1: 0.023
0.093
0.031
0.023
0,850 +. 0.025
Clevr
0.037 = 0.027
0.099 = 0.023
0.089 + 0.017
0.145
0.633 +: 0.177
Average cost per query
S0.38
$0.21
$0.08
2 -00
$0.08
Baselines: We design the following baselines for comparison
lc-LLM denotes the long-contex: LLMs that can directly take subset of database and natural language question as input, and produce the desired analysis. We mainly evaluate against several model families, including GPT-4 (2) and Claude-3 (4. Of course, when evaluating the lc-LLM based approaches, we use the natural language instead of UQL as the prompt.
RAG-based can be applied to some non-aggregation queries, such as semantic retrieval. For the retrieval part we use max inner omer-producct search (MIPS) on top of the same embeddings that are used by UQE, for controlled experiment.
UDF simply treats the LLM calls as User-defined function of an SQL engine, with the same budget UQE by default. This approach will not have the advanced sampling / search algorithm as used in UQE, which also serves as an ablation for the effectiveness of our UQE.
Datasets: We evaluate different approaches on common analytical tasks in three widely used application domains. We use the datasets that were previously created for discriminative tasks, as these datasets contain both the unstructured columns and the structured ones (the labels in the corresponding dataset). We then hide these structured label columns and perform analytical tasks on the unstructured columns, where these hidden structured columns will be used to compute the ground-truth. The text based tasks include IMDB [27] movie reviews, customer service dialogs including Action-Based Conversations Dataset (ABCD (8) and AirDialog [4]], and image based Clevr 123 dataset. Please refer to Appendix C.I for more information.
Setup: We use 2 [ to embed the text-based unstructured columns, and Vertex [40] for multimodal embeddings. For budget constraint queries, we allow different approachces to access at most 128 rows in the database by default.
8

---

Table 3: Conditional abstraction and aggregation.
Methods
Benchmarks
Metrics
le-gpt-4-turbe
Ic-chaude---puu
UOL-chadde--taikk
END| coat
0.143 = 0.034
0.121 0.014
0.111 0.019
AirDialog
$0.21
$0.37
$0.04
account_ account_accesee access- END,
0.134 = 0.031
0.113 + 0.010
0.110 = 0.016
ABCD
si single wetiitte_quueee query ENDD
0.031 + 0.034
0.011 0.006
0.005 0.002
50.34
$ 0.56
$ 0.07
G0134
Figure 4: Variance of different sampling approaches for aggregation queries over text datasets.
6.1
Main results
We run queries on different datasets by instantiating the template shown in each of the sections below. The exact natural language and UQL queries can be found in Appendix D and more information including statistics of conditions we used for query and hyperparameters (for UQE we simply use the default hyperparameters for sampling and online learning) be found in Appendix C
6.1.1 Conditional aggregation
This task provides aggregated statistics over databases with specified conditions, with the template as:
SELECT CO)NT(+) FROM [tablel WHERE s"satisfies natural language specified condition "J We report the relative estimation error (i.e., |predict - www.tttuuuuee///eeeeeee (ount/ttttuuuee) and standard deviation in Table [ For lc-LLM baselines we estimate the count based on groups of unbiased data samples that fed into the prompt.
For text based aggregation we use Hlaude3-haiku as the backbone model, where UQE deploys 10x reduction in relative errors while reducing the cost by factor of 20x more. For the image dataset, since only limited set of L.LMs are capable right now, we use gpt-4o the backbone, and compare with lc-LLLM baselines. Thanks to the improved sampling method in UQE, the same gpt-4o consistently achieves improved performance out-of-the. thx-box. To verify this, we feed one image at time to got-4o and manually aggregate the count, the estimation error would be 17.10% + 13.95 and 19.35% + 13.8 % for the two queries of Clevr, which is twice higher than UQE in the worst case.
6.1.2 Semantic retrieval
This task filters rows in databases that satisfy specified conditions, with the template
SELECT FROM gtableB WHERE [ ("satisfies natural language specified condition D LIMIT While we limit the output size to be B 256 to keep the total cost within a reasonable budget. The challenging scenarios are when the number of rows that satisfy the predicate is few (i.e., "rare event finding"). Table shows similar sets of comparison, but the metric is Fl score which evaluates the quality of SELECT-ed rows. Overall UQE (with claude-3-haiku as backbone LLM) consistently achieves comparable or better performance than the baseline methods. MIPS which uses the same embedding of unstructured data UQE, has high variance across different types of queries. The queries such as "dialogs with account access issues" would be very suitable for MIPS as the embedding similarity able capture that well. For queries involving reasoning (e.g., find the images with less than 4 objects), it is pretty hard for pretrained embeddings to express this.
6.1.3 Abstraction and aggregation
This task abstracts the intrinsics of each row, and then performs semantics-based GROUP BY, grouping the common intrinsics across all rows. Finally, it provides aggregated statistics over each group:
SELECT derived_attribute, (*)NT(+) FROM Ktableff GROUP BY exxtraatt an abstract intrinsic attribute specified in natural language " AS derived_attribute LIMIT 10
The challenging problems this task are (i) building a taxonomy with good coverage, and (2) bias and variance reduction for groups with small population. The result of this query is a list of

---

1.00
1.00
1.00
1.00
(Masro overgee
(Mostog averagee
IM (Madnn bveragel
0.75
0.75
0.75
0.75
IWoaing Rocal
Rocall
9.50
0.30
0.50
3.50
0.25
0.00
0.00
9.00
128
Number Rorations
Number to
Number Raratland
Number Iterations
Figure 5: Recall (moving average with window size 16) against the number of iterations on (from left to right) AirDialog with condition (cancel, no so_flight) and Clevr with [obj count < #spheres 3). Colored lines and shades denote median and interquartile ranges across 8 indepen- dent queries and gray lines denote individual queries. The gray dashed lines denote the fraction of the positive population in the entire dataset.
[obj_count
Table 4: Quality at different compute budget B.
Table 5: Error of the aggregation operation on
Budget B
256
128
64
32
IMDB dataset under different budget B
Retrival
latency(s]
38.08
21.61
11.11
5.84
Budget B
512
256
128
32
score
0,978
0.828
latency(s)
5.83
4.28
2.93
UDF 8.11%
8.35%
13.67%
Aggregation
Ervor
5.75%
6.84%
8.29%
UQE
5.75%
6.84%
8.29%
tuples of derived attributes and their number of occurrences in the dataset. We use the earth mover's distance (EMD (30) as the evaluation metric to compare the extracted tuples and ground-trum tuples. The distance between pair of attributes is defined by one minus the cosine similarity of their text embeddings. We can see from Table@athat UQE consistently outperforms baselines while achieving much lower cost. We also show in Appendix with more qualitative results comparisons.
6.2 Ablation studies
We study the effectiveness of UQE for aggregation queries in Section 6.2.1 and non -angeegggttion queries in Section 6.2.2 and the quality/cost trade-off of UQE in Section 6.2.3 In appendix we provide more results on other modalities C.3 consistency C.4 and latency C.5
6.2.1 Variance of different sampling approaches for aggregation queries
To decouple the variance introduced by the algorithm and the bias introduced by the LLM based predictors, here we use the ground- truth label as the predictive result and focus the effectiveness of variance reduction. Figure 4 shows the box plot of different sampling methods. We can see using stratified sampling over the embeddings of unstructured content achieves significant lower variance compared to the uniform random sampling. Also both of these achieve similar expected values, which also justifies the correctness unbiasedness.
6.2.2 Efficiency of online learning for non non-aggregation queries
We show the effectiveness of the online learning in terms of the recall as a function of the iteration steps in Figure Compared to the dashed line in the figure which indicates the results of uniform random sampling, the online learning can achieve significant boost in terms of the recall. While for some queries the variance at early iterations can be high, these all converge well in the end.
6.2.3 Trade-off between cost/latency and accuracy
Generally the larger compute budget B the better quality UQE will get, and we verify this in Table 4 UQE can achieve pretty good quality even with very low budget, and notably compared to the bascline, it achieves similar quality with 16x reduction of the compute needed. We show more results in Section C.5 regarding the compute efficiency.
7 Conclusion
This paper proposed an unstructured query engine that leverages 1) the flexibility of LLMS for data understanding: 2) the advances sampling and online learning for efficient data scanning; 3) and the compiler that bridges these algorithmic workflows with LLMs. We demonstrated its efficiency and accuracy over three analytic tasks on four datasets with two different modalities. However the current work is still very limited in terms of 1) the semantics it lacks, including table join and other types of aggregations; 2) an automated selection of LLMs and sampling configurations; 3) and scaling to even larger databases. We hope to investigate these further in future works.
10

---

Acknowledgments and Disclosure of Funding
We thank Carsten Binnig, Howie Xu, Ras Bodik, Xinyi Chen, and the anonymous reviewers for providing helpful discussion and suggestions.
References
[1] Voyage 2. Voyage 2. httpss//hthbb..comm///gggpa///gp
[2] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, 1lge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.065: 087744 2023.
[3] Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Neural module networks. 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pages 39-48, 2015. URL
[4] Al Anthropic. The claude model family: Opus, sonnet, haiku. Claude-3 Model Card, 2024.
[5] Sören Becker, Johanna Vielhaben, Marcel Ackermann, Klaus-Robert Müller, Sebastian Lapuschkin, and Wojeiech Samek. Audiomnist: Exploring explainable artificial intel- ligence for audio analysis on a simple benchmark. Journal of the Franklin Institute, 2023. ISSN 0016-0032. doi: https://doi.org/ 10t.0..111....... ofto////.....ali....... wtw.annnii.223.111111 http://wwweeeoodcciccccoooeeeeee
URL
[6] Luca Beurer-Kellnet Marc Fischer, and Martin Vechev. Prompting is programming: A query language for large language models. Proceedings of the ACM on Programming Languages, (PL.DI)194661999) 2023.
[7] Don Chamberlin. A complete guide to DB2 universal database. Morgan Kaufmann, 1998.
[8] Derek Chen, Howard Chen, Yi Yang. Alex Lin, and Zhou Yu. Action-based conversations dataset: A corpus for building more in-depth task-oriented dialogue systems. arXiv preprint arXiv:2/04.0078,, 2021.
[9] Wenhu Chen. Large language models are few (1)-shot table reasoners. arXiv preprint arXiv:2210.06710, 2022.
[10] Xinyun Chen, Chen Liang, Adams Wei Yu, Denny Zhou, Dawn Xiaodong Song, and Quoc V.
Le. Neural symbolic reader: Scalable integration of distributed and symbolic representations for reading comprehension, In International Conference on Learning Representations, 2020.
URL https://api. http:://pp..ooaattttssosrrrrrr//
[11] Zhoujun Cheng, Tianbao Xie, Peng Shi, Chengzu Li, Rahul Nadkarni, Yushi Hu, Caiming Xiong, Dragomir Radev, Mari Ostendorf, Luke Zettlemoyer, et al. Binding language models in symbolic languages. arXiv preprint wrXiv:22200022877 2022.
[12] Edgar F Codd. The relational model for database management: version 2. Addison- Wesley Longman Publishing Co., Inc., 1990.
[13] Nada Elgendy and Ahmed Elragal. Big data analytics: literature review paper. In Advances in Data Mining, Applications and Theoretical Aspects: 14th Industrial Conference, ICDM 2014, St. Petersburg. Russia, July 16-20, 2014. Proceedings 14, pages 214-227. Springer, 2014.
[14] Ramez Elmasri and Shamkant B Navathe. Database systems: models, languages, design, and application programming. Pearson, 2013.
[15] Xi Fang, Weijie Xu, Fiona Anting Tan, Jiani Zhang, Ziging Hu, Yanjun Qi, Scott Nickleach, Diego Socolinsky, Srinivasan Sengamedu, and Christos Faloutsos, Large language models on tabular data-a a survey. arXiv preprint 24Xiv:2402. 174444 2024.
[16] Dawei Gao, Haibin Wang, Yaliang Li, Xiuyu Sun, Yichen Qian, Bolin Ding, and Jingren Zhou. Text-to-sql empowered by large language models: benchmark evaluation. ArXiv, abs/2308. 2023. URL http::/pw....mmaiiicccccccccpppp

---

[17] Luyu Gao, Aman Madaan, Shuyan Zhou, Uni Alon, Pengfei Liu, Yiming Yang. Jamie Callan, and Graham Neubig. Pal: Program-aided aided language models. In International Conference on Machine Learning, pages 10764-10799. PMIR, 2023.
[18] Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, and Haofen Wang. Retrieval-aus -aurmetel- generation for large language models: A survey, arXiv preprint arXiv:2312. 10997, 2023.
[19] Roman Garnett, Bayesian optimization. Cambridge University Press, 2023.
[20] Otis Gospodnetic, Erik Hatcher, and Michael McCandless. Lucene action. Simon and Schuster, 2010.
[21] Jiaqi Guo, Zecheng Zhan, Yan Gao, Yan Xiao, Jian-Guang Lou, Ting Liu, and D. Zhang. Towards complex text-to-sql in cross-domain database with intermediate representation. ArXiv, 2019. URL https://api.semmat http://ps..mmmiiiiiooooooooooooa
[22] Frank Hutter, Holger H Hoos, and Kevin Leyton- BrotonBBroww... Sequential model-based optimization for general algorithm configuration. In Learning and Intelligent Optimization: 5th International Conference, LION 5, Rome, Italy, January 17-21, 2011. Selected Papers 5, pages 507-523. Springer, 2011.
[23] Justin Johnson, Bharath Hariharan, Laurens Van Der Maaten, Li Fei-Fei, C Lawrence Zitnick, and Ross Girshick. Clevr: diagnostic dataset for compositional language and elementary visual reasoning. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 2901-2910, 2017.
[24] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, al. Retreneal-augmented generation for knowledge-intensive nlp tasks. Advances in Neural Information Processing Systems, 33:9459-9474, 2020.
[25] Peng Li, Yeye He, Dror Yashar, Weiwei Cui, Song Ge, Haidong Zhang, Danielle Rifinski Fainman, Dongmei Zhang, and Surajit Chaudhuri. Table-gpt: Table-tuned gpt for diverse table tasks. arXiv preprint arXiv:2310.0922 2023.
[26] Shu Liu, Asim Biswal, Audrey Cheng, Xiangxi Mo, Shiyi Cao, Joseph Gonzalez, Ion Stoica, and Matei Zaharia. Optimizing Ilm queries in relational workloads. arXiv preprint arXiv:2403.0588 058221, 2024.
[27] Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. Learning word vectors for sentiment analysis. Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Humun Language Technologies, pages 142- 150, Portland, Oregon, USA, June 2011. Association for Computational Linguistics. URL
http://www.ccdwbb.ogg//anoooooo 1-1015.
[28] Barzan Mozafari and Ning Niu. handbook for building an approximate query engine. IEEE Data Eng. Bull., 38(3):3 2015.
[29] Arvind Neelakantan, Quoe V. Le, and Ilya Sutskever. Neural programmer: Induc- ing latent programs with gradient descent. CoRR, abs/1511. 1,04344, 2015. http://p..oomaattttsssoooarrroop
URL
[30] Ofir Pele and Michael Werman. Fast and robust earth mover's distances. In 2009 IEEE 12th international conference on computer vision, pages 460-467. IEEE, 2009.
[31] Mohammad Reza Pourreza and Davood Rafeii. Din-sql: Decomposed in-context
learning of text-to-sql with self-correction. ArXiv, abs/2304.11015, 2023. URL
[32] Raghu Ramakrishnan and Johannes Gehrke. Database management systems. McGraw-Hill, Inc., 2002.
12

---

[43] Pengcheng Yin, Zhengdong Lu, Hang Li, and Ben Kao. quirer: Learning to query tables. ArXiv, abs/1512.00965. 2015. http:p//...aaaaiiaoooooooooooooo [33] Machel Reid, Nikolay Savinov, Denis Teplyashin, Dmitry Lepikhin, Timothy Lillicrap, Jean- baptiste Alayrac. Radu Soricut, Angeliki Lazaridou. Orhan Firat, Julian Schrittwieser, al. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context. arXiv preprint 200xv::2003.055300 2024.
[34] Mohammed Saeed, Nicola De Cao, and Paolo Papotti. Querying large language models with sql. arXiv preprini MrXiv:230400047) 2023.
[35] Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. Picard: Parsing incrementally for constrained regressive decoding from language models. ArXiv, (is/2109.05092 2021. URL https::/app..emanniischhooo htt.r//oooorooogoooorss02222390
[36] Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan Adams, and Nando De Freitas. Taking the human out of the loop: A review of bayesian optimization. Proceedings the the IEEE, 104
(1):148-175, 2015.
[37] Ruoxi Sun, Sercan O Arik, Hootan Nakhost, Hanjun Dai, Rajarishi Sinha, Pengcheng Yin, and Tomas Pfister. Sql-palm: Improved large language modeladaptation for text-to-sql. arXiv preprint arXiv:2306.0077 00739, 2023.
[38] Dídac Surís, Sachit Menon, and Carl Vondrick. Vipergpt: Visual inference via python execution for reasoning. Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 11888-11899, 2023.
[39] James Thorne, Majid Yazdani, Marzieh Saeidi, Fabrizio Silvestri, Sebastian Riedel, and Alon Halevy. Neural databases. arXiv preprint arXiv:2010.06993,, 2020.
[40]
Vertex.
Vertex API.
[41] Wei Wei, Quoe Le, Andrew Dai, and Jia Li. Airdialogue: An environment for goal-oriented dialogue research. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 3844-3854, 2018
[42] Yiheng Xu, Minghao Li, Lei Cui, Shaohan Huang, Furu Wei, and Ming Zhou. Layoutlm: Pre- training of text and layout for document image understanding. In Proceedings of the 26th ACM SIGKDD international conference knowledge discovery & data mining, pages 1200, 2020.
Neural en- URL
[44] Pengcheng Yin, Graham Neubig, Wen tau Yih, and Sebastian Riedel. Tabert: Pretraining for joint understanding of textual and tabular data. ArXiv, abs/2005.08314, 2020. URL
[45] Lijun Yu, Jin Miao, Xiaoyu Sun, Jiayi Chen, Alexander G Hauptmann, Hanjun Dai, and Wei Wei. Documentnet: Bridging the data gap in document pre-training. In Proceedings of the 2023 Conference on Empirical Methods in Naturl Language Processing: Industry Truck, pages 707-722, 2023.
[46] Tao Yu, Michihiro Yasunaga, Kai-Chou Yang, Rui Zhang, Dongxu Wang, Zi- fan Li, and Dragomir R. Radev. SyntaxsqInet: Syntax tree networks for com- plex and cross-domain text-to-sql task. ArXiv, abs/1810.05237, 2018. URL
[47] Tao Yu, Rui Zhang, Kai-Chou Yang. Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Z Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir R. Radev. Spider: A large-scale human-labeled dataset for complex and cross- domain semantic parsing and text-to-sql task. ArXiv, abs/1809.0888 2018. URL
[48] Chunhui Yuan and Haitao Yang. Research on k-value selection method of k-means clustering algorithm. J, 222):2226622)) 235., 2019.
13

---

A Proof
Proposition:
The optimal proposal distribution p that minimizes the variance of estimation in Eq
is P: x J(Ta, cond). The variance gets O with this proposal.
Let's simplify the notation a bit and use fx) for f(T, cond) and prove the variance reduction in general cases for binary function f. For the simplicity let's omit the constant [T] and focus on the estimation of the expectation term. If we come up with new proposal distribution p [0, 1]
where Exer p(x) 1, then we get a new estimator in the following form:
-[p()) g(x) p(z) p(z) (l(()) [(x)] Ex- (()) p(x)
[f
f(x)]
(4)
We hope this new estimator would have lower variance. Let's define u(x) g(a)) notation, and look its variance first:
for the ease of p(x) f(x
Varp(u(a)) = Epl [3)(a()
(5)
Since our estimator is unbiased, E [x(x]] [f [x)] and thus has nothing to do with p, let's focus on minimizing the first term. More specifically have the optimization
min Ex](2(x:]
s.t. p(x) > 0, Vz, Σ p(x) =1
(6)
.ET
Let:
(a(x))(x))²
L(,, (2.).22)
Σ Aup(a)) + A2 12222220 p(x) - 1)
p(z)
#ET
2ET
2ET
and we can find the saddle point of min, max (L(p, {hx) )2)) using K.K.T condition.
(a(z)
pla)² Ag + + 1= Va ET
>xp(z)= p(x) > (0), Vrr
Ao iz 1) = 0, >n p(a))
and we can get the optimal solution of
p(x) = (x))(())
(8)
and put it back into Eq(1) we can see the optimal variance would be
(g(x)f(x)) BB(u(s)] g(a)(())
Var,(u(x))
E.1(a)
[E,)(() Σ
which means one sample would be good enough! In our context, ((x) is usually just constant (e.g..
q(x) 1 for the [Case Count]), and f(x E {0, 1). In this case, a simplified optimal proposal would be:
p(x) x f(x) and the partition function is [z
(10)
14

---

or in another word, ideally we should have zero-chance to sample from regions where f(x) 0, and have equal chances sample where f(x)
B
UQL specifications
B.1 Tokenizer
We use the following pattern matching to tokenize the UQL programs/queries.
import ply. lex as lex
reserved
'select' 'SELECT',
'from" 'FROM',
'where: 'WHERE',
'as" : 'AS',
'limit' 'LIMIT',
'group'. 'GROUP:
'order: 'ORDER
by 'BY',
'to': 'TO',
'and': 'AND'.
'or': 'OR'. countt COUNT',
avv'' : 'AGG',
'uum : 'SUX' 'desc': DESC
tokens [ 'SEPARATOR',
'ALL'
ML_LITERAL"
MAR_NAME'.
TABLE_
COMPARE_OPERATOR
INTEGER',
FLOAT',
LEFT LEET_ PARENTHESIS
RIIHT PARENTHESIS',
] + list (reserved, values
values ())
SEPARATOR
t_ ALL r'
NL LITERAL
INTEGER r' d'
FLOAT = r' [ [0-9]++
LEFT PARENTHESIS r'
t S__RIGHT_PARENTEEE PARENTHESIS =
def t
I [a---zA- 1-----------------------------9- [a-zz-ZA-Z [a-z4---4- [a-zA-2_0-9]- type reserved. get (t. value. lover O,, WAR_ !) return
B.2 Grammar
Below we show the context free grammar of the UQL. Note that this represents subset of the "natural query" analogy SQL, and leave other clauses like table join into the future work.
UQL grammar
uql_query
palectcllaue from_clause claest from_clause OptionaaLclause_comm
15

---

optional_clause_cooo clause_
optional clause combo aational_claute
aptional_claur
optional_clause
limit_clause
tlauc
where_clause
group_by_clane _lauue
order_by_clause
seluct_clause SELECT select_ expreessxoossio
select_expression
scleet_expression SEPARATOR select_ sclect_literal
select_literas ALL variable
aariable_literal literal
nl nl_linn literal
aggregation
INTEGER
aggregation
agg_op LEFT PARENTHESIS NAME RIGHT PARENTHESIS agg_op LEFT PARENTHESIS ALL RIGHT_ PARENTHEESSS
ag PARENTHHHNSSS VAR_NAME RIGHT PARENTHESIS AS VAR_NAME agg_op op LEFT PARENTHESIS ALL RIGHT PARENTHESIS AS VAR NAME
agg
AVG COUNT
SUM
variable_ variable_literal literal
VAR NAME
VAR NAME AS NAME
nl_literal
NL LITERAL
LITERAL AS NAME
from_clause FROM NAME
where_clausc
WHERE where_expression
where pxsre__xpeessoo where settreeexpession AND predicate
where_est expressxpoession OR predicate predicate
group_by_clause GROUP BY group_by_expression
group_by_expressing
group_ sroup_by_expressie SEPARATOR group_by literal group_by_litera
group_ by literal : mllliteral
order_by_clane
ORDER BY order_by_cxpression
ORDER BY order_by DESC
order by expression
order _y__by_________ expression SEPARATOR order by literal order bilterra
literal
order_ literal VAR_NAM
LITERAL
I INTEGER
predicate
NI.LITERAT.
VAR NAME COMPARELOPERATOOR OPERATOR LITERAE
VAR NAME COMPARE OPERATOR INTEGER
16

---

Dataset
Conditions
percentage of occurrence the data
book cancel
51.40%
1.46%
Airdialog
no_flight no mo_reservation
23.08% %
23.89%
single item query
10.41% %
ABCD
account access
10.44%
IMDB
positive_reviee
50%
obj _bu_t <
12.65%
Clevr
# spheres >
17.53%
Table Dataset statistics
NAME COMPARE_OPERATOR FLOAT
limit_clause LIMIT INTEGER
to to_clause TO VAR NAME
C Experiments
C.1 Datasets
We evaluate different approaches common analytical tasks in three widely used application domains. We use the datasets that were previously created for discriminative tasks, as these datasets contain both the unstructured columns and the structured ones (the labels in the corresponding dataset).. We then hiden these structured label columns and perform analytical tasks on the unstructured ones, where these hidden structured columns will be used to compute the groundtruth.
User review mining. We use IMDB [27] for semantic analysis of user sentiment. The entire dataset contains 50K highly polar movie reviews with positive and negative sentiment labels. Goal-oriented (customer service) dialogue systems. We use two datasets for this category, including I) Action-Based Conversations Dataset (ABCD [8) for intent identification, which has 10,042 dialogs with 10 distinct user intents requiring unique sequences of actions constrained by policies to achieve task success; and 2) AirDialog [1] for conversation outcome understanding. It contains 402,037 goal-oriented conversation on flight booking with 5 possible ground-tre -tund states. Image understanding. We Clevr (33 dataset for multimodal data understanding and retrieving. Specifically we use the val split of the dataset, which contains 15,000 images of objects containing different number of cylinders, cubes and spheres with different sizes/colors. We down-sample the image to size no more than 128 x 128, and only feed the images to the LLMs while holding out scene metadata for evaluation only.
for Also see Table for the detailed statistics of different query conditions. Rare events like cancel in AirDialog is typically challenging find and aggregate on.
C.2 Parameter and experiment setup
For the embeddings, dimensionality of 512. We preprocess the embeddings for all the datasets and keep them static during the queries.
the v for text and for images, Google Vertex API with
For the aggregation queries, we use faiss to cluster the embeddings into 10 groups, and perform stratified sampling top.
For the ouline learning setting for non nog-gggregation queries, in our experiment we simply set e,, be O. We start training the function g when we collect at least one possible and one negative example labeled by the L.M. Then after every minibatch of samples collected, we train g via linear logistic regression and simply leverage sklearn for that.
Other parameters that might matter include: the sampling budget B for aggregation queries 128 and for non-aggregation queries it is 256. For group-by queries the UQE needs step in building the taxonomy, where the budget for that 16.
17

---

Table 7: Retrieval Fl score on AudioMnist dataset.
Query
UDF UDD-gemmni
MIPS
UQE-
"Three"
0.109 1 0.022
0,445
0.839 - 0.135
"A number whose square equals to itself"
0.259 +: 0.068
0.039
0.922 + 0.024
"The minimum prime number"
0.107 + 0.044
0
0.917 = 0.025
Table 8: Performance of UQE with different LLM backends.
Task
UDF
UQE-haiku (in the main paper)
UQE- KQE-gpt4o-mini-0718
Retrieval
0.505 + 0.030
0.978 0.003
0.956 + 0.010
Aggregation
13.67% +: 6.24%
5.75% 3.43%
6.33% + 4.71%
We set these parameters based on educated guess and keep them as default across all the queries over all the datasets.
C.3 Audio modality
We use the audio MNIST [5] data for this experiment. This dataset contains 30k wav files from 60 speakers pronouncing digits 0-9. We perform the audio semantic retrieval experiments. The query is first converted to audio space using TTS and the corresponding audio embedding is used for MIPS search. We use Gemini Pro 1.5 as the backend model, as supports the audio inputs nicely. As is shown in Table 7 the proposed UQE consistently does better than alternatives, and it also allows complex queries that require reasoning, while embedding based MIPS is limited to certain types of queries.
C.4 Consistency of the execution results
While UQE is able to leverage the foundation models analyze the unstructured databases directly, the execution result is not deterministic due to the nature of the stochasticity of the algorithm and the LLMs themselves. In our paper we aim reducing the variance so as improve the consistency. However when the backend LLM gets updated, it might also cause the potential inconsistency. Below we analyze the effect of different LLM backends.
Table (ssoww the effect on the IMDB dataset, where we see little variation. Actually the difference caused by the model switching is much lower than using worse query engine. Of course, this behavior shift would be task related, but with the advances of LLMs we believe this variation would converge and be more stable to different prompts in the future.
C.5 Latency
We report the runtime of UQE with claude-3-haiku as backbone, and 1c-gpt-4-turbo as the baseline method in Table 9
We can see UQE achieves low latency in aggregation operations, but higher latency in retrieval. This is due the online update and re-evaluation of the function described in Section 4.1.2 The experiments were run on MacBook Pro CPU, so we expect this bottleneck would be alleviated with better engineered system, which we will focus in our future works.
C.6 Group By qualitative results
For single_itens itt_ttttt_uuuaeee query in ABCD, the items mentioned in the dialogs found by UQE is:
[[ boots '338']
L'jacket '282']
['jeans' '268']
['shirt 11
For account_access ABCD, the issues mentioned in the dialogs found by UQE is:
[[ Forgot Password' '457'] '] [' Forgot Username '406' ']
[' L'os phone for wwo-factor authentication' '362 ']1
Which is very close to the ground truth frecover_useranng 2fa, recover_password)
For airdialog, the outcomes found by UQE is
18

---

Table Runtime (in seconds) comparison for different types of queries over different benchmarks.
Conditional aggregation
Semantic Retrieval
Methods
Clevr
ABCD
IMDB
Airdialog
Clevr
ABCD
IMDB
Airdialog
UQE-claude-3haaiku
3.13
3.34
5.83
3.85
46.00
41.20
38.08
67.14
lo-gpt-4-turbo
28.06
4.72
4.37
3.23
63.38
10.10
20.61
23.06
Flight Ticket Booked" '199383']
['No Flights Available '100884']
(No Reservation Found" '80775'1
['Flight Reservation Cancelled '51937']]
Where the ground truth has one more additional outcome (cancel). But since the percentage of cancellation is very small, it is expected that this might be missing from the group by abstraction when number of occurs very limited.
D Prompts
D.1 Prompts for lc-LLMs
D.1.1 Task: Conditional aggregation
IMDB dataset
System prompt
Read the following movie reviews, and categorize them into either positive or negative class, depending on the sentiment of the review. If the movie has a mixed sentiment, try your best to classify into positive or negative class based the overall sentiment. In the end, please just output single number, which is [the total number of positive reviews]
User prompt
Below are the reviews:
[Review 0]: Some TV programs continue into embarrassment (my beloved 'X-
+ Files' comes mind.)...
[Review 1]: The tale of the titular Adam (Mark 0' Halloran) and Paul (Tom Murphy),
ABCD dataset
System prompt
The following dialogs between a customer service agent and a customer.
Dialogs start by headers such **Dialog 1**, **Dialog 2**, and so Your task is to classify whether the dialog content is about the theme "account access issue". Then count how many dialogs theme. In the end, output the count as a single number. Here is more detailed explanation about Theme "<THEME>", Be sure this information when you classify.
talking about this
Theme "<THEME>" dialogs content is about THEME_ EXPLANATION. Please perform thorough analysis for each of the dialog. In the end, please **only** output a single number, which is [the total number of dialogs] that talks about the theme "account access issue".
<THEME> account access issue
<THEME> requesting detailed specifications of a certain item sold on the
website
<THEME <THEME_EXPLANCE
EXPLANATION> the customer could not access the account and was locked out, such as couldnt recall their username, couldn't perform two-factor authentication, or forgot their password and couldn't access their account
19

---

<THEME SHEEMEEEPPANNTIONE = the customer needed help with the detailed specifications certain item sold on the website, such as inquiries about detailed information of a specific retail item about materials, whether shrinks, stock availability, etc., promotions, order status, shipping status, questions about how to use the website to purchase an item, or difficulties on using the website to add to cart purchase an item, or inquiries about subscription
NOT inquiries about
User prompt
Below are the dialogs:
**Dialog 0**:
[agent]: Hello, how can help you today
[customer]: Hello my name is Alessandro Phoenix and I need make the shipping cost is included on my order
AirDialog dataset
System prompt
The following
dialogs between airline ticketing agent and customer.
Dialogs start by headers such as **Dialog 1**, **Dialog 2**, and so on.
The outcome of the dialog will be of the following 5 categories:
[book]: the agent has booked a flight for the customer (not including the flight change);
[cancel]: the agent canceled the existing valid reservation for the customer;
[no_reservation]: the customer wants to change or cancel the flight 1037 but there is no valid reservation under this customer; io_ffight]]: the customer aims to book a flight from departure to destination but finds no flights between departure and destination; Your task is to count how many dialogs have outcome <OUTCOME>. Please **nnly** output a single number, which is [the total number of dialogs] that satisfied the above requirements.
<OUTCOME> [book]
<OUTCOME> = [cancel]
<OUTCOME> [no_reservation]
<OUTCOME> = [no_flight]
User prompt
Below are the dialogs:
**Dialog 0**:
customer: Hello.
agent: Hello, how can help you today?
customer: Can you please find a flight from DFW to SEA?
**Dialog 1**;
customer: Hi, I am Melissa Thompson.
agent: Hello, how may support you today? customer: I want to celebrate Thanks giving day 11/23 with my friends at New York. Can you book ticket for me?
Clevr dataset
Task: Conditional aggregation
System prompt
Please read the following images, count how many them show that <CONDITION>.
20

---

<CONDITION> there are less than 4 objects in the image
<CONDITION> there are more than spheres the image
User prompt
image\_00 <base644
image\__L <base64\eencdde\__inne
Please output a single number, which is the total number of images that satisfy the condition.
D.1.2 Task: Semantic retrieval
IMDB dataset
System prompt
Read the following movie reviews, and list the indices of reviews with positive sentiment. If the movie has mixed sentiment, try your best to classify into positive negative class based the overall sentiment In the end, please only output a list of indices in the format of [review_3, revieu_7, ...]
User prompt
Below are the reviews:
[Review 0]: Some TV programs continue into embarrassment (my beloved
+ Files' comes to mind.)...
[Review 1] The tale titular Adam (Mark 0' Halloran) and Paul (Tom
4 Murphy),
ABCD dataset
System prompt
The following are dialogs between customer service agent and customer. Dialogs start by headers such as **dialog_1** **dialog_2** and so on. Your task is to find out the dialogs where <CONDITION>. Please only output format of [dialog_3, dialog_7, ...]
list of indices
<CONDITION> = the customer could not access the account and was locked out, such as couldnt recall their username, couldn't perform two-factor authentication, or forgot their password and couldn't access their account <CONDITION> the customer needed help with the detailed specifications of certain item sold on the website, such as inquiries about detailed information specific retail item about materials, whether shrinks, stock availability, etc., but NOT inquiries about promotions, order status, shipping status, questions about how use the website to purchase an item, or difficulties on using the website to add to cart or purchase an item, or inquiries about subscription
User prompt
Below the dialogs:
**dialog_0*** 0+*
[agent]: Hello! Welcome AcmeBrands, how cani help you? [customer]: Hi. I am very frustrated because I am trying to use your website and it is running slowly!
ddialog_1*x: 1**;
[customer]: hi there
[agent]: : Hi! What can help you with today?
[customer]: wanted to know if you'd d be able to tell me the arm length a shirt i'm thinking of buying?
21

---

AirDialog dataset
System prompt The following dialogs between airline ticketing agent and a customer. Dialogs start with headers such as **dialog_1** 1** **dialog_2** and so Your task is find out the dialogs where CONDITION. Please only output list of indices in the format of [dialog_3, dialog_7, ....
<CONDITION> = the agent has booked flight for the customer (not including the flight change)
<CONDITION> the agent canceled the existing valid reservation for the customer
<CONDITION> = the customer aims to book flight from departure to destination but finds no flights between departure and destination <CONDITION> the customer wants change cancel the flight but there is no valid reservation under this customer
User prompt
Below are the dialogs:
**Dialog 0**:
customer: Hello.
agent: Hello, how help you today?
customer: Can you please find a flight from DFW to SEA?
**Dialog 1**:
customer: Hi, I am Melissa Thompson.
agent: Hello, how may support you today? customer: I want celebrate Thanks giving day 11/23 with my friends at New York. Can you book a ticket for me?
Clevr dataset
System prompt
Please read and parse the following images. Images start with labels such as #*image_0** **image_1** and so on.
Your task is to find out the images where <CONDITION>. Please only output list of indices in the format of [image_3, image_7, ...]
<CONDITION> = there less than objects in the image <CONDITION> there are more than spheres in the image
User prompt
image_0: (base64_encoded_imaee image_1: -base64_encoded image>
Given above, the relevant images are:
D.1.3 Task: Abstraction and aggregation
ABCD dataset
System prompt
The following are dialogs between customer service agent and customer. Dialogs start with headers such as +*dialog_1+s, **dialog_2*x; and so on. Your task is to analyze all the dialogs, and summarize
ATTSTTRACTAATRRIBTEEE> into groups. Please output the table of your analysis, in the format of pairs of number_of _f_alogg belong to that). Specifically in the format as: group 1,number_on of _dialoo group 2,number_on of dialogs
22

---

<ABSTRACT_ATIRIBUNT
the type of account access issue CABSTRACT_ATTRIIUTT the single item involved in the dialog
User prompt
Below are the dialogs:
**dialog_0**;
[agent]: good afternoon, how can I help you?
[customer]: hey think mixed up or forgot which username I'm in with you guys
**diaoo- 1**:
[agent]: Hi there, thanks for contacting Acme! How can I help you?
AirDialog dataset
System prompt
The following are dialogs between airline ticketing agent and customer.
Dialogs start with headers such as **dialog_1**, #rdialog2***, and so on. Your task is to analyze all the dialogs, and summarize MABSTRACT_AATTRBUUU
into groups. Please output the table of your amalysis, in the format of pairs of MAASTTRACTATTRRBUTE>>>>>> number_on number_of_diee _i__ologs belong to that). Specifically in the format as: group 1, n,number__ of dialogs group 2, 2,number_on of of_dialog
<ABSTRACT_ATTRIBUN
outcome of the dialog
User prompt
Below are the dialogs:
**dialog_0**
customer: Hi.
agent: Hello. How may help you?
customer: I need to book flight ticket from DEN EWR enjoy music 4 festivals.
d=dialog_
customer:
agent: Hello, how may help you?
D.2
Prompts for UQF-orchettrated LLMss
D.2.1
Task: Conditional aggregation, Semantic retrieval
IMDB dataset
System prompt
Please analyze the following movie review, only reply <True> if <WHERE_CLAUS <False> otherwise.
WHERE_CLAUSE: the review sentiment is overall positive
User prompt
[Mviee review]: May I please have my $13.00 00 back? I would have rather watched "Hydro- Electric Power Comes North America"...
ABCD dataset
System prompt
23

---

Read the following customer support dialog between an agent and customer, and only reply <True> if CHAUSE,, or <False> otherwise.
<WHERE_CLAUSE> CLAUSE> the customer could not access the account and was locked out, such as couldnt recall their username, couldn't perform two-factor authentication, or forgot their password and couldn't access their account <WHERE_ WHERE_CLAUSE>> the customer needed help with the detailed specifications of certain item sold on the website, such as inquiries about detailed information specific retail item about materials, whether shrinks, stock availability, etc., but NOT inquiries about promotions, order status, shipping status, questions about how use the website to purchase an item, or difficulties on using the website to add to cart or purchase an item, or inquiries about subscription
<WHERE_
User prompt
[Dialog]: [agent]: Hi! Thank you for contacting today. How help you?
[customer]: I'm pretty upset that jacket that I ordered is saying that it is out of stock. Do you know when it will be back in stock? [agent]: I
sorry that happened to you [agent]: : Yes, let me look in to that for you [action] Searching the FAQ pages
AirDialog dataset
System prompt
Read the following airline ticketing dialog between the customer and the agent, and only reply <True> if WWHERE_CLAUSE <False> otherwise.
CLAUSE the agent has booked flight for the customer (not including the flight change) WHERE_CLAUSED the agent canceled existing valid reservation for the customer
WHHERE_CLAUSE> the customer aims to book a flight from departure to destination but finds flights between departure and destination WHHER__LAASSE the customer wants to change or cancel the flight but there is no valid reservation under this customer
User prompt
[Dialog]: customer: Hello.
agent: Hello, how can I help you?
customer: Please book a flight ticket from CLT to DEN.
agent: Sure, let know your travelling dates.
Clevr dataset
System prompt
Read the following image, and only reply <True> if WHHERE_CLAUSE, or <False> otherwise.
<WHERE CLAUSE> there are less objects the image
<WHERE_CLAUSE,
= there are more than 3 spheres in the image
User prompt
Image: @base64_encoded_iing immge>>
D.2.2 Task: Abstraction and aggregation
ABCD dataset
1. Building taxonomy
24

---

System prompt
The following are dialogs between customer service agent and a customer. Dialogs start with headers such as **dialog_1**, 1**
**dialog_2**, and Your task is to analyze all the dialogs, and summarize
CEBSTRRAC_AATRIBBTEER into groups. Please output the table of your analysis, in the format of pairs of ("<ABSTRACT, (""ASTTACC_ATTRRUUTE"""" number_of_dialon belong to that). Specifically the format as: group 1, 1,number_oo of _ialoos group 2, number of _f_alllog
ABBSTRACT_ATTRIBUU = the type of account access issue <ABSTRACT_ATTRRBUTE the single item involved in the dialog
User prompt
Below are the dialogs:
*#dialog_0**:
[agent]: good afternoon, how can I help you?
[customer] hey think i mixed up forgot which username I'm in 9 with you guys as
#kdialog_1e _
[agent]: Hi there, thanks for contacting Acme! How can I help you 9?
2. Group-wise conditional aggregation
System prompt
Read the given airline ticketing dialog between an agent and a
+ customer, and classify issue, into one or several
categories below. Here are the description of the 2
O categories:
[0] : Forgot Username
[1] Forgot PasswordOnly reply the index of the category,
G separated by "," Here is the example format:
[0, 3]
User prompt
Here is the customer support dialog:
[agent]: Hello, how can help you today [customer]: Hi. I seem to have forgotten my username [agent]: Okay lets get that for you, could get your Full Name Zip Code Email Adress and Phone Number please [customer] Sanya Afzal
AirDialog dataset
1. Building taxonomy
System prompt
The following are dialogs between airline ticketing agent and a customer. Dialogs start with headers such as #*dialog_1**, **dialog_2** and so on.
Your task is to analyze all the dialogs, and summarize "<ABSTRACT_AA ATTRIBUTEE into groups. Please output the table of your analysis, in the format of pairs of ("4ASTRACTATTRIIIEEE"" number_of _f_iloo belong to that). Specifically the format as: group 1 coumber_of_diale0
25

---

group
of cimmber_ofddialooo
ABSTRACT_ATTRIBUTE the outcome of the dialog
User prompt
Below the dialogs:
**dialog_O0 0+*:
customer: Hi.
agent: Hello. How may I help you?
customer: I need book flight ticket from DEN EWR to enjoy - music festivals.
##dialog_1** customer: Hi.
agent: Hello, how may I help you?
2. Group-wise conditional aggregation System prompt
Read the given airline ticketing dialog between the customer and the agent, and classify outcome, into one or several
4 categories below. Here are the description of the 2 categories:
[0] Reservation cancelled
[1] : Ticket bookedOnly reply the index category, separated
+ by "." Here is the example format:
[0, 3]
User prompt
Here is the airline ticketing dialog: customer: Hello
agent: Hello, how may I help you?
customer: Can you help to book flight ticket from SEA AUS
4
agent: Sure, S dates?
glad to help you. May I know your travelling
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provided thorough experiments and explanations of the algorithms jusify the claim.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
We discussed that in the conclusion section and we pointed out three major limitations.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
27

---

Answer:
[Yes]
Justification:
We have the proof for the optimal variance reduction proposal in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
We use public LLMs on public benchmarks, and the prompts are all included in the appendix. For our work we have provided enough details for reimplementation, and will work open sourcing as well.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
28

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: The data and prompts are all public and we have provided the information. We are working on open sourcing the code after going through the internal approval process.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please
the NeurIPS code and data submission guidelines wwwpu/cciccuuieeeeoooeeebbbeeeee
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https://nips.co htttps://niss.cc/puull///////
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We have provided the information in the appendix and main paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We provided the variance of the results almost all tables when applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
29

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We mainly use public API.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't It make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We have checked.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is pure algorithmic and enginnering study for new forms of databases.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
30

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: No risk as far as we can see.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We have properly cited the models (GPT4, Claude3) we used in the paper.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assett are released, the license, copyright information, and terms of use package should be provided. For popular datasets, paperswithcode. httrssswthhoodeccmmdaaatsett com/datasets has curated
licenses for some datasets. Their licensing guide can help determine the license of dataset.
31

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Not involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: no crowdsourcing research
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
32


Reviews:
[{"review_id": "lCVAXOnS6Q", "reviewer": "Reviewer_uiEW", "summary": "This paper proposes an unstructured query language based on a small segment of SQL. Its key feature is that it further supports unstructured texts and images because the authors assume that LLMs work on intra-row texts. During the query, the authors propose using online learning on LLM outputs over batches to improve the sample quality in the upcoming batches. Empirical results convey important information; that is, feeding longer context into larger LLMs does not work as well as using smaller LLMs in a more organized way.", "questions": "- Given that the output in the virtual column will work with other parts of the SQL, what is the failure rate in output formatting in the experiments?", "limitations": "Yes,", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper discusses several possibilities for using LLMs in relational databases with text columns. It reveals a new possibility that one could do something between 1. using LLMs as a black box and letting them handle everything in the context. and 2. using LLMs to parse the question into SQL and let the database engine do the job with much smaller LLMs.\n\nFor queries requiring sampling, a simple online learning algorithm is used to improve the sample efficiency.", "weaknesses": "- This paper is more like a technical report or a guideline for building certain products. The overall product presented is simplified from the introduction's proposed question. Realizing this system under the strong assumption that LLMs work on intra-row semantic understanding is not too difficult: the virtual column, although it seems to be filled by LLMs, can be realized in several prompts, such as closed-domain classification for WHERE and open-domain classification for GROUPBY.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments. Below we try to address the potential misunderstandings, and provide more experimental results for justifications.\n\n\n### **\"...technical report...the strong assumption that LLMs work on intra-row semantic understanding\"**\n\nWhile generating the virtual column entirely and process with SQL is a feasible approach, the goal of the paper is to present an efficient system that can void such kind of \"linear scan\" of the database content, and thus the core of the contribution lies in the unbiased+low-variance sampler and the online learning approach that orchestrates well with the LLMs. Thus we focus on providing algorithmic detail and the proof (see appendix A) for these while put less attention on the database and system layer. If the reviewer have specific details that would like to learn more, please feel free to let us know. We will also release the code afterwards.\n\nRegarding the assumption that LLMs work on intra-row semantic understanding, we have carefully examined this. On IMDB dataset, the gpt model can achieve **97%** accuracy on average over each review, and many of the errors are actually due to the unclear sentiment from the data. Definitely the accuracy would depend on the difficulty of the question, but having a good-enough out-of-the-box solution can be a good starting point, given that people are still pushing the frontier of LLMs.\n\n\n### **\"...failure rate in output formatting...\"**\n\nWe completely rewrite the entire SQL engine and thus the error handling can be easily done in our system. As is shown in Appendix, most of the time we ask LLMs to output <True> or <False> based on the query. We did a quick experiment to see when the LLM failed to generate either of these.\n\n\n| Dataset | LLM            | Violation rate |\n| ------- | -------------- | -------------- |\n| IMDB    | Claude-3-haiku | 0.0%           |\n|         | gpt-4o-mini    | 0.8%           |\n| ABCD    | Claude-3-haiku | 0.0%           |\n|         | gpt-4o-mini    | 0.2%           |\n\nWe can see the above models, despite being small and cheap, are very good at instruction following and the formatting violation rate can be tolerated with extra error handling. And we believe that the next generation LLMs can only be better at instruction following. Actually as of Aug-6, openai released a new version of gpt-4o (**gpt-4o-2024-08-06**) which claimed to have **100%** accuracy on complex format following.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MisCi7wJ3U", "reviewer": "Reviewer_6SvA", "summary": "This paper proposes an ambitious new framework for analytics on unstructured databases, the Universal Query Engine (UQE). The authors first present a list of semantics and clauses for querying unstructured databases and propose methods for implementing these functionalities, including indexing and compiling. Experiments on multimodal unstructured data analytics tasks show that UQE outperforms other methods, demonstrating the promise of utilizing UQE in database analytics.", "questions": "I have listed my questions in the Weaknesses section.", "limitations": "The limitations of the work are properly stated.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The motivation is quite interesting and necessary to broaden the functionalities of databases.\n- The paper is clearly written and well-presented.\n- The authors presented the exact scope of the task and proposed methods accordingly.\n- The proposed approach is reasonable and performs well within the scope of the work.", "weaknesses": "- Could you elaborate more on the difference between BINDER and this approach (line 39)? Is it due to the lack of indexing and compatibility with unstructured information?\n- Similar to the first point, the baselines seem a bit weak. Why have the authors not used BINDER as their baseline?\n- I want to hear the authors' opinions on how advancements in LLMs and vision models might affect the guarantee that databases consistently return the same results. Traditional database engines, which are widely used, provide this consistency over time. Could these technological advancements affect the reliability of database analytics and, subsequently, compromise their reliability?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing insightful and constructive feedback. We provide our response below, as well as extra experimental results in the global response. We look forward to learning your further thoughts.\n\n### **\"... difference between BINDER...\"**\n\nYes as the reviewer pointed out, our focus is on the analogy of \"indexing\" (or sampling and search) to efficiently implement the unstructured database query engine. BINDER focuses on translating natural language questions into programs with llm as a callable function. The execution of this program is delegated to existing SQL implementations. These two can actually work together to deliver a better end to end system. \n\n### **\"...used BINDER as their baseline?\"**\n\nWhile BINDER and our UQE have different focuses, we provided additional experiments using BINDER on our tasks in the general response. We can see that without the query engine optimization, BINDER would achieve much higher variance and error when performing aggregation queries, and the retrieval F1 is also much lower compared to UQE under the same LLM budgets.\n\n### **\"...consistently return the same results...compromise their reliability\"***\n\nWe totally agree with the reviewer that the consistency and reliability is important, and that's why our algorithm (especially the one for the aggregation query) optimizes for low-variance and zero-bias estimation, which has significantly boosted this compared to all baselines. In addition to that, one can further reduce the temperature of the LLMs and use fixed random seeds to make sure the results are reproducible for a given setup.\n\nThe reviewer raised another good point where the LLM behind the scene gets updated and that would cause the inconsistency across different versions of LLMs. This is a generic problem of the application built on top of LLMs, but here are several ways to mitigate it.\n\n1. Result caching: for the same query, one can always cache the intermediate or final results to save the compute and also make it consistent for the same question.\n\n2. Prompt calibration: once a new model is deployed, a common practice is to adjust the prompt a bit to make it consistent or fitting better on the target tasks. Similar practices can be made for the database queries, as long as a proper evaluation set is available. In our experiment we prepare multi-modal datasets with the ground-truth labels to validate and calibrate the prompts.\n\n3. Even without any further effort, it may not be that inconsistent in some situations. In our paper we used claude-3-haiku as the backbone, and below we use the latest gpt-4o-mini to provide more justification for that. On IMDB we see little variation, where we can see that, the difference caused by the model switching is much lower than using a worse query engine.\n\n\n| Task        | BINDER         | UQE-haiku (in paper) | UQE-gpt4o-mini (new) |\n| ----------- | -------------- | -------------------- | -------------------- |\n| Retrieval   | 0.505 ± 0.030  | 0.978 ± 0.003        | 0.956 ±0.010         |\n| Aggregation | 13.67% ± 6.24% | 5.75% ± 3.43%        | 6.33%± 4.71%         |\n\nOf course, this behavior shift would be task related, but with the advances of LLMs we believe this variation would converge and be more stable to prompts.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ljZTc9D1mY", "reviewer": "Reviewer_rs84", "summary": "This paper propose a new Universal Query Engine (UQE) that directly interrogates and draws insights from unstructured data collections.\nFurther, a Universal Query Language (UQL) is proposed as a dialect of SQL that provides full natural language flexibility in specifying conditions and operators.\nUQE leverages the ability of LLMs to conduct analysis of unstructured data and achieve efficient and accurate query execution.", "questions": "Please see the weakness section.", "limitations": "No discussion on limitations, I suggest the authors to add one.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The idea of designing new query language and query engine for unstructured databases leveraging the power of LLMs is interesting.\n2. The paper is also very clear with thorough experiments and analysis.\n3. Well-organized presentation of the proposed method and its components.", "weaknesses": "1. Many details about the design and implementation of UQE are missing. For example, the description of the generation of machine-specific code (assembly instructions) during the compilation stage (L251) is not clear. Please clarify the details of this strategy. Additionally, the authors claim that calling the LLM dominates the overall cost per query (L239). Providing detailed information about the LLM-calling stage would be beneficial.\n2. The indexing technique introduced by UQE is related to the sampling strategy based on specific queries. However, database indexing is traditionally meant to facilitate quick searches. If each query requires sampling, will this impact efficiency? Additionally, doesn't this compromise accuracy?\n3. This paper primarily addresses unstructured datasets, including video and audio. However, the experiments only involve text and images, lacking validation for broader generalizability. \n4. Furthermore, there are plenty of multi-modal vector databases, yet the authors only compare the RAG-based query. Can UQE outperform recent multi-modal query databases, such as Milvus and MillenniumDB? If so, demonstrating this would make the evaluation more convincing.\n5. Does the query support join operations, such as joining across multiple different modal files?\n6. It's hard to validate the results without supplying code/models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments. Below we try to address the potential misunderstandings, and provide more experimental results for justifications.\n\n\n### Q1 **\"...machine-specific code...clarify the details...\"**\n\nThe analogy is to show how to convert the query (in UQL) to the machine code (the concrete prompts that work with LLMs). Concretely, for example, a `WHERE cond` statement would be \"compiled\" to\n    \n>*Please analyze the following movie review, and only reply <True> if cond, or <False> otherwise.*\n\nand executed on the rows sampled by the online-learning or unbiased samplers. We provided the full set of prompts in appendix for your information. \n\n### Q1 **\"...LLM dominates the overall cost per query...Providing detailed information\"**\n\nFor example, a query on clevr dataset costs  0.2USD using gpt-4o. The compute on the client side only takes CPU time for 30s. On AWS such a machine costs 5.80USD/month, so 30s of compute would be nothing, compared to the LLM calls.\n\n### Q2 **\"...database indexing...sampling...impact efficiency? ...accuracy?\"**\n\nThe traditional database is able to build index on the columns that might be conditioned on, so as to avoid linear scan of the entire database. For unstructured data, as we don't know the query beforehand, there is no such indexing. Vector DB builds the embedding based indexing, but can only be useful for limited types of queries as we have seen in the experiments.\n    \nBased on that, we propose the analogy of indexing in unstructured database, i.e. the sampling techniques to 1) avoid linear scan; 2) handle complex reasonings; 3) have statistical guarantee.\n\nSo to answer your question, it is actually the sampling (and the online learning) that makes things efficient. There's rich literature [1] on approximated compute engine, and we have shown that its accuracy is much better than alternatives throughout comprehensive experiments (e.g., **40x** F1 score compared to the reviewer suggested Milvus for some queries).\n\n\n### Q3 **\"...addresses unstructured datasets, including video and audio. However, the experiments only involve text and images\"**\n\nThe proposed UQE framework rely on the LLM backend for multi-modal queries, and the optimization done in the paper is agnostic to the modality. \n\nNevertheless, we provide new experimental results on the Audio MNIST, which contains 30k wav files from 60 speakers pronouncing digits 0-9.\n\nBelow we perform the audio semantic retrieval experiments. The query is first converted to audio space using TTS and the corresponding audio embedding is used for MIPS/Milvus search.\n| Query                                    | BINDER-gemini | MIPS/Milvus | UQE-gemini    |\n| ---------------------------------------- | ------------- | ----------- | ------------- |\n| \"Three\"                                  | 0.109 ± 0.022 | 0.445       | **0.839 ± 0.135** |\n| \"A number whose square equals to itself\" | 0.259 ± 0.068 |    0.039         | **0.922 ± 0.024**             |\n| \"The minimum prime number\"               | 0.107 ± 0.044 | 0           | **0.917 ± 0.025** |\n\nWe can see UQE consistently does better than alternatives, and it also allow complex queries that require reasoning, while embedding based MIPS or Milvus is limited to the type of queries.\n\n### Q4 **\"...Can UQE outperform ... Milvus and MillenniumDB...\"**\n\nIn our paper we compared against MIPS (Maximum inner-product search) and we show the clear advantage in Table 2. Vector DB like Milvus is designed for fast but approximated nearest neighbor (ANN) search. By default it uses inner product as the similarity metric, thus is expected to be an approximation of MIPS in our paper (where we do full vector database scan without approximation).\n\nNevertheless, we still run Milvus on all benchmarks, and the results have been included in the global response and UQE still wins in almost all query types. MillenniumDB is for graph or structured data query and thus may not be suitable to compare. We hope this would resolve some misunderstandings.\n\n\n### Q5 **\"...join operations...\"**\n\nNo, we have stated in our conclusion section that table join optimization is not done in our paper. With that said, one can still create the virtual columns in UQL via `SELECT` and then use existing SQL engine for the joins, at a potential very high cost of language model calls. We hope to optimize the join operation in future work.\n\n### Q6 **\"...code/models\"**\n\nThe model/data and prompts are all provided already. We will release the code.\n\n### **Limitation section**\n\nWe have already clearly stated the limitation of current work in the conclusion section, including 1) lack of table join optimization; 2) LLM selection; 3) even larger datasets. And we will work on these in future works.\n\n\nReferences:\n>[1] A handbook for building an approximate query engine.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RkHq4M0sAp", "reviewer": "Reviewer_E5QU", "summary": "This paper proposed a Universal Query Engine to directly draw insights from unstructured data. For aggregation queries, this paper designed an unbiased sampling algorithm to solve the problem that it’s hard to apply index on virtual columns. Inspired by the workflow of the C++ compiler, this paper also proposed a workflow of optimizing and generating prompt to achieve more efficient query.", "questions": "I noticed that lc-gpt-4-turbo also has quite a high latency on Semantic Retrieval tasks, is it possible to do more optimization on the model itself to improve the performance to make such a method practice?", "limitations": "Yes, the authors have mentioned the limitations of this work, but I suggest to provide more comprehensive evaluations, detailed discussions about UQE’s scalability and cost. After all, these are critical problems about the practicality.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. This paper suited an interesting and important problem, by using LLM, more complex, semantics -related SQL queries can be achieved.\n2. This paper took efficient into consideration and proposed corresponding algorithm and workflow to improve the query speed.\n3. Provided theory proof of the unbiased sampling algorithm.\n4. The idea of introducing compiler’s workflow into such problem to accelerating the LLM’s inference is interesting.", "weaknesses": "1. UQE seems to lack scalability on the Semantic Retrieval task. The latency reported in Table 5 is as high as 38.08 seconds. Also, the paper didn’t state that whether these numbers are the total latency or average latency per query. If they are latency per query, using UQE on the Semantic Retrieval task still has a far distance from practice.\n2. The cost of embedding operation of Algorithm 1 and 2, and the cost of Algorithm 2 are not discussed in the paper. Although the authors wrote in the appendix that the g function in Algorithm 2 caused the high latency problem, no quantitative analysis was provided.\n3. Lack of comparison with important baselines. I noticed that the references [9] and [33] mentioned in related work are not included in the baselines. Using LLM as UDF may significantly slow down the queries, however, they may have better accuracy on aggregation queries. Thus, I think it’s necessary to include them in the baselines to further evaluate the performance of the trade-off made by Algorithm 1 between accuracy and latency. \n4. Lack of evaluation of UQE’s time cost in the main text of the paper. I noticed those results are reported in the appendix. However, in the database area, the latency and cost are significant metrics that should be reported in the main text of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments, and we do value your opinion regarding the latency issues. Below we try to justify from the use cases and existing baselines, and also provide more experimental results. \n\n### Q1 **\"...latency...far distance from practice...\"**\n\nThe latency is per query and is averaged over 8 runs. We agree that this latency is not meant for real-time queries like the SQL engine behind web apps. The type of query that is most useful is for massive data analytics, where the alternative solution is usually to train a task specific ml model, build up the data preprocessing pipeline and then run SQL, which can easily take days for data scientists.\n\n\nSecondly, our framework offers the flexibility to do trade-offs between latency and accuracy. Take the IMDB retrieval experiment as an example:\n\n\n| Budget $B$ | 256           | 128           | 64            | 32            |\n| ---------- | ------------- | ------------- | ------------- | ------------- |\n| Latency(s)   | 38.08         | 21.61         | 11.11         | 5.84          |\n| F1 score   | 0.978 ± 0.003 | 0.974 ± 0.005 | 0.921 ± 0.013 | 0.828 ± 0.035 |\n\nAnd for aggregation:\n\n| Budget $B$ | 128            | 64            | 32            |\n| ---------- | -------------- | ------------- | ------------- |\n| Latency(s) |  5.83 |  4.28      | 2.93            |\n| Error      | 5.75% ± 3.43%  | 6.84% ± 5.52% | 8.29% ± 7.39% |\n\nSo comparing to alternative solutions for data analytics, which take days to first preprocess the data into structured columns and then run SQL, the speed of UQE is significantly improved.\n\n### Q2 **\"...cost of embedding... cost of Algorithm 2...g function...\"**\n\nThe embedding cost is the same as the vector DBs. This is a pre-processing step and only needs to be done once per dataset. For text we use voyage-2 which costs 0.1 USD / million tokens, and it roughly take 8h (due to rate limit) to embed these datasets. For image we use Cloud Vertex multi-modal embedding and it takes 12h (due to rate limit).\n\nFor a query on IMDB that takes 21s, querying g and updating g takes 1.5s and 0.5s respectively. The main reason for the latency is the sequential nature of online learning of g, and a potential improvement is to leverage batched online learning to improve the parallelism.\n\n### Q3 **\"...baselines.. the trade-off made by Algorithm 1 between accuracy and latency\"**\n\nWe followed the reviewer's advice to include BINDER (the viper-gpt is similar but for images) in all the experiments, and as shown in our global rebuttal, the performance of BINDER is much worse when given the same LLM budgets (we stop the BINDER execution when running out of budget, as looping over the entire database can easily cost hundreds of dollars, which is not feasible for us).\n\nTo see how the accuracy evolves for both UQE and BINDER, we perform the following experiments on aggregation tasks (IMDB) by varying the budgets. In paper we use B=128, and we lower/higher the budget for UQE/BINDER respectively in the table below.\n\n\n| Budget $B$ | 512            | 256           | 128            | 64            | 32            |\n| ---------- | -------------- | ------------- | -------------- | ------------- | ------------- |\n| BINDER     | 8.11%  ± 3.15% | 8.35% ± 5.47% | 13.67% ± 6.24% |      -         |      -         |\n| UQE        |         -       |     -          | 5.75% ± 3.43%  | 6.84% ± 5.52% | 8.29% ± 7.39% |\n\n\nwe can see that both BINDER and UQE will have more accurate estimation when given more budget. But for BINDER, it takes 16x more LLM calls (512) compared to UQE (32) to obtain the same level of accuracy or precision. We hope this answers the question of tradeoff of Algorithm 1.\n\n\n### Q4 **\"...latency and cost...in the main text...\"**\n\nWe have provided the cost per query in every table in the main text. We will follow the reviewer's advice to include the latency and also the above trade-off analysis into the main text.\n\n\n### Q5 **\"... lc-gpt-4-turbo also has quite a high latency...\"**\n\n\nlc-gpt-4-turbo is basically the baseline on feeding the entire content into gpt-4-turbo and ask questions. There could be several ways that make it faster (though it is not the focus of this paper to make LLM itself run faster):\n\n1. prefix caching; if the data never changes, one can cache majority of the kv states of prompts which can save 2x of the cost/latency or so.\n\n2. in general, the models will only get faster/cheaper, e.g., gpt-4o-mini which came out recently.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their insightful feedback, and below we provide experimental updates w.r.t baselines to address the reviewers’ comments.

### **Comparison with baselines like BINDER [1] (review 6SvA and E5QU)**

While [1] and UQE use similar SQL-like language, the focus is very different. [1] or [2] focuses on translating natural language questions into programs with llm as a callable function. The execution of this program is delegated to existing SQL implementations. On the contrary, UQE replaces the query engine layer, with the focus to execute this kind of programs in an efficient and accurate manner.

Nevertheless, we adapted BINDER (or equivalently [2] if it is for image) for our task by providing the program directly and executing it until it reaches the same API cost as UQE. 

Below is the estimation error and variance on aggregation tasks (lower the better).

| Benchmark |       Query        |  lc-GPT4-turbo  |     BINDER      |         UQE         |
|:---------:|:------------------:|:---------------:|:---------------:|:-------------------:|
|   IMDB    | sentiment_positive | 49.02% ± 21.23% | 13.67% ± 6.24%  |  **5.75% ± 3.43%**  |
|   ABCD    |   account_access   | 69.25% ± 32.82% | 18.99% ± 9.85%  | **11.75% ± 9.78%**  |
|           | single_item_query  | 78.42% ± 9.36%  | 26.95% ± 22.16% | **12.32% ± 10.53%** |
| AirDialog |        book        | 47.58% ± 15.24% | 10.15% ± 7.64%  |  **4.98% ± 2.26%**  |
|           |     no_flight      | 47.92% ± 21.62% | 21.08% ± 16.78% |  **8.78% ± 8.12%**  |
|           |   no_reservation   | 50.54% ± 21.86% | 21.19% ± 12.10% |  **7.23% ± 5.40%**  |
|   Clevr   |   obj_count < 4    | 22.46% ± 19.35% | 31.04% ± 25.15% |  **9.55 ± 8.55%**   |
|           |   # spheres > 3    | 35.72% ± 14.95% | 19.35% ± 13.81% | **15.14% ± 10.71%** |

Below is the F1 score (higher the better) on semantic retrieval tasks. Note that vector DB (or per reviewer rs84, Milvus) is doing approximated MIPS as we reported in the paper, so basically they are the same and we merge their results below:

| Benchmark |       Query        | lc-GPT4-turbo  |     BINDER     | MIPS/Milvus |        UQE        |
|:---------:|:------------------:|:--------------:|:--------------:|:-----------:|:-----------------:|
|   IMDB    | sentiment_positive | 0.397 ± 0.041  | 0.505 ± 0.030  |    0.875    | **0.978 ± 0.003** |
|   ABCD    |   account_access   | 0.045 ± 0.033  | 0.076 ± 0.017  |  **0.961**  |   0.940 ± 0.019   |
|           | single_item_query  | 0.023 ± 0.021  | 0.065 ± 0.017  |    0.266    | **0.935 ± 0.006** |
| AirDialog |        book        | 0.327 ± 0.0667 | 0.342 ±  0.031 |    0.930    | **0.979 ± 0.010** |
|           |     no_flight      | 0.066 ± 0.037  | 0.144 ±  0.034 |    0.867    | **0.928 ± 0.018** |
|           |   no_reservation   | 0.156 ± 0.075  | 0.145 ± 0.042  |    0.965    | **0.969 ± 0.004** |
|           |       cancel       | 0.006 ± 0.009  | 0.013 ±  0.009 |    0.066    | **0.741 ± 0.205** |
|   Clevr   |   obj_count < 4    | 0.058 ± 0.026  | 0.093 ± 0.031  |    0.023    | **0.897 ± 0.006** |
|           |   # spheres > 3    | 0.037 ± 0.027  | 0.089 ± 0.017  |    0.145    | **0.859 ± 0.007** |

From the tables above, we can see UQE achieves much better estimation precision and retrieval effectiveness compared to BINDER or a straight query engine implementation. Meanwhile, we confirmed again that vector DBs, even the commercial ones, may not be suitable for some retrieval tasks that require deep reasoning.

To see how the accuracy evolves for both UQE and BINDER, we perform the following experiments on aggregation tasks (IMDB) by varying the budgets. In paper we use B=128, and we lower/higher the budget for UQE/BINDER respectively in the table below.


| Budget $B$ | 512            | 256           | 128            | 64            | 32            |
| ---------- | -------------- | ------------- | -------------- | ------------- | ------------- |
| BINDER     | 8.11%  ± 3.15% | 8.35% ± 5.47% | 13.67% ± 6.24% |      -         |      -         |
| UQE        |         -       |     -          | 5.75% ± 3.43%  | 6.84% ± 5.52% | 8.29% ± 7.39% |

we can see that both BINDER and UQE will have more accurate estimation when given more budget. But for BINDER, it takes 16x more LLM calls (512) compared to UQE (32) to obtain the same level of accuracy or precision.

### **Results on audio database (review rs84)**

Follow reviewer rs84, we provide new experimental results on the Audio MNIST, which contains 30k wav files from 60 speakers pronouncing digits 0-9.

Below we perform the audio semantic retrieval experiments. The query is first converted to audio space using TTS and the corresponding audio embedding is used for MIPS/Milvus search.
| Query                                    | BINDER-gemini | MIPS/Milvus | UQE-gemini    |
| ---------------------------------------- | ------------- | ----------- | ------------- |
| "Three"                                  | 0.109 ± 0.022 | 0.445       | **0.839 ± 0.135** |
| "A number whose square equals to itself" | 0.259 ± 0.068 |    0.039         | **0.922 ± 0.024**             |
| "The minimum prime number"               | 0.107 ± 0.044 | 0           | **0.917 ± 0.025** |

We can see UQE consistently does better than alternatives, and it also allow complex queries that require reasoning, while embedding based MIPS or Milvus is limited to the type of queries.


>References\
[1] Binder: Binding Language Models in Symbolic Languages\
[2] ViperGPT: Visual Inference via Python Execution for Reasoning

Meta-review: The paper presents a system that can be used to conduct data analytics on unstructured data. The system uses, of course, LLMs :) The system is tested and thoroughly assessed.

Reviewers have given average scores but in general we are all favorable for this paper to appear as poster at NeurIPS.
Decision: Accept (poster)