approximate nearest neighbor search (anns) is now widely used in various applications including information retrieval, question answering, and recommendation. as the amount of vector data grows continuously, it becomes important to support updates to vector index, the enabling technique that allows for efficient and accurate anns on vectors.
because of the curse of high dimensionality, it is often costly to identify the right neighbors of a single new vector, a necessary process for index update. to amortize update costs, existing systems maintain a secondary index to accumulate updates, which are merged by the main index by global rebuilding the entire index periodically. however, this approach has high fluctuations of search latency and accuracy, not even to mention that it requires substantial resources and is extremely time-consuming for rebuilds.
we introduce spfresh, a system that supports in-place vector updates. at the heart of spfresh is lire, a lightweight incremental rebalancing protocol to split vector partitions and reassign vectors in the nearby partitions to adapt to data distribution shift. lire achieves low-overhead vector updates by only reassigning vectors at the boundary between partitions, where in a high-quality vector index the amount of such vectors are deemed small. with lire, spfresh provides superior query latency and accuracy to solutions based on global rebuild, with only 1% of dram and less than 10% cores needed at the peak compared to the state-of-the-art, in a billion scale disk-based vector index with a 1% of daily vector update rate.
in this paper, we present brainstorm, a deep learning framework for optimizing dynamic nns, which bridges the gap by unifying how dynamism should be expressed. brainstorm proposes (1) cell, the key data abstraction that lets model developers express the data granularity where dynamism exists, and (2) router, a unified interface to let model developers express how cells should be dynamically dispatched. brainstorm handles efficient execution of routing actions. this design allows brainstorm to collect profiles of fine-grained dataflow at the correct granularity. the traceability further opens up a new space of dynamic optimization for dynamic nns to specialize their execution to the runtime dynamism distribution. extensive evaluations show brainstorm brings up to 11.7× speedup (3.29× on average) or leads to 42% less memory consumption for popular dynamic neural networks with the proposed dynamic optimizations.
dynamic sparsity, where the sparsity patterns are unknown until runtime, poses a significant challenge to deep learning. the state-of-the-art sparsity-aware deep learning solutions are restricted to pre-defined, static sparsity patterns due to significant overheads associated with preprocessing. efficient execution of dynamic sparse computation often faces the misalignment between the gpu-friendly tile configuration for efficient execution and the sparsity-aware tile shape that minimizes coverage wastes (non-zero values in tensor).
in this paper, we propose pit, a deep-learning compiler for dynamic sparsity. pit proposes a novel tiling mechanism that leverages permutation invariant transformation (pit), a mathematically proven property, to transform multiple sparsely located micro-tiles into a gpu-efficient dense tile without changing the computation results, thus achieving both high gpu utilization and low coverage waste. given a model, pit first finds feasible pit rules for all its operators and generates efficient gpu kernels accordingly. at runtime, with the sread and swrite primitives, pit rules can be executed extremely fast to support dynamic sparsity in an online manner. extensive evaluation on diverse models shows that pit can accelerate dynamic sparsity computation by up to 5.9x over state-of-the-art compilers.
in this paper, we introduce positional skip-wise (pose) training for efficient adaptation of large language models~(llms) to extremely long context windows. pose decouples train length from target context window size by simulating long inputs using a fixed context window with manipulated position indices during training. concretely, we select several short chunks from a long input sequence, and introduce distinct skipping bias terms to modify the position indices of each chunk. these bias terms, along with the length of each chunk, are altered for each training example, allowing the model to adapt to all positions within the target context window without training on full length inputs. experiments show that, compared with fine-tuning on the full length, pose greatly reduces memory and time overhead with minimal impact on performance. leveraging this advantage, we have successfully extended the llama model to 128k tokens. furthermore, we empirically confirm that pose is compatible with all rope-based llms and various position interpolation strategies. notably, by decoupling fine-tuning length from target context window, pose can theoretically extend the context window infinitely, constrained only by memory usage for inference. with ongoing advancements for efficient inference, we believe pose holds great promise for scaling the context window even further.
in many real-world tasks, some parts of state features, called contexts, are independent of action signals, e.g., customer demand in inventory control, speed of lead car in autonomous driving, etc. one of the challenges of reinforcement learning in these applications is that the true context transitions can be easily exposed some unknown source of contamination, leading to a shift of context transitions between source domains and target domains, which could cause performance degradation for rl algorithms. however, existing methods on robust rl aim at learning robust policies against the deviations of the entire system dynamics. to tackle this problem, this paper proposes the framework of robust situational markov decision process (rs-mdp) which captures the possible deviations of context transitions explicitly. to scale to large context space, we introduce the softmin smoothed robust bellman operator to learn the robust q-value approximately, and apply our rs-mdp framework to existing rl algorithm sac to learn the desired robust policies. we conduct experiments on several robot control tasks with dynamic contexts and inventory control tasks to demonstrate that our algorithm can generalize better and more robust against deviations of context transitions, and outperform existing robust rl algorithms.
we present kosmos-2.5, a multimodal literate model for machine reading of text-intensive images. pre-trained on large-scale text-intensive images, kosmos-2.5 excels in two distinct yet cooperative transcription tasks: (1) generating spatially-aware text blocks, where each block of text is assigned its spatial coordinates within the image, and (2) producing structured text output that captures styles and structures into the markdown format. this unified multimodal literate capability is achieved through a shared transformer architecture, task-specific prompts, and flexible text representations. we evaluate kosmos-2.5 on end-to-end document-level text recognition and image-to-markdown text generation. furthermore, the model can be readily adapted for any text-intensive image understanding task with different prompts through supervised fine-tuning, making it a general-purpose tool for real-world applications involving text-rich images. this work also paves the way for the future scaling of multimodal large language models.
large language models (llms) have been applied in various applications due to their astonishing capabilities. with advancements in technologies such as chain-of-thought (cot) prompting and in-context learning (icl), the prompts fed to llms are becoming increasingly lengthy, even exceeding tens of thousands of tokens. to accelerate model inference and reduce cost, this paper presents llmlingua, a coarse-to-fine prompt compression method that involves a budget controller to maintain semantic integrity under high compression ratios, a token-level iterative compression algorithm to better model the interdependence between compressed contents, and an instruction tuning based method for distribution alignment between language models. we conduct experiments and analysis over four datasets from different scenarios, i.e., gsm8k, bbh, sharegpt, and arxiv-march23; showing that the proposed approach yields state-of-the-art performance and allows for up to 20x compression with little performance loss.