Search

The recent rise of large language models (LLMs) has resulted in increased efforts towards running LLMs at reduced precision. Running LLMs at lower precision supports resource constraints and furthers their democratization, enabling users to run billion-parameter LLMs on their personal devices. To supplement this ongoing effort, we propose INT-FP-QSim: an open-source simulator that enables flexible evaluation of LLMs and vision transformers at various numerical precisions and formats. INT-FP-QSim leverages existing open-source repositories such as TensorRT, QPytorch and AIMET for a combined simulator that supports various floating point and integer formats. With the help of our simulator, we survey the impact of different numerical formats on the performance of LLMs and vision transformers at 4-bit weights and 4-bit or 8-bit activations. We also compare recently proposed methods like Adaptive Block Floating Point, SmoothQuant, GPTQ and RPTQ on the model performances. We hope INT-FP-QSim will enable researchers to flexibly simulate models at various precisions to support further research in quantization of LLMs and vision transformers., Comment: This report is supplementary material to the open-source code available at: https://github.com/lightmatter-ai/INT-FP-QSim

We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph $G= (A \cup P, E)$ with weights on the edges in $E$, and with lower and upper quotas on the vertices in $P$. We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in $A$ are incident to at most one matching edge, while vertices in $P$ are either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (WMLQ), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of WMLQ from the viewpoints of classic polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between NP-hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quota $u_{max}$ as basis, and we prove that this dependence is necessary unless FPT = W[1]. The approximability of WMLQ is also discussed: we present an approximation algorithm for the general case with performance guarantee $u_{\max}+1$, which is asymptotically best possible unless P = NP. Finally, we elaborate on how most of our positive results carry over to matchings in arbitrary graphs with lower quotas., Comment: preliminary version has appeared at ISAAC 2015

Flows over time are used to model many real-world logistic and routing problems. The networks underlying such problems -- streets, tracks, etc. -- are inherently undirected and directions are only imposed on them to reduce the danger of colliding vehicles and similar problems. Thus the question arises, what influence the orientation of the network has on the network flow over time problem that is being solved on the oriented network. In the literature, this is also referred to as the contraflow or lane reversal problem. We introduce and analyze the price of orientation: How much flow is lost in any orientation of the network if the time horizon remains fixed? We prove that there is always an orientation where we can still send $\frac{1}{3}$ of the flow and this bound is tight. For the special case of networks with a single source or sink, this fraction is $\frac12$ which is again tight. We present more results of similar flavor and also show non-approximability results for finding the best orientation for single and multicommodity maximum flows over time.

Padberg introduced a geometric notion of ranks for (mixed) integer rational polyhedrons and conjectured that the geometric rank of the matching polytope is one. In this work, we prove that this conjecture is true.