Retrieved but not ranked: surface-form bias in structural retrieval, from mathematics to agent trajectories

AI summary

Overview

Research area: Information retrieval and representation learning — specifically "structural retrieval," where a query and its correct match share an underlying procedure or technique but little or no surface wording. The paper spans two domains: competition mathematics and embodied-agent task trajectories.

Technical level: Advanced. The evaluation protocol relies on bootstrap confidence intervals, paired bootstrap judge comparisons, McNemar tests, and exact hypergeometric chance baselines, though the core finding is stated in plain terms.

Scope: One shared evaluation protocol applied across two unrelated domains to test whether embedding retrieval follows surface form or underlying structure, and to test what reranking stages actually recover.

What This Paper Is About

Embedding retrieval is normally tested on cases where wording and meaning point the same direction. This paper deliberately pulls them apart: it asks models to retrieve items that share an underlying structure — the same mathematical technique, or the same procedural task type — while sharing almost no vocabulary. The goal is to find out which signal embedding retrieval actually follows, what a reranking stage can recover, and whether retrieval quality reaches a downstream solver.

Key Contributions

1. A two-domain evaluation of structural retrieval under one shared protocol, with tiered "disguise-requiring" gold items, exact chance baselines, a rank-1 failure taxonomy, and bootstrap confidence intervals on every headline number. Published numbers from each source benchmark were reproduced as a validation gate first (MathNet's easy-tier values recovered within one point; the trajectory benchmark's MEDIUM mean average precision recovered within 0.007).

2. Evidence that embedding retrieval anchors on literal surface content in both domains — 0.0% strict Hit@1 under heavy disguise in mathematics with the answer still retrievable below, and below-chance retrieval in trajectories once gold excludes the query's literal object and receptacle tokens.

3. A "lexical-control sign flip": the same lexical reranker damages mathematical retrieval and improves trajectory retrieval, with a token-class ablation locating the mechanism. The paper proposes the control's sign as a cheap diagnostic of whether a benchmark's surface variation is adversarial or incidental.

4. A judge-dependence result for LLM reranking and a paired downstream null. Reranking direction replicates across three judges, but effect size, tier profile, and which judge is the outlier all change with domain. In a paired downstream experiment, oracle retrieval was statistically indistinguishable from adversarially bad retrieval, and a complete-answers-only analysis locates the mechanism.

Main Findings

• Mathematics rank-1 failure is complete. Against 500 queries and a 117,088-item corpus, strict Hit@1 at the hardest disguise tier is 0.0% [0.0, 0.0] for both production embedders (gemini-embedding-001 and Qwen3-Embedding-8B). The correct item sits in the top 10 nearly always: lenient Hit@10 is 99 to 100% at both tiers. At easy tier, Gemini-emb reaches 12.2% Hit@1 [9.4, 15.2] with 97.6% Hit@10 [96.2, 98.8]; Qwen-emb reaches 8.6% [6.2, 11.0] with 95.2% Hit@10 [93.2, 97.0]. At hard tier, Qwen-emb falls to 2.8% Hit@5 [1.4, 4.4] and 21.0% Hit@10 [17.6, 24.6].

• Failures are lexical, not random. Between 84 and 98% of misses are the query's own planted near-miss, and in 95.2 to 99.8% of misses the winning candidate is more lexically similar to the query than gold is. One example: a character-identical problem with a single flipped inequality wins at cosine 0.860, while the true renamed-variable equivalent sits at rank four with cosine 0.821.

• Trajectory retrieval falls below chance. Under strict gold requiring the same task type but a different target object, Hit@1 is 17.8% [11.0, 25.4] (Qwen-emb), 15.3% [9.3, 22.0] (Gemini-emb), and 9.3% [4.2, 14.4] (MiniLM) against exact chance of 15.3%. Once gold must involve a different object and a different receptacle, all three embedders fall below chance: 11.0%, 8.5%, and 6.8% against chance of 14.1%. A reference definition accepting any object gives 75.4%, 74.6%, and 50.0% against chance of 16.9%.

• The lexical control flips sign. In mathematics the control reduces Hit@1, losing 9.1% (Gemini-emb) and 4.8% (Qwen-emb) of the recoverable gap at easy tier, and is flat at hard tier. In trajectories it helps, closing +25.9% [11.3, 41.2] (Qwen-emb), +36.4% [23.4, 50.0] (Gemini-emb), and +32.1% [18.5, 47.1] (MiniLM) of the strict gap. The interpretation: MathNet's equivalents are adversarially paraphrased while its decoys preserve lexical overlap, so lexical signal points the wrong way; ALFWorld's surface variation is incidental, so verb and receptacle overlap correlates with task type.

