OpenRaiser/Intern-Atlas huggingface dataset:
Polynomial definability in constraint languages with few subpowers
Venue: arXiv cs.LO 2026
Year: 2026

A first-order formula is called primitive positive (pp) if it only admits the use of existential quantifiers and conjunction. Pp-formulas are a central concept in (fixed-template) constraint satisfaction since CSP($Γ$) can be viewed as the problem of deciding the primitive positive theory of $Γ$, and pp-definability captures gadget reductions between CSPs. An important class of tractable constraint languages $Γ$ is characterized by having few subpowers, that is, the number of $n$-ary relations pp-definable from $Γ$ is bounded by $2^{p(n)}$ for some polynomial $p(n)$. In this paper we study a restriction of this property, stating that every pp-definable relation is definable by a pp-formula of polynomial length. We conjecture that the existence of such short definitions is actually equivalent to $Γ$ having few subpowers, and verify this conjecture for a large subclass that, in particular, includes all constraint languages on three-element domains. We furthermore discuss how our conjecture imposes an upper complexity bound of co-NP on the subpower membership problem of algebras with few subpowers.
Kugelblitz: Executable, Cost-Aware Design-Space Exploration for Programmable Packet Pipelines
Venue: arXiv cs.NI 2026
Year: 2026

Programmable packet-processing pipelines are a core building block of modern SmartNICs and switches, yet their design requires navigating intertwined trade-offs among program feasibility, hardware cost, and system-level performance. Existing approaches rely on proxy metrics such as stage or ALU count, which often mispredict capability and end-to-end behavior. We present Kugelblitz, a framework for executable, cost-aware design-space exploration of programmable packet pipelines. Kugelblitz decouples packet-processing programs from pipeline architectures and uses compiler-based feasibility checking to prune designs that cannot support target workloads. For feasible architectures, Kugelblitz automatically generates synthesizable RTL, enabling synthesis-backed area and timing estimation and cycle-accurate full-system evaluation with real application workloads. Using representative programs including NAT, firewalling, and an in-network key-value cache, we show that proxy metrics substantially overestimate capability, that performance rankings change under system-level evaluation, and that the cost of supporting richer workloads is highly non-linear.
Optimizing Sampling Patterns for Compressed Sensing MRI with Diffusion Generative Models
Venue: arXiv cs.LG 2026
Year: 2026

Magnetic resonance imaging (MRI) is a powerful medical imaging modality, but long acquisition times limit throughput, patient comfort, and clinical accessibility. Diffusion-based generative models serve as strong image priors for reducing scan-time with accelerated MRI reconstruction and offer robustness across variations in the acquisition model. However, most existing diffusion-based approaches do not exploit the unique ability in MRI to jointly design both the sampling pattern and the reconstruction method. While prior learning-based approaches have optimized sampling patterns for end-to-end unrolled networks, analogous methods for diffusion-based reconstruction have not been established due to the computational burden of posterior sampling. In this work, we propose a method to optimize k-space sampling patterns for accelerated multi-coil MRI reconstruction using diffusion models as priors. We introduce a training objective based on a single-step posterior mean estimate that avoids backpropagation through an expensive iterative reconstruction process. Then we present a greedy strategy for learning Cartesian sampling patterns that selects informative k-space locations using gradient information from a pre-trained diffusion model while enforcing spatial diversity among samples. Experimental results across multiple anatomies and acceleration factors demonstrate that diffusion models using the optimized sampling patterns achieve higher-quality reconstructions in comparison to using fixed and learned baseline patterns.
SQL2Circuits: Estimating Cardinalities, Execution Times, and Costs for SQL Queries with Quantum Natural Language Processing
Venue: arXiv cs.DB 2026
Year: 2026

Recent advances in quantum computing have led to progress in exploring quantum applications across diverse fields, including databases and data management. This work presents a quantum machine learning model that tackles the challenge of estimating metrics, such as cardinalities, execution times, and costs, for SQL queries in relational databases. Precise estimations are crucial for the query optimizer to optimize query processing in relational databases efficiently. Our proposed quantum machine learning model consists of a novel query encoding mechanism, which maps SQL queries into high-dimensional Hilbert spaces using grammatical representations of the queries. The encoding mechanism translates SQL queries into parameterized quantum circuits, forming the core of the quantum machine learning model. The parameters in this model are tuned using standard quantum machine learning techniques. This encoding was first developed in quantum natural language processing (QNLP), and this work demonstrates its natural application in database optimization. Because the encoding mechanism is mathematically robust, the quantum machine learning model is also explainable, allowing us to draw a one-to-one correspondence between the elements in SQL queries and the model's parameters. The method is also scalable because it consists of multiple circuits, and we train and evaluate the model with hundreds of queries. Compared to previous research, our model achieves high accuracy, supporting the results obtained in the original QNLP research. We extend the previous QNLP work by adding 4-class and 8-class classification tasks and comparing the cardinality estimation results with those from state-of-the-art databases. We theoretically analyze the quantum machine learning model by calculating its expressibility and entangling capabilities.
Near-Optimal Partially Observable Reinforcement Learning with Partial Online State Information
Venue: arXiv cs.LG 2026
Year: 2026

