RAG-FGO: Dynamic Optimization of Query-Rewriting Agents for Generative RAG

Qigan Sun, Xudong Wang, Chaoning Zhang, Chenghao Li, Jiaquan Zhang, Jiehui Xie, Sungyoung Lee, Jie Zou, Ning Xie, Peng Wang, Yang Yang, Heng Tao Shen
37 minread3.95scoreNo. 111-17 AI Search issue
Contents · 6 sections1When the wording misses the corpus, a frozen rewrite often misses too2Putting the prompt and the decoding parameters in one agent3A walkthrough: who stays after one search iteration4Raising the mutation count to 15 barely moves F15What this means for people who build retrieval-augmented QA6Limitations
Rel 5Nov 3Prac 4Evid 2Time 5

A frozen rewrite prompt misses the next phrasing: how RAG-FGO searches for a query-rewriting strategyYou built a retrieval-augmented QA system over internal docs. A colleague asks, "Where is last year's design doc that changed timeouts to exponential backoff?" The wording does not match the document title, and the hits are all timeout alerts.

So you add a step before retrieval: an LLM rewrites the question into something easier to search. You wrote the prompt carefully and already tuned temperature and top-p once. Some questions retrieve well after the rewrite; a slightly different phrasing, and the same prompt drifts. The same rewrite can hit this time and miss the next.

This paper, from Kyung Hee University, the University of Electronic Science and Technology of China, and Tongji University, asks how that rewriting strategy should be searched. Traditional retrieval uses the user's original wording. Generative retrieval lets an LLM rewrite first, but usually with a frozen prompt and a single generation. Prior work sometimes uses evolution or reinforcement learning to search prompts, and sometimes uses heuristics to tune decoding parameters at generation time. This paper puts the prompt template and the decoding parameters into one search object. On the retrieval-workflow side, ReAct combines reasoning with a retrieval tool, Self-Act splits a question into sub-questions and retrieves for each, and Aflow decides when to reason and when to retrieve; Aflow is the strongest retrieval baseline in this paper's six-benchmark QA comparison. RAG-FGO is inspired by the Fungal Growth Optimizer (FGO). FGO is a bio-inspired search method that uses hyphal expansion and branching to explore broadly and refine locally at the same time. The authors apply it to rewriting strategies: a prompt template plus a set of decoding parameters become a query-rewriting agent, searched in a mixed space with no gradients. Global search rewrites the prompt to escape local optima, local search adjusts phrasing for finer alignment, and an elite memory pool re-evaluates candidates across iterations to keep strong strategies. With GPT-4o-mini as the answer generator, mean answer-level F1 on six QA benchmarks rises from Aflow's 68.9 to 77.1.

Searching a rewrite agent that jointly holds the prompt and the decoding parameters, and keeping strong strategies by re-evaluating them across iterations, raises QA scores that depend on retrieval; on reasoning benchmarks with weaker external-evidence constraints, the mean is only slightly higher, and the method can trail the strongest prompting baseline on individual sets.

When the wording misses the corpus, a frozen rewrite often misses too

Retrieval often stalls on how the user asked. If the surface form of the question does not match how the knowledge base is written, the reachable evidence is already narrower.

Generative retrieval tries to close that gap: the LLM rewrites first, then the system retrieves, turning user intent into a query the corpus can match. The flexibility brings a new problem. Rewrite quality depends not only on the retriever, but also on the generation configuration. Strategy quality is often judged by indirect feedback, such as how close the retrieved text is to the target information. That signal is noisy and can drift across questions and domains. A frozen rewrite prompt that works on one phrasing fails on another.

So the authors treat rewriting as an optimization problem over a strategy space. A query-rewriting agent A has two parts: a discrete prompt template C, which sets the form and structure of the rewrite, and continuous decoding parameters θ, such as temperature, top-p, and repetition penalties, which control how random the rewrite is and how it reads. Given a user question q, the agent uses an LLM L to write a new query, then a retriever R fetches passages from the knowledge base. At training time, the fetched passages are compared with the sample's ground-truth supporting context by semantic similarity, and that score evaluates the agent. The similarity is only available after rewrite and retrieval, the retriever is non-differentiable, and generation is stochastic, so this is a mixed discrete-continuous, noisy, gradient-free black-box problem. Hand-tuning one prompt, or only making local edits around it, can stall on a strategy that looks decent and then wobbles on the next batch of questions.

