💬 NLP

LEAF-SQL: Level-wise Exploration with Adaptive Fine-graining for Text-to-SQL Skeleton Prediction

LEAF-SQL is a novel framework that enhances Text-to-SQL performance on complex queries by reframing skeleton prediction as a coarse-to-fine tree search process, utilizing a three-level hierarchy and specialized agents to systematically explore and adaptively refine diverse structural hypotheses, thereby achieving state-of-the-art execution accuracy on the BIRD benchmark.

Original authors: Zhao Tan, Xiping Liu, Qing Shu, Qizhi Wan, Dexi Liu, Changxuan Wan

Published 2026-05-12

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Zhao Tan, Xiping Liu, Qing Shu, Qizhi Wan, Dexi Liu, Changxuan Wan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to give a complex order to a very smart, but sometimes overly literal, robot chef. You want a specific dish, but the robot needs to know the exact recipe steps (the "SQL") to get it right from a massive pantry (the "database").

The paper LEAF-SQL is about teaching this robot a better way to figure out the recipe when the order gets complicated.

Here is the breakdown of the problem and their solution, using simple analogies:

The Problem: The "One-and-Done" Mistake

Previously, when people asked the robot for a complex dish (like "Find the top 10 customers who spent the most, but only if they bought items from the 'Electronics' section"), the robot would try to guess the entire recipe in one single leap.

The Risk: If the robot guessed the wrong structure for the first step (e.g., it thought you wanted a list instead of a summary), the whole recipe failed. It was like trying to build a house by guessing the location of every single brick at once. If you get the foundation wrong, the house collapses.
The Old Way: Most methods tried to predict the final, detailed structure immediately. If they got it wrong, there was no way to fix it.

The Solution: LEAF-SQL (The "Architect's Search")

The authors propose a new method called LEAF-SQL. Instead of guessing the final recipe all at once, they treat it like a tree search where the robot explores different possibilities, starting with a rough sketch and slowly adding details.

Think of it like a detective solving a mystery or an architect designing a building:

Start with a Rough Sketch (Coarse Level):
First, the robot asks: "Do we need a list? Do we need a summary? Do we need to combine two lists?" It doesn't worry about specific ingredients yet. It just draws a basic outline.
- Analogy: Drawing a stick figure of a house. You know it has a roof and walls, but you don't know the color of the bricks yet.
Add Details Gradually (Fine-Graining):
Once the basic shape looks right, the robot starts filling in the blanks. "Okay, this wall needs a window here. This roof needs a chimney."
- Analogy: Moving from the stick figure to a blue-print, and then to a 3D model with specific materials.
The Two Special Agents (The Team):
To make this work, the system uses two specialized "agents" (AI helpers):
- The Architect (Skeleton Formulation Agent): This agent is the creative one. It looks at the current sketch and says, "What if we tried adding a sub-basement here?" or "What if we connected these two rooms differently?" It generates many different versions of the recipe structure.
- The Inspector (Skeleton Evaluation Agent): This agent is the critical thinker. It looks at the Architect's new ideas and says, "Wait, that basement design doesn't make sense for this question," or "That connection is impossible." It prunes (cuts off) the bad ideas immediately so the system doesn't waste time on them.
The Result: A Menu of Options:
Instead of betting on just one recipe, LEAF-SQL produces a menu of several different, valid recipe structures.
- For simple questions, it might confidently pick the most detailed, fancy recipe.
- For very hard, confusing questions, it might stick to a simpler, safer recipe structure that is less likely to fail.
- Finally, it tries all the recipes in the menu and picks the one that actually works (the one that gives the correct answer).

Why This is a Big Deal

The paper claims that this "search and refine" approach is much better than the old "guess it all at once" method, especially for hard problems.

Flexibility: If one path leads to a dead end, the system can backtrack and try a different path without starting over from scratch.
Adaptability: It knows when to be bold (using complex structures for easy questions) and when to be safe (using simple structures for confusing questions).
Performance: In their tests (specifically on a benchmark called BIRD, which is like a "final exam" for database questions), this method achieved a 71.6% success rate, beating other top methods. It proved that by exploring multiple possibilities and filtering out the bad ones, the robot chef can cook much more complex dishes correctly.

Summary

LEAF-SQL stops the AI from trying to jump to the finish line. Instead, it teaches the AI to walk step-by-step: draw a rough map, check if the map makes sense, add details, check again, and finally, try the best few maps to see which one leads to the treasure. This makes it much harder for the AI to get lost in complex logic.

Technical Summary: LEAF-SQL

Problem Statement

Text-to-SQL aims to translate natural language questions into executable SQL queries, enabling non-experts to access databases. While Large Language Models (LLMs) have achieved state-of-the-art performance on benchmarks like Spider and BIRD through prompting, they struggle with complex queries involving deeply nested logic or multiple clauses.

Existing approaches often utilize SQL skeletons (intermediate representations of query logic) to decompose the task into "Text-to-Skeleton" and "Skeleton-to-SQL" steps. However, current skeleton-based methods suffer from two critical limitations:

Limited Exploration of Alternative Structures: Most methods commit to predicting a single skeleton in an "all-or-nothing" strategy. If this single structural hypothesis is flawed, the entire generation process fails without opportunity for correction.
Simple Reasoning Mechanism: Current approaches typically attempt to generate a detailed, fine-grained skeleton in a single step. This forces the model to resolve all structural complexities simultaneously, lacking a mechanism to begin with a high-level plan and progressively refine details.