Partially observable Markov decision processes (POMDPs) are a general framework for sequential decision-making under latent state uncertainty, yet learning in POMDPs is intractable in the worst case. Motivated by sensing and probing constraints in practice, we study how much online state information (OSI) is sufficient to enable efficient learning guarantees. We formalize a model in which the learner can query only partial OSI (POSI) during interaction. We first prove an information-theoretic hardness result showing that, for general POMDPs, achieving an $ε$-optimal policy can require sample complexity that is exponential unless full OSI is available. We then identify two structured subclasses that remain learnable under POSI and propose corresponding algorithms with provably efficient performance guarantees. In particular, we establish regret upper bounds with $\tilde{O}(\sqrt{K})$ dependence on the number of episodes $K$, together with complementary lower bounds, thereby delineating when POSI suffices for efficient reinforcement learning. Our results highlight a principled separation between intractable and tractable regimes under incomplete online state access and provide new tools for jointly optimizing POSI queries and learning control actions.
Utility Theory based Cognitive Modeling in the Application of Robotics: A Survey
Venue: arXiv cs.RO 2026
Year: 2026

Cognitive modeling, which explores the essence of cognition, including motivation, emotion, and perception, has been widely applied in the artificial intelligence (AI) agent domains, such as robotics. From the computational perspective, various cognitive functionalities have been developed through utility theory to provide a detailed and process-based understanding for specifying corresponding computational models of representations, mechanisms, and processes. Especially for decision-making and learning in multi-agent/robot systems (MAS/MRS), a suitable cognitive model can guide agents in choosing reasonable strategies to achieve their current needs and learning to cooperate and organize their behaviors, optimizing the system's utility, building stable and reliable relationships, and guaranteeing each group member's sustainable development, similar to the human society. This survey examines existing robotic systems for developmental cognitive models in the context of utility theory. We discuss the evolution of cognitive modeling in robotics from behavior-based robotics (BBR) and cognitive architectures to the properties of value systems in robots, such as the studies on motivations as artificial value systems, and the utility theory based cognitive modeling for generating and updating strategies in robotic interactions. Then, we examine the extent to which existing value systems support the application of robotics from an AI agent cognitive modeling perspective, including single-agent and multi-agent systems, trust among agents, and human-robot interaction. Finally, we survey the existing literature of current value systems in relevant fields and propose several promising research directions, along with some open problems that we deem necessary for further investigation.
Recurrent Action Transformer with Memory
Venue: arXiv cs.LG 2026
Year: 2026

Transformers have become increasingly popular in offline reinforcement learning (RL) due to their ability to treat agent trajectories as sequences, reframing policy learning as a sequence modeling task. However, in partially observable environments (POMDPs), effective decision-making depends on retaining information about past events -- something that standard transformers struggle with due to the quadratic complexity of self-attention, which limits their context length. One solution to this problem is to extend transformers with memory mechanisms. We propose the Recurrent Action Transformer with Memory (RATE), a novel transformer-based architecture for offline RL that incorporates a recurrent memory mechanism designed to regulate information retention. We evaluate RATE across a diverse set of environments: memory-intensive tasks (ViZDoom-Two-Colors, T-Maze, Memory Maze, Minigrid-Memory, and POPGym), as well as standard Atari and MuJoCo benchmarks. Our comprehensive experiments demonstrate that RATE significantly improves performance in memory-dependent settings while remaining competitive on standard tasks across a broad range of baselines. These findings underscore the pivotal role of integrated memory mechanisms in offline RL and establish RATE as a unified, high-capacity architecture for effective decision-making over extended horizons. Code: https://sites.google.com/view/rate-model/.
Benchmarking the Influence of Pre-training on Explanation Performance in MR Image Classification
Venue: arXiv cs.CV 2026
Year: 2026

Convolutional Neural Networks (CNNs) are frequently and successfully used in medical prediction tasks. They are often used in combination with transfer learning, leading to improved performance when training data for the task are scarce. The resulting models are highly complex and typically do not provide any insight into their predictive mechanisms, motivating the field of "explainable" artificial intelligence (XAI). However, previous studies have rarely quantitatively evaluated the "explanation performance" of XAI methods against ground-truth data, and transfer learning and its influence on objective measures of explanation performance has not been investigated. Here, we propose a benchmark dataset that allows for quantifying explanation performance in a realistic magnetic resonance imaging (MRI) classification task. We employ this benchmark to understand the influence of transfer learning on the quality of explanations. Experimental results show that popular XAI methods applied to the same underlying model differ vastly in performance, even when considering only correctly classified examples. We further observe that explanation performance strongly depends on the task used for pre-training and the number of CNN layers pre-trained. These results hold after correcting for a substantial correlation between explanation and classification performance.
Positional Embedding-Aware Activations
Venue: arXiv cs.CV 2026
Year: 2026

