PaperlayerView exact revision on arXiv

Source-linked AI summary

Alpha-SQL: Zero-Shot Text-to-SQL using Monte Carlo Tree Search

Boyan Li, Jiayi Zhang, Ju Fan, Yanwei Xu, Chong Chen, Nan Tang, Yuyu Luo

arXiv:2502.17248v2cs.DB

TL;DR

Zero-shot Text-to-SQL avoids task-specific fine-tuning, but transferring pretrained LLM knowledge to schema-specific SQL generation remains challenging. Alpha-SQL uses MCTS with LLM-generated reasoning actions to construct queries progressively. It reports 69.7% execution accuracy on the BIRD development set without fine-tuning.

  • Problem

    Zero-shot Text-to-SQL must transfer pretrained LLM knowledge to SQL generation over natural-language questions and database schemas without task-specific annotated data.

    Source: §4.1 · p. 4

  • Method

    Alpha-SQL frames SQL generation as progressive construction over an MCTS tree, using LLM-generated reasoning actions to guide search through partial reasoning states.

    Source: §1 · p. 2

  • Results

    69.7% execution accuracy on the BIRD development set, with Alpha-SQL significantly outperforming existing zero-shot methods.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Alpha-SQL is a plug-and-play, fine-tuning-free framework that delivers competitive Text-to-SQL performance with open-source LLMs.

    Source: §6 · p. 9

Abstract

from arXiv · show

Text-to-SQL, which enables natural language interaction with databases, serves as a pivotal method across diverse industries. With new, more powerful large language models (LLMs) emerging every few months, fine-tuning has become incredibly costly, labor-intensive, and error-prone. As an alternative, zero-shot Text-to-SQL, which leverages the growing knowledge and reasoning capabilities encoded in LLMs without task-specific fine-tuning, presents a promising and more challenging direction. To address this challenge, we propose Alpha-SQL, a novel approach that leverages a Monte Carlo Tree Search (MCTS) framework to iteratively infer SQL construction actions based on partial reasoning states. To enhance the framework's reasoning capabilities, we introduce LLM-as-Action-Model to dynamically generate SQL construction actions during the MCTS process, steering the search toward more promising SQL queries. Moreover, Alpha-SQL employs a self-supervised reward function to evaluate the quality of candidate SQL queries, ensuring more accurate and efficient query generation. Experimental results show that Alpha-SQL achieves 69.7% execution accuracy on the BIRD development set, using a 32B open-source LLM without fine-tuning. Alpha-SQL outperforms the best previous zero-shot approach based on GPT-4o by 2.5% on the BIRD development set.

1. Introduction

The introduction motivates zero-shot Text-to-SQL as a lower-cost alternative to repeated task-specific fine-tuning, while noting the challenge of transferring general LLM knowledge to SQL generation. Alpha-SQL addresses this challenge through progressive SQL construction with MCTS, LLM-generated reasoning actions, and self-supervised candidate evaluation.

1. Introduction

  • Fine-tuning requires labeled data and substantial compute, and must be repeated as stronger LLMs emerge; zero-shot methods avoid that training but struggle to transfer pretrained knowledge to schema-specific SQL generation.The challenge affects schema-relationship interpretation, complex query construction, and robustness across contexts.Source: §1 · p. 1
  • Alpha-SQL decomposes query generation into manageable steps and searches a tree whose nodes are partial reasoning states and whose edges are SQL-construction actions.Iteratively selecting actions from root to leaf progressively constructs a valid SQL query.Source: §1 · pp. 1–2
  • LLM-as-Action-Model generates step-by-step reasoning after each action and stores it with the partial state, keeping subsequent SQL-construction actions context-aware.The reasoning guides MCTS toward more promising queries.Source: §1 · p. 2
  • A self-supervised reward evaluates candidate SQL by comparing execution results from high-temperature samples with the predicted query, filtering invalid candidates and prioritizing promising reasoning paths.Alpha-SQL selects the candidate with the highest self-consistency score as its final output.Source: §1 · p. 2
  • 69.7% execution accuracy on the BIRD development set; Figure 1 reports 15%-20% improvement across Qwen2.5 sizes (7B-32B) and performance surpassing RSL-SQL on BIRD (Dev).The introduction also reports that ablations confirm the effectiveness of reasoning actions and that performance improves with more MCTS rollouts.Source: §1 · p. 2, Figure 1 · p. 2

2. Related Work

Prior Text-to-SQL work explores decomposition and test-time search, but the related work notes that general reasoning approaches do not fully address SQL-specific challenges. Alpha-SQL combines progressive SQL construction with MCTS and LLM-driven reasoning.

