Paper Walkthrough: It Takes Two to Match — Co-Evolving Both Sides of Retrieval with RL

A paper that rebuilds the first stage of search by having two LLMs write keywords — one for queries, one for items — and training them in alternation until their vocabularies meet. Explained from scratch.

It Takes Two to Match: Co-Evolving Generative Retriever with Reinforcement Learning

Whatever the first stage drops is gone for good

The paper is "It Takes Two to Match: Co-Evolving Generative Retriever with Reinforcement Learning" (arXiv:2609.00638, by Runpeng Dai, Kaili Huang, Changsung Kang and Ciya Liao, posted 2026-09-01).

Here is what it claims, up front. Retrieval — the first stage of search and advertising systems — narrows a huge item universe down to a candidate set for downstream ranking and auction. Recent work has been pouring LLMs into this stage through query expansion, data synthesis and retrieval-feedback training, but the generative component is almost always used to augment the query side while the actual matching is still handed off to a separate downstream retriever. The paper's system, CoGR, instead trains LLMs to build the retrieval representation itself on both sides: each generator emits a compact set of keywords, and matching happens directly through an inverted index. Training runs in two stages. Supervised fine-tuning (SFT) first establishes an aligned keyword space; then co-evolving reinforcement learning alternately optimizes the query- and item-side generators with GRPO against the opposite side's frozen index. Both sides chase the same query-to-item retrieval $F_1$: the query side receives that $F_1$ directly, while the item side receives a counterfactual marginal reward measuring how much its generated keywords moved the query-side $F_1$. Against 10 representative sparse, dense and generative baselines, CoGR wins on both an internal APP Marketplace dataset and the public WANDS benchmark, improving $F_1$ over the strongest baseline by $10.9\%$ and $36.1\%$ respectively (Abstract).

Why does this stage matter so much? Because, as the paper puts it, its errors are largely irreversible (§1). An item that isn't retrieved can't be rescued by any downstream model, however clever. Push too many irrelevant items through and you simply load up the next stage. Cast wide but land precise — that recall/precision tension is the job of stage one.

An analogy: make both the job ad and the résumé use the same words

Keyword retrieval is job matching. The employer writes required skills into the posting; the candidate writes owned skills into the résumé. Share a word, and you meet.

In practice the posting says "front-end" and the résumé says "React." The substance lines up, the strings don't, and the two never find each other.

The usual fix is to leave résumés alone and expand the posting's vocabulary. CoGR's move is to rewrite both documents — and not once. Each side is rewritten repeatedly, in alternation, guided by how many matches the last rewrite actually produced. That is what the title's It Takes Two is pointing at.

What came before, and the axis this paper shifts

The paper sorts prior work into three families (§1, §5):

• Sparse (lexical) retrieval — BM25 and friends, matching explicit terms through an inverted index. It remains dominant in sponsored search, where advertisers bid on keywords directly, but lexical representations struggle with deeper semantic relations.
• Dense retrieval — map queries and items into one continuous space and match by vector similarity. DPR and ANCE are the canonical examples.
• Generative retrieval — autoregressively generate item identifiers instead of searching by similarity, as in DSI and RIPOR. The paper notes it depends heavily on identifier design and faces decoding-scalability and generalization challenges.

On top of these came LLM-based query expansion, pseudo-document generation, and eventually methods like DeepRetrieval that train an LLM from downstream retrieval-metric rewards. The paper's observation is that nearly all of them train one side only, usually the query side (§1). CoGR changes that: train both, and let the generated keywords be the index. A side benefit it emphasizes is compatibility — keyword output drops straight into existing keyword-based retrieval infrastructure.

The contrast with dense retrieval is easier to feel than to read. Drag a query through a cloud of document vectors below: dense retrieval ranks by a continuous distance, whereas keyword matching is a hard yes/no on whether a string appears.

Mechanism 1: matching is just set overlap

Before the training story, pin down what retrieval is here. A query-side generator $G^q$ and an item-side generator $G^i$ emit keyword sets $S_q = G^q(q)$ and $S_i = G^i(i)$. The retrieved set is defined as (§2.1):

In words: take the bag holding the query itself plus its generated keywords, take the bag holding the item itself plus its generated keywords, and admit the item if the two bags share at least one element. That's it. ($\cap$ is intersection, $\varnothing$ the empty set, so "intersection isn't empty" means "at least one overlap.")

That gives a candidate set but no ordering, so the paper treats each side's keyword set as a bag of words and ranks the retrieved items by BM25 (§2.1). CoGR's novelty is entirely in how candidates are produced; the ranking function stays classical.

One more intuition to hold onto. The similarity dense retrieval uses is an inner product, which grows as two vectors point the same way. Keyword overlap is that quantity crushed down to 0 or 1.

If you want the embedding side of this story, see Embeddings from scratch; for how retrieval plugs into generation, see RAG fundamentals.