检索结果-内蒙古大学图书馆

Limits of KV Cache Compression for Tensor Attention based Autoregressive Transformers

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Chen, Yifang Li, Xiaoyu Liang, Yingyu Shi, Zhenmei Song, Zhao Tian, Yu The University of Chicago United States Stevens Institute of Technology United States The University of Hong Kong Hong Kong University of Wisconsin-Madison United States The Simons Institute for the Theory of Computing UC Berkeley United States

The key-value (KV) cache in autoregressive transformers presents a significant bottleneck during inference, which restricts the context length capabilities of large language models (LLMs). While previous work analyzes the fundamental space complexity barriers in standard attention mechanism [Haris and Onak, 2025], our work generalizes the space complexity barriers result to tensor attention version. Our theoretical contributions rely on a novel reduction from communication complexity and deduce the memory lower bound for tensor-structured attention mechanisms when d = Ω(log n). In the low dimensional regime where d = o(log n), we analyze the theoretical bounds of the space complexity as well. Overall, our work provides a theoretical foundation for us to understand the compression-expressivity tradeoff in tensor attention mechanisms and offers more perspectives in developing more memory-efficient transformer architectures. © 2025, CC BY.

关键词： Tensors

Force Matching with Relativistic Constraints: A Physics-Inspired Approach to Stable and Efficient Generative Modeling

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Cao, Yang Chen, Bo Li, Xiaoyu Liang, Yingyu Sha, Zhizhou Shi, Zhenmei Song, Zhao Wan, Mingda Wyoming Seminary Middle Tennessee State University Stevens Institute of Technology The University of Hong Kong University of Wisconsin-Madison Tsinghua University Simons Institute for the Theory of Computing University of California Berkeley United States Anhui University

This paper introduces Force Matching (ForM), a novel framework for generative modeling that represents an initial exploration into leveraging special relativistic mechanics to enhance the stability of the sampling process. By incorporating the Lorentz factor, ForM imposes a velocity constraint, ensuring that sample velocities remain bounded within a constant limit. This constraint serves as a fundamental mechanism for stabilizing the generative dynamics, leading to a more robust and controlled sampling process. We provide a rigorous theoretical analysis demonstrating that the velocity constraint is preserved throughout the sampling procedure within the ForM framework. To validate the effectiveness of our approach, we conduct extensive empirical evaluations. On the half-moons dataset, ForM significantly outperforms baseline methods, achieving the lowest Euclidean distance loss of 0.714, in contrast to vanilla first-order flow matching (5.853) and first- and second-order flow matching (5.793). Additionally, we perform an ablation study to further investigate the impact of our velocity constraint, reaffirming the superiority of ForM in stabilizing the generative process. The theoretical guarantees and empirical results underscore the potential of integrating special relativity principles into generative modeling. Our findings suggest that ForM provides a promising pathway toward achieving stable, efficient, and flexible generative processes. This work lays the foundation for future advancements in high-dimensional generative modeling, opening new avenues for the application of physical principles in machine learning. © 2025, CC BY.

关键词： Generative adversarial networks

An MSVL Based Model Checking Method for Multi-threaded C Programs 10th

学校读者我要写书评

暂无评论

An MSVL Based Model Checking Method for Multi-threaded C Pro...

International Workshop on Structured Object-Oriented Formal Language and Method, SOFL+MSVL 2020

作者： Shu, Xinfeng Wang, Zhenyu Gao, Weiran Wang, Xiaobing Zhao, Liang School of Computer Science and Technology Xi’an University of Posts and Telecommunications Xi’an710061 China Institute of Computing Theory and Technology Xidian University Xi’an710071 China

ISBN: (纸本)9783030774738

To solve the problem that software testing is unable to meet the verification needs of multi-threaded C programs, a novel verification approach with Modeling, Simulation and Validation Language (MSVL) is proposed. To this end, the rules for describing the parallel execution semantics of multi-threaded C program with MSVL are defined,, and a specific tool is developed for automatically translating a multi-threaded C program into its equivalent MSVL program. In addition, an example is given to illustrate how the approach works. The approach fully utilizes the powerful expressiveness of MSVL to verify the multi-threaded C programs in a direct way, and helps to improve the quality of the software system. © 2021, Springer Nature Switzerland AG.

关键词： Model checking

