Language models trained with reinforcement learning to write SQL still break down on questions that need several tables joined together. The usual training signal is a single bit: did the query return the right rows? A query can fail because the model picked the wrong join path through the database schema or because it got a filter wrong, and the bit does not say which. When every sampled attempt at a hard question fails, the bit carries no information at all. We propose to read the join structure out of each sampled query. This is the small graph of tables and the foreign-key links the query uses. We then assign credit to that structure directly. Two queries that join the same tables in the same way are treated as the same structural decision, however differently they are worded. A query that recovers part of the correct join graph earns partial credit, even when its result is wrong.
The training method we modify is Group Relative Policy Optimization (GRPO). It is a reinforcement learning method that samples a group of answers per question and scores each answer relative to the group average, so it needs no separate learned value model. Sullivan & Koller showed that GRPO quietly acts as a step-level reward model over shared token prefixes. SQL breaks that mechanism. Equivalent join decisions rarely share token prefixes, because aliases, join order and clause order all vary. Our claim is that keying GRPO's implicit step-level credit on join subgraphs, identified up to isomorphism and anchored in the schema, will raise accuracy on multi-join questions. It should also reduce the number of training questions where every sample fails and learning stalls. The obvious cheap substitute is credit based on table-set overlap. We expect the gains to come specifically from cases that substitute cannot distinguish: the same tables connected through different paths, and the same table used in two roles.
Where this sits
Three findings motivate the work. Kang et al. (GRIT) show that models struggle to infer cross-table join links and report up to 19.71% gains on multi-join Spider queries from extracting key links symbolically. This locates the bottleneck in join structure. Their extraction runs before generation and is never trained into the policy. Stoisser et al. apply GRPO to Text-to-SQL on BIRD with execution-based and composite string, component and judge rewards. They report transfer gains such as a 34% relative exact-match increase on CRT-QA for LLaMA-8B. Their composite reward has no notion of join-graph topology, and complex multi-hop joins remain a weakness. We keep their training setting and change how credit is assigned. Sullivan & Koller supply the mechanism and one constraint. Their λ-GRPO reweights loss by the inverse frequency of a shared prefix, which stops popular failing prefixes from crushing rare good continuations. They analyze only one-dimensional token prefixes on math tasks. We carry the same correction over to structural prefixes.
Two lines of work show that structural constraints help, but neither trains the policy on them. GCR forces decoding to follow valid knowledge-graph paths with a prefix tree and eliminates hallucinated paths. It works only at inference and only over linear paths. GRASP and GraphRAG-R1 train graph agents with GRPO, using unconstrained probing and hand-tuned retrieval penalties respectively. Neither assigns credit to matched substructures. From the subgraph-matching literature we take the framing and one practical observation. RL-QVO and GNN-PE treat multi-way joins as queries that embed a small graph into a large one. Subgraph isomorphism is NP-complete in general (Levinson), but SQL join graphs have perhaps two to eight table nodes. Exact matching at that size is cheap enough to run on every rollout without learned filters or offline indices. The exponential difficulty lies in the model's search over possible join paths, not in checking a candidate. That observation is why the proposal is practical.
Core Claim
Each sampled query $o_i$ is parsed into a join graph $H_i$. Its nodes are table instances labeled by table name, with aliases kept distinct. Its edges are join predicates labeled by the column pair. The parser also records the map $f_i$ from $H_i$ into the schema graph $S$, whose nodes are tables and whose edges are declared or inferred key links. We canonicalize $(H_i, f_i)$ up to isomorphism to get a structure class $c_i$. Two rollouts that alias tables differently or list joins in a different order receive the same class.
For a group of $G$ rollouts with rewards $r_i$, group mean $\bar r$ and standard deviation $\sigma$, we estimate a structure-level success rate $\hat p(c)$. This is the mean reward of the rollouts in class $c$. Tokens in the FROM/JOIN/ON span receive the structure advantage. All remaining tokens receive the residual within their class:
$$A^{\text{join}}_i = \frac{\hat p(c_i) - \bar r}{\sigma}\cdot\frac{1}{n_{c_i}}, \qquad A^{\text{rest}}_i = \frac{r_i - \hat p(c_i)}{\sigma},$$
Here $n_c$ is the number of rollouts in class $c$. The $1/n_c$ factor is the structural analogue of λ-GRPO's inverse-prefix weighting. It keeps a common failing structure from drowning out rare correct ones. A typical example of such a structure is a join that routes through a central hub table. The decomposition gives the join decision and the filter/aggregation decisions separate credit without any step annotations.
Some groups have every execution reward equal to zero. Only for those groups, we replace $r_i$ with $\gamma\, m(H_i, H^*)$, where $\gamma < 1$ and $H^*$ is the gold join graph. The function $m$ is the fraction of gold join edges preserved by the best label-consistent embedding between $H_i$ and $H^*$. We compute $m$ exactly by backtracking over a maximum common subgraph. When tables repeat, more than one embedding is possible, and this is where isomorphism matters rather than plain label matching.
We restrict the partial reward to all-fail groups for a specific reason. Elsewhere, comparing against a single gold join graph would penalize valid alternative join paths. Execution remains the reward whenever it carries signal.
Research Program
The work has three parts. The first is a robust SQL-to-join-graph parser and canonicalizer for the BIRD and Spider dialects. It must handle self-joins, subqueries (each subquery treated as its own join graph, linked to its parent) and implicit joins in WHERE clauses. The parser's coverage is reported as a result in its own right.
The second is the training recipe. We follow Stoisser et al.: a short supervised warm-start, then GRPO on BIRD train. The training model is Qwen2.5-Coder-7B, the 7B scale at which Alpha-SQL reports a large gap from direct prompting. We implement four variants that differ only in credit assignment: execution only, token-level λ-GRPO, structure-keyed advantages, and structure-keyed advantages plus the all-fail fallback.
The third is analysis. During training we log the fraction of all-fail groups, the number of distinct structure classes per group, and how often the policy's top structure class is correct. Together these show whether the method speeds up the discovery of correct join structures, or only polishes filters once the joins are already right.
Baselines
The do-nothing reference is the warm-started model before any reinforcement learning, evaluated with the same prompt and greedy decoding. This shows how much any reinforcement learning stage contributes.
The strongest training-based competitor is standard GRPO with an execution-match reward, as in Stoisser et al.. It is the published recipe for exactly this problem, and every variant here is a change to it. The file reports no BIRD dev number for that paper (no reported result found on Lacuna for Stoisser et al. on BIRD dev), so we reproduce it ourselves. It gets identical data, group size, number of policy updates, learning-rate sweep and random seeds as our method.
The second competitor is token-prefix λ-GRPO from Sullivan & Koller. It tests whether the existing fix for popularity bias already captures the benefit without any structural parsing.
The third competitor is GRPO with a table-and-join-set overlap partial reward. It is the cheapest form of structural credit, and the proposal must beat it to justify isomorphism-based matching.
The strongest overall reference is Alpha-SQL. It is an inference-time Monte Carlo tree search method that reports 69.7% execution accuracy on BIRD dev with Qwen2.5-Coder-32B and 87.0% on Spider (Alpha-SQL). We do not expect a single-pass 7B model to beat these headline numbers. The comparison is accuracy per unit of inference compute, and accuracy on the multi-join slice.
The ablations remove each ingredient of our method in turn: structure-keyed advantages without the fallback, the fallback without the advantage decomposition, and the full method without the $1/n_c$ weighting.
Beating the GRPO execution baseline requires two outcomes. The first is a statistically significant execution-accuracy gain, over at least three seeds, on BIRD dev questions with three or more joined table instances. The second is overall accuracy that does not decline.
Why not just…?
Why not just give partial credit for overlapping tables and join columns? This is the most serious threat, and it may suffice whenever every table appears once and only one key path connects them. In that regime label-based overlap and subgraph matching coincide. They differ in two cases. One is a table used in two roles, such as a flights table joined to airports once as origin and once as destination. The other is a pair of tables connected by more than one foreign-key route. To settle the question, we will build a slice of BIRD and Spider dev where the gold query repeats a table or the schema graph has multiple paths between the gold tables. If the set-overlap baseline matches our method on that slice, we drop the isomorphism component and report the simpler method.
Why not just constrain decoding to valid schema joins, as GCR does for knowledge-graph paths? GCR removes invalid paths at inference, but validity is not correctness. Many wrong join paths are valid schema walks. A mask also gives no training signal when all samples fail. We will run schema-validity masking as an extra inference-time condition on both the baseline and our policy. If masking accounts for most of the gain, the failures were invalid joins rather than wrong valid ones, and our credit mechanism is unnecessary.
Why not just run tree search at inference time like Alpha-SQL? It works, and it currently holds the best number in the file. It pays for that with many rollouts and executions per question, a cost Alpha-SQL itself acknowledges as higher latency. We report accuracy against the number of database executions per question. Our claim is limited to the low-compute end of that curve and to whether the trained policy makes search more efficient when the two are combined.
Why not just sample more rollouts per question so that fewer groups fail completely? Larger groups reduce all-fail groups only slowly when the chance of a correct join path is very small on long joins. They also do nothing about the fragmentation of credit across token forms. We include a compute-matched baseline with double the group size. If it closes the gap, the fallback reward is not needed.
Proposed Experiments
The main evaluation is execution accuracy on BIRD dev and Spider, broken down by the number of joined table instances (one, two, three or more) and by the repeated-table/multi-path slice described above. Transfer is measured on CRT-QA, where Stoisser et al. report relative exact-match gains, to check that structural credit does not hurt general tabular reasoning.
Four checks decide whether the claim holds. First, the full method should produce a faster decline in the fraction of all-fail training groups than execution-only GRPO, at matched update steps. Second, structure-keyed advantages should beat token-prefix λ-GRPO on the three-or-more-join slice. If they do not, keying credit on structure adds nothing beyond prefix reweighting. Third, the isomorphism-based fallback should beat set-overlap credit specifically on the repeated-table/multi-path slice, while the two tie elsewhere. Fourth, an audit of 200 questions with execution-correct predictions whose join graphs differ from the gold graph should show no degradation. That audit checks whether the gold-anchored fallback teaches the model to avoid valid alternative join paths.
We also report how parser failures are distributed and how training wall-clock time grows with the number of tables. This makes the second clause of the core claim concrete: exact matching costs little at SQL scale, while the policy's search is where the exponential difficulty appears.
References
- GRPO is Secretly a Process Reward Model
- GRIT: Guided Relational Integration for Efficient Multi-Table Understanding
- Sparks of Tabular Reasoning via Text2SQL Reinforcement Learning
- Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
- GRASP: Graph Reasoning via Agentic Solving and Probing of LLMs
- GraphRAG-R1: Graph Retrieval-Augmented Generation with Process-Constrained Reinforcement Learning
- Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching
- Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding
- A Self-Organizing Retrieval System for Graphs
- Alpha-SQL: Zero-Shot Text-to-SQL using Monte Carlo Tree Search