Logic in Computer Science · Cross-listed from math.LO
Medvedev logic is undecidable
Rodrigo Nicolau Almeida and Søren Brinck Knudstorp
We show that Medvedev's logic of finite problems, a well-known superintuitionistic logic, is undecidable. The key method is a reduction from the periodic tiling problem to non-theoremhood in Medvedev's logic. This settles a longstanding open problem. Using similar techniques, but reducing instead to the ordinary tiling problem, we likewise obtain undecidability of Skvortsov's logic of infinite problems, and the fact that the two logics are distinct – in fact, they are separated by any aperiodic tiling of the plane. Due to the fact that Medvedev's logic figures in so many different areas, these results have implications for several fields – for example, the study of schematic fragments of logics such as propositional dependence logic, or the study of internal logics of toposes. The core idea and technical work of the undecidability proof were obtained using ChatGPT Sol 5.6, and formally verified in Lean by Claude Opus 5. A detailed methodology section outlines how such results were obtained.
Read the full abstract ▾
Artificial Intelligence
ZGCM-1: A Fully Open and Extremely Efficient Foundation Model for Math and Agentic Search
Jiyan He, Guang Liang, Hao Liu et al. (+19 more)
In this work, we present ZGCM-1, a fully open 7B dense foundation model trained from scratch with extreme data, system, and algorithmic efficiency. ZGCM-1 is founded on a core premise: compact models cannot passively memorize the open web, but can overcome parametric capacity limits by coupling deliberate internal thinking with active external tool use. To support this paradigm across a 256K context, we develop an end-to-end, high-efficiency open training recipe: Architecture & System Co-design: interleaved gated sliding-window and full
attention, and a stable FP8
Muon optimizer; Progressive Curriculum & MDP Mid-Training: context scaling across 16K, 64K, and 256K, and the reformulation of interaction traces into Markov Decision Processes. Furthermore, we establish an AI-native R&D workflow where
agent swarms autonomously manage cluster operations, data curation, and rapid diagnostic evaluation. Extensive evaluations show that ZGCM-1-7B is competitive across 7B model family on general
benchmarks. On several challenging mathematical
reasoning and agentic search suites, it remains competitive with frontier models orders of magnitude larger, such as Qwen3-235B-A22B and GLM-5.1. We also show that our pre-training design offers a ~4.2x efficiency improvement in 16K pre-training time-to-loss. Across the full development lifecycle, we distill eight actionable empirical findings-spanning architectural scaling, SFT quality
pruning, long-context generalization, and agentic co-training dynamics. To facilitate community research, we open-source model weights from the pre-training, mid-training, and post-training stages, intermediate checkpoints, training code, per-stage data and data recipes, and W&B logs.
Read the full abstract ▾
All authors Jiyan He, Guang Liang, Hao Liu, Haoxiang Guan, Jinbo Sun, Junyi Guo, Wenjun Feng, Yantai Xie, Yifei Shen, Bin Shao, Chuyang Wei, Kai Chen, Kexin Zhou, Minghang Zhu, Shuxin Zheng, Tie-Yan Liu, Taine Zhao, Wenhui Zhu, Xueyin Xu, Xiaoqing Zhang, Yatao Li, Yuxuan Ren
Computers and Society
LOCO 2026 Lightning Talk Abstracts: 2nd International Workshop on Low Carbon Computing
Ignatius Ezeani, Adrian Friday, Abdessalam Elhabbash et al. (+3 more)
This volume contains the accepted lightning-talk contributions from the 2nd International Workshop on Low Carbon Computing (LOCO 2026), held at Lancaster University, United Kingdom, on 10-11 September 2026. The collection brings together 14 short papers presenting emerging research, early-stage results, practical tools, and critical perspectives on reducing the environmental impacts of computing. Topics include carbon and energy measurement, carbon-aware scheduling, sustainable artificial intelligence and machine learning, high-performance computing, computational sufficiency, hardware longevity, interoperability, frugal computing, and post-growth approaches to digital technology. The contributions were selected by the LOCO 2026 Programme Committee for their relevance to the workshop and their potential to stimulate discussion across technical, organisational, and societal dimensions of low-carbon computing. They are published together in this edited volume as a companion collection to the main LOCO 2026 proceedings index.
Read the full abstract ▾
All authors Ignatius Ezeani, Adrian Friday, Abdessalam Elhabbash, John Vidler, Daniel King, Paul Dempster
Cryptography and Security
SkillAtlas: An Attack Trace Library for Agent Skills
Yuxin Tian, Zenghao Duan, Liang Pang et al. (+2 more)
Agent skills are reusable units for
language-model
agents, but their risks emerge through model decisions, user context, tool calls, and execution feedback rather than through stable signatures or a single sandbox run. Existing static, dynamic, and
benchmark-style evaluations rarely preserve public evidence that can be inspected, searched, and reused. We present SkillAtlas, a hosted attack trace library that converts private
agent-skill security report bundles into reviewed, redacted, and searchable public cases. The library contains 3,014 cases, 6,589 traces, 151,131 steps, 233 affected skills, and 8 risk categories; 42.5% of successful cases first become successful after a non-success initial round, and trajectory-grounded labels improve pre-execution guard accuracy to 0.770.
Read the full abstract ▾
All authors Yuxin Tian, Zenghao Duan, Liang Pang, Zhiyi Yin, Xueqi Cheng
Human-Computer Interaction
Real-time Learning and Evolution in Robotic Art Installations
Sofian Audry and Stephen Kelly
We present three robotic art installations which explore the aesthetics of adaptive behavior. Through
embodied machine leaning and digital
evolution, these works draw viewers into an artificial ecosystem in which open-ended novelty, trial-and-error learning, competition, and cooperation emerge in real time. Research-creation practices are examined in relation to these works, focusing on how they redefine the role of artists within a human-machine collective while examining points of convergence and divergence between artistic and engineering approaches to adaptive robotics. The systems in question use learning and evolutionary processes not as a means to optimize a specific solution, but as an aesthetic experience on its own, suggesting new modes of interdisciplinary art-science research. Finally, we discuss strategies and practices to elevate the aesthetic experience for audiences, including contexts of presentation as well as temporal and material considerations for artworks based on
embodied adaptive systems.
Read the full abstract ▾
Information Theory
A New Upper Bound on the Binary Deletion Channel Capacity
Özgür Soysal
We prove that the capacity of the binary deletion channel satisfies $C(d)\le (1-d)/4$ for every $13/20\le d<1$. The proof describes the output from right to left, using a six-bit context to assign a description length. We bound the increase in expected description length minus output
entropy when one input bit is added. A relative-
entropy identity reduces this bound to finitely many linear inequalities. A potential on input windows of length 26 makes the inequalities
telescope, giving a bound for every input word. Deletion composition extends the result from $d=13/20$ to all larger deletion probabilities. We also obtain finite-block bounds on mutual information and decoding error, with explicit $O(\log n/n)$ corrections. The finite certificate is checked using exact integer arithmetic, and the proof is formalized end to end in Lean.
Read the full abstract ▾
Machine Learning · Cross-listed from stat.ML
Beyond Point Forecasts: A Survey on Probabilistic Forecasting for Time Series and Spatiotemporal Data
Donia Besher, Rajdeep Pathak, Madhurima Panja et al. (+1 more)
Probabilistic
forecasting is central to decision-making under uncertainty, yet its methodological landscape has become increasingly fragmented across temporal and spatiotemporal
forecasting, statistical modeling, machine learning, and deep generative modeling. This survey develops a unified perspective by organizing probabilistic
forecasting methods according to where and how uncertainty is introduced into the
forecasting pipeline. Our taxonomy connects model-agnostic approaches including ensembles and distribution-free calibration, with model-intrinsic approaches spanning
Bayesian modeling, parametric predictive distributions, distributional regression, and modern generative models, and further examines the emerging role of time series foundation models. Beyond methodological synthesis, we identify the assumptions, computational demands, and forms of uncertainty represented by different paradigms, and translate these distinctions into data-driven and domain-specific guidance for method selection. We complement the survey with a cross-paradigm empirical study on univariate, multivariate, and spatiotemporal
forecasting tasks. The results reveal that no single uncertainty-quantification paradigm dominates across settings. Calibration, sharpness, predictive accuracy, and computational efficiency can lead to substantially different model preferences, while expressive generative models and zero-shot foundation models exhibit markedly different accuracy-efficiency trade-offs. Lastly, we identify unresolved challenges surrounding uncertainty in evolving dependency structures, physics-informed predictive distributions,
forecasting extreme events, handling count-valued, directional, and continuous-time series, and the development of unified software resources. Our survey provides both a conceptual framework and a practical roadmap for probabilistic
forecasting research.
Read the full abstract ▾
All authors Donia Besher, Rajdeep Pathak, Madhurima Panja, Tanujit Chakraborty
Machine Learning · Cross-listed from stat.ML
Stochastic Gradient Descent over P2
Maria Oprea, Qin Li and Yunan Yang
Stochastic gradient descent (SGD) admits
diffusion approximations that replace the complicated randomness of
stochastic gradients by Gaussian noise, providing a powerful tool for understanding its dynamics and long-time behavior. We investigate whether an analogous approximation principle holds for optimization over probability measures, where the objective is a functional defined on the Wasserstein space P2. The nonlinear geometry and infinite-dimensional nature of P2 prevent a direct extension of the classical Euclidean theory. Using Lions differentiability, we lift the problem to a linear
Hilbert space, where higher-order differential calculus becomes available. We then construct a Gaussian random-field approximation whose velocity field matches the mean and covariance of the original
stochastic gradient. By exploiting this moment matching through higher-order Taylor expansions, we show that the Gaussian approximation captures the SGD dynamics with second-order weak accuracy. Our result provides a rigorous foundation for replacing sample-driven randomness by analytically tractable Gaussian fluctuations in
stochastic optimization over probability measures.
Read the full abstract ▾
Computer Vision
ProtoCAM: Interpretable Few-Shot Mask-Guided Prototypical Learning for Breast Lesion Classification in Ultrasound Imaging
Ashkan Ebadi
Breast ultrasound imaging plays an important role in the early detection and diagnosis of breast cancer, particularly for patients with dense breast tissue. However, developing reliable deep learning models for ultrasound analysis is challenging due to limited annotated medical data and the need for interpretable predictions. To address these challenges, this paper proposes ProtoCAM, an explainable few-shot learning framework for breast lesion classification that integrates mask-guided feature encoding, prototypical metric learning, and gradient-based visual explanations. The proposed approach leverages lesion masks to guide feature extraction and constructs class prototypes within an
embedding space to enable robust classification under limited training samples. The framework was evaluated on the BUSI
dataset using a stratified group k-fold cross-validation protocol to prevent patient-level data leakage. Experimental results demonstrate ProtoCAM's high performance in low-data scenarios. In a 3-way 5-shot setting, the proposed method achieves a macro F1-score of 0.910, representing a substantial improvement over standard supervised CNN models. Among the evaluated backbone networks, ResNet18 achieved the best performance, reaching a macro F1-score of 91.65% under a 15-shot configuration, providing interpretable insights into the classification decisions. These results highlight the potential of explainable few-shot learning frameworks for reliable computer-aided breast cancer diagnosis in data-scarce medical imaging environments.
Read the full abstract ▾
Information Retrieval
PCGNet: Unifying Shared and Specific Information for Fashion Matching Recommendations
Shuiying Liao and P. Y. Mok
In fashion domain, recommending complementary clothing items that match selected pieces is a crucial cross-selling technique that improves customer satisfaction. Nevertheless, fashion matching presents significant challenges, as recommendations must not only align with individual user fashion preferences but also ensure compatibility between garments. These challenges are twofold. First, existing models often assume an overly simplified decoupled relationship between product compatibility and personalized user preferences, overlooking the natural complexity between the two. Second, existing data-driven approaches are not optimized for real-world fashion data, which is typically sparse and characterized by noisy interactions. To address these challenges, we propose Personalized Compatibility Graph Network, a multi-objective graph learning framework that organically unifies the modeling of product compatibility and personal preferences. PCGNet uses contrastive mutual information maximization to extract and align shared and view-specific patterns, thereby capturing the complex interplay between compatibility and personal preferences. Moreover, we introduce a correlation-aware neighbor sampling and a learnable global graph augmentation, which enhance the model by incorporating self-supervised signals mined directly from the graph, ensuring more stable and informative representations. Finally, PCGNet generates recommendation scores through the joint optimization of BPR ranking loss and multi-view mutual information losses. Experimental validation on two
benchmark datasets demonstrates that PCGNet significantly outperforming state-of-the-art methods across all four evaluation metrics.
Read the full abstract ▾
Data Structures and Algorithms
NOC NOC, who's there? Clustering systems of tree-child and normal networks
Anna Lindeberg and Marc Hellmuth
Clustering systems provide a natural way to encode structural information contained in phylogenetic networks. In this note, we study the clustering systems of normal and tree-child networks through an overlap-based property of set systems, called not-overlap-covered (NOC). We show that the NOC property is equivalent to inclusion-visibility, a memberwise formulation of the strict-compatibility condition previously used for tree-child clustering systems. We characterize normal networks as precisely the semi-regular networks whose clustering systems satisfy NOC. Consequently, a clustering system is realized by a normal network if and only if it satisfies NOC, or equivalently, if every one of its clusters is inclusion-visible. In this case, the Hasse diagram provides a canonical normal realization. These are exactly the clustering systems realized by tree-child networks. The NOC formulation yields a sharp quadratic upper bound on the number of distinct clusters of tree-child and normal networks and a direct
polynomial-time recognition
algorithm. Finally, we explore several consequences of the NOC perspective beyond the phylogenetic setting. These include connections to the enumeration of normal networks, an order-theoretic interpretation of inclusion-visibility, structural properties of NOC set systems, and a tractable special case of Minimum Set Cover, which is NP-hard in general.
Read the full abstract ▾
Robotics
Bridging Thought and Action: Taming Long-Horizon Instability in Open-Source LLM Agents with a MetaTool-Enhanced ROS Framework
Kazi Abrar Mahmud, Nilotpaul Kundu Dhurubo, Tamal Kirttonia et al. (+2 more)
Large
Language Models (LLMs) have enabled more natural human-
robot interaction, but open-source models often exhibit unstable long-horizon
reasoning and inefficient action execution when deployed in agentic robotic frameworks. This paper presents an enhanced ROS-
Agent based architecture that improves task reliability and execution efficiency for agentic robotic systems using open-source LLMs. The proposed system introduces a novel intermediate mechanism, termed the MetaTool, which enforces structured planning prior to action execution. Given a natural-
language command, the MetaTool induces the LLM to generate a pseudo-code plan of intended tool invocations, which is stored in the ROS-
Agent's scratchpad and persists throughout execution. By explicitly separating planning from execution, the proposed approach reduces execution loops and improves deterministic behavior. The architecture is validated on a custom mobile robotic platform with
multimodal perception and motion control capabilities. Experimental results on real-world interactive tasks demonstrate improved task completion and contextual consistency, with up to ~24% gains on complex tasks compared to the baseline framework.
Read the full abstract ▾
All authors Kazi Abrar Mahmud, Nilotpaul Kundu Dhurubo, Tamal Kirttonia, Sabbir Hossain Ujjal, Mohammad Ariful Haque
Software Engineering
The Agentic Company OS: Substrate Inversion for Sustained Enterprise Agent Deployment
Oliver Aleksander Larsen and Mahyar T. Moghaddam
Enterprise AI
agents often succeed in a demonstration and then stall once they must operate day after day. An industry report estimates that most pilots never reach production and that deployed systems rarely retain feedback or improve over time, while
agent benchmarks show single-run successes masking unreliable repetition. We argue that these failure modes share a common architectural root:
agents reason over data structured for human operators and traditional applications, not for the
language models that power them. This position paper proposes that companies deploying
agents in sustained operation should rebuild their cognitive substrate, the shared environment
agents read as working context, around representations matched to that
reasoning surface, isolating schema translation to the action boundary. Markdown is the instantiation available today, not a proven
agent-native primitive. Two mechanisms ground the argument: context-bandwidth asymmetry, the gap between one-pass reading of connected prose and field-by-field typed access that strips relations; and cross-loop coupling, the claim that action, skill, and policy loops compound only if they share one substrate. A four-layer framework (Data, Knowledge, Intelligence, Governance) operationalizes the position, with a Sync
Agent enforcing the action boundary and a per-skill trust gradient, making governance and auditability structural properties of the substrate. The position revives the shared-substrate tradition of classical multi-
agent systems under LLM-era economics. We analyze the main objections and risks, including indirect
prompt injection on the compile path, and outline a research agenda for evaluating substrates directly.
Read the full abstract ▾
Computer Vision
Global-Local Contextual Progressive Expansion Network for Martian Landslide Segmentation in Multimodal Remote Sensing Imagery
Leo Thomas Ramos, Sidike Paheding, Abel A. Reyes-Angulo et al. (+4 more)
Automated landslide
segmentation on Mars is one of the important tasks for understanding its surface processes, and all will aid in future space exploration. However, it remains a relatively underexplored open challenge because landslide morphology is highly variable, foreground regions are often sparse or irregular, and orbital observations combine heterogeneous spectral and topographic cues. In this context, this work investigates the capability of deep learning to address Martian landslide
segmentation through an extensive assessment of modern neural
segmentation models. To the best of our knowledge, this is the first study to provide such a comprehensive exploration in this domain. We further propose TransCPLES, a U-shaped network that couples Contextual Progressive Layer Expansion feature extraction with
Transformer-based contextual
reasoning, enabling the model to capture local geomorphic patterns and broader spatial dependencies for more reliable landslide delineation. Experiments on MMLSv2, a seven-band
multimodal Martian landslide
dataset, show that TransCPLES achieves the best overall performance when evaluated on geographically distinct samples, with consistent delineation across different landslide extents, stable foreground discrimination, and a favorable balance between accuracy and computational cost compared with several state-of-the-art convolutional,
attention-based, and
Transformer-based
segmentation models. With this work, we hope to provide a useful reference and encourage further research and development in deep learning for planetary remote sensing. Code will be available after publication.
Read the full abstract ▾
All authors Leo Thomas Ramos, Sidike Paheding, Abel A. Reyes-Angulo, Rajaneesh A., Sajinkumar K.S., Angel D. Sappa, Thomas Oommen
Information Theory
When Do Pilots Matter for OFDM Sensing? Pilot-Data Resource Design for ISAC
Shengcai Zhou, Luping Xiang, Yi Wang et al. (+1 more)
Practical OFDM-based integrated sensing and communication (
ISAC) signals contain deterministic pilots and random data payloads, yet how these two types of resources jointly affect matched-filter sensing performance remains insufficiently understood. This paper establishes an analytical and optimization framework for pilot-data (P-D) OFDM sensing. We first derive a closed-form mean-square periodic autocorrelation function (MS P-ACF), which characterizes the respective contributions of the average subcarrier power spectrum and data-symbol randomness to sensing sidelobes. Based on this result, we reveal that pilot placement has no impact on normalized sidelobes under uniform power allocation or on the normalized global expected integrated sidelobe level (EISL), whereas it becomes an effective design degree of freedom for reshaping sidelobes under nonuniform power allocation. We further derive the globally optimal two-level pilot-data power allocation for global EISL minimization and characterize pilot placement for peak sidelobe suppression. For region-of-interest (ROI) sensing, we jointly optimize pilot placement and subcarrier power allocation to minimize the normalized ROI-EISL. A strictly uniform pilot placement is proved globally optimal under specified conditions, while a bisection-and-branch-and-bound
algorithm is developed for general resource configurations. Numerical results validate the theoretical analysis and demonstrate that the proposed design reduces the ROI sidelobe level by up to 2.19 dB compared with optimized uniform-pilot OFDM, while improving ranging accuracy at an SNR of -10 dB by 84.3$\%$. These results reveal when and how pilot placement can be exploited to regulate the sensing behavior of random OFDM communication signals, providing practical resource-design principles for OFDM-based
ISAC.
Read the full abstract ▾
All authors Shengcai Zhou, Luping Xiang, Yi Wang, Kun Yang
Computer Vision
Pedestrian Crossing Intent Classification From Event-Based Vision Using Convolutional Spiking Neural Networks With Temporal Augmentation
Henok Teklu, Mustafa Sakhai, Maciej Wielgosz et al. (+1 more)
Anticipating whether a pedestrian will cross the road is safety-critical for autonomous vehicles, requiring real-time inference under challenging conditions including motion blur, high dynamic range, and class imbalance. Conventional frame-based deep networks process redundant RGB data at fixed frame rates, limiting their temporal resolution and energy efficiency. In this work we present an end-to-end pipeline that (i) converts real-world driving footage from the Joint
Attention in Autonomous Driving (JAAD)
dataset into synthetic dynamic
vision sensor (DVS) event streams using the v2e simulator, (ii) augments training with the CARLA-simulated DVS sequences of the DVS-PedX
dataset under both normal and adverse weather conditions, and (iii) trains a novel convolutional spiking neural network (Conv-SNN) with clip-consistent DVS augmentation to classify pedestrian crossing intent as binary: crossing or non-crossing. We detail all architectural decisions, the exact leaky-integrate-and-fire
neuron dynamics with surrogate-gradient learning, the class-balanced loss formulation, JAAD oversampling at 6x, and a 70/15/15 stratified splitting protocol. The trained model achieves 95.83% accuracy and F1 = 0.9695 on the JAAD DVS test set, 97.79% accuracy and F1 = 0.9478 on normal CARLA DVS, and 94.78% accuracy and F1 = 0.8369 on adverse-weather CARLA DVS, all from a 1.07M-parameter architecture trained on CPU. Compared to prior frame-based approaches on JAAD, our method closes or surpasses the reported accuracy while operating natively on sparse temporal representations. We include a thorough analysis of the convergence behaviour across all 15 training epochs, domain transfer characteristics, and a quantitative comparison with representative related work.
Read the full abstract ▾
All authors Henok Teklu, Mustafa Sakhai, Maciej Wielgosz, Matej Mertik
Graphics
SNAP3D: Physically Grounded 3D Parts for Assembly from a Single Image
Yu-Rou Tuan, Hao-Tang Tsui, Nicolas Ugrinovic et al. (+2 more)
Part-aware 3D asset generation enables applications such as editing, articulation, simulation, and fabrication, yet existing methods can generate visually complete individual parts without ensuring that they form a valid physical assembly. Consequently, generated neighboring parts may interpenetrate, lack valid connections, or collapse under
gravity. We propose a physics-guided framework for improving single-image part-aware 3D generation with physically compatible geometry and stable connections. Our method resolves inter-part penetration, recovers a contact graph between neighboring parts, and introduces parameterized connectors at their contact surfaces. Using feedback from physical simulation, we refine connector placement, orientation, and dimensions to improve assembly stability while preserving the generated geometry. We further introduce a physics-based evaluation protocol that complements conventional
geometric metrics by directly testing assembly validity and stability under
gravity. Experiments comparing against multiple part-aware 3D generators show substantial improvements in physical realizability and stability while maintaining
geometric quality. We additionally validate the resulting parts through 3D printing and real-world assembly.
Read the full abstract ▾
All authors Yu-Rou Tuan, Hao-Tang Tsui, Nicolas Ugrinovic, Kris Kitani, Xiaoxuan Ma
Computation and Language
Type Diversity Enables Transformers to Generalise Compositionally
Anssi Moisio, Mathias Creutz and Mikko Kurimo
Compositional generalisation has been divided into lexical and structural generalisation. Previous work has found that structural generalisation is harder than lexical for
Transformers. We propose that this difference is not inherent to
Transformers, but due to the high diversity of lexical types and low diversity of structural types in the specific
datasets of these previous works. By type diversity we mean the number of different constructors of that type, instead of, for example, the specific word combinations that might populate the structure. To test this, we vary the amounts of type diversity of lexical and structural types in previously published
datasets. We create linguistically diverse variants of the COGS and SLOG
datasets using Grammatical Framework. We find that type diversity correlates with compositional generalisation equally in lexical and structural test cases, supporting our hypothesis. We note a contradiction with the proposition in previous work that compound divergence explains the difficulty in compositional generalisation tasks. We further investigate the effects of other
dataset properties on compositional generalisation, such as the diversity of types other than the novel test structure, and surface properties of the logical semantics format.
Read the full abstract ▾
Computation and Language
SAS: Simple Attention Sparsification via End-to-End Optimization of Context Ranking
Zhiwei Li, Lei Zhu, Hao Gu et al. (+6 more)
Post-training
attention sparsification reduces the quadratic cumulative
attention cost of pretrained
Transformers by selecting a small set of context units (
tokens or blocks) for each query. Existing trainable methods usually use a lightweight selector to score context units, followed by hard Top-K selection that blocks gradients from the
language modeling loss. Consequently, these methods commonly distill layer-wise dense
attention distributions. Although this encourages the selector to rank context units by dense
attention weights in the original model, the ranking is not directly aligned with their impact on predictions under a fixed
attention budget (i.e., the number of attended context units per query), potentially wasting the limited budget on less useful units. To address this misalignment, we propose Simple
Attention Sparsification (SAS), a gated sparse
attention mechanism that optimizes context ranking end-to-end with the
language modeling loss. The key idea is to inject the selector's continuous scores into
attention logits during training, allowing the loss to update the selector through standard backpropagation. We identify several choices crucial for this simple design to work well in practice: placing the gate inside the
attention softmax in log form, using normalized softmax gates to calibrate historical context against the always-retained current block, and preserving continuous selector scores so the model learns relative priorities rather than only hard selections. To support long-sequence training, we implement a
memory-efficient Triton kernel that integrates SAS into FlashAttention-style computation. Across
reasoning, long-context understanding, and agentic tasks, SAS consistently outperforms trainable sparse
attention baselines across
attention budgets, with especially large gains under tight budgets, demonstrating more effective context ranking for downstream tasks.
Read the full abstract ▾
All authors Zhiwei Li, Lei Zhu, Hao Gu, Xiang Hu, Yan Wang, Haitao Mi, Sirui Han, Leo Liang, Zhijiang Guo
Data Structures and Algorithms
Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to $\beta\leq \frac{1}{2}+\varepsilon$
Mathews Boban, Anqi Li and Shayan Oveis Gharan
We introduce a new family of trickledown
theorems, a.k.a., local to global technique to bound the spectral gap of the Glauber dynamics for multi-state
spin systems. In this technique instead of upper-bounding the influence
matrix of a link of co-dimension 2 by $\lambda I$ (where $\lambda$ is the second
eigenvalue of the link), we upper-bound the influence
matrix after a carefully chosen rank-1 shift. The rank-1 shift allows for a significantly smaller upper-bound but it comes at the cost of bounding the average loss due to rank-1 perturbations. As an application we use this method to show that the natural Glauber dynamics mixes in
polynomial time to generate samples from the Sherrington-Kirkpatrick model for $\beta\leq \tfrac{1}{2}+\varepsilon$, for an absolute constant $\varepsilon>0$. At the heart of the proof we manage to bound the loss due to rank-1 perturbations by averaging over all links of co-dimension 2.
Read the full abstract ▾
Human-Computer Interaction
From Review to Reuse: How Post-Task Workflow Can Support Human-AI Agent Interaction
Zekun Wu, Xinru Wang, Rock Yuren Pang et al. (+2 more)
AI
agents can automate tasks by turning a single natural-
language request into a multi-step process spanning tools, files, and applications. Users are often left to judge that process from fragmented execution information and the final output. To make the completed process easier to understand, validate, and reuse, we investigate post-task workflows: editable, graph-based representations of an
agent's completed execution. We first analyzed 10,803 public workflow templates from n8n to characterize real-world automation practice, then developed Trace2Flow, a research probe that translates
agent execution traces into interactive post-task workflows. In a study, participants (N = 20) reviewed
agent executions with
prompt or
agent errors. We found that post-task workflows improved their understanding and error detection over a
prompt-only condition, and that validation succeeded mainly when users cross-checked across multiple evidence sources. For follow-up tasks, adapting the workflow matched adapting the prior
prompt in success, time, and difficulty, and was often preferred.
Read the full abstract ▾
All authors Zekun Wu, Xinru Wang, Rock Yuren Pang, Chenglong Wang, Anna Maria Feit
Computer Vision · Cross-listed from eess.IV
Recurrent Dynamic Range Extension
Sebastian Dille, Keru Fu, S. Mahdi H. Miangoleh et al. (+1 more)
We present an approach to progressively extend the highlights of an image. Instead of reconstructing the full dynamic range of a complex scene directly, we learn a simpler task first: We extend the dynamic range of an input image by a single exposure value. Once this is mastered, we retrieve the full HDR image for the scene by executing our network recurrently, progressively increasing the dynamic range of the input. Our formulation is agnostic to the input dynamic range and targets a bounded output domain. This enables us to use widely available RAW images for the reconstruction task and adapt
adversarial losses to construct realistic images. By incorporating
Memory Replay for backpropagation, we can train our network recurrently over multiple inference stages and reduce reconstruction errors. As a consequence, our system reconstructs challenging long-tailed HDR scenes robustly and shows powerful recovery of bright light sources and highlights.
Read the full abstract ▾
All authors Sebastian Dille, Keru Fu, S. Mahdi H. Miangoleh, Yağ{\i}z Aksoy
Artificial Intelligence
Rethinking Heterogeneous System Disaggregation for Subquadratic Attention
Arya Tschand, Yaosheng Fu, Vikram Sharma Mailthody et al. (+6 more)
Frontier
language models are more aggressively using subquadratic
attention to reduce the
memory footprint and compute requirements during inference while still delivering frontier accuracy. While existing systems make dense
attention-centric disaggregated serving decisions, we show that disaggregating inference around the unique arithmetic intensity and
memory footprint of subquadratic
attention LLMs can achieve significant throughput and energy efficiency gains on emerging DRAM-based and SRAM-only heterogeneous systems. We introduce SQD (SubQuadratic Disaggregation), a fine-grained heterogeneous disaggregation scheme that splits decode by quadratic and subquadratic
attention rather than by operator type, and that applies across subquadratic
attention variants. For sparse
attention LLMs, we disaggregate decode into top-k selection, which must index through the full KV, and top-k
attention plus FFN, which have static
memory footprints. For linear and sliding-window
attention LLMs, we disaggregate decode into dense
attention layers and subquadratic
attention layers plus FFN. In an adjusted 8xB200 heterogeneous system proxy, we observe average
tokens/J improvements of 53% on GLM 5.2, 31% on Nemotron 3 Ultra, and 56% on Gemma 4 31B over the strongest GPU-only baselines. In an analytical model of a Rubin plus LPX system with fixed power budgets, we observe 1.2x to 1.5x tighter achievable latencies and up to 3.6x higher throughput over the best baseline of
attention-FFN disaggregation. Our experiments also reveal architectural insights on chip and interconnect provisioning for next-generation heterogeneous systems serving subquadratic
attention.
Read the full abstract ▾
All authors Arya Tschand, Yaosheng Fu, Vikram Sharma Mailthody, Nicolai Oswald, Po-An Tsai, Ritchie Zhao, Oreste Villa, Vijay Janapa Reddi, Karu Sankaralingam
Computational Complexity
A Dichotomy for Boolean Complex Holant Problems with Conjugate-Closed Signature Sets
Jincheng Guan, Shuai Shao and Zhuxiao Tang
We study Boolean Holant problems with complex-valued signature sets closed under conjugation. Such sets arise naturally in tensor-network expressions for classical strong simulation of
quantum circuits. We prove a complexity dichotomy for such problems with an explicit tractability criterion. This extends the dichotomy for real-valued Holant problems, with the same four tractability conditions. Our proofs use Xia's projective binary group framework and
quantum entanglement theory. The conjugate closure assumption precisely makes $k$-uniformity, directly applicable to the classification of Holant problems, by realizing reduced density
matrices via Holant gadgets. We also use the classification of absolutely maximally entangled states to resolve a particular $6$-ary obstruction in our inductive proof of the \#P-hardness.
Read the full abstract ▾
Artificial Intelligence
A Hybrid LSTM-XGBoost Framework for Multi-Horizon Stock Return Prediction Across Diversified Equity Portfolios
Seif ElDein Mostafa, Yahia Ahmed, Farah Datwish et al. (+1 more)
Accurate prediction of equity returns remains a major challenge in computational finance due to the non-stationary, nonlinear, and low signal-to-noise ratio nature of financial time series. This paper proposes a hybrid two-stage architecture that combines a long short-term
memory (LSTM) network with an XGBoost gradient-boosted regressor for multi-horizon stock return prediction across a diversified panel of 14 U.S. equities spanning six industry sectors. The LSTM component, comprising two stacked layers with 64 hidden units, processes 60-day sliding windows of five sequential
market features to produce 64-dimensional temporal
embeddings that encode learned sequential
market dynamics. These
embeddings are concatenated with 14 hand-crafted technical indicators to form a 78-dimensional hybrid feature vector, which is subsequently passed to an XGBoost regressor tuned via 3-fold cross-validation grid search. The framework is trained on a multi-stock pooled corpus using strict chronological splits and per-stock MinMaxScaling to prevent look-ahead bias, and evaluated across four prediction horizons of 30, 90, 252, and 365 trading days. Experimental results demonstrate that the hybrid model achieves a test RMSE of 0.0949 on the 30-day horizon, roughly one-third that of the standalone LSTM baseline, while marginally matching or surpassing the XGBoost-Only baseline across the majority of stocks. Directional accuracy rises with horizon length, reaching 97.6% at 365 days; we show, however, that this largely tracks the high base rate of positive long-horizon returns in the sample, and we therefore
benchmark directional accuracy against a naive always-positive predictor and treat the above-base-rate gap at short horizons as the more informative signal. A composite investment scoring framework derived from multi-horizon predictions is further proposed to support portfolio ranking and decision support.
Read the full abstract ▾
All authors Seif ElDein Mostafa, Yahia Ahmed, Farah Datwish, Marwa Solayman
Artificial Intelligence
CMA-OT: Hierarchical Expert Supervision for Dance-to-Music Generation
Jinting Wang, Chenxing Li, Dong Yu et al. (+1 more)
Dance-to-music (D2M) generation aims to synthesize music that is rhythmically and stylistically aligned with dance
videos. A key challenge arises from the semantic mismatch between sparse dance cues, such as rhythm and style, and the dense information required for music composition, including structure, instrumentation, and expressive dynamics. Existing methods typically rely on these sparse cues and supervise only the final audio output, resulting in poorly learned music representations and generated music with limited musicality and structural coherence. To address these issues, we propose Curriculum-guided Multi-scale representation
Alignment with scale-aware Optimal Transport (CMA-OT), a novel paradigm that leverages an external music expert to provide hierarchical supervision for the generator's latent features, bridging the semantic gap and enhancing representation learning. To effectively incorporate hierarchical supervision, we introduce a curriculum-guided multi-scale learning strategy that progressively transfers musical knowledge from the expert to the music generator, enabling stable and effective representation learning. Moreover, to accommodate the semantic and structural variations across different expert scales and achieve fine-grained
alignment under temporal mismatch, we propose a scale-aware optimal transport
alignment mechanism, which models soft correspondences between hierarchical expert representations and the generator's latent features. Extensive experiments on two
datasets demonstrate that CMA-OT achieves state-of-the-art performance in rhythmic synchronization, perceptual quality, and overall music generation.
Read the full abstract ▾
All authors Jinting Wang, Chenxing Li, Dong Yu, Li Liu
Computation and Language
Continue, Adapt, or Yield: In-Turn Adaptation to Overlapping Speech in Full-Duplex Agents
Yunqi Lu, Tyler Baumgartner, Nikhil Johri et al. (+6 more)
Full-duplex evaluation often emphasizes whether an
agent keeps speaking or stops. That binary cannot express a third response humans use routinely: continuing to speak while incorporating what the listener just contributed. The contribution may be a missing word, a correction or a clarification. We introduce Duplex Cue, an evaluation of this in-turn adaptation in full-duplex voice
agents. Duplex Cue separates listener intent (backchannel, collaboration, or interruption) from speaker behavior: continuing unchanged, adapting within the turn, or yielding. Adaptation includes acknowledgment as well as content revision. In a single-model case study using 300 human-confirmed cues from unscripted English conversations, we compare recorded human responses with PersonaPlex continuations generated while replaying the listener's audio. We retain 208 pairs with the ongoing speaker active at cue onset and a scorable response in each condition. On the 66 collaborative pairs, recorded speakers adapt in 68.2% of cases, compared with 34.8% for PersonaPlex. The model otherwise continues unchanged (42.4%) or yields (22.7%). These findings show why evaluating natural voice interaction requires measuring how an
agent responds to a listener's contribution as well as whether it keeps speaking.
Read the full abstract ▾
All authors Yunqi Lu, Tyler Baumgartner, Nikhil Johri, Brandon Tai, Candice Fan, Luc Debaupte, Ruben Aguilar, Bill Wang, Yi Zhong
Computational Engineering
Extreme-Scale Linear-Scaling Kohn-Sham DFT at 100 Million Atoms: Bridging Quantum Simulations and Experiments
Qimen Xu, Yu Zhang, Dixing Ni et al. (+11 more)
Kohn-Sham density functional theory (DFT) remains the workhorse of ab initio materials simulation, yet cubic computational and quadratic
memory scaling have confined calculations to a few hundred to thousands of atoms, spanning only nanometers, far below experimentally relevant length scales. We introduce XLSDFT, a linear-scaling DFT framework based on divide-and-conquer decomposition of the one-particle density
matrix and Chebyshev-filtered subspace iteration, achieving linear computational and
memory scaling while retaining DFT accuracy. Deployed on the LineShine exascale supercomputer, XLSDFT reduces computational complexity by orders of magnitude, enabling unprecedented DFT scale: a 200-million-atom silicon
crystal, twentyfold beyond the prior record. Our implementation achieves 96.6% weak-scaling efficiency and sustained 157.9 Pflop/s (FP64) for a 100-million-atom scaling study. We further simulate an 11-million-atom all-solid-state battery interface of unprecedented complexity, 1,000 times beyond prior DFT for such systems, revealing how lithium metal reacts with the solid electrolyte at atomic resolution, in quantitative agreement with spectroscopy experiments.
Read the full abstract ▾
All authors Qimen Xu, Yu Zhang, Dixing Ni, Lei Gao, Guangnan Feng, Qinrui Zheng, Jianting Liu, Haitian Lu, Zhaopeng Jia, Wei Xue, Shriram Chandran, Torsten Hoefler, Haohuan Fu, Yutong Lu
Machine Learning · Cross-listed from stat.ME
A Ranking Approach for Measuring Calibration
Anirban Chatterjee and Rina Foygel Barber
When providing forecasted probabilities with a predictive model, the ideal model offers perfect calibration: the true probability of the outcome (i.e., the probability that $Y=1$) exactly matches the forecasted probability $f(X)$. In practice, models inevitably exhibit calibration error, and it is therefore important to be able to measure this miscalibration to assess a model's reliability. The Expected Calibration Error (ECE) is the most widely used measure of miscalibration, but is known to be impossible to estimate the ECE with guaranteed accuracy in an assumption-free setting. In this work, we propose an alternative measure, the rankECE, that is based on comparing points with neighboring values of the predicted probability $f(X)$. Our theoretical guarantees and empirical results establish that rankECE provides a better proxy for ECE as compared to binned approximations to ECE, which are the most commonly-used approximations in practice.
Read the full abstract ▾
Systems and Control
An Equivariant Filter for Spacecraft Nonlinear Relative Navigation with Range and Bearing Measurements
Gil Serrano, Bruno J. Guerreiro, Pedro Lourenço et al. (+1 more)
Relative
navigation is a fundamental task in space proximity operations and autonomous rendezvous. The nonlinear relative orbital dynamics are equivariant and admit a semidirect product Lie group
symmetry. This property is used to design an Equivariant Filter (EqF). The filter estimates the relative position and velocity between a chaser spacecraft and a target by lifting the filter dynamics to the group, while respecting the underlying geometry of the problem. Simulations demonstrate the filter's performance and effectiveness.
Read the full abstract ▾
All authors Gil Serrano, Bruno J. Guerreiro, Pedro Lourenço, Rita Cunha