OpenRaiser/Intern-Atlas huggingface dataset:
Parameterized Maximum Node-Disjoint Paths
Venue: arXiv cs.DS 2025
Year: 2025

We revisit the Maximum Node-Disjoint Paths problem, the natural optimization version of Node-Disjoint Paths, where we are given a graph $G$, $k$ pairs of vertices $(s_i, t_i)$ and an integer $\ell$, and are asked whether there exist at least $\ell$ vertex-disjoint paths in $G$ whose endpoints are given pairs. We present several results, with an emphasis towards FPT approximation. Our main positive contribution is to show that the problem's intractability can be overcome using approximation and that for several of the structural parameters for which the problem is hard, most notably tree-depth, it admits an efficient FPT approximation scheme, returning a $(1-\varepsilon)$-approximate solution in time $f(td,\varepsilon)n^{O(1)}$. We manage to obtain these results by comprehensively mapping out the structural parameters for which the problem is FPT if $\ell$ is also a parameter, hence showing that understanding $\ell$ as a parameter is key to the problem's approximability. This, in turn, is a problem we are able to solve via a surprisingly simple color-coding algorithm, which relies on identifying an insightful problem-specific variant of the natural parameter, namely the number of vertices used in the solution. A natural question is whether the FPT approximation algorithm we devised for tree-depth can be extended to pathwidth. We resolve this negatively, showing that under the Parameterized Inapproximability Hypothesis no FPT approximation scheme for this parameter is possible, even in time $f(pw,\varepsilon)n^{g(\varepsilon)}$, thus precisely determining the parameter border where the problem transitions from ``hard but approximable'' to ``inapproximable''. Lastly, we strengthen existing lower bounds by replacing W[1]-hardness by XNLP-completeness for parameter pathwidth, and improving the $n^{o(\sqrt{td})}$ ETH-based lower bound for tree-depth to $n^{o(td)}$.
Uncertainty in latent representations of variational autoencoders optimized for visual tasks
Venue: arXiv cs.LG 2025
Year: 2025

Deep Generative Models (DGMs) can learn flexible latent variable representations of images while avoiding intractable computations, common in Bayesian inference. However, investigating the properties of inference in Variational Autoencoders (VAEs), a major class of DGMs, reveals severe problems in their uncertainty representations. Here we draw inspiration from classical computer vision to introduce an inductive bias into the VAE by incorporating a global explaining-away latent variable, which remedies defective inference in VAEs. Unlike standard VAEs, the Explaing-Away VAE (EA-VAE) provides uncertainty estimates that align with normative requirements across a wide spectrum of perceptual tasks, including image corruption, interpolation, and out-of-distribution detection. We find that restored inference capabilities are delivered by developing a motif in the inference network (the encoder) which is widespread in biological neural networks: divisive normalization. Our results establish EA-VAEs as reliable tools to perform inference under deep generative models with appropriate estimates of uncertainty.
Strategy Complexity of Büchi and Transience Objectives in Concurrent Stochastic Games
Venue: arXiv cs.GT 2025
Year: 2025

We study 2-player zero-sum concurrent (i.e., simultaneous move) stochastic Büchi games and Transience games on countable graphs. Two players, Max and Min, seek respectively to maximize and minimize the probability of satisfying the game objective. The Büchi objective is to visit a given set of target states infinitely often. This can be seen as a special case of maximizing the expected $\limsup$ of the daily rewards, where all daily rewards are in $\{0,1\}$. The Transience objective is to visit no state infinitely often, i.e., every finite subset of the states is eventually left forever. Transience can only be met in infinite game graphs. We show that in Büchi games there always exist $\varepsilon$-optimal Max strategies that use just a step counter (discrete clock) plus 1 bit of public memory. This upper bound holds for all countable graphs, but it is a new result even for the special case of finite graphs. The upper bound is tight in the sense that Max strategies that use just a step counter, or just finite memory, are not sufficient even on finite game graphs. This upper bound is a consequence of a slightly stronger new result: $\varepsilon$-optimal Max strategies for the combined Büchi and Transience objective require just 1 bit of public memory (but cannot be memoryless). Our proof techniques also yield a closely related result, that $\varepsilon$-optimal Max strategies for the Transience objective alone can be chosen as memoryless.
An MRP Formulation for Supervised Learning: Generalized Temporal Difference Learning Models
Venue: arXiv cs.LG 2025
Year: 2025

