Rewrites a user query into a better-performing alternative using an offline-cached mapping of frequent queries, so common reformulations happen at lookup speed rather than at full-pipeline cost.
Patent Overview
- Inventor
- Amit Singhal
- Assignee
- Google LLC
- Filed
- 2004-03-31
- Granted
- 2010-11-23
- Application Number
- US 10/814,222
The Challenge
Online Query Rewriting Is Expensive
Real-time query rewriting that examines logs, considers synonyms, and evaluates retrieval alternatives is expensive to run on every query. Most queries are repeats of patterns seen before. The system needs a way to amortize the rewrite cost across users by computing rewrites offline for frequent queries and serving them from a cache, while still falling back to live rewriting for novel queries.
- Live Rewriting Burns Latency — Computing the best rewrite for every query at serve time adds milliseconds to every search. For high-volume queries this cost is paid millions of times for the same work.
- Most Queries Repeat — A small set of head queries account for a large share of total traffic. Computing rewrites once for each head query and caching them is far cheaper than recomputing per impression.
- Cache Has To Stay Fresh — Query rewrites depend on the current document corpus and current ranking behavior. Cached rewrites that go stale produce degraded results. Refresh policy is part of the design.
- Novel Queries Still Need A Rewrite Path — The long tail of queries cannot all be cached. The system needs a fallback that produces a reasonable rewrite at serve time when the cache misses.
- Predetermined Conditions Gate Cache Use — Not every cached rewrite is safe to apply on every query. The system needs conditions (query similarity threshold, freshness check, user-context match) that gate when the cache result is used.
Innovation
Offline Map, Online Lookup
The system mines query logs offline to build a mapping from frequently-seen queries to their best rewrites. The mapping is cached in memory. At serve time, when a user query matches a cached entry under predetermined conditions, the rewrite is fetched from the cache and used to retrieve documents. Cache misses fall through to live rewriting or the original query.
- Mine Frequent Queries — Offline analysis of query logs identifies the queries that account for substantial traffic share. These are the candidates for cached rewrites.
- Compute Best Rewrites Offline — For each frequent query, run the full rewrite pipeline offline (synonym expansion, semantic similarity, performance testing) to produce the best alternative formulation.
- Cache The Mapping — Store the (original query → best rewrite) pairs in a fast lookup cache. The cache is read-only at serve time and rebuilt periodically as logs and corpus evolve.
- Receive User Query — When a search query arrives, the runtime checks whether it matches a cached entry under predetermined conditions: exact match, normalized match, or fuzzy similarity within tolerance.
- Apply Cached Rewrite — On cache hit and condition pass, fetch the rewrite and issue it to the backend retrieval system instead of the original query. The rewrite is what actually drives document retrieval.
- Fall Through On Cache Miss — When no cached entry matches or conditions fail, the system either runs live rewriting (slower path) or issues the original query unchanged. The fallback path keeps the long tail covered.
- Refresh The Cache Periodically — Offline rebuilds incorporate new query patterns and corpus changes. Cache freshness is a tunable parameter balancing computational cost against rewrite quality.
Precomputation Amortizes The Rewrite Cost
The system trades offline compute for online latency. A rewrite computed once and served millions of times costs far less per query than a rewrite computed per request, and the offline path can afford more sophisticated rewrite logic than serve-time budgets allow.
Compute Where It Pays Off
Frequent queries get expensive offline computation amortized over millions of impressions. Rare queries get the cheaper online path because the impression count cannot pay back precomputation cost.
- Offline Map — Computed once per refresh cycle. Holds the best rewrite for each frequent query, found using full pipeline analysis.
- Cache Lookup — Constant-time lookup at serve time. Hot in memory so the latency cost is negligible compared to the saved rewrite computation.
- Predetermined Conditions — Gates that decide when a cached rewrite is safe to apply. Conditions can be exact match, freshness check, or context match.
The cache is the difference between expensive query rewriting and free query rewriting.
<\/section>Technical Foundation
The Cache And Its Conditions
The cache structure is straightforward; the conditions and freshness policy are where the system gets its quality.
- Frequent-Query Set — The subset of query log entries that meet the frequency threshold. Computed offline and refreshed on a schedule.
- Cached Rewrite — The best alternative form of the frequent query, produced by full-pipeline offline analysis. Stored as a string with optional metadata.
- Predetermined Conditions — Per-entry conditions that gate cache use: exact match, normalized match, freshness, user-context match. Conditions are evaluated at serve time.
- Cache Freshness Policy — How often the cache is rebuilt. Frequent rebuilds catch corpus and behavior changes but cost more compute; infrequent rebuilds save compute but risk stale rewrites.
Quality Metrics
- Cache Hit Rate — Higher is better for latency; the long tail caps how high this can go. Production values often exceed 50% for head-heavy query distributions.
hit_rate = |hits| / |total queries| - Rewrite Quality Delta — Positive values indicate the rewrite improves retrieval. Cached rewrites are only kept while their delta stays positive on the current corpus.
delta = quality(rewrite) - quality(original)
Key Insight: The patent treats query rewriting as a precomputation problem rather than a serve-time problem. Once you frame it that way, more sophisticated rewrite logic becomes affordable because it runs offline. The cache is not just a latency optimization; it enables rewrite techniques that would never be acceptable to run per-request.
<\/section>The Process
The Rewrite Pipeline
Offline cache construction and online lookup run on different cadences but share the rewrite map data structure.
- Log Aggregation — Aggregate query log entries by normalized form. Compute frequency per unique query and identify the candidate set for caching.
- Per-Query Rewrite Computation — For each candidate, run the full rewrite analysis: synonym expansion, semantic similarity, performance testing. Output is one or more candidate rewrites with quality scores.
- Best-Rewrite Selection — Pick the highest-quality rewrite per candidate query. Apply additional safety checks: no information-dropping, no intent shift.
- Cache Population — Write the (query → best rewrite) pairs into the runtime cache. Optionally write companion metadata (freshness timestamp, condition flags).
- Runtime Lookup — User query arrives. Normalize and probe the cache. If hit and conditions pass, use the rewrite; otherwise fall through to original query or live rewriting.
- Issue Search — Send the chosen query (original or rewrite) to the backend retrieval system and return results.
Quality Control
Quality Control
Conditions That Prevent Misuse
Cached rewrites can become inappropriate when context changes. The conditions framework prevents stale or misapplied rewrites from reaching live retrieval.
- Exact Or Normalized Match — Cached entries can require exact string match or normalized match (lowercased, whitespace-collapsed). Stricter match reduces false-positive cache hits.
- Freshness Check — Each cache entry carries a timestamp. Entries older than the freshness threshold are invalidated and fall through to live rewriting.
- User-Context Gate — Some rewrites only apply when user context matches (locale, language, signed-in state). The condition is checked before the rewrite is used.
- Quality Floor — Rewrites whose quality delta has dropped below threshold on the current corpus are removed from the cache during refresh. The cache only holds rewrites that still improve retrieval.
What This Means for SEO
What This Means for SEO
Query rewriting at cache speed is a quiet but constant force in how queries actually reach the retrieval engine. Your page is competing against the engine’s best guess at what the user really meant, not always against the literal query.
- Head Queries May Be Silently Rewritten — Common, repeated queries are the most likely to hit a cached rewrite. Your page may be ranked against a rewritten form of the query, not the literal user input. SERP analysis should account for this.
- Long-Tail Queries Hit The Live Path — Less frequent queries either get live rewriting or pass through unchanged. Long-tail SEO can rely more on the literal query terms because the rewrite layer is less aggressive there.
- SERP Stability Reflects Cache Stability — Cached rewrites refresh on a schedule. SERPs for head queries can shift suddenly when the cache rebuild lands a new best rewrite. Track ranking volatility on a per-query basis to spot these refresh effects.
- Synonym And Variant Coverage Helps — Pages that cover the synonym space of a head query are likely to match both the original query form and its cached rewrite. Variant coverage compounds with rewrite handling rather than competing with it.
- Freshness Of Corpus-Relative Quality Matters — Cached rewrites are dropped when the corpus changes such that the rewrite no longer outperforms the original. If you become the canonical answer for a rewritten query, the rewrite tends to persist; if your content drifts off-topic, the rewrite may be deactivated.
- Watch For Query-Rewrite Mismatches In Analytics — Your Search Console queries reflect what was logged; ranking is influenced by what was actually retrieved. Discrepancies between query and CTR patterns may reflect rewrites.
- Brand-Plus-Generic Combinations Often Get Rewritten — Compound queries like "brand name plus generic product" frequently get rewritten to broader or narrower forms. Pages targeting these patterns benefit from covering both halves explicitly.