Search

Sparse attention can effectively mitigate the significant memory and throughput demands of Large Language Models (LLMs) in long contexts. Existing methods typically employ a uniform sparse attention mask, applying the same sparse pattern across different attention heads and input lengths. However, this uniform approach fails to capture the diverse attention patterns inherent in LLMs, ignoring their distinct accuracy-latency trade-offs. To address this challenge, we propose the Mixture of Attention (MoA), which automatically tailors distinct sparse attention configurations to different heads and layers. MoA constructs and navigates a search space of various attention patterns and their scaling rules relative to input sequence lengths. It profiles the model, evaluates potential configurations, and pinpoints the optimal sparse attention compression plan. MoA adapts to varying input sizes, revealing that some attention heads expand their focus to accommodate longer sequences, while other heads consistently concentrate on fixed-length local contexts. Experiments show that MoA increases the effective context length by $3.9\times$ with the same average attention span, boosting retrieval accuracy by $1.5-7.1\times$ over the uniform-attention baseline across Vicuna-{7B,13B}, and Llama3-{8B,70B} models. Moreover, MoA narrows the capability gaps between sparse and dense models, reducing the maximum relative performance drop from $9\%-36\%$ to within $5\%$ across two long-context understanding benchmarks. MoA achieves a $1.2-1.4\times$ GPU memory reduction, boosting decode throughput by $6.6-8.2\times$ and $1.7-1.9\times$ compared to FlashAttention2 and vLLM, with minimal impact on performance. Our code is available at \url{https://github.com/thu-nics/MoA}.

We study the limiting extremal and cluster point processes of branching Brownian motion. The former records the heights of all extreme values of the process, while the latter records the relative heights of extreme values in a genealogical neighborhood of order unity around a local maximum thereof. For the extremal point process, we show that the mass of upper level sets $[-v, \infty)$ grows as $C_\star Z v e^{\sqrt{2} v}(1+o(1))$ as $v \to \infty$, almost surely, where $Z$ is the limit of the associated derivative martingale and $C_\star \in (0, \infty)$ is a universal constant. For the cluster point process, we show that the logarithm of the mass of $[-v, \infty)$ grow as $\sqrt{2}v$ minus random fluctuations of order $v^{2/3}$, which are governed by an explicit law in the limit. The first result improves upon the works of Cortines et al. (arXiv:1703.06529) and Mytnik et al. (arXiv:2009.02042) in which asymptotics are shown in probability, while the second makes rigorous the derivation in the physics literature by Mueller et al. (arXiv:1910.06382) and Le et al. (arXiv:2207.07672) and resolves a conjecture thereof., Comment: 37 pages

We propose a discrete approach to approximate the solution for the prescribed Gaussian curvature problem in 2-dimensional manifolds, based on the notion of discrete conformality. Our approach gives a convenient way to numerically compute the solution by minimizing a convex functional.

Given a triangulated surface, a polyhedral metric could be constructed by gluing Euclidean triangles edge-to-edge. We carefully describe the construction and prove that such a polyhedral metric is the only intrinsic metric on the glued surface that preserves the lengths of the curves on the Euclidean triangles. We also discuss the edge length coordinates of the Teichm\"uller space of the polyhedral metrics on a marked surface.

We prove that for a convex polytope decomposition of a domain in $\mathbb R^n$, an integral curve of a piecewise analytic vector field is chopped by the decomposition into finitely many pieces. As a consequence, we prove the finiteness of the number of the edge flips in a discrete Yamabe flow.

We proved a rigidity result for Delaunay triangulations of the plane under Luo's discrete conformal change, extending previous results on hexagonal triangulations. Our result is a discrete analogue of the conformal rigidity of the plane. We followed Zhengxu He's analytical approach in his work on the rigidity of disk patterns, and developed a discrete Schwarz lemma and a discrete Liouville theorem. The main tools include conformal modulus, discrete extremal length, and maximum principles in discrete conformal geometry., Comment: Final version, to appear in Advances in Mathematics

Let $S$ be the 2-sphere and $V \subset S$ be a finite set of at least three points. We show that for each function $\kappa: V \rightarrow (0, 2\pi)$ satisfying elementary necessary conditions, in each discrete conformal class of spherical cone-metrics there exists a unique metric realizing $\kappa$ as its discrete curvature. This can be seen as a discrete version of a result of Luo and Tian.

Many real-world networks exhibit the so-called small-world phenomenon: their typical distances are much smaller than their sizes. One mathematical model for this phenomenon is a long-range percolation graph on a $d$-dimensional box $\{0, 1, \cdots, N\}^d$, in which edges are independently added between far-away sites with probability falling off as a power of the Euclidean distance. A natural question is how the resulting diameter of the box of size $N$, measured in graph-theoretical distance, scales with $N$. This question has been intensely studied in the past and the answer depends on the exponent $s$ in the connection probabilities. In this work we focus on the critical regime $s = d$ studied earlier in a work by Coppersmith, Gamarnik, and Sviridenko and improve the bounds obtained there to a sharp leading-order asymptotic, by exploiting the high degree of concentration due to the large amount of independence in the model., Comment: 10 pages, improves the bounds obtained in arXiv:math/0112029v1 to a sharp leading order asymptotic

We show that a uniformly acute triangulation of the plane is rigid under Luo's discrete conformal change, extending previous results on hexagonal triangulations. Our result is a discrete analogue of the conformal rigidity of the plane. We followed He's analytical approach in his work on the rigidity of disk patterns. The main tools include maximum principles, a discrete Liouville theorem, smooth and discrete extremal lengths on networks. The key step is relating the Euclidean discrete conformality to the hyperbolic discrete conformality, to obtain an L-infinity bound on the discrete conformal factor., Comment: 17 pages, 1 figure

Protein complexes are macromolecules essential to the functioning and well-being of all living organisms. As the structure of a protein complex, in particular its region of interaction between multiple protein subunits (i.e., chains), has a notable influence on the biological function of the complex, computational methods that can quickly and effectively be used to refine and assess the quality of a protein complex's 3D structure can directly be used within a drug discovery pipeline to accelerate the development of new therapeutics and improve the efficacy of future vaccines. In this work, we introduce the Equivariant Graph Refiner (EGR), a novel E(3)-equivariant graph neural network (GNN) for multi-task structure refinement and assessment of protein complexes. Our experiments on new, diverse protein complex datasets, all of which we make publicly available in this work, demonstrate the state-of-the-art effectiveness of EGR for atomistic refinement and assessment of protein complexes and outline directions for future work in the field. In doing so, we establish a baseline for future studies in macromolecular refinement and structure analysis., Comment: 18 pages, 3 figures, and 8 tables. Under review

It has been shown that spaces of geodesic triangulations of surfaces with negative curvature are contractible. Here we propose an approach aiming to prove that the spaces of geodesic triangulations of a surface with negative curvature are homeomorphic to Euclidean spaces $\mathbb{R}^n$., Comment: 11 pages, 3 figures

In this paper, we propose a meshless method of computing eigenvalues and eigenfunctions of a given surface embedded in $\mathbb R^3$. We use point cloud data as input and generate the lattice approximation for some neighborhood of the surface. We compute the eigenvalues and eigenvectors of the cubic lattice graph as an approximation of the eigenvalues and eigenfunctions of the Laplace-Beltrami operator on the surface. We perform extensive numerical experiments on surfaces with various topology and compare our computed eigenvalues from point cloud surface with exact solutions and standard finite element methods using triangle mesh.

In this paper, we determine the topology of the spaces of convex polyhedra inscribed in the unit $2$-sphere and the spaces of strictly Delaunay geodesic triangulations of the unit $2$-sphere. These spaces can be regarded as discretized groups of diffeomorphisms of the unit $2$-sphere. Hence, it is natural to conjecture that these spaces have the same homotopy types as those of their smooth counterparts. The main result of this paper confirms this conjecture for the unit $2$-sphere. It follows from an observation on the variational principles on triangulated surfaces developed by I. Rivin. On the contrary, the similar conjecture does not hold in the cases of flat tori and convex polygons. We will construct simple examples of flat tori and convex polygons such that the corresponding spaces of Delaunay geodesic triangulations are not connected., Comment: 10 pages, 5 figures

A knowledge graph (KG) is a data structure which represents entities and relations as the vertices and edges of a directed graph with edge types. KGs are an important primitive in modern machine learning and artificial intelligence. Embedding-based models, such as the seminal TransE [Bordes et al., 2013] and the recent PairRE [Chao et al., 2020] are among the most popular and successful approaches for representing KGs and inferring missing edges (link completion). Their relative success is often credited in the literature to their ability to learn logical rules between the relations. In this work, we investigate whether learning rules between relations is indeed what drives the performance of embedding-based methods. We define motif learning and two alternative mechanisms, network learning (based only on the connectivity of the KG, ignoring the relation types), and unstructured statistical learning (ignoring the connectivity of the graph). Using experiments on synthetic KGs, we show that KG models can learn motifs and how this ability is degraded by non-motif (noise) edges. We propose tests to distinguish the contributions of the three mechanisms to performance, and apply them to popular KG benchmarks. We also discuss an issue with the standard performance testing protocol and suggest an improvement. To appear in the proceedings of Complex Networks 2021., Comment: 16 pages

The notion of discrete conformality proposed by Luo and Bobenko-Pinkall-Springborn on triangle meshes has rich mathematical theories and wide applications. Gu et al. proved that the discrete uniformizations approximate the continuous uniformization for closed surfaces of genus $\geq 1$, given that the approximating triangle meshes are reasonably good. In this paper, we generalize this result to the remaining case of genus-zero surfaces, by reducing it to planar cases via stereographic projections., Comment: 19 pages, 4 figures. Comments are welcomed!

Using the fractional discrete Laplace operator for triangle meshes, we introduce a fractional combinatorial Calabi flow for discrete conformal structures on surfaces, which unifies and generalizes Chow-Luo's combinatorial Ricci flow for Thurston's circle packings, Luo's combinatorial Yamabe flow for vertex scaling and the combinatorial Calabi flow for discrete conformal structures on surfaces. For Thurston's Euclidean and hyperbolic circle packings on triangulated surfaces, we prove the longtime existence and global convergence of the fractional combinatorial Calabi flow. For vertex scalings on polyhedral surfaces, we do surgery on the fractional combinatorial Calabi flow by edge flipping under the Delaunay condition to handle the potential singularities along the flow. Using the discrete conformal theory established by Gu et al., we prove the longtime existence and global convergence of the fractional combinatorial Calabi flow with surgery., Comment: 30 pages, 0 figures

We prove that the deformation space of geodesic triangulations of a flat torus is homotopy equivalent to a torus. This solves an open problem proposed by Connelly et al. in 1983, in the case of flat tori. A key tool of the proof is a generalization of Tutte's embedding theorem for flat tori. When this paper is under preparation, Erickson and Lin proved a similar result, which works for all convex drawings., Comment: 15 pages, 2 figures

We proved the contractibility of the deformation space of the geodesic triangulations on a closed surface of negative curvature. This solves an open problem proposed by Connelly et al. in 1983, in the case of hyperbolic surfaces. The main part of the proof is a generalization of Tutte's embedding theorem for closed surfaces of negative curvature., Comment: 18 pages, 5 figures. Comments are welcomed!

The paper proves a result on the convergence of discrete conformal maps to the Riemann mappings for Jordan domains. It is a counterpart of Rodin-Sullivan's theorem on convergence of circle packing mappings to the Riemann mapping in the new setting of discrete conformality. The proof follows the same strategy that Rodin-Sullivan used by establishing a rigidity result for regular hexagonal triangulations of the plane and estimating the quasiconformal constants associated to the discrete conformal maps., Comment: 37 pages, 11 figures

We propose a novel meshless method to compute harmonic maps and conformal maps for surfaces embedded in the Euclidean 3-space, using point cloud data only. Given a surface, or a point cloud approximation, we simply use the standard cubic lattice to approximate its $\epsilon$-neighborhood. Then the harmonic map of the surface can be approximated by discrete harmonic maps on lattices. The conformal map, or the surface uniformization, is achieved by minimizing the Dirichlet energy of the harmonic map while deforming the target surface of constant curvature. We propose algorithms and numerical examples for closed surfaces and topological disks., Comment: 26 pages, 9 figures

The notions of discrete conformality on triangle meshes have rich mathematical theories and wide applications. The related notions of discrete uniformizations on triangle meshes, suggest efficient methods for computing the uniformizations of surfaces. This paper proves that the discrete uniformizations approximate the continuous uniformization for closed surfaces of genus $\geq1$, when the approximating triangle meshes are reasonably good. To the best of the authors' knowledge, this is the first convergence result on computing uniformizations for surfaces of genus $>1$., Comment: 34 pages, 3 figures

We prove that the Koebe circle domain conjecture is equivalent to the Weyl type problem that every complete hyperbolic surface of genus zero is isometric to the boundary of the hyperbolic convex hull of the complement of a circle domain. It provides a new way to approach the Koebe's conjecture using convex geometry. Combining our result with the work of He-Schramm on the Koebe conjecture, one establishes that every simply connected non-compact polyhedral surface is discrete conformal to the complex plane or the open unit disk. The main tool we use is Schramm's transboundary extremal lengths.