Abstract
Answering real-world complex queries, such as complex product search, often requires accurate retrieval from semi-structured knowledge bases that involve a blend of unstructured (e.g., textual descriptions of products) and structured (e.g., entity relations of products) information. However, previous works have mostly studied textual and relational retrieval tasks as separate topics. To address the gap, we develop STARK, a large-scale Semi-structure retrieval benchmark on Textual and Relational Knowledge Bases. Our benchmark covers three domains: product search, academic paper search, and queries in precision medicine. We design a novel pipeline to synthesize realistic user queries that integrate diverse relational information and complex textual properties, together with their ground-truth answers. We conduct rigorous human evaluation to validate the quality of our synthesized queries and enhance the benchmark with high-quality human-generated queries. Our experiments suggest that STARK presents significant challenges to current retrieval and LLM systems, indicating the demand for more capable retrieval systems.
Introduction
In real-world scenarios, information retrieval is rarely a matter of simple keyword matching or structured filtering alone. Consider a user searching for a product: "Can you find a push-along tricycle from Radio Flyer that’s both fun and safe for my kid?" This query is inherently "semi-structured." It contains a hard relational constraint (Brand: Radio Flyer) alongside soft textual requirements (fun, safe, for kids).
Historically, the research community has treated textual retrieval (searching documents) and relational retrieval (querying knowledge graphs) as separate domains. However, modern AI applications—such as advanced e-commerce assistants or precision medicine tools—require systems that can navigate both simultaneously. STaRK was created to bridge this gap, providing a rigorous testbed for evaluating retrieval systems driven by Large Language Models (LLMs) on semi-structured knowledge bases (SKBs).
The STaRK Datasets
The benchmark introduces three large-scale SKBs across diverse domains:
- STARK-AMAZON: A product search dataset with over 1 million entities and 9.4 million relations (e.g., "also bought," "has brand").
- STARK-MAG: Based on the Microsoft Academic Graph, containing 1.8 million papers and 39.8 million relations (citations, authors, institutions).
- STARK-PRIME: A complex precision medicine dataset with 129k entities and 8.1 million relations, including gene-protein interactions and disease indications.
To ensure authenticity, the researchers also collected a set of 274 human-generated queries to serve as a reference for validating the synthetic data.
Methodology: Synthetic Query Generation
To create a large-scale benchmark, the authors developed a novel, automated pipeline to generate realistic queries that "entangle" text and relations. The process involves four key stages:
- Relational Sampling: Picking a relationship template (e.g., "Product X belongs to Brand Y") and grounding it with real entities from the SKB.
- Textual Extraction: Using an LLM to analyze a "gold" answer and extract specific properties (e.g., "durable," "easy to assemble") from its descriptions and reviews.
- Query Synthesis: A two-step process where one LLM generates an initial draft and a second (GPT-4 Turbo) rephrases it to add natural complexity and context.
- Answer Filtering: A panel of LLMs verifies which other items in the database meet the textual requirements, ensuring a comprehensive and accurate ground-truth list.
Key Results and Insights
Experiments conducted on STaRK reveal significant performance gaps in current state-of-the-art systems:
- The Resilience of Simple Baselines: Traditional keyword-based search (BM25) often outperformed smaller, specialized "dense" retrievers. This suggests that many modern embedding models lose fine-grained details when compressing documents into single vectors.
- Reasoning vs. Matching: Standard retrievers are frequently distracted by "keyword stuffing." For instance, a model might rank a paper highly because it repeats a technical term, even if it fails to meet a specific relational constraint like a university affiliation.
- The Power of Reranking: LLM-based rerankers (such as GPT-4 and Claude 3) are significantly better at disentangling complex requirements because they can reason about content rather than just calculating mathematical similarity scores.
- Performance and Latency: On human-generated Amazon queries, the best model (Claude 3 Reranker) achieved a Hit@1 of only 53.09%. Furthermore, the latency for GPT-4 reranking averaged ~25 seconds per query, highlighting a major hurdle for real-time applications.
Conclusion
STaRK demonstrates that current retrieval and LLM systems struggle with the multi-faceted reasoning required for real-world semi-structured queries. While LLM rerankers offer higher accuracy, their high latency and the relatively low recall of standard retrievers indicate a clear need for more efficient, "reasoning-aware" retrieval architectures. Future work may expand STaRK to include multi-modal data, such as images for e-commerce, and address the privacy complexities inherent in real-world knowledge bases.
Summary updated