共找到 20 条结果
Retrieval Augmented Generation (RAG) is a promising technique for mitigating two key limitations of large language models (LLMs): outdated information and hallucinations. RAG system stores documents as embedding vectors in a database. Given a query, search is executed to find the most related documents. Then, the topmost matching documents are inserted into LLMs' prompt to generate a response. Efficient and accurate searching is critical for RAG to get relevant information. We propose a cost-effective searching algorithm for retrieval process. Our progressive searching algorithm incrementally refines the candidate set through a hierarchy of searches, starting from low-dimensional embeddings and progressing into a higher, target-dimensionality. This multi-stage approach reduces retrieval time while preserving the desired accuracy. Our findings demonstrate that progressive search in RAG systems achieves a balance between dimensionality, speed, and accuracy, enabling scalable and high-performance retrieval even for large databases.
We study a variant of the searching problem where the environment consists of a known terrain and the goal is to obtain visibility of an unknown target point on the surface of the terrain. The searcher starts on the surface of the terrain and is allowed to fly above the terrain. The goal is to devise a searching strategy that minimizes the competitive ratio, that is, the worst-case ratio between the distance traveled by the searching strategy and the minimum travel distance needed to detect the target. For $1.5$D terrains we show that any searching strategy has a competitive ratio of at least $\sqrt{82}$ and we present a nearly-optimal searching strategy that achieves a competitive ratio of $3\sqrt{19/2} \approx \sqrt{82} + 0.19$. This strategy extends directly to the case where the searcher has no knowledge of the terrain beforehand. For $2.5$D terrains we show that the optimal competitive ratio depends on the maximum slope $λ$ of the terrain, and is hence unbounded in general. Specifically, we provide a lower bound on the competitive ratio of $Ω(\sqrtλ)$. Finally, we complement the lower bound with a searching strategy based on the maximum slope of the known terrain, which achiev
Inspired by human-like behaviors for navigation: first searching to explore unknown areas before discovering the target, and then the pathfinding of moving towards the discovered target, recent studies design parallel submodules to achieve different functions in the searching and pathfinding stages, while ignoring the differences in reward signals between the two stages. As a result, these models often cannot be fully trained or are overfitting on training scenes. Another bottleneck that restricts agents from learning two-stage strategies is spatial perception ability, since the studies used generic visual encoders without considering the depth information of navigation scenes. To release the potential of the model on strategy learning, we propose the Two-Stage Reward Mechanism (TSRM) for object navigation that decouples the searching and pathfinding behaviours in an episode, enabling the agent to explore larger area in searching stage and seek the optimal path in pathfinding stage. Also, we propose a pretraining method Depth Enhanced Masked Autoencoders (DE-MAE) that enables agent to determine explored and unexplored areas during the searching stage, locate target object and plan
This paper reviews, analyzes, and proposes a new perspective on the bi-encoder architecture for neural search. While the bi-encoder architecture is widely used due to its simplicity and scalability at test time, it has some notable issues such as low performance on seen datasets and weak zero-shot performance on new datasets. In this paper, we analyze these issues and summarize two main critiques: the encoding information bottleneck problem and limitations of the basic assumption of embedding search. We then construct a thought experiment to logically analyze the encoding and searching operations and challenge the basic assumptions of embedding search. Building on these observations, we propose a new perspective on the bi-encoder architecture called the \textit{encoding--searching separation} perspective, which conceptually and practically separates the encoding and searching operations. This framework is applied to explain the root cause of existing issues and suggest mitigation strategies, potentially lowering training costs and improving retrieval performance. Finally, we discuss the broader implications of the ideas underlying this perspective, the new design surface it exposes
Searching dependency graphs and manipulating them can be a time consuming and challenging task to get right. We document Semgrex, a system for searching dependency graphs, and introduce Ssurgeon, a system for manipulating the output of Semgrex. The compact language used by these systems allows for easy command line or API processing of dependencies. Additionally, integration with publicly released toolkits in Java and Python allows for searching text relations and attributes over natural text.
Effective information searching is essential for enhancing the reasoning and generation capabilities of large language models (LLMs). Recent research has explored using reinforcement learning (RL) to improve LLMs' search capabilities by interacting with live search engines in real-world environments. While these approaches show promising results, they face two major challenges: (1) Uncontrolled Document Quality: The quality of documents returned by search engines is often unpredictable, introducing noise and instability into the training process. (2) Prohibitively High API Costs: RL training requires frequent rollouts, potentially involving hundreds of thousands of search requests, which incur substantial API expenses and severely constrain scalability. To address these challenges, we introduce ZeroSearch, a novel RL framework that incentivizes the capabilities of LLMs to use a real search engine with simulated searches during training. Our approach begins with lightweight supervised fine-tuning to transform the LLM into a retrieval module capable of generating both useful and noisy documents in response to a query. During RL training, we employ a curriculum-based rollout strategy
Syntax-guided synthesis is commonly used to generate programs encoding policies. In this approach, the set of programs, that can be written in a domain-specific language defines the search space, and an algorithm searches within this space for programs that encode strong policies. In this paper, we propose an alternative method for synthesizing programmatic policies, where we search within an approximation of the language's semantic space. We hypothesized that searching in semantic spaces is more sample-efficient compared to syntax-based spaces. Our rationale is that the search is more efficient if the algorithm evaluates different agent behaviors as it searches through the space, a feature often missing in syntax-based spaces. This is because small changes in the syntax of a program often do not result in different agent behaviors. We define semantic spaces by learning a library of programs that present different agent behaviors. Then, we approximate the semantic space by defining a neighborhood function for local search algorithms, where we replace parts of the current candidate program with programs from the library. We evaluated our hypothesis in a real-time strategy game calle
The necessary of buiding the searching system being able to support users expressing their searching by natural language queries is very important and opens the researching direction with many potential. It combines the traditional methods of information retrieval and the researching of Question Answering (QA). In this paper, we introduce a searching system built by us for searching courses on the Vietnam OpenCourseWare Program (VOCW). It can be considered as the first tool to be able to perform the user's Vietnamese questions. The experiment results are rather good when we evaluate this system on the precision
Many people have stress to leave their job and start a new one because of the new environment and not enough knowledge about the culture and structure about the new organization they are going to work in. New employees in company normally need to integrate in their working place environment quicker to start doing their job. That makes them ask a lot of questions to their colleagues and sometimes their colleagues are too busy to answer those questions. In the literature is defined that this problem could be solved when new employees use digital system for information as the proposed system for searching of information. Furthermore, the quality of the returned results from the searching system is defined as a standard for the efficiency of the searching systems. Because of this, it is proposed a semantic system for searching information of employees in a company that will help to better orient new employees in a company, to know the position and the function of each employee in the company
This paper is about searching the combinatorial space of contingency tables during the inner loop of a nonlinear statistical optimization. Examples of this operation in various data analytic communities include searching for nonlinear combinations of attributes that contribute significantly to a regression (Statistics), searching for items to include in a decision list (machine learning) and association rule hunting (Data Mining). This paper investigates a new, efficient approach to this class of problems, called RADSEARCH (Real-valued All-Dimensions-tree Search). RADSEARCH finds the global optimum, and this gives us the opportunity to empirically evaluate the question: apart from algorithmic elegance what does this attention to optimality buy us? We compare RADSEARCH with other recent successful search algorithms such as CN2, PRIM, APriori, OPUS and DenseMiner. Finally, we introduce RADREG, a new regression algorithm for learning real-valued outputs based on RADSEARCHing for high-order interactions.
Efficient indexing and searching of high dimensional data has been an area of active research due to the growing exploitation of high dimensional data and the vulnerability of traditional search methods to the curse of dimensionality. This paper presents a new approach for fast and effective searching and indexing of high dimensional features using random partitions of the feature space. Experiments on both handwritten digits and 3-D shape descriptors have shown the proposed algorithm to be highly effective and efficient in indexing and searching real data sets of several hundred dimensions. We also compare its performance to that of the state-of-the-art locality sensitive hashing algorithm.
It is essential to know the arrangement of the atoms in a material in order to compute and understand its properties. Searching for stable structures of materials using first-principles electronic structure methods, such as density functional theory (DFT), is a rapidly growing field. Here we describe our simple, elegant and powerful approach to searching for structures with DFT which we call ab initio random structure searching (AIRSS). Applications to discovering structures of solids, point defects, surfaces, and clusters are reviewed. New results for iron clusters on graphene, silicon clusters, polymeric nitrogen, hydrogen-rich lithium hydrides, and boron are presented.
We introduce the concepts of Grover operators and Grover kernels to systematically analyse Grover's searching algorithms. Then, we investigate a one-parameter family of quantum searching algorithms of Grover's type and we show that the standard Grover's algorithm is a distinguished member of this family. We show that all the algorithms of this class solve the searching problem with an efficiency of order $O(\sqrt{N})$, with a coefficient which is class-dependent. The analysis of this dependence is a test of the stability and robustness of the algorithms. We show the stability of this constructions under perturbations of the initial conditions and extend them upon a very general class of Grover operators.
Vision Transformer has shown great visual representation power in substantial vision tasks such as recognition and detection, and thus been attracting fast-growing efforts on manually designing more effective architectures. In this paper, we propose to use neural architecture search to automate this process, by searching not only the architecture but also the search space. The central idea is to gradually evolve different search dimensions guided by their E-T Error computed using a weight-sharing supernet. Moreover, we provide design guidelines of general vision transformers with extensive analysis according to the space searching process, which could promote the understanding of vision transformer. Remarkably, the searched models, named S3 (short for Searching the Search Space), from the searched space achieve superior performance to recently proposed models, such as Swin, DeiT and ViT, when evaluated on ImageNet. The effectiveness of S3 is also illustrated on object detection, semantic segmentation and visual question answering, demonstrating its generality to downstream vision and vision-language tasks. Code and models will be available at https://github.com/microsoft/Cream.
I improve the tight bound on quantum searching by Boyer et al. (quant-ph/9605034) to a matching bound, thus showing that for any probability of success Grovers quantum searching algorithm is optimal. E.g. for near certain success we have to query the oracle pi/4 sqrt{N} times, where N is the size of the search space. I also show that unfortunately quantum searching cannot be parallelized better than by assigning different parts of the search space to independent quantum computers. Earlier results left open the possibility of a more efficient parallelization.
Deep search agents, which autonomously iterate through multi-turn web-based reasoning, represent a promising paradigm for complex information-seeking tasks. However, current agents suffer from critical inefficiency: they conduct excessive searches as they cannot accurately judge when to stop searching and start answering. This stems from outcome-centric training that prioritize final results over the search process itself. We identify the root cause as misaligned decision boundaries, the threshold determining when accumulated information suffices to answer. This causes over-search (redundant searching despite sufficient knowledge) and under-search (premature termination yielding incorrect answers). To address these errors, we propose a comprehensive framework comprising two key components. First, we introduce causal intervention-based diagnosis that identifies boundary errors by comparing factual and counterfactual trajectories at each decision point. Second, we develop Decision Boundary Alignment for Deep Search agents (DAS), which constructs preference datasets from causal feedback and aligns policies via preference optimization. Experiments on public datasets demonstrate that de
Multi-hop claim verification is inherently challenging, requiring multi-step reasoning to construct verification chains while iteratively searching for information to uncover hidden bridging facts. This process is fundamentally interleaved, as effective reasoning relies on dynamically retrieved evidence, while effective search demands reasoning to refine queries based on partial information. To achieve this, we propose Hierarchical Agent Reasoning and Information Search (HARIS), explicitly modeling the coordinated process of reasoning-driven searching and search-informed reasoning. HARIS consists of a high-level reasoning agent that focuses on constructing the main verification chain, generating factual questions when more information is needed, and a low-level search agent that iteratively retrieves more information, refining its search based on intermediate findings. This design allows each agent to specialize in its respective task, enhancing verification accuracy and interpretability. HARIS is trained using reinforcement learning with outcome-based rewards. Experimental results on the EX-FEVER and HOVER benchmarks demonstrate that HARIS achieves strong performance, greatly adva
Purpose: The timespan over which exploratory searching can occur, as well as the scope and volume of the search activities undertaken, can make it difficult for searchers to remember key details about their search activities. These difficulties are present both in the midst of searching as well as when resuming a search that spans multiple sessions. In this paper, we present a search interface design and prototype implementation to support cross-session exploratory search in a public digital library context. Methods: Search Timelines provides a visualization of current and past search activities via a dynamic timeline of the search activity (queries and saved resources). This timeline is presented at two levels of detail. An Overview Timeline is provided alongside the search results in a typical search engine results page design. A Detailed Timeline is provided in the workspace, where searchers can review the history of their search activities and their saved resources. A controlled laboratory study (n=32) was conducted to compare this approach to a baseline interface modelled after a typical public digital library search/workspace interface. Results: Participants who used Search T
Quantum walk followed by some amplitude amplification technique has been successfully used to search for marked vertices on various graphs. Lackadaisical quantum walk can search for target vertices on graphs without the help of any additional amplitude amplification technique. These studies either exploit AKR or SKW coin to distinguish the marked vertices from the unmarked vertices. The success of AKR coin based quantum walk search algorithms highly depend on the arrangements of the set of marked vertices on the graph. For example, it fails to find adjacent vertices, diagonal vertices and other exceptional configurations of vertices on a two-dimensional periodic square lattice and on other graphs. These coins also suffer from low success probability while searching for marked vertices on a one-dimensional periodic lattice and on other graphs for certain arrangements for marked vertices. In this article, we propose a modified coin for the lackadaisical quantum walk search. It allows us to perform quantum walk search for the marked vertices by doing Grover search on the coin space. Our model finds the marked vertices by searching the self-loops associated with the marked vertices. It
We introduce the study of search games between a mobile Searcher and an immobile Hider in a new setting in which the Searcher has some potentially erroneous information, i.e., a prediction on the Hider's position. The objective is to establish tight tradeoffs between the consistency of a search strategy (i.e., its worst case expected payoff assuming the prediction is correct) and its robustness (i.e., the worst case expected payoff with no assumptions on the quality of the prediction). Our study is the first to address the full power of mixed (randomized) strategies; previous work focused only on deterministic strategies, or relied on stochastic assumptions that do not guarantee worst-case robustness in adversarial situations. We give Pareto-optimal strategies for three fundamental problems, namely searching in discrete locations, searching with stochastic overlook, and searching in the infinite line. As part of our contribution, we provide a novel framework for proving optimal tradeoffs in search games which is applicable, more broadly, to any two-person zero-sum games in learning-augmented settings.