Improving Retrieval Embeddings on Conjunctive Queries with Partial Credit

As users refine search queries, especially in e-commerce, they tend to add requirements as conjunctions, making each query more specific than the last. One limitation in existing training paradigms is the binary training objective; hard negatives that subtly conflict with the query are considered just as incorrect as easy, obviously irrelevant negatives. To leverage the wasted information, we present the Graded Objective for Learning Distinctions, or GOLD mining, a hard negative mining strategy that generates hard negatives with known violations of query conditions. Additionally, we contribute GOLD reweighting, a loss function modification strategy that assigns partial credit to hard negatives that nearly satisfy the query. We demonstrate that both GOLD mining and GOLD reweighting are compatible with four common existing loss function families. Applying both generally improves win rate and achieves state-of-the-art recall. Our theoretical analysis establishes that under reasonable assumptions, GOLD Margin-MSE gains the guarantee that uniformly low loss on the objective implies approximate affine recoverability of attributes.