OpenRaiser/Intern-Atlas huggingface dataset:
Designing Exploration Contracts
Venue: arXiv cs.GT 2025
Year: 2025

We study a natural application of contract design in the context of sequential exploration problems. In our principal-agent setting, a search task is delegated to an agent. The agent performs a sequential exploration of $n$ boxes, suffers the exploration cost for each inspected box, and selects the content (called the prize) of one inspected box as outcome. Agent and principal obtain an individual value based on the selected prize. To influence the search, the principal a-priori designs a contract with a non-negative payment to the agent for each potential prize. The goal of the principal is to maximize her expected reward, i.e., value minus payment. Interestingly, this natural contract scenario shares close relations with the Pandora's Box problem. We show how to compute optimal contracts for the principal in several scenarios. A popular and important subclass is that of linear contracts, and we show how to compute optimal linear contracts in polynomial time. For general contracts, we obtain optimal contracts under the standard assumption that the agent suffers cost but obtains value only from the transfers by the principal. More generally, for general contracts with non-zero agent values for outcomes we show how to compute an optimal contract in two cases: (1) when each box has only one prize with non-zero value for principal and agent, (2) for i.i.d. boxes with a single prize with positive value for the principal.
Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGrad
Venue: arXiv cs.LG 2025
Year: 2025

Adaptive methods are extremely popular in machine learning as they make learning rate tuning less expensive. This paper introduces a novel optimization algorithm named KATE, which presents a scale-invariant adaptation of the well-known AdaGrad algorithm. We prove the scale-invariance of KATE for the case of Generalized Linear Models. Moreover, for general smooth non-convex problems, we establish a convergence rate of $O \left(\frac{\log T}{\sqrt{T}} \right)$ for KATE, matching the best-known ones for AdaGrad and Adam. We also compare KATE to other state-of-the-art adaptive algorithms Adam and AdaGrad in numerical experiments with different problems, including complex machine learning tasks like image classification and text classification on real data. The results indicate that KATE consistently outperforms AdaGrad and matches/surpasses the performance of Adam in all considered scenarios.
DDF: A Novel Dual-Domain Image Fusion Strategy for Remote Sensing Image Semantic Segmentation with Unsupervised Domain Adaptation
Venue: arXiv cs.CV 2025
Year: 2025

Semantic segmentation of remote sensing images is a challenging and hot issue due to the large amount of unlabeled data. Unsupervised domain adaptation (UDA) has proven to be advantageous in incorporating unclassified information from the target domain. However, independently fine-tuning UDA models on the source and target domains has a limited effect on the outcome. This paper proposes a hybrid training strategy as well as a novel dual-domain image fusion strategy that effectively utilizes the original image, transformation image, and intermediate domain information. Moreover, to enhance the precision of pseudo-labels, we present a pseudo-label region-specific weight strategy. The efficacy of our approach is substantiated by extensive benchmark experiments and ablation studies conducted on the ISPRS Vaihingen and Potsdam datasets.
A General Reduction for High-Probability Analysis with General Light-Tailed Distributions
Venue: arXiv cs.LG 2025
Year: 2025

We describe a general reduction technique for analyzing learning algorithms that are subject to light-tailed (but not necessarily bounded) randomness, a scenario that is often the focus of theoretical analysis. We show that the analysis of such an algorithm can be reduced, in a black-box manner and with only a small loss in logarithmic factors, to an analysis of a simpler variant of the same algorithm that uses bounded random variables and is often easier to analyze. This approach simultaneously applies to any light-tailed randomization, including exponential, sub-Gaussian, and more general fast-decaying distributions, without needing to appeal to specialized concentration inequalities. Derivations of a generalized Azuma inequality, convergence bounds in stochastic optimization, and regret analysis in multi-armed bandits with general light-tailed randomization are provided to illustrate the technique.
LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits
Venue: arXiv cs.LG 2025
Year: 2025

