OpenRaiser/Intern-Atlas huggingface dataset:
Data-Driven Mechanism Design using Multi-Agent Revealed Preferences
Venue: arXiv cs.GT 2025
Year: 2025

We study a sequence of independent one-shot non-cooperative games where agents play equilibria determined by a tunable mechanism. Observing only equilibrium decisions, without parametric or distributional knowledge of utilities, we aim to steer equilibria towards social optimality, and to certify when this is impossible due to the game's structure. We develop an adaptive RL framework for this mechanism design objective. First, we derive a multi-agent revealed-preference test for Pareto optimality that gives necessary and sufficient conditions for the existence of utilities under which the empirically observed mixed-strategy Nash equilibria are socially optimal. The conditions form a tractable linear program. Using this, we build an IRL step that computes the Pareto gap, the distance of observed strategies from Pareto optimality, and couple it with a policy-gradient update. We prove convergence to a mechanism that globally minimizes the Pareto gap. This yields a principled achievability test: if social optimality is attainable for the given game and observed equilibria, Algorithm 1 attains it; otherwise, the algorithm certifies unachievability while converging to the mechanism closest to social optimality. We also show a tight link between our loss and robust revealed-preference metrics, allowing algorithmic suboptimality to be interpreted through established microeconomic notions. Finally, when only finitely many i.i.d. samples from mixed strategies (partial strategy specifications) are available, we derive concentration bounds for convergence and design a distributionally robust RL procedure that attains the mechanism-design objective for the fully specified strategies.
New Complexity and Algorithmic Bounds for Minimum Consistent Subsets
Venue: arXiv cs.CG 2025
Year: 2025

In the Minimum Consistent Subset (MCS) problem, we are presented with a connected simple undirected graph $G=(V,E)$, consisting of a vertex set $V$ of size $n$ and an edge set $E$. Each vertex in $V$ is assigned a color from the set $\{1,2,\ldots, c\}$. The objective is to determine a subset $V' \subseteq V$ with minimum possible cardinality, such that for every vertex $v \in V$, at least one of its nearest neighbors in $V'$ (measured in terms of the hop distance) shares the same color as $v$. A variant of MCS is the minimum strict consistent subset (MSCS) in which instead of requiring at least one nearest neighbor of $v$, all the nearest neighbors of $v$ in $V'$ must have the same color as $v$. The decision version for MCS problem as well as for MSCS problem asks whether there exists a subset $V'$ of cardinality at most $l$ for some positive integer $l$. The MCS problem is known to be NP-complete for planar graphs. In this paper, we establish that the MCS problem for trees, when the number of colors $c$ is considered an input parameter, is NP-complete. We propose a fixed-parameter tractable (FPT) algorithm for MCS on trees running in $O(2^{6c}n^6)$ time, significantly improving the currently best-known algorithm whose running time is $O(2^{4c}n^{2c+3})$. In an effort to comprehensively understand the computational complexity of the MCS problem across different graph classes, we extend our investigation to interval graphs. We show that it remains NP-complete for interval graphs, thus enriching graph classes where MCS remains intractable. We also show that the MSCS problem is log-APX-hard on general graphs and NP-complete on planar graphs.
Characterizing the Age of Information with Multiple Coexisting Data Streams
Venue: arXiv cs.NI 2025
Year: 2025