In traditional statistical learning, data points are usually assumed to be independently and identically distributed (i.i.d.) following an unknown probability distribution. This paper presents a contrasting viewpoint, perceiving data points as interconnected and employing a Markov reward process (MRP) for data modeling. We reformulate the typical supervised learning as an on-policy policy evaluation problem within reinforcement learning (RL), introducing a generalized temporal difference (TD) learning algorithm as a resolution. Theoretically, our analysis establishes connections between the solutions of linear TD learning and ordinary least squares (OLS). Under specific conditions -- particularly when the noise is correlated -- the TD solution serves as a more effective estimator than OLS. Furthermore, we show that when our algorithm is applied with many commonly used loss functions -- such as those found in generalized linear models -- it corresponds to the application of a novel and generalized Bellman operator. We prove that this operator admits a unique fixed point, and based on this, we establish convergence guarantees for our generalized TD algorithm under linear function approximation. Empirical studies verify our theoretical results, examine the vital design of our TD algorithm and show practical utility across various datasets, encompassing tasks such as regression and image classification with deep learning.
Guided AbsoluteGrad: Magnitude of Gradients Matters to Explanation's Localization and Saliency
Venue: arXiv cs.CV 2025
Year: 2025

This paper proposes a new gradient-based XAI method called Guided AbsoluteGrad for saliency map explanations. We utilize both positive and negative gradient magnitudes and employ gradient variance to distinguish the important areas for noise deduction. We also introduce a novel evaluation metric named ReCover And Predict (RCAP), which considers the Localization and Visual Noise Level objectives of the explanations. We propose two propositions for these two objectives and prove the necessity of evaluating them. We evaluate Guided AbsoluteGrad with seven gradient-based XAI methods using the RCAP metric and other SOTA metrics in three case studies: (1) ImageNet dataset with ResNet50 model; (2) International Skin Imaging Collaboration (ISIC) dataset with EfficientNet model; (3) the Places365 dataset with DenseNet161 model. Our method surpasses other gradient-based approaches, showcasing the quality of enhanced saliency map explanations through gradient magnitude.
Now Let's Make It Physical: Enabling Physically Trusted Certificate Issuance for Keyless Security in CAs
Venue: arXiv cs.CR 2025
Year: 2025

The signing key protection of Certificate Authorities (CAs) remains a critical challenge in PKI. Traditional approaches struggle to eliminate the risk of key exposure due to those (un)intentional human errors. This long-standing dilemma motivates us to propose Armored Core, a novel PKI security extension using the trusted binding of Physically Unclonable Function (PUF) for CAs. PUFs leverage manufacturing variations to generate unique and random responses. Combining with XOR and hash, they can make key exposure impossible for CAs through keyless certificate issuance. In Armored Core, we design a set of PUF-based X.509v3 certificate functions for CAs to generate physically trusted "signatures" without using a digital key. Moreover, we introduce a novel PUF transparency mechanism to effectively monitor the PUF operations in CAs. We integrate Armored Core into real-world PKI systems including Let's Encrypt Pebble and Certbot. We also provide a PUF-embedded hardware prototype. The evaluation results show that Armored Core can achieve keyless certificate issuance while improving the computation performance by 4.9%~73.7%. It only incurs small communication and storage overhead (<4%).
Beyond Chain-of-Thought: A Survey of Chain-of-X Paradigms for LLMs
Venue: arXiv cs.CL 2025
Year: 2025