We investigate the \emph{linear contextual bandit problem} with independent and identically distributed (i.i.d.) contexts. In this problem, we aim to develop a \emph{Best-of-Both-Worlds} (BoBW) algorithm with regret upper bounds in both stochastic and adversarial regimes. We develop an algorithm based on \emph{Follow-The-Regularized-Leader} (FTRL) with Tsallis entropy, referred to as the $α$-\emph{Linear-Contextual (LC)-Tsallis-INF}. We show that its regret is at most $O(\log(T))$ in the stochastic regime under the assumption that the suboptimality gap is uniformly bounded from below, and at most $O(\sqrt{T})$ in the adversarial regime. Furthermore, our regret analysis is extended to more general regimes characterized by the \emph{margin condition} with a parameter $β\in (1, \infty]$, which imposes a milder assumption on the suboptimality gap. We show that the proposed algorithm achieves $O\left(\log(T)^{\frac{1+β}{2+β}}T^{\frac{1}{2+β}}\right)$ regret under the margin condition.
F$^3$Loc: Fusion and Filtering for Floorplan Localization
Venue: arXiv cs.CV 2025
Year: 2025

In this paper we propose an efficient data-driven solution to self-localization within a floorplan. Floorplan data is readily available, long-term persistent and inherently robust to changes in the visual appearance. Our method does not require retraining per map and location or demand a large database of images of the area of interest. We propose a novel probabilistic model consisting of an observation and a novel temporal filtering module. Operating internally with an efficient ray-based representation, the observation module consists of a single and a multiview module to predict horizontal depth from images and fuses their results to benefit from advantages offered by either methodology. Our method operates on conventional consumer hardware and overcomes a common limitation of competing methods that often demand upright images. Our full system meets real-time requirements, while outperforming the state-of-the-art by a significant margin.
Diffusion-based learning of contact plans for agile locomotion
Venue: arXiv cs.RO 2025
Year: 2025

Legged robots have become capable of performing highly dynamic maneuvers in the past few years. However, agile locomotion in highly constrained environments such as stepping stones is still a challenge. In this paper, we propose a combination of model-based control, search, and learning to design efficient control policies for agile locomotion on stepping stones. In our framework, we use nonlinear model predictive control (NMPC) to generate whole-body motions for a given contact plan. To efficiently search for an optimal contact plan, we propose to use Monte Carlo tree search (MCTS). While the combination of MCTS and NMPC can quickly find a feasible plan for a given environment (a few seconds), it is not yet suitable to be used as a reactive policy. Hence, we generate a dataset for optimal goal-conditioned policy for a given scene and learn it through supervised learning. In particular, we leverage the power of diffusion models in handling multi-modality in the dataset. We test our proposed framework on a scenario where our quadruped robot Solo12 successfully jumps to different goals in a highly constrained environment.
Graph Generation Powered with LLMs for Boosting Multivariate Time-Series Representation Learning
Venue: arXiv cs.AI 2025
Year: 2025

Sourced from multiple sensors and organized chronologically, Multivariate Time-Series (MTS) data involves crucial spatial-temporal dependencies. To capture these dependencies, Graph Neural Networks (GNNs) have emerged as powerful tools. As explicit graphs are not inherent to MTS data, graph generation becomes a critical first step in adapting GNNs to this domain. However, existing approaches often rely solely on the data itself for MTS graph generation, leaving them vulnerable to biases from small training datasets. This limitation hampers their ability to construct effective graphs, undermining the accurate modeling of underlying dependencies in MTS data and reducing GNN performance in this field. To address this challenge, we propose a novel framework, K-Link, leveraging the extensive universal knowledge encoded in Large Language Models (LLMs) to reduce biases for powered MTS graph generation. To harness the knowledge within LLMs, such as physical principles, we design and extract a \textit{Knowledge-Link graph} that captures universal knowledge of sensors and their linkage. To empower MTS graph generation with the knowledge-link graph, we further introduce a graph alignment module that transfers universal knowledge from the knowledge-link graph to the graph generated from MTS data. This enhances the MTS graph quality, ensuring effective representation learning for MTS data. Extensive experiments demonstrate the efficacy of K-Link for superior performance on various MTS tasks.
CDC: A Simple Framework for Complex Data Clustering
Venue: arXiv cs.LG 2025
Year: 2025