In this paper we analyze the distribution of the Age of Information (AoI) of a tagged data stream sharing a processor with a set of other data streams. We do so in the highly general setting in which the interarrival times pertaining to the tagged stream can have any distribution, and also the service times of both the tagged stream and the background stream are generally distributed. The packet arrival times of the background process are assumed to constitute a Poisson process, which is justified by the fact that it typically is a superposition of many relatively homogeneous streams. The first main contribution is that we derive an expression for the Laplace-Stieltjes transform of the AoI in the resulting GI+M/GI+GI/1 model. Second, we use stochastic ordering techniques to identify tight stochastic bounds on the AoI, leading to an explicit lower and upper bound on the mean AoI. In addition, when approximating the tagged stream's inter-generation times through a phase-type distribution (which can be done at any precision), we present a computational algorithm for the mean AoI. As illustrated through a sequence of numerical experiments, the analysis enables us to assess the impact of background traffic on the AoI of the tagged stream. It turns out that the upper bound on the mean AoI is remarkably close to its true value, which yields an explicit expression (in terms of the model parameters) for an accurate proxy of the AoI-minimizing generation rate.
Extending Cislunar Communication Network Reach Using Reconfigurable Intelligent Surfaces
Venue: arXiv cs.ET 2025
Year: 2025

This study introduces a novel approach to enhance communication networks in the Cislunar space by leveraging Reconfigurable Intelligent Surfaces (RIS). Using the ability of RIS to dynamically control electromagnetic waves, this paper tackles the challenges of signal attenuation, directivity, and divergence in Cislunar missions, primarily caused by immense distances and that Earth-based station transmitters do not always face the Moon. A new optimization problem is formulated, whose objective is to maximize the received signal-to-noise ratio (SNR) for Earth-to-Moon communications. We derive a closed-form solution to the problem of determining the optimal RIS phase shift configuration based on the effective area of the RIS. Through extensive simulations, this paper demonstrates how optimal adjustments in RIS phase shifts can significantly enhance signal integrity, hinting at the substantial potential of RIS technology to revolutionize long-distance Cislunar communication.
On the Fourier analysis in the SO(3) space : EquiLoPO Network
Venue: arXiv cs.CV 2025
Year: 2025

Analyzing volumetric data with rotational invariance or equivariance is an active topic in current research. Existing deep-learning approaches utilize either group convolutional networks limited to discrete rotations or steerable convolutional networks with constrained filter structures. This work proposes a novel equivariant neural network architecture that achieves analytical Equivariance to Local Pattern Orientation on the continuous SO(3) group while allowing unconstrained trainable filters - EquiLoPO Network. Our key innovations are a group convolutional operation leveraging irreducible representations as the Fourier basis and a local activation function in the SO(3) space that provides a well-defined mapping from input to output functions, preserving equivariance. By integrating these operations into a ResNet-style architecture, we propose a model that overcomes the limitations of prior methods. A comprehensive evaluation on diverse 3D medical imaging datasets from MedMNIST3D demonstrates the effectiveness of our approach, which consistently outperforms state of the art. This work suggests the benefits of true rotational equivariance on SO(3) and flexible unconstrained filters enabled by the local activation function, providing a flexible framework for equivariant deep learning on volumetric data with potential applications across domains. Our code is publicly available at https://gricad-gitlab.univ-grenoble-alpes.fr/GruLab/ILPO/-/tree/main/EquiLoPO.
Tractable Conjunctive Queries over Static and Dynamic Relations
Venue: arXiv cs.DB 2025
Year: 2025

We investigate the evaluation of conjunctive queries over static and dynamic relations. While static relations are given as input and do not change, dynamic relations are subject to inserts and deletes. We characterise syntactically three classes of queries that admit constant update time and constant enumeration delay. We call such queries tractable. Depending on the class, the preprocessing time is linear, polynomial, or exponential (under data complexity, so the query size is constant). To decide whether a query is tractable, it does not suffice to analyse separately the sub-queries over the static relations and over the dynamic relations, respectively. Instead, we need to take the interaction between the static and the dynamic relations into account. Even when the sub-query over the dynamic relations is not tractable, the overall query can become tractable if the dynamic relations are sufficiently constrained by the static ones.
Learning Syntax Without Planting Trees: Understanding Hierarchical Generalization in Transformers
Venue: arXiv cs.CL 2025
Year: 2025