Chain-of-Thought (CoT) has been a widely adopted prompting method, eliciting impressive reasoning abilities of Large Language Models (LLMs). Inspired by the sequential thought structure of CoT, a number of Chain-of-X (CoX) methods have been developed to address various challenges across diverse domains and tasks involving LLMs. In this paper, we provide a comprehensive survey of Chain-of-X methods for LLMs in different contexts. Specifically, we categorize them by taxonomies of nodes, i.e., the X in CoX, and application tasks. We also discuss the findings and implications of existing CoX methods, as well as potential future directions. Our survey aims to serve as a detailed and up-to-date resource for researchers seeking to apply the idea of CoT to broader scenarios.
Retrieval and Distill: A Temporal Data Shift-Free Paradigm for Online Recommendation System
Venue: arXiv cs.IR 2025
Year: 2025

Current recommendation systems are significantly affected by a serious issue of temporal data shift, which is the inconsistency between the distribution of historical data and that of online data. Most existing models focus on utilizing updated data, overlooking the transferable, temporal data shift-free information that can be learned from shifting data. We propose the Temporal Invariance of Association theorem, which suggests that given a fixed search space, the relationship between the data and the data in the search space keeps invariant over time. Leveraging this principle, we designed a retrieval-based recommendation system framework that can train a data shift-free relevance network using shifting data, significantly enhancing the predictive performance of the original model in the recommendation system. However, retrieval-based recommendation models face substantial inference time costs when deployed online. To address this, we further designed a distill framework that can distill information from the relevance network into a parameterized module using shifting data. The distilled model can be deployed online alongside the original model, with only a minimal increase in inference time. Extensive experiments on multiple real datasets demonstrate that our framework significantly improves the performance of the original model by utilizing shifting data.
CompilerDream: Learning a Compiler World Model for General Code Optimization
Venue: arXiv cs.PL 2025
Year: 2025

Effective code optimization in compilers is crucial for computer and software engineering. The success of these optimizations primarily depends on the selection and ordering of the optimization passes applied to the code. While most compilers rely on a fixed sequence of optimization passes, current methods to find the optimal sequence either employ impractically slow search algorithms or learning methods that struggle to generalize to code unseen during training. We introduce CompilerDream, a model-based reinforcement learning approach to general code optimization. CompilerDream comprises a compiler world model that accurately simulates the intrinsic properties of optimization passes and an agent trained on this model to produce effective optimization strategies. By training on a large-scale program dataset, CompilerDream is equipped to serve as a general code optimizer across various application scenarios and source-code languages. Our extensive experiments first highlight CompilerDream's strong optimization capabilities for autotuning, where it leads the CompilerGym leaderboard. More importantly, the zero-shot generalization ability of large-scale trained compiler world model and agent, excels across diverse datasets, surpassing LLVM's built-in optimizations and other state-of-the-art methods in both settings of value prediction and end-to-end code optimization.
Learning World Models With Hierarchical Temporal Abstractions: A Probabilistic Perspective
Venue: arXiv cs.AI 2025
Year: 2025

Machines that can replicate human intelligence with type 2 reasoning capabilities should be able to reason at multiple levels of spatio-temporal abstractions and scales using internal world models. Devising formalisms to develop such internal world models, which accurately reflect the causal hierarchies inherent in the dynamics of the real world, is a critical research challenge in the domains of artificial intelligence and machine learning. This thesis identifies several limitations with the prevalent use of state space models (SSMs) as internal world models and propose two new probabilistic formalisms namely Hidden-Parameter SSMs and Multi-Time Scale SSMs to address these drawbacks. The structure of graphical models in both formalisms facilitates scalable exact probabilistic inference using belief propagation, as well as end-to-end learning via backpropagation through time. This approach permits the development of scalable, adaptive hierarchical world models capable of representing nonstationary dynamics across multiple temporal abstractions and scales. Moreover, these probabilistic formalisms integrate the concept of uncertainty in world states, thus improving the system's capacity to emulate the stochastic nature of the real world and quantify the confidence in its predictions. The thesis also discuss how these formalisms are in line with related neuroscience literature on Bayesian brain hypothesis and predicitive processing. Our experiments on various real and simulated robots demonstrate that our formalisms can match and in many cases exceed the performance of contemporary transformer variants in making long-range future predictions. We conclude the thesis by reflecting on the limitations of our current models and suggesting directions for future research.
T-Explainer: A Model-Agnostic Explainability Framework Based on Gradients
Venue: arXiv cs.LG 2025
Year: 2025

