OptAgent: Optimizing Query Rewriting for E-Commerce via Multi-Agent Simulation

The problem: evaluating the un-verifiable

LLMs shine on tasks with a checkable answer — code that runs, math that resolves. E-commerce query rewriting has no such gold standard: whether a rewrite truly captures what a shopper meant is subjective and latent. A static reward model or a single LLM-judge is brittle here, and a lone unguided rewrite often lands worse than the user's original query. OptAgent's idea: if you can't verify the answer, simulate the customer — many of them — and let their collective behavior become the reward.

The fitness signal: a jury of simulated shoppers

Rather than one judge, OptAgent evaluates a rewrite with an ensemble of K = 5 agents. Each agent submits the query to the real search interface, parses the first page of results (dropping sponsored listings), and for every product weighs the title, description, image, price, rating, first reviews and shipping. It then assigns a relevance score in {−1, 0, +1} — Irrelevant / Partially Relevant / Fully Relevant — and makes an actual purchase decision. Averaging semantic scores across agents, plus a normalized purchase value (with diminishing returns), yields a single continuous fitness F(q).

Temperatures, not personas

A natural way to get diverse judges is to give each a persona — but the paper found personas smuggle in bias: a benign trait can tip an agent into discriminatory scoring (documented as a case study). OptAgent instead diversifies by sampling temperature — the K agents run at {0.00, 0.25, 0.50, 0.75, 1.00} — spreading reasoning paths without injecting a predefined identity. The ensemble tracks people well: it correlates with human annotators at Pearson r = 0.552, essentially the same as annotators agree with each other (r = 0.532) — expected, since the task is genuinely subjective.

The optimizer: a genetic search over rewrites

With a fitness function in hand, OptAgent treats rewriting as evolutionary search. The user's query is rephrased into an initial population (N = 5); each generation, candidates are scored, the top ones become parents, and the next generation is bred by crossover (mixing two parents) and mutation (altering one), for G = 4 generations. Guided search explores the space more effectively than one-shot sampling — best fitness climbs each generation with diminishing returns. Run on Gemini-2.5-Flash.

Results

Evaluated on 1,000 real Etsy queries across five categories, scored by mean fitness. OptAgent wins every category; parenthesized numbers are its gain over the strong Best-of-N baseline:

Two findings stand out. A naive LLM-rewrite often underperforms the original query — an unguided rewrite easily misreads intent — which is exactly why generate-many-then-verify matters. And the biggest gains come on Tail queries (+28.7% over the user's original): rare, data-sparse searches where there's no historical pattern to learn from are where evolutionary exploration helps most. Fandom queries gain least (+8.7%) — franchise searches are already precise.

What each piece contributes

Ablating components on the full dataset shows the evolutionary machinery — not just having a good judge — carries the result:

Crossover does the heavy lifting; mutation is a light touch. And a nice sanity check on realism: like real shoppers, the simulated agents disproportionately buy products ranked near the top of the results — a positional bias the framework reproduces rather than launders away.

Why it matters

OptAgent is a recipe for optimizing against subjective, un-verifiable objectives: replace the missing gold label with a simulation of the humans you're trying to satisfy, make that simulation a fitness function, and let evolutionary search do the rest. Query rewriting is the testbed, but the pattern — many diverse simulated users as a dynamic reward — travels to any setting where "is this actually better?" can't be checked with a formula.

Resources

Paper: arXiv:2510.03771 · work done during an internship at Etsy