Enhancing SQL Query Generation with Neurosymbolic Reasoning

Henrijs Princis, Cristina David, Alan MycroftAAAI 2025 · DOI

TL;DR

This paper introduces Xander, a neurosymbolic architecture that enhances Large Language Models (LLMs) for SQL query generation. By integrating symbolic reasoning with LLMs, Xander explores the search space more efficiently, leading to significant improvements in both accuracy and runtime, even allowing smaller LMs to outperform much larger ones.

What Problem Does This Paper Address?

Generating accurate SQL queries from natural language descriptions is a challenging task for Language Models (LMs). While LMs have shown promise, they often struggle with the vast and complex search space of possible SQL queries. A key limitation is their tendency to follow a linear search strategy, committing to a single path and potentially missing optimal solutions. Furthermore, verifying the correctness of generated SQL queries typically requires full execution, which is computationally expensive and only possible after the entire query is formed. This paper addresses these issues by proposing a neurosymbolic approach that leverages symbolic reasoning to guide the LM's search more effectively and to enable early detection of errors.

Methods

Xander employs a neurosymbolic architecture that combines a pretrained LM with several symbolic modules. The core innovation is the use of Best-First Search (BFS) with backtracking to explore the solution space non-linearly, moving beyond the typical linear generation of LMs.

Key components include:

  • Symbolic Query Checker (PQC): This module checks incomplete SQL queries for validity before they are fully generated. This is crucial for pruning erroneous paths early, saving computational resources. It performs vocabulary, scope, and type checking.
  • Query Test-and-Repair (QTR): For complete queries, this module executes them and verifies their output against user-provided examples. If a query is incorrect, it attempts to repair it by making minor, systematic changes.
  • Standardised SQL: The authors introduce a normalized form of SQL that enforces uppercase keywords, includes all clauses, and expands aliases. This stricter syntax simplifies error detection and reduces stylistic variations that can confuse LMs.

The architecture is designed to be compatible with any pretrained LM, allowing for enhancement without modifying the LM itself.

Datasets

The primary dataset used for training and evaluation is Spider. The authors note that the original Spider dataset does not include output examples, so they generated these by executing the golden queries and taking the first returned tuple. They also rewrote the Spider dataset to conform to their Standardised SQL format.

Key Insights and Ideas

  • Neurosymbolic Reasoning for Efficiency: Combining symbolic reasoning with LMs can dramatically improve efficiency by intelligently exploring the search space, rather than relying solely on the LM's probabilistic predictions.
  • Early Error Detection is Crucial: The ability to check incomplete queries (via the Partial-Query Checker) is a significant advantage, allowing for early pruning of bad paths and avoiding wasted computation.
  • Standardised SQL Simplifies Learning: A normalized SQL syntax reduces ambiguity and stylistic noise, making it easier for LMs to learn and for symbolic checkers to identify errors.
  • Smaller Models Can Compete: Neurosymbolic approaches can bridge the gap between smaller, more efficient LMs and larger, more powerful (and expensive) ones, offering a compelling alternative to simply scaling model size.

Key Results

  • Xander significantly improves execution accuracy (average of 10.9%) and exact-match accuracy (average of 6.0%) compared to purely neural approaches.
  • It finds correct queries 28% faster.
  • A notable result is a CodeT5 small model (62M parameters) enhanced with Xander outperforming a four-times-larger CodeT5 base model (222M parameters).
  • Standardised SQL alone provides a substantial boost in execution accuracy (9.5% increase when a single attempt is allowed).
  • The Symbolic Query Checker is found to be 22% more accurate than a Neural Query Checker in identifying query mistakes.

Limitations and Future Work

  • Limitations of Standardised SQL: The authors acknowledge that some complex queries in the original Spider dataset cannot be expressed in Standardised SQL, leading to a reduction in the number of usable queries.
  • Neural Query Checker Performance: While explored, the Neural Query Checker was less accurate than the Symbolic Query Checker, particularly in recognizing runtime errors.
  • Future Work: The paper suggests exploring the Neural Query Checker further and investigating its potential for other tasks. The generalizability of the neurosymbolic approach to other code generation tasks beyond SQL is also a promising avenue. The authors also highlight the potential for further improvements by incorporating more sophisticated repair mechanisms.

Summary updated

BibTeX
@inproceedings{princis2025enhancing,
  author = {Henrijs Princis and Cristina David and Alan Mycroft},
  title = {{Enhancing SQL Query Generation with Neurosymbolic Reasoning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i19.34198},
}
Figure