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

Dear Reviewer,

Thank you for your comprehensive review and for providing a clear summary of our proposed Alpha-SQL method. We understand the need for comparison against a "Best-of-N" baseline, the omission of base model performance for larger Qwen models in Table 4, and the lack of detailed analysis on computational costs (token usage and latency). These are valid points crucial for thoroughly evaluating a test-time compute method like Alpha-SQL. We appreciate the opportunity to address these concerns.

Below, we address each point in detail:

1. Comparison with Best-of-N Baseline

Reviewer Concern: "...a comparison with the best-of-N method (directly generate N candidate SQL queries then use self-consistency to select the most consistent answer) which is the common strong baseline for any test-time compute methods would truly convince me about the effectiveness of this method." Reviewer Weakness: "... a comparison with a baseline like Best-of-N method is very important."

• Our Response: Thank you for suggesting the comparison with the Best-of-N baseline. We agree that this is a relevant and strong baseline for evaluating test-time inference methods employing self-consistency. While Best-of-N explores the model's output diversity from a single prompt state, Alpha-SQL uses MCTS to explore diverse reasoning paths before final SQL generation.

  • Comparison with Best-of-N: | Base LLM | Direct Prompting | Directly Promoting with Best-of-N | Alpha-SQL | |------------------------------|------------------|-----------------------------------|-----------| | Qwen2.5-Coder-Instruct-7B | 48.4% | 56.3% | 66.8% | | Qwen2.5-Coder-Instruct-14B | 57.4% | 62.3% | 68.7% | | Qwen2.5-Coder-Instruct-32B | 62.6% | 63.4% | 69.7% |

  • The results clearly demonstrate that Alpha-SQL significantly outperforms the Best-of-N baseline across all tested Qwen model sizes. For instance, with the 7B model, Alpha-SQL achieves 66.8% EX compared to 56.3% for Best-of-N (+10.5%). Similarly, with the 32B model, Alpha-SQL reaches 69.7% compared to 63.4% (+6.3%). This confirms that the structured reasoning path exploration enabled by Alpha-SQL's MCTS framework offers substantial benefits beyond simply sampling multiple outputs from a fixed initial prompt state, even when using self-consistency for selection. We will add these comparative results and include this analysis in the revised manuscript.

2. Missing Base Model Performance (Qwen 14B & 32B in Table 4)

Reviewer Concern: "...the base performance for the larger Qwen 14B and 32B models are not provided in table 4 but I think seeing the performance gain for these models is also important cause I believe the performance gap could be smaller for these models." Reviewer Note on Table 4: "Table 4 has the issue of missing the baseline performance for 14B abd 32B models."

• Our Response: Thank you for pointing out the missing base model performance data for the Qwen2.5-Coder-14B and -32B models in Table 4. We completely agree that showing the performance gain achieved by Alpha-SQL over the respective base models is important for a full evaluation across different model sizes, and we appreciate you highlighting this omission. As shown in the table provided in our response to your first point (regarding fair comparison and Best-of-N baselines), we have now completed the evaluation to determine the baseline performance for these models. We will update Table 4 in the revised manuscript to include this complete comparison and add a discussion analyzing these performance gains.

3. Cost Analysis: Token Usage and Latency

Reviewer Weakness: "A detailed analysis on the token usage of this method is required..." Reviewer Weakness: "A detailed analysis on the latency of this method is also required, most of the text-to-SQL systems require performing in few seconds to be able to useful in real world settings."

• Our Response: We understand the need for a detailed analysis of computational costs, specifically token usage and inference latency, to assess the practical viability of Alpha-SQL.
• Due to rebuttal length limitations, we kindly refer the reviewer to our detailed response to Reviewer guJX, specifically: Point 1 (Fair Comparison...) and Point 2 (Computational Cost Analysis...). We believe those sections fully address the concerns regarding token usage and latency analysis.

We believe these additions will significantly strengthen the paper's evaluation by providing crucial comparative data and cost context. We appreciate the reviewer's constructive feedback, which helps us improve the rigor of our study, and we hope the revised manuscript will meet the standards for acceptance.

Sincerely,

The Authors

Dear Reviewer,

Thank you for your detailed feedback. We appreciate the opportunity to clarify our approach, particularly regarding the core concerns about the MCTS framework's validity, the reward mechanism, experimental fairness, and novelty, which we believe may stem from some misunderstandings.

