TTD-SQL: Tree-Guided Token Decoding for Efficient and Schema-Aware SQL Generation

Chetan Sharma, Ramasuri Narayanam, Soumyabrata Pal, Kalidas Yeturu, Shiv Kumar Saini, Koyel MukherjeeEMNLP 2025 · OpenReview

TL;DR

This paper introduces TTD-SQL, a novel framework that significantly speeds up SQL generation from natural language by intelligently pre-computing schema-aware decision trees. This approach reduces inference latency by up to 19.96% and improves the accuracy of generated SQL by mitigating schema hallucinations, making LLMs more practical for real-time data analysis.

What Problem Does This Paper Address?

Natural language interfaces (NLIs) are crucial for democratizing data analytics, allowing non-technical users to query databases using plain English. Text-to-SQL systems, which translate these queries into SQL, have seen remarkable progress with Large Language Models (LLMs). However, deploying these systems in real-world, high-stakes applications like finance or healthcare faces two major hurdles:

  1. Inference Latency: LLMs typically generate SQL tokens sequentially (autoregressive decoding). This process involves a full forward pass for each token, leading to slow query responses. For instance, on the BIRD benchmark, some models take over 14 seconds per query.
  2. Schema Hallucinations: LLMs can sometimes generate invalid SQL, such as referencing non-existent columns or tables, leading to incorrect data retrieval and eroding user trust.

Existing solutions often trade off efficiency for correctness or vice-versa, leaving a gap for a method that optimizes both.

Methods

The core innovation is Tree-Guided Token Decoding (TTD-SQL), a lightweight framework that integrates SQL grammar and database schema constraints directly into the LLM's decoding process without altering the LLM itself.

Here's how it works:

  • Schema-Aware Token Trees: TTD pre-computes token-level decision trees. These trees map SQL keywords, table names, and column identifiers to potential continuations.
  • Deterministic Auto-fill: For unambiguous schema elements, TTD can deterministically "auto-fill" tokens. For example, if the LLM generates "Song_", TTD knows the next token is likely "ID" (e.g., for "Song_ID") and can directly append it, skipping a redundant LLM forward pass.
  • Hybrid Approach: When faced with ambiguity or complex reasoning, TTD seamlessly reverts to standard LLM autoregressive generation. This hybrid strategy balances efficiency with generative flexibility.
  • Offline Tree Construction: The schema trees are built offline in a three-stage pipeline: schema augmentation (generating variations of schema elements), tokenization-aware decomposition (using the LLM's tokenizer), and tree assembly (building prefix trees).

Datasets

The paper evaluates TTD-SQL on two standard text-to-SQL benchmarks:

  • Spider: A large-scale, complex dataset with 992 questions across 19 databases.
  • BIRD (Minidev): A lightweight dataset comprising 500 high-quality question-SQL pairs from 11 databases, designed for evaluating real-world scenarios.

Key Insights and Ideas

  • Schema Constraints as Decoding Guides: The paper demonstrates that embedding schema knowledge directly into the decoding process, rather than just through prompting or fine-tuning, is highly effective for both speed and accuracy.
  • The Power of Deterministic Transitions: By identifying and auto-filling predictable token sequences based on schema, TTD significantly reduces the number of LLM forward passes required, directly translating to faster inference.
  • Tokenization Matters: The granularity of tokenization significantly impacts TTD's performance. Models with finer-grained tokenization (e.g., splitting cust_id into cust, _, id) allow for deeper decision paths in the schema trees and thus higher auto-fill rates and speedups.
  • Bridging the Gap: TTD successfully bridges the gap between rigid, traditional parser-based methods (which are accurate but slow) and flexible LLM generation (which is fast but prone to errors), offering a practical middle ground.

Key Results

  • Latency Reduction: TTD achieves significant speedups, with token rates improving by up to 19.96% over standard autoregressive decoding (e.g., CodeLlama on Spider). For Qwen2.5-Coder-32B and Llama-70B on BIRD, TTD achieved over 1-second gains in 51% and 60% of queries, respectively.
  • Hallucination Mitigation: TTD substantially reduces schema hallucinations, leading to executable SQL rates improving by up to +17.7% (e.g., CodeLlama on BIRD).
  • Accuracy Maintained: TTD generally matches or exceeds the execution accuracy of standard autoregressive decoding, and in many cases, outperforms other grammar-constrained methods.
  • Model Agnosticism: The framework demonstrates broad applicability, showing consistent benefits across five diverse LLMs (CodeLlama, Phi-4, Qwen2.5, Granite, Llama-70B) with varying parameter sizes and training paradigms.

Limitations and Future Work

  • Static Schema Requirement: TTD currently relies on pre-computed trees for fixed schemas. The authors acknowledge that dynamic or evolving databases would require efficient incremental tree update mechanisms, which is a direction for future work.
  • Tokenization Sensitivity: The performance gains are dependent on how schema items are tokenized by the LLM's tokenizer. While this is an inherent property of LLMs, it highlights the importance of tokenizer choice.
  • Enterprise Schema Potential: The authors suggest that TTD's benefits could be amplified in enterprise settings with more complex, proprietary schemas, where deeper token trees could lead to even more deterministic predictions and stronger hallucination prevention.

Summary updated

Abstract

Natural language interfaces (NLIs) democratize data analytics by enabling non-technical users to query relational databases via Text-to-SQL systems. While large language models (LLMs) have achieved state-of-the-art accuracy on benchmarks like Spider and BIRD, two critical challenges persist for real-time deployment: (1) inference latency due to sequential autoregressive decoding (e.g., average inference latency on BIRD (Minidev) is 14.3 seconds per query for Qwen2.5-Coder32B and 22.86 seconds for Llama-70B.), and (2) schema hallucinations (e.g., invalid column references like customer_ids instead of cust_id). (2) schema hallucinations (e.g., Qwen2.5-Coder-32B Instruct generated ... COUNT(users.UserId) ... = users.Id ..., using users.Id correctly in JOIN but hallucinating users.UserId in COUNT). To address these, we propose Tree-Guided Token Decoding (TTD-SQL), a lightweight framework that integrates SQL grammar and database schema constraints into the decoding process without modifying the underlying LLM. TTD precomputes token-level decision trees over SQL keywords, table names, and column identifiers, enabling deterministic “auto-fill” transitions for uniquely determined tokens (e.g., “Song_” → “ID”) while retaining flexibility for unconstrained reasoning. Across five LLMs (CodeLlama, Phi-4, Qwen2.5, Granite, Llama70B), TTD achieves up to 19.96% token-rate speedups by eliminating redundant forward passes (e.g., CodeLlama: 8.97→10.76 tokens/s on Spider) and reduces schema hallucinations by +17.7% in executable-SQL rates (e.g., CodeLlama on BIRD). By bridging rigid parser based methods and flexible LLM generation, TTD offers a practical path toward reliable, high-performance SQL generation in both public benchmarks and enterprise settings.
BibTeX
@inproceedings{sharma2025ttd,
  author = {Chetan Sharma and Ramasuri Narayanam and Soumyabrata Pal and Kalidas Yeturu and Shiv Kumar Saini and Koyel Mukherjee},
  title = {{TTD-SQL: Tree-Guided Token Decoding for Efficient and Schema-Aware SQL Generation}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2025},
  url = {https://openreview.net/forum?id=SkhiW9jvaY},
}
Figure