ComLQ: Benchmarking Complex Logical Queries in Information Retrieval

Ganlin Xu, Zhitao Yin, Linghao Zhang, Jiaqing Liang, Weijia Lu, Xiaodong Zhang, Zhifei Yang, Sihang Jiang, Di YangAAAI 2026 · DOI

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:

  1. Passage Selection: They start by selecting passages from a large corpus (Wikipedia).
  2. 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.
  3. 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

Abstract

Information retrieval (IR) systems play a critical role in navigating information overload across various applications. Existing IR benchmarks primarily focus on simple queries that are semantically analogous to single- and multi-hop relations, overlooking complex logical queries involving first-order logic operations such as conjunction (∧), disjunction (∨), and negation (¬). Thus, these benchmarks can not be used to sufficiently evaluate the performance of IR models on complex queries in real-world scenarios. To address this problem, we propose a novel method leveraging large language models (LLMs) to construct a new IR dataset ComLQ for Complex Logical Queries, which comprises 2,909 queries and 11,251 candidate passages. A key challenge in constructing the dataset lies in capturing the underlying logical structures within unstructured text. Therefore, by designing the subgraph-guided prompt with the subgraph indicator, an LLM (such as GPT-4o) is guided to generate queries with specific logical structures based on selected passages. All query-passage pairs in ComLQ are ensured structure conformity and evidence distribution through expert annotation. To better evaluate whether retrievers can handle queries with negation, we further propose a new evaluation metric, Log-Scaled Negation Consistency (LSNC@K). As a supplement to standard relevance-based metrics (such as nDCG and mAP), LSNC@K measures whether top-K retrieved passages violate negation conditions in queries. Our experimental results under zero-shot settings demonstrate existing retrieval models' limited performance on complex logical queries, especially on queries with negation, exposing their inferior capabilities of modeling exclusion. In summary, our ComLQ offers a comprehensive and fine-grained exploration, paving the way for future research on complex logical queries in IR.
BibTeX
@inproceedings{xu2026comlq,
  author = {Ganlin Xu and Zhitao Yin and Linghao Zhang and Jiaqing Liang and Weijia Lu and Xiaodong Zhang and Zhifei Yang and Sihang Jiang and Di Yang},
  title = {{ComLQ: Benchmarking Complex Logical Queries in Information Retrieval}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2026},
  doi = {10.1609/aaai.v40i40.40706},
}
Figure