OpenRaiser/Intern-Atlas huggingface dataset:
Position-based Rogue Access Point Detection
Venue: arXiv cs.CR 2025
Year: 2025

Rogue Wi-Fi access point (AP) attacks can lead to data breaches and unauthorized access. Existing rogue AP detection methods and tools often rely on channel state information (CSI) or received signal strength indicator (RSSI), but they require specific hardware or achieve low detection accuracy. On the other hand, AP positions are typically fixed, and Wi-Fi can support indoor positioning of user devices. Based on this position information, the mobile platform can check if one (or more) AP in range is rogue. The inclusion of a rogue AP would in principle result in a wrong estimated position. Thus, the idea to use different subsets of APs: the positions computed based on subsets that include a rogue AP will be significantly different from those that do not. Our scheme contains two components: subset generation and position validation. First, we generate subsets of RSSIs from APs, which are then utilized for positioning, similar to receiver autonomous integrity monitoring (RAIM). Second, the position estimates, along with uncertainties, are combined into a Gaussian mixture, to check for inconsistencies by evaluating the overlap of the Gaussian components. Our comparative analysis, conducted on a real-world dataset with three types of attacks and synthetic RSSIs integrated, demonstrates a substantial improvement in rogue AP detection accuracy.
Random Abstract Cell Complexes
Venue: arXiv cs.DS 2025
Year: 2025

We define a model for random (abstract) cell complexes (CCs), similiar to the well-known Erdős-Rényi model for graphs and its extensions for simplicial complexes. To build a random cell complex, we first draw from an Erdős-Rényi graph, and consecutively augment the graph with cells for each dimension with a specified probability. As the number of possible cells increases combinatorially -- e.g., 2-cells can be represented as cycles, or permutations -- we derive an approximate sampling algorithm for this model limited to two-dimensional abstract cell complexes. As a basis for this algorithm, we first introduce a spanning-tree-based method that samples simple cycles and allows the efficient approximation of various properties, most notably the probability of occurence of a given cycle. This approximation is of independent interest as it enables the approximation of a wide variety of cycle-related graph statistics using importance sampling. We use this to approximate the number of cycles of a given length on a graph, allowing us to calculate the sampling probability to arrive at a desired expected number of sampled 2-cells. The probability approximation also trivially leads to a sampling algorithm for $2$-cells with a desired sampling probability. We provide some initial analysis into the properties of random CCs drawn from this model. We further showcase practical applications for our random CCs as null models, and in the context of (random) liftings of graphs to cell complexes. The cycle sampling, cycle count estimation, and combined cell sampling algorithms are available in the package `py-raccoon` on the Python Packaging Index.
Improving NLSAT for Nonlinear Real Arithmetic
Venue: arXiv cs.SC 2025
Year: 2025

The Model-Constructing Satisfiability Calculus (MCSAT) framework has been applied to SMT problems over various arithmetic theories. NLSAT, an implementation using cylindrical algebraic decomposition (CAD) for explanation, is especially competitive for nonlinear real arithmetic (NRA) constraints. However, current Conflict-Driven Clause Learning (CDCL)-style algorithms only consider literal information when making decisions, and thus ignore the influence of clauses on arithmetic variables. This limitation may lead NLSAT to encounter unnecessary conflicts due to suboptimal literal choices. To address this issue, we analyze conflicts caused by literal decisions and incorporate clause-level information that directly affects arithmetic variables. We propose two main algorithmic improvements: a clause-level feasible-set-based look-ahead mechanism and an arithmetic propagation-based branching heuristic. We implement our solver, named clauseSMT, based on a dynamic variable ordering framework. Experiments indicate that clauseSMT is competitive on nonlinear real arithmetic problems compared with existing SMT solvers (CVC5, Z3, YICES2), and it outperforms all of them on satisfiable instances of SMT(QF_NRA) in SMT-LIB. We also evaluate the effectiveness of our proposed methods.
Branches: Efficiently Seeking Optimal Sparse Decision Trees with AO*
Venue: arXiv cs.LG 2025
Year: 2025

