CRUSH4SQL: Collective Retrieval Using Schema Hallucination For Text2SQL
Authors: Mayank Kothyari
Dhruva Dhingra
Sunita Sarawagi
Soumen Chakrabarti
Venue: EMNLP 2023 Main (2023)
Keywords: Text-to-SQL
LLM
Retrieval augmentation
Query decomposition

Abstract: Existing Text-to-SQL generators require the entire schema to be encoded with the user text.  This is expensive or impractical for large databases with tens of thousands of columns.  Standard dense retrieval techniques are inadequate for schema subsetting of a large structured database, where the correct semantics of retrieval demands that we rank sets of schema elements rather than individual documents. In response, we propose a two-stage process for effective coverage during retrieval.  First, we use an LLM to hallucinate a minimal DB schema that it deems adequate to answer the query.  We use the hallucinated schema to retrieve a subset of the actual schema, by composing the results from multiple dense retrievals. Remarkably, hallucination --- generally considered a nuisance --- turns out to be actually useful as a bridging mechanism. Since no existing benchmarks exist for schema subsetting on large databases, we introduce two benchmarks: (1) A semi-synthetic dataset of 4502 schema elements, by taking a union of schema on the well-known SPIDER dataset, and (2) A real-life benchmark called SocialDB sourced from an actual large data warehouse comprising of 17844 schema elements. We show that our method leads to significantly higher recall than SOTA retrieval-based augmentation methods.

CRUSH4SQL: Collective Retrieval Using Schema Hallucination For Text2SQL
Mayank Kothyari' and Dhruva Dhingra and Sunita Sarawagi' and Soumen Chakrabarti Department of Computer Science and Engineering Indian Institute of Technology Bombay, Mumbai, India
Abstract
benchmarks such SPIDER (Yu et al., 2018) and WikisQL (Zhong et al., 2017), and even "datasets in the wild," " like SEDE (Hazoom et al., 2021), are all associated with modest-sized schema. E.g.. the average number of tables and columns in any one schema for SPIDER is 5.3 tables and 28.1 columns, and for SEDE is 29 tables and 212 columns.
Existing Text-to-SQL generators require the entire schema be encoded with the user text. This is expensive or impractical for large datahases with tens thousands columns. Standard dense retrieval techniques inad- equate for schema subsetting of a large struc- tured database, where the correct semantics of retrieval demands that we rank sety of schema elements rather than individual elements. In response, propose two-stage process for effective coverage during retrieval. First, we instruct an L.LM hallucinate minimal DB schema deemed adequate answer the query. We use the hallucinated schema to retrieve subset of the actual schema, by composing the results from multiple dense retrievals. Re- markably. hallucination - generally consid- ered nuisance ful as bridging mechanism. Since exist- ing benchmarks exist for schema subsetting large databases, introduce three bench- marks. Two semi-synthetic datasets are de- rived from the union of schemas in two well- known datasets, SPIDER and BIRD, result- ing in 4502 and 798 schema elements respec- tively. real-life benchmark called SocialDB is sourced from an actual large data warehouse comprising 17844 schema elements. We show that our method! leads significantly higher recall than SOTA retrieval-based augmentation methods.
In contrast, real-life datasets may have thousands of tables with hundreds of columns per table. E.g., real-life data warehouse of data about various so- cial indicators of a country comprises of more than 17.8 thousand columns! For such large schema, we cannot afford to include the entire schema in the prompt preceding each query; only high-recall subset of the schema can be attached to each ques- tion. LLM-as-a-service usually charges for each token exchanged between client and server, we want the subset to be small as possible while ensuring high recall. Even for in-house (I.)LMs or other Text-to-SQL methods, admitting extrancous schema elements as candidates for use in the gen- erated SQL reduces its accuracy (Li et al., 2023a). Retrieving a subset of a corpus of passages to augment the LLM prompt has become emerg- ing area (Shi et al., 2023; Ram al., 2023) for non-Text-to-SQL applications as well. Most trieval modules depend on standard "dense passage retrieval" (DPR) based on similarity between the question embedding and an embedding of a docu- ment (Khattab and Zaharia, 2020) or schema ele- ment (Nogueira et al., 2020; Muennighoff, 2022).
out to be actually use-
1 Introduction
We argue (and later demonstrate) that Text-to- SQL needs more circumspect approach to jointly leverage the strengths of LLMs and dense retrieval. Consider a question "What is the change in fe- male school enrollment and GDP in Cameroon between 2010 and 2020?", to be answered from a large database like World bank data?. An ef- fective Text-to-SQL system needs to realize that GDP and female school enrollment are two key
State-of-the language model based Text-to-SQL. generators provide impressive accuracies on well known benchmarks, but they require the entire DB schema as input, along with the user question text (Scholak et al., 2021; Li al., 2023a; Liu al., 2023; Rajkumar al., 2022). Widely-used
Corresponding Authors: maykat2017 @om.l...mmmmmmmmmmmmmmmmmmmmm. sunita @ iitb.ac.in
'The code and dataset for the paper are available at https: //gi tigb com/ haom/MayK.... Slayk/CRRSSHSS,
hnttps://datacaatllog.or wortellloogwwwwobbbbbe. org//

---

"atoms' in the question and match these ta- bles Development indicators and Education statistics respectively. Additionally, it needs to generalize Cameroon to Country, and 2010, 2020 to year to match correct columns in these ta- bles. This requires generalization and phrase-level matching via LLMs (with all the world knowl- edge they incorporate); pre-deep-NLP and 'hard' segmentation techniques (Gupta and Bendersky, 2015), as well as token-decomposed deep retrieval, such as ColBERT (Khattab and Zaharia, 2020), are unlikely to suffice.
maximize coverage of distinct elements of the hal- lucinated schemn while rewarding connectivity of the selected subset the schema graph.
Our second contribution involves the creation of three novel benchmarks for the task of retrieval augmentation related to Text-to-SQL conversion large schema. We developed two semi-synthetic benchmarks, encompassing 4502 and 768 columns respectively, by taking a union of all databases from the well-known SPIDER benchmark, as well as the relatively recent BIRD benchmark. The third benchmark is sourced from a production data warehouse and features 17.8 thousand columns. This serves to mitigate critical limitation in ex- isting Text-to-SQL. benchmarks, which have much smaller schema. Beyond its large scale, our third benchmark introduces additional challenges such as a significantly higher overlap in column names, and challenging lexical gaps (when compared to SPIDER), between schema mentions in the ques- tion and the actual schema name.
Our setting thus requires us to retrieve, score and select sets of schema elements that collectively cover explain the whole query. This bears some superficial similarity with multi-hop question swering (QA). Closer scrutiny reveals that, in multi- hop QA benchmarks such HotPorQA, each ques- tion comes with only 10 passages, out of which are 'distractors' and two need to selected to ex- tract the answer. The best-performing systems (Li et al., 2023c; Yin et al., 2022) can afford exhaus- tive pairing of passages along with the question, followed by scoring using all-to-attention such problem setting with
Using these benehmarks, we present exten- sive empirical comparison between CRUSH and existing methods. We show consistent gains in recall of gold schema elements, which translates to increased accuracy of Text-to-SQL. generation.
techniques do not scale thousands of tables and hundreds of columns per table, where as many as 30 schema elements may be involved query.
The results of our analysis provide valuable in- sights into the weaknesses of the existing single- embedding token-level representations.
Our contributions: In this paper, we propose new method called CRUSH² that leverages LLM hallucination (generally considered a nuisance) in conjunction with dense retrieval, to identify a small, high-recall subset of schema elements for a down- stream Text-to-SQL. stage. CRUSH first uses few- shot prompting of an LLM to hallucinate a minimal schema that can be used to answer the given query. In the example above, the LLM might hallucinate schema that includes tables like
2 Notation and problem statement
We are given a large database schema D consist- ing of a set of tables T, with each table & E T comprising of a set of columns c C(t). We will use d denote a schema element ('document'), which can be either a table or column. A schema element d has a textual name or description Sd)). The text associated with a column t.c is written as the concatenation S(I).((c) as shown in Figure 1.
Indicators(names country, year) and Education enrollment data(type, country, year, value)
Apart from the database, the input includes nat- ural language question r. Question with (possibly unknown) correct ('gold') SQL query g(r). The gold SQL query q(x) mentions a subset R(g(z)) of the schema elements from D. Almost always, R(q(=)) < [D].
associated
The hallucinated schema contains strings that are significantly closer to the gold table names men- tioned earlier. We use the hallucinated schema elements to define collection of index probes for fast index- retrieval of the actual schema ele- ments in the DB. Finally, CRUSH approximately solves a novel combinatorial subset selection objec- tive to determine a high-recall, small-sized schema subset. The objective includes special terms to
Our goal is to retrieve from D, (small) subset R(x) C D that includes R(g(=)), i.e., R(g(z)) c R(æ). The question æ will be concatenated with the schema subset R(x)) and input to a Text-to-SQI. model to convert the question into an SQL query. There are multiple reasons to minimize R(x)]
*Collcctive Retricval Using Schema Hallucination

