论文检索

Theory · Optimization

Vincent Cohen-Addad, David Woodruff, Shenghao Xie, Samson Zhou

We study the problem of graph and hypergraph sparsification in insertion-only data streams. The input is a hypergraph $H=(V, E, w)$ with $n$ nodes, $m$ hyperedges, and rank $r$, and the goal is to compute a hypergraph $\widehat{H}$ that preserves the energy of each vector $x \in \mathbb{R}^n$ in $H$, up to a small multiplicative error. In this paper, we give a streaming algorithm that achieves a $(1+\varepsilon)$-approximation, using $\mathcal{O}\left(\frac{rn}{\varepsilon^2} \log^2 n \log r\right) \cdot$ poly $(\log \log m)$ bits of space, matching the sample complexity of the best known offline algorithm up to poly $(\log \log m)$ factors. Our approach also provides a streaming algorithm for graph sparsification that achieves a $(1+\varepsilon)$-approximation, using $\mathcal{O}\left(\frac{n}{\varepsilon^2} \log n\right)\cdot\text{poly}(\log\log n)$ bits of space, improving the current bound by $\log n$ factors. Furthermore, we give a space-efficient streaming algorithm for min-cut approximation. Along the way, we present an online algorithm for $(1+\varepsilon)$-hypergraph sparsification, which is optimal up to poly-logarithmic factors. Hence, we achieve $(1+\varepsilon)$-hypergraph sparsification in the sliding window model, with space optimal up to poly-logarithmic factors. Lastly, we give an adversarially robust algorithm for hypergraph sparsification using $\frac{n}{\varepsilon^2} \cdot $ poly $(r, \log n, \log r, \log \log m)$ bits of space.

Deep Learning · Generative Models and Autoencoders

Xiaohang Tang, Rares Dolga, Sangwoong Yoon, Ilija Bogunovic

Improving the reasoning capabilities of diffusion-based large language models (dLLMs) through reinforcement learning (RL) remains an open problem. The intractability of dLLMs likelihood function necessitates approximating the current, old, and reference policy likelihoods at each policy optimization step. This reliance introduces additional computational overhead, and can lead to large variance and estimation error in RL objective -- particularly in computing the policy ratio for importance sampling. To mitigate these issues, we introduce wd1, a novel ratio-free policy optimization approach that reformulates the RL objective as a weighted log-likelihood, requiring only a single approximation for the current parametrized policy likelihood. We formally show that our proposed method can be interpreted as energy-guided discrete diffusion training combined with negative sample unlearning, thereby confirming its theoretical soundness. In experiments on LLaDA-8B model, wd1 outperforms diffusion-based GRPO (d1) while requiring lower computational cost, achieving up to a +59\% improvement in accuracy. Furthermore, we extend wd1 to denoising-stepwise weighted policy optimization (wd1++), achieving state-of-the-art math performance of 44.2\% on MATH500 and 84.5\% on GSM8K with only 20 RL training steps.

Deep Learning · Theory

Alessio Giorlandino, Sebastian Goldt

Finding the right initialisation for neural networks is crucial to ensure smooth training and good performance. In transformers, the wrong initialisation can lead to one of two failure modes of self-attention layers: rank collapse, where all tokens collapse into similar representations, and entropy collapse, where highly concentrated attention scores lead to training instability. While previous work has studied different scaling regimes for transformers, an asymptotically exact, down-to-the constant prescription for how to initialise transformers has so far been lacking. Here, we provide an analytical theory of signal propagation through deep transformers with self-attention, layer normalisation, skip connections and MLP. Our theory yields a simple algorithm to compute trainability diagrams that identify the correct choice of initialisation hyper-parameters for a given architecture. We overcome the key challenge, an exact treatment of the self-attention layer, by establishing a formal parallel with the Random Energy Model from statistical physics. We also analyse gradients in the backward path and determine the regime where gradients vanish at initialisation. We demonstrate the versatility of our framework through three case studies. Our theoretical framework gives a unified perspective on the two failure modes of self-attention and gives quantitative predictions on the scale of both weights and residual connections that guarantee smooth training.

