OptAgent: Optimizing Query Rewriting for E-commerce via Multi-Agent Simulation
OptAgent combines multi-agent shopping simulation with genetic search, improving Etsy query fitness 21.98% over original queries and 3.36% over BoN.
Key Findings
Methodology
OptAgent first asks an LLM to generate an initial population of semantically similar rewrites. Multiple Gemini-2.5-Flash shopper agents, each sampled at a different temperature, inspect retrieved products. They assign −1, 0, or 1 for irrelevant, partially relevant, or fully relevant products, then simulate purchases. The averaged relevance scores and normalized purchase value form fitness for a genetic algorithm using selection, LLM-based crossover, and mutation.
Key Results
- On 1,000 real Etsy queries, OptAgent achieved mean fitness 0.7441, versus 0.6100 for the user query, 0.5509 for a single LLM rewrite, and 0.7199 for Best-of-N. Thus it improved over the original by 21.98% and over BoN by 3.36%.
- OptAgent led every reported subsection: Head 0.7660, Torso 0.7377, Tail 0.6405, Fandom 0.7969, and multilingual 0.8547. The largest relative gain over original queries was approximately 28.67% on Tail queries, where historical supervision is sparse.
- For 287 human-annotated queries, agent scores correlated with human judgments at Pearson r=0.552, p<0.001; human-human correlation was 0.532. Removing evolution reduced fitness to 0.6965, while removing crossover yielded 0.6987 and removing mutation 0.7419.
Significance
The work addresses a central obstacle in subjective AI optimization: useful outputs lack a single gold answer and therefore lack a crisp reward. It offers a practical alternative to expensive RLHF, static reward models, and single-judge RLAIF. For industry, the approach is particularly relevant to new products, rare queries, and the search long tail, where interaction logs are limited. For research, it demonstrates that simulated preference populations can supply an actionable, though noisy, optimization signal.
Technical Contribution
The main contribution is a continuous fitness landscape built from multi-agent product judgments and purchase simulation. Product scores are averaged across agents, then combined as F=w10s10+wasa+wpp, with weights 0.5, 0.4, and 0.1 for top-10 relevance, all-result relevance, and normalized purchase value. LLMs operate directly as semantic crossover and mutation operators, enabling natural-language search over query space. Population-based optimization is more robust than greedy hill climbing when the evaluator is stochastic.
Novelty
The novelty lies in coupling evaluator diversity with evolutionary generation. Rather than using personas, which may introduce demographic or behavioral bias, OptAgent varies sampling temperature to obtain distinct reasoning paths. Compared with a static reward model, a single LLM judge, or Best-of-N sampling, it jointly models robust evaluation and iterative semantic exploration. The paper’s distinctive claim is not merely “use several judges,” but use their simulated shopping behavior as the reward driving query evolution.
Limitations
- Agents cannot reliably parse information hidden in interactive page elements such as size or color dropdowns. This causes relevance errors precisely when users specify fine-grained product attributes.
- The evaluator may over-weight customer reviews or the absence of reviews, penalizing new products that are relevant but lack review history. Its Pearson correlation of 0.552 with human ratings confirms useful but imperfect alignment.
- The study uses one platform, 1,000 queries, and Gemini-2.5-Flash; online click, conversion, cost, and cross-model generalization remain insufficiently validated.
Future Work
Future systems should combine structured product attributes, browser interaction parsing, calibrated multilingual evaluators, and real user feedback. Important directions include adaptive temperature and agent-count selection, cost-aware evolutionary search, debiasing for new products and low-resource languages, and online A/B tests measuring clicks, purchases, returns, and long-term satisfaction rather than offline fitness alone.
AI Executive Summary
E-commerce queries are often short, misspelled, and underspecified: a shopper may type “blue birthday gift fast delivery” while leaving crucial preferences implicit. Rewriting such queries is not ordinary grammatical editing. There is rarely one correct answer, so historical matching, RLHF, and single-LLM judging all struggle: logs are sparse for tail queries, human labels are expensive, and judges can be biased by verbosity, position, or superficial wording.
OptAgent reframes the task as simulated preference optimization. It generates a population of candidate rewrites, retrieves products, and asks several LLM agents to behave like shoppers. Agents inspect titles, descriptions, images, prices, ratings, reviews, and shipping information; classify products as fully relevant, partially relevant, or irrelevant; and simulate which items they would purchase. Their averaged judgments, together with normalized purchase value, define fitness. A genetic algorithm then preserves strong candidates and uses LLM-based crossover and mutation to create later generations.
On 1,000 real Etsy queries, OptAgent reached fitness 0.7441, compared with 0.6100 for the original query and 0.7199 for Best-of-N; the reported gains were 21.98% and 3.36%, respectively. Tail queries improved by about 28.67%, and the method led across Head, Torso, Tail, Fandom, and multilingual subsets. Human alignment was moderate, r=0.552 on 287 queries. The approach therefore offers a promising blueprint for optimization without explicit rewards, but hidden page attributes, review bias, low-resource languages, inference cost, and the absence of online business metrics remain important constraints.
Deep Analysis
Background
LLMs perform strongly on verifiable tasks where STaR and GRPO can exploit clear rewards, but e-commerce Query Rewriting lacks a unique answer. Earlier systems used encoder-only historical matching, Seq2Seq semantic classification, reinforcement-learning reformulation, and session graphs. These approaches can work with abundant interaction logs, yet new and tail queries remain poorly supervised. RLAIF reduces annotation cost, but single LLM judges exhibit position, verbosity, reliability, and robustness problems.
Core Problem
Given an ambiguous user query, the system must produce a rewrite that better exposes latent intent and improves the resulting product list. The objective is multi-dimensional: relevance depends on attributes, descriptions, images, reviews, price, and shipping, while commercial value may also matter. No gold rewrite exists, so static labels are inadequate. A single rewrite can distort intent, and greedy optimization can settle on a local optimum under a noisy evaluator.
Innovation
- �� Replace one judge with temperature-diverse simulated shoppers. • Convert discrete product labels into continuous cross-agent scores. • Combine top-10 relevance, all-page relevance, and normalized purchase value. • Use LLMs for semantic crossover and mutation rather than string-level edits. • Apply population-based genetic search, which explores multiple query regions and is less vulnerable to stochastic reward noise. The design specifically targets data-sparse long-tail and multilingual search.
Methodology
- �� Initial population: an LLM produces diverse rewrites preserving the original intent. • Retrieval: each candidate retrieves products; sponsored items are filtered, and agents receive title, description, image, price, rating, four leading reviews, and shipping details. • Relevance evaluation: every agent outputs −1, 0, or 1 plus reasoning for each product. • Shopper simulation: the agent selects products it would buy and computes raw purchase value. • Fitness: average product scores produce s10 and sa; purchase value is exponentially normalized, then F=0.5s10+0.4sa+0.1p. • Evolution: elite candidates are copied forward, crossover occurs with probability 0.7, mutation with probability 0.1, and the best query across up to four generations is returned.
Experiments
The dataset contains 1,000 PII-screened real queries from Etsy, organized into Head, Torso, Tail, Fandom, and multilingual groups; the multilingual subset contains 150 queries. Experiments use Gemini-2.5-Flash with temperatures 0.00, 0.25, 0.50, 0.75, and 1.00. Baselines are the original query, one LLM-Rewrite, and Best-of-N Rewrite, which samples eight candidates. The study also obtains human labels for 287 queries, reports Pearson correlation, and removes evolution, crossover, or mutation in ablations.
Results
Overall fitness was 0.7441 for OptAgent, versus 0.6100 for the original, 0.5509 for LLM-Rewrite, and 0.7199 for BoN. Gains were strong for Tail, Fandom, and multilingual queries; Italian multilingual queries improved 32.36%, while the “Others” group gained only 0.49% over BoN. Best-population fitness increased over four generations with diminishing returns. Ablations identify crossover as central: removing all evolutionary operations produced 0.6965, removing crossover 0.6987, and removing mutation 0.7419.
Applications
Search engines can use the framework offline to optimize rare, misspelled, newly emerging, or multilingual queries before deploying rewrites online. It can also support recommendation retrieval, sponsored-search candidate filtering, and customer-intent normalization. Practical deployment requires product-page access, model and inference-cost controls, safety filters, and human audits. Offline agent scores should initially be paired with click and conversion monitoring rather than treated as a final business metric.
Limitations & Outlook
The evaluator is a useful but noisy proxy: r=0.552 indicates only moderate human alignment. Browser-visible information is incomplete when key attributes are hidden in interactive controls, and review dependence can disadvantage new products. Purchase value may conflict with relevance, while low-resource languages receive weaker generation and evaluation. The paper does not establish online CTR, conversion, return, or satisfaction gains. Future work should add structured browsing, real feedback, cost-aware search, and cross-model replication.
Plain Language Accessible to non-experts
Imagine a large department store and a hurried customer handing a clerk a vague note: “blue birthday gift, arrive quickly.” The clerk’s job is not merely to rewrite the sentence neatly. The real task is to infer what products would actually satisfy the customer. OptAgent first writes several possible versions of the note, then sends a group of pretend shoppers into the store.
Each pretend shopper examines product names, pictures, prices, ratings, reviews, and delivery information. They mark items as a strong match, partial match, or poor match, and decide what they might buy. Their opinions are combined, so one odd judgment does not control the result. Different settings make the shoppers think in somewhat different ways, much like a family comparing gifts from different perspectives.
The system then runs a competition. Good notes survive, two good notes can be blended into a new note, and another note receives a small wording change. The process repeats until a strong version emerges. On 1,000 Etsy searches, this strategy improved the score 21.98% over the original queries and 3.36% over a generate-many-and-pick-one method.
It is not a perfect mind reader. A pretend shopper may miss a size hidden behind a webpage button or distrust a new product simply because it has few reviews. So OptAgent is best understood as a fast panel of test shoppers: useful for discovering better directions, but still requiring human checks and real customer experiments before full deployment.
ELI14 Explained like you're 14
Suppose you are searching online for “blue gift for my friend, must arrive fast.” The computer cannot read your mind. Maybe you want a hoodie, a mug, or room decoration. A normal rewrite might make the sentence longer but accidentally change what you meant. OptAgent handles this like a gaming squad: several AI teammates inspect the search results and give their own opinions.
Each teammate checks the product picture, title, price, rating, reviews, and delivery details. Then it says, “great match,” “sort of,” or “not really,” and chooses items it might buy. The system mixes their opinions instead of trusting one referee. Some teammates think carefully and cautiously; others explore more unusual possibilities. That variety is created by changing the model’s temperature.
Next comes the evolution round, like upgrading characters in a game. The best search phrases stay. Two strong phrases can combine their useful parts, while another gets a small change, such as a synonym or a different word order. After several rounds, the system keeps the best phrase it has found. On 1,000 real Etsy searches, it beat the original queries by 21.98% and beat the Best-of-N approach by 3.36%.
But the AI squad can still make mistakes! It may not see a color or size hidden inside a webpage menu, and it may think a new product is bad because nobody has reviewed it yet. That is why OptAgent is like a team of smart game testers, not an all-knowing oracle. It can help find promising searches, while real people and real shopping data must still check the final result.
Glossary
Query Rewriting
The process of reformulating a user’s search into a form that better expresses intent. Technically, it is a generation problem optimized for downstream retrieval quality.
It is the task optimized by OptAgent.
Multi-Agent Simulation
A procedure in which multiple LLM instances independently act as evaluators or users and their judgments are aggregated. It seeks robustness through evaluator diversity.
It supplies OptAgent’s dynamic reward signal.
Genetic Algorithm
A population-based optimizer that repeatedly applies selection, crossover, and mutation. It can explore several regions of a search space and tolerate noisy fitness.
It evolves candidate query rewrites.
Best-of-N
A test-time strategy that generates N candidates and selects the highest-scoring one. It adds sampling diversity but lacks iterative population-level evolution.
It is the main rewriting baseline, using about eight candidates.
Temperature Sampling
A generation control that changes how concentrated or exploratory token sampling is. Low temperature is more deterministic; high temperature enables more varied reasoning.
Different temperatures diversify shopper-agent judgments.
Fitness Function
A numerical objective used to compare candidate solutions. Here it combines top-10 relevance, all-result relevance, and exponentially normalized purchase value.
The genetic algorithm maximizes this score.
Open Questions Unanswered questions from this research
- 1 Agent scores align with humans only moderately. It remains unclear whether more agents, multiple model families, explicit user profiles, or calibration can improve reliability without making evaluation prohibitively expensive.
- 2 The study does not show whether offline fitness translates into online click-through, conversion, retention, returns, or satisfaction. Controlled A/B testing is needed to establish business validity.
- 3 Low-resource languages and review-sparse new products remain difficult. Better multilingual models, structured attributes, browser interaction, and fairness-aware calibration are required.
Applications
Immediate Applications
Offline long-tail query optimization
An e-commerce search team can generate and simulate many rewrites for rare, misspelled, or newly emerging queries before deployment. It needs product-page access and inference-budget controls; the expected outcome is better relevance with fewer manually authored rules.
Multilingual search improvement
Platforms can use agent ensembles to select rewrites for German, French, Italian, and other languages, provided each language receives quality audits. Low-resource languages require human review and calibration so model weakness does not become systematic retrieval disadvantage.
Long-term Vision
Preference-aware search optimization
A future system could combine simulated preferences with live feedback to optimize relevance, price, delivery, conversion, and satisfaction jointly. Major obstacles include cost, evaluator bias, privacy, safety, and the gap between simulated shoppers and real consumers.
Abstract
Deploying capable and user-aligned LLM-based systems necessitates reliable evaluation. While LLMs excel in verifiable tasks like coding and mathematics, where gold-standard solutions are available, adoption remains challenging for subjective tasks that lack a single correct answer. E-commerce Query Rewriting (QR) is one such problem where determining whether a rewritten query properly captures the user intent is extremely difficult to figure out algorithmically. In this work, we introduce OptAgent, a novel framework that combines multi-agent simulations with genetic algorithms to verify and optimize queries for QR. Instead of relying on a static reward model or a single LLM judge, our approach uses multiple LLM-based agents, each acting as a simulated shopping customer, as a dynamic reward signal. The average of these agent-derived scores serves as an effective fitness function for an evolutionary algorithm that iteratively refines the user's initial query. We evaluate OptAgent on a dataset of 1000 real-world e-commerce queries in five different categories, and we observe an average improvement of 21.98% over the original user query and 3.36% over a Best-of-N LLM rewriting baseline.