1. Validity and Significance of the MCTS Framework for Text-to-SQL

Reviewer Concerns: Formulating Text-to-SQL as a search problem is unconvincing/lacks support; main pipeline is nearly fixed (like CHESS), making many paths ineffective; questions value of searching reasoning actions; inconsistency between MCTS claim and reward function impact.

• Our Response: We respectfully disagree that formulating Text-to-SQL as an MCTS search problem lacks significance. While fixed workflows like CHESS exist, Text-to-SQL often requires flexible adaptation (e.g., for schema complexity, query ambiguity) that MCTS provides.
  • Why MCTS is Beneficial: Alpha-SQL uses MCTS precisely to navigate the choices within the reasoning process, not just execute fixed steps.
    • Adaptability: MCTS allows Alpha-SQL to dynamically select the most useful sequence of preparatory actions (like Schema Selection, Value Identification) for a given query, rather than following a rigid pipeline. It efficiently prunes suboptimal paths while exploring promising variations. Our analysis presented to Reviewer 5kbR (Point 5) demonstrates this adaptive path selection based on database complexity.
    • Clarifying Reward Propagation: This seems to be a key point of misunderstanding. The reward obtained after SQL generation is backpropagated through the entire MCTS tree via standard MCTS updates. This directly influences the selection probabilities of all preceding actions (including Actions 1-4) based on their contribution to successful outcomes. This holistic path guidance fundamentally differs from the local feedback/refinement mechanisms in methods like CHESS or E-SQL [2].
    • Theoretical Support: Our contribution is the novel application and formulation of the well-established MCTS algorithm for zero-shot Text-to-SQL, supported by strong empirical results. We will enhance Section 3 to clarify the MCTS reward backpropagation mechanism.

2. Fair Experimental Comparison (Qwen vs. GPT-4)

Reviewer Concerns: Experiments lack fair comparison using the same base LLM; Alpha-SQL uses Qwen, baselines use GPT-4; need Alpha-SQL results on GPT-4.

• Our Response: We acknowledge the importance of fair comparison. Due to rebuttal length constraints, we kindly refer you to our detailed response to Reviewer guJX (Points 1 & 2). This includes direct performance comparisons of Qwen-32B and GPT-4o (showing they have similar base capabilities on BIRD-dev) and evaluations of baselines (RSL-SQL, CHESS-SQL) run directly on Qwen-7B. These results demonstrate Alpha-SQL's significant gains originate from the framework itself, not just the base model.

3. Novelty Concerns (SQL Generation)

Reviewer Concern: Core SQL Generation action is based on existing method (CHASE-SQL), raising concerns about novelty and effectiveness.

• Our Response: While we leverage insights from prior work like CHASE-SQL for components like SQL Generation, the primary novelty of Alpha-SQL lies in the overall MCTS framework. This includes the dynamic orchestration of actions, adaptive reasoning path construction, and the integration of components into a cohesive, effective system for zero-shot Text-to-SQL. We will refine our discussion to better delineate these contributions.

4. Computational Cost Analysis

Reviewer Concern: MCTS likely increases runtime; analysis of inference cost needed; limitations section missing.

• Our Response: We agree cost analysis is essential. Our analysis, detailed quantitatively in response to Reviewer guJX (Points 1 & 2), confirms Alpha-SQL achieves higher accuracy but incurs higher latency compared to baselines run on the same model. We commit to adding a dedicated "Computational Cost Analysis" subsection and a "Limitations" section discussing these trade-offs in the revised manuscript.

5. Missing References

Reviewer Suggestion: Include discussion of E-SQL and the LLM Agents survey.

• Our Response: Thank you for suggesting E-SQL and the LLM Agents survey. We agree they are relevant and will incorporate discussion of both in our revised related work section.

6. Supplementary Material Clarification

Reviewer Statement: "There is no supplementary material provided."

• Our Response: We apologize for any confusion. Supplementary material, including detailed prompts, algorithm code, and running results, was provided with our initial submission and should be accessible via the OpenReview page.

We hope that these clarifications and planned revisions will address the reviewer's concerns and lead to a re-evaluation of our work's contributions.

Dear Reviewer,