In today's data-driven digital era, the amount as well as complexity, such as multi-view, non-Euclidean, and multi-relational, of the collected data are growing exponentially or even faster. Clustering, which unsupervisely extracts valid knowledge from data, is extremely useful in practice. However, existing methods are independently developed to handle one particular challenge at the expense of the others. In this work, we propose a simple but effective framework for complex data clustering (CDC) that can efficiently process different types of data with linear complexity. We first utilize graph filtering to fuse geometry structure and attribute information. We then reduce the complexity with high-quality anchors that are adaptively learned via a novel similarity-preserving regularizer. We illustrate the cluster-ability of our proposed method theoretically and experimentally. In particular, we deploy CDC to graph data of size 111M.
Wiki-TabNER: Integrating Named Entity Recognition into Wikipedia Tables
Venue: arXiv cs.AI 2025
Year: 2025

Interest in solving table interpretation tasks has grown over the years, yet it still relies on existing datasets that may be overly simplified. This is potentially reducing the effectiveness of the dataset for thorough evaluation and failing to accurately represent tables as they appear in the real-world. To enrich the existing benchmark datasets, we extract and annotate a new, more challenging dataset. The proposed Wiki-TabNER dataset features complex tables containing several entities per cell, with named entities labeled using DBpedia classes. This dataset is specifically designed to address named entity recognition (NER) task within tables, but it can also be used as a more challenging dataset for evaluating the entity linking task. In this paper we describe the distinguishing features of the Wiki-TabNER dataset and the labeling process. In addition, we propose a prompting framework for evaluating the new large language models on the within tables NER task. Finally, we perform qualitative analysis to gain insights into the challenges encountered by the models and to understand the limitations of the proposed~dataset.
The Ubiquitous Skiplist: A Survey of What Cannot be Skipped About the Skiplist and its Applications in Big Data Systems
Venue: arXiv cs.DB 2025
Year: 2025

Skiplists have become prevalent in systems. The main advantages of skiplists are their simplicity and ease of implementation, and the ability to support operations in the same asymptotic complexities as their tree-based counterparts. In this survey, we explore skiplists and their many variants. We highlight many scenarios about how skiplists are useful, and how they fit well in these usage scenarios. We also compare skiplists with other data structures, especially tree-based structures. Extensions to skiplists include structural modifications, as well as algorithmic enhancements and operations. We categorize the existing extensions, and summarize the skiplist variants that belong to each category. We present how data systems incorporate skiplist variants into many different application scenarios to serve various purposes. These data systems cover a wide range of applications, from data indexing to block-chain, from network algorithms to deterministic skiplists, etc. It illustrates an impactful and diverse applications of skiplists in various domains of data systems.
Optimizing Inventory Placement for a Downstream Online Matching Problem
Venue: arXiv cs.DS 2025
Year: 2025