Efficient Quantum Pseudorandomness from Hamiltonian Phase States

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Bostanci, John Haferkamp, Jonas Hangleiter, Dominik Poremba, Alexander Columbia University United States Harvard University United States QuICS University of Maryland & NIST United States Simons Institute for the Theory of Computing UC Berkeley United States Massachusetts Institute of Technology United States

Quantum pseudorandomness has found applications in many areas of quantum information, ranging from entanglement theory, to models of scrambling phenomena in chaotic quantum systems, and, more recently, in the foundations of quantum cryptography. Kretschmer (TQC’21) showed that both pseudorandom states and pseudorandom unitaries exist even in a world without classical one-way functions. To this day, however, all known constructions require classical cryptographic building blocks which are themselves synonymous with the existence of one-way functions, and which are also challenging to implement on realistic quantum hardware. In this work, we seek to make progress on both of these fronts simultaneously—by decoupling quantum pseudorandomness from classical cryptography altogether. We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem, which is the task of decoding output states of a random instantaneous quantum polynomial-time (IQP) circuit. Hamiltonian phase states can be generated very efficiently using only Hadamard gates, single-qubit Z rotations and CNOT circuits. We show that the hardness of our problem reduces to a worst-case version of the problem, and we provide evidence that our assumption is plausibly fully quantum;meaning, it cannot be used to construct one-way functions. We also show information-theoretic hardness when only few copies of HPS are available by proving an approximate t-design property of our ensemble. Finally, we show that our HPS assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives, ranging from pseudorandom states, to quantum pseudoentanglement, to pseudorandom unitaries, and even primitives such as public-key encryption with quantum keys. Along the way, we analyze a natural iterative construction of pseudorandom unitaries which resembles a candidate of Ji, Liu, and Song (CRYPTO’18). © 2024, CC BY.

关键词： Hamiltonians

Theoretical Guarantees for High Order Trajectory Refinement in Generative Flows

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Gong, Chengyue Li, Xiaoyu Liang, Yingyu Long, Jiangxuan Shi, Zhenmei Song, Zhao Tian, Yu The University of Texas Austin United States Stevens Institute of Technology United States The University of Hong Kong Hong Kong University of Wisconsin-Madison United States South China University of Technology China The Simons Institute for the Theory of Computing UC Berkeley United States

Flow matching has emerged as a powerful framework for generative modeling, offering computational advantages over diffusion models by leveraging deterministic Ordinary Differential Equations (ODEs) instead of stochastic dynamics. While prior work established the worst case optimality of standard flow matching under Wasserstein distances, the theoretical guarantees for higher-order flow matching - which incorporates acceleration terms to refine sample trajectories - remain unexplored. In this paper, we bridge this gap by proving that higher-order flow matching preserves worst case optimality as a distribution estimator. We derive upper bounds on the estimation error for second-order flow matching, demonstrating that the convergence rates depend polynomially on the smoothness of the target distribution (quantified via Besov spaces) and key parameters of the ODE dynamics. Our analysis employs neural network approximations with carefully controlled depth, width, and sparsity to bound acceleration errors across both small and large time intervals, ultimately unifying these results into a general worst case optimal bound for all time steps. © 2025, CC BY.

关键词： Ordinary differential equations

Model-based feature selection for neural networks: A mixed-integer programming approach

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Zhao, Shudian Tsay, Calvin Kronqvist, Jan Optimization and Systems Theory Department of Mathematics KTH Royal Institute of Technology Stockholm Sweden Department of Computing Imperial College London London United Kingdom

In this work, we develop a novel input feature selection framework for ReLU-based deep neural networks (DNNs), which builds upon a mixed-integer optimization approach. While the method is generally applicable to various classification tasks, we focus on finding input features for image classification for clarity of presentation. The idea is to use a trained DNN, or an ensemble of trained DNNs, to identify the salient input features. The input feature selection is formulated as a sequence of mixed-integer linear programming (MILP) problems that find sets of sparse inputs that maximize the classification confidence of each category. These "inverse" problems are regularized by the number of inputs selected for each category and by distribution constraints. Numerical results on the well-known MNIST and FashionMNIST datasets show that the proposed input feature selection allows us to drastically reduce the size of the input to ∼15% while maintaining a good classification accuracy. This allows us to design DNNs with significantly fewer connections, reducing computational effort and producing DNNs that are more robust towards adversarial attacks. Copyright © 2023, The Authors. All rights reserved.