The development of machine learning applications has increased significantly in recent years, motivated by the remarkable ability of learning-powered systems to discover and generalize intricate patterns hidden in massive datasets. Modern learning models, while powerful, often exhibit a complexity level that renders them opaque black boxes, lacking transparency and hindering our understanding of their decision-making processes. Opacity challenges the practical application of machine learning, especially in critical domains requiring informed decisions. Explainable Artificial Intelligence (XAI) addresses that challenge, unraveling the complexity of black boxes by providing explanations. Feature attribution/importance XAI stands out for its ability to delineate the significance of input features in predictions. However, most attribution methods have limitations, such as instability, when divergent explanations result from similar or the same instance. This work introduces T-Explainer, a novel additive attribution explainer based on the Taylor expansion that offers desirable properties such as local accuracy and consistency. We demonstrate T-Explainer's effectiveness and stability over multiple runs in quantitative benchmark experiments against well-known attribution methods. Additionally, we provide several tools to evaluate and visualize explanations, turning T-Explainer into a comprehensive XAI framework.
Learning Actionable Counterfactual Explanations in Large State Spaces
Venue: arXiv cs.LG 2025
Year: 2025

Recourse generators provide actionable insights, often through feature-based counterfactual explanations (CFEs), to help negatively classified individuals understand how to adjust their input features to achieve a positive classification. These feature-based CFEs, which we refer to as \emph{low-level} CFEs, are overly specific (e.g., coding experience: \(4 \to 5+\) years) and often recommended in a feature space that doesn't straightforwardly align with real-world actions. To bridge this gap, we introduce three novel recourse types grounded in real-world actions: high-level continuous (\emph{hl-continuous}), high-level discrete (\emph{hl-discrete}), and high-level ID (\emph{hl-id}) CFEs. We formulate single-agent CFE generation methods, where we model the hl-discrete CFE as a solution to a weighted set cover problem and the hl-continuous CFE as a solution to an integer linear program. Since these methods require costly optimization per agent, we propose data-driven CFE generation approaches that, given instances of agents and their optimal CFEs, learn a CFE generator that quickly provides optimal CFEs for new agents. This approach, also viewed as one of learning an optimal policy in a family of large but deterministic MDPs, considers several problem formulations, including formulations in which the actions and their effects are unknown, and therefore addresses informational and computational challenges. We conduct extensive empirical evaluations using healthcare datasets (BRFSS, Foods, and NHANES) and fully-synthetic data. For negatively classified agents identified by linear or threshold-based classifiers, we compare the high-level CFE to low-level CFEs and assess the effectiveness of our network-based, data-driven approaches. Results show that the data-driven CFE generators are accurate, and resource-efficient, and high-level CFEs offer key advantages over low-level CFEs.
Optimizing Cycle Life Prediction of Lithium-ion Batteries via a Physics-Informed Model
Venue: arXiv cs.LG 2025
Year: 2025