We present a neural network architecture designed to naturally learn a positional embedding and overcome the spectral bias towards lower frequencies faced by conventional activation functions. Our proposed architecture, SPDER, is a simple MLP that uses an activation function composed of a sinusoidal multiplied by a sublinear function, called the damping function. The sinusoidal enables the network to automatically learn the positional embedding of an input coordinate while the damping passes on the actual coordinate value by preventing it from being projected down to within a finite range of values. Our results indicate that SPDERs speed up training by 10x and converge to losses 1,500-50,000x lower than that of the state-of-the-art for image representation. SPDER is also state-of-the-art in audio representation. The superior representation capability allows SPDER to also excel on multiple downstream tasks such as image super-resolution and video frame interpolation. We provide intuition as to why SPDER significantly improves fitting compared to that of other INR methods while requiring no hyperparameter tuning or preprocessing.
Topological Inductive Bias fosters Multiple Instance Learning in Data-Scarce Scenarios
Venue: arXiv cs.LG 2026
Year: 2026

Multiple instance learning (MIL) is a framework for weakly supervised classification, where labels are assigned to sets of instances, i.e., bags, rather than to individual data points. This paradigm has proven effective in tasks where fine-grained annotations are unavailable or costly to obtain. However, the effectiveness of MIL drops sharply when training data are scarce, such as for rare disease classification. To address this challenge, we propose incorporating topological inductive biases into the data representation space within the MIL framework. This bias introduces a topology-preserving constraint that encourages the instance encoder to maintain the topological structure of the instance distribution within each bag when mapping them to MIL latent space. As a result, our Topology Guided MIL (TG-MIL) method enhances the performance and generalizability of MIL classifiers across different aggregation functions, especially under scarce-data regimes. Our evaluations show average performance improvements of 15.3% for synthetic MIL datasets, 2.8% for MIL benchmarks, and 5.5% for rare anemia classification compared to current state-of-the-art MIL models, where only 17-120 samples per class are available. We make our code publicly available.
Approximately: Independence Implies Vertex Cover
Venue: arXiv cs.CG 2026
Year: 2026

$\newcommand{\eps}{\varepsilon}$ We observe that a $(1-\eps)$-approximation algorithm to Independent Set, that works for any induced subgraph of the input graph, can be used, via a polynomial time reduction, to provide a $(1+\eps)$-approximation to Vertex Cover. This basic observation was made before, see [BHR11]. As a consequence, we get a PTAS for VC for unweighted pseudo-disks, QQPTAS for VC for unweighted axis-aligned rectangles in the plane, and QPTAS for MWVC for weighted polygons in the plane. To the best of our knowledge all these results are new.
Testing Graph Properties with the Container Method
Venue: arXiv cs.DS 2026
Year: 2026

We establish nearly optimal sample complexity bounds for testing the $ρ$-clique property in the dense graph model. Specifically, we show that it is possible to distinguish graphs on $n$ vertices that have a $ρn$-clique from graphs for which at least $εn^2$ edges must be added to form a $ρn$-clique by sampling and inspecting a random subgraph on only $\tilde{O}(ρ^3/ε^2)$ vertices. We also establish new sample complexity bounds for $ε$-testing $k$-colorability. In this case, we show that a sampled subgraph on $\tilde{O}(k/ε)$ vertices suffices to distinguish $k$-colorable graphs from those for which any $k$-coloring of the vertices causes at least $εn^2$ edges to be monochromatic. The new bounds for testing the $ρ$-clique and $k$-colorability properties are both obtained via new extensions of the graph container method. This method has been an effective tool for tackling various problems in graph theory and combinatorics. Our results demonstrate that it is also a powerful tool for the analysis of property testing algorithms.
Robustness Over Time: Understanding Adversarial Examples' Effectiveness on Longitudinal Versions of Large Language Models
Venue: arXiv cs.CR 2026
Year: 2026

