Machine Learning
Rare Event Analysis of Large Language Models
Jake McAllister Dorman, Edward Gillman, Dominic C. Rose et al. (+2 more)
Being probabilistic models, during inference large
language models (LLMs) display rare events: behaviour that is far from typical but highly significant. By definition all rare events are hard to see, but the enormous scale of LLM usage means that events completely unobserved during development are likely to become prominent in deployment. Here we present an end-to-end framework for the systematic analysis of rare events in LLMs. We provide a practical implementation spanning theory, efficient generation strategies, probability estimation and error analysis, which we illustrate with concrete examples. We outline extensions and applications to other models and contexts, highlighting the generality of the concepts and techniques presented here.
Read the full abstract ▾
All authors Jake McAllister Dorman, Edward Gillman, Dominic C. Rose, Jamie F. Mair, Juan P. Garrahan
Machine Learning
Displacement-Resistant Extensions of DPO with Nonconvex $f$-Divergences
Idan Pipano, Shoham Sabach, Kavosh Asadi et al. (+1 more)
DPO and related
algorithms align
language models by directly optimizing the RLHF objective: find a policy that maximizes the Bradley-Terry reward while staying close to a reference policy through a KL divergence penalty. Previous work showed that this approach could be further generalized: the original problem remains tractable even if the KL divergence is replaced by a family of $f$-divergence with a convex generating function $f$. Our first contribution is to show that convexity of $f$ is not essential. Instead, we identify a more general condition, referred to as DPO-inducing, that precisely characterizes when the RLHF problem remains tractable. Our next contribution is to establish a second condition on $f$ that is necessary to prevent probability displacement, a known empirical phenomenon in which the probabilities of the winner and the loser responses approach zero. We refer to any $f$ that satisfies this condition as displacement-resistant. We finally focus on a specific DPO-inducing and displacement-resistant $f$, leading to our novel SquaredPO loss. Compared to DPO, this new loss offers stronger theoretical guarantees while performing competitively in practice.
Read the full abstract ▾
All authors Idan Pipano, Shoham Sabach, Kavosh Asadi, Mohammad Ghavamzadeh
Machine Learning
Weisfeiler and Lehman Go Categorical
Seongjin Choi, Gahee Kim and Se-Young Yun
While lifting map has significantly enhanced the expressivity of graph neural networks, extending this paradigm to hypergraphs remains fragmented. To address this, we introduce the categorical Weisfeiler-Lehman framework, which formalizes lifting as a functorial mapping from an arbitrary data category to the unifying category of graded posets. When applied to hypergraphs, this perspective allows us to systematically derive Hypergraph Isomorphism Networks, a family of neural architectures where the message passing
topology is strictly determined by the choice of functor. We introduce two distinct functors from the category of hypergraphs: an incidence functor and a symmetric simplicial complex functor. While the incidence architecture structurally mirrors standard bipartite schemes, our functorial derivation enforces a richer information flow over the resulting poset, capturing complex intersection geometries often missed by existing methods. We theoretically characterize the expressivity of these models, proving that both the incidence-based and symmetric simplicial approaches subsume the expressive power of the standard Hypergraph Weisfeiler-Lehman test. Extensive experiments on real-world
benchmarks validate these theoretical findings.
Read the full abstract ▾
Machine Learning · Cross-listed from cs.CV
Revisiting Emotions Representation for Recognition in the Wild
Joao Baptista Cardia Neto, Claudio Ferrari and Stefano Berretti
Facial
emotion recognition has been typically cast as a single-label classification problem of one out of six prototypical
emotions. However, that is an oversimplification that is unsuitable for representing the multifaceted spectrum of spontaneous emotional states, which are most often the result of a combination of multiple
emotions contributing at different intensities. Building on this, a promising direction that was explored recently is to cast
emotion recognition as a distribution learning problem. Still, such approaches are limited in that research
datasets are typically annotated with a single
emotion class. In this paper, we contribute a novel approach to describe complex emotional states as probability distributions over a set of
emotion classes. To do so, we propose a solution to automatically re-label existing
datasets by exploiting the result of a study in which a large set of both basic and compound
emotions is mapped to probability distributions in the Valence-Arousal-Dominance (VAD) space. In this way, given a face image annotated with VAD values, we can estimate the likelihood of it belonging to each of the distributions, so that emotional states can be described as a mixture of
emotions, enriching their description, while also accounting for the ambiguous nature of their perception. In a preliminary set of experiments, we illustrate the advantages of this solution and a new possible direction of investigation. Data annotations are available at https://github.com/jbcnrlz/affectnet-b-annotation.
Read the full abstract ▾
Machine Learning · Cross-listed from cs.GT
Fair Transit Stop Placement: A Clustering Perspective and Beyond
Haris Aziz, Ling Gai, Yuhang Guo et al. (+1 more)
We study the transit stop placement (TrSP) problem in general metric spaces, where
agents travel between source-destination pairs and may either walk directly or utilize a shuttle service via selected transit stops. We investigate
fairness in TrSP through the lens of justified representation (JR) and the core, and uncover a structural correspondence with fair clustering. Specifically, we show that a constant-factor approximation to proportional
fairness in clustering can be used to guarantee a constant-factor biparameterized approximation to core. We establish a lower bound of 1.366 on the approximability of JR, and moreover show that no clustering
algorithm can approximate JR within a factor better than 3. Going beyond clustering, we propose the Expanding Cost
Algorithm, which achieves a tight 2.414-approximation for JR, but does not give any bounded core guarantee. In light of this, we introduce a parameterized
algorithm that interpolates between these approaches, and enables a tunable trade-off between JR and core. Finally, we complement our results with an experimental analysis using small-
market public carpooling data.
Read the full abstract ▾
All authors Haris Aziz, Ling Gai, Yuhang Guo, Jeremy Vollen
Machine Learning
Robust Online Learning
Sajad Ashkezari
We study the problem of learning robust classifiers where the classifier will receive a perturbed input. Unlike robust PAC learning studied in prior work, here the clean data and its label are also adversarially chosen. We formulate this setting as an online learning problem and consider both the realizable and agnostic learnability of hypothesis classes. We define a new dimension of classes and show it controls the mistake bounds in the realizable setting and the regret bounds in the agnostic setting. In contrast to the dimension that characterizes learnability in the PAC setting, our dimension is rather simple and resembles the Littlestone dimension. We generalize our dimension to multiclass hypothesis classes and prove similar results in the realizable case. Finally, we study the case where the learner does not know the set of allowed perturbations for each point and only has some prior on them.
Read the full abstract ▾
Machine Learning
On the Convergence of Multicalibration Gradient Boosting
Daniel Haimovich, Fridolin Linder, Lorenzo Perini et al. (+2 more)
Multicalibration gradient boosting has recently emerged as a scalable method that empirically produces approximately multicalibrated predictors and has been deployed at web scale. Despite this empirical success, its convergence properties are not well understood. In this paper, we provide computational guarantees for multicalibration gradient boosting
algorithms. We show that the magnitude of successive prediction updates decays at $O(1/\sqrt{T})$, which implies the same convergence rate bound for the empirical multicalibration error over rounds. Under additional smoothness assumptions on the weak learners, this rate improves to linear convergence. We further establish convergence for adaptive variants. Experiments on real-world
datasets support our theory and clarify the regimes in which the method achieves fast convergence.
Read the full abstract ▾
All authors Daniel Haimovich, Fridolin Linder, Lorenzo Perini, Niek Tax, Milan Vojnovic
Machine Learning
Calibrating Generative AI to Produce Realistic Essays for Data Augmentation
Edward W. Wolfe and Justin O. Barber
Data augmentation can mitigate limited training data in machine-learning automated scoring engines for constructed response items. This study seeks to determine how well three approaches to large
language model prompting produce essays that preserve the writing quality of the original essays and produce realistic text for augmenting ASE training
datasets. We created simulated versions of student essays, and human raters assigned scores to them and rated the realism of the generated text. The results of the study indicate that the predict next prompting strategy produces the highest level of agreement between human raters regarding simulated essay scores, predict next and sentence strategies best preserve the rated quality of the original essay in the simulated essays, and predict next and 25 examples strategies produce the most realistic text as judged by human raters.
Read the full abstract ▾
Machine Learning
AEGIS: Adversarial Target-Guided Retention-Data-Free Robust Concept Erasure from Diffusion Models
Fengpeng Li, Kemou Li, Qizhou Wang et al. (+2 more)
Concept erasure helps stop
diffusion models (DMs) from generating harmful content; but current methods face robustness retention trade off. Robustness means the model fine-tuned by concept erasure methods resists reactivation of erased concepts, even under semantically related
prompts. Retention means unrelated concepts are preserved so the model's overall utility stays intact. Both are critical for concept erasure in practice, yet addressing them simultaneously is challenging, as existing works typically improve one factor while sacrificing the other. Prior work typically strengthens one while degrading the other, e.g., mapping a single erased
prompt to a fixed safe target leaves class level remnants exploitable by
prompt attacks, whereas retention-oriented schemes underperform against adaptive adversaries. This paper introduces
Adversarial Erasure with Gradient Informed Synergy (AEGIS), a retention-data-free framework that advances both robustness and retention.
Read the full abstract ▾
All authors Fengpeng Li, Kemou Li, Qizhou Wang, Bo Han, Jiantao Zhou
Machine Learning
Soft Forward-Backward Representations for Zero-shot Reinforcement Learning with General Utilities
Marco Bagatella, Thomas Rupf, Georg Martius et al. (+1 more)
Recent advancements in zero-shot reinforcement learning (RL) have facilitated the extraction of diverse behaviors from unlabeled, offline data sources. In particular, forward-backward
algorithms (FB) can retrieve a family of policies that can approximately solve any standard RL problem (with additive rewards, linear in the occupancy measure), given sufficient capacity. While retaining zero-shot properties, we tackle the greater problem class of RL with general utilities, in which the objective is an arbitrary differentiable function of the occupancy measure. This setting is strictly more expressive, capturing tasks such as distribution matching or pure exploration, which may not be reduced to additive rewards. We show that this additional complexity can be captured by a novel, maximum
entropy (soft) variant of the forward-backward
algorithm, which recovers a family of
stochastic policies from offline data. When coupled with zero-order search over compact policy
embeddings, this
algorithm can sidestep iterative optimization schemes, and optimizes general utilities directly at test-time. Across both didactic and high-dimensional experiments, we demonstrate that our method retains favorable properties of FB
algorithms, while also extending their range to more general RL problems.
Read the full abstract ▾
All authors Marco Bagatella, Thomas Rupf, Georg Martius, Andreas Krause
Machine Learning · Cross-listed from cs.CR
A Unified Framework for LLM Watermarks
Thibaud Gloaguen, Robin Staab, Nikola Jovanović et al. (+1 more)
LLM watermarks allow tracing AI-generated texts by inserting a detectable signal into their generated content. Recent works have proposed a wide range of watermarking
algorithms, each with distinct designs, usually built using a bottom-up approach. Crucially, there is no general and principled formulation for LLM watermarking. In this work, we show that most existing and widely used watermarking schemes can in fact be derived from a principled constrained optimization problem. Our formulation unifies existing watermarking methods and explicitly reveals the constraints that each method optimizes. In particular, it highlights an understudied quality-diversity-power trade-off. At the same time, our framework also provides a principled approach for designing novel watermarking schemes tailored to specific requirements. For instance, it allows us to directly use perplexity as a proxy for quality, and derive new schemes that are optimal with respect to this constraint. Our experimental evaluation validates our framework: watermarking schemes derived from a given constraint consistently maximize detection power with respect to that constraint.
Read the full abstract ▾
All authors Thibaud Gloaguen, Robin Staab, Nikola Jovanović, Martin Vechev
Machine Learning · Cross-listed from cs.AI
Semantically Labelled Automata for Multi-Task Reinforcement Learning with LTL Instructions
Alessandro Abate, Giuseppe De Giacomo, Mathias Jackermeier et al. (+3 more)
We study multi-task reinforcement learning (RL), a setting in which an
agent learns a single, universal policy capable of generalising to arbitrary, possibly unseen tasks. We consider tasks specified as linear temporal logic (LTL) formulae, which are commonly used in formal methods to specify properties of systems, and have recently been successfully adopted in RL. In this setting, we present a novel task
embedding technique leveraging a new generation of semantic LTL-to-automata translations, originally developed for temporal synthesis. The resulting semantically labelled automata contain rich, structured information in each state that allow us to (i) compute the automaton efficiently on-the-fly, (ii) extract expressive task
embeddings used to condition the policy, and (iii) naturally support full LTL. Experimental results in a variety of domains demonstrate that our approach achieves state-of-the-art performance and is able to scale to complex specifications where existing methods fail.
Read the full abstract ▾
All authors Alessandro Abate, Giuseppe De Giacomo, Mathias Jackermeier, Jan Kretínský, Maximilian Prokop, Christoph Weinhuber
Machine Learning
Disentanglement by means of action-induced representations
Gorka Muñoz-Gil, Hendrik Poulsen Nautrup, Arunava Majumder et al. (+4 more)
Learning interpretable representations with variational autoencoders (VAEs) is a major goal of representation learning. The main challenge lies in obtaining disentangled representations, where each latent dimension corresponds to a distinct generative factor. This difficulty is fundamentally tied to the inability to perform nonlinear independent component analysis. Here, we introduce the framework of action-induced representations (AIRs) which models representations of physical systems given experiments (or actions) that can be performed on them. We show that, in this framework, we can provably disentangle degrees of freedom w.r.t. their action dependence. We further introduce a variational AIR architecture (VAIR) that can extract AIRs and therefore achieve provable disentanglement where standard VAEs fail. Beyond state representation, VAIR also captures the action dependence of the underlying generative factors, directly linking experiments to the degrees of freedom they influence.
Read the full abstract ▾
All authors Gorka Muñoz-Gil, Hendrik Poulsen Nautrup, Arunava Majumder, Paulin de Schoulepnikoff, Florian Fürrutter, Marius Krumm, Hans J. Briegel
Machine Learning
Optimized Piecewise Affine Abstractions of Neural Networks with Learnable Activation Functions
Noah Schwartz, Chandra Kanth Nagesh, Sriram Sankaranarayanan et al. (+3 more)
We present a generalized framework for the range verification of neural networks featuring non-linear activation functions. Our approach first constructs an “optimized piecewise affine abstraction" of the network that replaces each non-linear activation function by a piecewise affine (PWA) function plus a bounded error. Such PWA functions are readily amenable to existing neural network verification techniques using specializations of linear arithmetic SMT solvers and mixed-integer optimization approaches. However, there are infinitely many ways to abstract each node, with a natural tradeoff between the number of pieces used, the global error bound, and the complexity of the resulting verification problem. We propose a dynamic programming (DP)
algorithm to systematically compute the optimized PWA abstraction for general activation functions, guaranteeing tighter output bounds. The
algorithm combines a local DP approximation at each node with a global error bound, yielding a variant of the knapsack problem for deciding how to allocate a fixed budget on the total number of pieces across units so as to minimize the worst-case error bound between the network and its approximation. Although the knapsack problem is itself NP-hard, we can use pseudo-
polynomial DP
algorithms as well as approximation schemes to solve it efficiently. Crucially, our approach is broadly applicable to diverse networks consisting of non-linear activations, including standard Multi-Layer Perceptrons (MLPs) and recently proposed architectures such as Kolmogorov-Arnold Networks (KANs). Over a series of KAN
benchmarks spanning 20 to 22,000 parameters, our approach yields output bounds that are consistently of smaller width than uniform PWA allocation. The overall time taken is roughly comparable while the overhead for computing the optimized abstraction is subsumed by the time taken to compute output bounds.
Read the full abstract ▾
All authors Noah Schwartz, Chandra Kanth Nagesh, Sriram Sankaranarayanan, Ramneet Kaur, Tuhin Sahai, Susmit Jha
Machine Learning
Pairwise is Not Enough: Hypergraph Neural Networks for Multi-Agent Pathfinding
Rishabh Jain, Keisuke Okumura, Michael Amir et al. (+2 more)
Multi-
Agent Path Finding (MAPF) is a representative multi-
agent coordination problem, where multiple
agents are required to navigate to their respective goals without collisions. Solving MAPF optimally is known to be NP-hard, leading to the adoption of learning-based approaches to alleviate the online computational burden. Prevailing approaches, such as Graph Neural Networks (GNNs), are typically constrained to pairwise message passing between
agents. However, this limitation leads to suboptimal behaviours and critical issues, such as
attention dilution, particularly in dense environments where group (i.e. beyond just two
agents) coordination is most critical. Despite the importance of such higher-order interactions, existing approaches have not been able to fully explore them. To address this representational bottleneck, we introduce HMAGAT (Hypergraph Multi-
Agent Attention Network), a novel architecture that leverages attentional mechanisms over directed hypergraphs to explicitly capture group dynamics. Empirically, HMAGAT establishes a new state-of-the-art among learning-based MAPF solvers: e.g., despite having just 1M parameters and being trained on 100$\times$ less data, it outperforms the current SoTA 85M parameter model. Through detailed analysis of HMAGAT's
attention values, we demonstrate how hypergraph representations mitigate the
attention dilution inherent in GNNs and capture complex interactions where pairwise methods fail. Our results illustrate that appropriate inductive biases are often more critical than the training data size or sheer parameter count for multi-
agent problems.
Read the full abstract ▾
All authors Rishabh Jain, Keisuke Okumura, Michael Amir, Pietro Lio, Amanda Prorok
Machine Learning
F-GRPO: Don't Let Your Policy Learn the Obvious and Forget the Rare
Daniil Plyusov, Alexey Gorbatovski, Boris Shaposhnikov et al. (+4 more)
Reinforcement Learning with Verifiable Rewards (RLVR) is commonly based on group sampling to estimate advantages and stabilize policy updates. In practice, computational limits often rule out very large groups, so training proceeds with finite rollout sets that can reinforce only the correct behavior they expose. At practical group sizes, updates can miss rare-correct trajectories while still containing mixed rewards, concentrating probability on more common sampled solutions. We derive the probability of such
prompt-local tail-miss events as a function of group size, showing non-monotonic behavior, and in the categorical abstraction characterize how unsampled-correct mass can shrink even as total correct mass grows. Motivated by this analysis, we propose a difficulty-aware scaling coefficient, inspired by Focal loss, that down-weights updates on high-success sampled groups. Empirically, categorical simulation illustrates the same effect in the categorical setting, Maze provides a single-solution test, and LLM experiments include a representative GRPO group-size sweep together with fixed-$N$ transfer across GRPO, DAPO, and CISPO. On Qwen2.5-7B at $N{=}8$, our method improves average math pass@256 from 64.1 $\rightarrow$ 70.3 (GRPO), 69.3 $\rightarrow$ 72.5 (DAPO), and 73.2 $\rightarrow$ 76.8 (CISPO); OOD pass@256 also improves in all three cases, without increasing group size or computational cost.
Read the full abstract ▾
All authors Daniil Plyusov, Alexey Gorbatovski, Boris Shaposhnikov, Viacheslav Sinii, Alexey Malakhov, Daria Korotyshova, Daniil Gavrilov
Machine Learning · Cross-listed from stat.ML
Distribution Shift in Missing Data Imputation: A Risk-Based Perspective and Importance-Weighted Correction under MAR
Luke Shannon, Song Liu and Katarzyna Reluga
Missing data imputation, where a model is trained on observed data to estimate unobserved values, is a fundamental problem in machine learning. In this paper, we rigorously formulate imputation model learning as a mean-squared error risk minimisation problem. We show that when the probability of missingness depends on the data, many state-of-the-art methods fail to account for the resulting distribution shift between the observed data used for training and the full data distribution used for evaluation. Consequently, these approaches do not minimise mean-squared error on the full data distribution. Instead, we propose a novel imputation
algorithm designed to learn an imputation model from the observed data while explicitly accounting for this distribution shift. Simulation studies show consistent improvements over otherwise identical uncorrected baselines, with average reductions of 3% in RMSE and 7% in Wasserstein distance.
Read the full abstract ▾
Machine Learning
SaDiT: Efficient Protein Backbone Design via Latent Structural Tokenization and Diffusion Transformers
Shentong Mo and Lanqing Li
Generative models for de novo
protein backbone design have achieved remarkable success in creating novel
protein structures. However, these
diffusion-based approaches remain computationally intensive and slower than desired for large-scale structural exploration. While recent efforts like Proteina have introduced flow-matching to improve sampling efficiency, the potential of tokenization for structural compression and acceleration remains largely unexplored in the
protein domain. In this work, we present SaDiT, a novel framework that accelerates
protein backbone generation by integrating SaProt Tokenization with a
Diffusion Transformer (DiT) architecture. SaDiT leverages a discrete latent space to represent
protein geometry, significantly reducing the complexity of the generation process while maintaining theoretical SE(3) equivalence. To further enhance efficiency, we introduce an IPA
Token Cache mechanism that optimizes the Invariant Point
Attention (IPA) layers by reusing computed
token states during iterative sampling. Experimental results demonstrate that SaDiT outperforms state-of-the-art models, including RFDiffusion and Proteina, in both computational speed and structural viability. We evaluate our model across unconditional backbone generation and fold-class conditional generation tasks, where SaDiT shows superior ability to capture complex topological features with high designability.
Read the full abstract ▾
Machine Learning
Explaining Grokking in Transformers through the Lens of Inductive Bias
Jaisidh Singh, Diganta Misra and Antonio Orvieto
We investigate grokking in
transformers through the lens of inductive bias: dispositions arising from architecture or optimization that let the network prefer one solution over another. We first show that architectural choices such as the position of Layer Normalization (LN) strongly modulates grokking speed. This modulation is explained by isolating how LN on specific pathways shapes shortcut-learning and
attention entropy. Subsequently, we study how different optimization settings modulate grokking, inducing distinct interpretations of previously proposed controls such as readout scale. Particularly, we find that using readout scale as a control for lazy training can be confounded by learning rate and weight decay in our setting. Accordingly, we show that features evolve continuously throughout training, suggesting grokking in
transformers can be more nuanced than a lazy-to-rich transition of the learning regime. Finally, we show how generalization predictably emerges with feature compressibility in grokking, across different modulators of inductive bias. Our code is released at https://tinyurl.com/y52u3cad.
Read the full abstract ▾
Machine Learning · Cross-listed from cs.CR
Taipan: A Query-free Transfer-based Multiple Sensitive Attribute Inference Attack Solely from Auxiliary Graphs
Ying Song and Balaji Palanisamy
Graph-structured data underpin a wide spectrum of modern applications, yet their multiple sensitive attributes are not isolated but deeply coupled with graph
topology. This coupling facilitates intersectional
privacy leakage through attribute inference attacks (AIAs). Existing AIAs predominantly assume adversaries with two capabilities: (I) access to either auxiliary data sampled from the same distribution as the target or partial training records, and (II) the ability to repeatedly query the victim model. In reality, however, these assumptions are often impractical due to stringent data protection regulations, prohibitive query budgets, and heightened detection risks. Moreover, as prior attacks are designed to infer a single sensitive attribute at a time, they fail to simultaneously recover multiple attributes and thus underestimate overall
privacy risks arising from cross-attribute dependencies. More critically, they obscure a systemic blind spot: auxiliary graphs alone are sufficient to expose multiple sensitive attributes in the target graph. This threat persists even under distribution shifts, enabling stealthy offline attacks without any model interactions. To investigate this unexplored vulnerability, we introduce Taipan, the first query-free framework for multiple sensitive attribute inference attacks on graphs (G-MSAIAs). Taipan incorporates Hierarchical Attack Knowledge Routing to capture intricate inter-attribute correlations, and
Prompt-guided Attack Prototype Refinement to mitigate distribution shifts between auxiliary and target graphs. Extensive experiments on diverse real-world graph
datasets demonstrate that Taipan consistently achieves strong attack performance across same-, similar-, and out-of-distribution settings, and remains effective under partial label coverage or even rigorous
privacy guarantees.
Read the full abstract ▾
Machine Learning · Cross-listed from quant-ph
Quantum Attention by Overlap Interference: Predicting Classical and Many-Body Quantum Sequences
Alessio Pecilli and Matteo Rosati
We propose a variational
quantum implementation of self-
attention (QSA)-the core operation in
transformers and large
language models-which predicts future elements of a sequence by forming overlap-weighted combinations of past data. At variance with previous approaches, our QSA realizes the required nonlinearity through interference of state overlaps and a degree-$k$
polynomial kernel, and estimates a loss based on Rényi-$1/2$ entropic functionals via two observables' expectation values, avoiding the decoding of amplitude-encoded predictions into classical probabilities. QSA also accommodates a constrained, trainable data-
embedding tying state overlaps to data-level similarities. Its dominant end-to-end training complexity scales as $O\left(\mu^{-1}k^2Td\right)$, versus $O\left(T d^{k+1}\right)$ of the fairest classical comparison, with $\mu$ a training signal; we show numerically that this allows a complexity advantage in the regime where sequence length $T$ dominates the
embedding size $d$. In simulations, our QSA-based
quantum transformer learns sequence prediction on classical data and on many-body transverse-field Ising trajectories-establishing trainable
attention as a practical primitive for
quantum dynamical modeling.
Read the full abstract ▾
Machine Learning
Diffeomorphism-Equivariant Neural Networks
Josephine Elisabeth Oettinger, Zakhar Shumaylov, Johannes Bostelmann et al. (+2 more)
Incorporating group
symmetries via equivariance into neural networks has emerged as a robust approach for overcoming the efficiency and data demands of modern deep learning. While most existing approaches, such as group convolutions and averaging-based methods, focus on compact, finite, or low-dimensional groups with linear actions, this work explores how equivariance can be extended to infinite-dimensional groups. We propose a strategy designed to induce diffeomorphism equivariance in pre-trained neural networks via energy-based canonicalisation. Formulating equivariance as an optimisation problem allows us to access the rich toolbox of already established differentiable image registration methods. Empirical results on
segmentation and classification tasks confirm that our approach achieves approximate equivariance and generalises to unseen transformations without relying on extensive data augmentation or retraining.
Read the full abstract ▾
All authors Josephine Elisabeth Oettinger, Zakhar Shumaylov, Johannes Bostelmann, Jan Lellmann, Carola-Bibiane Schönlieb
Machine Learning
NanoQuant: Efficient Sub-1-Bit Quantization of Large Language Models
Hyochan Chong, Dongkyu Kim, Changdong Kim et al. (+1 more)
Weight-only quantization has become a standard approach for efficiently serving large
language models (LLMs). However, existing methods fail to efficiently compress models to binary (1-bit) levels, as they either require large amounts of data and compute or incur additional storage. In this work, we propose NanoQuant, the first post-training quantization (PTQ) method to compress LLMs to both binary and sub-1-bit levels. NanoQuant formulates quantization as a low-rank binary factorization problem, and compresses full-precision weights to low-rank binary
matrices and scales. Specifically, it utilizes an efficient alternating direction method of multipliers (ADMM) solver to precisely initialize latent binary
matrices and scales, and then tunes the initialized parameters through a block and model reconstruction process. Consequently, NanoQuant establishes a new Pareto frontier in low-
memory post-training quantization, and enables sub-1-bit compression. NanoQuant makes large-scale deployment feasible on consumer hardware. For example, it compresses Llama2-70B by 25.8$\times$ in just 13 hours on a single H100, enabling a 70B model to operate on a consumer 8 GB GPU. Code is available at https://github.com/SamsungLabs/NanoQuant.
Read the full abstract ▾
All authors Hyochan Chong, Dongkyu Kim, Changdong Kim, Minseop Choi
Machine Learning · Cross-listed from cs.NI
Makespan Minimization in Split Learning: From Theory to Practice
Robert Ganian, Fionn Mc Inerney and Dimitra Tsigkari
Split learning recently emerged as a solution for distributed machine learning with heterogeneous IoT devices, where clients can offload part of their training to computationally-powerful helpers. The core challenge in split learning is to minimize the training time by jointly devising the client-helper assignment and the schedule of tasks at the helpers. We first study the model where each helper has a
memory cardinality constraint on how many clients it may be assigned, which represents the case of homogeneous tasks. Through complexity theory, we rule out exact
polynomial-time
algorithms and approximation schemes even for highly restricted instances of this problem. We complement these negative results with a non-trivial
polynomial-time 5-approximation
algorithm. Building on this, we then focus on the more general heterogeneous task setting considered by Tirana et al. [INFOCOM 2024], where helpers have
memory capacity constraints and clients have variable
memory costs. In this case, we prove that, unless P=NP, the problem cannot admit a
polynomial-time approximation
algorithm for any approximation factor. However, by adapting our aforementioned 5-approximation
algorithm, we develop a novel heuristic for the heterogeneous task setting and show that it outperforms heuristics from prior works through extensive experiments.
Read the full abstract ▾
Machine Learning
Memory-Conditioned Flow-Matching for Stable Autoregressive PDE Rollouts
Victor Armegioiu
Autoregressive generative PDE solvers can be accurate one step ahead yet drift over long rollouts, especially in coarse-to-fine regimes where each step must regenerate unresolved fine scales. This is the regime of
diffusion and flow-matching generators: although their internal dynamics are Markovian, rollout stability is governed by per-step conditional law errors. Using the Mori–Zwanzig projection formalism, we show that eliminating unresolved variables yields an exact resolved
evolution with a Markov term, a
memory term, and an orthogonal forcing, exposing a structural limitation of memoryless closures. Motivated by this, we introduce
memory-conditioned
diffusion/flow-matching with a compact online state injected into denoising via latent features. Via disintegration,
memory induces a structured conditional tail prior for unresolved scales and reduces the transport needed to populate missing frequencies. We prove Wasserstein stability of the resulting conditional kernel. We then derive discrete Grönwall rollout bounds that separate
memory approximation from conditional generation error. Experiments on compressible flows with shocks and multiscale mixing show improved accuracy and markedly more stable long-horizon rollouts, with better fine-scale spectral and statistical fidelity.
Read the full abstract ▾
Machine Learning
Pruning at Initialisation through the lens of Graphon Limit: Convergence, Expressivity, and Generalisation
Hoang Pham, The-Anh Ta and Long Tran-Thanh
Pruning at Initialisation methods discover sparse, trainable subnetworks before training, but their theoretical mechanisms remain elusive. Existing analyses are often limited to finite-width statistics, lacking a rigorous characterisation of the global sparsity patterns that emerge as networks grow large. In this work, we connect discrete
pruning heuristics to graph limit theory via graphons, establishing the graphon limit of PaI masks. We introduce a Factorised Saliency Model that encompasses popular
pruning criteria and prove that, under regularity conditions, the discrete masks generated by these
algorithms converge to deterministic bipartite graphons. This limit framework establishes a novel topological taxonomy for sparse networks: while unstructured methods (e.g., Random, Magnitude) converge to homogeneous graphons representing uniform connectivity, data-driven methods (e.g., SNIP, GraSP) converge to heterogeneous graphons that encode implicit feature selection. Leveraging this continuous characterisation, we derive two fundamental theoretical results: (i) a Universal Approximation
Theorem for sparse networks that depends only on the intrinsic dimension of active coordinate subspaces; and (ii) a Graphon-NTK generalisation bound demonstrating how the limit graphon modulates the kernel geometry to align with informative features. Our results transform the study of sparse neural networks from combinatorial graph problems into a rigorous framework of continuous operators, offering a new mechanism for analysing expressivity and generalisation in sparse neural networks.
Read the full abstract ▾
Machine Learning · Cross-listed from cs.CV
CytoCrowd: A Multi-Annotator Benchmark Dataset for Cytology Image Analysis
Yonghao Si, Xingyuan Zeng, Zhao Chen et al. (+4 more)
High-quality annotated
datasets are crucial for advancing machine learning in medical image analysis. However, a critical gap exists: most
datasets either offer a single, clean ground truth, which hides real-world expert disagreement, or they provide multiple annotations without a separate gold standard for objective evaluation. To bridge this gap, we introduce CytoCrowd, a new public
benchmark for cytology analysis. The
dataset features 446 high-resolution images, each with two key components: (1) raw, conflicting annotations from four independent pathologists, and (2) a separate, high-quality gold-standard ground truth established by a senior expert. This dual structure makes CytoCrowd a versatile resource. It serves as a
benchmark for standard computer
vision tasks, such as object detection and classification, using the ground truth. Simultaneously, it provides a realistic testbed for evaluating annotation aggregation
algorithms that must resolve expert disagreements. We provide comprehensive baseline results for both tasks. Our experiments demonstrate the challenges presented by CytoCrowd and establish its value as a resource for developing the next generation of models for medical image analysis. The
dataset is publicly available at https://github.com/YHSI5358/CytoCrowd-
Datasets.
Read the full abstract ▾
All authors Yonghao Si, Xingyuan Zeng, Zhao Chen, Libin Zheng, Caleb Chen Cao, Lei Chen, Jian Yin
Machine Learning · Cross-listed from cs.RO
HuMI: Humanoid Whole-Body Manipulation from Humanoid-Free Demonstrations
Ruiqian Nai, Boyuan Zheng, Junming Zhao et al. (+8 more)
Current approaches for
humanoid whole-body manipulation, primarily relying on teleoperation or visual sim-to-real reinforcement learning, are hindered by hardware logistics and complex reward engineering. Consequently, demonstrated autonomous skills remain limited and are typically restricted to controlled environments. In this paper, we present the
Humanoid Manipulation Interface (HuMI), a portable and efficient framework for learning diverse whole-body manipulation tasks across various environments. HuMI enables
humanoid-free data collection by capturing rich whole-body motion using portable hardware. This data drives a hierarchical learning pipeline that translates human motions into dexterous and feasible
humanoid skills. Extensive experiments across five whole-body tasks–including kneeling, squatting, tossing, walking, and bimanual manipulation–demonstrate that HuMI achieves a 3x increase in data collection efficiency compared to teleoperation and attains a 70% success rate in unseen environments.
Read the full abstract ▾
All authors Ruiqian Nai, Boyuan Zheng, Junming Zhao, Haodong Zhu, Sicong Dai, Zunhao Chen, Yihang Hu, Yingdong Hu, Tong Zhang, Chuan Wen, Yang Gao
Machine Learning
Temperature Scaling Attack Disrupting Model Confidence in Federated Learning
Kichang Lee, Jaeho Jin, JaeYeon Park et al. (+2 more)
Predictive confidence serves as a foundational control signal in mission-critical systems, directly governing risk-aware logic such as escalation, abstention, and conservative fallback. While prior
federated learning attacks predominantly target accuracy or implant
backdoors, we identify confidence calibration as a distinct attack objective. We present the Temperature Scaling Attack (TSA), a training-time attack that degrades calibration while preserving accuracy. By injecting temperature scaling with learning rate-temperature coupling during local training, TSA shifts model confidence while keeping predictive accuracy and common optimization signals close to benign training. We provide a convergence analysis under non-IID settings, showing that the coupling controls the primary update scale while leaving a bounded temperature-induced residual, yielding the standard non-convex FL convergence structure with an additional residual term. Across three
benchmarks, TSA substantially shifts calibration (e.g., 145% error increase on CIFAR-100) with <2% accuracy change, and remains effective under robust aggregation and post-hoc calibration defenses. Case studies further show up to a 7.2x increase in missed verifications in healthcare and severe confidence-gating failures in autonomous driving, even when accuracy is unchanged. Overall, our results establish calibration integrity as a critical attack surface in
federated learning.
Read the full abstract ▾
All authors Kichang Lee, Jaeho Jin, JaeYeon Park, Songkuk Kim, JeongGil Ko
Machine Learning · Cross-listed from cs.CG
Graph-Based Nearest-Neighbor Search without the Spread
Jeff Giliberti, Sariel Har-Peled, Jonas Sauer et al. (+1 more)
$\renewcommand{\Re}{\mathbb{R}}$Recent work showed how to construct nearest-neighbor graphs of linear size, on a given set $P$ of $n$ points in $\Re^d$, such that one can answer approximate nearest-neighbor queries in logarithmic time in the spread. Unfortunately, the spread might be unbounded in $n$, and an interesting theoretical question is how to remove the dependency on the spread. Here, we show how to construct an external linear-size data structure that, combined with the linear-size graph, allows us to answer ANN queries in logarithmic time in $n$.
Read the full abstract ▾
All authors Jeff Giliberti, Sariel Har-Peled, Jonas Sauer, Ali Vakilian