We study the inventory placement problem of splitting $Q$ units of a single item across warehouses in advance of a downstream online matching problem that represents the dynamic fulfillment decisions of an e-commerce retailer. This is a challenging problem both theoretically, due to the computational complexity of the downstream matching problem, and practically, as the fulfillment team continuously updates its algorithm while the placement team lacks direct evaluation of placement decisions. We compare the performance of three placement procedures based on optimizing surrogate functions that have been studied and applied: Offline, Myopic, and Fluid placement. On the theory side, we show that optimizing inventory placement for the Offline surrogate leads to an $α(1-(1-1/d)^d)$-approximation for the joint placement and fulfillment problem under any demand model that admits an $α$-competitive fulfillment policy. We assume $d$ is an upper bound on how many warehouses can serve any demand location. The crux of our theoretical contribution is to use randomized rounding to derive a tight $(1-(1-1/d)^d)$-approximation for the integer programming problem of optimizing the Offline surrogate. We further show how to extend this result to a multi-SKU setting, improving upon the best known approximation of $1/2$. We use statistical learning to show that rounding after optimizing a sample-average Offline surrogate, which is necessary due to the exponentially-sized support, indeed has vanishing loss. On the experimental side, we evaluate how different combinations of placement and fulfillment procedures perform on a wide array of synthetic instances. When coupled with a good fulfillment procedure, optimizing the Offline surrogate performs best even compared to computationally-intensive simulation procedures, corroborating our theory.
Parendi: Thousand-Way Parallel RTL Simulation
Venue: arXiv cs.DC 2025
Year: 2025

Hardware development critically depends on cycle-accurate RTL simulation. However, as chip complexity increases, conventional single-threaded simulation becomes impractical due to stagnant single-core performance. Parendi is an RTL simulator that addresses this challenge by exploiting the abundant fine-grained parallelism inherent in RTL simulation and efficiently mapping it onto the massively parallel Graphcore IPU (Intelligence Processing Unit) architecture. Parendi scales up to 5888 cores on 4 Graphcore IPU sockets. It allows us to run large RTL designs up to 4$\times$ faster than the most powerful state-of-the-art x64 multicore systems. To achieve this performance, we developed new partitioning and compilation techniques and carefully quantified the synchronization, communication, and computation costs of parallel RTL simulation: The paper comprehensively analyzes these factors and details the strategies that Parendi uses to optimize them.
Graph-oriented Instruction Tuning of Large Language Models for Generic Graph Mining
Venue: arXiv cs.CL 2025
Year: 2025

Graphs with abundant attributes are essential in modeling interconnected entities and enhancing predictions across various real-world applications. Traditional Graph Neural Networks (GNNs) often require re-training for different graph tasks and datasets. Although the emergence of Large Language Models (LLMs) has introduced new paradigms in natural language processing, their potential for generic graph mining, training a single model to simultaneously handle diverse tasks and datasets, remains under-explored. To this end, our novel framework MuseGraph, seamlessly integrates the strengths of GNNs and LLMs into one foundation model for graph mining across tasks and datasets. This framework first features a compact graph description to encapsulate key graph information within language token limitations. Then, we propose a diverse instruction generation mechanism with Chain-of-Thought (CoT)-based instruction packages to distill the reasoning capabilities from advanced LLMs like GPT-4. Finally, we design a graph-aware instruction tuning strategy to facilitate mutual enhancement across multiple tasks and datasets while preventing catastrophic forgetting of LLMs' generative abilities. Our experimental results demonstrate significant improvements in five graph tasks and ten datasets, showcasing the potential of our MuseGraph in enhancing the accuracy of graph-oriented downstream tasks while improving the generation abilities of LLMs.
An In-depth Evaluation of Large Language Models in Sentence Simplification with Error-based Human Assessment
Venue: arXiv cs.CL 2025
Year: 2025

Recent studies have used both automatic metrics and human evaluations to assess the simplification abilities of LLMs. However, the suitability of existing evaluation methodologies for LLMs remains in question. First, the suitability of current automatic metrics on LLMs' simplification evaluation is still uncertain. Second, current human evaluation approaches in sentence simplification often fall into two extremes: they are either too superficial, failing to offer a clear understanding of the models' performance, or overly detailed, making the annotation process complex and prone to inconsistency, which in turn affects the evaluation's reliability. To address these problems, this study provides in-depth insights into LLMs' performance while ensuring the reliability of the evaluation. We design an error-based human annotation framework to assess the LLMs' simplification capabilities. We select both closed-source and open-source LLMs, including GPT-4, Qwen2.5-72B, and Llama-3.2-3B. We believe that these models offer a representative selection across large, medium, and small sizes of LLMs. Results show that LLMs generally generate fewer erroneous simplification outputs compared to the previous state-of-the-art. However, LLMs have their limitations, as seen in GPT-4's and Qwen2.5-72B's struggle with lexical paraphrasing. Furthermore, we conduct meta-evaluations on widely used automatic metrics using our human annotations. We find that these metrics lack sufficient sensitivity to assess the overall high-quality simplifications, particularly those generated by high-performance LLMs.
Towards Datacenter Environmental Sustainability Using Carbon Depreciation Models
Venue: arXiv cs.DC 2025
Year: 2025