Computer Vision · Image and Video Generation

Weiqiao Han, Chenlin Meng, Christopher Manning, Stefano Ermon

We present DistillKac, a fast image generator that uses the damped wave equation and its stochastic Kac representation to move probability mass at finite speed. In contrast to diffusion models whose reverse time velocities can become stiff and implicitly allow unbounded propagation speed, Kac dynamics enforce finite speed transport and yield globally bounded kinetic energy. Building on this structure, we introduce classifier free guidance in velocity space that preserves square integrability under mild conditions. We then propose endpoint only distillation that trains a student to match a frozen teacher over long intervals. We prove a stability result that promotes supervision at the endpoints to closeness along the entire path. Experiments demonstrate DistillKac delivers high quality samples with very few function evaluations while retaining the numerical stability benefits of finite speed probability flows.

Wuyang Cong, Junqi Shi, Ming Lu, Xu Zhang, Zhan Ma

Hierarchical coding offers distinct advantages for learned image compression by capturing multi-scale representations to support scale-wise modeling and enable flexible quality scalability, making it a promising alternative to single-scale models. However, its practical performance remains limited. Through spectral analysis of training dynamics, we reveal that existing hierarchical image coding approaches suffer from cross-scale energy dispersion and spectral aliasing, resulting in optimization inefficiency and performance bottlenecks. To address this, we propose explicit spectral regularization schemes for hierarchical image coding, consisting of (i) intra-scale frequency regularization, which encourages a smooth low‑to‑high frequency buildup as scales increase, and (ii) inter-scale similarity regularization, which suppresses spectral aliasing across scales. Both regularizers are applied only during training and impose no overhead at inference. Extensive experiments demonstrate that our method accelerates the training of the vanilla model by 2.3$\times$, delivers an average 20.65\% rate–distortion gain over the latest VTM-22.0 on public datasets, and outperforms existing single-scale approaches, thereby setting a new state of the art in learned image compression.

General Machine Learning · Transfer, Multitask and Meta-learning

Qingyuan Liu, Jia-Chen Gu, Yunzhi Yao, Hong Wang, Nanyun (Violet) Peng

Large language models (LLMs) require constant updates to remain aligned with evolving real-world knowledge. Model editing offers a lightweight alternative to retraining, but sequential editing that updates the LLM knowledge through multiple successive edits often destabilizes representations and induces catastrophic forgetting. In this work, we seek to better understand and mitigate performance degradation caused by sequential editing. We hypothesize that hyperspherical uniformity, a property that maintains uniform distribution of neuron weights on a hypersphere, helps the model remain stable, retain prior knowledge, while still accommodate new updates. We use Hyperspherical Energy (HE) to quantify neuron uniformity during editing, and examine its correlation with editing performance. Empirical studies across widely used editing methods reveals a strong correlation between HE dynamics and editing performance, with editing failures consistently coinciding with uncontrolled HE fluctuations. We further theoretically prove that HE dynamics impose a lower bound on the degradation of pretrained knowledge, highlighting why HE stability is crucial for knowledge retention. Motivated by these insights, we propose SPHERE (Sparse Projection for Hyperspherical Energy-Regularized Editing), an HE-driven regularization strategy that stabilizes neuron weight distributions, ultimately preserving prior knowledge while enabling reliable sequential updates. Specifically, SPHERE identifies a sparse space complementary to the principal hyperspherical directions of the pretrained weight matrices and projects new knowledge onto it, attenuating perturbations on the principal directions. Extensive experiments on LLaMA3 (8B) and Qwen2.5 (7B) show that SPHERE outperforms the best baseline in editing capability by an average of 16.41%, while most faithfully preserving general model performance, thereby offering a principled path toward reliable large-scale knowledge editing.

Applications · Everything Else