Decision Tree (DT) Learning is a fundamental problem in Interpretable Machine Learning, yet it poses a formidable optimisation challenge. Practical algorithms have recently emerged, primarily leveraging Dynamic Programming and Branch & Bound. However, most of these approaches rely on a Depth-First-Search strategy, which is inefficient when searching for DTs at high depths and requires the definition of a maximum depth hyperparameter. Best-First-Search was also employed by other methods to circumvent these issues. The downside of this strategy is its higher memory consumption, as such, it has to be designed in a fully efficient manner that takes full advantage of the problem's structure. We formulate the problem within an AND/OR graph search framework and we solve it with a novel AO*-type algorithm called Branches. We prove both optimality and complexity guarantees for Branches and we show that it is more efficient than the state of the art theoretically and on a variety of experiments. Furthermore, Branches supports non-binary features unlike the other methods, we show that this property can further induce larger gains in computational efficiency.
Random Reed-Solomon Codes and Random Linear Codes are Locally Equivalent
Venue: arXiv cs.IT 2025
Year: 2025

We establish an equivalence between two important random ensembles of linear codes: random linear codes (RLCs) and random Reed-Solomon (RS) codes. Specifically, we show that these models exhibit identical behavior with respect to key combinatorial properties -- such as list-decodability and list-recoverability -- when the alphabet size is sufficiently large. We introduce monotone-decreasing local coordinate-wise linear (LCL) properties, a new class of properties tailored for the large alphabet regime. This class encompasses list-decodability, list-recoverability, and their average-weight variants. We develop a framework for analyzing these properties and prove a threshold theorem for RLCs: for any LCL property $\mathcal{P}$, there exists a threshold rate $R_\mathcal{P}$ such that RLCs are likely to satisfy $\mathcal{P}$ when $R < R_\mathcal{P}$ and unlikely to do so when $R > R_\mathcal{P}$. We extend this threshold theorem to random RS codes and show that they share the same threshold $ R_\mathcal{P} $, thereby establishing the equivalence between the two ensembles and enabling a unified analysis of list-recoverability and related properties. Applying our framework, we compute the threshold rate for list-decodability, proving that both random RS codes and RLCs achieve the generalized Singleton bound. This recovers a recent result of Alrabiah, Guruswami, and Li (2023) via elementary methods. Additionally, we prove an upper bound on the list-recoverability threshold and conjecture that this bound is tight. Our approach suggests a plausible pathway for proving this conjecture and thereby pinpointing the list-recoverability parameters of both models. Indeed, following the release of a prior version of this paper, Li and Shagrithaya (2025) used our equivalence theorem to show that random RS codes are near-optimally list-recoverable.
Exploiting Chordal Sparsity for Fast Global Optimality with Application to Localization
Venue: arXiv cs.RO 2025
Year: 2025

In recent years, many estimation problems in robotics have been shown to be solvable to global optimality using their semidefinite relaxations. However, the runtime complexity of off-the-shelf semidefinite programming (SDP) solvers is up to cubic in problem size, which inhibits real-time solutions of problems involving large state dimensions. We show that for a large class of problems, namely those with chordal sparsity, we can reduce the complexity of these solvers to linear in problem size. In particular, we show how to replace the large positive-semidefinite variable with a number of smaller interconnected ones using the well-known chordal decomposition. This formulation also allows for the straightforward application of the alternating direction method of multipliers (ADMM), which can exploit parallelism for increased scalability. We show for two example problems in simulation that the chordal solvers provide a significant speed-up over standard SDP solvers, and that global optimality is crucial in the absence of good initializations.
Federated Class-Incremental Learning with Hierarchical Generative Prototypes
Venue: arXiv cs.LG 2025
Year: 2025

