Divide, Link, and Conquer: Recall-oriented Schema Linking for NL-to-SQL via Question Decomposition

Kiran Pradeep, Kirushikesh Db, Nishtha Madaan, Sameep Mehta, Pushpak BhattacharyyaEMNLP 2025

TL;DR

This paper introduces RoSL, a novel framework that enhances Natural Language to SQL (NL-to-SQL) systems by applying question decomposition before schema linking. This approach significantly improves schema recall and execution accuracy for smaller, more deployable Large Language Models (LLMs) without requiring task-specific fine-tuning, addressing privacy and resource constraints in enterprise settings.

What Problem Does This Paper Address?

The increasing demand for efficient access to structured data by non-technical users has driven the development of Natural Language to SQL (NL-to-SQL) systems. While powerful proprietary LLMs achieve state-of-the-art results, their use raises privacy concerns. Open-source LLMs offer an alternative, but high-performing variants are resource-intensive. Smaller, more deployable open-source LLMs are promising but often require extensive fine-tuning, limiting their flexibility. Existing NL-to-SQL systems typically perform schema linking (identifying relevant tables and columns) and SQL generation. However, for smaller LLMs, schema linking is crucial but can be a bottleneck, often sacrificing recall for precision. This paper addresses the challenge of improving schema linking for smaller LLMs to boost overall NL-to-SQL performance without fine-tuning, making these systems more practical for real-world deployment.

Methods

The core innovation of RoSL is the introduction of question decomposition at the schema linking stage. Unlike prior work that applied decomposition during SQL generation, RoSL first breaks down complex NL questions into simpler sub-questions. This is handled by a Question Decomposer Agent. The rationale is that smaller LLMs struggle with complex, multi-entity queries in a single pass. By decomposing, the model can focus on smaller, more manageable parts, leading to better schema element retrieval.

After decomposition, a Schema Selector Agent identifies a reduced schema relevant to each sub-question. Finally, a SQL Generator Agent produces the SQL query using the combined relevant schema information. This modular, plug-and-play framework does not require task-specific fine-tuning, making it adaptable to various open-source LLMs. The authors explore different decomposition strategies, including constrained variants where sub-questions are limited to single tables.

Datasets

The paper evaluates its approach on two standard NL-to-SQL benchmarks:

  • Spider: A large-scale, cross-domain benchmark known for testing generalization across unseen database schemas.
  • BIRD: A more recent benchmark reflecting real-world enterprise scenarios, characterized by larger schemas and more complex, multi-hop queries.

For ablation studies, the authors use the subsampled_dev split of the BIRD dataset, as introduced by Talaei et al. (2024).

Key Insights and Ideas

  • Decomposition at Schema Linking is Key: Applying question decomposition before schema linking, rather than during SQL generation, is a novel and effective strategy for improving schema recall, especially for smaller LLMs.
  • Smaller LLMs Benefit Greatly: While larger models might implicitly handle schema relevance, smaller LLMs are highly sensitive to schema noise, making explicit and improved schema linking via decomposition critical for their performance.
  • Recall Over Precision Trade-off: The authors demonstrate that their approach improves schema linking recall significantly, which in turn leads to better overall execution accuracy, even if it means retrieving slightly more schema elements initially.
  • Plug-and-Play for Accessibility: RoSL's fine-tuning-free nature makes it highly adaptable and deployable with various open-source LLMs, addressing practical concerns of privacy and resource constraints in enterprise environments.
  • Complexity Matters: The number of sub-questions generated generally increases with query complexity, indicating that decomposition helps models tackle more challenging queries by breaking them down.

Key Results

  • On the BIRD benchmark, RoSL (SL+QD) achieved the highest execution accuracy for three out of four tested smaller LLMs.
  • For ibm-granite/granite-3.3-8b-instruct, RoSL improved execution accuracy from 37.31% (NoSL) to 40.35%, a significant gain.
  • RoSL improved schema linking recall by 25.1% and execution accuracy by 8.2% on the BIRD benchmark using ibm-granite/granite-3.3-8b-instruct.
  • Across models, RoSL consistently boosted schema linking recall, with notable improvements for smaller models like ibm-granite/granite-3.3-8b-instruct (from 0.5334 to 0.6673) and Llama-3.1-8B-Instruct (from 0.7008 to 0.8446).
  • RoSL achieves competitive performance with proprietary models on the Spider benchmark, reaching 67.89% accuracy with Llama-3.1-8B and 75.43% with phi-4-14B, without fine-tuning.
  • Despite increased LLM calls and tokens, the effective per-query latency with 8 parallel workers for RoSL was 23.1s, demonstrating practical efficiency.

Limitations and Future Work

  • Decomposition Quality: The effectiveness of RoSL hinges on the quality of the generated sub-questions. Poor decompositions could lead to irrelevant or incomplete schema retrieval.
  • Inference Overhead: Introducing question decomposition increases latency due to additional LLM calls. While RoSL's effective latency is manageable with parallel workers, it's a trade-off for improved accuracy.
  • SQL Recomposition Challenge: Experimenting with decomposing SQL queries and then recomposing them led to degraded performance, suggesting challenges in maintaining logical consistency and join semantics.
  • Constraint Sensitivity: Highly constrained decomposition variants (e.g., SL+TableQD) can underperform due to overly restrictive assumptions.

Future work includes exploring dynamic decomposition strategies, LLM-driven sub-question validation, and reinforcement learning to jointly optimize decomposition and SQL generation quality.

Summary updated

BibTeX
@inproceedings{pradeep2025divide,
  author = {Kiran Pradeep and Kirushikesh Db and Nishtha Madaan and Sameep Mehta and Pushpak Bhattacharyya},
  title = {{Divide, Link, and Conquer: Recall-oriented Schema Linking for NL-to-SQL via Question Decomposition}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2025},
}
Figure