Data Structures and Algorithms
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
All of arXiv
Monday 9 November
In a seminal work, Gaspers and Szeider [FOCS 2013] gave a fixed-parameter tractable (FPT) approximate algorithm for finding a strong backdoor of size at most $k$ to incidence treewidth at most $t$, for a given CNF-formula $\phi$. In particular, their algorithm runs in $f(k,t) |\phi|^3$ time, and finds a strong backdoor to treewidth at most $t$, of $\phi$, of size at most $2^k$ whenever there exists one of size at most $k$. Determining whether the detection of strong backdoors to bounded incidence treewidth is FPT parameterized by $k+t$ was left open in their work and this has been repeatedly posed as an open question by Gaspers and Szeider, for example in [The Multivariate Algorithmic Revolution and Beyond 2012] and more recently in [Computer Science Reviews 2025], even for incidence forests and when the input is a $3$-CNF formula. We answer this question affirmatively. We show that strong backdoors to forests can be found in linear-FPT time on arbitrary non-tautological CNF formulas (not just on 3-CNF formulas). Given such a formula $\phi$ and a budget $k$, our algorithm finds a strong backdoor to the class of forests, of size at most $k$, or correctly reports that none exists, in $2^{2^{O(k)}} |\phi|$ time. Moreover, we show that our result is as tight as it can get. First, we show that finding strong backdoors to treewidth $t$ for any $t \geq 2$ is W[1]-hard, even on non-tautological 3-CNF formulas. Second, the running time of our algorithm is tight: it is linear in the input size and a better than double-exponential dependence on $k$ in the running time would imply a $2^{o(N/\log N)}$-time algorithm for solving 3-SAT on $N$ variables, which would beat even the very recently claimed sub-exponential algorithm for solving 3-SAT by OpenAI and Anthropic.
Commutative Algebra
Split Kernel Multiplication Modules
We introduce split kernel multiplication (SKM) modules, for which every submodule has the form $N=IM\oplus\ker f$, where $I$ is an ideal of $R$ and $f$ is an endomorphism of $M$. We study direct sums, localization, and connections with multiplication and retractability properties. For the idempotent version (ISKM), we prove that $R\oplus k^b$ is ISKM over a local ring $(R,\mathfrak m)$, with residue field $k$ and $b\geq1$, if and only if $\mathfrak m^2=0$. We also classify ISKM modules of the form $R^a\oplus k^b$ over local rings. For commutative Noetherian rings, we show that $R^2$ is SKM if and only if $R$ is an Artinian principal ideal ring. Finally, we prove that every finitely generated $R$-module is ISKM if and only if $R$ is a finite product of fields.
Read the full abstract
Distributed Computing
Mitigating SM-Level Load Imbalance in 3D Gaussian Splatting on GPUs
3D Gaussian Splatting (3DGS) enables photorealistic, real-time rendering on commodity GPUs and is increasingly adopted in generative world models and autonomous driving simulators. However, existing optimizations rely on algorithmic changes that often require retraining, or on specialized accelerators that lack flexibility across evolving 3DGS variants. In this paper, we identify a fundamental inefficiency in GPU-based 3DGS rendering: severe SM-level load imbalance caused by uneven workloads across screen tiles. This imbalance creates a long execution tail, leaving most SMs idle while a few process computationally intensive tiles, particularly in large-scale urban scenes. To address this, we present a software-defined GPU scheduling approach that mitigates the execution tail. Our approach uses a persistent kernel to schedule heavy tiles first and selectively chunks outlier tiles across multiple CTAs. A lightweight per-frame policy determines when and how much to chunk using tile statistics already available in the rendering pipeline. Our approach requires neither retraining nor specialized hardware and can be applied orthogonally to existing optimizations across diverse 3DGS variants. Averaged per scene, it accelerates alpha blending by up to 2.93x on a large-scale urban scene, and by up to 5.6x on its most imbalanced frames, while retaining the original alpha blending formulation.
Read the full abstract
High Energy Physics (Phenomenology)
Heavy-quark spin symmetry and Pauli exclusion in pentaquarks with three to five heavy quarks
We study negative-parity hidden-flavor pentaquarks with three to five heavy quarks, $QQ\bar{Q}qq$, $QQQ\bar{Q}q$, and $QQQQ\bar{Q}$ with $Q=c,b$ and $q=u,d$, in QCD sum rules, using the complete set of S-wave baryon–meson currents with $J^P=1/2^-$, $3/2^-$, and $5/2^-$ and the operator product expansion up to dimension 10, 9, and 6. We focus on the splittings between states of the same baryon–meson configuration, which, unlike the absolute masses, are only weakly affected by the choice of the heavy-quark mass scheme and by a finite width. Configurations whose light degrees of freedom have a unique spin are nearly degenerate or show splittings that decrease from charm to bottom by a factor compatible with $\bar m_c/\bar m_b$, whereas configurations with two light quarks in different hadrons show splittings that are not reduced, as expected from heavy-quark spin symmetry. A decomposition of the correlators into factorizable two-hadron and connected quark-exchange contributions shows that the correlators are dominated by the two-hadron part and that this pattern holds separately for both parts: the quark-exchange contribution decreases from charm to bottom when a heavy quark is exchanged and is not reduced when a light quark is exchanged. In the fully heavy systems the $1/2^-$ and $3/2^-$ states are degenerate within about $20$~MeV, while the $5/2^-$ state lies $126$–$139$~MeV ($cccc\bar c$) and $183$–$228$~MeV ($bbbb\bar b$) above the $3/2^-$ state. This splitting is generated by the exchange terms between the identical heavy quarks and does not decrease from charm to bottom, which points to the Pauli principle rather than to a hyperfine effect. Currents whose baryon and meson share no quark flavor are exactly factorizable at this order and cannot distinguish bound states from two-hadron states.
Read the full abstract
Neural and Evolutionary Computing
Maximizing Detection Probability in UAV Search Missions using Random-Key Optimizers
This paper focuses on the stochastic and real-time constraints of Unmanned Aerial Vehicle (UAV) path planning in Search and Rescue (SAR) missions. We introduce a configurable data-driven and intelligent routing architecture that combines a closed-loop probability update with the Random-Key Optimizers (RKO). Our problem is mathematically modeled as a dynamic probabilistic variant of the Open Vehicle Routing Problem (OVRP), enabling the solver to switch adaptively between two objectives, thereby balancing probability maximization and resource minimization. The framework degrades elegantly under noisy priors but not under biased ones: a systematically biased map performs about half as well as flying with no prior at all. Computational tests show that the proposed scheme is scalable and competitive with single-path scenarios in terms of solution performance and serves as a strong decision guide for intelligent planning in SAR operations in unstable environments
Read the full abstract
Systems and Control
A Scale-Space Theory of Memory
Scale-space theory has emerged as a central attempt to restrict the general theory of signal processing with geometric constraints inspired from the animal world. In the mathematical language of operator theory, scale-space theory restricts the Toeplitz operator. The present paper investigates scale-space theory for memory systems. We investigate how scale space theory restricts a memory system encoding past information, that is, restricts the Hankel operator. Our main result is to establish a close correspondence between scale-space theory and the long-studied relaxation property.
Read the full abstract
Programming Languages
Beating Rytter's Bound: All-Pairs CFL Reachability in $O(n^3(\log\log n)^2/(\log n)^2)$ Time
Context-free reachability and 2NPDA recognition are fundamental problems in program analysis and language theory. Despite years of effort, the best algorithms for these problems run in time $O(n^3/\log n)$ on a word RAM model; they are based on an observation of Rytter in 1985 for 2NPDA which was adapted for CFL reachability by Chaudhuri in 2008. No better algorithm has been designed since. We give the first improvement to Rytter's algorithm. For both all-pairs context-free reachability and 2NPDA recognition, we show a deterministic algorithm running in $O(n^3(\log\log n)^2/(\log n)^2)$ time and $O(n^{2+\epsilon})$ words of space for every fixed $0<\epsilon<1$ on a word RAM. Our improvement is based on a new data structure that reports set differences using batched maintenance of exact intersection counts, allowing saturation to skip regions that contain no new reachability information.
Read the full abstract
Machine Learning
A Modular Perspective for Modeling MARL Systems
The growing complexity of Multi-Agent Reinforcement Learning (MARL) has fragmented the literature, obscuring underlying architectural choices behind diverse implementations. This fragmentation makes it difficult to evaluate critical modeling dimensions in isolation, identify how components affect the resulting system dynamics, and compare, reuse, or combine contributions across the literature. This paper proposes a modular perspective for modeling, analyzing, and implementing MARL systems. We decompose them into eight functional modules: agents, environments, learning, reward modeling, training and execution modes, communication, modeling of other agents, and evaluation criteria. For each module, we clarify its role and review representative approaches. We instantiate this decomposition in MARLKIT, a framework whose modules are explicit and interchangeable. MARLKIT demonstrates how the proposed perspective supports transparent experimental assumptions and the controlled variation and combination of MARL mechanisms. Experiments illustrate its ability to prototype, compare, reuse and combine modules while making differences between configurations explicit. Overall, the paper provides a structured perspective on MARL modeling and implementation, offering a common language for making modeling choices explicit, supporting clearer descriptions of MARL approaches, and supporting more controlled experimentation through the systematic isolation and combination of MARL mechanisms.
Read the full abstract
Computers and Society
Hidden Distances: How Likert-Scale Spacing Shapes Algorithmic Voting Advice
Voting Advice Applications (VAAs) are algorithmic recommenders that match voters with political candidates on policy preferences. They are widely adopted across many multi-party democracies; in Denmark, 62% of eligible voters used a VAA ahead of the 2022 general election, and 45% of VAA users reported following its advice. VAAs typically ask voters and candidates to respond to policy statements on a Likert scale, from “strongly disagree” to “strongly agree”, and recommend candidates whose responses are closest to the voter's. Computing these distances requires assigning numbers to response options, a design choice without an empirical basis, since it is unknown how people perceive the distances between options. Here we show that this seemingly technical choice substantially changes whom voters are matched with. We parameterize the distance between “(dis)agree” and “strongly (dis)agree” relative to the distance between “neutral” and “(dis)agree” as $\alpha$, and quantify how it changes recommendations for a popular Danish VAA. We find that moving from equidistant options to doubling this distance can change $37.7\%$ of top candidate matches and $21.9\%$ of top party matches, although no answers change. Low $\alpha$-values favor candidates with strong positions, with some parties receiving up to $ 19.6\%$ more recommendations, while high $\alpha$-values favor moderates. Similarly, female candidates receive fewer recommendations at low $\alpha$ and more at high $\alpha$-values. Our findings demonstrate that undisclosed quantification choices in algorithmic recommenders can carry considerable electoral consequences, and they call for transparency and sensitivity analysis in VAA design. As Likert-based matching also underpins dating platforms and roommate allocation systems, these implications extend well beyond elections.
Read the full abstract
High Energy Astrophysical Phenomena
Depth of Maximum of EAS and Mean Mass Composition of Primary CRs from the Spatial and Temporal Distribution of Cherenkov Light According to TAIGA-HiSCORE Data
We present the dependence of the depth of maximum of extensive air showers (EAS), $X_{\max}$, on the energy of the primary particle, as determined from data recorded with the wide-angle Cherenkov array TAIGA-HiSCORE during the 2021–2025 observation seasons. The reconstruction of $X_{\max}$ from the experimental data uses relations obtained from EAS simulations: the dependence on the steepness of the Cherenkov light lateral distribution function ($P$-method) and on the full width at half maximum of the Cherenkov light pulse ($\tau$-method). The reconstructed $X_{\max}$ values are converted into the mean logarithmic mass $\langle\ln A\rangle$, which characterizes the primary cosmic-ray mass composition. The results are compared with measurements from Tunka-133 (2017), the Pierre Auger Observatory (2019), LHAASO (2024), TALE (2026), and other experiments.
Read the full abstract
Computation and Language
MNN-Pocket-0.3B Technical Report
This technical report presents MNN-Pocket-0.3B, a compact 300M-parameter dense language model designed for efficient on-device deployment and supporting context lengths of up to 32K tokens. With an INT4 deployment footprint of only 173 MB and decoding throughput of up to 466 tokens/s on iPad Pro M5 (Metal), it can be seamlessly integrated into applications on edge devices such as smartphones and smart glasses. MNN-Pocket-0.3B is developed through the co-design of its architecture, data, training pipeline, and inference system. Hardware-aware architecture selection and dependency-aware vocabulary pruning balance model capability with on-device memory and compute constraints. A four-stage pre-training pipeline covering approximately 4.1 trillion high-quality Chinese and English tokens equips the model with broad knowledge and reasoning capabilities. This is followed by a three-stage post-training pipeline comprising instruction fine-tuning, multi-teacher on-policy distillation, and quantization-aware training. Finally, hardware-specific optimizations in the MNN inference engine enable fast, memory-efficient inference and long-context processing. Extensive evaluations demonstrate that MNN-Pocket-0.3B achieves frontier-level performance among models of comparable size, with particularly strong results in Chinese and English knowledge and reasoning, mathematics, coding, and instruction following. It consistently outperforms similarly sized open-source models and even surpasses several 0.5B-parameter models on instruction-following benchmarks. We release MNN-Pocket-0.3B with open weights and ready-to-use MNN deployment packages. We hope it will provide a practical foundation for capable, responsive, and memory-efficient edge applications while advancing research and development in on-device language models.
Read the full abstract
Machine Learning
The Optimal Rate Constant of Heavy-Ball Momentum on Smooth Strongly Convex Functions
The heavy-ball method with a constant step size and a constant momentum parameter accelerates gradient descent on quadratics, but no choice of the two parameters does so on the class of smooth strongly convex functions. We determine how much faster than gradient descent it can be made on this class. Writing the best worst-case rate over all tunings as $1-c(\kappa)/\kappa$, where $\kappa$ is the condition number, we prove that $c(\kappa)$ tends to $8$ in every dimension of two or more. The lower bound on the rate holds for every tuning, because a tuning that is faster than $1-8/\kappa$ on quadratics follows a slowly decaying spiral on some function of two variables. The matching upper bound comes from an explicit tuning, with nearly the momentum of Polyak's tuning and a step size about $\sqrt{\kappa}/8$ times smaller, and from a Lyapunov function whose positivity is verified in exact arithmetic. Optimally tuned heavy-ball is therefore asymptotically four times faster than gradient descent on this class.
Read the full abstract
Computational Physics
Efficient sensitivity analysis for combustion problems via reformulation and adjoint methods
Numerical simulations of combustion processes rely on chemical kinetic models, whose predictive capability is typically assessed by comparing measurements of quantities of interest (QoIs) in idealized experimental configurations with the corresponding simulated values. Sensitivity analysis quantifies the influence of model parameters on QoIs, making it a key tool for model development and optimization. Given the large number of parameters involved in detailed kinetic models compared to the number of QoIs, adjoint methods are a promising approach for efficient sensitivity analysis. Ignition delay times (IDTs) and extinction strain rates (ESRs) are among the QoIs of primary importance. However, applying adjoint methods to these quantities is not straightforward and is addressed in this work. The system of governing equations is reformulated via a coordinate transformation that makes the QoI an explicit component of the solution vector. This reformulation enables the application of adjoint sensitivity analysis for both IDT and ESR. A computational complexity analysis demonstrates that the proposed formulation significantly improves algorithmic efficiency compared to conventional approaches. The methodology is verified by comparing adjoint sensitivity coefficients with those obtained from other methods. Execution time measurements show computational cost reductions of up to two orders of magnitude relative to standard direct sensitivity analysis. A benchmark study is conducted across kinetic models of increasing size to assess how far theoretical efficiency gains are realized in practice. While the results show that implementation details can limit performance for smaller problem sizes, the expected asymptotic scaling is observed for larger models. The benchmark thus provides a reference framework for identifying key performance bottlenecks and guiding subsequent optimization efforts.
Read the full abstract
Numerical Analysis
Unmasking shortcut solutions of coding agents on partial differential equations
Coding agents now write simulation programs, but benchmarks usually judge only whether their output matches a reference. In manufactured-solution tasks the data determine the exact solution, so a matching output need not come from a solver. We introduce PDEViBench, a benchmark of 290 tasks in six equation families that traces each passing program to the computation behind its output and reruns unclear programs on changed data. A Codex agent (GPT-5.2) passed 80% of 1,450 runs, yet about one pass in ten returned the exact solution without solving the equation. Counting only solved passes changed which task features made problems seem hard and reversed the ranking of two prompts. Once the prompt forbade the shortcut, every pass was a numerical solve, and on tasks without a closed-form solution passing programs stayed correct on changed data. Scientific coding benchmarks should check how each answer was computed as well as whether it matches.
Read the full abstract
Artificial Intelligence
PACE-ECG: Patient-Aware Contrastive ECG Pretraining; Leveraging Longitudinal Structure for Transferable Representations
Foundation models for physiological signals are commonly evaluated on in-domain interpretation tasks, but their ability to transfer to longitudinal clinical prognosis across healthcare systems remains uncertain. We developed PACE-ECG, an ECG pretraining framework that combines contrastive learning across temporally neighbouring recordings from the same patient with clinically guided multitask supervision. We evaluated frozen ECG representations for post-myocardial-infarction all-cause mortality and incident heart failure prediction across MIMIC-IV and two external HEEDB cohorts, comparing the proposed representation with DeepECG-SSL, a state-of-the-art model, and two control baselines. Across both downstream tasks, the proposed model outperformed DeepECG-SSL in-domain (AUROC +1.9% for mortality and +4.0% for heart failure) and on external populations in HEEDB-Boston (+5.6% for mortality +10.3% for heart failure) and HEEDB-Atlanta (+6.9% for mortality +11.0% for heart failure) while using an encoder 41 times smaller and a fraction of the pretraining data. A matched ablation showed that patient-temporal pairing improved external mortality and heart failure AUROC over generic self-supervision by 7.0% and 9.4% on HEEDB-Boston and 8.9% and 9.3% on HEEDB-Atlanta. These findings indicate that pretraining-objective design greatly influences downstream transfer alongside model and data scale, and that in-domain performance alone is insufficient to establish the clinical generalisability of ECG foundation representations.
Read the full abstract
Robotics
ExoStack: A Modular and Reconfigurable Software Framework for Wearable Robotics Using ROS 2
Wearable robots depend on a software chain that links body-worn sensing to gait interpretation, assistance generation, and actuation. Personalization further requires each measured response to remain associated with the assistance parameters that generated it. This paper presents ExoStack, a modular ROS 2 framework for implementing that chain across embedded hubs and a host computer. Its Embedded Sensing and Actuation (ESA) library configures ESP32 boards as microROS sensing and actuation hubs. ExoCore supplies multi-hub synchronization, gait-event detection, profile generation, motion planning, cost evaluation, and human-in-the-loop (HIL) optimization as configuration-instantiated nodes. The PASE desktop application edits configurations, launches the processing stages, and visualizes ROS 2 topics. Hardware drivers and algorithm plugins can be added through defined interfaces without modifying the generic processing nodes. We characterize hub and planner timing on three embedded computers and demonstrate reuse on two pneumatic exosuits.
Read the full abstract
Computer Vision
HumanSightBench: A Benchmark for Human Visual Perception in MLLMs
Multimodal large language models (MLLMs) have demonstrated strong performance on knowledge-intensive and reasoning-based vision-language benchmark datasets, but still struggle to solve the visual questions that people can solve easily. Evaluating the differences between MLLMs and human-level visual perception is challenging due to end-to-end evaluation which combines various skills, or because we are uncertain if individual items are valid. Specifically, observed errors may reflect visual perception, language priors, background knowledge, question ambiguity, and underspecified answers. Our guideline for HumanSightBench is that we construct items that are human-easy by construction and model-hard by evaluation. HumanSightBench contains 2,876 visual questions with short answers across 7 top-level perceptual categories and 21 subcategories. We only include items that pass five inclusion gates: question clarity, answer uniqueness, visual grounding, human solvability, and text-only shortcut filtering. According to the protocol, errors are defined as incorrect answers on human-validated visual tasks with the evaluated interface. The inclusion gates are intended to reduce confounds from ambiguity and external knowledge. The best pass@3 score is 65.6% across eight evaluated MLLMs. No evaluated model exceeds 27.5% on Counting. These results identify capability gaps that are hidden by overall scores and can help future training experiments and held-out evaluation.
Read the full abstract
Distributed Computing
Evolving Infra: Agent-Adaptive LLM Serving at Scale
Agentic workloads are a major source of LLM inference demand. Existing prefill–decode (PD) disaggregated serving systems offer limited flexibility for runtime adaptation of compute allocation and KV cache management, and rely on coarse signals that only partly capture the diverse and dynamic agent workload. These limitations lead to load imbalance between prefill and decode nodes and eviction of KV caches that agents will reuse. We present Evolving Infra, an agent-adaptive serving framework that adapts compute allocation to agent workloads and KV cache management to agent context management at runtime. We decouple compute allocation from key–value (KV) cache management, allowing nodes to switch efficiently between prefill and decode. Building on this design, an online planner matches the PD split to workload composition, while an agent-aware distributed KV manager guides cache eviction and transfer with signals from agent context management. Across coding, math, and computer-use tasks with GLM-5.2 and Kimi K2.6 on up to 256 GB300 GPUs, Evolving Infra reduces mean end-to-end request latency and P95 TTFT by up to 4.1x and 14x over Dynamo, NVIDIA's production framework. We open-source the system implementation of Evolving Infra at https://github.com/mit-han-lab/EvolvingInfra.
Read the full abstract
Materials Science
Atomically Sharp Magnetic Domain Walls beyond Micromagnetics
Atomically narrow magnetic domain walls can arise in ultrathin magnetic films, van der Waals magnets, and systems with reduced effective exchange stiffness due to competing exchange interactions. As their width approaches the atomic lattice spacing, the continuum approximation underlying micromagnetics becomes increasingly unreliable. We investigate the structure and stability of such domain walls in a one-dimensional nearest-neighbor J-K-D spin-lattice model incorporating Heisenberg exchange, uniaxial anisotropy, and Dzyaloshinskii-Moriya interaction (DMI). In the absence of DMI, we demonstrate analytically a continuous transition to an atomically sharp easy-axis wall at the critical exchange-to-anisotropy ratio J/K = 3/2, characterized by the softening of a localized Hessian mode. Atomistic spin-dynamics simulations confirm this transition and reveal that fitting discrete wall profiles with the conventional micromagnetic solution, as commonly done in experimental analyses, underestimates the exchange interaction and overestimates the anisotropy. Finite DMI removes the perfectly collinear wall as a stationary configuration, replacing the transition by a smooth crossover toward a strongly localized but canted wall that approaches the collinear easy-axis configuration only asymptotically in the strong-anisotropy limit. We derive an analytical expression for the DMI-induced canting in this regime and demonstrate its strongly enhanced canting response near the critical ratio. These findings establish the limitations of micromagnetic descriptions of atomically narrow domain walls and suggest opportunities for controlling their structure through anisotropy and DMI.
Read the full abstract
Combinatorics
Upper bounds on all-terminal reliability polynomials in terms of cycle basis lengths
Let $G=(V(G),E(G))$ be a connected multigraph with $n$ vertices and $m$ edges. The all-terminal reliability polynomial of $G$ can be written as $R_G(q)=(1-q)^{n-1}\sum\limits_{i=0}^{d}H_iq^i$ where $d=m-n+1$ is the cycle rank, each edge fails independently with probability $q\in[0,1]$, and $H_0,\ldots,H_d$ are the associated coefficients. A cycle basis, which consists of cycles that form a basis of the cycle space of a graph, is an important tool for characterizing its cycle structure. The structural properties of cycle bases, together with the associated length optimization problems and construction algorithms, have been extensively studied. In this context, Colbourn posed the following open problem, which concerns upper bounds on the reliability coefficients in terms of cycle-basis lengths: For all-terminal reliability, is it true that if $G$ has a cycle basis containing cycles of lengths $c_1,\ldots,\allowbreak c_{m-n+1}$, then $H_i \le\sum\limits_{\substack{I\subseteq\{1,\ldots,m-n+1\},|I|=i}}\prod\limits_{j\in I}(c_j-1)$? In this paper, we establish a result that resolves this open problem.
Read the full abstract
Theoretical Economics
Inequality-Aware Regulation
I study regulation of a screening monopolist when the regulator cares about the distribution of surplus across heterogeneous consumers and the firm. Consumers privately know their willingness to pay for quality, and the firm privately knows its production costs. Regulatory contracts specify quality-price options that the firm must offer. I show that when the regulator gives greater weight to consumers with lower willingness to pay, baseline regulation is optimal: the regulator requires affordable basic options but leaves the firm free to design and price premium options. Under strong consumer-side redistributive concerns, a single required basic option suffices. The regulator uses the firm's incentive to extract surplus from premium buyers to support low regulated prices for basic options.
Read the full abstract
Artificial Intelligence
Reconfigurable Action Theories: A Formal Foundation for Dynamically Composable Agent Harnesses
Action theories typically fix their vocabulary and causal laws, whereas agent harnesses can change their tools, providers, and policies during execution. We introduce Reconfigurable Action Theories (RAT), in which actions can change the action theory itself. A theory module in RAT contains a vocabulary, causal laws, and an initializer. A RAT configuration records the active modules and the world state. Module loading and unloading are represented by actions governed by ordinary causal laws. RAT retains the standard causal action semantics of its language fragment when the active module set is fixed. We give sufficient conditions for at most one next configuration, preservation of existing behavior when a module is added, and equal results when modules are loaded in either order. We establish the computational complexity of reasoning tasks in RAT and translate finite RAT systems into nonmonotonic causal theories and Answer Set Programming (ASP), preserving bounded executions. Experiments compare finite RAT models with executions of official DeepSeek Harness, Pi, and OpenHands implementations. RAT provides a formal basis for checking how component changes affect a harness's available actions, behavior, and reachable goals.
Read the full abstract
Computational Engineering
Physics-Informed Sinusoidal Representation Networks for Damage Identification in Ultrasonic Guided Wave Structural Health Monitoring
Ultrasonic guided wave (UGW) inspection has become an effective method in structural health monitoring (SHM). While machine learning has enhanced damage detection capabilities, purely data-driven models remain constrained by extensive labeled datasets and limited physical interpretability. Standard multi-layer perceptrons (MLPs) further suffer from spectral bias (F-Principle) in high-frequency regimes, prioritizing low-frequency components while failing to resolve the high-frequency oscillations critical for UGW reconstruction. Physics-Informed Sinusoidal Representation Networks (PI-SIRENs) address these limitations by embedding governing partial differential equations directly into the training process. Building upon SIRENs, which utilize periodic activation functions to inherently capture high-frequency spectral content, the proposed framework is designed to operate effectively in sparse ultrasonic measurement regimes. This work introduces a frequency-domain PI-SIREN framework tailored for the Mindlin-Reissner plate theory to reconstruct ultrasonic wavefields without temporal discretization. The model parameters are optimized using a hybrid strategy comprising three phases: first-order Adam, residual-adaptive refinement (RAR) and quasi-Newton L-BFGS. Numerical and experimental evaluations confirm that the model serves as a physics-consistent baseline derived from sparse data, functioning as a computationally efficient surrogate for damage identification in SHM and non-destructive testing (NDT). Integrating the surrogate into a damage identification pipeline detects and localizes a milled notch from sparse experimental measurements with a localization error of 1 % of the plate diagonal. In contrast, data-driven benchmarks and MLPs with hyperbolic tangent activation functions, with and without Fourier feature embedding, are unable to identify damage due to higher reconstruction errors.
Read the full abstract
Analysis of PDEs
On the Abels–Garcke–Grün Model for Incompressible Two-Phase Flows with Unmatched Densities: Phase Separation and Rayleigh–Taylor Instability
Instability phenomena are ubiquitous in multi-fluid flows. For binary fluid mixtures, phase separation may occur under specific conditions, in which a homogeneous state becomes unstable and spontaneously segregates into different phases, leading to the formation of distinct patterns. Furthermore, when a heavier fluid is superposed over a lighter one in a gravitational field, the fluid interface can be sensitive to perturbations that trigger the Rayleigh–Taylor (RT) instability, i.e., the lighter fluid penetrates upward into the heavier fluid against gravity. We investigate such instability phenomena and the inhibiting conditions for incompressible, immiscible two-phase flows with unmatched densities, within the framework of a diffuse-interface model, which is called the Abels–Garcke–Grün (AGG) model. More precisely, we adopt energy methods to establish several stability/instability conditions for the perturbed system of the AGG model, which is obtained by slightly perturbing the equilibrium profile $(\mathbf{0},\overline{\varphi})$, where $\overline{\varphi}=\overline{\varphi}(x_3)$ depends solely on the vertical coordinate $x_3$. Notably, for a constant equilibrium profile $\overline{\varphi}=\alpha\in(-1,1)$ satisfying $\Psi''(\alpha)<0$, we establish a threshold for stability and instability of the phase-separation problem. Similar stability results are also established for the perturbed system with $\overline{\varphi}$ satisfying the RT instability condition in the presence of gravity. In particular, if the phase-separation condition fails and $\partial_{x_3}\overline{\varphi}$ is a constant, a larger value of $\partial_{x_3}\overline{\varphi}$, a greater interfacial thickness and a higher surface energy density contribute to inhibiting RT instability.
Read the full abstract
Rings and Algebras
A Note on Similarity Classes From Atomic Factorizations in Domains
We construct an example of a non-Archimedean valued skew field k, with elements a and b of distinct absolute value such that there are no p, q $\in$ k[x] (x a central indeterminate) such that (x -b)(x -a) = pq, p similar to x -a, and q similar to x -b. The obstruction lies in the non-existence of a solution in k to Sylvester's equation at -tb = 1. We also disprove a 1963 result by Cohn (also reproduced in Cohn's 2006 monograph), by constructing a domain with similar elements a and b with a an atom and b not a product of atoms (resp., a product of two atoms, one of them central).
Read the full abstract
Distributed Computing
RecoGEM: A Serving System for Production-Scale Generative Recommendation
Generative recommendation (GR) is moving industrial recommender systems (RecSys) from scoring candidate items to autoregressively generating item identifiers. This shift promises higher recommendation quality, but makes serving substantially harder: each request executes a short sequence of dependent decoding steps that explore a large item space and select promising candidates on the latency-critical path. GR not only creates structural mismatches with conventional RecSys pipelines, but also challenges the architectural and optimization assumptions of LLM serving stacks, making direct adoption of existing systems difficult. We present RecoGEM, our production GR serving system. RecoGEM uses a runtime–engine decoupling architecture to move GR-specific serving responsibilities, such as candidate-state transitions and live artifact updates, to a dedicated runtime. Its execution engine exploits GR's short token sequences, large candidate populations, and predictable step shapes to optimize self-attention, candidate selection, and execution planning. RecoGEM has been deployed for over nine months across our production lines, serving applications with hundreds of millions of users and supporting more than ten GR model families. On our OneModel production workloads, RecoGEM reaches over 1,000 QPS per serving instance with P99 latency below 35 ms and a 2.88$\times$ throughput improvement over representative baselines.
Read the full abstract
Robotics
Be My Eye: Learning to See Beyond a Robot's Own Perspective
Robots operating in the real world are inherently subject to partial observability, particularly in multi-robot collaboration, where individual observations may be insufficient for effective task execution. A key challenge is leveraging complementary observations from partner robots to support collaborative decision-making. We argue that information sharing should go beyond passively transmitting raw observations or generic visual features. Instead, robots should selectively encode task-relevant information according to task objectives and execution progress. To this end, we propose a task-oriented active context sharing framework that transforms robot observations into compact representations, preserving critical information under constrained communication budgets. The framework adopts a two-stage training paradigm. In the first stage, onboard observations and task instructions are jointly encoded into compact context representations. Task-oriented future prediction and soft task-progress correspondence learning guide this collaboration-agnostic compression, preserving information about task objectives and execution progress. In the second stage, the learned representations are integrated into a pretrained Vision-Language-Action (VLA) policy, enabling bidirectional context exchange. Each robot combines complementary partner information with local observations to guide action generation. Action supervision jointly refines the context representations and policy, aligning information sharing with collaborative decision-making. Controlled experiments demonstrate substantial performance gains under constrained communication budgets, while three real-world experiments validate the framework in complex dual-robot tasks. These results highlight a shift from passive visual transmission toward active, task-oriented context sharing that directly supports collaborative decision-making.
Read the full abstract
High Energy Physics (Theory)
Zeta function in Coulomb background
We calculate the one-loop vacuum energy of a massive scalar field confined to the interior of a sphere with Dirichlet boundary conditions and subject to a Coulomb background potential $\alpha/r$. The spectrum is determined by the zeros of a confluent hypergeometric (Kummer) function, and the corresponding zeta function is constructed and analytically continued to $s=-1/2$. The renormalization is performed by subtracting the divergent part of the zeta function, defined through the heat kernel expansion, which removes the non-decreasing powers of the mass and leaves a finite, physically normalized vacuum energy. While the heat kernel coefficients for the pure Bessel (Coulomb-free) case are well known, the Coulomb contributions to the coefficients are not; we determine them by matching the analytic continuation of the zeta function to the general form of the divergent part, obtaining terms proportional to $\alpha$ and $\alpha^2$. A key technical point is that the uniform asymptotic expansion of the mode generating function cannot be used in full; a part must be retained unexpanded, and an integral representation of the digamma function is used to carry out the analytic continuation. In the infinite-volume limit the renormalized vacuum energy tends to a constant $E_0^{ren,\infty}(\alpha,m)=\alpha e(\alpha/m)$, with a dimensionless function $e$ that depends only on the ratio $\al/m$. This limit shows that a finite, physically meaningful renormalized vacuum energy can be defined for a massive scalar field in the background of a Coulomb source. For $m\to\infty$ it vanishes in accordance with the normalization condition, while for $m\to0$ it diverges, so that the present calculation does not apply to a massless field, pointing to the need of another vacuum state in that case.
Read the full abstract
Artificial Intelligence
Depth as a Candidate Source: Portfolio Allocation for Recurrent Test-Time Scaling in Large Language Models
Recurrent latent reasoning in large lanugage models (LLMs) scales test-time computation by increasing recurrent depth, naturally framing inference as a problem of deciding when to stop. We identify a previously overlooked limitation of this single-depth view through systematic preliminary analysis: deeper recurrence can lose correct solutions found at shallower depths, while depth-specific success sets remain broadly non-nested even after controlling for marginal accuracy. This suggests that depth determines not only computation cost, but also access to distinct candidate solutions. Motivated by this finding, we propose Depth Portfolio Allocation (DPA), which reformulates recurrent test-time scaling as budgeted allocation across depth-specific candidate sources. DPA supports both fixed portfolios and feedback-guided sequential allocation under a shared inference budget. Experiments on GSM8K, SVAMP, MultiArith, and MBPP show that mixed-depth portfolios expand oracle coverage under matched candidate counts and nominal costs, while feedback-guided allocation generally matches or improves uniform allocation and can reduce computation in high-budget settings. Code and data are avaible at : https://anonymous.4open.science/r/LLM-latent-B7BC/.
Read the full abstract
Optics
Optical frequency combs on thin-film lithium niobate: from principles to applications
Optical frequency combs, consisting of mutually coherent and equally spaced spectral lines, provide a powerful means of synthesizing, distributing, and processing optical frequencies on chip. Among integrated photonic platforms, thin-film lithium niobate (TFLN) is particularly attractive for comb generation because it combines strong electro-optic (EO) functionality, accessible $\chi^{(2)}$ and $\chi^{(3)}$ nonlinearities, low-loss nanophotonic confinement, and versatile dispersion engineering. This review summarizes the physical foundations and representative realizations of TFLN combs, and discusses their applications in optical communication, microwave photonics, optical computing, and precision metrology. The integration of nonlinear functionality, EO control, and passive photonic components is expected to advance compact, energy-efficient comb sources and broaden the utility of TFLN in integrated photonics and quantum optics.