# GenRewrite: Query Rewriting via Large Language Models

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Mar 2024.

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

- [When Search Engine Services meet Large Language Models: Visions and Challenges](https://mlsanity.com/paper/2407.00128/) (2024)
- [A Survey of Data Agents: Emerging Paradigm or Overstated Hype?](https://mlsanity.com/paper/2510.23587/) (2025)
- [Securing Large Language Models: Addressing Bias, Misinformation, and Prompt Attacks](https://mlsanity.com/paper/2409.08087/) (2024)
- [MIRIAD: Augmenting LLMs with millions of medical query-response pairs](https://mlsanity.com/paper/2506.06091/) (2025)
- [Towards Action Hijacking of Large Language Model-based Agent](https://mlsanity.com/paper/2412.10807/) (2024)
- [A New Query Expansion Approach via Agent-Mediated Dialogic Inquiry](https://mlsanity.com/paper/2502.08557/) (2025)
- [Cognitive-Aligned Document Selection for Retrieval-augmented Generation](https://mlsanity.com/paper/2502.11770/) (2025)
- [QueryBandits for Hallucination Mitigation: Exploiting Semantic Features for No-Regret Rewriting](https://mlsanity.com/paper/2508.16697/) (2025)
- [REVISION:Reflective Intent Mining and Online Reasoning Auxiliary for E-commerce Visual Search System Optimization](https://mlsanity.com/paper/2510.22739/) (2025)
- [RuleFlow : Generating Reusable Program Optimizations with LLMs](https://mlsanity.com/paper/2602.09051/) (2026)
- [LLMs and Agentic AI in Insurance Decision-Making: Opportunities and Challenges For Africa](https://mlsanity.com/paper/2508.15110/) (2025)
- [Search-GRT: Guided Retrieval Training of Search Agents to Optimize for Complex Question Answering](https://mlsanity.com/paper/2608.00974/) (2026)

## Abstract (arXiv)

Query rewriting is an effective technique for refining poorly written queries before they reach the query optimizer. However, manual rewriting is not scalable, as it is prone to errors and requires deep expertise. Traditional query rewriting algorithms fall short too: rule-based approaches fail to generalize to new query patterns, while synthesis-based methods struggle with complex queries. Fortunately, Large Language Models (LLMs) already possess broad knowledge and advanced reasoning capabilities, making them a promising solution for tackling these longstanding challenges. In this paper, we present GenRewrite, the first holistic system that leverages LLMs for query rewriting beyond traditional rules. We introduce the notion of Natural Language Rewrite Rules (NLR2s), which serve as hints for the LLM while also a means of knowledge transfer from rewriting one query to another, allowing GenRewrite to become smarter and more effective over time. We present a novel counterexample-guided technique that iteratively corrects the syntactic and semantic errors in the rewritten query, significantly reducing the LLM costs and the manual effort required for verification. Across the standard TPC-DS and JOB benchmarks and their SQLStorm-generated variants, GenRewrite consistently optimizes more queries at every speedup threshold than all baselines. At the >=2x threshold on TPC-DS, GenRewrite improves 25 queries-1.35x more than LLM-driven baselines and 2.6x more than LLM-enhanced rule-based baselines-and the gap widens further on TPC-DS (SQLStorm); on JOB and its SQLStorm variant, where queries are simpler, absolute gains are smaller but GenRewrite still leads by a notable margin.