Thank you for your detailed and insightful review of our paper. Below, we address each point in detail:

1. Fair Comparison, Model Choice, and Performance Validation (Addressing Concerns on Experiments, Q1, Q2a, and Rationale for Qwen)

• Our Response: We acknowledge the critical importance of fair comparison and understand the concern that the observed performance gains might be attributed solely to the base LLM (Qwen2.5-Coder) rather than the Alpha-SQL framework. We also agree that the rationale for choosing Qwen needs clarification.

  • Direct Qwen vs. GPT-4o Prompting Comparison - Addresses Q1:

    • To directly address the relative strength of the base models on this task (Q1), we performed a direct prompting comparison between Qwen2.5-Coder-Instruct-32B and GPT-4o on the BIRD dev set using the same simple prompt structure. We also included results using simple self-consistency:

      Model	Execution Accuracy
      GPT-4o	62.3%
      Qwen2.5-Coder-Instruct-32B	62.6%
      GPT-4o + Self-consistency	63.2%
      Qwen2.5-Coder-Instruct-32B + Self-consistency	63.4%

    • This comparison reveals that Qwen2.5-Coder-Instruct-32B and GPT-4o exhibit very comparable performance on the BIRD dev set when using simple direct prompting (62.6% vs 62.3%) and even when enhanced with basic self-consistency (63.4% vs 63.2%). This indicates that neither model has a significant inherent advantage over the other for this specific task under these simple zero-shot conditions.

  • Run Baselines on Qwen2.5-Coder-Instruct-7B: | Methods | Execution Accuracy | Input Tokens (K) / Question | Output Tokens (K) / Question | Total Tokens (K) / Question | Latency (s) / Question | |-----------|--------------------|-----------------------------|------------------------------|-----------------------------|------------------------| | RSL-SQL | 57.7% | 12.1 | 0.3 | 12.4 | 11.35 | | CHESS-SQL | 61.0% | 327.0 | 24.8 | 351.8 | 284.4 | | Alpha-SQL | 66.8% | 138.0 | 72.2 | 200.2 | 377.1 |

    • Comparing these results, Alpha-SQL (66.8%) significantly outperforms both RSL-SQL (57.7%) and CHESS-SQL (61.0%) when using the identical base LLM. Specifically, Alpha-SQL achieves a +5.8% absolute gain in execution accuracy over the strongest baseline evaluated here (CHESS-SQL). This result strongly suggests that the performance improvements demonstrated by Alpha-SQL are substantially attributed to our proposed MCTS framework and reasoning path exploration, rather than solely being an effect of the base model choice. We will add these crucial comparative results to the relevant tables in the revised manuscript.

2. Computational Cost Analysis (Addressing Concerns on Cost, Weakness, Q2b)

Reviewer Concerns: Computational cost not discussed; method seems costly; need for analysis considering forward passes, self-consistency samples, tokens, execution time; comparison needed using same self-consistency N.

• Our Response: We agree that a discussion of computational cost is essential for contextualizing Alpha-SQL's performance gains, especially given its MCTS nature. We have analyzed the average computational cost per query on the BIRD dev set using the Qwen2.5-Coder-Instruct-7B model. The table above (in point 1) includes Alpha-SQL and the baselines run on the same model.
• In summary, Alpha-SQL delivers state-of-the-art accuracy among these methods on the same base model, demonstrating better token efficiency than the next best method (CHESS-SQL), but this comes at the cost of increased latency. In future work, we plan to optimize the MCTS process to mitigate this latency, potentially exploring strategies such as heuristic pruning and SQL execution caching mechanisms.

3. Depth of Analysisn (Addressing Concerns on Claims, Analysis, Q3)

• Our Response: We appreciate the reviewer's push for deeper analysis beyond aggregate execution accuracy to better illustrate how Alpha-SQL improves text-to-SQL generation.
  • As detailed in our response to Reviewer 5kbR's point 5 ("Analysis of Common Reasoning Paths"), our analysis of the reasoning paths chosen by Alpha-SQL demonstrates its ability to dynamically adapt its strategy based on database complexity (e.g., selectively including 'Schema Selection' only when needed). This provides initial insight into its advantages over fixed-sequence methods.

Dear Reviewer,

Thank you for your thorough review and constructive feedback. We appreciate your positive assessment and valuable suggestions, which will help improve our paper's clarity.

