STaRK: Benchmarking LLM Retrieval on Textual and Relational Knowledge Bases

Shirley Wu, Shiyu Zhao, Michihiro Yasunaga, Kexin Huang, Kaidi Cao, Qian Huang, Vassilis N. Ioannidis, Karthik Subbian, James Zou, Jure Leskovec

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).

Overview of the STaRK framework showing the interaction between users, the LLM retrieval system, and the semi-structured knowledge base.

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:

  1. Relational Sampling: Picking a relationship template (e.g., "Product X belongs to Brand Y") and grounding it with real entities from the SKB.
  2. 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.
  3. 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.
  4. 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.
The STaRK query generation pipeline, illustrating the transition from relational information and textual properties to a natural language query.

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

Abstract

Answering real-world complex queries, such as complex product search, often requires accurate retrieval from semi-structured knowledge bases that involve 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 K nowledge Bases. Our benchmark covers three domains/datasets: 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 (items). We conduct rigorous human evaluation to validate the quality of our synthesized queries. We further enhance the benchmark with high-quality human-generated queries to provide an authentic reference. STARK serves as a comprehensive testbed for evaluating the performance of retrieval systems driven by large language models (LLMs). Our experiments suggest that STARK presents significant challenges to the current retrieval and LLM systems, indicating the demand for building more capable retrieval systems. The benchmark data and code are available on https://github.com/snap-stanford/stark.
BibTeX
@inproceedings{wu2024stark,
  author = {Shirley Wu and Shiyu Zhao and Michihiro Yasunaga and Kexin Huang and Kaidi Cao and Qian Huang and Vassilis N. Ioannidis and Karthik Subbian and James Zou and Jure Leskovec},
  title = {{STaRK: Benchmarking LLM Retrieval on Textual and Relational Knowledge Bases}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
}
Figure