Large Language Models (LLMs) undergo continuous updates to improve user experience. However, prior research on the security and safety implications of LLMs has primarily focused on their specific versions, overlooking the impact of successive LLM updates. This prompts the need for a holistic understanding of the risks in these different versions of LLMs. To fill this gap, in this paper, we conduct a longitudinal study to examine the adversarial robustness -- specifically misclassification, jailbreak, and hallucination -- of three prominent LLM families: GPT, Llama, and Qwen. Our study reveals that LLM updates do not consistently improve adversarial robustness as expected. For instance, a later version of GPT-3.5 degrades regarding misclassification and hallucination despite its improved resilience against jailbreaks. GPT-4 and GPT-4o demonstrate (incrementally) higher robustness overall. Larger Llama and Qwen models do not uniformly exhibit improved robustness across all three aspects studied. In addition, larger model sizes do not necessarily yield improved robustness. Minor updates lacking substantial robustness improvements can exacerbate existing issues rather than resolve them. We hope our study can offer valuable insights into navigating model updates and informed decisions in model development and usage.
Introducing Divergence for Infinite Probabilistic Models
Venue: arXiv cs.FL 2026
Year: 2026

Computing the reachability probability in infinite state probabilistic models has been the topic of numerous works. Here we introduce a new property called \emph{divergence} that when satisfied allows to compute reachability probabilities up to an arbitrary precision. One of the main interests of divergence is that this computation does not require the reachability problem, i.e., the possibility to reach target states from an initial state in a given model, to be decidable. Then we study the decidability of divergence for random walks and the probabilistic versions of Petri nets where the weights associated with transitions may also depend on the current state. This should be contrasted with most of the existing works that assume weights independent of the state. Such an extended framework is motivated by the modeling of real case studies. Moreover, we exhibit some subclasses of channel systems and pushdown automata that are divergent by construction, particularly suited for specifying open distributed systems and networks prone to performance collapsing where probabilities related to service requirements are needed.
Multi-event Video-Text Retrieval
Venue: arXiv cs.CV 2026
Year: 2026

Video-Text Retrieval (VTR) is a crucial multi-modal task in an era of massive video-text data on the Internet. A plethora of work characterized by using a two-stream Vision-Language model architecture that learns a joint representation of video-text pairs has become a prominent approach for the VTR task. However, these models operate under the assumption of bijective video-text correspondences and neglect a more practical scenario where video content usually encompasses multiple events, while texts like user queries or webpage metadata tend to be specific and correspond to single events. This establishes a gap between the previous training objective and real-world applications, leading to the potential performance degradation of earlier models during inference. In this study, we introduce the Multi-event Video-Text Retrieval (MeVTR) task, addressing scenarios in which each video contains multiple different events, as a niche scenario of the conventional Video-Text Retrieval Task. We present a simple model, Me-Retriever, which incorporates key event video representation and a new MeVTR loss for the MeVTR task. Comprehensive experiments show that this straightforward framework outperforms other models in the Video-to-Text and Text-to-Video tasks, effectively establishing a robust baseline for the MeVTR task. We believe this work serves as a strong foundation for future studies. Code is available at https://github.com/gengyuanmax/MeVTR.
Low-redundancy Distillation for Continual Learning
Venue: arXiv cs.LG 2026
Year: 2026

Continual learning (CL) aims to learn new tasks without erasing previous knowledge. However, current CL methods primarily emphasize improving accuracy while often neglecting training efficiency, which consequently restricts their practical application. Drawing inspiration from the brain's contextual gating mechanism, which selectively filters neural information and continuously updates past memories, we propose Low-redundancy Distillation (LoRD), a novel CL method that enhances model performance while maintaining training efficiency. This is achieved by eliminating redundancy in three aspects of CL: student model redundancy, teacher model redundancy, and rehearsal sample redundancy. By compressing the learnable parameters of the student model and pruning the teacher model, LoRD facilitates the retention and optimization of prior knowledge, effectively decoupling task-specific knowledge without manually assigning isolated parameters for each task. Furthermore, we optimize the selection of rehearsal samples and refine rehearsal frequency to improve training efficiency. Through a meticulous design of distillation and rehearsal strategies, LoRD effectively balances training efficiency and model precision. Extensive experimentation across various benchmark datasets and environments demonstrates LoRD's superiority, achieving the highest accuracy with the lowest training FLOPs.
Comparing Time-Series Analysis Approaches Utilized in Research Papers to Forecast COVID-19 Cases in Africa: A Literature Review
Venue: arXiv cs.LG 2026
Year: 2026

This literature review aimed to compare various time-series analysis approaches utilized in forecasting COVID-19 cases in Africa. The study involved a methodical search for English-language research papers published between January 2020 and July 2023, focusing specifically on papers that utilized time-series analysis approaches on COVID-19 datasets in Africa. A variety of databases including PubMed, Google Scholar, Scopus, and Web of Science were utilized for this process. The research papers underwent an evaluation process to extract relevant information regarding the implementation and performance of the time-series analysis models. The study highlighted the different methodologies employed, evaluating their effectiveness and limitations in forecasting the spread of the virus. The result of this review could contribute deeper insights into the field, and future research should consider these insights to improve time series analysis models and explore the integration of different approaches for enhanced public health decision-making.