2. Related Work

  • Text-to-SQL systems decompose tasks into candidate generation, refinement, and selection; CHASE-SQL uses a multi-step pipeline to generate and validate candidates, especially for nested queries.Alpha-SQL incorporates CHASE-SQL’s Divide-and-Conquer CoT strategy into its reasoning action space.Source: §2 · p. 2
  • Test-time planning, search, verification, tree search, Best-of-N sampling, and MCTS improve inference reasoning, but these approaches do not fully address SQL schema understanding, semantic accuracy, and execution-feedback refinement.The related-work discussion specifically notes this gap for general MCTS reasoning methods.Source: §2 · pp. 2–3
  • Alpha-SQL applies MCTS to dynamic, progressive SQL generation, integrating LLM-driven reasoning and database feedback to guide exploration without task-specific labeled data.The paper contrasts this with prior approaches that rely on static pipelines or fine-tuning.Source: §2 · pp. 2–3

3. Alpha-SQL

The section frames zero-shot Text-to-SQL as constructing valid queries without task-specific labels in a combinatorially large search space. Alpha-SQL models query construction as MCTS over partial reasoning states and uses execution-based self-consistency to guide search.

3.1. Zero-shot Text-to-SQL

  • Exhaustive Text-to-SQL search is impractical because the space grows exponentially with schema and question complexity, while zero-shot systems must generalize without task-specific labeled data.The search formulation represents nodes as partial reasoning states and edges as SQL construction actions; a root-to-leaf path forms a candidate query.Source: §3.1 · p. 3

3.2. An Overview of Alpha-SQL

  • Alpha-SQL uses MCTS to iteratively explore SQL construction actions, with each trajectory producing a candidate query from partial reasoning states.The root is an empty query, and the search builds a tree of reasoning trajectories.Source: §3.2 · pp. 3–4
  • The self-supervised reward compares execution results of sampled SQL queries with the predicted query to prioritize paths with consistent results.Sampled queries are generated for each reasoning path, and stable execution results support prioritization without annotated data.Source: §3.2 · p. 4

4. The Design Details of Alpha-SQL

Alpha-SQL combines context-conditioned LLM actions with MCTS to construct and select candidate SQL queries, alongside retrieval of database values relevant to a question. Its design specifies action choices and ordering, search updates, and a two-stage value-retrieval process.

4.1. LLM-as-Action-Model

  • LLM-as-Action-Model generates actions dynamically from the question, schema, and current partial reasoning state, enabling stepwise SQL construction.The seven-action space includes question rephrasing, schema selection, column-value and function identification, SQL generation, revision, and termination.Source: §4.1 · pp. 4–5

4.2. MCTS for Candidate SQL Generation

  • MCTS uses selection, expansion, simulation, and backpropagation to generate candidate SQL trajectories, then selects the query with the highest execution-result consistency.Backpropagation samples SQL queries and updates action rewards and visit counts; pruning removes duplicate nodes when sampled schema subsets match.Source: §4.2 · p. 6

4.3. Database Value Retrieval

  • Database value retrieval preprocesses TEXT-column values into MinHash signatures, then uses LSH and similarity thresholds to retrieve values for the LLM prompt.Online retrieval extracts question keywords and filters retrieved values using editing and semantic similarity thresholds.Source: §4.3 · pp. 6–7

5. Experiments

Alpha-SQL is evaluated on BIRD and Spider, with additional experiments examining rollout counts, baseline LLMs, and the action space. Its strongest reported results come from the BIRD evaluation, while ablations and rollout analyses examine the framework’s behavior.

5.1. Experimental Setup

  • Evaluation uses Execution Accuracy on Spider and BIRD development sets, with a 147-sample BIRD subset used for comparison experiments; models are Qwen2.5-Coder 7B, 14B, and 32B.The subset contains 81 simple, 54 moderate, and 12 challenging questions; MCTS uses 24 rollouts in the reported settings.Source: §5.1 · p. 7, §5.2 · p. 7

5.2. Main Results on BIRD and Spider Datasets

  • 69.7% average accuracy on BIRD is reported for the 32B model; on Spider, Qwen2.5-Coder-14B improves 2.1% over fine-tuned SFT CodeS-15B.The BIRD and Spider results are reported for their respective development sets.Source: §5.2 · p. 7, Table 2 · p. 8, Table 3 · p. 8

5.3. Impact of MCTS Rollouts on Performance

  • More MCTS rollouts correlate positively with both upper-bound and final accuracy; the authors report significant improvement with 24 rollouts despite over 3,000 possible reasoning paths per task.The rollout analysis used Qwen2.5-Coder-7B on the 147-sample Subsampled Development Set.Source: §5.1 · p. 7, §5.3 · p. 8, Figure 5 · p. 8

5.4. Comparison with Baseline LLMs

  • On the Subsampled Development Set, Alpha-SQL with 7B parameters surpasses the baseline LLMs, and improves accuracy by 17.0% for Qwen2.5-Coder-7B and 16.5% for Phi-4 over direct prompting.The comparisons use a standardized Text-to-SQL prompt for the baseline LLMs.Source: §5.4 · pp. 8–9, Table 4 · p. 9