JUNYONG AHN, Hyeongrok Han, Bong Gyun Kang, Jisoo Mok, Byunghan Lee, Sungroh Yoon

Developing a mobile system capable of generating responses based on stored user data is a crucial challenge. Since user data is stored in the form of Knowledge Graphs, the field of knowledge graph question answering (KGQA) presents a promising avenue towards addressing this problem. However, existing KGQA systems face two critical limitations that preclude their on-device deployment: resource constraints and the inability to handle data accumulation. Therefore, we propose MobileKGQA, the first on-device KGQA system capable of adapting to evolving databases with minimal resource demands. MobileKGQA significantly reduces computational overhead through embedding hashing. Moreover, it successfully adapts to evolving databases under resource constraints through a novel annotation generation method. Its mobile applicability is validated on the NVIDIA Jetson Orin Nano edge-device platform, achieving 20.3% higher performance while using only 30.4% of the energy consumed by the SOTA (state-of-the-art). On standard KGQA benchmarks, using just 7.2% of the computation and 9% of the parameters, MobileKGQA demonstrates performance that is empirically indistinguishable from the SOTA and outperforms baselines under distribution shift scenarios.

Deep Learning · Graph Neural Networks

Luca Miglior, Matteo Tolloso, Alessio Gravina, Davide Bacciu

Effectively capturing long-range interactions remains a fundamental yet unresolved challenge in graph neural network (GNN) research, critical for applications across diverse fields of science. To systematically address this, we introduce ECHO (Evaluating Communication over long HOps), a novel benchmark specifically designed to rigorously assess the capabilities of GNNs in handling very long-range graph propagation. ECHO includes three synthetic graph tasks, namely single-source shortest paths, node eccentricity, and graph diameter, each constructed over diverse and structurally challenging topologies intentionally designed to introduce significant information bottlenecks. ECHO also includes two real-world datasets, ECHO-Charge and ECHO-Energy, which define chemically grounded benchmarks for predicting atomic partial charges and molecular total energies, respectively, with reference computations obtained at the density functional theory (DFT) level. Both tasks inherently depend on capturing complex long-range molecular interactions. Our extensive benchmarking of popular GNN architectures reveals clear performance gaps, emphasizing the difficulty of true long-range propagation and highlighting design choices capable of overcoming inherent limitations. ECHO thereby sets a new standard for evaluating long-range information propagation, also providing a compelling example for its need in AI for science.

Deep Learning · Generative Models and Autoencoders

Mingyu Kim, Young-Heon Kim, Mijung Park

Safety mechanisms for diffusion and flow models have recently been developed along two distinct paths. In robot planning, control barrier functions are employed to guide generative trajectories away from obstacles at every denoising step by explicitly imposing geometric constraints. In parallel, recent data-driven, negative guidance approaches have been shown to suppress harmful content and promote diversity in generated samples. However, they rely on heuristics without clearly stating when safety guidance is actually necessary. In this paper, we first introduce a unified probabilistic framework using a Maximum Mean Discrepancy (MMD) potential for image generation tasks that recasts both Shielded Diffusion and Safe Denoiser as instances of our energy-based negative guidance against unsafe data samples. Furthermore, we leverage control-barrier functions analysis to justify the existence of a critical time window in which negative guidance must be strong; outside of this window, the guidance should decay to zero to ensure safe and high-quality generation. We evaluate our unified framework on several realistic safe generation scenarios, confirming that negative guidance should be applied in the early stages of the denoising process for successful safe generation.

Theory · Probabilistic Methods

Dror Freirich, Nir Weinberger