Putting the prompt and the decoding parameters in one agent

Optimization starts by initializing a population of agents. Prompts are drawn from a predefined template pool; the paper gives this example: "As a linguistic diversity expert, you excel at subtly rewriting sentences while preserving their core intent and information." Decoding parameters are sampled from a normal distribution so the starting points are spread out. The parameter example in the paper is temperature 0.7, top-p 0.8, frequency penalty 2.0, presence penalty 2.0, and a 1,024-token maximum.

How is each iteration scored? After an agent writes a new query, the retriever returns passages. A pretrained embedding model turns the retrieved passages and the ground-truth supporting context into vectors, and cosine similarity is computed. A score closer to 1 means the retrieved text is closer to the evidence this sample should see. Agents in the current iteration are ranked by this score, and the top ones are kept in the elite memory pool. Agents are selected by how close retrieval is to the gold evidence; the tables later report answer-level F1 between the final answer and the gold answer. The two are related, but they are not the same number.

To move through this strategy space, the framework uses two kinds of mutation in parallel. Global search has an LLM rebuild the prompt structure and applies a larger perturbation to the decoding parameters, dropping near-zero changes that do nothing, so the search can jump away from the current wording. Local search makes small edits such as synonym swaps or tone tweaks, and nudges the parameters only nearby, so an already-promising region can be aligned more tightly. Each selected agent grows a batch of new candidates according to the mutation count mc; which search is used is decided by a probability p_t that rises over iterations. Early on, p_t is small and most mutations go global; later, p_t is larger and most mutations go local.

A query-rewriting agent is a prompt plus decoding parameters; after local or global mutation it is ranked and filtered, then enters the elite memory pool.
A query-rewriting agent is a prompt plus decoding parameters; after local or global mutation it is ranked and filtered, then enters the elite memory pool.

Figure 2 reads left to right in four panels: what an agent contains, how the two mutations work, ranking by score, and the memory pool keeping elites and dropping weaker ones. Source: paper Figure 2.

Why a memory pool? Because the scores are unstable. The same strategy can drop on a harder batch, and generation stochasticity can make one strategy score high then low. If each iteration compares last batch's historical scores with this batch's new scores, the baseline is skewed, and a strong strategy can be replaced by a misaligned number. The elite memory pool has a fixed capacity M=5. Each iteration re-evaluates the previous elites and the new agents on the same new batch of questions, then keeps the best 5 from that pool. The comparison is on the same batch, so swings in difficulty are less likely to skew the baseline.

Search stops in either of two cases: the best agent stays unchanged for a run of iterations, or the iteration budget is used up. The best agent A* is then taken from the memory pool. At test time it is used for a single forward rewrite, with no further search.

The tables later compare rewriting strategies under the same retrieval budget, so the retrieval setup needs to be stated first. The rewriter is Qwen2.5-7B-Instruct throughout. The retriever is E5-base-v2, fetching 10 passages by inner product from the DPR English Wikipedia split (20 December 2018 dump, about 21 million passages of about 100 words each). Final answers are written by the backbone generators; GPT-4o-mini in the main table is one of them.

A walkthrough: who stays after one search iteration

The next walkthrough follows the paper's training loop. The setting matches the main HotpotQA experiment: each selected agent mutates mc=12 times in the iteration, and the memory pool has capacity M=5. The question and similarity scores below are illustrative, to show who changes whom and who stays next; the F1 numbers later all come from the paper's tables.

The illustrative original question is a multi-hop item: "Which university did the director of Inception attend as an undergraduate?" Searching with that wording tends to surface movie pages first, and the director's education page may not be in the top 10. The rewrite agent needs to turn this into a more retrieval-friendly query, for example by making the director's name and terms such as "undergraduate university" explicit.