Federated Learning (FL) aims at unburdening the training of deep models by distributing computation across multiple devices (clients) while safeguarding data privacy. On top of that, Federated Continual Learning (FCL) also accounts for data distribution evolving over time, mirroring the dynamic nature of real-world environments. While previous studies have identified Catastrophic Forgetting and Client Drift as primary causes of performance degradation in FCL, we shed light on the importance of Incremental Bias and Federated Bias, which cause models to prioritize classes that are recently introduced or locally predominant, respectively. Our proposal constrains both biases in the last layer by efficiently finetuning a pre-trained backbone using learnable prompts, resulting in clients that produce less biased representations and more biased classifiers. Therefore, instead of solely relying on parameter aggregation, we leverage generative prototypes to effectively balance the predictions of the global model. Our method significantly improves the current State Of The Art, providing an average increase of +7.8% in accuracy.
Scalable MatMul-free Language Modeling
Venue: arXiv cs.CL 2025
Year: 2025

Large Language Models (LLMs) have fundamentally altered how we approach scaling in machine learning. However, these models pose substantial computational and memory challenges, primarily due to the reliance on matrix multiplication (MatMul) within their attention and feed-forward (FFN) layers. We demonstrate that MatMul operations can be eliminated from LLMs while maintaining strong performance, even at billion-parameter scales. Our MatMul-free models, tested on models up to 2.7B parameters, are comparable to state-of-the-art pre-trained Transformers, and the performance gap narrows as model size increases. Our approach yields significant memory savings: a GPU-efficient implementation reduces memory consumption by up to 61% during training and over 10x during inference. When adapted for a multi-chip neuromorphic system, the model leverages asynchronous processing to achieve 4x higher throughput with 10x less energy than edge GPUs.
Edit Distance Robust Watermarks via Indexing Pseudorandom Codes
Venue: arXiv cs.CR 2025
Year: 2025

Motivated by the problem of detecting AI-generated text, we consider the problem of watermarking the output of language models with provable guarantees. We aim for watermarks which satisfy: (a) undetectability, a cryptographic notion introduced by Christ, Gunn & Zamir (2024) which stipulates that it is computationally hard to distinguish watermarked language model outputs from the model's actual output distribution; and (b) robustness to channels which introduce a constant fraction of adversarial insertions, substitutions, and deletions to the watermarked text. Earlier schemes could only handle stochastic substitutions and deletions, and thus we are aiming for a more natural and appealing robustness guarantee that holds with respect to edit distance. Our main result is a watermarking scheme which achieves both undetectability and robustness to edits when the alphabet size for the language model is allowed to grow as a polynomial in the security parameter. To derive such a scheme, we follow an approach introduced by Christ & Gunn (2024), which proceeds via first constructing pseudorandom codes satisfying undetectability and robustness properties analogous to those above; our key idea is to handle adversarial insertions and deletions by interpreting the symbols as indices into the codeword, which we call indexing pseudorandom codes. Additionally, our codes rely on weaker computational assumptions than used in previous work. Then we show that there is a generic transformation from such codes over large alphabets to watermarking schemes for arbitrary language models.
Discovering Continuous-Time Memory-Based Symbolic Policies using Genetic Programming
Venue: arXiv cs.NE 2025
Year: 2025

Artificial intelligence techniques are increasingly being applied to solve control problems, but often rely on black-box methods without transparent output generation. To improve the interpretability and transparency in control systems, models can be defined as white-box symbolic policies described by mathematical expressions. For better performance in partially observable and volatile environments, the symbolic policies are extended with memory represented by continuous-time latent variables, governed by differential equations. Genetic programming is used for optimisation, resulting in interpretable policies consisting of symbolic expressions. Our results show that symbolic policies with memory compare with black-box policies on a variety of control tasks. Furthermore, the benefit of the memory in symbolic policies is demonstrated on experiments where memory-less policies fall short. Overall, we present a method for evolving high-performing symbolic policies that offer interpretability and transparency, which lacks in black-box models.
Distilling Aggregated Knowledge for Weakly-Supervised Video Anomaly Detection
Venue: arXiv cs.CV 2025
Year: 2025