When compressing continuous data, some loss of information is inevitable, and this incurred a distortion upon reconstruction. The Rate–Distortion (RD) function characterizes the minimum achievable rate for a code whose decoding permits a specified amount of distortion. We exploit the connection between rate-distortion theory and entropic optimal transport to propose a novel stochastic-control formulation for the former, and use a classic result dating back to Schrodinger to show that the tradeoff between rate and mean squared error distortion is equivalent to a tradeoff between control energy and the differential entropy of the terminal state, whose probability law defines the reconstruction distribution. For a special class of sources, we show that the optimal control law and the corresponding trajectory in the space of probability measures are obtained by solving a backward heat equation. In more general settings, our approach yields a numerical method that estimates the RD function using diffusion processes with a constant diffusion coefficient. We demonstrate the effectiveness of our method through several examples.

Theory · Probabilistic Methods

Navid Akhavan Attar, Hesam Asadollahzadeh, Ling Luo, Uwe Aickelin

The merit of Conformal Prediction (CP), as a distribution-free framework for uncertainty quantification, depends on generating prediction sets that are efficient, reflected in small average set sizes, while adaptive, meaning they signal uncertainty by varying in size according to input difficulty. A central limitation for deep conformal classifiers is that the nonconformity scores are derived from softmax outputs, which can be unreliable indicators of how certain the model truly is about a given input, sometimes leading to overconfident misclassifications or undue hesitation. In this work, we argue that this unreliability can be inherited by the prediction sets generated by CP, limiting their capacity for adaptiveness. We propose a new approach that leverages information from the pre-softmax logit space, using the Helmholtz Free Energy as a measure of model uncertainty and sample difficulty. By reweighting nonconformity scores with a monotonic transformation of the energy score of each sample, we improve their sensitivity to input difficulty. Our experiments with four state-of-the-art score functions on multiple datasets and deep architectures show that this energy-based enhancement improves the adaptiveness of the prediction sets, leading to a notable increase in both efficiency and adaptiveness compared to baseline nonconformity scores, without introducing any post-hoc complexity.

Wonjong Jang, Yucheol Jung, Gyeongmin Lee, Seungyong Lee 0001

Self-intersection repair in static 3D surface meshes presents unique challenges due to the absence of temporal motion and penetration depth information—two critical elements typically leveraged in physics-based approaches. We introduce a novel framework that transforms local contact handling into a global repair strategy through a combination of local signed tangent-point energies and their gradient diffusion. At the heart of our method is a key insight: rather than computing expensive global repulsive potentials, we can effectively approximate long-range interactions by diffusing energy gradients from local contacts throughout the mesh surface. In turn, resolving complex self-intersections reduces to simply propagating local repulsive energies through standard diffusion mechanics and iteratively solving tractable local optimizations. We further accelerate convergence through our momentum-based optimizer, which adaptively regulates momentum based on gradient statistics to prevent overshooting while maintaining rapid intersection repair. The resulting algorithm handles a variety of challenging scenarios, from shallow contacts to deep penetrations, while providing computational efficiency suitable for interactive applications.

Yue Chang, Otman Benchekroun, Maurizio M. Chiaramonte, Peter Yichen Chen, Eitan Grinspun

Eigenanalysis of differential operators, such as the Laplace operator or elastic energy Hessian, is typically restricted to a single shape and its discretization, limiting reduced order modeling (ROM). We introduce the first eigenanalysis method for continuously parameterized shape families. Given a parametric shape, our method constructs spatial neural fields that represent eigen-functions across the entire shape space. It is agnostic to the specific shape representation, requiring only an inside/outside indicator function that depends on shape parameters. Eigenfunctions are computed by minimizing a variational principle over nested spaces with orthogonality constraints. Since eigenvalues may swap dominance at points of multiplicity, we jointly train multiple eigenfunctions while dynamically reordering them based on their eigenvalues at each step. Through causal gradient filtering, this reordering is reflected in backpropagation. Our method enables applications to operate over shape space, providing a single ROM that encapsulates vibration modes for all shapes, including previously unseen ones. Since our eigenanalysis is differentiable with respect to shape parameters, it facilitates eigenfunction-aware shape optimization. We evaluate our approach on shape optimization for sound synthesis and locomotion, as well as reduced-order modeling for elastodynamic simulation.