Transformers trained on natural language data have been shown to learn its hierarchical structure and generalize to sentences with unseen syntactic structures without explicitly encoding any structural bias. In this work, we investigate sources of inductive bias in transformer models and their training that could cause such generalization behavior to emerge. We extensively experiment with transformer models trained on multiple synthetic datasets and with different training objectives and show that while other objectives e.g. sequence-to-sequence modeling, prefix language modeling, often failed to lead to hierarchical generalization, models trained with the language modeling objective consistently learned to generalize hierarchically. We then conduct pruning experiments to study how transformers trained with the language modeling objective encode hierarchical structure. When pruned, we find joint existence of subnetworks within the model with different generalization behaviors (subnetworks corresponding to hierarchical structure and linear order). Finally, we take a Bayesian perspective to further uncover transformers' preference for hierarchical generalization: We establish a correlation between whether transformers generalize hierarchically on a dataset and whether the simplest explanation of that dataset is provided by a hierarchical grammar compared to regular grammars exhibiting linear generalization.
List Items One by One: A New Data Source and Learning Paradigm for Multimodal LLMs
Venue: arXiv cs.CV 2025
Year: 2025

Set-of-Mark (SoM) Prompting unleashes the visual grounding capability of GPT-4V, by enabling the model to associate visual objects with tags inserted on the image. These tags, marked with alphanumerics, can be indexed via text tokens for easy reference. Despite the extraordinary performance from GPT-4V, we observe that other Multimodal Large Language Models (MLLMs) struggle to understand these visual tags. To promote the learning of SoM prompting for open-source models, we propose a new learning paradigm: "list items one by one," which asks the model to enumerate and describe all visual tags placed on the image following the alphanumeric orders of tags. By integrating our curated dataset with other visual instruction tuning datasets, we are able to equip existing MLLMs with the SoM prompting ability. Furthermore, we evaluate our finetuned SoM models on five MLLM benchmarks. We find that this new dataset, even in a relatively small size (10k-30k images with tags), significantly enhances visual reasoning capabilities and reduces hallucinations for MLLMs. Perhaps surprisingly, these improvements persist even when the visual tags are omitted from input images during inference. This suggests the potential of "list items one by one" as a new paradigm for training MLLMs, which strengthens the object-text alignment through the use of visual tags in the training stage. Finally, we conduct analyses by probing trained models to understand the working mechanism of SoM. Our code and data are available at \url{https://github.com/zzxslp/SoM-LLaVA}.
Derandomization with Pseudorandomness
Venue: arXiv cs.LO 2025
Year: 2025

Derandomization techniques are often used within advanced randomized algorithms. In particular, pseudorandom objects, such as hash families and expander graphs, are key components of such algorithms, but their verification presents a challenge. This work shows how such algorithms can be expressed and verified in Isabelle and presents a pseudorandom objects library that abstracts away the deep algebraic/analytic results involved. Moreover, it presents examples that show how the library eases and enables the verification of advanced randomized algorithms. Highlighting the value of this framework is that it was recently used to verify the space-optimal distinct elements algorithm by Blasiok from 2018, which relies on the combination of many derandomization techniques to achieve its optimality.
RUMOR: Reinforcement learning for Understanding a Model of the Real World for Navigation in Dynamic Environments
Venue: arXiv cs.RO 2025
Year: 2025

Autonomous navigation in dynamic environments is a complex but essential task for autonomous robots, with recent deep reinforcement learning approaches showing promising results. However, the complexity of the real world makes it infeasible to train agents in every possible scenario configuration. Moreover, existing methods typically overlook factors such as robot kinodynamic constraints, or assume perfect knowledge of the environment. In this work, we present RUMOR, a novel planner for differential-drive robots that uses deep reinforcement learning to navigate in highly dynamic environments. Unlike other end-to-end DRL planners, it uses a descriptive robocentric velocity space model to extract the dynamic environment information, enhancing training effectiveness and scenario interpretation. Additionally, we propose an action space that inherently considers robot kinodynamics and train it in a simulator that reproduces the real world problematic aspects, reducing the gap between the reality and simulation. We extensively compare RUMOR with other state-of-the-art approaches, demonstrating a better performance, and provide a detailed analysis of the results. Finally, we validate RUMOR's performance in real-world settings by deploying it on a ground robot. Our experiments, conducted in crowded scenarios and unseen environments, confirm the algorithm's robustness and transferability.
Online Data Augmentation for Forecasting with Deep Learning
Venue: arXiv cs.LG 2025
Year: 2025

Deep learning approaches are increasingly used to tackle forecasting tasks involving datasets with multiple univariate time series. A key factor in the successful application of these methods is a large enough training sample size, which is not always available. Synthetic data generation techniques can be applied in these scenarios to augment the dataset. Data augmentation is typically applied offline before training a model. However, when training with mini-batches, some batches may contain a disproportionate number of synthetic samples that do not align well with the original data characteristics. This work introduces an online data augmentation framework that generates synthetic samples during the training of neural networks. By creating synthetic samples for each batch alongside their original counterparts, we maintain a balanced representation between real and synthetic data throughout the training process. This approach fits naturally with the iterative nature of neural network training and eliminates the need to store large augmented datasets. We validated the proposed framework using 3797 time series from 6 benchmark datasets, three neural architectures, and seven synthetic data generation techniques. The experiments suggest that online data augmentation leads to better forecasting performance compared to offline data augmentation or no augmentation approaches. The framework and experiments are publicly available.
Sparse Reconstruction of Optical Doppler Tomography with Alternative State Space Model and Attention
Venue: arXiv cs.CV 2025
Year: 2025

Optical coherence Doppler tomography (ODT) is an emerging blood flow imaging technique. The fundamental unit of ODT is the 1D depth-resolved trace named raw A-scans (or A-line). A 2D ODT image (B-scan) is formed by reconstructing a cross-sectional flow image via Doppler phase-subtraction of raw A-scans along B-line. To obtain a high-fidelity B-scan, densely sampled A-scans are required currently, leading to prolonged scanning time and increased storage demands. Addressing this issue, we propose a novel sparse ODT reconstruction framework with an Alternative State Space Attention Network (ASSAN) that effectively reduces raw A-scans needed. Inspired by the distinct distributions of information along A-line and B-line, ASSAN applies 1D State Space Model (SSM) to each A-line to learn the intra-A-scan representation, while using 1D gated self-attention along B-line to capture the inter-A-scan features. In addition, an effective feedforward network based on sequential 1D convolutions along different axes is employed to enhance the local feature. In validation experiments on real animal data, ASSAN shows clear effectiveness in the reconstruction in comparison with state-of-the-art reconstruction methods.
UnifiedRL: A Reinforcement Learning Algorithm Tailored for Multi-Task Fusion in Large-Scale Recommender Systems
Venue: arXiv cs.IR 2025
Year: 2025

As the last pivotal stage of Recommender System (RS), Multi-Task Fusion (MTF) is responsible for combining multiple scores outputted by Multi-Task Learning (MTL) model into a final score to maximize user satisfaction. Recently, to optimize long-term user satisfaction, Reinforcement Learning (RL) is used for MTF in RSs. However, the existing offline RL algorithms used for MTF have the following severe problems: a) To avoid Out-of-Distribution (OOD), their constraints are overly strict, which seriously damage performance; b) They are unaware of the exploration policy used to collect training data, only suboptimal policy can be learned; c) Their exploration policies are inefficient and hurt user experience. To solve the above problems, we propose an innovative method called UnifiedRL tailored for MTF in large-scale RSs. UnifiedRL seamlessly integrates offline RL model with its custom exploration policy to relax overly strict constraints, which is different from existing RL-MTF methods and significantly improves performance. In addition, compared to existing exploration policies, UnifiedRL's custom exploration policy is highly efficient, enabling frequent online exploration and offline training iterations, which further improves performance. Extensive offline and online experiments are conducted in a large-scale RS. The results demonstrate that UnifiedRL outperforms other existing MTF methods remarkably, achieving a +4.64% increase in user valid consumption and a +1.74% increase in user duration time. To the best of our knowledge, UnifiedRL is the first RL algorithm tailored for MTF in RSs and has been successfully deployed in multiple large-scale RSs since June 2023, yielding significant benefits.
From Languages to Geographies: Towards Evaluating Cultural Bias in Hate Speech Datasets
Venue: arXiv cs.CL 2025
Year: 2025