Step 1: the agent rewrites and is scored. The current best agent in the pool, A_best, writes a new query with its prompt and decoding parameters. The retriever returns 10 passages, and cosine similarity is computed against the ground-truth supporting context. Illustrative number: A_best scored 0.75 on the previous batch, and that score is carried into this iteration.

Step 2: selected agents grow new variants. The walkthrough follows only the best seed, A_best; in the method, every selected agent grows mc candidates. This iteration has a local-search probability p_t, given by p_t = p_min + (t-1)/(T_max-1)×(p_max-p_min). The illustrative values used here are p_min=0.2, p_max=0.8, and T_max=11. In iteration 1, p_1=0.2, so about 12×0.2=2.4 of the 12 mutations go local (synonym edits, small parameter nudges) and about 9.6 go global (an LLM rewrites the whole prompt, and the parameters jump farther). By iteration 11, p_11=0.8, and the counts swap: about 9.6 local and 2.4 global.

During training, rewrite agents produce new queries for retrieval, are ranked by similarity to gold evidence, enter the memory pool, and then go through local or global search into the next iteration.
During training, rewrite agents produce new queries for retrieval, are ranked by similarity to gold evidence, enter the memory pool, and then go through local or global search into the next iteration.

The top of Figure 3 is the full path of one iteration; the bottom separates local search (sampling near the center) from global search (larger perturbations that avoid the center). Source: paper Figure 3.

Step 3: new candidates are scored with the same similarity. Illustrative number: a new agent A_new from global restructuring scores 0.82 on the current batch. If that 0.82 is compared with A_best's 0.75 from the previous batch, A_new looks better. The two batches can differ in difficulty, so those two scores do not sit on the same baseline.

Step 4: the memory pool re-scores the 5 previous elites and the new agents on the same current batch q_t, then keeps the top 5. Illustrative numbers: after re-evaluation on that batch, A_new scores 0.68 and A_best scores 0.71. A_new ranks behind A_best. Re-evaluation compares old and new strategies on the same questions, which reduces misaligned comparisons from a high score on a previous batch that does not hold now, or from a batch that happened to be easy to retrieve. A single re-evaluation does not remove the jitter that comes from generation stochasticity.

Step 5: search stops when the best agent stays unchanged for a run of iterations, or when the iteration budget is reached. The kept A* does a single forward rewrite at test time.

These illustrative scores are not experimental results. The paper's leave-one-out ablations show how much the memory pool matters. With GPT-4o-mini as the generator, the full model reaches 81.5 answer-level F1 on HotpotQA; removing the memory pool drops it to 75.2, a 6.3-point loss. The drop is between 6.3 and 7.1 points on all five datasets, the largest of the three components. Removing local search costs 4.8 to 5.2 points; removing global search costs 2.6 to 4.0 points.

With the elite memory pool, similarity between retrieved text and gold evidence rises faster and plateaus earlier at a higher level; without it, the curve oscillates more and settles lower.
With the elite memory pool, similarity between retrieved text and gold evidence rises faster and plateaus earlier at a higher level; without it, the curve oscillates more and settles lower.

Figure 6 plots similarity trajectories during training on HotpotQA, NQ (Natural Questions, real user queries against Wikipedia), 2Wiki, and MuSiQue. Blue is with the memory pool; red is without. Source: paper Figure 6.

With the memory pool, similarity rises faster and levels off earlier at a higher value; without it, the curve shakes more, especially on HotpotQA and 2Wiki, and the stable level is lower. These ablations remove one component from the full model, so they show how many points that component is still worth when the other two are present. They cannot show how the three components interact pairwise, and they cannot show whether the drop ranking would still put the memory pool first under a different p_t schedule.

Raising the mutation count to 15 barely moves F1

After the search, how do the six QA sets look? The table below is answer-level F1 (%) with GPT-4o-mini as the generator. Aflow has the highest mean among this group of retrieval baselines. RAG-FGO moves the six-set mean from 68.9 to 77.1, with a wider gap on the multi-hop sets HotpotQA, 2Wiki, and MuSiQue.

MethodHotpotQA2WikiMuSiQueSix-set mean
Self-Act73.169.267.368.4
Aflow73.565.771.668.9
RAG-FGO81.577.379.477.1

