TL;DR
This paper introduces ComLQ, a new benchmark dataset for evaluating information retrieval (IR) systems on complex logical queries that involve operations like conjunction, disjunction, and negation. They also propose a novel metric, LSNC@K, to specifically assess how well systems handle negation. Experiments reveal that current IR models struggle significantly with these complex queries, especially those involving negation, highlighting a critical gap in their capabilities.
What Problem Does This Paper Address?
Modern information retrieval (IR) systems are essential for navigating the vast amount of information available online. However, existing IR benchmarks primarily focus on simple queries that can be answered by following single or multi-hop relationships. This overlooks a significant portion of real-world user queries that involve more complex logical reasoning, such as combining multiple conditions (conjunction), considering alternatives (disjunction), or excluding certain information (negation). These complex queries are often expressible using first-order logic (FOL). The lack of comprehensive benchmarks for these complex logical queries means that current IR models may not be adequately evaluated for their ability to handle sophisticated information needs, particularly those involving exclusion.
Methods
The authors tackle this problem by introducing a novel data synthesis process to create the ComLQ dataset. This process involves:
- Passage Selection: They start by selecting passages from a large corpus (Wikipedia).
- Subgraph-Guided Prompt Design: A key innovation is the use of a "subgraph-guided prompt" for Large Language Models (LLMs) like GPT-4o. This prompt includes a "subgraph indicator" that helps the LLM understand and generate queries with specific logical structures (e.g., projection, intersection, negation) based on the selected passages. This approach combines the generative power of LLMs with symbolic logic for structural control.
- Expert Verification: To ensure data quality, human annotators rigorously review each generated query-passage pair for "structure conformity" (does the query adhere to the intended logical structure?) and "evidence distribution" (is the supporting evidence for the query spread across the passages as intended?).
To specifically evaluate negation handling, they propose a new metric: Log-Scaled Negation Consistency (LSNC@K). This metric measures how often the top-K retrieved passages violate the negation conditions specified in a query, complementing standard relevance metrics like nDCG and mAP.
Datasets
The primary dataset introduced in this paper is ComLQ.
- ComLQ: This dataset comprises 2,909 queries and 11,251 candidate passages. It covers 9 query types without negation and 5 query types with negation, aiming for a balanced distribution to evaluate negation handling. The queries are designed to represent complex logical structures like projection, intersection, union, and negation.
- Wikipedia: Used as the source for passage selection during the ComLQ dataset construction.
Key Insights and Ideas
- LLMs as Query Generators: Leveraging LLMs with carefully designed prompts (especially the subgraph indicator) is an effective way to automatically generate complex logical queries that are grounded in real text.
- The "Negation Gap": Current IR models exhibit a significant weakness in handling queries with negation. This isn't just about relevance; it's about understanding and respecting exclusion criteria.
- Order Matters: The order of logical operations in a query can drastically impact retrieval performance. For instance, intersection-then-projection queries are easier for models than projection-then-intersection queries.
- Sparse vs. Dense: Surprisingly, traditional sparse retrievers like BM25 can still be competitive with, and sometimes outperform, dense retrievers on these complex logical queries, challenging the assumption that dense models always dominate.
- Subgraph Indicator is Crucial: The subgraph indicator in the prompt is vital for LLMs to generate structurally consistent and accurate complex logical queries. Without it, LLMs struggle more with complex structures.
Key Results
- Performance Degradation: All tested retrieval models show a consistent performance degradation as query complexity increases (e.g., from 1-hop to 3-hop queries).
- Negation Weakness: Models perform significantly worse on queries involving negation. LSNC@100 scores are consistently low across all models for negation queries, indicating a widespread inability to model exclusion.
- BM25 Competitiveness: BM25 outperformed other models on several query types and was competitive overall, sometimes even surpassing dense retrievers.
- Order Impact: Retrievers performed worse on projection-then-intersection queries compared to intersection-then-projection queries.
- Evidence Distribution Challenge: Queries requiring information from multiple passages are more challenging for retrievers.
Limitations and Future Work
- Limitations:
- The paper acknowledges that current retrieval models exhibit significant limitations on complex logical queries, particularly with negation.
- The study was conducted under zero-shot settings, meaning models were not fine-tuned on the ComLQ dataset. This highlights the inherent capabilities of the models rather than their potential after adaptation.
- Future Work:
- The ComLQ dataset and the proposed LSNC metric are intended to pave the way for future research on complex logical queries in IR.
- There is a clear need for developing specialized retrieval approaches tailored to different logical structures and for improving models' ability to handle exclusion and complex semantic compositions.
- Further research is needed to bridge the gap in models' capabilities for reasoning over complex structures and negation.
Summary updated