• LLM reranking recovers substantial gap, but magnitudes do not transfer. Across three independently trained judges, all twenty-one judge-by-configuration cells are positive. Recovery spans 5 to 63% of the gap in mathematics and 43 to 76% in trajectories. In mathematics, Haiku-j is 1.8 to 2.8 times stronger than Gemini-j and more than five times stronger than GLM-j at easy tier (58.1% and 63.3% of gap closed) yet weaker than both at hard tier (5.4% and 6.7%). In trajectories the ranking inverts: GLM-j leads at 68.5% to 75.8%, while Haiku-j lands at 43.9 to 48.2%. Each domain has a different outlier judge. Paired bootstrap differences between judges exclude zero in every configuration.

• Query style shifts judge performance. Gemini-j's gains drop from 61.5 to 62.5% on the human-paraphrased original 40 queries to 36.6 to 40.0% on the templated new-78, while GLM-j holds steady at 68.3 to 76.0%.

• Contamination is established in one cell, directionally consistent elsewhere. At hard tier, well-known competitions (IMO, USAMO, APMO; n=57) against the pooled rest (n=443) show a +19.8 point gap [6.7, 33.2] for Gemini-j with Gemini-emb candidates. The other five cells range from +1.4 to +8.1 points with confidence intervals spanning zero.

• Same model, two deployments, different results. Two servings of identical Qwen3-Embedding-8B weights (mean pairwise cosine 0.9947 over 500 identical texts, never above 0.999) agreed on five of six retrieval metrics but differed significantly on hard-tier Hit@10: 17 discordant queries in one direction against 1 in the other (McNemar exact p = 0.00014).

• The downstream retrieval effect is a paired null. In 210 mathematics problems with solver DeepSeek-v4-flash at a 32,768-token budget, accuracy was flat at 67 to 70% across all three conditions under both graders. None versus gold: 13 queries where context hurt against 10 where it helped (p = 0.678). None versus deliberately bad retrieval: 11 against 8 (p = 0.648). On the 64 of 210 queries that failed zero-shot, gold recovered 10 (15.6%) while breaking 13 of the 146 already solved — a net of minus 3; deliberately bad retrieval nets an identical minus 3.

• The null has a located mechanism: truncation. Restricting to the 127 of 210 queries whose answers finished within budget in all three conditions, accuracy is 97.6 to 100% in every condition under both graders, with zero to two discordant pairs. The headline 69.5% zero-shot accuracy is largely a proxy for whether the derivation fits the budget. The ceiling is not explained by fame: on completable problems, accuracy is 100.0% versus 99.1% for famous versus non-famous problems under Grader A.

• Eight evaluation-integrity incidents are documented. Most involved silent truncation that parsed as valid output — including GLM-j's chain-of-thought condition truncating 63.3% of its 2,000 responses mid-reasoning while still parsing, and an earlier solver pilot truncating 49.6% of answers in a condition-correlated way.

Methodology in Plain English

The authors built one pipeline and ran it unchanged through two unrelated domains so that any result couldn't be blamed on a single benchmark's quirks.

Mathematics. 500 queries from MathNet-Retrieve were ranked against the full 117,088-item corpus. Each query is an LLM-generated paraphrase of a source competition problem at EASY or HARD disguise, and each has exactly one correct source problem plus a planted lexically similar but mathematically different near-miss. The corpus is byte-identical across tiers — only the gold designation changes — so the tier axis isolates disguise alone.