After swapping the generator, the mean is still above Aflow for the same generator, which indicates that the search is not tied to one model. GPT-4.1-nano moves from 69.7 to 73.7, Qwen-Long from 76.4 to 79.8, Qwen-Max from 69.0 to 72.4, and Gemma-2-27B from 66.3 to 70.3.

On seven reasoning benchmarks, with GPT-4o-mini as the generator, RAG-FGO averages 63.7, just above ReFeri at 63.6. On MATH500 it scores 78.0, below USC (sample several chains of thought and take a majority vote) at 78.6; on MMLU-pro it scores 64.5, below ReFeri at 65.0. That means it does not beat the strongest prompting method on these two sets.

Against methods built specifically for query rewriting, with Qwen2.5-7B-Instruct as the generator, RAG-FGO has the highest EM, F1, and accuracy on HotpotQA, StrategyQA, AmbigQA, and PopQA. The comparison set includes direct LLM rewriting, HyDE (the model first writes a hypothetical document and that text is used for retrieval), Query2Doc, and trained rewriters such as SFT, RaFe (DPO), RRR (PPO), and Q-PRM. The gains are clearer on ambiguous and long-tail facts: AmbigQA F1 moves from the strongest baseline Q-PRM's 63.9 to 66.4, and PopQA accuracy moves from 63.6 to 65.2.

Whether more search is worth it depends on both the score and the tokens spent. Figure 4 plots F1 against mc on the six datasets with GPT-4o-mini. The clearest gains are from 3 mutations to 6 or 9: HotpotQA rises from 79.2 to 80.5, then to a near-saturated 81.5. LongBench is already 71.5 at 9 mutations and only 71.6 at 15. Adding more mutations after that barely moves the score, so the return to extra search is thinning out.

On six QA benchmarks, answer-level F1 rises with the mutation count mc and approaches saturation after 9 to 12 mutations.
On six QA benchmarks, answer-level F1 rises with the mutation count mc and approaches saturation after 9 to 12 mutations.

In Figure 4 the x-axis is the mutation count mc and the y-axis is F1 (%); the generator is GPT-4o-mini. Source: paper Figure 4.

Token cost keeps rising, so that saturation point is why the main experiments choose mc as they do. Going from 9 to 15 mutations costs about 0.34M extra tokens on SQuAD and HotpotQA, and about 0.50M to 0.69M extra tokens on LongBench, MuSiQue, and NQ, for only 0 to 0.6 more F1 points. That is why the main experiments use 9 mutations for LongBench and 12 for HotpotQA. The working range is 9 to 12, which typically costs 0.5M to 1.25M tokens.

With GPT-4o-mini as the generator, comparing an agent searched on the target set against an agent transferred from HotpotQA with no further tuning, F1 drops in every case, and the drop is larger when the question style is farther away. NQ falls from 73.8 when searched on-target to 71.1 after transfer, SQuAD from 79.2 to 77.3, AmbigQA from 63.9 to 59.8, and StrategyQA from 70.2 to 64.5. All four starting scores are from target-specific search. That means a transferred agent still works, but a large task shift still calls for another search on the target set.

What this means for people who build retrieval-augmented QA

Do not freeze a hand-tuned rewrite prompt after one pass; search the prompt and the decoding parameters together, and keep a small memory pool that re-evaluates elites across iterations, which is more stable under noisy retrieval feedback.

If your system already has a query-rewrite step, treat "prompt template + temperature + top-p" as one search object and optimize them together. Do not drop the memory pool: removing it from the full method costs 6 to 7 F1 points on five datasets, more than removing local search or global search. Choose the mutation count from your own score-versus-cost curve; in this paper, 9 to 12 is the range that is near saturation while still keeping token spend in check, and going to 15 barely raises the score.

Limitations

This search is run offline before deployment and needs an extra training budget. At test time the best agent needs only one forward rewrite, but the framework cannot keep adapting online to new questions or a changing knowledge base.

How did this read for you?

One tap, no sign-in; tap again to undo. Only anonymous counts are kept, never who you are.

Discussion

Add experiment details, reproduction notes or a different take. Requires a GitHub sign-in.

Loading the discussion…