Methodology: LEAF-SQL

The authors propose LEAF-SQL (Level-wise Exploration with Adaptive Fine-graining for Text-to-SQL Skeleton Prediction), a framework that reframes skeleton prediction as a coarse-to-fine tree search process. Instead of a single-step prediction, LEAF-SQL systematically explores diverse structural hypotheses and adaptively determines the appropriate level of detail.

The framework consists of three primary modules:

1. Level-wise Skeleton Search (LWSS)

This module formalizes skeleton prediction as a search problem within a structured tree space, progressing through three phases:

Three-Level Skeleton Hierarchy: To guide the search, the authors define a hierarchy derived from the Abstract Syntax Tree (AST) of queries:
- Base Level: Contains top-level clause nodes (e.g., SELECT, FROM, WHERE), capturing the fundamental logical structure.
- Expanded Level: Incorporates nested structures (e.g., subqueries within WHERE), revealing complex relationships.
- Detailed Level: Specifies granular details for placeholders and explicit table join conditions, mirroring the final SQL structure.
Skeleton Formulation Agent (SkeFor): An LLM-based agent responsible for generating new branches. It proposes diverse, more detailed skeleton candidates from a parent node. Its strategy is adaptive:
- Base Phase: Generates diverse foundational skeletons.
- Expanded Phase: Iteratively explores the next nested level.
- Detailed Phase: Specifies placeholder details and join conditions.
Skeleton Evaluation Agent (SkeEva): A specialized, fine-tuned small language model acting as a quality gatekeeper. It evaluates candidate skeletons for semantic alignment with the question and database schema. It prunes low-quality or incorrect branches to prevent combinatorial explosion and guide the search toward promising paths.

The search terminates when a node reaches the "Detailed" granularity or when all potential children of a valid node are pruned. The output is a set of structurally diverse and granularity-adaptive skeleton candidates.

2. SQL Generation

Given the set of skeleton candidates ( $S$ ), this module uses an LLM with zero-shot prompting to fill each skeleton with specific database schema elements (tables, columns) to produce a set of executable SQL queries ( $Y$ ). The skeleton serves as a structural guide to constrain the LLM's output.

3. Result Selection

To determine the final answer, the framework executes all valid SQL candidates. Queries resulting in errors or empty sets are discarded. The remaining queries are grouped by their execution results. The group with the largest number of queries is selected as the most likely correct answer. In the event of a tie, an LLM acts as an arbitrator to select the best result.

Key Contributions

Novel Framework: The proposal of LEAF-SQL, which redefines skeleton prediction as a coarse-to-fine tree search, enabling systematic exploration of diverse structural hypotheses and adaptive granularity adjustment.
Technical Components: The design of a three-level skeleton hierarchy, a Skeleton Formulation Agent for generating diverse branches, and a Skeleton Evaluation Agent for intelligent pruning.
Empirical Validation: Comprehensive experiments demonstrating consistent performance improvements across various LLM backbones on multiple benchmarks.

Experimental Results

The authors evaluated LEAF-SQL on five benchmarks: Spider, BIRD, SYN, REALISTIC, and DK.

BIRD Benchmark (Hidden Test Set): LEAF-SQL achieved an Execution Accuracy (EX) of 71.6% using GPT-4o, outperforming leading search-based (Alpha-SQL) and skeleton-based methods. This represents a significant improvement over the previous state-of-the-art.
BIRD Dev Set: Achieved 73.5% EX with Gemini-2.5-Pro.
Spider Dev Set: Achieved 89.7% EX with Gemini-2.5-Pro.
Complex Queries: The method showed particular strength on challenging queries. On the BIRD-Challenging subset, LEAF-SQL with Gemini-2.5-Pro reached 64.1% EX, surpassing MCTS-SQL by 7.3 points.
Robustness: On robustness benchmarks (SYN, REALISTIC, DK), LEAF-SQL consistently outperformed baselines, achieving an average accuracy of 79.2% with GPT-4o.

Ablation Studies confirmed the necessity of each component:

Removing diversity (single-path search) caused a 4.7-point drop.
Removing pruning (brute-force expansion) caused a 2.8-point drop.
Replacing voting with random selection caused a 3.1-point drop.

Efficiency: Despite the search overhead, asynchronous streaming and demonstration pruning keep the end-to-end latency around 12 seconds, making it practically competitive.

Significance and Claims

The paper claims that LEAF-SQL addresses the fragility of single-hypothesis skeleton prediction by introducing a progressive, search-based paradigm. By decomposing the task into levels (Base, Expanded, Detailed) and validating intermediate steps, the framework balances the high potential of fine-grained skeletons with the reliability of coarse-grained ones.

The authors emphasize that their approach provides a stronger foundation for Text-to-SQL generation by:

Exploring multiple valid logical structures rather than committing to a single guess.
Dynamically adapting skeleton granularity based on task complexity (e.g., falling back to coarser skeletons for difficult queries where fine-grained prediction is risky).
Achieving new state-of-the-art results on the challenging BIRD benchmark, affirming the effectiveness of tree-search-based skeleton prediction for complex queries.

The authors acknowledge limitations, noting that the framework currently incurs higher latency than single-pass methods due to multiple LLM interactions, making it less suitable for strictly real-time applications, and that its stability on large enterprise schemas requires further validation.