PExA: Parallel Exploration Agent for Complex Text-to-SQL¶

🕒 Published (v1): 2026-04-24 18:12 UTC · Source: Arxiv · Venue: ACL 2026 · link

Why this paper was selected

Parallel exploration reformulates text-to-SQL as coverage-guided agentic search

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

PExA reframes text-to-SQL as a software test-coverage problem: a Planner decomposes a natural-language query into atomic SQL "test cases" executed in parallel, and a Proposer synthesizes the final long-form SQL from the gathered evidence. This parallelized multi-agent architecture achieves 70.2% execution accuracy (state-of-the-art) on Spider 2.0 while keeping wall time competitive with sequential baselines (~5.55 min/query).

Problem¶

Agentic text-to-SQL methods improve accuracy via deep planning, iterative self-correction, and multi-tool calls, but incur high latency because operations execute sequentially (latency scales as the sum of all steps). Simpler methods are fast but inaccurate on complex, real-world benchmarks like Spider 2.0, which features 150+ large cross-domain databases, nested types, and long SQL. PExA targets better Pareto optimality on this latency-vs-performance frontier.

Method¶

PExA contains three specialized sub-agents orchestrated by the Planner:

Planner: In a single forward pass, decomposes the user query into a diverse suite of self-contained NL test cases (unit tests), each targeting a semantic sub-requirement (filter, join, aggregation, existence check). Test cases intentionally extend beyond the original query to probe adjacent database information ("over-generation"). The Planner also decides when to invoke the Proposer and performs final verification.
Test Case Generator: Translates each NL test case into SQL via lightweight LLM-based schema linking and database compression (following ReFoRCE). All test cases execute in parallel against the database using an SQL Executor tool, receiving three feedback types: compilation error, NULL result, or success with truncated results. For each test case, the sub-agent also generates multiple candidate SQL queries with diverse reasoning strategies in one call (single-step multi-path search), bounding latency to the slowest branch rather than their sum.
SQL Proposer: Integrates the executed test cases (distilled evidence, not full schema metadata) to synthesize the final long-form SQL. A Semantic Verifier back-translates the SQL to NL and checks alignment with the original query; mismatches trigger a semantic error and revision.

Parallelism is exploited at three levels: (a) diverse test case planning in one pass, (b) concurrent test case execution, and (c) single-step multi-path SQL generation per test case.

Key Contributions¶

Reformulation of text-to-SQL as a software test-coverage problem, enabling natural parallelism and broader semantic surface exploration beyond strict query decomposition.
PExA, a three-sub-agent system (Planner, Test Case Generator, SQL Proposer) with parallel planning, concurrent execution, and single-step multi-path search.
State-of-the-art 70.2% EX on Spider 2.0 (at submission), outperforming ReFoRCE (39.7% EX@4) and Spider-Agent (27.4% EX@4), with wall time of 5.55 min/query.
Empirical analysis of LLM synergies, branching factor trade-offs, and error categorization.

Results¶

Spider 2.0-Snow: PExA 45.7% EX / 49.5% EX@4, wall time 5.55 min — vs. ReFoRCE 36.6/39.7, Spider-Agent 25.2/27.4.
Spider 2.0-Lite*: PExA 46.6% EX / 49.9% EX@4.
Leaderboard (updated evaluation): 70.2% EX at submission time.
Ablation (Snow, single run, EX):
Full: 42.9%
w/o plan-time parallelization: 40.0% (−2.9 pp)
w/o test-time parallelization: 39.9% (−3.0 pp)
w/o Semantic Verifier: 42.3% (−0.6 pp)
w/o Proposer: 41.1% (−1.8 pp)
Branching factor: EX rises from 38.4% (1 plan branch, 1 exec branch) to 42.9% (unconstrained); limiting to 1 exec branch costs 4.5 pp.
LLM mixing: GPT-o3 homogeneous = 42 EX; GPT-5 = 45 EX; Claude Sonnet-4 homogeneous = 38 EX; Sonnet-4 as Planner + GPT-o3 elsewhere = 44 EX.
Error analysis: 42.3% of failures are semantic/approach errors; 36.5% join errors; 13.5% schema-linking errors; 5.8% aggregation errors; 2.0% other.

Limitations¶

Baselines frozen at November 2025; newer (non-open) methods cannot be fairly compared.
No post-training; post-training could further improve agentic capabilities but may reduce robustness.
Framework generates many LLM calls, making it computationally expensive.
Evaluated only on Spider 2.0; generalization to other text-to-SQL benchmarks or broader code-generation tasks is not demonstrated.
No bias mitigation for GPT-o3 outputs.

Relevance to Agentic AI / LLM Agents¶

PExA is a direct instantiation of the multi-agent agentic workflow paradigm applied to a structured reasoning task, offering a concrete mechanism to resolve the latency-performance trade-off that plagues sequential agent chains. The insight — reframing a complex task as test coverage and exploiting the independence of unit tests to enable parallel tool-calling — is generalizable beyond SQL to any agentic setting where sub-tasks are semantically independent. The Planner-as-orchestrator pattern and single-step multi-path search are immediately relevant to researchers designing compound AI systems with controllable compute budgets. The LLM-mixing ablations also provide rare empirical evidence on where specialized models (planning vs. long-context generation) differ within a shared agent architecture.