Retrieved but not ranked: surface-form bias in structural retrieval, from mathematics to agent trajectories
2026-09-01 • Machine Learning
Machine LearningArtificial IntelligenceInformation Retrieval
AI summaryⓘ
The authors test how well embedding retrieval methods can find items that match in meaning but differ in wording, using math problems and agent trajectories as examples. They find these methods mostly fail when surface words don’t match, often picking items that look more similar even if meaning differs. Adding a lexical reranker helps in the agent task but hurts in math, showing whether surface differences are accidental or tricky. Using a large language model reranker improves retrieval in both areas, but some gains in math come from memorization of known problems. Finally, even perfect retrieval doesn’t help the solver much, suggesting its main limits lie elsewhere.
embedding retrievallexical similarityadversarial surface variationcompetition mathematicsembodied-agent trajectoriesrerankerlarge language modelzero-shot accuracymemorizationMcNemar test
Authors
Nabira Rashid, Manolis Kellis
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.