Duowen Chen 0003, Zhiqi Li 0004, Taiyuan Zhang, Jinjin He, Junwei Zhou 0001, Bart G. van Bloemen Waanders, Bo Zhu 0002

This paper presents a unified compressible flow map framework designed to accommodate diverse compressible flow systems, including high-Mach-number flows (e.g., shock waves and supersonic aircraft), weakly compressible systems (e.g., smoke plumes and ink diffusion), and incompressible systems evolving through compressible acoustic quantities (e.g., free-surface shallow water). At the core of our approach is a theoretical foundation for compressible flow maps based on Lagrangian path integrals, a novel advection scheme for the conservative transport of density and energy, and a unified numerical framework for solving compressible flows with varying pressure treatments. We validate our method across three representative compressible flow systems, characterized by varying fluid morphologies, governing equations, and compressibility levels, demonstrating its ability to preserve and evolve spatiotemporal features such as vortical structures and wave interactions governed by different flow physics. Our results highlight a wide range of novel phenomena, from ink torus breakup to delta wing tail vortices and vortex shedding on free surfaces, significantly expanding the range of fluid systems that flow-map methods can handle.

Huanyu Chen, Jiahao Wen, Jernej Barbic

We give a method to simulate large deformations of 3D elastic rods under arbitrary nonlinear isotropic 3D solid materials. Rod elastic energies in existing graphics literature are derived from volumetric models under the small-strain linearization assumptions. While the resulting equations can and are commonly applied to large deformations, the material modeling has been limited to a single material, namely linear Hooke law. Starting from any 3D solid nonlinear isotropic elastic energy density function ψ, we derive our rod elastic energy by subjecting the 3D solid volumetric material to the limit process whereby rod thickness is decreased to zero. This enables us to explain rod stretching, bending and twisting in a unified model. Care must be taken to adequately model cross-sectional in-plane and out-of-plane deformations. Our key insight is to compute the three cross-sectional deformation modes corresponding to bending (in the two directions) and twisting, using linear theory. Then, given any ψ, we use these modes to derive an analytical formula for a 5D "macroscopic" large-deformation rod elastic energy function of the local longitudinal stretch, radial scaling, the two bending curvatures and torsion. Our model matches linear theory for small deformations, including cross-sectional shrinkage due to Poisson's effect, and produces correct bending and torsional constants. Our experiments demonstrate that our energy closely matches volumetric FEM even under large stretches and curvatures, whereas commonly used methods in graphics deviate from it. We also compare to closely related work from mechanics literature; we give an explicit expansion of all energy terms in terms of the rod cross-section diameter, allowing independent adjustment of stretching, bending and twisting. Finally, we observe an inherent limitation in the ability of rod models to control nonlinear bendability and twistability. We propose to "relax" rod physics to more easily control nonlinear bending and twisting in computer graphics applications.

Ugo Paavo Finnendahl, Markus Worchel, Tobias Jüterbock, Daniel Wujecki, Fabian Brinkmann, Stefan Weinzierl, Marc Alexa

Differentiable rendering has become a key ingredient in solving challenging inverse problems in computer graphics and vision. Existing systems can simulate and differentiate the spatial propagation of light. We exploit the duality of light transport simulations and geometric acoustics to apply differential rendering techniques to established acoustic simulation methods. The resulting system is capable of simulating sound according to the geometrical acoustics model and computing derivatives of the output energy spectrograms with respect to arbitrary parameters of the scene, including materials, emitters, microphones, and scene geometry. Contrary to current differentiable transient rendering, we can handle arbitrary simulation depths and achieve constant memory and linear execution times by presenting a temporal extension of Path Replay Backpropagation [Vicini et al. 2021]. We verify our model against established simulation software, and demonstrate the capabilities of optimization with gradients at examples of inverse acoustics and optimizing room parameters. This opens up a new field of research for acoustic optimization that could be as impactful for the acoustic community as differentiable rendering was for the graphics community.

