Long-context Large Language Models (LLMs) have enabled numerous downstream applications but also introduced significant challenges related to computational and memory efficiency. To address these challenges, optimizations for long-context inference have been developed, centered around the KV cache. However, existing benchmarks often evaluate in single-request, neglecting the full lifecycle of the KV cache in real-world use. This oversight is particularly critical, as KV cache reuse has become widely adopted in LLMs inference frameworks, such as vLLM and SGLang, as well as by LLM providers, including OpenAI, Microsoft, Google, and Anthropic. To address this gap, we introduce SCBENCH (SharedContextBENCH), a comprehensive benchmark for evaluating long-context methods from a KV cache centric perspective: 1) KV cache generation, 2) KV cache compression, 3) KV cache retrieval, and 4) KV cache loading. Specifically, SCBench uses test examples with shared context, ranging 12 tasks with two shared context modes, covering four categories of long-context capabilities: string retrieval, semantic retrieval, global information, and multi-task. With SCBench, we provide an extensive KV cache-centric analysis of eight categories long-context solutions, including Gated Linear RNNs (Codestal-Mamba), Mamba-Attention hybrids (Jamba-1.5-Mini), and efficient methods such as sparse attention, KV cache dropping, quantization, retrieval, loading, and prompt compression. The evaluation is conducted on six Transformer-based long-context LLMs: Llama-3.1-8B/70B, Qwen2.5-72B/32B, Llama-3-8B-262K, and GLM-4-9B. Our findings show that sub-O(n) memory methods suffer in multi-turn scenarios, while sparse encoding with O(n) memory and sub-O(n^2) pre-filling computation perform robustly. Dynamic sparsity yields more expressive KV caches than static patterns, and layer-level sparsity in hybrid architectures reduces memory usage with strong performance. Additionally, we identify attention distribution shift issues in long-generation scenarios.

The integration of long-context capabilities with visual understanding unlocks unprecedented potential for Vision Language Models (VLMs). However, the quadratic attention complexity during the pre-filling phase remains a significant obstacle to real-world deployment. To overcome this limitation, we introduce MMInference (Multimodality Million tokens Inference), a dynamic sparse attention method that accelerates the prefilling stage for long-context multi-modal inputs. First, our analysis reveals that the temporal and spatial locality of video input leads to a unique sparse pattern, the Grid pattern. Simultaneously, VLMs exhibit markedly different sparse distributions across different modalities. We introduce a permutation-based method to leverage the unique Grid pattern and handle modality boundary issues. By offline search the optimal sparse patterns for each head, MMInference constructs the sparse distribution dynamically based on the input. We also provide optimized GPU kernels for efficient sparse computations. Notably, MMInference integrates seamlessly into existing VLM pipelines without any model modifications or fine-tuning. Experiments on multi-modal benchmarks-including Video QA, Captioning, VisionNIAH, and Mixed-Modality NIAH-with state-of-the-art long-context VLMs (LongVila, LlavaVideo, VideoChat-Flash, Qwen2.5-VL) show that MMInference accelerates the pre-filling stage by up to 8.3x at 1M tokens while maintaining accuracy. Our code is available at https://ama.ms/MMInference.

The computational challenges of Large Language Model (LLM) inference remain a significant barrier to their widespread deployment, especially as prompt lengths continue to increase. Due to the quadratic complexity of the attention computation, it takes 30 minutes for an 8B LLM to process a prompt of 1M tokens (i.e., the pre-filling stage) on a single A100 GPU. Existing methods for speeding up prefilling often fail to maintain acceptable accuracy or efficiency when applied to long-context LLMs. To address this gap, we introduce MInference (Milliontokens Inference), a sparse calculation method designed to accelerate pre-filling of long-sequence processing. Specifically, we identify three unique patterns in long-context attention matrices-the A-shape, Vertical-Slash, and Block-Sparse-that can be leveraged for efficient sparse computation on GPUs. We determine the optimal pattern for each attention head offline and dynamically build sparse indices based on the assigned pattern during inference. With the pattern and sparse indices, we perform efficient sparse attention calculations via our optimized GPU kernels to significantly reduce the latency in the pre-filling stage of longcontext LLMs. Our proposed technique can be directly applied to existing LLMs without any modifications to the pre-training setup or additional fine-tuning. By evaluating on a wide range of downstream tasks, including InfiniteBench, RULER, PG-19, and Needle In A Haystack, and models including LLaMA-3-1M, GLM-4-1M, Yi-200K, Phi-3-128K, and Qwen2-128K, we demonstrate that MInference effectively reduces inference latency by up to 10x for pre-filling on an A100, while maintaining accuracy. Our code is available at https://aka.ms/MInference.