Perceptions of hate can vary greatly across cultural contexts. Hate speech (HS) datasets, however, have traditionally been developed by language. This hides potential cultural biases, as one language may be spoken in different countries home to different cultures. In this work, we evaluate cultural bias in HS datasets by leveraging two interrelated cultural proxies: language and geography. We conduct a systematic survey of HS datasets in eight languages and confirm past findings on their English-language bias, but also show that this bias has been steadily decreasing in the past few years. For three geographically-widespread languages -- English, Arabic and Spanish -- we then leverage geographical metadata from tweets to approximate geo-cultural contexts by pairing language and country information. We find that HS datasets for these languages exhibit a strong geo-cultural bias, largely overrepresenting a handful of countries (e.g., US and UK for English) relative to their prominence in both the broader social media population and the general population speaking these languages. Based on these findings, we formulate recommendations for the creation of future HS datasets.
Graph Attention Reinforcement Learning for Multicast Routing and Age-Optimal Scheduling
Venue: arXiv cs.NI 2025
Year: 2025

Multicast routing is essential for real-time group applications, such as video streaming, virtual reality, and metaverse platforms, where the Age of Information (AoI) acts as a crucial metric to assess information timeliness. This paper studies dynamic multicast networks with the objective of minimizing the expected average Age of Information (AoI) by jointly optimizing multicast routing and scheduling. The main challenges stem from the intricate coupling between routing and scheduling decisions, the inherent complexity of multicast operations, and the graph representation. We first decompose the original problem into two subtasks amenable to hierarchical reinforcement learning (RL) methods. We propose the first RL framework to address the multicast routing problem, also known as the Steiner Tree problem, by incorporating graph embedding and the successive addition of nodes and links. For graph embedding, we propose the Normalized Graph Attention mechanism (NGAT) framework with a proven contraction mapping property, enabling effective graph information capture and superior generalization within the hierarchical RL framework. We validate our framework through experiments on four datasets, including the real-world AS-733 dataset. The results demonstrate that our proposed scheme can be up to 9.85 times more computationally efficient than traditional multicast routing algorithms, achieving approximation ratios of 1.1-1.3 that are not only comparable to state-of-the-art (SOTA) methods but also highlight its superior generalization capabilities, performing effectively on unseen and more complex tasks. Additionally, our age-optimal TGMS algorithm reduces the average weighted Age of Information (AoI) by 25.6% and the weighted peak age by 29.2% under low-energy scenarios.
Learning Fairer Representations with FairVIC
Venue: arXiv cs.LG 2025
Year: 2025

Mitigating bias in automated decision-making systems, particularly in deep learning models, is a critical challenge due to nuanced definitions of fairness, dataset-specific biases, and the inherent trade-off between fairness and accuracy. To address these issues, we introduce FairVIC, an innovative approach that enhances fairness in neural networks by integrating variance, invariance, and covariance terms into the loss function during training. Unlike methods that rely on predefined fairness criteria, FairVIC abstracts fairness concepts to minimise dependency on protected characteristics. We evaluate FairVIC against comparable bias mitigation techniques on benchmark datasets, considering both group and individual fairness, and conduct an ablation study on the accuracy-fairness trade-off. FairVIC demonstrates significant improvements ($\approx70\%$) in fairness across all tested metrics without compromising accuracy, thus offering a robust, generalisable solution for fair deep learning across diverse tasks and datasets.