Agent trajectories. 336 ALFWorld trajectories were matched against 118 queries (the 40 released by the source benchmark plus 78 drawn from ALFWorld's public split). Relevance was defined by task type, labeled exhaustively from task metadata by a rule classifier of eleven anchored regular expressions over the corpus's 180 unique task-description strings, then human-audited on stratified 60-item samples with zero disagreements. Two escalating "disguise requirements" were applied: gold must involve a different target object, then a different object and a different receptacle. Because every candidate carries a label, chance is exact and hypergeometric per query.

Retrieval and reranking. Each query is embedded once and ranked by cosine similarity. Reranking always operates on the same fixed top-10 candidate list, so all conditions are compared on identical inputs. Three LLM judges (Gemini 3.1 Flash-Lite, GLM-5.2, Claude Haiku 4.5, all at temperature 0) each pick a single best candidate, which is moved to rank 1.

The key metric is "share of the recoverable gap closed": (Hit@1 after reranking minus Hit@1 before) divided by (Hit@10 minus Hit@1 before). A reranker is scored only against what its candidate list made retrievable. Every Hit@k carries a bootstrap 95% confidence interval from 10,000 resamples.

Downstream test. A single solver attempted 210 problems under three conditions: no context, a deliberately bad retrieval, and the gold equivalent with its solution. Two independent graders scored answers on a 0-to-7 scale binarized at 6 or above. Finish-reason was logged for every generation so truncated outputs could be separated from completed ones.

Why This Matters

Impact on research. The paper argues that a single-domain study of "semantic" retrieval cannot separate properties of embedding models from properties of the benchmark. The lexical control's sign is proposed as a cheap, essentially free diagnostic that reveals which regime a benchmark occupies before any expensive evaluation runs. The judge-dependence result also cautions against reporting any single reranking effect size as a portable property, and the downstream null challenges the assumption that better retrieval necessarily improves a solver.

Real-world applications:

• Retrieval-augmented generation pipelines: knowing that a cheap lexical reranker can help or hurt depending on how a corpus's surface variation arose gives practitioners a fast sanity check before deploying an LLM reranker.
• Agent memory and procedural retrieval: systems that retrieve past trajectories or action sequences for reuse should know that embedding retrieval can rank below chance when the match must generalize past literal object and container names.
• Evaluation design for benchmarks: the paper recommends routine reporting of exact chance baselines, lexical-control sign, and per-condition truncation audits — directly applicable to anyone building a retrieval or reasoning benchmark.
• LLM-as-judge deployments: the demonstrated drift in judge performance across domains and query styles, plus the memorization-contamination signal, matters for anyone using judges as a scoring stage.

Industry relevance. The deployment divergence result — two servings of identical weights disagreeing significantly on one metric where ranking margins are thin — is a practical warning for teams that treat model endpoints as interchangeable. The truncation finding is equally practical: headline accuracy under a token budget can be closer to a measure of whether an answer fits than of whether the model can solve the problem.

Future Directions

1. More judges and more domains. Three judges is a small sample; magnitudes varied more than eightfold among them and each domain had a different outlier, so the observed spread is best read as a lower bound on judge variability. One further candidate proved structurally infeasible as a judge.

2. Separating memorization from reasoning. Contamination attribution is correlational, and the well-known subset may differ in ways beyond training exposure. The authors note that MathNet's equivalents and decoys were generated by a Gemini-3-flash-family model, creating a possible unmeasured family-level affinity with Gemini-j.

3. Generalizing the downstream null. The result rests on one solver whose effective headroom proved near zero once truncation was controlled for. Whether the retrieval-to-solver link is similarly absent for other solvers, domains, and problem difficulties is untested.

4. Widening the trajectory evidence. The trajectory domain uses one dataset family, one 336-item corpus, and 118 queries — short of the planned 150, which was unreachable without a heavy simulation dependency. Provenance and phrasing style are also confounded in the old-versus-new query subset contrast.

Target Audience

Researchers and practitioners in information retrieval, retrieval-augmented generation, and agent systems who evaluate embedding models or operate retrieve-then-rerank pipelines. It is especially relevant to benchmark designers, who will find the lexical-control diagnostic and the truncation-audit recommendations directly actionable, and to applied teams deciding whether to add an LLM reranking stage or whether to trust a model endpoint as a stable component. The dense statistical apparatus means the paper is best suited to readers comfortable with confidence intervals and paired significance testing, though its central claims are stated plainly enough for a general machine learning audience.

Authors’ abstract

We evaluate embedding retrieval where surface form and meaning are pulled apart on purpose: retrieving items that share underlying structure but not wording, in two unrelated domains under one protocol, competition mathematics (MathNet-Retrieve; 500 queries, 117,088-item corpus) and embodied-agent trajectories (ALFWorld-derived; 118 queries, 336 trajectories). In mathematics the failure is complete: strict Hit@1 at the heaviest disguise tier is 0.0% for both production embedders (bootstrap 95% CI [0.0, 0.0]) while the correct item sits in the top 10 nearly always, and in 95.2 to 99.8% of misses the winner is more lexically similar to the query than the correct answer. In trajectories, where surface variation is incidental, the same models land at or near hypergeometric chance when gold must involve a different object, and below chance for all three embedders once gold must differ in object and receptacle: retrieval anchors on literal tokens, not task structure. A lexical reranker control hurts in mathematics and helps in trajectories (closing 26 to 36% of the gap, CIs excluding zero); its sign reveals whether a benchmark's surface variation is adversarial or incidental. An LLM reranker recovers 5 to 63% of the gap in mathematics and 43 to 76% in trajectories; direction replicates across three judges (all 21 cells positive), but effect sizes, tier profiles, and the outlier judge change with domain (paired differences excluding zero everywhere). Mathematics gains concentrate on well-known competitions (+19.8 points, CI [+6.7, +33.2], one of six cells), so part of the recovery is memorization. In a paired downstream experiment (210 queries, graders at 96 to 99% agreement), oracle retrieval was indistinguishable from adversarially bad retrieval (McNemar p = 0.678); the solver's 69.5% zero-shot accuracy is largely a truncation proxy (97 to 100% on finished answers), leaving no headroom.