Video anomaly detection aims to develop automated models capable of identifying abnormal events in surveillance videos. The benchmark setup for this task is extremely challenging due to: i) the limited size of the training sets, ii) weak supervision provided in terms of video-level labels, and iii) intrinsic class imbalance induced by the scarcity of abnormal events. In this work, we show that distilling knowledge from aggregated representations of multiple backbones into a single-backbone Student model achieves state-of-the-art performance. In particular, we develop a bi-level distillation approach along with a novel disentangled cross-attention-based feature aggregation network. Our proposed approach, DAKD (Distilling Aggregated Knowledge with Disentangled Attention), demonstrates superior performance compared to existing methods across multiple benchmark datasets. Notably, we achieve significant improvements of 1.36%, 0.78%, and 7.02% on the UCF-Crime, ShanghaiTech, and XD-Violence datasets, respectively.
Robots Have Been Seen and Not Heard: Effects of Consequential Sounds on Human-Perception of Robots
Venue: arXiv cs.RO 2025
Year: 2025

Robots make compulsory machine sounds, known as `consequential sounds', as they move and operate. As robots become more prevalent in workplaces, homes and public spaces, understanding how sounds produced by robots affect human-perceptions of these robots is becoming increasingly important to creating positive human robot interactions (HRI). This paper presents the results from 182 participants (858 trials) investigating how human-perception of robots is changed by consequential sounds. In a between-participants study, participants in the sound condition were shown 5 videos of different robots and asked their opinions on the robots and the sounds they made. This was compared to participants in the control condition who viewed silent videos. Consequential sounds correlated with significantly more negative perceptions of robots, including increased negative `associated affects', feeling more distracted, and being less willing to colocate in a shared environment with robots.
Filtered not Mixed: Stochastic Filtering-Based Online Gating for Mixture of Large Language Models
Venue: arXiv cs.LG 2025
Year: 2025

We propose MoE-F - a formalized mechanism for combining $N$ pre-trained Large Language Models (LLMs) for online time-series prediction by adaptively forecasting the best weighting of LLM predictions at every time step. Our mechanism leverages the conditional information in each expert's running performance to forecast the best combination of LLMs for predicting the time series in its next step. Diverging from static (learned) Mixture of Experts (MoE) methods, our approach employs time-adaptive stochastic filtering techniques to combine experts. By framing the expert selection problem as a finite state-space, continuous-time Hidden Markov model (HMM), we can leverage the Wohman-Shiryaev filter. Our approach first constructs N parallel filters corresponding to each of the $N$ individual LLMs. Each filter proposes its best combination of LLMs, given the information that they have access to. Subsequently, the N filter outputs are optimally aggregated to maximize their robust predictive power, and this update is computed efficiently via a closed-form expression, generating our ensemble predictor. Our contributions are: **(I)** the MoE-F plug-and-play filtering harness algorithm, **(II)** theoretical optimality guarantees of the proposed filtering-based gating algorithm (via optimality guarantees for its parallel Bayesian filtering and its robust aggregation steps), and **(III)** empirical evaluation and ablative results using state-of-the-art foundational and MoE LLMs on a real-world __Financial Market Movement__ task where MoE-F attains a remarkable 17\% absolute and 48.5\% relative F1 measure improvement over the next best performing individual LLM expert predicting short-horizon market movement based on streaming news. Further, we provide empirical evidence of substantial performance gains in applying MoE-F over specialized models in the long-horizon time-series forecasting domain.
Towards Understanding the Influence of Training Samples on Explanations
Venue: arXiv cs.LG 2025
Year: 2025

Explainable AI (XAI) is widely used to analyze AI systems' decision-making, such as providing counterfactual explanations for recourse. When unexpected explanations occur, users may want to understand the training data properties shaping them. Under the umbrella of data valuation, first approaches have been proposed that estimate the influence of data samples on a given model. This process not only helps determine the data's value, but also offers insights into how individual, potentially noisy, or misleading examples affect a model, which is crucial for interpretable AI. In this work, we apply the concept of data valuation to the significant area of model evaluations, focusing on how individual training samples impact a model's internal reasoning rather than the predictive performance only. Hence, we introduce the novel problem of identifying training samples shaping a given explanation or related quantity, and investigate the particular case of the cost of computational recourse. We propose an algorithm to identify such influential samples and conduct extensive empirical evaluations in two case studies.
Graph Convolutional Branch and Bound
Venue: arXiv cs.LG 2025
Year: 2025

