Research map / Large language models / Agents, code and math
Enhancing SQL Query Generation with Neurosymbolic Reasoning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Xander, a neurosymbolic best-first search framework that wraps a fine-tuned LM with symbolic partial-query checking, fuzzing-based repair, and a Normalized SQL format to generate SQL from questions plus I/O examples.
Problem
Generating SQL queries from natural language questions plus user-provided input/output examples, where LMs make syntax, runtime and example errors and the solution space is large.
Approach
Explores a solution tree with Best-First Search and backtracking over LM token continuations, pruning partial queries with a symbolic checker (vocabulary, scope, type checks), repairing complete queries via Hamming-distance-one fuzzing, and using Normalized SQL to reduce stylistic variation.
Key results
- Xander increases average validation execution accuracy by 10.9% and reduces time per query by about 28% across LMs.
- CodeT5 small with Xander (78.6% execution accuracy) outperforms CodeT5 base without Xander (73.6%).
- Phi-1.5 with Xander reaches 72.0% execution accuracy versus 42.3% without it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add Xander | CodeT5 small · Spider validation | execution accuracy: 69.9 -> 78.6 | Helped |
| Add Xander | CodeT5 base · Spider validation | execution accuracy: 73.6 -> 80.5 | Helped |
| Add Xander | BART · Spider validation | exact match accuracy: 51.5 -> 39.0 | Hurt |
| Add Xander | Microsoft Phi-1.5 · Spider validation | execution accuracy: 42.3 -> 72.0 | Helped |
| Use Normalized SQL instead of SQL (ablation) | CodeT5 small, one attempt · Spider validation | execution accuracy: 48.7 -> 58.4 | Helped |
| Add examples to the input specification (ablation) | CodeT5 small with Normalized SQL, one attempt · Spider validation | execution accuracy: 58.4 -> 59.7 | Helped |
| Add PQC (ablation) | CodeT5 small with Normalized SQL and examples, one attempt · Spider validation | execution accuracy: 59.7 -> 63.9 | Helped |
| Allow multiple attempts instead of one attempt (ablation) | CodeT5 small with Normalized SQL and examples · Spider validation | execution accuracy: 59.7 -> 76.0 | Helped |
| Add PQC (ablation) | CodeT5 small with Normalized SQL and examples, multiple attempts · Spider validation | execution accuracy: 76.0 -> 78.4 | Helped |
| Add enumerative repair (ablation) | CodeT5 small with PQC and multiple attempts · Spider validation | execution accuracy: 78.4 -> 78.6 | No clear effect |
| Add enumerative repair (ablation) | CodeT5 base with PQC and multiple attempts · Spider validation | execution accuracy: 80.4 -> 80.5 | No clear effect |
| Add enumerative repair (ablation) | CodeT5 small with PQC and multiple attempts · Spider validation | validation time per sample: 10.2 -> 9.1 | Helped |
Surprising findings
- The neural query checker (NQC) reached only 46% accuracy versus 69% for the symbolic checker, suggesting actor-critic RL is not appropriate here.
- ChatGPT-3.5 (58.3% execution accuracy) underperforms several fine-tuned small LMs with Xander.
Limitations
- Normalized SQL forbids complex joins and aliases, excluding some Spider queries (about 1.5% use complex joins; self-joins removed).
- Requires example output tuples, which are hard to supply for aggregation queries.
- Evaluated only on Spider and small models; may help less for very large LMs.
Experimental setup
Datasets: Spider
Benchmarks: Spider validation set
Metrics: execution accuracy exact match accuracy validation time per sample
Baselines: CodeT5 small CodeT5 base BART CodeGen Microsoft Phi-1.5 ChatGPT-3.5 Picard Duoquest RASAT REDSQL
Builds on: Picard CodeRL Byte-Pair Encoding Distilled Test Suites
Closest papers by meaning
- Structure-Guided Large Language Models for Text-to-SQL Generation (ICML 2025 · similarity 0.88)
- Alpha-SQL: Zero-Shot Text-to-SQL using Monte Carlo Tree Search (ICML 2025 · similarity 0.88)
- CogSQL: A Cognitive Framework for Enhancing Large Language Models in Text-to-SQL Translation (AAAI 2025 · similarity 0.87)
- CHASE-SQL: Multi-Path Reasoning and Preference Optimized Candidate Selection in Text-to-SQL (ICLR 2025 · similarity 0.86)
- SQL-R1: Training Natural Language to SQL Reasoning Model By Reinforcement Learning (NeurIPS 2025 · similarity 0.86)
- ORACLE: Optimizing Reasoning Abilities of Large Language Models via Constraint-Led Synthetic Data Elicitation (AAAI 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.