Accurately measuring the cycle lifetime of commercial lithium-ion batteries is crucial for performance and technology development. We introduce a novel hybrid approach combining a physics-based equation with a self-attention model to predict the cycle lifetimes of commercial lithium iron phosphate graphite cells via early-cycle data. After fitting capacity loss curves to this physics-based equation, we then use a self-attention layer to reconstruct entire battery capacity loss curves. Our model exhibits comparable performances to existing models while predicting more information: the entire capacity loss curve instead of cycle life. This provides more robustness and interpretability: our model does not need to be retrained for a different notion of end-of-life and is backed by physical intuition.
A Novel Spike Transformer Network for Depth Estimation from Event Cameras via Cross-modality Knowledge Distillation
Venue: arXiv cs.CV 2025
Year: 2025

Depth estimation is a critical task in computer vision, with applications in autonomous navigation, robotics, and augmented reality. Event cameras, which encode temporal changes in light intensity as asynchronous binary spikes, offer unique advantages such as low latency, high dynamic range, and energy efficiency. However, their unconventional spiking output and the scarcity of labelled datasets pose significant challenges to traditional image-based depth estimation methods. To address these challenges, we propose a novel energy-efficient Spike-Driven Transformer Network (SDT) for depth estimation, leveraging the unique properties of spiking data. The proposed SDT introduces three key innovations: (1) a purely spike-driven transformer architecture that incorporates spike-based attention and residual mechanisms, enabling precise depth estimation with minimal energy consumption; (2) a fusion depth estimation head that combines multi-stage features for fine-grained depth prediction while ensuring computational efficiency; and (3) a cross-modality knowledge distillation framework that utilises a pre-trained vision foundation model (DINOv2) to enhance the training of the spiking network despite limited data availability.This work represents the first exploration of transformer-based spiking neural networks for depth estimation, providing a significant step forward in energy-efficient neuromorphic computing for real-world vision applications.
InspectorRAGet: An Introspection Platform for RAG Evaluation
Venue: arXiv cs.SE 2025
Year: 2025

Large Language Models (LLM) have become a popular approach for implementing Retrieval Augmented Generation (RAG) systems, and a significant amount of effort has been spent on building good models and metrics. In spite of increased recognition of the need for rigorous evaluation of RAG systems, few tools exist that go beyond the creation of model output and automatic calculation. We present InspectorRAGet, an introspection platform for performing a comprehensive analysis of the quality of RAG system output. InspectorRAGet allows the user to analyze aggregate and instance-level performance of RAG systems, using both human and algorithmic metrics as well as annotator quality. InspectorRAGet is suitable for multiple use cases and is available publicly to the community. A live instance of the platform is available at https://ibm.biz/InspectorRAGet.
Voting with Partial Orders: The Plurality and Anti-Plurality Classes
Venue: arXiv cs.GT 2025
Year: 2025

In the theory of voting, the Plurality rule for preferences that come in the form of linear orders selects the alternatives most frequently appearing in the first position of those orders, while the Anti-Plurality rule selects the alternatives least often occurring in the final position. We explore extensions of these rules to preferences that are partial orders, offering axiomatic characterisations for them.
Data Quality in Crowdsourcing and Spamming Behavior Detection
Venue: arXiv cs.HC 2025
Year: 2025

As crowdsourcing emerges as an efficient and cost-effective method for obtaining labels for machine learning datasets, it is important to assess the quality of crowd-provided data, so as to improve analysis performance and reduce biases in subsequent machine learning tasks. Given the lack of ground truth in most cases of crowdsourcing, we refer to data quality as annotators' consistency and credibility. Unlike the simple scenarios where Kappa coefficient and intraclass correlation coefficient usually can apply, online crowdsourcing requires dealing with more complex situations. We introduce a systematic method for evaluating data quality and detecting spamming threats via variance decomposition, and we classify spammers into three categories based on their different behavioral patterns. A spammer index is proposed to assess entire data consistency, and two metrics are developed to measure crowd workers' credibility by utilizing the Markov chain and generalized random effects models. Furthermore, we showcase the practicality of our techniques and their advantages by applying them on a face verification task with both simulation and real-world data collected from two crowdsourcing platforms.