Embedding retrieval ranks matching words above shared underlying structure

Across competition mathematics and embodied-agent trajectories, embedding models retrieved plausible candidates but often ranked lexical overlap ahead of structural similarity.

PaperTop Universitycs.LGarXiv:2609.01556v1 ↗

Nabira Rashid · Manolis Kellis

Independent · MIT CSAIL · Kellis Lab

Research Digest·3 September 2026·3 min read

Read the paper →

What they did

The authors evaluated embedding retrieval under a shared protocol in two domains: MathNet-Retrieve, with 500 queries against 117,088 competition-mathematics items, and an ALFWorld-derived dataset, with 118 queries against 336 embodied-agent trajectories. The evaluations deliberately separated underlying structure from wording or object names.

They then applied lexical and LLM-based rerankers to the retrieved candidates. A separate paired experiment covering 210 mathematics queries compared downstream solving with oracle retrieval against deliberately poor retrieval; graders agreed on 96–99% of judgments.

Key findings

At the strongest mathematics disguise tier, both production embedders achieved 0.0% strict Hit@1, with bootstrap 95% confidence intervals of [0.0, 0.0], although the correct item was almost always among the top 10.
In 95.2–99.8% of mathematics misses, the top-ranked incorrect item was more lexically similar to the query than the structurally correct item.
For agent trajectories, retrieval was at or near hypergeometric chance—random selection given the candidate pool—when the correct trajectory used a different object, and below chance for all three embedders when both object and receptacle differed.
Lexical reranking hurt mathematics but closed 26–36% of the gap in trajectories. LLM reranking recovered 5–63% of the mathematics gap and 43–76% of the trajectory gap; all 21 model-judge conditions improved, although effects varied substantially by domain and judge.

Why it matters

The results distinguish candidate retrieval from candidate ranking: embedding systems may locate a structurally relevant item while still placing token-level matches above it. This matters for retrieval-augmented reasoning and agent systems, where examples that share a plan, proof strategy, or action structure may use different entities and vocabulary.

Caveats

The study covers two constructed benchmarks and a limited set of embedders and reranking judges, so the magnitude of the bias may not transfer directly to other domains. Mathematics reranking gains were concentrated in well-known competitions—only one of six reported cells showed a notable gain, +19.8 points with a 95% confidence interval of [+6.7, +33.2]—suggesting memorization. In the downstream test, oracle and adversarial retrieval were statistically indistinguishable (McNemar p = 0.678) because the solver’s 69.5% accuracy largely reflected truncated outputs; completed answers were already 97–100% accurate, leaving little room to measure retrieval effects.

The paper argues that standard retrieval evaluations can conceal a ranking failure when lexical and semantic signals normally align. Its two-domain design strengthens that diagnosis: deliberately disguised mathematics and incidental entity variation in agent trajectories produce the same token-anchoring pattern, while the opposite effects of lexical reranking show that benchmark construction changes how the bias appears.

The downstream null result is also methodological: better retrieval cannot demonstrate value when the solver is already nearly perfect on completed outputs and failures mostly come from truncation. Future evaluations need both structure-sensitive retrieval metrics and downstream tasks with measurable headroom.

ZOTPAPER