5.5. Ablation Study of Action Space

  • Removing any action reduces performance; SQL Revision is particularly important because it uses database-execution feedback to correct SQL.The ablation removes individual actions from the original action space on the Subsampled Development Set.Source: §5.5 · p. 9, Table 5 · p. 9

6. Conclusion

Alpha-SQL frames zero-shot Text-to-SQL as structured search, combining MCTS with LLM-as-Action-Model without fine-tuning. Experiments report competitive BIRD performance and support the effectiveness of its reasoning actions and additional MCTS rollouts.

6. Conclusion

  • Alpha-SQL combines MCTS and LLM-as-Action-Model to search SQL queries without fine-tuning, achieving 69.7% on the BIRD development set.The conclusion also reports that ablations validate the reasoning actions and that performance improves with more MCTS rollouts.Source: §6 · p. 9

A.1. Alpha-SQL Algorithm

The algorithm builds a search tree of partial SQL reasoning states and explores it through repeated MCTS rollouts. It updates search values using execution-result self-consistency and returns the candidate SQL with the highest self-consistency.

A.1. Alpha-SQL Algorithm

  • Each rollout selects a path through the tree, expands valid actions into new states, and simulates actions until it reaches a terminal state and extracts SQL.The tree begins at a root containing the question and database schema.Source: §A.1 · pp. 12–13
  • Selection uses UCT to balance estimated reward and action visit counts while traversing the tree toward an unexpanded node.Expansion invokes the LLM-as-Action-Model to generate child states for valid actions.Source: §A.1 · p. 12
  • At terminal states, the algorithm samples SQL queries and scores self-consistency by comparing their execution results with the predicted SQL’s execution result.That reward updates node values along the rollout path to guide later searches.Source: §A.1 · pp. 12–13
  • After the rollouts, Alpha-SQL returns the candidate SQL with the highest self-consistency score.The authors characterize the procedure as a fine-tuning-free approach for exploring the SQL-query search space.Source: §A.1 · p. 12

A.2. Prompt Template for Actions

The appendix supplies prompts for actions in Alpha-SQL’s SQL-construction process. They cover question rephrasing, schema and column analysis, SQL generation, and revision.

A.2. Prompt Template for Actions

  • Question rephrasing splits the context into conditions while preserving the original question’s information.The example converts a movie query into conditions for release year, sort order, and returned titles.Source: §A.2 · p. 14
  • Schema selection asks the model to use the question and hint to identify the table columns needed to craft a SQL query.The prompt frames the task as examining the provided database schema.Source: §A.2 · p. 15
  • Column-function identification asks which potential column functions are needed to answer the question.The prompt includes a database-schema example with a column description.Source: §A.2 · p. 17, Figure 9 · p. 17
  • SQL generation prompts the model to produce a query from database information and the question, using schema descriptions and value examples.The prompt describes a recursive divide-and-conquer approach to SQL query generation.Source: §A.2 · p. 18, Figure 10 · p. 18
  • SQL revision asks the model to correct a query after execution errors or incorrect, empty, or unexpected results, using schema and execution information.The prompt directs the model to examine the failed query and its execution result.Source: §A.2 · p. 19, Figure 11 · p. 19

A.3. Prompt Template for Question Keywords Extraction

The section provides a prompt template for extracting keywords from a question and hint. It targets terms useful for understanding the inquiry and formulating related queries.

A.3. Prompt Template for Question Keywords Extraction

  • The template analyzes a question and hint to extract keywords, keyphrases, and named entities.The appendix identifies this as the prompt template for the question-keyword extraction described in Section 4.3.Source: §A.3 · p. 20
  • The extracted elements are intended to capture core components of the inquiry and guidance provided by the hint.Source: §A.3 · p. 20
  • The prompt frames these terms and phrases as useful for formulating searches or queries related to the question.Source: §A.3 · p. 20, Figure 12 · p. 20

A.4. Prompt Template for Baseline LLMs

The section provides a prompt template for directly calling baseline LLMs to generate SQL. It supplies database schemas and additional information, including value examples to help select columns.

A.4. Prompt Template for Baseline LLMs

  • The baseline prompt asks an LLM to generate a SQL query from database information, a question, and additional information.The appendix identifies this as the template for directly calling baseline LLMs in Section 5.4.Source: §A.2 · p. 18, §A.4 · p. 21
  • The prompt describes database structure through table schemas, with comments after dashes providing additional column descriptions.Source: §A.4 · p. 21
  • Value examples are actual column values, and the prompt directs the model to use them to justify which columns to select.Source: §A.4 · p. 21, Figure 13 · p. 21
Loading 2502.17248v2…