Recently, the growing need for increasingly capable computing resources to be available on-demand has led to the prosperity of data centers. These data centers have led to several challenges and opportunities to address the environmental impacts from this computing resource. Conventional thinking has been concerned with minimizing energy usage of data centers to address sustainability. However, due to energy efficiency trends and renewable energy integration, recent evidence has demonstrated that embodied carbon is increasingly important and calls for improvements in data center provisioning strategies. In this paper we propose to adopt carbon depreciation models to better encourage the longer lifetime of hardware in the data center. Carbon depreciation models apply a higher proportion of embodied carbon to newly provisioned servers. This promotes provisioning fewer new servers to service jobs only with strict quality-of-service (QoS) constraints and extending lifetime of existing servers whose embodied carbon has already been mostly recovered. Along with carbon depreciation, we make the case that both embodied and operational carbon from server idle time must also be recovered during active jobs. This promotes provisioning strategies that maintain high rates of utilization. We show that prior carbon accounting strategies are counterproductive for sustainability with a greedy job scheduler that attempts to minimize carbon under QoS constraints as they price jobs as 25% cheaper on new versus old hardware. Our approach uses a greedy scheduler that prefers older hardware due to non-linear carbon depreciation promoting sustainable provisioning. Our approach reduces carbon by between 28--57% depending on assumptions for server lifetimes.
Stacking as Accelerated Gradient Descent
Venue: arXiv cs.LG 2025
Year: 2025

Stacking, a heuristic technique for training deep residual networks by progressively increasing the number of layers and initializing new layers by copying parameters from older layers, has proven quite successful in improving the efficiency of training deep neural networks. In this paper, we propose a theoretical explanation for the efficacy of stacking: viz., stacking implements a form of Nesterov's accelerated gradient descent. The theory also covers simpler models such as the additive ensembles constructed in boosting methods, and provides an explanation for a similar widely-used practical heuristic for initializing the new classifier in each round of boosting. We also prove that for certain deep linear residual networks, stacking does provide accelerated training, via a new potential function analysis of the Nesterov's accelerated gradient method which allows errors in updates. We conduct proof-of-concept experiments to validate our theory as well.
Safe Pareto Improvements for Expected Utility Maximizers in Program Games
Venue: arXiv cs.GT 2025
Year: 2025

Agents in mixed-motive coordination problems such as Chicken may fail to coordinate on a Pareto-efficient outcome. Safe Pareto improvements (SPIs) were originally proposed to mitigate miscoordination in cases where players lack probabilistic beliefs as to how their delegates will play a game; delegates are instructed to behave so as to guarantee a Pareto improvement on how they would play by default. More generally, SPIs may be defined as transformations of strategy profiles such that all players are necessarily better off under the transformed profile. In this work, we investigate the extent to which SPIs can reduce downsides of miscoordination between expected utility-maximizing agents. We consider games in which players submit computer programs that can condition their decisions on each other's code, and use this property to construct SPIs using programs capable of renegotiation. We first show that under mild conditions on players' beliefs, each player always prefers to use renegotiation. Next, we show that under similar assumptions, each player always prefers to be willing to renegotiate at least to the point at which they receive the lowest payoff they can attain in any efficient outcome. Thus subjectively optimal play guarantees players at least these payoffs, without the need for coordination on specific Pareto improvements. Lastly, we prove that renegotiation does not guarantee players any improvements on this bound.