We consider the group testing problem over probabilistic community-oriented infection models, which have attracted significant attention in the wake of the COVID-19 pandemic. To the best of our knowledge, existing theoretical results on the complexity of group testing in such settings are derived under the assumption that tests are noiseless. We present novel upper and lower bounds for the noisy case, focusing on adaptive group testing schemes tailored to the community structure of the population. For the achievability result, we devise an algorithm which incorporates knowledge of the community structure into a noisy binary search procedure from [1]. Our algorithm exhibits favorable performance in the context of the recently-introduced stochastic block infection model [2]. Furthermore, our lower bound applies to any adaptive algorithm, any probabilistic infection model, and any (noisy or noiseless) testing model satisfying certain natural criteria, and thus can be of independent interest.

Group testing was conceived during World War II to identify soldiers infected with syphilis using as few tests as possible, and it has attracted renewed interest during the COVID-19 pandemic. A long-standing assumption in the probabilistic variant of the group testing problem is that individuals are infected by the diseaseindependently. However, this assumption rarely holds in practice, as diseases often spread through interactions between individuals and therefore cause infections to be correlated. Inspired by characteristics of COVID-19 and other infectious diseases, we introduce an infection model over networks which generalizes the traditional i.i.d. model from probabilistic group testing. Under this model, we ask whether knowledge of the network structure can be leveraged to perform group testing more efficiently, focusing specifically on community-structured graphs drawn from the stochastic block model. We prove that a simple community-aware algorithm outperforms the baseline binary splitting algorithm when the model parameters are conducive to “strong community structure.” Moreover, our novel lower bounds imply that the community-aware algorithm is order-optimal in certain parameter regimes. We extend our bounds to the noisy setting and support our results with numerical experiments.

We consider the problem of estimating a d-dimensional, s-sparse discrete distribution from independent samples subject to a joint b-bit communication constraint and ε-local differential privacy constraint. As an intermediate step, we introduce the Privatized Random Hashing (PRH) scheme, which concatenates a hashing-based quantization strategy with the randomized response privacy mechanism. Despite its simplicity, PRH turns out to achieve the order-optimal minimax estimation error and sample complexity in the standard (non-sparse) estimation setting, for all communication and privacy regimes. We then address the sparse case by developing a two-stage, non-interactive estimation scheme based on PRH in which the first half of samples are used to localize the unknown support of the distribution, and the remaining samples are used to obtain precise estimates of the individual probabilities. Using this scheme, we characterize the minimax sample complexity of the sparse case up to logarithmic factors, unifying existing results in the literature that considered communication and privacy constraints separately.

Since the inception of the group testing problem in World War II, one of the prevailing assumptions in the probabilistic variant of the problem has been that individuals in the population are infected by a disease independently. However, this assumption rarely holds in practice, as diseases typically spread through interactions between individuals and therefore cause infections to be correlated. Inspired by characteristics of COVID-19 and similar diseases, we consider an infection model over networks which generalizes the traditional i.i.d. model from probabilistic group testing. Under this infection model, we ask whether knowledge of the network structure can be leveraged to perform group testing more efficiently, focusing specifically on community-structured graphs drawn from the stochastic block model. We prove that when the network and infection parameters are conducive to “strong community structure;” our proposed adaptive, graph-aware algorithm outperforms the baseline binary splitting algorithm, and is even order-optimal in certain parameter regimes. A full version of this paper is accessible at http://arxiv.org/abs/2101.0240S. Omitted proofs and numerical experiments are provided in the full version

We propose a grant-free random access scheme for short-packet communication on a collision channel without feedback, where user identities are conveyed through their activity patterns. We show that this problem is inherently related to the non-adaptive group testing problem, where the goal is to identify a small subset of defective items within a larger population, using as few (pre-determined) tests as possible. In the frame-synchronous case, where users' transmissions are aligned, we find that any solution to the non-adaptive group testing problem is also a solution to the random access problem. Similar connections to group testing are identified in the asynchronous variant of the problem, in which case users' transmissions within a frame are received with arbitrary and unknown delays at the receiver. We show that such delays can be accommodated without any additional penalty with respect to the scaling of the transmission length, and that in the regime where the data payload is small, the performance of the proposed random access scheme comes close to that of fully coordinated access schemes.

Augmented reality (AR) technologies have seen significant improvement in recent years with several consumer and commercial solutions being developed. New security challenges arise as AR becomes increasingly ubiquitous. Previous work has proposed techniques for securing the output of AR devices and used reinforcement learning (RL) to train security policies which can be difficult to define manually. However, whether such systems and policies can be deployed on a physical AR device without degrading performance was left an open question. We develop a visual output security application using a RL trained policy and deploy it on a Magic Leap One head-mounted AR device. The demonstration illustrates that RL based visual output security systems are feasible.