# Maximum Matchings via Glauber Dynamics

Anant Jindal Laxmi Niwas Mittal Institute of Information Technology, India.
<EMAIL_ADDRESS>Gazal Kochar Laxmi Niwas Mittal Institute of
Information Technology, India<EMAIL_ADDRESS>Manjish Pal Indian Institute
of Technology Gandhinagar, India<EMAIL_ADDRESS>
###### Abstract

In this paper we study the classic problem of computing a maximum cardinality
matching in general graphs $G=(V,E)$. This problem has been studied
extensively more than four decades. The best known algorithm for this problem
till date runs in $O(m\sqrt{n})$ time due to Micali and Vazirani [24]. Even
for general bipartite graphs this is the best known running time (the
algorithm of Karp and Hopcroft [16] also achieves this bound). For regular
bipartite graphs one can achieve an $O(m)$ time algorithm which, following a
series of papers, has been recently improved to $O(n\log n)$ by Goel, Kapralov
and Khanna (STOC 2010) [15]. In this paper we present a randomized algorithm
based on the Markov Chain Monte Carlo paradigm which runs in $O(m\log^{2}n)$
time, thereby obtaining a significant improvement over [24].

We use a Markov chain similar to the _hard-core model_ for Glauber Dynamics
with _fugacity_ parameter $\lambda$, which is used to sample independent sets
in a graph from the Gibbs Distribution [31], to design a faster algorithm for
finding maximum matchings in general graphs. Motivated by results which show
that in the hard-core model one can prove fast mixing times (for e.g. it is
known that for $\lambda$ less than a critical threshold the mixing time of the
hard-core model is $O(n\log n)$ [27], we define an analogous Markov chain
(depending upon a parameter $\lambda$) on the space of all possible partial
matchings of a given graph $G$, for which the probability of a particular
matching $M$ in the stationary follows the Gibbs distribution which is:

$\displaystyle\pi(M)=\frac{\lambda^{|M|}}{\sum_{x\in\Omega}\lambda^{|x|}}$

where $\Omega$ is the set of all possible matchings in $G$.

We prove upper and lower bounds on the mixing time of this Markov chain.
Although our Markov chain is essentially a simple modification of the one used
for sampling independent sets from the Gibbs distribution, their properties
are quite different. Our result crucially relies on the fact that the mixing
time of our Markov Chain is independent of $\lambda$, a significant deviation
from the recent series of works [11, 26, 28, 29, 30] which achieve
computational transition (for estimating the partition function) on a
threshold value of $\lambda$. As a result we are able to design a randomized
algorithm which runs in $O(m\log^{2}n)$ time that provides a major improvement
over the running time of the algorithm due to Micali and Vazirani. Using the
conductance bound, we also prove that mixing takes $\Omega(\frac{m}{k})$ time
where $k$ is the size of the maximum matching.

##  1 Introduction

Given an unweighted undirected graph $G=(V,E)$ with $|E|=m$ and $|V|=n$, a
matching $M$ is a set of edges belonging to $E$ such that no two edges in $M$
are incident on a vertex. If there is a matching of size $n/2$ (for $n$ even),
then it is called a _perfect matching_. The Maximum Matching problem is to
find the maximum sized matching in a given graph. The computational complexity
of this problem has been studied extensively for more than four decades
starting with an algorithm of Edmonds.

###  1.1 General Graphs

Edmonds’s celebrated paper ‘Paths, Trees and Flowers’ [9] was the first to
give an efficient algorithm (also called the _blossom shrinking algorithm_)
for finding maximum matching in general graphs. This algorithm can be
implemented in $O(n^{4})$ time. The running time was subsequently improved in
a number of papers [10, 20, 22]. All these papers were variants of Edmonds
algorithm. Even and Kariv [12] obtained an improvement to $O(n^{2.5})$ which
was improved by Micali and Vazirani [24] who gave an $O(m\sqrt{n})$ time
algorithm for the problem by a careful handling of blossoms. This is the best
known algorithm for finding maximum matchings in general bipartite graphs.

###  1.2 Bipartite Graphs

For bipartite graphs, the problem can easily be solved using the max-flow
algorithm by Ford and Fulkerson, an algorithm usually taught in an
undergraduate algorithms course [21], which has a running time of $O(mn)$. The
first algorithm for this problem was given by Konig [19]. Hopcroft and Karp
[16] gave an algorithm that runs in $O(m\sqrt{n})$ time. This algorithm is an
exact and deterministic algorithm. The problem becomes significantly simpler
for regular bipartite graphs. In a _d-regular_ bipartite graph every vertex
has degree $d$. When $d$ is a power of 2, Gabor and Kariv were able to achieve
an $O(m)$ algorithm. After significant efforts, the ideas used there were used
by Cole, Ost and Schirra [4] to obtain a get an $O(m)$ algorithm for general
$d$.

In a recent line of attack by Goel, Kapralov and Khanna [13, 14], the authors
were able to use sampling based methods to get improved running time. In the
most recent paper they were able to achieve a running time of $O(n\log n)$ for
$d$-regular graphs [15]. Their algorithm performs an appropriately truncated
random-walk on a modified graph to successively find augmenting path.

##  2 Our Results

In this paper we give a Markov Chain Monte Carlo algorithm for finding a
maximum matching in general bipartite graphs. Our algorithm is in the spirit
similar to [15] which also is a ‘truncated random walk’ based algorithm,
however the stationary distribution of the underlying Markov Chains in their
case is different from ours. Inspired from the hard-core model with fugacity
parameter $\lambda$ of sampling independent sets from graphs we define a
similar Markov Chain over the space of all possible partial matching such that
its stationary distribution $\pi(\cdot)$ is the Gibbs distribution, ie. given
a matching $M$ its probability $\pi$ is

$\displaystyle\pi(M)=\frac{\lambda^{|M|}}{\sum_{\sigma\in\Omega}\lambda^{|\sigma|}}$

where $\Omega$ is the set of all possible matchings in $G$. Notice that
$\pi(M)$ is maximum for maximum matchings and if $\lambda$ is a significantly
large number, $\pi(M)$ tends to 1 for maximum matchings. Our algorithm is
extremely simple (being a standard in the MCMC paradigm). Starting from a
fixed matching we start a random walk in $\Omega$ according to the underlying
graph $\tilde{G}$ of the Markov chain. After $T_{mix}$ (mixing time) steps the
distribution reached by the algorithm is roughly the same as the Gibbs
distribution. More formally, the variation distance of ${\cal D}^{t}$ (the
distribution after $t$ steps) from the Gibbs distribution is less than
$\frac{1}{2e}$. This just leaves the task of proving an upper-bound on the
mixing time of the Markov Chain, for which we resort to the Coupling Method
introduced by Bubley and Dyer [2]. We define a metric $\Phi(\cdot,\cdot)$ and
apply the bound from [2], to show that the Markov Chain mixes in $O(m\log n)$
time. We also use the conductance method to show that the mixing time will be
at least $\Omega(\frac{m}{k})$ where $k$ is the size of the maximum matching.
Thus upto logarithmic factors the bounds are same when $k$ is small (at most
polylogarithmic). The main result of our paper can be concisely written as
follows:

######  Theorem 1 (Main).

There exists a randomized algorithm which given a graph $G=(V,E)$ with $|V|=n$
and $|E|=m$ finds a maximum matching in $O(m\log^{2}n)$ time with high
probability.

Important remark: It has been pointed to us independently by Yuval Peres,
Jonah Sherman, Piyush Srivastava and other anonymous reviewers that the
coupling used in this paper doesn’t have the right marginals because of which
the mixing time bound doesn’t hold, and also the main result presented in the
paper. We thank them for reading the paper with interest and promptly pointing
out this mistake.

###  2.1 Organization

The paper is organized as follows: in Section 3 we give a brief description of
the basic idea and technique that are underlying our algorithm. Subsequently
in Section 4 we give an overview of the MCMC paradigm which includes basic
preliminaries and definitions regarding Markov Chain and Mixing. Section 7 is
devoted to the details of the chain being used by us and proving that indeed
it has the desired properties. We then prove upper and lower bounds on its
mixing time using the coupling method and conductance argument in Section 8
and Section 9 respectively. We end the paper with a conclusion and some open
problems.

##  3 The Idea: Maximum Matchings via Glauber Dynamics

Our ideas are inspired mainly from the results in the Glauber dynamics of the
hard-core model of fugacity parameter $\lambda$, for sampling independent sets
from the Gibbs distribution. According to the Gibbs distribution the
probability of an independent set $I$ is given by

$\displaystyle{\cal
G}(I)=\frac{\lambda^{|I|}}{\sum_{\rho\in\Omega}\lambda^{|\rho|}}$

where $\Omega$ is the set of all possible independent sets in $G$ and ${\cal
Z}=\sum_{\rho\in\Omega}\lambda^{|\rho|}$ is also called the _partition
function_. Clearly for $\lambda=1$ the partition function value is same as the
number of independent sets in the graph (computing which is a #P-Hard
problem).
In the hard-core model given a particular configuration $\sigma$ of an
independent set ($\sigma$ can be thought of an $n$-dimensional 0/1 vector
which is 1 for all the vertices which are in the independent set and 0
otherwise), we choose a vertex randomly uniformly, if this vertex is already
present in the independent set we keep it with probability
$\frac{\lambda}{1+\lambda}$ and discard it with probability
$\frac{1}{1+\lambda}$ otherwise the vertex is not in the independent set and
if this vertex can be added to the independent set (i.e. none of its neighbors
are already present in the independent set) then again it is added with with
probability $\frac{\lambda}{1+\lambda}$ and rejected with probability
$\frac{1}{1+\lambda}$. The beauty of this Markov Chain is that the stationary
distribution is the Gibbs distribution. The details of this chain can be found
in [31].

The key difference between the mixing time of Glauber Dynamics for independent
sets and our case is that one can achieve fast mixing time in the former case
only for small values of $\lambda$. In fact intuitively one should not be able
to obtain fast mixing times for large values of $\lambda$ because such a
result would imply that we can design a randomized polynomial time algorithm
for finding maximum independent set in a graph, which is an NP-Hard problem.
This intuition has led to a series of papers [11, 26, 28, 29, 30] which
ultimately has been successful in proving that there exists a threshold value
of $\lambda=\lambda_{c}$ such that if $\lambda>\lambda_{c}$ then estimating
the partition function is hard (the exact technical condition is that unless
$NP=RP$ no FPRAS exists for estimating ${\cal Z}$) and for
$\lambda<\lambda_{c}$ one can obtain an FPTAS for the same problem. Previous
to this result, the computational complexity of estimating the partition
function (and counting the number of independent sets) was only understood for
special graphs [5, 32]. Apart from these results substantial attention has
been given to obtain good bounds on the mixing time of this chain for trees
[28].

We define a Markov Chain which is tuned to our need. In our case $\sigma$ is a
set of edges which form a partial matching. We make a simple modification to
the above chain, wherein instead of picking a random vertex we pick a random
edge $e_{r}\in E$ and perform the same experiment with the parameter $\lambda$
as in the case of independent sets (notice that the chosen edge won’t be added
if in the present matching there is an edge sharing an end point with
$e_{r}$). We then show that this chain is aperiodic and irreducible with
stationary as the Gibbs distribution over the space of all possible partial
matchings with parameter $\lambda$. We then use the techniques of bounding the
mixing time to achieve a $\lambda$ independent upper bound. This remarkable
property allows us to exploit the nature of Gibbs distribution (which we
obtain for very large values of $\lambda$) without getting an overhead on the
mixing time.

###  3.1 Markov Chain Monte Carlo

Markov Chain Monte Carlo algorithms have played a significant role in
statistics, econometrics, physics and computing science over the last two
decades. For some high-dimensional problems in geometry, such as computing the
volume of a convex body in $d$ dimensions, MCMC simulation is the only known
general approach for providing a solution within time polynomial in $d$ [6].
For a number of other hard problems like approximating the permanent [18],
approximate counting [17], the only known FPRASs (_Fully Polynomial time
Randomized Approximation Schemes_) rely on the MCMC paradigm. In this paper,
we use this method to obtain a faster algorithm for the classical problem of
finding maximum matchings in general graphs, a problem which is known to be
solvable in polynomial time.
The Markov Chain Monte Carlo (MCMC) method is a simple and frequently used
approach for sampling from the Gibbs distribution of a statistical mechanical
system. The idea goes like this, we design a Markov chain whose state space is
$\Omega$ whose stationary distribution is the desired Gibbs distribution.
Starting at an arbitrary state, we simulate the Markov chain on $\Omega$ until
it is sufficiently close to its stationary distribution. We then output the
final state which is a sample from (close to) the desired distribution. The
required length of the simulation, in order to get close to the stationary
distribution, is traditionally referred to as the mixing time $\tau$ or
$T_{mix}$ and the aim is to bound the mixing time to ensure that the
simulation is efficient. For a detailed understanding of the theory of Markov
Chains we would recommend the recent excellent book by Levin, Peres and Wilmer
[23].

##  4 Preliminaries

###  4.1 Markov chains

Consider a stochastic process $(X_{t})_{t=0}^{\infty}$ on a finite state space
$\Omega$. Let P denote a non-negative matrix of size $|\Omega|\times|\Omega|$
which satisfies

$\sum_{j\epsilon\Omega}P_{ij}=1\mbox{ }\forall i\in\Omega$

The process is called a Markov chain if for all times $t$ and $i,j\in\Omega$
probability of going from $i^{th}$ state to $j^{th}$ state is independent of
the path by which $i^{th}$ state is reached i.e. if $X_{t}$ is the state of
the process at time $t$ then

$\mbox{P}[X_{t+1}|X_{t}=x_{t},X_{t-1}=x_{t-1}\dots
X_{0}=x_{0}]=\mbox{P}[X_{t+1}|X_{t}=x_{t}]$

A distribution $\pi$ is called a _stationary distribution_ if it satisfies
$\pi P=\pi$. A necessary and sufficient condition for a chain to have a unique
stationary distribution is that the chain is

  * 1.

_Irreducible_ : for all $i,j\in\Omega$ there exists a time $t$ such that
$P^{t}_{ij}>$ 0; and

  * 2.

_Aperiodic_ : for all $i\in\Omega$, GCD {$t:P^{t}_{ii}>$ 0} = 1.

A Markov Chain which has both of the above properties is called _ergodic_. For
an ergodic Markov chain, if a distribution $\pi$ satisfies the detailed
balance equations

$\pi_{i}P_{ij}=\pi_{j}P_{ji}$

for all $i,j\in\Omega$ then $\pi$ is the (unique) stationary distribution and
such a chain is called _reversible_.

###  4.2 Mixing Time

The notion of mixing time is defined as a way to measure the closeness of the
distribution after $t$ steps w.r.t. the stationary distribution. The total
variation distance between two discrete probability distributions over a
finite space $\Omega$ is defined as the half of the $l_{1}$ norm of the
corresponding probability vectors.

$d_{TV}(\mu,\nu)=\frac{1}{2}\sum_{\omega\in\Omega}|\mu(\omega)-\nu(\omega)|$

If $P_{t}$ is the probability distribution after $t$ steps in the random walk
then $T_{mix}$ is the minimum $t$ for which,

$d_{TV}(P_{t},\pi)\leq\frac{1}{2e}$

where $\pi$ is the stationary distribution. Therefore, if we intend to get
close to a stationary distribution we just have to truncate the random walk on
the state space after $\tau$ steps.

###  4.3 Conductance

The conductance of a Markov chain is defined as the following quantity,

$\phi(G)=\displaystyle\min_{S\subset V}\frac{\sum_{i\in
S,j\in\bar{S}}\pi_{i}p_{ij}}{(\sum_{i\in
S}\pi_{i})(\sum_{i\in\bar{S}}\pi_{i})}$

Another quantity of our interest here is $T_{relax}$, the _relaxation time_ of
the Markov chain. $T_{relax}$ is defined as the inverse of conductance i.e.
$T_{relax}=\frac{1}{\phi(G)}$. It is known that $T_{mix}$ and $T_{relax}$ obey
the following inequality [1].

$T_{relax}+1\leq T_{mix}.$

Also it is known [28] that

$\displaystyle T_{relax}=\Omega\left(\frac{1}{\phi}\right),$

a bound usually used to prove lower bounds on the Mixing time of Markov
Chains.

##  5 The Chain

In this section, we describe the chain considered by our algorithm which is
essentially a modification of the hard-core model of Glauber Dynamics. Recall
that our objective is to come up with a chain whose stationary distribution
ensures that the probability of being at a maximum matching is the largest.
Recall that first we need to ensure that our chain is aperiodic and
irreducible.

We use the following natural modification of the Markov chain for the hard-
core model of Glauber dynamics.

  * •

Choose an edge $e_{r}$ uniformly at random from $E$.

  * •

Let

$\sigma^{\prime}=\begin{cases}\sigma\bigcup\\{e_{r}\\},&\text{with
probability}\frac{\lambda}{1+\lambda}\\\
\sigma\backslash\\{e_{r}\\},&\text{with
probability}\frac{1}{1+\lambda}\end{cases}$

  * •

If $\sigma^{\prime}$ is a valid matching, move to state $\sigma^{\prime}$
otherwise remain at state $\sigma$.

We are now prepared to prove that this is a valid Markov Chain with stationary
as the Gibbs distribution, where we define Gibbs distribution as the following
distribution over the set of all possible matchings $\Omega$ as

$\displaystyle{\cal
G}(M)=\frac{\lambda^{|M|}}{\sum_{x\in\Omega}\lambda^{|x|}}$

In the rest, we will call $Z=\sum_{x\in\Omega}\lambda^{|x|}$.

######  Lemma 1.

$X_{t}$ is ergodic with stationary distribution as $\cal G$.

###### Proof.

Since for every state there is some probability by which the walk can remain
in the same state, the chain is aperiodic. Also the underlying graph is
connected because given any matching there is a at least one path to reach any
other matching (consider the path that first drops all the edges of the
initial matching and adds the edges of the new matching one by one).
To show that the stationary of this distribution is $\cal G$, we would show
that the chain is reversible w.r.t. $\cal G$. Consider two distinct states $i$
and $j$ in the Markov Chain. Assume w.l.o.g that there is an edge from $i$ to
$j$ (if there is no edge from $i$ to $j$ then the balance equations
corresponding to $i$ and $j$ are trivially satisfied). Let the configuration
$i$ has $t$ edges in it then according to our construction, $j$ will have
either $t+1$ or $t-1$ states (it won’t be $t$ because we have assumed that the
two states are distinct). We will just look at the case when $j$ has $t+1$
edges, the other case is analogous. Since we are interested in showing
reversibility w.r.t. $\cal G$, $\pi_{i}=\frac{\lambda^{t}}{Z}$ and
$\pi_{j}=\frac{\lambda^{t+1}}{Z}$. Therefore,
$\pi_{i}P_{ij}=\frac{\lambda^{t}}{Z}\cdot\frac{\lambda}{m(1+\lambda)}$, and
$\pi_{j}P_{ji}=\frac{\lambda^{t+1}}{Z}\cdot\frac{1}{m(1+\lambda)}$. Thus
$\pi_{i}P_{ij}=\pi_{j}P_{ji}=\frac{\lambda^{t+1}}{mZ(1+\lambda)}$

∎

##  6 Upper Bound using Coupling

In this section we prove an upper bound on $T_{mix}$ of the chain defined in
the previous section. Our bound is based on the coupling argument introduced
by Bubley and Dyer [2]. We first give a description of the coupling method.

###  6.1  Coupling Method

A coupling of a Markov chain on state space is a stochastic process
$(\sigma_{t},\eta_{t})$ on $|\Omega|\times|\Omega|$ such that:

  * •

$\sigma_{t}$ and $\eta_{t}$ are copies of the original Markov chain and

  * •

if $\sigma_{t}=\eta_{t}$, then $\sigma_{t+1}=\eta_{t+1}$

Thus the chains follow each other after the first instant when they hit each
other. In order to measure the distance between the two copies of the chain,
one introduces a distance function $\Phi$ on the product state space
$\Omega\times\Omega$ so that
$\Phi=\Phi(\sigma_{t},\eta_{t})=0\Longleftrightarrow\sigma_{t}=\eta_{t}$. For
two states $\sigma$ and $\eta$ let $\rho(\sigma,\eta)$ be the set of all paths
from $\sigma$ to $\eta$ in the Markov Chain. The following theorem due to to
Bubley and Dyer is used to prove mixing time on Markov chain.

######  Theorem 2.

Let $\Phi$ be an integer-valued metric defined on $\Omega\times\Omega$ which
takes values in {0,1…D} such that, for all $\sigma,\eta\in\Omega$ there exists
a path $\xi\in\rho(\sigma,\eta)$ with

$\displaystyle\Phi(\sigma,\eta)=\sum_{i}\Phi(\xi^{i},\xi^{i+1})$

Suppose there exists a constant $\beta<$1 and a coupling
$(\sigma_{t},\eta_{t})$ of the Markov chain such that, for all
$\sigma_{t},\eta_{t}$,

$\displaystyle
E[\Phi(\sigma_{t+1},\eta_{t+1})]\leq\beta\Phi(\sigma_{t},\eta_{t})$

Then the mixing time is bounded by

$\displaystyle\tau\leq\frac{\log(2eD)}{1-\beta}$

###### Proof.

Can be found in [2, 31]. ∎

In order to bound the mixing time, we will define a coupling so as to minimize
the time until both copies of the Markov chain reach the same state, and we
will do that by defining the coupling in such a way that on every step both
markov chains reach towards same state. The aim is to prove a good upper bound
on $E[\Phi(\sigma_{t+1},\eta_{t+1})]$ in terms of $\Phi(\sigma_{t},\eta_{t})$.
In the following subsection we define the coupling:

####  6.1.1 Coupling

Consider the following process $(\sigma_{t},\eta_{t})$ on
$|\Omega|\times|\Omega|$ where $\Omega$ is the space of all possible
matchings.

######  Definition 1.

Choose an edge uniformly at random,

  * 1.

If insertion is possible in both $\sigma$ and $\eta$ then add it probability
$\frac{\lambda}{1+\lambda}$ and remove it with probability
$\frac{1}{1+\lambda}$.

  * 2.

If insertion is possible in one and not possible in the other then remove that
edge if it is already present in one matching.

Notice that here we are relying on the fact that one can insert an edge if it
is already present in it. It is easy to verify that this indeed is a coupling
for the Markov chain defined in the previous section.

We use the following distance function for the aforementioned coupling. Let

$\sigma\oplus\eta=\left\\{e\in
E|e\in\left((\sigma\setminus\eta)\bigcup(\eta\setminus\sigma)\right)\right\\}\mbox{
where }\sigma\mbox{ and }\eta\in\Omega$

define the distance function $\Phi(\sigma_{t},\eta_{t})=|\sigma\oplus\eta|$
which is the number of edges present in one but not in the other. Our
objective is to upper-bound $E[\Phi_{(}\sigma_{t+1},\eta_{t+1})]$ in terms of
$d_{t}=\Phi(\sigma_{t},\eta_{t})$. Based on the definition of our coupling the
following cases may arise once we pick an edge $e_{r}$ uniformly randomly:

  * 1.

$e_{r}$ can be added to both $\sigma_{t}$ and $\eta_{t}$: The subevents are
(a) $e_{r}$ was present in both of them, in this case
$\Phi(\sigma_{t+1},\eta_{t+1})=d_{t}$, (b) $e_{r}$ is not present in both of
them, in which case again $\Phi(\sigma_{t+1},\eta_{t+1})=d_{t}$ and (c)
$e_{r}$ is present in one but not in other, in which case
$\Phi(\sigma_{t+1},\eta_{t+1})=d_{t}-1$.

  * 2.

$e_{r}$ can be added in exactly one of $\sigma_{t}$ and $\eta_{t}$: The sub
events for this case are (a) $e_{r}$ is not present in both, which gives
$\Phi(\sigma_{t+1},\eta_{t+1})=d_{t}$ (b)$e_{r}$ is present in one matching
and not in other, in which case $\Phi(\sigma_{t+1},\eta_{t+1})=d_{t}-1$

  * 3.

$e_{r}$ can’t be added to any one of $\sigma_{t}$ and $\eta_{t}$: In this case
$\Phi(\sigma_{t+1},\eta_{t+1})=d_{t}$.

Using the above events we can prove the following:

######  Lemma 2.

$\displaystyle
E[\Phi(\sigma_{t+1},\eta_{t+1})]=\Phi(\sigma_{t},\eta_{t})\left(1-\frac{1}{m}\right)$.

###### Proof.

Since $\Phi(\sigma_{t+1},\eta_{t+1})$ can only take two values either $d$ or
$d-1$ we only need to calculate the the probability of the happening of one of
these cases. This happens when either the event 1(c) or the event 2(b) takes
place (as mentioned above). Thus,

$\mbox{{Pr}}[\Phi(\sigma_{t+1},\eta_{t+1})=d_{t}-1]=\mbox{{Pr}}[1(c)\cup
2(b)]$

clearly the distance becomes $d_{t}-1$ when the chosen edge is one of the
edges in $\sigma\oplus\eta$. We can divide $\sigma\oplus\eta$ in to two sets
$U$ and $\bar{U}$. $U$ is the set of edges which can be added to the matching
in which it is not present, and $\bar{U}$ is the set of edge which can’t be
added to the matching in which it is not present. Using this notation we can
write the desired probability as

$\displaystyle\displaystyle\mbox{{Pr}}[1(c)\cup 2(b)]$ $\displaystyle=$
$\displaystyle\sum_{e\in
U}\frac{1}{m}\left(\frac{\lambda}{1+\lambda}+\frac{1}{1+\lambda}\right)+\sum_{e\in\bar{U}}\frac{1}{m}$
$\displaystyle=$
$\displaystyle\frac{|\sigma\oplus\eta|}{m}=\frac{\Phi(\sigma_{t},\eta_{t})}{m}$

Therefore,

$\displaystyle\displaystyle E[\Phi(\sigma_{t+1},\eta_{t+1})]$ $\displaystyle=$
$\displaystyle(d_{t}-1)\frac{\Phi(\sigma_{t},\eta_{t})}{m}+d_{t}\left(1-\frac{\Phi(\sigma_{t},\eta_{t})}{m}\right)$
$\displaystyle=$
$\displaystyle\Phi(\sigma_{t},\eta_{t})\left(1-\frac{1}{m}\right)(\mbox{ since
}d_{t}=\Phi(\sigma_{t},\eta_{t}))$

∎

We can now prove the following:

######  Lemma 3.

$T_{mix}=O(m\log n)$.

###### Proof.

Given any $\sigma$ and $\eta$ we define a $d=\Phi(\sigma,\eta)$ length path as
$\sigma=\xi^{1},\xi^{2}\dots,\xi^{d}=\eta$ such that $\xi^{i+1}$ is the state
obtained by removing exactly one edge from
$\xi^{i}\in\sigma\bigcap(\sigma\oplus\eta)$ for $i=1,2\dots j$ where $\xi^{j}$
consists only of edges which do not belong to $\sigma\oplus\eta$ and for all
$k\geq j$, $\xi^{k+1}$ is obtained by adding one edge to $\xi^{k}$ which
belongs to $\eta\bigcap(\sigma\oplus\eta)$. Since $\xi^{i},\xi^{i+1}=1$ for
all $i=1,2\dots d-1$, we have

$\displaystyle\Phi(\sigma,\eta)=\sum_{i}\Phi(\xi^{i},\xi^{i+1})$

Also we can write

$E[\Phi(\sigma_{t+1},\eta_{t+1})]=\beta\Phi(\sigma_{t},\eta_{t})(\mbox{ with
}\beta=\left(1-\frac{1}{m}\right))$

this allows us to apply the result from Theorem 2 which gives the following
result

$\displaystyle T_{mix}\leq\frac{\log 2eD}{\displaystyle
1-\left(1-\frac{1}{m}\right)}\leq m\log(4en)=O(m\log n)$

where we have used $\beta=(1-1/m)$ and $D=2n$. ∎

Our algorithm is concisely presented as follows:

Input: A Graph $G=(V,E)$ with $|V|=n$ and $|E|=m$

$\sigma_{0}\leftarrow anymatching$;

$\lambda=2^{m}$;

for  _$t=0$ _to_ $10m\log n$_ do

choose an edge $e_{r}$ uniformly randomly ;

$\sigma^{\prime}=\begin{cases}\sigma_{t}\bigcup\\{e_{r}\\},&\text{with
probability}\frac{\lambda}{1+\lambda}\\\
\sigma_{t}\backslash\\{e_{r}\\},&\text{with
probability}\frac{1}{1+\lambda}\end{cases}$;

if $\sigma^{\prime}$ is a valid matching;

$\sigma_{t+1}=\sigma^{\prime}$;

else;

$\sigma_{t+1}=\sigma_{t}$;

end for

return _$\sigma_{t}$_

Algorithm 1 RandMatching

######  Theorem 3.

The probability that the random walk in Algorithm 1 ends on a maximum matching
is at least $\frac{20}{189}$.

###### Proof.

Let ${\cal M}_{i}$ be the set all of matchings of size $i$ (and $S_{i}$ be its
cardinality) in the given graph. Also, let $k$ be the size of the maximum
matching. We need to find the probability that the random walk lands up on a
maximum matching after $T=10m\log n\geq T_{mix}$ steps. Let $X_{T}$ be the
state after $T$ steps, and $\pi_{T}$ be the probability distribution after $T$
steps then by definition of mixing time and triangle inequality,

$\displaystyle\left|\sum_{\omega\in{\cal
M}_{k}}\pi_{T}(\omega)-\sum_{\omega\in{\cal M}_{k}}{\cal
G}(\omega)\right|\leq\sum_{\omega\in{\cal M}_{k}}|\pi_{T}(\omega)-{\cal
G}(\omega)|\leq\sum_{\omega\in\Omega}|\pi_{T}(\omega)-{\cal
G}(\omega)|\leq\frac{1}{e}$

where $\sum_{\omega\in{\cal M}_{k}}\pi_{T}(\omega):=\mbox{Pr}_{k}(\pi_{T})$ is
the probability of reaching a maximum matching after $T$ steps (the success
probability of the algorithm) and $\sum_{\omega\in{\cal M}_{k}}{\cal
G}(\omega):=\mbox{Pr}_{k}({\cal G})$ is the probability of finding a maximum
matching according to the Gibbs distribution. We need to find the probability
that $X_{T}$ is a maximum matching. Thus we have,

$\mbox{Pr}_{k}(\pi_{T})\in\left[\mbox{Pr}_{k}({\cal
G})-\frac{1}{e},\mbox{Pr}_{k}({\cal G})+\frac{1}{e}\right]$

Also,

$\displaystyle\mbox{Pr}_{k}({\cal G})$ $\displaystyle=$
$\displaystyle\frac{\lambda^{k}S_{k}}{\displaystyle\sum_{i=0}^{k}\lambda^{i}S_{i}}$
$\displaystyle=$
$\displaystyle\frac{\lambda^{k}S_{k}}{\displaystyle\lambda^{k}S_{k}+\lambda^{k-1}S_{k-1}+\lambda^{k-2}S_{k-2}+\dots+S_{0}}$

dividing by $\lambda^{k}$ both numerator and denominator

$\displaystyle=$ $\displaystyle\frac{S_{k}}{S_{k}+\frac{\displaystyle
S_{k-1}}{\lambda}+\frac{S_{k-2}}{\lambda^{2}}+...+\frac{S_{0}}{\lambda^{k}}}$

We put $\lambda=S_{m}$ where $S_{m}$=$\displaystyle\max_{i}^{k}S_{i}$

$\displaystyle=$ $\displaystyle\frac{S_{k}}{\displaystyle
S_{k}+\frac{S_{k-1}}{S_{m}}+\frac{S_{k-2}}{S_{m}^{2}}+\dots+\frac{S_{0}}{S_{m}^{k}}}=\frac{1}{\displaystyle
1+\frac{S_{k-1}}{S_{k}S_{m}}+\frac{S_{k-2}}{S_{k}S_{m}^{2}}+\dots+\frac{S_{0}}{S_{k}S_{m}^{k}}}$

By definition of $S_{m}$, $\frac{S_{i}}{S_{m}}$ is always $\leq 1$, hence we
have

$\displaystyle\frac{1}{\displaystyle
1+\frac{S_{k-1}}{S_{k}S_{m}}+\frac{S_{k-2}}{S_{k}S_{m}^{2}}+\dots+\frac{S_{0}}{S_{k}S_{m}^{k}}}$
$\displaystyle\geq$ $\displaystyle\frac{1}{\displaystyle
1+\frac{1}{S_{k}}+\frac{1}{S_{k}S_{m}}+\frac{1}{S_{k}S_{m}^{2}}...+\frac{1}{S_{k}S_{m}^{k-1}}}$
$\displaystyle\geq$ $\displaystyle\frac{1}{\displaystyle
1+\frac{1}{S_{k}}\left(1+\frac{1}{S_{m}}+\frac{1}{S_{m}^{2}}\dots+\frac{1}{S_{m}^{k-1}}\right)}$
$\displaystyle\geq$ $\displaystyle\frac{1}{\displaystyle
1+\frac{1}{S_{k}}\left(\frac{1-\left(\frac{1}{S_{m}}\right)^{k}}{1-\frac{1}{S_{m}}}\right)}$
$\displaystyle\geq$ $\displaystyle\frac{1}{\displaystyle
1+\frac{1}{S_{k}}\left(\frac{S_{m}^{k}-1}{S_{m}^{k-1}(S_{m}-1)}\right)}$

Since

$\displaystyle\displaystyle\left(\frac{S_{m}^{k}-1}{S_{m}^{k-1}(S_{m}-1)}\right)$
$\displaystyle=$
$\displaystyle\left(1+\frac{S_{m}^{k-1}-1}{S_{m}^{k-1}(S_{m}-1)}\right)=1+\Theta\displaystyle\left(\frac{1}{S_{m}}\right)\leq\frac{11}{10}$
$\displaystyle\mbox{Pr}_{k}({\cal G})$ $\displaystyle\geq$
$\displaystyle\frac{1}{1+\frac{1}{\displaystyle\frac{11S_{k}}{10}}}\geq\frac{10}{21}$

This gives us,

$\mbox{Pr}_{k}(\pi_{T})\geq\frac{10}{21}-\frac{1}{e}\geq\frac{20}{189}$

∎

Notice that our proof still goes through even if we choose a $\lambda$ that is
larger than $S_{m}$ (we can take $\lambda=2^{m}$). Therefore $\lambda$ can be
represented using $m$ bits. We can now prove the main theorem,

######  Theorem 4.

Given a graph $G=(V,E)$ with $|V|=n$ and $|E|=m$, there exists a randomized
algorithm that runs in $O(m\log^{2}n)$ time and finds a maximum matching with
high probability.

###### Proof.

Each step of the algorithm runs in $O(1)$ time (we just need to maintain an
array which indicates whether the $i^{th}$ vertex is occupied in the matching
or not), thus one call of Algorithm 1 runs in $O(m\log n)$ time which by
Theorem 3 lands on a maximum matching with probability $\frac{20}{169}$. Thus
calling it $10\log n$ times independently, ensures that we land on a maximum
matching in one call is at least $1-\left(\frac{169}{189}\right)^{10\log
n}=1-\frac{1}{n^{\Omega(1)}}$. ∎

##  7 Lower Bound via Conductance

The conductance method as defined in the Section is used to obtain lower
bounds on the mixing time of the a Markov chain. To get a lower bound on
$T_{relax}$ we need an upper-bound on $\phi$, and by definition of $\phi$, for
any cut $(S,\bar{S})$.

$\phi\leq\displaystyle\left(\frac{\sum_{i\in
S,j\in\bar{S}}\pi_{i}P_{ij}}{(\sum_{i\in
S}\pi_{i})(\sum_{i\in\bar{S}}\pi_{i})}\right)$

This allows us to observe:

######  Lemma 4.

For any graph $G$, the conductance of our Markov Chain satisfies

$\phi\leq O\left(\frac{k}{m}\right)$

where $k$ is the size of maximum matching.

###### Proof.

To give an upper bound on conductance we need to construct a cut $(S,\bar{S})$
for which we can estimate the above quantity. Let $S$ be consisting of exactly
one matching which is the maximum matching $m_{k}$ where $k$ is the size of
the maximum matching. Thus the number of edges going out of $S$ is $k$.

$\displaystyle\frac{\sum_{i\in S,j\in\bar{S}}\pi_{i}P_{ij}}{(\sum_{i\in
S}\pi_{i})(\sum_{i\in\bar{S}}\pi_{i})}=\frac{\frac{\lambda^{k}}{Z}\cdot
k\cdot\frac{1}{m(\lambda+1)}}{\frac{\lambda^{k}}{Z}\left(1-\frac{\lambda^{k}}{Z}\right)}=\frac{k}{(1+\lambda)m}\cdot\frac{1}{\left(1-\frac{\lambda^{k}}{Z}\right)}$

Also using the terminology of Theorem 3

$\displaystyle\displaystyle\frac{\lambda^{k}}{Z}=\frac{\lambda^{k}}{\sum_{i=0}^{k}S_{i}\lambda^{i}}=\frac{1}{\sum_{i=0}^{k}S_{k-i}\frac{1}{\lambda^{i}}}\leq\frac{1}{\sum_{i=0}^{k}\frac{1}{\lambda^{i}}}=\frac{\lambda^{k}(\lambda-1)}{\lambda^{k+1}-1}=1-\Theta\left(\frac{1}{\lambda}\right)$

Therefore,

$\displaystyle\frac{\sum_{i\in S,j\in\bar{S}}\pi_{i}P_{ij}}{(\sum_{i\in
S}\pi_{i})(\sum_{i\in\bar{S}}\pi_{i})}=\frac{k}{(1+\lambda)m}\cdot\frac{1}{\Theta\left(\frac{1}{\lambda}\right)}=\Theta\left(\frac{k}{m}\right)$

Thus the result follows. ∎

As a result of the previous lemma we have the following result.

######  Lemma 5.

For any graph $G$, the mixing time of our Markov chain satisfies,
$T_{mix}\geq\Omega\left(\frac{m}{k}\right)$

###### Proof.

Follows from results in Section 4.3. ∎

Thus the lower bound is sharp (upto logarithmic factors) if the size of the
matching in the given graph is small (say at most $O(\mbox{poly}\log n)$).

A Note on Other methods to prove Lower Bound: There are other methods, apart
from conductance, which can be used to prove lower bounds on mixing time.
Although powerful and useful in many contexts, it is not clear whether such
methods could be applied to our chain. For eg. the Wilson’s method [1] expects
the knowledge of one eigenvector of the transition vector that is different
from the all 1’s vector and the corresponding eigenvalue lies in the range
$\left(0,\frac{1}{2}\right)$. Since the matrix $P$ for our case is an
exponential sized matrix with apparently no useful pattern in the entries, it
is not clear how to come up with such an eigenvector. In fact, we made several
educated guesses for coming up with such a vector all of which failed to serve
our purpose.

##  8 Conclusion

In this paper, we gave a new randomized algorithm for finding maximum
matchings in general bipartite graphs that runs in $O(m\log^{2}n)$ time that
improves upon the running time of Micali and Vazirani. Our algorithm was based
on the MCMC paradigm which performs a truncated random walk on the Markov
Chain defined by the Glauber Dynamics with parameter $\lambda$. Apart from the
benefit of being very simple (both in analysis and implementation) our
algorithm is the first near linear time complexity algorithm for the maximum
matching problem for general graphs. Moreover, unlike [15] the running time of
our algorithm is not a random variable.

To our knowledge this is for the first time Glauber dynamics and the nature of
Gibbs distribution has been exploited to design an faster algorithm for a
problem for which efficient solutions are already known, and we hope this idea
can be of use in other problems as well. The obvious open problem will be to
improve both the upper-bounds and lower bounds on the mixing time. Is it
possible to improve upon the present bound to get an $O(m)$ time algorithm?
Also one can explore the possibility of proving a tighter lower bound of
$\Omega(m)$ by using more refined techniques. More specifically, it would be
interesting to see if one can obtain an explicit eigenvector of the transition
matrix $P$ (that is different from all 1’s vector) and apply Wilson’s to get
an improved lower bound on the mixing time.

##  9 Acknowledgements

Manjish Pal would like to thank Eric Vigoda for answering his mails about the
Gibbs distribution. Thanks to Purushottam Kar for his feedback on the
presentation of the paper.

## References

  * [1] N. Berestycki, Eight lectures on Mixing Times, 2009.
  * [2] R. Bubley and M.E. Dyer, Path coupling, Dobrushin uniqueness, and approximate counting, 38th Annual Symposium on Foundations of Computer Science, IEEE, 1997.
  * [3] R. Cole and J.E. Hopcroft, On edge coloring bipartite graphs, SIAM J. Comput., 11(3), 1982, pp. 540-546.
  * [4] R. Cole, K. Ost, and S. Schirra, Edge-coloring bipartite multigraphs in $O(E\log D)$ time, Combinatorica, 21(1), 2001, pp. 5-12.
  * [5] M. Dyer, A. Frieze and M. Jerrum, On Counting Independent Sets In Sparse Graphs, SIAM Journal on Computing 31(5), 2001, pp. 1527-1541.
  * [6] M. Dyer, A. Frieze and R. Kannan, A random polynomial time algorithm for approximating the volume of convex sets, Journal of the Association for Computing Machinery, 38,1991, pp. 1-17.
  * [7] M. Dyer and C. Greenhill, On Markov chains for independent sets, Journal of Algorithms 35(1) 2000, pp. 17-49.
  * [8] M. Dyer, L. A. Goldberg and M. Jerrum, Markov chain comparison, Probability Surveys Vol. 3, 2006, pp. 89 111.
  * [9] J. Edmonds, Paths, Trees and Flowers, Canadian J. 1965, pp. 449-467
  * [10] H. Gabow, Implementation of Algorithms for Maximum Matching of Graphs, PhD Thesis, 1973
  * [11] A. Galanis, Q. Ge, D. Stefankovic, E. Vigoda and L. Yang., Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model, arXiv:1105.5131v1 , 2011.
  * [12] H.N. Gabow and O. Kariv, Algorithms for edge coloring bipartite graphs and multigraphs, SIAM J. Comput., 11(1), 1982, pp. 117 129.
  * [13] A. Goel, M. Kapralov, and S. Khanna, Perfect matchings via uniform sampling in regular bipartite graphs, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, 2009, pp. 11-17.
  * [14] A. Goel, M. Kapralov, and S. Khanna, Perfect matchings in $O(n^{1.5})$ time in regular bipartite graphs., arXiv:0902.1617v2, 2009.
  * [15] A. Goel, M. Kapralov, and S. Khanna, Perfect Matchings in $O(n\log n)$ Time in Regular Bipartite Graphs, STOC, 2010.
  * [16] J.E. Hopcroft and R.M. Karp, An $n^{\frac{5}{2}}$ algorithm for maximum matchings in bipartite graphs, SIAM J.Comput., 2(4),1973, pp. 225-231.
  * [17] Mark Jerrum and Alistair Sinclair, The Markov chain Monte Carlo method: an approach to approximate counting and integration , ”Approximation Algorithms for NP-hard Problems,” D.S.Hochbaum ed., PWS Publishing, Boston, 1996.
  * [18] M.R. Jerrum and A.J. Sinclair, Approximating the permanent, SIAM Journal on Computing, 1989 vol. 18, pp.1149 1178.
  * [19] D. K$\ddot{o}$nig, Uber graphen und ihre anwendung auf determinententheorie und mengenlehre, Math. Annalen, 77,1916, pp. 453-465.
  * [20] T. Kameda and I. Munro, A $O(|V|\cdot|E|)$ Algorithm for Maximum Matchings of Graphs, Computing, vol.12, pp. 91-98, 1974.
  * [21] R. Kleinberg and Eva Tardos, Algorithm Design, Addison Wesley, 2005.
  * [22] E.G. Lawler, Combinatorial Optimization Theory, Holt, Rinehart and Winston, Chapter 6, pp. 217-239, 1976.
  * [23] D. A. Levin, Y. Peres, E. Wilmer, Markov Chains and Mixing Times, American Mathematical Society, 2009.
  * [24] S. Micali and V. V. Vazirani, An $O(|E|\sqrt{|V|})$ time Algorithm for Maximum Matchings, FOCS, 1980, pp.17-27.
  * [25] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
  * [26] E. Mossel, D. Weitz and N. Wormald, On the hardness of sampling independent sets beyond the tree threshold, Probability Theory and Related Fields, 2009 vol. 143, no. 3-4, pp. 401-439.
  * [27] F. Martinelli, A. Sinclair and D. Weitz, Fast mixing for independent sets, colorings and other models on trees, SODA, 2004, pp. 456-465
  * [28] R. Restrepo, D. Stefankovic, J.C. Vera, E. Vigoda and L. Yang, Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees, arXiv:1007.2255v1, 2010.
  * [29] A. Sly, Computational Transition at the Uniqueness Threshold, FOCS, 2010, pp. 287-296.
  * [30] D. Weitz, Counting independent sets up to the tree threshold, STOC, 2006, pp. 140-149.
  * [31] E. J.Vigoda, Sampling from Gibbs distributions, 1999, Phd Thesis.
  * [32] S. Vadhan, The Complexity of Counting in Sparse, Regular, and Planar Graphs, SIAM Journal on Computing 31(2),2001, pp. 398-427.


# A comprehensive evaluation of ChatGPT’s zero-shot Text-to-SQL capability

Aiwei Liu1, Xuming Hu1, Lijie Wen1, Philip S. Yu1,2
1Tsinghua University
2University of Illinois at Chicago
1{liuaw20<EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

This paper presents the first comprehensive analysis of ChatGPT’s Text-to-SQL
ability. Given the recent emergence of large-scale conversational language
model ChatGPT and its impressive capabilities in both conversational abilities
and code generation, we sought to evaluate its Text-to-SQL performance. We
conducted experiments on 12 benchmark datasets with different languages,
settings, or scenarios, and the results demonstrate that ChatGPT has strong
text-to-SQL abilities. Although there is still a gap from the current state-
of-the-art (SOTA) model performance, considering that the experiment was
conducted in a zero-shot scenario, ChatGPT’s performance is still impressive.
Notably, in the ADVETA (RPL) scenario, the zero-shot ChatGPT even outperforms
the SOTA model that requires fine-tuning on the Spider dataset by 4.1%,
demonstrating its potential for use in practical applications. To support
further research in related fields, we have made the data generated by ChatGPT
publicly available at https://github.com/THU-BPM/chatgpt-sql.

##  1 Introduction

With the increasing attention given to large-scale language models, they have
become an essential component in natural language processing. As the size of
pre-trained models grows, their usage is also gradually changing. Different
from models such as BERT Devlin et al. (2018) and T5 Raffel et al. (2020),
which require fine-tuning with a small amount of data, models such as GPT-3
Brown et al. (2020), require the prompt design to generate target outputs. The
recent ChatGPT111https://chat.openai.com/ model, which employs Reinforcement
Learning for Human Feedback (RLHF) Christiano et al. (2017), simplifies prompt
design, enabling better utilization of the zero-shot ability of large-scale
pre-trained models in a conversational way. Based on this, many works have
begun to analyze the zero-shot ability of ChatGPT in various natural language
processing tasks, such as information extraction Wei et al. (2023), text
summarization Wang et al. (2023), and mathematical abilities Frieder et al.
(2023). Due to ChatGPT’s strong ability in code generation and the fact that
code generation models usually require a large amount of annotated data to
produce good results, a zero-shot code generation model is very important.
This paper first conducts a comprehensive evaluation of ChatGPT’s zero-shot
performance on a challenging code generation task: Text-to-SQL.

The Text-to-SQL task involves converting user input text into SQL statements
that can be executed on a database, allowing non-expert users to better access
the contents of a database. The design of Text-to-SQL models is typically
challenging because they need to work across different databases and consider
various user text input text and database structures. Due to the complexity of
the Text-to-SQL task, a comprehensive evaluation of its performance requires
consideration of a variety of scenarios in addition to the classic Spider
dataset Yu et al. (2018). For example, Spider-SYN Gan et al. (2021a) focuses
on scenarios where the data schema mentioned in the user text input is
synonymous with the database schema, Spider-DK Gan et al. (2021b) considers
scenarios where the input question contains additional knowledge, Spider-CG
Gan et al. (2022) emphasizes the combination generalization ability of models,
and ADVETA Pi et al. (2022) considers scenarios where column names in the
database have been modified. Additionally, to better reflect real-world
scenarios, SParCYu et al. (2019b) and CoSQL Yu et al. (2019a) incorporate
multi-turn interaction between the user and the system. Finally, to evaluate
models’ multilingual capabilities, CSpider Min et al. (2019) and DuSQL Wang et
al. (2020) evaluate Text-to-SQL performance in Chinese.

During our experiments, we evaluate the ability of ChatGPT on 12 different
Text-to-SQL benchmark datasets. Based on the experimental results, we conclude
the following observations:

  1. 1.

Compared to the current state-of-the-art (SOTA) model that uses complete
training data, ChatGPT without using task-specific training data only performs
14% worse. This already demonstrates that ChatGPT is a strong zero-shot Text-
to-SQL converter.

  2. 2.

The robustness of ChatGPT in generating SQL statements is very strong, and the
performance gap between ChatGPT and the SOTA models is only 7.8% on some
robustness settings of the Spider dataset, which is lower than the 14% gap on
the standard Spider dataset.

  3. 3.

In the ADVETA Pi et al. (2022) scenario where the column names in the database
are adversarially modified, ChatGPT’s performance even surpasses that of the
current SOTA models by 4.1%.

  4. 4.

The Exact Match metric of the data generated by ChatGPT is very low because
there are many different ways to express SQLs with the same purpose.
Therefore, we mainly use execution accuracy as the evaluation metric.

Overall, our experiments demonstrate that ChatGPT has strong Text-to-SQL
capabilities and robustness, and it outperforms SOTA models in certain
scenarios.

##  2 Method

Figure 1: Example prompts for Text-to-SQL using ChatGPT. The prompt at the top
is for a single-turn scenario, while the one below is for multi-turn scenarios
where only new questions are added in each interaction.

In order to enable ChatGPT to generate accurate SQL outputs, we utilized the
prompt as shown in Figure 1. To ensure a fair demonstration of ChatGPT’s Text-
to-SQL capabilities, we directly adopted the Text-to-SQL prompt used in the
OpenAI demo webwite222https://platform.openai.com/examples/default-sql-
translate without conducting further prompt exploration.

The upper half of Figure 1 represents the prompt in a single-turn Text-to-SQL
scenario, where only the database and question information is required in the
prompt. Meanwhile, in order to facilitate further evaluations, we emphasize in
the prompt that the generated SQL statements can be executed in an SQLite
database. The lower half of Figure 1 represents the prompt in a multi-turn
Text-to-SQL scenario, where the prompt for the first interaction is the same
as that in the single-turn scenario, and for subsequent interactions, only the
new questions are required.

##  3 Experiment

Methods / Datasets | Spider | Spider-SYN | Spider-Realistic
---|---|---|---
VA | EX | TS | VA | EX | TS | VA | EX | TS
T5-3B + PICARD | 98.4 | 79.3 | 69.4 | 98.2 | 69.8 | 61.8 | 97.1 | 71.4 | 61.7
RASAT + PICARD | 98.8 | 80.5 | 70.3 | 98.3 | 70.7 | 62.4 | 97.4 | 71.9 | 62.6
RESDSQL-3B + NatSQL | 99.1 | 84.1 | 73.5 | 98.8 | 76.9 | 66.8 | 98.4 | 81.9 | 70.1
ChatGPT | 97.7 | 70.1(14$\downarrow$) | 60.1 | 96.2 | 58.6(18.3$\downarrow$) | 48.5 | 96.8 | 63.4(18.5 $\downarrow$) | 49.2

Table 1: Comparison of the performance of ChatGPT and other models on Spider,
Spider-SYN, and Spider-Realistic datasets.

Methods / Datasets | Spider-DK | ADVETA(rpl) | ADVETA(add)
---|---|---|---
VA | EX | TS | VA | EX | TS | VA | EX | TS
T5-3B + PICARD | 97.8 | 62.5 | - | 92.7 | 50.6 | - | 97.2 | 69.4 | -
RASAT + PICARD | 98.5 | 63.9 | - | 92.9 | 51.5 | - | 97.4 | 70.7 | -
RESDSQL-3B + NatSQL | 98.8 | 66.0 | - | 93.9 | 54.4 | - | 97.9 | 71.9 | -
ChatGPT | 96.4 | 62.6(3.4 $\downarrow$) | - | 91.4 | 58.5(4.1 $\uparrow$) | - | 93.1 | 68.1(3.8 $\downarrow$) | -

Table 2: Performance of different methods on the Spider-DK, ADVETA(RPL) and
ADVETA(ADD) benchmark datasets.

###  3.1 Experiment Setup

Datasets. We conduct extensive experiments on twelve public benchmark datasets
as follows: (1) Spider Yu et al. (2018) is a large-scale cross-domain Text-to-
SQL benchmark. It contains 8659 training samples across 146 databases and 1034
evaluation samples across 20 databases. (2) Spider-SYN Gan et al. (2021a) is a
challenging variant of the Spider evaluation dataset. Spider-SYN is
constructed by manually modifying natural language questions with synonym
substitutions. (3) Spider-DK Gan et al. (2021b) is a human-curated dataset
based on Spider, which samples 535 question-SQL pairs across 10 databases from
the Spider development set and modifies them to incorporate the domain
knowledge. (4) Spider-Realistic Deng et al. (2020) is a new evaluation set
based on the Spider dev set with explicit mentions of column names removed,
which contains 508 samples. (5) Spider-CG(SUB) and Spider-CG(APP) Gan et al.
(2022) are two evaluation datasets to measure the compositional generalization
of models, which is constructed by sub-sentence substitution between different
examples and appending a sub-sentence into another sentence separately. (6)
ADVETA(rpl) and ADVETA(add) Pi et al. (2022) are two challenging test datasets
for the Spider dataset which are composed of adversarial replacements of
column names and the addition of new column names, respectively. (7) CSpider
Min et al. (2019) dataset is constructed by translating Spider into Chinese,
which is the same size as the origin Spider dataset (8) DuSQL Wang et al.
(2020) is a larger scale Chinese Text-to-SQL dataset with 23,797 question/SQL
pairs. (9) SParC Yu et al. (2019b) and CoSQL Yu et al. (2019a) are two multi-
turn Text-to-SQL dataset with 1625 and 1007 questions in the dev set
separately.

Evaluation Metrics. We mainly adopt three evaluation metrics which are valid
SQL (VA), execution accuracy(EX), and test-suite accuracy (TS). Valid SQL (VA)
is the proportion of SQL statements that can be executed successfully.
Execution accuracy (EX) is the proportion of data where the execution results
match the standard SQL statements. Test-suite accuracy (TS) Zhong et al.
(2020) could achieve high code coverage from a distilled test suite of the
database, which is also based on execution. Note that we do not use the main-
stream exact match accuracy, as SQL queries that achieve the same goal can
often be expressed in different ways, making it difficult for zero-shot
ChatGPT models to achieve high exact match accuracy.

Methods / Datasets | Spider-CG(SUB) | Spider-CG(APP)
---|---|---
VA | EX | TS | VA | EX | TS
T5-3B + PICARD | 98.4 | 82.1 | 74.3 | 95.8 | 68.0 | 60.5
RASAT + PICARD | 99.0 | 82.6 | 76.1 | 96.2 | 68.6 | 61.0
RESDSQL-3B + NatSQL | 99.4 | 83.3 | 77.5 | 96.4 | 69.4 | 62.4
ChatGPT | 98.3 | 76.6(6.7 $\downarrow$) | 67.2 | 91.2 | 61.3(8.1 $\downarrow$) | 47.9

Table 3: Performance of different methods on the Spider-CG(SUB) and Spider-
CG(APP) benchmark datasets.

Baselines. Due to our exclusive reliance on execution-based evaluation, we did
not employ baselines such as RatSQL Wang et al. (2019) and LGESQL Cao et al.
(2021), which generate only SQL skeletons without generating values. Instead,
we primarily utilized three baselines: (1) PICARD Scholak et al. (2021) is a
method for constraining auto-regressive decoders of language models through
incremental parsing. (2) RASAT Qi et al. (2022) introduces relation-aware
self-attention into transformer models and also utilizes constrained auto-
regressive decoders. (3) RESDSQL Li et al. (2023) proposes a ranking-enhanced
encoding and skeleton-aware decoding framework to decouple the schema linking
and the skeleton parsing. Among those, PICARD and RASAT are based on T5-3B
Raffel et al. (2020) model.

###  3.2 Main Experiment

Evaluation on Spider Dataset. In Table 1, we present a comparison between
ChatGPT and the current state-of-the-art (SOTA) models. Overall, ChatGPT
exhibits a strong Text-to-SQL ability.Despite the 14% gap in execution
accuracy compared to the current SOTA models and a 13.4% gap in test suite
accuracy, it is remarkable that ChatGPT achieved such results in a zero-shot
scenario considering that it was not fine-tuned on the Spider training set.

Evaluation on Spider-SYN and Spider-Realistic Datasets. Table 1 also includes
a comparison of ChatGPT’s performance on the Spider-SYN and Spider-Realistic
datasets. The main difference between these datasets and the Spider dev set is
that they eliminate the explicit appearance of the database schema in the
questions. Overall, although ChatGPT still performs well on these two
settings, the performance gap between ChatGPT and the original SOTA models
becomes slightly larger than that on the Spider dataset. This suggests that
the current models have already achieved sufficient robustness in these two
scenarios.

Evaluation on Spider-DK and ADVETA Datasets. In Table 2, we further compare
and analyze ChatGPT’s performance on Spider-DK, ADVETA (RPL), and ADVETA
(ADD). We find that ChatGPT performs exceptionally well on these datasets,
with very small performance gaps compared to the current SOTA models. In fact,
ChatGPT outperforms all current SOTA models on ADVETA (RPL). For the Spider-DK
dataset, we speculate that ChatGPT’s excellent performance is due to its
additional knowledge provided by the large-scale pretraining. As for scenarios
such as ADVETA, where the dataset’s column names undergo adversarial
modifications, the poor generalization performance of current models may be
due to the significant distribution difference from the original dataset.
Overall, ChatGPT exhibits strong robustness in scenarios that require
additional knowledge or adversarial modifications are applied to the database
column names.

Methods / Datasets | SParC | CoSQL
---|---|---
VA | EX | VA | EX
T5-3B + PICARD | - | - | 97.5 | 64.7
RASAT + PICARD | 98.4 | 74.0 | 97.8 | 66.3
ChatGPT | 97.3 | 63.1 | 95.8 | 60.7

Table 4: The performance of ChatGPT on two multi-turn Text-to-SQL datasets:
SParC and CoSQL.

Evaluation on Spider-CG Dataset. In Table 3, we further analyze ChatGPT’s
ability in the compositional generalization scenario. We found that in Spider-
CG (SUB), SQL substructures are replaced to form combinations that do not
exist in the training set. In this scenario, ChatGPT even outperforms the
original Spider dev set. Even on the more challenging Spider-CG (APP) dataset,
ChatGPT achieves strong performance, and the performance gap with SOTA models
is relatively smaller than that on the original Spider dataset. Overall, since
ChatGPT is a zero-shot model, it is not as affected by compositional
generalization as the SOTA models. Overall, zero-shot models have greater
advantages in the compositional generalization setting.

Methods / Datasets | CSpider | DuSQL
---|---|---
VA | EX | VA | EX
ChatGPT | 96.0 | 65.1 | 82.7 | 53.7

Table 5: The performance of ChatGPT on two Chinese Text-to-SQL datasets:
CSpider and DuSQL.

Evaluation on multi-turn Text-to-SQL scenarios. Given ChatGPT’s strong
contextual modeling ability, we further evaluate its performance on multi-turn
Text-to-SQL scenarios: SParC and CoSQL. As shown in Table 4, ChatGPT exhibits
strong multi-turn Text-to-SQL ability. Although there is still a gap compared
to the current SOTA models, the gap is relatively smaller compared to the
single-turn Spider dataset. Meanwhile, ChatGPT also performs better on CoSQL
datasets with more average interactions, which also indicates that ChatGPT’s
strong contextual modeling ability is very helpful for multi-turn Text-to-SQL.

Evaluation on Chinese Text-to-SQL scenarios. We further evaluate ChatGPT’s
Text-to-SQL ability on other languages in Table 5. The experiments are mainly
conducted on two datasets, CSpider and DuSQL, where only the questions are in
Chinese for CSpider and both the schema names and questions are in Chinese for
DuSQL. The results show that while ChatGPT performs well in the Chinese Text-
to-SQL scenario, there is still a performance gap compared to the English
Text-to-SQL scenario. Moreover, the performance is even worse when the table
names and column names are also in Chinese, with a large number of generated
SQL queries being non-executable and a lower execution accuracy. This suggests
the cross-lingual generalization ability of ChatGPT requires further
improvement.

###  3.3 Case Study

|  Question: Show the stadium name and the number of concerts in each stadium.
---
ChatGPT: SELECT stadium.Name, COUNT(concert.concert_ID) FROM stadium  LEFT
JOIN  concert ON stadium.Stadium_ID = concert.Stadium_ID GROUP BY
stadium.Name;
Gold: SELECT T2.name , count(*) FROM concert AS T1  JOIN stadium AS T2 ON
T1.stadium_id = T2.stadium_id GROUP BY T1.stadium_id
|  Question:How many car models were produced by the maker with full name
American Motor Company?
---
ChatGPT: SELECT COUNT(*) FROM model_list WHERE  Maker  = ’American Motor
Company’
Gold: SELECT count(*) FROM CAR_MAKERS AS T1 JOIN model_list AS T2 ON T1.Id =
T2.Maker WHERE  T1.FullName  = ’American Motor Company’;
|  Question: How many cars have a larger accelerate than the car with the
largest horsepower?
---
ChatGPT: SELECT COUNT(*) FROM cars_data WHERE Accelerate > (SELECT
MAX(Horsepower) FROM cars_data)
Gold: SELECT COUNT(*) FROM CARS_DATA WHERE Accelerate > (SELECT  Accelerate
FROM CARS_DATA ORDER BY Horsepower DESC LIMIT 1);
|  Question: What is the abbreviation of Airline "JetBlue Airways"?
---
ChatGPT: SELECT Abbreviation FROM airlines WHERE Airline =  ’Jetblue Airways’
;
Gold: SELECT Abbreviation FROM AIRLINES WHERE Airline =  "JetBlue Airways";

Table 6: Case study: We selected four cases of incorrect predictions generated
by ChatGPT on the Spider development set for analysis.

In Table 6, we present four typical prediction errors made by ChatGPT on the
Spider dev dataset. The first error case shows that ChatGPT tends to design
JOIN statements more finely by using LEFT JOIN, but this level of granularity
is not present in the original Spider dev dataset. The second error case
arises from ChatGPT’s confusion regarding the database structure, and it is
not clear which column the term "full name" specifically refers to. The third
example’s error was due to the generated SQL statement lacking correct
semantic interpretation, resulting in incorrect output for the "where" clauses
with nested SQL statements. The fourth case of error is due to errors in
copying specific values, where the case sensitivity of the original value was
not preserved when regenerating the value.

In summary, ChatGPT’s errors mostly occur in small details, and some of these
issues can be addressed and improved in later stages of development, such as
in the first, third, and fourth cases. However, for errors like the second
case, which indicate a lack of understanding of the database schema, further
improvements to the model’s ability may be necessary to resolve them.

##  4 Related Work

Text-to-SQL is an important semantic parsing task that converts natural
language questions posed by users into SQL statements that can be executed on
a database. On the classic Spider dataset Yu et al. (2018), many classic works
such as RatSQL Wang et al. (2019) and LGESQL Cao et al. (2021) have achieved
excellent results. Since Text-to-SQL is a very complex task involving both
user input questions and database structure, the robustness of the model is
crucial. To further explore this issue, Gan et al. (2021a) proposed the
Spider-SYN dataset to evaluate the robustness of models under synonym
substitution scenarios. Some works, such as Proton Wang et al. (2022) and
ISESL-SQL Liu et al. (2022), are also devoted to improving the robustness of
models in this scenario. Meanwhile, many works explore the robustness of the
Text-to-SQL task in other scenarios. The Spider-DK dataset Gan et al. (2021b)
evaluates the robustness of models in scenarios requiring additional
knowledge. The Spider-Realistic dataset Deng et al. (2020) removes the
explicit appearance of dataset schema information in user questions, thereby
increasing the difficulty of the original task. The Spider-CG dataset Gan et
al. (2022) evaluates the robustness of models in compositional generalization
scenarios. The ADVETA dataset Pi et al. (2022) evaluates the robustness of
models in scenarios involving adversarial modifications of database table
information. In addition, to verify the robustness of models in cross-lingual
scenarios, CSpider Min et al. (2019) and DuSQL Wang et al. (2020) have been
proposed to evaluate the robustness of models in the Chinese language. To
evaluate the performance of Text-to-SQL in more realistic scenarios, SParC Yu
et al. (2019b) and CoSQL Yu et al. (2019a) have been proposed to evaluate the
performance of multi-turn Text-to-SQL. Models such as STaR Cai et al. (2022)
and CQR-SQL Xiao et al. (2022) have also achieved good results in this
scenario.

Currently, several methods have been attempted to explore the improvement of
large-scale language models for Text-to-SQL models. The PICARD Scholak et al.
(2021) and RASAT Qi et al. (2022) utilize the T5-3B model, but still require
the training data for fine-tuning. Rajkumar et al. (2022) investigated the
Text-to-SQL capabilities of the GPT3 model in a zero-shot setting. Cheng et
al. (2022) proposed the BINDER model based on the GPT3 codex, which has
similar Text-to-SQL generation capabilities with the need for in-context
exemplar annotations. However, these works do not provide a comprehensive
evaluation of Text-to-SQL and are limited to a few datasets without other
robustness settings. In this work, we are the first to evaluate the
comprehensive Text-to-SQL capabilities of ChatGPT.

##  5 Conclusion

In this work, we conducted a comprehensive analysis of ChatGPT’s zero-shot
ability in Text-to-SQL. We found that even without using any training data,
ChatGPT still has strong Text-to-SQL ability, although there is still some gap
compared to the current SOTA models. Additionally, ChatGPT demonstrated strong
robustness, performing relatively better on most robustness benchmarks and
even surpassing the current SOTA models on the ADVETA benchmark. Although this
paper has made some findings, we only utilize a common prompt to evaluate
ChatGPT’s ability. And in future work, better prompts could be designed to
explore ChatGPT’s Text-to-SQL ability.

##  6 Future work

In future work, we will primarily consider the following two directions to
further explore ChatGPT’s capabilities in the Text-to-SQL task. Firstly, we
will conduct more interactions with ChatGPT to address the issue of generating
non-executable SQL statements. We can design ChatGPT to engage in multi-turn
dialogues with the provided database error messages to further ensure the
validity of generated SQL statements. Secondly, we will add more highly
correlated in-context examples to the prompt to enhance ChatGPT’s ability to
generate Text-to-SQL.

## References

  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901.
  * Cai et al. (2022) Zefeng Cai, Xiangyu Li, Binyuan Hui, Min Yang, Bowen Li, Binhua Li, Zheng Cao, Weijie Li, Fei Huang, Luo Si, et al. 2022.  Star: Sql guided pre-training for context-dependent text-to-sql parsing.  _arXiv preprint arXiv:2210.11888_.
  * Cao et al. (2021) Ruisheng Cao, Lu Chen, Zhi Chen, Yanbin Zhao, Su Zhu, and Kai Yu. 2021.  Lgesql: line graph enhanced text-to-sql model with mixed local and non-local relations.  _arXiv preprint arXiv:2106.01093_.
  * Cheng et al. (2022) Zhoujun Cheng, Tianbao Xie, Peng Shi, Chengzu Li, Rahul Nadkarni, Yushi Hu, Caiming Xiong, Dragomir Radev, Mari Ostendorf, Luke Zettlemoyer, et al. 2022.  Binding language models in symbolic languages.  _arXiv preprint arXiv:2210.02875_.
  * Christiano et al. (2017) Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. 2017.  Deep reinforcement learning from human preferences.  _Advances in neural information processing systems_ , 30.
  * Deng et al. (2020) Xiang Deng, Ahmed Hassan Awadallah, Christopher Meek, Oleksandr Polozov, Huan Sun, and Matthew Richardson. 2020.  Structure-grounded pretraining for text-to-sql.  _arXiv preprint arXiv:2010.12773_.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Frieder et al. (2023) Simon Frieder, Luca Pinchetti, Ryan-Rhys Griffiths, Tommaso Salvatori, Thomas Lukasiewicz, Philipp Christian Petersen, Alexis Chevalier, and Julius Berner. 2023\.  Mathematical capabilities of chatgpt.  _arXiv preprint arXiv:2301.13867_.
  * Gan et al. (2022) Yujian Gan, Xinyun Chen, Qiuping Huang, and Matthew Purver. 2022.  Measuring and improving compositional generalization in text-to-sql via component alignment.
  * Gan et al. (2021a) Yujian Gan, Xinyun Chen, Qiuping Huang, Matthew Purver, John R Woodward, Jinxia Xie, and Pengsheng Huang. 2021a.  Towards robustness of text-to-sql models against synonym substitution.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 2505–2515.
  * Gan et al. (2021b) Yujian Gan, Xinyun Chen, and Matthew Purver. 2021b.  Exploring underexplored limitations of cross-domain text-to-sql generalization.  _arXiv preprint arXiv:2109.05157_.
  * Li et al. (2023) Haoyang Li, Jing Zhang, Cuiping Li, and Hong Chen. 2023.  Decoupling the skeleton parsing and schema linking for text-to-sql.  _arXiv preprint arXiv:2302.05965_.
  * Liu et al. (2022) Aiwei Liu, Xuming Hu, Li Lin, and Lijie Wen. 2022.  Semantic enhanced text-to-sql parsing via iteratively learning schema linking graph.  In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , pages 1021–1030.
  * Min et al. (2019) Qingkai Min, Yuefeng Shi, and Yue Zhang. 2019.  A pilot study for chinese sql semantic parsing.  _arXiv preprint arXiv:1909.13293_.
  * Pi et al. (2022) Xinyu Pi, Bing Wang, Yan Gao, Jiaqi Guo, Zhoujun Li, and Jian-Guang Lou. 2022.  Towards robustness of text-to-SQL models against natural and realistic adversarial table perturbation.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2007–2022, Dublin, Ireland. Association for Computational Linguistics.
  * Qi et al. (2022) Jiexing Qi, Jingyao Tang, Ziwei He, Xiangpeng Wan, Chenghu Zhou, Xinbing Wang, Quanshi Zhang, and Zhouhan Lin. 2022.  Rasat: Integrating relational structures into pretrained seq2seq model for text-to-sql.  _arXiv preprint arXiv:2205.06983_.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _The Journal of Machine Learning Research_ , 21(1):5485–5551.
  * Rajkumar et al. (2022) Nitarshan Rajkumar, Raymond Li, and Dzmitry Bahdanau. 2022.  Evaluating the text-to-sql capabilities of large language models.  _arXiv preprint arXiv:2204.00498_.
  * Scholak et al. (2021) Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. 2021.  Picard: Parsing incrementally for constrained auto-regressive decoding from language models.  _arXiv preprint arXiv:2109.05093_.
  * Wang et al. (2019) Bailin Wang, Richard Shin, Xiaodong Liu, Oleksandr Polozov, and Matthew Richardson. 2019.  Rat-sql: Relation-aware schema encoding and linking for text-to-sql parsers.  _arXiv preprint arXiv:1911.04942_.
  * Wang et al. (2023) Jiaan Wang, Yunlong Liang, Fandong Meng, Zhixu Li, Jianfeng Qu, and Jie Zhou. 2023\.  Cross-lingual summarization via chatgpt.  _arXiv preprint arXiv:2302.14229_.
  * Wang et al. (2022) Lihan Wang, Bowen Qin, Binyuan Hui, Bowen Li, Min Yang, Bailin Wang, Binhua Li, Jian Sun, Fei Huang, Luo Si, et al. 2022.  Proton: Probing schema linking information from pre-trained language models for text-to-sql parsing.  In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , pages 1889–1898.
  * Wang et al. (2020) Lijie Wang, Ao Zhang, Kun Wu, Ke Sun, Zhenghua Li, Hua Wu, Min Zhang, and Haifeng Wang. 2020.  Dusql: A large-scale and pragmatic chinese text-to-sql dataset.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6923–6935.
  * Wei et al. (2023) Xiang Wei, Xingyu Cui, Ning Cheng, Xiaobin Wang, Xin Zhang, Shen Huang, Pengjun Xie, Jinan Xu, Yufeng Chen, Meishan Zhang, et al. 2023.  Zero-shot information extraction via chatting with chatgpt.  _arXiv preprint arXiv:2302.10205_.
  * Xiao et al. (2022) Dongling Xiao, Linzheng Chai, Qian-Wen Zhang, Zhao Yan, Zhoujun Li, and Yunbo Cao. 2022.  Cqr-sql: Conversational question reformulation enhanced context-dependent text-to-sql parsers.  _arXiv preprint arXiv:2205.07686_.
  * Yu et al. (2019a) Tao Yu, Rui Zhang, He Yang Er, Suyi Li, Eric Xue, Bo Pang, Xi Victoria Lin, Yi Chern Tan, Tianze Shi, Zihan Li, et al. 2019a.  Cosql: A conversational text-to-sql challenge towards cross-domain natural language interfaces to databases.  _arXiv preprint arXiv:1909.05378_.
  * Yu et al. (2018) Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, et al. 2018.  Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-sql task.  _arXiv preprint arXiv:1809.08887_.
  * Yu et al. (2019b) Tao Yu, Rui Zhang, Michihiro Yasunaga, Yi Chern Tan, Xi Victoria Lin, Suyi Li, Heyang Er, Irene Li, Bo Pang, Tao Chen, et al. 2019b.  Sparc: Cross-domain semantic parsing in context.  _arXiv preprint arXiv:1906.02285_.
  * Zhong et al. (2020) Ruiqi Zhong, Tao Yu, and Dan Klein. 2020.  Semantic evaluation for text-to-sql with distilled test suites.  _arXiv preprint arXiv:2010.02840_.