B ool Q uestions: Does Dense Retrieval Understand B oolean Logic in Language? (2024)

Abstract: Dense retrieval, which aims to encode the semantic information of arbitrary text into dense vector representations or embeddings, has emerged as an effective and efficient paradigm for text retrieval, consequently becoming an essential component in various natural language processing systems. These systems typically focus on optimizing the embedding space by attending to the relevance of text pairs, while overlooking the Boolean logic inherent in language, which may not be captured by current training objectives. In this work, we first investigate whether current retrieval systems can comprehend the Boolean logic implied in language. To answer this question, we formulate the task of Boolean Dense Retrieval and collect a benchmark dataset, BoolQuestions, which covers complex queries containing basic Boolean logic and corresponding annotated passages. Through extensive experimental results on the proposed task and benchmark dataset, we draw the conclusion that current dense retrieval systems do not fully understand Boolean logic in language, and there is a long way to go to improve our dense retrieval systems. Furthermore, to promote further research on enhancing the understanding of Boolean logic for language models, we explore Boolean operation on decomposed query and propose a contrastive continual training method that serves as a strong baseline for the research community.

## introduction text retrieval is a fundamental component of various natural language processing systems, including question answering @xcite , dialogue systems @xcite , web search @xcite and so on. in the era of large language models, text retrieval has become increasingly critical as it provides an offline 1 code and dataset are available at https://github.com/ zmzhang2000/boolean-dense-retrieval . and incrementally updatable knowledge database, directly influencing the reliability and quality of generated responses @xcite in the retrieval-augmented generation paradigm @xcite . traditional text retrieval methods estimate the relevance of query and document based on lexical overlap @xcite . utilizing the "bag-of-words" assumption and set theory @xcite , these methods organize text content in the form of inverted indexes @xcite , which handle boolean logic efficiently. the boolean retrieval model was later extended to return ranked lists of documents by leveraging term weights @xcite . to more flexibly consider the weights of different words, probabilistic models such as bm25 @xcite and statistical language modeling @xcite were introduced. nevertheless, these probabilistic models still rely on lexical overlap while omitting boolean operations, making it hard to handle boolean logic in queries. with the advent of deep learning, these handcrafted sparse text features have gradually been replaced by low-dimensional dense vectors learned by neural networks @xcite @xcite , particularly using lstm @xcite and the powerful transformer architecture @xcite . unlike sparse vector spaces, dense vectors are believed to capture the semantics implied in texts @xcite . in these frameworks, retrieval systems are expected to assign high scores to ground-truth query-document pairs and relatively lower scores to irrelevant or randomly combined pairs, often framed within modern deep learning paradigms such as contrastive learning frameworks. benefiting from pre-trained language models, text retrieval has achieved significant performance improvements @xcite @xcite . however, dense retrieval systems primarily focus on encoding the relevance of texts, which may be insufficient for handling complex boolean logic in natural language queries. specifically, since current retrieval systems do not incorporate boolean logic in their training paradigms, there is no guarantee of comparability in the output scores for querydocument pairs involving boolean logic. for example, the relevance scores for queries containing logical not, which exclude undesired information, have not been thoroughly investigated. in contrast, lexical-based retrieval systems effectively address complex boolean logic using set theory, a method not directly applicable to dense retrieval. consequently, it remains unclear whether dense retrieval systems can fully comprehend and process complex boolean logic. to answer this question, we formulate the task of boolean dense retrieval (bdr) and collect a benchmark dataset, boolquestions, which includes complex queries containing basic boolean logic and corresponding annotated passages. we evaluate several state-of-the-art dense retrieval systems on the proposed task and benchmark dataset, finding significant performance drops on not questions, as illustrated in figure 1 . our findings indicate that current dense retrieval models do not fully understand boolean logic in language. based on these observations, we generate additional training data for not questions and propose a contrastive continual learning baseline to enhance the understanding of logical not in natural language. while the proposed baseline reduces the negative rate of the passage list returned by retrieval systems, it also slightly sacrifices accuracy. this phenomenon underscores the difficulty of understanding logical not in natural language for dense retrieval systems. nevertheless, the proposed baseline serves as a starting point for further research on dense retrieval in the community. ## related work in this section, we briefly introduce several highly related works about our work. ## task definition in this section, we initially review the technique of dense retrieval, subsequently give a formal definition of what we term as boolean dense retrieval. the objective of text retrieval is to identify documents within a substantial text corpus that are relevant to specific queries. we denote the query text by q and the corpus by @xmath0. typically, retrieval models evaluate each document in the corpus, assigning relevance scores and returning the top k documents based on these scores. the scoring function is typically implemented through either lexical or semantic matching methodologies. in this work, we focus on dense retrieval models, which are reputed for their capacity to encode the semantics of language into a dense vector representation. in dense retrieval, both query and document texts are represented as dense vectors, and their relevance is assessed within this vector space, expressed as: apart from the construction of the query, the retrieval process remains consistent as outlined above. moreover, because our query incorporates a more intricate construction method, we emphasize the need for more sophisticated evaluation metrics and training techniques for retrieval models. ## data collection in our work, we developed a question generation framework that progresses from simple to complex structures to gather questions embedded with simple questioner simple questioner simple questioner simple questioner disjunctive questioner or question converter not question converter and question converter answerer answerer answerer simple questioner disjunctive questioner or question converter not question converter and question converter answerer prompts boolean questions generation cyclic consistency filtering passage 1 passage 2 passage 4 passage 1 passage 2 passage 3 passage 3 simple question simple question simple question simple question disjunctive question or question not question and question or question not question and question answer answer cannot answer boolean logic. specifically, the process involves sampling text passages from a corpus, generating basic questions from these passages, and then combining these questions using boolean operators. the combined questions are subsequently rephrased into natural language. to ensure the relevance between generated questions and corresponding passages, we introduce a cyclic consistency filtering strategy, retaining only those questions that meet this criterion. addressing the challenge posed by restricted access to query logs in widely used search engines, we leverage gpt-4 foot_0 , one of the most advanced language generation models currently available. this model is tasked with constructing boolean questions tailored to the document collections found in prevalent retrieval datasets. next, we will provide a detailed introduction to our data collection pipeline, which is shown in figure 2 . all prompts used are detailed in appendix a. ## data analysis in this section, we detail statistics of the proposed boolquestions, analyze the distribution of question types and display examples to provide a more intuitive understanding of our data. ## experiments in this section, we begin by describing the metrics employed in our experiments. we then evaluate the performance of prevalent dense retrievers on the proposed dataset, introduce two baseline methods for approaching the boolean dense retrieval task, and finally, conduct a detailed analysis of these baseline methods. ## conclusions in this work, we formulate the task of boolean dense retrieval and investigate whether current dense retrieval systems understand boolean logic implied in natural language queries. by collecting a benchmark dataset boolquestions and evaluating the performance of prevalent dense retrievers, we find that not questions are challenging for current dense retrieval systems to understand correctly. further, we explore boolean operation on decomposed query and propose a contrastive continual training method that serves as a strong baseline for the research community.