Welfarist Formulations for Diverse Similarity Search

Modern data systems across web search, product recommendation, advertising, and retrieval-augmented generation increasingly rely on nearest neighbor search to identify the most relevant items for a given user query. However, optimizing solely for similarity often leads to redundant or unfair outcomes, such as a single seller or product category dominating all displayed results. While existing techniques attempt to enforce diversity by setting rigid caps on how many results can share the same attribute, these hard constraints fail to adapt dynamically to user intent and can significantly degrade search relevance when a specific category is explicitly requested.

The article develops a principled, economics-inspired framework that balances relevance and attribute diversity in similarity search without relying on ad hoc quotas. By treating attributes as economic agents and applying collective welfare formulations—specifically Nash social welfare and generalized p-mean welfare functions—the authors design algorithms that adaptively balance diversity and relevance in a query-dependent manner.

To evaluate this framework, the authors conducted theoretical analyses and empirical experiments across both single-attribute and multi-attribute environments. They tested their algorithms on real-world and semi-synthetic benchmark datasets comprising up to nearly 10 million vectors, including product image queries, academic machine learning papers, and high-dimensional image descriptors. The evaluation compared the welfare-based approach against standard approximate nearest neighbor search and prior hard-constrained diversity methods using standard relevance and diversity metrics.

The findings establish that the Nash-based formulation achieves high diversity while consistently maintaining strong relevance, regularly achieving an approximation ratio above 0.90 across datasets. In contrast, hard-constrained baselines demonstrated extreme sensitivity to user-defined quotas, occasionally suffering severe relevance drops with approximation ratios falling below 0.20 to 0.40. Furthermore, the generalized p-mean objective allows practitioners to smoothly tune the system between pure relevance and maximum diversity. For practical deployment, the authors showed that their algorithms can layer directly on top of existing search infrastructure, and an optimized union-fetching heuristic delivered up to a tenfold throughput increase and substantial latency reductions.

These results demonstrate that organizations can implement diversity and fairness safeguards in large-scale search and recommendation platforms without sacrificing relevance or overhauling existing index pipelines. Because the multi-attribute optimization problem is proved to be computationally hard, the authors provide a polynomial-time approximation algorithm that guarantees approximately 63% of optimal welfare. For latency-critical enterprise environments, adopting the union-fetching heuristic offers an effective balance between throughput and diverse retrieval, though practitioners should select tuning parameters to match their specific domain needs.