---

Prompt prefix decomposition
Real schema D
(Nes : K( ((m)
(cas)
calage salgge.cceet.ggg clu eus.iallniagg.
((s)
B
Hallcirota the minimal achemm redefional dscabase that can be used to ansver the nalural languinge quastion. quasiinn Here are some Examples: Ecample
club. club clubid, spreg sockt conereed onglrv
dubb www.mmebeerccc club.club
the player. and the name the teem that the player belonge
Solve collective objestive Eqn.
ane www.ereeeessss.. bwrovverrrrae srmens mojor collgge audart ckun
dublocation
Tables:
match pesson/seeson, team, player). seamphame,
Example
vestwets rambestt, regan boanh mamber club suubistudent.tuuue stuid,
Count number mambers the Bootup Bakmore Club older than 18.
R(a) diub student, age, club member of club club member of club.stuid
www..cc.bb.cceeee clubname
coof
stdted
LLM
club member club stuid, greeeteeedoog seotopupe
Hallucinated scnema K(zz)
Text2SQL
Ming, cac you
clubfnamme jd. location description) membbrr of dubjclub sludentt idy.
club clubdesc
studentiid age)
shuder,
((+)
Figure I: Illustration of how CRUSH works. We prefix decomposition prompt with in-context examples to the question x and submit to an LLM. The response has a hallucinated schema K((x)) with "query elements' k. The real schema D has 'documents' which may be connected to each other via same-table-as and primary-foreign-ke relations Ca.a". The queries from the hallucinated schema are used to get candidate real schema elements C(x). Similarities cos(k, d) lead to sk,d scores. B is the budget size of R(x). the relevant real schema subset to be returned by the optimizer. R(x)) used by the downtream Text-to-SQL. system.
(I) The size of D is significantly larger than can be fitted in a prompt LLM. (2) LLM-as-a-ser- vice usually charges usage fees in proportion to the number of tokens exchanged with the client.
erly to gold schema D, containing such schema elements Age, Club description, and Club members, etc., we need to perform multiple types of lexical and syntactic reasoning on the question and schema:
(3) The performance of even in-house (L) or other Text-to-SQL systems degrade when extra- neous schema elements are presented as possible candidates for inclusion in the SQL query. In this
extract segments like older than 18 and Bootup Baltimore Club, generalize the first segment to likely schema element Age, and,
paper focus the task of efficiently retrieving
R(x) from D, while maximizing the recall of gold schema elements in R(g(z)).
for the second segment, instead of attempting to match strings like Bootup Baltimore verba- tim, match to a schema element called Club description.
We assume that the schema D is indexed a pre-processing step. Each table t(c)....) in the database D is exploded into the form t.e for each column, where ''' is separator character. Each col- 'document' d in information
To bridge such large lexical gap between the tokens of x and the gold schema R(g(z)), we de- signed two-phase approach. In the first phase, we transform x into an intermediate form K(xx) comprising of multiple generalized segments lever- aging an LLM. In the second phase, we use K((z) to retrieve from the DB schema 2> suitable schema element subset R(x), by approximately optimizing combinatorial objective that collectively maxi- mizes coverage of all elements of K(x)). We de- scribe these two phases next.
umn now acts retrieval system, except that we will retrieve sets of documents. Each document is sent into a pre- trained transformer, SGPT (Muennighoff,, 2022), or the LLM service to get an embedding d.
3 The CRUSH4SQL Approach
Successfully matching user question x to rel- evant schema R(g(z)) could be quite non-trivial, since the schema element names descriptions are often not directly mentioned in the question. For example, consider the question x Count the number of members in the Bootup Baltimore Club older than 18. In order to match this question prop-
3.1 LLM-based Query Transformation
Our goal here is infer from the question text x, a set K(xx) of intermediate search strings, which, when used to probe a suitable index over the client's

---

DB schema, will retrieve R(x). After unsuccessful attempts with query decomposition and token-level retrieval methods, we proposed to harness an LLM to aid with this task.
apply a pretrained transformer, SGPT (Muennighoff, 2022)
get per-token contextual embedding vectors 4: average-pool ver-token embeddings into
Initially, we attempted to use the LLM to extract variable name mentions or perform conventional query decomposition like in (Pereira et al., 2022). While these showed promise, we obtained much better results when took a leap and harnessed the power of an LLM to directly hallucinate a DB schema that could be used to answer the question æ.
(Through experiments, we will show that using the form "x t.c" improves recall, compared to not pre- fixing x.) At this stage, K(xx)) has been converted into bag of vectors {k). We perform nearest neighbor search on D using each key vector k, and retain some number of top matches per probe k based on cosine similarity of their embeddings. This gives us the candidate C(x) of schema elements from D. See Figure 1.
We use state-of-the-ait LLMs with few-shot prompting to hallucinate such a schema. We em- ploy GPT-3 (text-davinci-003) with a fixed prompt comprising of six in-context examples as shown in the first half of Table 1 for one of our datasets. We create the desired output ((xz) corresponding each x in the prompt guided by the gold schema R(g(z)) in the SQL corresponding to x. In the second half of Table we show examples of a few hallucinated schema from the LLM in response to the prompt. In each of the four examples, we see that the LLM has produced very reasonable schemas applying the right level of generalization to constants and implicitly segmenting the query across multiple tables in the hallucinated schema. The same trend holds for the significantly more challenging examples from the SocialDB dataset as seen in Table 15, and is also observed in the BirdUnion dataset as shown in Table 16.
Cosine baseline: A baseline method may simply return C(r). However, C(x) thus collected was ob- served to be biased toward generic, uninformative schema names such as Name and iddetifierr that appear across many tables. This hurts coverage. Therefore, design more careful optimization around C(x), described next.
3.2.2 Retrieval objective
We extract from the candidate set C(x) manage- able subset R(x) with size [R(x)] S B for some size budget B, that provides coverage to all parts of K, and also to reward connectivity the schema graph on the retrieved subset. Recall that large budget not only results in a higher expense to use an LLM-as-a-servicee but may also provide more challenging generation task for the downstream Text-to-SQL module.
We experimented with a few other prompt types, and we will present comparison in Section 5.4 of our empirical evaluation.
Entropy-guided similarity: Instead of just co- sine the distance between k K and d D, we refine the similarity to score match of rarer columns higher. Consider some E K((x) that has good matches with many schema elements E C(x). In information retrieval, this is anal- ogous to query word with low inverse document frequency (IDF) (Manning et al., 2008), and its ef- fect scores should be damped down. In the deep retrieval regime,
3.2 Collective Retrieval
In this stage our goal is retrieve subset R(x) from D that collectively R(x) is closest to the halluncinated schema K. in the context of z. First, we retrieve a candidate set C(z) using IC as probes on the indexed embeddings in D, and then we col- lectively match C(x) to (Cx)).
notion of entropy to act as a surrogate for IDF. Specifically, let cos(k, d) be the cosine score between and Fix & and consider the multinomial probability distribution
3.2.1 Retrieving candidate set C(x)
K(x) consists of set of hallucinated tables with their hallucinated columns, each of the form (c)...... These are written out as a of "(.e1" column names prefixed with table names. Hence- forth, we regard (C(x) as a set such hallucinated texts {k}. Each E K((x) is converted into an embedding vector k for retrieving 'real' schema elements, via the following steps:
{1 + cos(k, d))
Edecca) 2 [1 cos(k, d')) :d C(a) :de(())) (1)
in the multinomial simplex Al((x)-11 This multi- nomial distribution has an entropy, which we will denote by (k).. If H (k) is large, that means & has no sharp preference for any schema element
I: form concatenation "r t.c"

---

in C(x), so its impact on the perceived similar- ity cos(k, d) should be dialed down, inspired by THIDF vector space model from information re- trieval. We achieve this effect via the score
neighbors in dense embedding space. First lan- guage model (LM) M like SGPT (Muennighoff, 2022) or OpenAl's Similarity and Search Em- beddings API (model text sexxt-embedding-adaaaaae converts each string S(d) into a fixed-length em- bedding vector which we denote d = (S)))) Given a question v. we obtain the embedding æ of 2, i.c., x (x). and then retrieve the K nearest neighbors of in D as R(x) K-NN {d d c D}). This method has the limitation that the top-K retrieved elements may be skewed towards captur- ing similarity with only a subset of the gold schema R(g(z)). The RESDSQL. (Li et al., 2023a) Text-to- SQL system, too, selects the most relevant schema items for the encoder, using a cross-encoder (based on RoBERTa) between the question and the whole schema. Although the inryy-interaction encoder may implicitly align question tokens to schema to- kens, there is no apparent mechanism ensure phrase discovery and (LLM knowledge mediated) measurement of coverage of question phrase with schema element descriptions.
Sk,d - - + cos(k, d)) o( (k)), (2)
where a.)) is the standard sigmoid shifted by the average entropy H defined as the average (k)
over all & E K.
Coverage score:
We will assume that the hal-
lucinated schema elements are all informative, so we would like to 'cover' all of them using R(x). We score coverage of a k by R(x) using a soft maximization function defined as smx(ssa d E R(x)) log Σ exp(()a)
Meat
The first part of our collective objective is O₂ (R(x))
Σ smx($kd d E R(x)) (4)
kEX(())
Connections between 'documents': Schema el- ements are not isolated, but related to each other using the rich structure of the schema graph (Wang et al., 2020, Figure 2). For example, two columns may belong to the same relation, or they may be- long to different tables connected by a foreign key-primary key link. A scalar connectivity score e(d, 2 0 characterizes the strength of such a connection between d, d' E C(x). In our experi- ments choose e(d, d') to be non-zero constant y for all column pairs that are part of the same table or connected by a foreign key. We should choose R(x) to also maximize
LLMs for ranking: Sun et al. (2023) use an LLM for relevance ranking in information retrieval. They show that a properly instructed LLM can beat supervised learning-to-rant approaches. No query decomposition of mulli-hop reasoning is involved. Other uses of LLMss in scoring and ranking items are recommender systems (Gao al., 2023; Hou et al., 2023): turning user profiles and interaction history into (recency focused) prompts, encoding candidates and their attributes into L.L inputs, and asking the LLM to rank the candidates. No- tably, LLMs struggle to rank items as the size of the candidate set grows from 5 to 50.
(R()))) = Σ smx(e(dd d'): d' C R(x)) (5)
dcR((a)
The function smix is chosen instead of directly summing d() for all pairs in R(x) to prevent quadratically growing rewards for large subgraphs.
LLMs for question decompostion and retrieval: Decomposing complex questions has been of inter- est for some years now (Wolfson et al., 2020). In the context of LLMs, Pereira et al. (2022) propose question answering system where supporting evi- dence to answer a question can be spread over mul- tiple documents. Similar to us, they use an LLM to decompose the question using five in-context examples. The subquestions are used to retrieve passages. A more general architecture is proposed by Khattab al. (2022). None of these methods use the notion of hallucinated schema. They match subquestions passages, not structured schema elements. They entrust the final collective answer extraction to an opaque LM. In contrast, we have an interpretable collective schema selection step.
Overall objective: Combining the two desider- ata, we get our overall objective as
R(x) argmax (O)(R) + O2(R)).
(6)
RCC(2)
|
with a balancing hyperparameter is possible to express the above optimization mixed integer linear program. In practice we find it expeditious to use simple greedy heuristic. Also, we fix all experiments.
4 Related work
Dense Passage Retrieval (DPR): A default method of identifying R(x) is based on nearest

---

#
LLM prompt: Hallucinate minimal schema of relational database that be used to answer the natural language
question. Here are some examples:
x
Count the number members in Boolup Baltimore Club older than Club(Name, id, description, location), member club(club id, student id), Student(id, age)
x
What are the names of all stations with a latitude smaller than 37.5?
Station(Name, Latitude)
x
Show the season, the player, and the name of the team that players belong to.
K
Match_seasooe (seaoo,,,,on, team, player), Team(name, team identifier)
Find the first name and age of the students who are playing both Football and Lacrosse.
K
student id), Student(age. first name, student id) What are the names of tourist attractions reachable by bus or at address 254 Ottilie Junction? Locations(address location id), Tourist attractionshhow get there, location id, name)
SportsInfo
K
g
Give name the highest paid instructor.
Instructor( (Name, Salary)
Hallucinated X. generated by LLM given input x What are the names of properties that are either houses or apartments with more than room? Property(nane type, number of rooms)
x
x
Which employee received the most awards in ovaluations? Give me the employee name.
K
Employee namee, employee id), Evaluations id, awards)
What is the document name and template id with description with the letter "w" in it?
K.
Document(name, description, template id)
What semester ids had both Masters and Bachelors students enrolled?
Semester(id, start date, end date), (arellt id, student id, degree). Student(id, name)
Table 1: Examples of in-context training examples given to the LLM to prompt it to hallucinate minimal schema of a database that can be used to answer the given question.
5
Experiments
question in the test set, since the gold SQL is available, we have access to the gold retrieval set R(q(=)) C D. We measure recall only over col- umn names, since if a column name is selected in R(x), the table name is always implicitly selected.
In this section we compare CRUSH with existing methods for schema subsetting. We also present detailed ablation the various design options for CRUSH.
BirdUnion: Following the same approach as with SpiderUnion, created BirdUnion from BIRD (Li al., 2023b), relatively new cross- domain dataset, with 95 large databases and total size of 33.4 GB. covers more than 37 profes- sional domains, such as blockchain, hockey, health- care, education, etc. To simulate a larger schema, we combined 11 schemas in the development set (where each schema covers approximately 6.82 ta- bles and 10.64 columns), prefixing each table name with its corresponding database name. The unified schema comprises 798 columns distributed across 75 tables, constituting D. We evaluate the model using 1534 questions sourced from BIRD dev-set. We adopt the same evaluation metric as with Spi- der
5.1 Datasets
We test the following two benchmarks that we designed, because of the absence of any pre- existing large-schema benchmark.
This is semi-synthetic bench- mark derived from SPIDER (Yu et al., 2018), pop- ular Text-to-SQL benchmark, where each question x corresponds to of the 166 database schemas. These schemas cover various, somewhat overlap- ping topics such as Singers, Concert, Orchestra, Dog Kennels, Pets, and so forth. Each schema is compact, averaging approximately 5.3 tables and 28 columns. To simulate a larger schema, we com- bine these 166 schemas, prefixing each table name with its corresponding database name. The uni- fied schema comprises 4,502 columns distributed across 876 tables, forming the D. We evaluate the model using 658 questions sourced from the SPIDER development set after excluding questions where the gold SQL contains '*'. Unlike in SPI- DER, the question æ is not associated with one of these 166 DB ids. Instead, the system has to find the correct schema subset.
SpiderUnion:
SocialDB: We created this benchmark from a real-life data warehouse, which collates statistics on various social, economic, and health indicators from a large country, featuring diverse geographical and temporal granularities. The complete database schema is publicly accessible. though withhold the URL during the anonymity period. The ware- house holds approximately 1046 tables and total of 18,685 columns. Each table and column carries descriptive names. From administrators of the Web-
Our evaluation metric, given a retrieved set [R(g())))R())] For each R(x),, is recall, defined as [K((())]

---

site, we obtained 77 questions along with the gold tables, which contain the answers. Some examples of questions and schema names can be found in Table 15. We could not obtain gold column names on this dataset, and thus our evaluation metric is table recall measured as (aalevs(ft))(/TTabes((1333
In Table 14 we present anecdote that illustrates how CRUSH is able to more effectively cover the gold schema, compared to Single DPR. Single DPR gets swamped by matches to the student id column across many diverse tables, whereas CRUSH is able to cover all gold columns.
[[able(((()))
5.2 Methods Compared
Impact of improved recall on Text-to-SQI. gen- eration accuracy: We use the state-of-arr RES- DSQL (Li al., 2023a) model for generating the SQL using the schema subset selected by various systems. Following standard practice, we use Exact Match (EM) and Execution Match (EX) accuracy to evaluate the quality of the generated SQL. As seen in Table 3, the improved recall of schema subsetting translates to improved accuracy of Text- to-SQL generation. However, beyond budget of 30, we see a drop in the accuracy of the generated SQL, presumably because the Text-to-SQL. method gets distracted by the irrelevant schema in the input. For the BirdUnion dataset, the RESDSQL system could not handle the larger schema at budget 100, but we expect similar trend.
Single DPR (SGPT): This is the popular Dense Passage Retrieval (DPR) baseline where we use the SGPT LM (Muennighoff, 2022) to embed into single embedding vector æ and retrieve from D based on cosine similarity with a D. Single DPR (OpenAD): As above, except we use OpenAl's Similarity and Search Embeddings API (text-embedding-aadee 0022 as the LM.
Token-level Embedding (ColBERT): Instead of searching with single embedding we perform (oken-decomposed retrieval for finer-grained in- teraction (Khattab and Zaharia, 2020).
CRUSH: Our proposed method, where we use OpenAl's Vanii to get hallucinated schema with prompts Table for SpiderUnion and Ta- ble 15 for SocialDB. Embeddings are obtained using SGPT, because we need contextual em- beddings for tokens in x (not supported in Ope- nAI's embedding API) to build embeddings for k E K. The default candidate set size is lim- ited 100, with edge scores assigned default value of e(d, 0.01 for all edges in both SpiderUnion and BirdUnion, while is zero for SocialDB.
5,4 Robustness Across Prompt Variations
Before we arrived at the schema hallucination ap- proach, we experimented with other prompts moti- vated by the techniques in the question decompo- sition literature. In Table 4 we present two such alternatives. (1) Variables: that seeks to identify key isolated variables mentioned in x, and (2) Rela- tions: that relates the variables to subject, roughly analogous to table name. We present a compari- son of different prompt types in Table 6. Observe that the schema-based prompts of CRUSH are con- sistently better than both the earlier prompts. In CRUSH we used six examples of hallucinated schema in the prompt for in-context learning. We reduce that number to two and four and present the results in Table 7. Recall improves significantly with more examples but even with two examples, the LLM provides gains over the baseline.
5.3 Overall Comparison
In Table 2 we present recall for different budgets on the size of the retrieved set R(x) on the four different methods on both the SpiderUnion and SocialDB datasets. Key observations:
We see significant boost in the recall by CRUSH, particularly low to medium budget levels. For example, on SpiderUnion at a budget of ten columns, we recall 83% of gold columns whereas the best existing method only gets up to 77%. On the BirdUnion dataset, we recall 76% with CRUSH, while the best alternative method reaches only 56%. On the more challenging SocialDB dataset we recall 58% of gold tables whereas the best alternative method gets 49%. Token-level methods are worse than even Single DPR-based methods.
In Tables 8 and 9, we present the impact of ran- dom shuffling on the six in-context examples in the prompt (Tables I and 15). We provide mean and standard deviation schema retrieval recall and downstream Text-to-SQL generation accuracy. No- tably, across the five iterations, the standard de- viation in recall and EX remains low, suggesting robust performance regardless of the prompt order. In Tables 10 and 11, we investigate the robustness of recall and EX values when different sets of few-
Embedding of OpenAl is slightly better than than of SGPT.

---

Data
Method
Budget
10
20
@
@
r
SpiderUnion
Single DPR (SGPT)
0.50
0.61
0.92
0.95
Single DPR (OpenAl)
0.55
0.64
0.77
0.86
0,90
0.93
0,96
Token-level (ColBERT)
0.49
0.59
0.72
0.84
0,88
0.92
0.95
CRUSH (ours)
0.72
0.90
0.92
0.94
0.97
SociaLDB
Single DPR (SGPT)
0.35
0.40
0.45
0.32
0.58
0.67
0.73
Single DPR (OpenAl)
0.39
0.44
0.49
0.56
0.60
0.67
0.76
Token-level (ColBERT)
0.36
0.36
0.44
0.51
0.55
0.57
0.64
CRUSH (ours)
0.40
0.52
0.58
0.67
0.69
0.71
0.75
BiroUnioo
Single DPR (OpenAl)
0.33
0.43
0.56
0.66
0.72
0.8
0,93
CRUSH (ours)
0.39
0.54
0.71
0.82
0.88
0.92
0.97
Table 2: Comparison of recall for various column ranking methods on the test sets of SpiderUnion, SocialDB, and
BirdUnion datasets. We observe a significant boost in the recall by CRUSH gold schema at all budget levels.
Data set
Method
Budget
@
@
10
@ 20
@ 30
@ 50
100
SpiderUnion
Single DPR (OpenAI)
0.29/0.33
0.35/0.41
0,45/0.53
0,48/0.57
0,48/0.59
0,48/0.59
0.51/0.62
CRUSH (ours)
0.35/0.39
0.46/0.53
0.52/0.60
0.53/0.64
0.54/0.64
0.52/0.63
0.52/0.62
BirdUnion
Single DPR(OpenAD)
0.03/0.07
0.05/0.10
0.07/0.13
0,09/0.15
0.09/0.16
0.10/0.18
+/-
CRUSH (ours)
0.04/0.07
0.07/0.11
0.09/0.15
0.11/0.19
0.11/0.19
0.12/0.21
Table Exact Match (EM) / Execution Match (EX) accuracy when RESDSQL is used to generate SQL on schema retrieved various budgets from CRUSH and Single DPR (OpenAI). The higher recall of CRUSH's retrievals lead to more accurate SQLs. Very large budget worsens SQL accuracy.
Example
Question
x
Count the number of memhers in club Bnotup Baltimore older than 18.
Variables: Age, Club
Relations: Age of club members, Name of the club
What are the names of all stations with a latitude smaller than 37.5?
Variahles: Latitude, Station
Relations:
Latitude of the station, Name of the station
Show the season, the player, and the name of the that players helong Variables: Match, Season, Player
Relations: Name the the player helongs to, Scason(s) played by player, Name of the player first name and age the students who are playing both Football and Lacrosse.
x
Variables: Student, Age, Game, Football
Relations:
Sports played by student, Age student, Name of student
Table 4: Two alternative forms of transforming x into segments. Contrast these with the hallucinated schema in Table 1. Only top-4 shown due to lack of space.
shot in-context examples. Low standard deviation suggests high level of robustness across differ- ent samples. In Table 12, explore the LLM's schema generation under different temperature tings, finding minimal impact on the results. Fi- nally, as shown in Table 13, even in the zero-shot setting, CRUSH exhibits significant improvement over the baseline Single DPR based retrieval.
entropy guided similarity, edge scores, and cov- erage of hallucinated schema elements. We study the impact of cach. We remove the entropy dis- counting in Eqn. (2), and observe a drop in recall low budget levels. When we remove the edge scores, we also see a mild drop.
To study the impact of coverage, we replace the soft-max function smx() with a simple summa- tion so that for each selected E D, the reward is just the sum of similarity to each k E K. We find that the recall suffers. A coverage encouraging objective is important to make that the lected items are not over-represented by matches few K.
5.5 Ablation on Collective Retriever
CRUSH includes a number of careful design choices. In Table 5 we show the impact of each design choice.
During retrieval, obtain the embeddings of k K. jointly with contrast, if indepen- dently embed k, the recall drops significantly. After retrieval, the overall objective of collec- tive selection (Eq 6) incorporates three key ideas:
Conclusion
While LLMs incorporate vast world knowledge and corpus statistics, they may be unfamiliar with

---

Budget
@
r@
10
@ 20
30
@ 50
@ 100
CRUSH
0.39
0.72
0.83
0.90
0.92
0,94
z-contextual embedding
0.53
0.66
0.77
0.86
0.90
0.93
0.95
Entropy
0.54
0.67
0.81
0.89
0.91
0.94
0.97
Edge scores
0.57
0.71
0.83
0,90
0.92
0.95
0.97
Coverage
0.54
0.67
0.81
0.89
0.91
0.94
0.97
Table 5: Ablation on design choices CRUSH on the SpiderUnion dataset. Each row after the first, provides CRUSH with one of the key design elements of CRUSH removed.
Prompt
Budget
tions.
type
r @ 3
@
r @ 10
r @ 20
@ 30
Variables
0.43
0.56
0.73
0.84
0.89
Dataset
Budget r
Relations
0.57
0.66
0.80
0.89
0.92
CRUSH
0.57
0.71
0.83
0.90
0.92
r r@
3
r
@
@
10
r
@
20
r @ 30
EM Mean
0.33
0.45
0.51
0.51
0.51
Table 6: Effecct of prompt types. Compared to the
EM Std
0.02
0.00
0.01
0.01
0.02
CRUSH prompt that ask for hallucinating a schema, the earlier two prompts, motivated by traditional ques- tion decomposition viewpoint, are much worse.
EX Mean
0.38
0.52
0.60
0.61
0.60
EX Std
0.01
0.00
0.01
0,02
0.02
Table 9: Effect of randomly shuffling (in-context) exam-
ples in CRUSH prompts (SpiderUnion) over EM/EXX
Number of prompts
Budget
@
S
@
10
@
20
@ 30
Dataset
Budget
Single DPR (SGPT)
0.50
0.61
0.76
0.86
0.89
@
Φ
10
@
20
@ 30
CRUSH (2 shots)
0.52
0.67
0.81
0.88
0.90
Recail Mean
0.60
0.70
0.80
0.90
0.90
CRUSH shots)
0.58
0.70
0.82
0.89
0.92
Recall Std
0.02
0.01
0.01
0.01
0.01
CRUSH (6 shots)
0.59
0.72
0.83
0.90
0.92
Table 10: Effect of selecting different (in-context) ex-
Table 7: Number of shots (in-context examples) in CRUSH prompts. Even two examples give gains over the baseline and increasing the number of examples im- proves recall.
amples in CRUSH prompts (SpiderUnion) over recall.
Budget
@
@
20
@
FM Mean
0.34
0.46
0.52
0.52
0.51
EM Stdey
0.01
0.02
0.01
0.02
0.02
Dataset
Budget
EX Mean
0.38
0.53
0.60
0.62
0.61
3
@
r
@
10
@
20
@
30
EX Stdey
0.01
0.01
0.01
0.02
0.02
SpiderUnion
Table 11: Effect of selecting different (in-context) exam-
Recall Mcan
0.58
0.70
0.82
0.89
0.92
ples in CRUSH prompts (SpiderUnion) over EM/EX.
Recall Std
0.01
0.01
0.00
0.00
0.01
SocialDB
Dataset
Budget
Recall Mcan
0.37
0.47
0.56
0.65
0.69
Recall Std
0.03
0.03
0.04
0.02
0.02
r
3
@
r
10 r @ 20 r @ 30
SpiderUnion
Table Effeet of randomly shuffling (in-context) exam-
Recall at temp
0.59
0.72
0.90
0.92
ples in CRUSH prompts (SpiderUnion) over recall.
Recall at temp = 0.5
0.58
0.70
0.82
0.89
0.92
Recall temp
0.58
0.69
0.82
0.89
0.91
(possibly private) client DB schemas, which can be very large, rendering impractical or expensive any attempt upload the full schema in-context along with questions for Text-to-SQL applications. Remarkably, we find a workable middle ground by allowing the LLM to hallucinate schema from the question and limited in-context examples with no reference to the client schema. Then we formulate a novel collective optimization to map the hallu- cinated schema to real DB schema elements. The resulting real schema subset that is retrieved has small size, yet high recall This schema subset can be readily uploaded MLassd Text-to-SQL methods. The reduced space of client DB schema elements also improves the accuracy of generated SQL for ofte-of-the-an Text-to-SQI. SQL implementa-
SocialDB
Recall temp 0
0.40
0.52
0.58
0.69
0.71
Recall temp 0.5
0.41
0.50
0.61
0.67
0.71
Recall at temp
0.36
0.47
0.56
0.63
0.70
Table 12: Effect of temperature changes on recall.
Dafaset
Budget r
r
@ 20
30
SpiderUnion
Zero shot
0.58
0.72
0.84
0.90
0.92
Single DPR(OpenAD)
0.55
0.64
0.77
0.86
0.90
CRUSH (ours)
0.59
0.72
0.83
0.90
0.92
SocialDB
zero shot
0.43
0.52
0.65
0.68
Single OPR(OpenAL)
0.39
0.44
0.49
0.56
0.60
CRUSH (ours)
0.40
0.52
0.58
0.67
0.69
Table 13: Effect of zero-shot prompting on recall.

---

lan- 7 Limitations
International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR "20, page 39-48, New York, NY, USA. Association for Computing Machinery.
Removing two limitations in CRUSH may be use- ful in future work. First, at present, hallucination is almost completely unguided by the client DB schema. It would be of interest to explore if the client DB schema can be compressed into a very small prompt text to give some limited guidance to the LLM schema hallucinator. At present the link weights e(d, d") between schema elements d, d' hardwired; may be useful to extend the learning optimization to fit these weights.
Haoyang Li, Jing Zhang, Cuiping Li, and Hong Chen. 2023a. Resdsql: Decoupling schema linking and skeleton parsing for text-to-sql.
Jinyang Li. Binyuan Hui, Ge Qu, Binhua Li, Jiaxi Yang.
Bowen Li, Bailin Wang, Bowen Qin, Rongyu Cao. Ruiying Geng, Nan Huo, Chenhao Ma, Kevin C. C. Chang, Fei Huang, Reynold Cheng, and Yongbin Li. 2023b, Can Ilm already serve as database interface? a big hench for large-scale database grounded text- to-sqls.
8 Acknowledgement
Xin- Yi Li, Wei-Jun Lei, and Yu-Bin Yang. 2023c. From easy to hard: Two-stage selector and reader for multi- hop question answering. In ICASSP.
We thank Microsoft for sponsoring access to Azure OpenAl API via the Accelerate Foundation Models Academic Research Initiative. A special thanks to Niti Aayog's 's NDAP team for letting us use their data schema and sharing their query workload. Ad- ditionally, we extend our thanks to Mayur Datar and Vinayak Borkar for stimulating discussions. We thank IBM's AI Horizons grant for partly sup- porting this research. Soumen Chakrabarti was partly supported by grants from IBM and SERB.
Aiwei Liu, Xuming Hu, Lijie Wen, and Philip S. Yu. 2023. A comprehensive evaluation of chatgpt's 's zero- shot text-to-sql capability.
Christopher D. Manning, Prabhakar Raghavan, and Hin- rich Schütze. 2008. Introduction to Information Re- Irieval. Cambridge University Press, Cambridge, UK.
Niklas Muennighoff. 2022. Sgpt: Gpt sentence
embeddings for semantic search. arXiv preprint arXiv:220..0890
References
Yunfan Gao, Tao Sheng, Youlin Xiang, Yun Xiong, Haofen Wang, and Jiawei Zhang. 2023. Chat-rec: Towards interactive and explainable llms-augmented recommender system.
Rodrigo Nogueira. Zhiying Jiang, Ronak Pradeep, and Jimmy Lin. 2020. Document ranking with a pre- trained scquence-to-sequene of the Association for Computational Linguistics: EMNLP 2020, pages 708-715 Online. Association for Computational Linguistics
model. In Findings
Manish Gupta and Michael Bendersky. 2015. Informa- tion retrieval with verbose queries. In SIGIR, pages 1121-1124.
Jayr Pereira, Robson Fidalgo. Roberto Lotufo, and Ro- drigo Nogueira. 2022. Visconde: Multi-document qa with gpt-3 and neural reranking.
Moshe Hazoom, Vibhor Malik, and Ben Bogin. 2021. Text-to-SQL in the wild: A
dataset based on stack exchange data. In Proceedings of the 1st Workshop on Natural Language Processing for Programming (NLP4Prog 2021), pages 77-87, Online. Association for Computational Linguistics.
Nitarshan Rajkumar, Raymond Li, and Dzmitry Bah- danau. 2022. Evaluating the text-to-sql capabilities of large language models.
Ori Ram, Yoav Levine, Itay Dalmedigos, Dor Muhlgay, Amnon Shashua, Kevin -cyton-Brown, and Yoav Shoham. 2023, In-context guage models.
Yupeng Hou, Junjie Zhang, Zihan Lin, Hongyu Lu, Ruobing Xie, Julian McAuley, and Wayne Xin Zhao. 2023. Large language models are zero-shot rankers for recommender systems.
Torsten Scholak, Nathan Schucher, and Dymitry Bah- danau. 2021. Picard parsing incrementally for constrained auto-regressive decoding from language models. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics.
Omar Khattab, Keshav Santhanam, Xiang Lisa Li, David Hall, Percy Liang. Christopher Potts, and Matei Zaharia. 2022. Demonstrate-searchh predict: Composing retrieval and language mod- els for showledge-intensing NLP. arXiv preprint 2422242
Weijia Shi, Sewon Min. Michihiro Yasunaga, Minjoon Seo, Rich James, Mike Lewis, Luke Zettlemoyer, and Wen tau Yih. 2023. Replug: Retrieval-augmented block-box language models.
Omar Khattab and Matei Zaharia. 2020. Colbert: Effi- cient and effective passage search via contextualized late interaction over bert. In Proceedings of the 43rd

---

Weiwei Sun, Lingyong Yan, Xinyu Ma, Pengjie Ren, Dawei Yin, and Zhaochun Ren. 2023. Is chatgpt good at search? investigating large language models re-ranking agent.
Xiannian Hu. Xinyu Zhang. Zhao Cao, Xuanjing Huang, and Xipeng Qiu. 2022. Rethinking label smoothing on multi-hop question answering. arXiv preprint arXhv:2212.09522
Bailin Wang, Richard Shin, Xiaodong Liu, Oleksandr Polozov, and Matthew Richardson, 2020. Rat-sql: Relation-ave aware schema encoding and linking for text- to-sql parsers. In Proceedings of the 58th Annual Meeting of the Association for Computational Lin- guistics, pages 7567-7578.
Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga. Dongxu Wang. Zifan Li, James Ma, Irene Li, Qingn- ing Yao, Shanelle Roman, et al. 2018. Spider: A large-scat human- labeled dataset for complex and cross-domain semantic parsing and text-to-sql task. In Proceedings of the 2018 Conference Empiri- cal Methods Natural Language Processing, pages 3911 1-3911.
Tomer Wolfson, Mor Geva, Ankit Gupta, Matt Gard- ner, Yoav Goldberg, Daniel Deutch, and Jonathan Berant. 2020. Break it down: A question understand- ing benchmark. Transactions of the Association for Computational Linguistics.
Victor Zhong, Caiming Xiong, and Richard Socher. 2017. Seq2sql: from natural language using reinforcement learning. CoRR, abs/1 709.00010.
Generating structured queries
Zhangyue Yin, Yuxin Wang, Yiguang Wu, Hang Yan,

---

CRUSH4SQL: Collective Retrieval Using Schema Hallucination For Text2SQL
(Appendix)
A
Anecdotes
Table 14 we show examples of schema retrieved by baseline single embedding method and CRUSH.
Observe how retrieved set from single embedding is biased towards matching one of the columns of the hallucinated schema.
B Prompts for the SocialDB dataset
In Table we show the six few-shot examples in prompts for schema hallucination. The bottom half of the table shows four hallucinated schema obtained from the L.M..
x R(g(z))
What are the ids of students who both have friends and are liked? fetworr.friend.suudenn id, network. likel. liked Single Embedding (OpenAl) college.student.idd
R(x)
student www.aaaawwsssmttt.tuuttttttttu.a id,
school_payerrschooo..chooLLL
www.oorrsssetteaannneeeeeeeeeeee __id,
subeennc.eeeccceeeccccocdttttttt candidate id,
voler.student.stuid
network__.likkesstuddee id,
school_playcraccoollboog.o.o
R(x)
CRUSH
student_ haw.aaaassaeeetteuuuuttttttttaaa
network_l.iikes.stuee id
_eeaminggssuudnnssstttde sttp:tntttttttt_tidt id
network__..fieendffrreee id
letwork_..freend.sttuee
hrtwork_llikks..lieee
dtrdd details
student aasessssssssetttttsueentttt ceatiletttcccceeeeeeeee _tt.rruaaatttnnnnneeeeaa id
fettork_2.personfrrennt
Table 14: Results from single embedding retrieval with OpenAl Vs CRUSH.

---

#
LLM prompt: Hallucinate minimal schema of a relational database that can be used to answer the natural language
question. Here are some examples:
What is the correlation between child nourishment and parental education in the of Madhya Pradesh?
haclly_helthh_uuueee female literate population)
age, child nourishment), Population_cena cennttuoooccuuu(((eeee state, age-group, male literate population,
x
Health center per population ratio the village level or district level from the year 2015?
К.
Health_ infirastructurevillaaee health facility), Population, cettiiiioonenuuususeeeee census((istrrict, male population, female population) Distribution of medical professionals by type across regions from 2011 onwards from the state of Kerala,
x
K.
Health statistics_ cacastics_sttttttte statewise professional)
x
Correlation between road connectivity and Mother Mortality Rate (MMR) during 2011 from the state UK.
K
Family health survey (state, year, maternal mortality). Road statistics(state, road type)
What is the trend for CPI of goods excluding food and fuel?
K
Inflation money and credit(year, Categories of Consumer Expenditure)
Correlation between number of bank branches and district growth? nown_amenities census(amenities, public works department), bank details(number of branches, bank type)
K.
Hallucinated K. generated LLM given input æ
x
Which Central Public Sector Enterprise generated most employment the years?
statistiex(enterpriie,, year, employment), how awareness among women impact births in caesarean section??
peppriss_ddtaallsctttrrisss sector)
K.
health_statisties, statewise (state, year, caesarean section births), women_awarenn awareness survey(state, year, awareness level)
x
what is the correlation between socio-cconomic status and health insurance enrollments?
I
socio economic status(income, education level), health insurance enrollment(age, gender. income level)
Trend of Total Export Volume of Select Commodities to Principal Countries based on New commodity classification as per 2009-10 10 over a period of years?
K
export export_data(yeat year commodity, country, total export volume), commmoddyycaassffccooooooooooooo new commodity classification)
Table 15: Examples of in-context training examples (for SocialDB) given to the LLM to prompt it to hallucinate a minimal schema of a database that can be used to answer the given question.
LLM prompt: Hallucinate minimal schema relational datahase that can be used to answer the natural language question. Here are some examples:
What is the brand of the truck that is used to ship by Zachery Hicks?
I
truck(truck id, make), shipment(truck id, driver id), driver id, first name, last name) State the name of the city where Jose Rodriguez works, paployyee(ocationll
K
firstname, lastname). location(IocationDD, locationcity)
Please list all horror films that have rating of I.
K
u2basc(mon (moviedd, rating), movies22ircetoor List all the names of the books written by Danielle Steel.
genre)
K.
bnok(hook, title), book_aokkaa auooor id, author_id id), author(author_ author author_name)
How many female representatives are there in Michigan?
K
(boouuebe id. bioguide, gender_ bjo), current lerms(bioguide, type, state)
x
How many stars does each of the 3 top users with the most likes in their reviews have?
Tips(user id. likes), Users(user id, user average average_stars)
Hallucinated R. generated by LLM given input x
Which country had the station that sold the most expensive product id No.2 for one unit?
K
Product(product id, price). Gas Station(gus station id, country), Sales(gas station id, product id, quantity)
Please list the titles of the posts owned by the esgillespie?
K
Posts(post_ie id, title, user_id), (d).dd), Users(user_iss id, username)
Which country the constructor which got point the No. 24 from? race(race_iae constructorjid p_ddd, points(race_ What the administrator's email address for the school with the highest number of test takers who received SAT scores of at least Pr0 the name the school.
K
constructor points), constructorcoonssuutrrr__ country)
x
AC
Schools(school id. school name, administrator _erit, Test takers(school id, SAT_ score)
Table 16: Examples of in co-eentex training examples (for BirdUnion) given to the LLM to prompt it to hallucinate minimal schema of database that can be used to answer the given question.


Reviews:
[{"review_id": "3A1mXfgOh8", "reviewer": "Reviewer_yafE", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Result 1: First we study the **effect of randomly shuffling the six few-shots**. We report mean and standard deviation of both recall for schema retrieval and accuracy of downstream text-to-sql generation.. Rest of the settings are the same as in the main tables in the paper.  Observe the low standard deviation in recall across the five runs.\n| Budget      | 3    | 5    | 10   | 20   | 30   | 50   |\n| ----------- | ---- | ---- | ---- | ---- | ---- | ---- |\n| SpiderUnion |      |      |      |      |      |      |\n| Recall Mean | 0.58 | 0.70 | 0.82 | 0.89 | 0.92 | 0.94 |\n| Recall Std  | 0.01 | 0.01 | 0.00 | 0.00 | 0.01 | 0.00 |\n| SocialDB    |      |      |      |      |      |      |\n| Recall Mean | 0.37 | 0.47 | 0.56 | 0.65 | 0.69 | 0.73 |\n| Recall Std  | 0.03 | 0.03 | 0.04 | 0.02 | 0.02 | 0.01 |\n\nEM/EX for different shuffles for SpiderUnion:\n| Budget  | 3    | 5    | 10   | 20   | 30   | 50   |\n| ------- | ---- | ---- | ---- | ---- | ---- | ---- |\n| EM Mean | 0.33 | 0.45 | 0.51 | 0.51 | 0.51 | 0.49 |\n| EM Std  | 0.02 | 0.00 | 0.01 | 0.01 | 0.02 | 0.02 |\n| EX Mean | 0.38 | 0.52 | 0.60 | 0.61 | 0.60 | 0.59 |\n| EX Std  | 0.01 | 0.00 | 0.01 | 0.02 | 0.02 | 0.02 |\n\nResult 2: Next we report **stability to different sets of examples chosen in the few-shots**.  Again observe the low standard-deviation in the resultant recall values.\n| Budget      | 3    | 5    | 10   | 20   | 30   | 50   |\n| ----------- | ---- | ---- | ---- | ---- | ---- | ---- |\n| SpiderUnion |      |      |      |      |      |      |\n| Recall Mean | 0.6  | 0.7  | 0.8  | 0.9  | 0.9  | 0.9  |\n| Recall Std  | 0.02 | 0.01 | 0.01 | 0.01 | 0.01 | 0.00 |\n\nEM/EX for different sets for SpiderUnion:\n| Budget  | 3    | 5    | 10   | 20   | 30   | 50   |\n| ------- | ---- | ---- | ---- | ---- | ---- | ---- |\n| EM Mean | 0.34 | 0.46 | 0.52 | 0.52 | 0.51 | 0.49 |\n| EM Std  | 0.01 | 0.02 | 0.01 | 0.02 | 0.02 | 0.02 |\n| EX Mean | 0.38 | 0.53 | 0.60 | 0.62 | 0.61 | 0.59 |\n| EX Std  | 0.01 | 0.01 | 0.01 | 0.02 | 0.02 | 0.02 |\n\nResult 3: Next we generate **multiple schemas from the LLM with different temperatures**.  The results do not change too much with temperature either.\n| Budget               | 3    | 5    | 10   | 20   | 30   | 50   |\n| -------------------- | ---- | ---- | ---- | ---- | ---- | ---- |\n| SpiderUnion          |      |      |      |      |      |      |\n| Recall at temp = 0   | 0.59 | 0.72 | 0.83 | 0.9  | 0.92 | 0.94 |\n| Recall at temp = 0.5 | 0.58 | 0.7  | 0.82 | 0.89 | 0.92 | 0.93 |\n| Recall at temp = 1   | 0.58 | 0.69 | 0.82 | 0.89 | 0.91 | 0.94 |\n| SocialDB             |      |      |      |      |      |      |\n| Recall at temp = 0   | 0.40 | 0.52 | 0.58 | 0.69 | 0.71 | 0.75 |\n| Recall at temp = 0.5 | 0.41 | 0.50 | 0.61 | 0.67 | 0.71 | 0.74 |\n| Recall at temp = 1   | 0.36 | 0.47 | 0.56 | 0.63 | 0.70 | 0.76 |\n\nResult 4: Finally, we observe that even with **zero-shots** the model provides significant gains over the baseline single-embedding based retrieval.   \n| Budget              | 3    | 5    | 10   | 20   | 30   | 50   |\n| ------------------- | ---- | ---- | ---- | ---- | ---- | ---- |\n| SpiderUnion         |      |      |      |      |      |      |\n| zero shot           | 0.58 | 0.72 | 0.84 | 0.9  | 0.92 | 0.94 |\n| Single DPR (OpenAI) | 0.55 | 0.64 | 0.77 | 0.86 | 0.90 | 0.93 |\n| CRUSH (ours)        | 0.59 | 0.72 | 0.83 | 0.9  | 0.92 | 0.94 |\n| SocialDB            |      |      |      |      |      |      |\n| zero shot           | 0.33 | 0.43 | 0.52 | 0.65 | 0.68 | 0.74 |\n| Single DPR (OpenAI) | 0.39 | 0.44 | 0.49 | 0.56 | 0.60 | 0.67 |\n| CRUSH (ours)        | 0.40 | 0.52 | 0.58 | 0.67 | 0.69 | 0.71 |", "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": "1. The paper presents a novel approach to schema subsetting in large databases, which can inspire further research and development in this area.\n\n2. The introduction of new benchmarks provides valuable resources for evaluating and comparing future methods in schema subsetting.\n\n3. The improved recall and enhanced Text-to-SQL accuracy demonstrated by the proposed method can contribute to the development of more efficient and accurate Text-to-SQL generators for large databases.\n\n4. The paper's findings can potentially lead to more practical and cost-effective solutions for Text-to-SQL applications in real-world scenarios involving large databases with numerous columns.", "reasons_to_reject": "- This paper relies a minimal database schema which is hallucinated by an LLM. It would be better to discuss the stability of this step, and how robust it is with respect to the final semantic parsing performance. ", "questions_to_authors": "", "paper_topic_and_main_contributions": "This paper addresses the problem of schema subsetting in large databases with tens of thousands of columns for Text-to-SQL generators. Encoding the entire schema with user text is expensive and impractical in such cases. The main challenge is that standard dense retrieval techniques are not suitable for ranking sets of schema elements rather than individual documents.\n\nThe paper makes the following contributions:\n\n1. It proposes a novel two-stage process for schema subsetting in large databases, leveraging an LLM to hallucinate a minimal database schema.\n2. It introduces two new benchmarks for schema subsetting on large databases.\n3. The proposed method demonstrates significantly higher recall than state-of-the-art retrieval-based augmentation methods, indicating its potential for practical applications.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "csDTZFvl3N", "reviewer": "Reviewer_1yLK", "summary": "", "questions": "A. Lines 044-048. Can you give a reference that might be helpful to others for this claim?\n\nB. Lines 228-231. Are you talking about your own unsuccessful attempts here? How about similar work by other researchers? Any papers with techniques that would not work here?\n\nC. How did you select the examples that you use in your prompt to GPT-3 (Table 1)? What is special about them?\n\n", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q1. *Can you give a reference that might be helpful to others for this claim?*\n1. World Bank data (https://datacatalog.worldbank.org/home)\n2. Data Commons (https://www.datacommons.org/)\n3. One more reference is omitted due to the double-blind review process\n\nQ2. *Are you talking about your own unsuccessful attempts here? How about similar work by other researchers? Any papers with techniques that would not work here?*\\\n-> Yes. We are not aware of any prior work on this scale of datasets for schema subsetting.\n\nQ3. *How did you select the examples that you use in your prompt to GPT-3 (Table 1)? What is special about them?*\\\n-> We randomly sampled over the training dataset.  In the response to reviewer yafE we present results with multiple random selections.", "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": "* The problem of natural language question answering over relational databases is an important one.\n* The CRUSH framework presented by the paper is interesting and solves an important subproblem of the general question answering problem.\n* The two benchmark datasets created by the author(s) are interesting in their own right.", "reasons_to_reject": "No reasons to reject in my opinion.", "questions_to_authors": "A. Lines 044-048. Can you give a reference that might be helpful to others for this claim?\n\nB. Lines 228-231. Are you talking about your own unsuccessful attempts here? How about similar work by other researchers? Any papers with techniques that would not work here?\n\nC. How did you select the examples that you use in your prompt to GPT-3 (Table 1)? What is special about them?\n\n", "paper_topic_and_main_contributions": "The paper is on the topic of natural language question answering over SQL databases. The author(s) proposes a method called CRUSH that uses LLMs and dense retrieval to obtain a small subset of a database schema that can then be used as one of the inputs of a Text-to-SQL system. The first component of CRUSH uses the in-context learning functionality of GPT-3 to retrieve a (hallucinated) schema K(q) that could be used to answer a user question q. Then, K(q) is passed as input to an optimization problem which also takes as input elements of the real database schema that match K(q). The solution of the optimization problem is a small schema R(q) that can be used to answer q with an existing question answering engine. Another contribution of the paper is the creation of two benchmark datasets (SpiderUnion and SocialDB) that can be used to evaluate similar proposals. Finally, the paper contains an ablation study evaluating the effect of various components of CRUSH.", "excitement": 4, "reproducibility": 5, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Missing_References": "No missing references in my opinion."}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "The paper is well written and it reads very nicely.\nSome minor comments:\n* Line 191: service\n* Related work section. It is unusual to have the related work section before the experiments. In my experience, the related work section is either the second section or the section before the last in a paper.\n* Line 384. RoBERTa\n"}}, {"review_id": "fehD6mVHRk", "reviewer": "Reviewer_H9wu", "summary": "", "questions": "- Could you provide any examples of how the hallucinated schemas differ from the gold schemas? How does this affect downstream SQL accuracy?\n- Have you experimented with any techniques to make the hallucination prompts more robust and reduce reliance on gold schemas?\n- Is there any plan to release the SocialDB benchmark to advance research in this area?\n- Could you discuss any challenges faced in real-world deployment or limitations compared to lab setting?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q1. *The techniques are evaluated only on the authors' new benchmarks. Additional experiments on other datasets could strengthen the results.*\\\nUnavailability of large scale datasets for the public is our  reason for introducing new benchmarks for further research in this study.  \n-> We are trying to run a second experiment by taking a union of the schema on another recently released Text-to-SQL benchmark.  We hope to publish the results soon.\n\nQ2. *The hallucination prompts are hand-designed based on gold schemas, which may limit real-world applicability. More analysis on robustness would help.*\\\nPlease note that the gold schema in our case is *very large*.  The few-shot examples cover only a small part of the gold schema.  Further, for the SpiderUnion datasets, the few-shot prompts were generated from the schema present in the training dataset whereas they were evaluated on unseen schema from the test set. We report additional numbers with other randomly chosen few-shot examples for the SpiderUnion dataset.  The results are present in the response to reviewer yafE.  We observe that our results are robust to many different ways of choosing the few-shots.  \n\nEven with zero-shot prompting we get good schema hallucinations as seen in the additional experiments reported in the response to reviewer yafE \n\nQ3. *Could you provide any examples of how the hallucinated schemas differ from the gold schemas? How does this affect downstream SQL accuracy?*\\\nWe give three examples, two of which give rise to correct SQL and another example where hallucinated schema fails leading to gold schema not getting retrieved and thus wrong SQL\n\nExample 1:\n```\nQuestion: Who owns the youngest dog? Give me his or her last name.\n\nGold SQL: SELECT T1.last_name FROM Owners AS T1 JOIN Dogs AS T2 ON T1.owner_id  =  T2.owner_id WHERE T2.age  =  ( SELECT max(age) FROM Dogs )\n\nGold Database schema:  \n\tBreeds(breed_code, breed_name)\n\tCharges(charge_id, charge_type, charge_amount)\n\tSizes(size_code, size_description)\n\tTreatment_Types(treatment_type_code, treatment_type_description)\n\tOwners(owner_id, first_name, last_name, street, city, state, zip_code, email_address, home_phone, cell_number)\n\tDogs(dog_id, owner_id, abandoned_yn, breed_code, size_code, name, age, date_of_birth, gender, weight, date_arrived, date_adopted, date_departed)\n\tProfessionals(professional_id, role_code, first_name, street, city, state, zip_code, last_name, email_address, home_phone, cell_number)\n\tTreatments(treatment_id, dog_id, professional_id, treatment_type_code, date_of_treatment, cost_of_treatment)\n\nSchema elements needed from Gold DB to write SQL: \n\tdogs(age, owner_id)\n\towners(last_name, owner_id)\n\nHallucinated Schema:  \n\towner(first name, last name, owner id)\n\tdog(dog id, age, owner id)\n\nCRUSH retrieval (top 10):\n       dog_kennels.dogs.owner_id\n       dog_kennels.dogs.dog_id\n       dog_kennels.owners.owner_id\n       dog_kennels.owners.first_name\n       dog_kennels.dogs.age\n       dog_kennels.owners.last_name\n       dog_kennels.dogs.name\n       dog_kennels.dogs.date_of_birth\n       dog_kennels.owners.state\n\nSQL (on CRUSH retrieval using chatGPT):\nSELECT o.last_name\nFROM owners o\nJOIN (\n    SELECT owner_id\n    FROM dogs\n    WHERE age = (SELECT MIN(age) FROM dogs)\n    LIMIT 1\n) youngest_dog_owner\nON o.owner_id = youngest_dog_owner.owner_id;\n\nNote: The Hallucinated Schema aligns closely with the \"Schema Elements Needed to Write SQL.\" This facilitates more effective retrieval of relevant schema elements for constructing accurate SQL query. \n\n```\n\nExample 2:\n```\nQuestion: Give me the description of the treatment type whose total cost is the lowest.\n\nGold SQL: SELECT T1.treatment_type_description FROM Treatment_types AS T1 JOIN Treatments AS T2 ON T1.treatment_type_code  =  T2.treatment_type_code GROUP BY T1.treatment_type_code ORDER BY sum(cost_of_treatment) ASC LIMIT 1\n\nGold Database schema: \n\tBreeds(breed_code, breed_name)\n\tCharges(charge_id, charge_type, charge_amount)\n\tSizes(size_code, size_description)\n\tTreatment_Types(treatment_type_code, treatment_type_description)\n\tOwners(owner_id, first_name, last_name, street, city, state, zip_code, email_address, home_phone, cell_number)\n\tDogs(dog_id, owner_id, abandoned_yn, breed_code, size_code, name, age, date_of_birth, gender, weight, date_arrived, date_adopted, date_departed)\n\tProfessionals(professional_id, role_code, first_name, street, city, state, zip_code, last_name, email_address, home_phone, cell_number)\n\tTreatments(treatment_id, dog_id, professional_id, treatment_type_code, date_of_treatment, cost_of_treatment)\n\nSchema elements needed from Gold DB to write SQL: \n\ttreatment_types(treatment_type_code, treatment_type_description)\n\ttreatments(cost_of_treatment, treatment_type_code)\n\nHallucinated Schema: \n\ttreatment_type(description, total cost)\n\nCRUSH retrieval (top 10):\n       dog_kennels.treatments.cost_of_treatment\n       hospital_1.trained_in.treatment\n       hospital_1.procedures.cost\n       hospital_1.medication.description\n       dog_kennels.treatment_types.treatment_type_description\n       dog_kennels.treatment_types.treatment_type_code\n       dog_kennels.treatments.treatment_type_code\n       dog_kennels.treatments.treatment_id\n       dog_kennels.treatments.date_of_treatment\n       dog_kennels.treatments.professional_id\n\nSQL (on CRUSH retrieval using chatGPT):\nSELECT tt.treatment_type_description\nFROM treatment_types tt\nJOIN treatments t ON tt.treatment_type_code = t.treatment_type_code\nGROUP BY tt.treatment_type_description\nHAVING SUM(t.cost_of_treatment) = (\n    SELECT MIN(total_cost)\n    FROM (\n        SELECT SUM(cost_of_treatment) AS total_cost\n        FROM treatments\n        GROUP BY treatment_type_code\n    ) AS subquery\n);\n\n\nNote: In this example, LLM hallucinates a minimal schema which aligns with the actual schema elements needed to write SQL and thus, leads to better retrieval.\n```\n\nExample 3:\n\n```\nQuestion: How many distinct nationalities are there?\n\nGold SQL: SELECT count(DISTINCT Nationality) FROM people\n\nGold Database schema: \n\tpoker_player(Poker_Player_ID, People_ID, Final_Table_Made, Best_Finish, Money_Rank, Earnings)\n\tpeople(People_ID, Nationality, Name, Birth_Date, Height)\n\nSchema elements needed from Gold DB to write SQL: \n\tpeople(nationality)\n\nHallucinated Schema: \n\tstudents(name, nationality)\n\nCRUSH retrieval (top 10):\n       student_assessment.students.student_details\n       student_assessment.students.student_id\n       e_learning.students.student_id\n       e_learning.students.personal_name\n       e_learning.students.middle_name\n       e_learning.students.family_name\n       e_learning.students.login_name\n       student_transcripts_tracking.students.other_student_details\n       student_transcripts_tracking.students.student_id\n       student_transcripts_tracking.students.ssn\n\nSQL (on CRUSH retrieval using chatGPT):\nSELECT COUNT(DISTINCT nationality) AS distinct_nationalities\nFROM students_student_assesment;\n\nNote: Given that the question becomes vague without dbid, and so does the hallucinated schema. Based on the few-shot examples LLM generates the best possible schema, and it would be wrong to expect LLM to incorporate any information regarding 'poker_player' in the hallucinated schema based solely on the question. Finally, with this hallucinated schema, it is difficult to get 'gold schema elements needed to write SQL' in topk, which has a direct consequence on the generated SQL\n\n``` \n\n\nQ4. *Have you experimented with any techniques to make the hallucination prompts more robust and reduce reliance on gold schemas?*\\\n-> \nWe do not depend much on gold schema to design the hallucination prompts.  For example, on the Spider datasets we found that even with zero-shot prompting we  hallucinated schema that is useful in retrieving the gold schema.\n\n\nQ5. *Is there any plan to release the SocialDB benchmark to advance research in this area?*\\\n-> We plan to release the SocialDB benchmark after the anonymity period is over.\n\nQ6. *Could you discuss any challenges faced in real-world deployment or limitations compared to lab setting?*\\\n-> Unlike academic benchmarks such as SPIDER and WikiSQL, real-world text-to-SQL datasets had a significantly higher number of columns per table, column names tended to be notably longer, and there was significant overlap in the words across column names. \nFurthermore, natural language utterances or questions posed within these datasets often fail to explicitly reference the schema items. This omission occurs because the database schema is not necessarily known to the user making the inquiry. For instance, the Spider dataset's question, \"titles of films that include 'Deleted Scenes' in their special feature section,\" might be more naturally expressed as \"films with deleted scenes\" in a real-world scenario.\nAdditionally, while datasets like SPIDER are extensive and span various domains, the queries within them are generated through crowdwork. Although these queries are based on real databases, they are essentially synthetic. This introduces a notable distinction from real-world datasets, where answering questions requires a substantial amount of real-world knowledge.", "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": "- Novel technique for schema retrieval using LLM hallucination, which helps overcome lexical gaps between queries and schema.\n- Principled objective function for collective retrieval that balances coverage and connectivity.\n- Thorough experimental analysis demonstrating gains over baselines.\n- New large-schema benchmarks that enable more realistic evaluation.\n- Well-written paper that clearly explains the limitations of prior work, motivation for technical approach, and ablation studies.", "reasons_to_reject": "- The techniques are evaluated only on the authors' new benchmarks. Additional experiments on other datasets could strengthen the results.\n- The hallucination prompts are hand-designed based on gold schemas, which may limit real-world applicability. More analysis on robustness would help.", "questions_to_authors": "- Could you provide any examples of how the hallucinated schemas differ from the gold schemas? How does this affect downstream SQL accuracy?\n- Have you experimented with any techniques to make the hallucination prompts more robust and reduce reliance on gold schemas?\n- Is there any plan to release the SocialDB benchmark to advance research in this area?\n- Could you discuss any challenges faced in real-world deployment or limitations compared to lab setting?", "paper_topic_and_main_contributions": "This paper addresses the problem of retrieving relevant schema elements from a large database schema to improve text-to-SQL systems. The main contributions are:\n\n- Proposes a two-stage approach called CRUSH that first uses an LLM to hallucinate a minimal schema, then retrieves actual schema elements that collectively cover the hallucinated schema.\n- Introduces two new large-schema benchmarks for evaluating retrieval-augmented text-to-SQL: SpiderUnion (4502 columns) and SocialDB (17.8k columns).\n- Shows improved recall over baselines on these benchmarks, translating to gains in downstream SQL accuracy.\n\nThe core idea of harnessing LLM hallucination to bridge the gap between query phrases and schema elements is novel and promising. The collective optimization for high-recall retrieval is also well-motivated. The new benchmarks fill an important gap in text-to-SQL research.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a novel usage of LLMs towards efficient schema subsetting in large databases. It also introduces large benchmarks for this purpose which can be used in future work. The reviewers concur on the utility of this work. It is also noted that additional experiments for their proposed technique with benchmarks not developed by the authors themselves would enrich the paper. However, this is a minor recommended update to the existing work. I would also recommend light restucturing of the work to highlight the most important results and numbers, as that gets a little lost in this existing presentation.
Decision: Accept-Main