关键词： Deep neural networks

On the Expressive Power of Modern Hopfield Networks

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Li, Xiaoyu Li, Yuanpeng Liang, Yingyu Shi, Zhenmei Song, Zhao Stevens Institute of Technology United States Beijing Normal University China The University of Hong Kong Hong Kong University of Wisconsin-Madison United States The Simons Institute for the Theory of Computing UC Berkeley United States

Modern Hopfield networks (MHNs) have emerged as powerful tools in deep learning, capable of replacing components such as pooling layers, LSTMs, and attention mechanisms. Recent advancements have enhanced their storage capacity, retrieval speed, and error rates. However, the fundamental limits of their computational expressiveness remain unexplored. Understanding the expressive power of MHNs is crucial for optimizing their integration into deep learning architectures. In this work, we establish rigorous theoretical bounds on the computational capabilities of MHNs using circuit complexity theory. Our key contribution is that we show that MHNs are DLOGTIME-uniform TC0. Hence, unless TC0 = NC1, a poly(n)-precision modern Hopfield networks with a constant number of layers and O(n) hidden dimension cannot solve NC1-hard problems such as the undirected graph connectivity problem and the tree isomorphism problem. We also extended our results to Kernelized Hopfield Networks. These results demonstrate the limitation in the expressive power of the modern Hopfield networks. Moreover, Our theoretical analysis provides insights to guide the development of new Hopfield-based architectures. © 2024, CC BY.

关键词：

Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Song, Zhao Ye, Mingquan Yin, Junze Zhang, Lichen Simons Institute for the Theory of Computing UC Berkeley United States University of Illinois Chicago United States Rice University United States Massachusetts Institute of Technology United States

Weighted low rank approximation is a fundamental problem in numerical linear algebra, and it has many applications in machine learning. Given a matrix M ∈ Rn×n, a non-negative weight matrix W ∈ R≥n×0n, a parameter k, the goal is to output two matrices X, Y ∈ Rn×k such that kW ◦ (M − XY ⌉)kF is minimized, where ◦ denotes the Hadamard product. It naturally generalizes the well-studied low rank matrix completion problem. Such a problem is known to be NP-hard and even hard to approximate assuming the Exponential Time Hypothesis [GG11, RSW16]. Meanwhile, alternating minimization is a good heuristic solution for weighted low rank approximation. In particular, [LLR16] shows that, under mild assumptions, alternating minimization does provide provable guarantees. In this work, we develop an efficient and robust framework for alternating minimization that allows the alternating updates to be computed approximately. For weighted low rank approximation, this improves the runtime of [LLR16] from kW k0k2 to kW k0k where kW k0 denotes the number of nonzero entries of the weight matrix. At the heart of our framework is a high-accuracy multiple response regression solver together with a robust analysis of alternating minimization. © 2023, CC BY-NC-SA.

关键词： Regression analysis

Exploring the Limits of KV Cache Compression in Visual Autoregressive Transformers

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Chen, Bo Li, Xiaoyu Ke, Yekun Liang, Yingyu Shi, Zhenmei Song, Zhao Middle Tennessee State University United States Stevens Institute of Technology United States The University of Hong Kong Hong Kong University of Wisconsin-Madison United States The Simons Institute for the Theory of Computing UC Berkeley United States

A fundamental challenge in Visual Autoregressive models is the substantial memory overhead required during inference to store previously generated representations. Despite various attempts to mitigate this issue through compression techniques, prior works have not explicitly formalized the problem of KV-cache compression in this context. In this work, we take the first step in formally defining the KV-cache compression problem for Visual Autoregressive transformers. We then establish a fundamental negative result, proving that any mechanism for sequential visual token generation under attention-based architectures must use at least Ω(n2d) memory, when d = Ω(log n), where n is the number of tokens generated and d is the embedding dimensionality. This result demonstrates that achieving truly sub-quadratic memory usage is impossible without additional structural constraints. Our proof is constructed via a reduction from a computational lower bound problem, leveraging randomized embedding techniques inspired by dimensionality reduction principles. Finally, we discuss how sparsity priors on visual representations can influence memory efficiency, presenting both impossibility results and potential directions for mitigating memory overhead. © 2025, CC BY.

关键词： Cache memory