# Graph-Reward-SQL: Execution-Free Reinforcement Learning for Text-to-SQL via Graph Matching and Stepwise Reward

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in Process reward models for reasoning, one of 10 directions in LLM alignment / RLHF / preference optimisation.
- Builds on 29 of its 43 references that are in the map.
- First posted on arXiv 18 May 2025.

## Placed in

- LLM alignment / RLHF / preference optimisation / [Process reward models for reasoning](https://mlsanity.com/alignment/process-reward-models-for-reasoning/)

## Builds on (most cited first, 29 of 29)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [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)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [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)
- [Seq2SQL: Generating Structured Queries from Natural Language using Reinforcement Learning](https://mlsanity.com/paper/1709.00103/) (2017)
- [DIN-SQL: Decomposed In-Context Learning of Text-to-SQL with Self-Correction](https://mlsanity.com/paper/2304.11015/) (2023)
- [RAT-SQL: Relation-Aware Schema Encoding and Linking for Text-to-SQL Parsers](https://mlsanity.com/paper/1911.04942/) (2019)
- [Text-to-SQL Empowered by Large Language Models: A Benchmark Evaluation](https://mlsanity.com/paper/2308.15363/) (2023)
- [Towards Complex Text-to-SQL in Cross-Domain Database with Intermediate Representation](https://mlsanity.com/paper/1905.08205/) (2019)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [CodeS: Towards Building Open-source Language Models for Text-to-SQL](https://mlsanity.com/paper/2402.16347/) (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)
- [Semantic Evaluation for Text-to-SQL with Distilled Test Suites](https://mlsanity.com/paper/2010.02840/) (2020)
- [DeepSpeed-Chat: Easy, Fast and Affordable RLHF Training of ChatGPT-like Models at All Scales](https://mlsanity.com/paper/2308.01320/) (2023)
- [MCS-SQL: Leveraging Multiple Prompts and Multiple-Choice Selection For Text-to-SQL Generation](https://mlsanity.com/paper/2405.07467/) (2024)
- [ACECODER: Acing Coder RL via Automated Test-Case Synthesis](https://mlsanity.com/paper/2502.01718/) (2025)
- [Exploring Chain-of-Thought Style Prompting for Text-to-SQL](https://mlsanity.com/paper/2305.14215/) (2023)
- [SQL-R1: Training Natural Language to SQL Reasoning Model By Reinforcement Learning](https://mlsanity.com/paper/2504.08600/) (2025)
- [Reasoning-SQL: Reinforcement Learning with SQL Tailored Partial Rewards for Reasoning-Enhanced Text-to-SQL](https://mlsanity.com/paper/2503.23157/) (2025)
- [Synthesizing Text-to-SQL Data from Weak and Strong LLMs](https://mlsanity.com/paper/2408.03256/) (2024)
- [Neural Subgraph Matching](https://mlsanity.com/paper/2007.03092/) (2020)
- [Reward-SQL: Boosting Text-to-SQL via Stepwise Execution-Aware Reasoning and Process-Supervised Rewards](https://mlsanity.com/paper/2505.04671/) (2025)
- [Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources](https://mlsanity.com/paper/1802.10233/) (2018)
- [Reward Design For An Online Reinforcement Learning Algorithm Supporting Oral Self-Care](https://mlsanity.com/paper/2208.07406/) (2022)

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

- [CogniSQL-R1-Zero: Lightweight Reinforced Reasoning for Efficient SQL Generation](https://mlsanity.com/paper/2507.06013/) (2025)
- [Beyond Query-Level Comparison: Fine-Grained Reinforcement Learning for Text-to-SQL with Automated Interpretable Critiques](https://mlsanity.com/paper/2511.22258/) (2025)
- [AGRO-SQL: Agentic Group-Relative Optimization with High-Fidelity Data Synthesis](https://mlsanity.com/paper/2512.23366/) (2025)
- [SteinerSQL: Graph-Guided Mathematical Reasoning for Text-to-SQL Generation](https://mlsanity.com/paper/2509.19623/) (2025)
- [Progress-SQL: Improving Reinforcement Learning for Text-to-SQL via Progressive Rewards](https://mlsanity.com/paper/2606.06825/) (2026)
- [EXPO-SQL: Execution-based Clause-level Policy Optimization for Text-to-SQL](https://mlsanity.com/paper/2606.23693/) (2026)
- [CAPER: Clause-Aligned Process Supervision for Text-to-SQL](https://mlsanity.com/paper/2606.03327/) (2026)

## Abstract (arXiv)

Reinforcement learning (RL) has been widely adopted to enhance the performance of large language models (LLMs) on Text-to-SQL tasks. However, existing methods often rely on execution-based or LLM-based Bradley-Terry reward models. The former suffers from high execution latency caused by repeated database calls, whereas the latter imposes substantial GPU memory overhead, both of which significantly hinder the efficiency and scalability of RL pipelines. To this end, we propose a novel reward model framework for RL-based Text-to-SQL named Graph-Reward-SQL, which employs the GMNScore outcome reward model. We leverage SQL graph representations to provide accurate reward signals while significantly reducing time cost and GPU memory usage. Building on this foundation, we further introduce StepRTM, a stepwise reward model that provides intermediate supervision over Common Table Expression (CTE) subqueries. This encourages both functional correctness and readability of SQL. Extensive comparative and ablation experiments on standard benchmarks, including Spider and BIRD, demonstrate that our method consistently outperforms existing reward models.