# Knapsack Optimization-based Schema Linking for LLM-based Text-to-SQL Generation

arXiv: https://arxiv.org/abs/2502.12911 · HTML: https://mlsanity.com/paper/2502.12911/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 51 of its 69 references that are in the map.
- First posted on arXiv 18 Feb 2025.

## Builds on (most cited first, 30 of 51)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Finetuned Language Models Are Zero-Shot Learners](https://mlsanity.com/paper/2109.01652/) (2021)
- [SimCSE: Simple Contrastive Learning of Sentence Embeddings](https://mlsanity.com/paper/2104.08821/) (2021)
- [DeepSeek-Coder: When the Large Language Model Meets Programming -- The Rise of Code Intelligence](https://mlsanity.com/paper/2401.14196/) (2024)
- [Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task](https://mlsanity.com/paper/1809.08887/) (2018)
- [Can LLM Already Serve as A Database Interface? A BIg Bench for Large-Scale Database Grounded Text-to-SQLs](https://mlsanity.com/paper/2305.03111/) (2023)
- [Prompt Programming for Large Language Models: Beyond the Few-Shot Paradigm](https://mlsanity.com/paper/2102.07350/) (2021)
- [StarCoder 2 and The Stack v2: The Next Generation](https://mlsanity.com/paper/2402.19173/) (2024)
- [DIN-SQL: Decomposed In-Context Learning of Text-to-SQL with Self-Correction](https://mlsanity.com/paper/2304.11015/) (2023)
- [TaBERT: Pretraining for Joint Understanding of Textual and Tabular Data](https://mlsanity.com/paper/2005.08314/) (2020)
- [Text-to-SQL Empowered by Large Language Models: A Benchmark Evaluation](https://mlsanity.com/paper/2308.15363/) (2023)
- [Spider 2.0: Evaluating Language Models on Real-World Enterprise Text-to-SQL Workflows](https://mlsanity.com/paper/2411.07763/) (2024)
- [RESDSQL: Decoupling Schema Linking and Skeleton Parsing for Text-to-SQL](https://mlsanity.com/paper/2302.05965/) (2023)
- [CodeS: Towards Building Open-source Language Models for Text-to-SQL](https://mlsanity.com/paper/2402.16347/) (2024)
- [GraPPa: Grammar-Augmented Pre-Training for Table Semantic Parsing](https://mlsanity.com/paper/2009.13845/) (2020)
- [CHESS: Contextual Harnessing for Efficient SQL Synthesis](https://mlsanity.com/paper/2405.16755/) (2024)
- [C3: Zero-shot Text-to-SQL with ChatGPT](https://mlsanity.com/paper/2307.07306/) (2023)
- [MAC-SQL: A Multi-Agent Collaborative Framework for Text-to-SQL](https://mlsanity.com/paper/2312.11242/) (2023)
- [CHASE-SQL: Multi-Path Reasoning and Preference Optimized Candidate Selection in Text-to-SQL](https://mlsanity.com/paper/2410.01943/) (2024)
- [Structure-Grounded Pretraining for Text-to-SQL](https://mlsanity.com/paper/2010.12773/) (2020)
- [Where to Go Next for Recommender Systems? ID- vs. Modality-based Recommender Models Revisited](https://mlsanity.com/paper/2303.13835/) (2023)
- [Next-Generation Database Interfaces: A Survey of LLM-based Text-to-SQL](https://mlsanity.com/paper/2406.08426/) (2024)
- [A comprehensive evaluation of ChatGPT's zero-shot Text-to-SQL capability](https://mlsanity.com/paper/2303.13547/) (2023)
- [Towards Robustness of Text-to-SQL Models against Synonym Substitution](https://mlsanity.com/paper/2106.01065/) (2021)
- [A Survey of Graph Retrieval-Augmented Generation for Customized Large Language Models](https://mlsanity.com/paper/2501.13958/) (2025)

## Built on by (most cited first, 9 of 9)

- [LinearRAG: Linear Graph Retrieval Augmented Generation on Large-scale Corpora](https://mlsanity.com/paper/2510.10114/) (2025)
- [Table-R1: Region-based Reinforcement Learning for Table Understanding](https://mlsanity.com/paper/2505.12415/) (2025)
- [FaithfulRAG: Fact-Level Conflict Modeling for Context-Faithful Retrieval-Augmented Generation](https://mlsanity.com/paper/2506.08938/) (2025)
- [Sparks of Tabular Reasoning via Text2SQL Reinforcement Learning](https://mlsanity.com/paper/2505.00016/) (2025)
- [ReEx-SQL: Reasoning with Execution-Aware Reinforcement Learning for Text-to-SQL](https://mlsanity.com/paper/2505.12768/) (2025)
- [Enhancing Text2Cypher with Schema Filtering](https://mlsanity.com/paper/2505.05118/) (2025)
- [Rethinking Schema Linking: A Context-Aware Bidirectional Retrieval Approach for Text-to-SQL](https://mlsanity.com/paper/2510.14296/) (2025)
- [MoG: Mixture of Experts for Graph-based Retrieval-Augmented Generation](https://mlsanity.com/paper/2605.31010/) (2026)
- [BudgetSchemaBench: A Budget-Swept Diagnostic for Schema Context in Text-to-SQL](https://mlsanity.com/paper/2610.00092/) (2026)

## Abstract (arXiv)

Generating SQLs from user queries is a long-standing challenge, where the accuracy of initial schema linking significantly impacts subsequent SQL generation performance. However, current schema linking models still struggle with missing relevant schema elements or an excess of redundant ones. A crucial reason for this is that commonly used metrics, recall and precision, fail to capture relevant element missing and thus cannot reflect actual schema linking performance. Motivated by this, we propose enhanced schema linking metrics by introducing a restricted missing indicator. Accordingly, we introduce textbfunderlineKnunderlineapsack optimization-based underlineSchema underlineLinking underlineApproach (KaSLA), a plug-in schema linking method designed to prevent the missing of relevant schema elements while minimizing the inclusion of redundant ones. KaSLA employs a hierarchical linking strategy that first identifies the optimal table linking and subsequently links columns within the selected table to reduce linking candidate space. In each linking process, it utilizes a knapsack optimization approach to link potentially relevant elements while accounting for a limited tolerance of potentially redundant ones. With this optimization, KaSLA-1.6B achieves superior schema linking results compared to large-scale LLMs, including DeepSeek-V3 with the state-of-the-art (SOTA) schema linking method. Extensive experiments on Spider and BIRD benchmarks verify that KaSLA can significantly improve the SQL generation performance of SOTA Text2SQL models by substituting their schema linking processes. The code is available at https://github.com/DEEP-PolyU/KaSLA.