1. Terminology ("Partial SQL Query States")

• Our Response: Thank you for highlighting this ambiguity. We agree "reasoning state" or "contextual state" is more accurate for internal nodes representing accumulated context (selected schema, functions, etc.) prior to the final SQL generation action. We will revise the manuscript accordingly.

2. Self-Consistency Sample Generation

• Our Response: Thanks for the question. There are two distinct stages: 1) During MCTS, we use deterministic sampling (Temperature=0) for the primary candidate SQL from a given reasoning state. 2) For reward calculation, we use stochastic sampling (Temperature =1.0) to generate N diverse SQL samples from the exact same reasoning state. The reward is based on execution agreement between the deterministic query and the diverse set. We will clarify this process in the revision.

3. Inference-Time Cost Evaluation

• Our Response: This is a very relevant point. The inference cost, particularly in terms of LLM calls and latency, is an important consideration for MCTS-based methods. Due to rebuttal length limitations, we kindly refer the reviewer to our detailed response to Reviewer guJX (Point 1 & 2). We believe those sections fully address the concerns regarding token usage and latency analysis.

4. Comparison with "SQL Generation" Action Alone

• Our Response: This is an excellent suggestion for a baseline. This baseline, representing a direct prompting approach using only the 'SQL Generation' action with the initial question and schema, corresponds to the "Direct Prompting" results in our experiments. | Base LLM | Direct Prompting | Directly Promoting with Self-consistency | Alpha-SQL | |------------------------------|------------------|------------------------------------------|-----------| | Qwen2.5-Coder-Instruct-7B | 48.4% | 56.3% | 66.8% | | Qwen2.5-Coder-Instruct-14B | 57.4% | 62.3% | 68.7% | | Qwen2.5-Coder-Instruct-32B | 62.6% | 63.4% | 69.7% |
• The results clearly show Alpha-SQL significantly outperforms direct, single-step prompting across all model sizes, demonstrating the substantial benefit of the MCTS framework for dynamic path construction and context gathering. We will ensure this is clearly discussed.

5. Analysis of Common Reasoning Paths

• Our Response: A valuable suggestion for deeper insight. Our analysis (Qwen-7B on BIRD-dev) shows Alpha-SQL dynamically adapts reasoning paths based on database complexity, unlike fixed-sequence methods.
• We analyzed the reasoning paths selected by Alpha-SQL (based on Qwen2.5-Coder-7B) on the BIRD-dev dataset. Our findings reveal interesting patterns that demonstrate the adaptive nature of Alpha-SQL's reasoning:
  • Simple Schema Databases: For databases with relatively simple schemas (e.g., 'toxicology' with 4 tables, avg. 2.8 columns/table), the most frequently selected reasoning path followed the pattern: Root -> Identify Column Values -> SQL Generation -> End. Notably, this common path omits the 'Schema Selection' action. This suggests that for simpler schemas where most tables/columns might be relevant or easily inferred, Alpha-SQL learns that the computational effort or potential risk of error from explicitly running 'Schema Selection' outweighs its benefits, adapting by taking a more direct path to SQL generation.
  • Complex Schema Databases: In contrast, for databases with more complex schemas (e.g., 'student_club' with 8 tables, avg. 6 columns/table; 'california_schools' with 3 tables, avg. 29.3 columns/table), the most common reasoning path pattern included explicit schema filtering: Root -> Identify Column Values -> Identify Column Functions -> Schema Selection -> SQL Generation -> End. The inclusion of the 'Schema Selection' action in these cases highlights Alpha-SQL's ability to recognize when detailed schema filtering is necessary due to complexity and dynamically incorporate the appropriate actions into the reasoning process.
  • Comparison to Fixed Sequences: This flexibility, driven by MCTS, demonstrates an advantage over rigid pipeline approaches. Leveraging the MCTS framework, it dynamically adapts the reasoning path based on the perceived complexity and characteristics of the specific database and query, selecting actions only when deemed beneficial by the search process. We will add details of this analysis, including path examples, to the Appendix in the revised manuscript.

Note: Due to the character limit for replies, we will discuss your other two questions, "Rollouts vs. Path Diversity" and "Using Labeled Data for Reward vs. Fine-tuning," later.