This article explores the integration of deep learning models into combinatorial optimization pipelines, specifically targeting NP-hard problems. Traditional exact algorithms for such problems often rely on heuristic criteria to guide the exploration of feasible solutions. In this work, we propose using neural networks to learn informative heuristics-most notably, an optimality score that estimates a solution's proximity to the optimum. This score is used to evaluate nodes within a branch-and-bound framework, enabling a more efficient traversal of the solution space. Focusing on the Traveling Salesman Problem, we describe two exact solvers-1-tree branch-and-bound and Concorde-and introduce a hybrid approach called Graph Convolutional Branch and Bound, which augments these solvers with a graph convolutional neural network along with a novel unsupervised training strategy that facilitates generalization to graphs of varying sizes without requiring labeled data. Empirical results demonstrate the effectiveness of the proposed method, showing a significant reduction in the number of explored branch-and-bound nodes and overall computational time.
ZeroPur: Succinct Training-Free Adversarial Purification
Venue: arXiv cs.CV 2025
Year: 2025

Adversarial purification is a kind of defense technique that can defend against various unseen adversarial attacks without modifying the victim classifier. Existing methods often depend on external generative models or cooperation between auxiliary functions and victim classifiers. However, retraining generative models, auxiliary functions, or victim classifiers relies on the domain of the fine-tuned dataset and is computation-consuming. In this work, we suppose that adversarial images are outliers of the natural image manifold, and the purification process can be considered as returning them to this manifold. Following this assumption, we present a simple adversarial purification method without further training to purify adversarial images, called ZeroPur. ZeroPur contains two steps: given an adversarial example, Guided Shift obtains the shifted embedding of the adversarial example by the guidance of its blurred counterparts; after that, Adaptive Projection constructs a directional vector by this shifted embedding to provide momentum, projecting adversarial images onto the manifold adaptively. ZeroPur is independent of external models and requires no retraining of victim classifiers or auxiliary functions, relying solely on victim classifiers themselves to achieve purification. Extensive experiments on three datasets (CIFAR-10, CIFAR-100, and ImageNet-1K) using various classifier architectures (ResNet, WideResNet) demonstrate that our method achieves state-of-the-art robust performance. The code will be publicly available.
CATCODER: Repository-Level Code Generation with Relevant Code and Type Context
Venue: arXiv cs.SE 2025
Year: 2025

Large language models (LLMs) have demonstrated remarkable capabilities in code generation tasks. However, repository-level code generation presents unique challenges, particularly due to the need to utilize information spread across multiple files within a repository. Specifically, successful generation depends on a solid grasp of both general, context-agnostic knowledge and specific, context-dependent knowledge. While LLMs are widely used for the context-agnostic aspect, existing retrieval-based approaches sometimes fall short as they are limited in obtaining a broader and deeper repository context. In this paper, we present CatCoder, a novel code generation framework designed for statically typed programming languages. CatCoder enhances repository-level code generation by integrating relevant code and type context. Specifically, it leverages static analyzers to extract type dependencies and merges this information with retrieved code to create comprehensive prompts for LLMs. To evaluate the effectiveness of CatCoder, we adapt and construct benchmarks that include 199 Java tasks and 90 Rust tasks. The results show that CatCoder outperforms the RepoCoder baseline by up to 14.44% and 17.35%, in terms of compile@k and pass@k scores. In addition, the generalizability of CatCoder is assessed using various LLMs, including both code-specialized models and general-purpose models. Our findings indicate consistent performance improvements across all models, which underlines the practicality of CatCoder. Furthermore, we evaluate the time consumption of CatCoder in a large open source repository, and the results demonstrate the scalability of CatCoder.