Élie Michel, Alec Jacobson, Siddhartha Chaudhuri, Jean-Marc Thiery

We present closed-form expressions for Green and biharmonic coordinates with respect to polynomial curved 2D cages, enabling reliable cage-based image deformation both to and from a curved cage. We further provide closed-form expressions for first- and second-order derivatives of these coordinates with respect to the encoded position. This enables the use of variational solvers for interacting with the 2D shape at arbitrary points while keeping the fast decoding strength of cage-based deformation, which we illustrate for a variety of elastic deformation energies.

Yucheol Jung, Hyomin Kim, Hyejeong Yoon, Yoonha Hwang, Seungyong Lee 0001

Non-rigid registration of 3D shape collections using a template mesh is essential for constructing 3D datasets. Traditional non-rigid Iterative Closest Point (ICP) methods rely on manually selected template meshes, which can result in inconsistent registrations when applied to diverse shape collections. This inconsistency arises particularly when the template lacks common shape features with the input instances or when landmark annotations are sparse. To overcome this limitation, we propose a novel ICP framework that jointly optimizes a shared template shape and its instance-wise deformations. Our joint optimization framework assigns distinct roles to the shared template and instance-wise deformations: the template captures common shape features, while instance-wise deformations handle residual registration errors. We use stronger smoothness regularization on the instance-wise deformations in early iterations to prioritize the accumulation of common details on the template. Additionally, a distortion alignment energy minimizes interinstance map distortions, promoting consistent instance-wise deformations. On challenging 3D datasets with large shape variations, our method achieves state-of-the-art fitting accuracy and consistent results in shape averaging and deformation transfer. By removing the need for a carefully selected preset template, our method extends the capability of extrinsic non-rigid registration frameworks, offering a more robust and flexible solution for challenging registration scenarios.

Lei Lan, Zixuan Lu, Chun Yuan 0001, Weiwei Xu 0003, Hao Su 0001, Huamin Wang 0001, Chenfanfu Jiang, Yin Yang 0002

In parallel simulation, convergence and parallelism are often seen as inherently conflicting objectives. Improved parallelism typically entails lighter local computation and weaker coupling, which unavoidably slow the global convergence. This paper presents a novel GPU algorithm that achieves convergence rates comparable to fullspace Newton's method while maintaining good parallelizability just like the Jacobi method. Our approach is built on a key insight into the phenomenon of overshoot. Overshoot occurs when a local solver aggressively minimizes its local energy without accounting for the global context, resulting in a local update that undermines global convergence. To address this, we derive a theoretically second-order optimal solution to mitigate overshoot. Furthermore, we adapt this solution into a pre-computable form. Leveraging Cubature sampling, our runtime cost is only marginally higher than the Jacobi method, yet our algorithm converges nearly quadratically as Newton's method. We also introduce a novel full-coordinate formulation for more efficient pre-computation. Our method integrates seamlessly with the incremental potential contact method and achieves second-order convergence for both stiff and soft materials. Experimental results demonstrate that our approach delivers high-quality simulations and outperforms state-of-the-art GPU methods with 50× to 100× better convergence.

Zhenyu Wang, Min Lu 0002

Collage and packing techniques are widely used to organize geometric shapes into cohesive visual representations, facilitating the representation of visual features holistically, as seen in image collages and word clouds. Traditional methods often rely on object-space optimization, requiring intricate geometric descriptors and energy functions to handle complex shapes. In this paper, we introduce a versatile image-space collage technique. Leveraging a differentiable renderer, our method effectively optimizes the object layout with image-space losses, bringing the benefit of fixed complexity and easy accommodation of various shapes. Applying a hierarchical resolution strategy in image space, our method efficiently optimizes the collage with fast convergence, large coarse steps first and then small precise steps. The diverse visual expressiveness of our approach is demonstrated through various examples. Experimental results show that our method achieves an order of magnitude speedup performance compared to state-of-the-art techniques.