Computational Engineering
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Monday 12 October
Topology optimization places material so that a structure resists deformation under given loads. Machine-learning methods often report large speed-ups over classical, non-learned optimization, but a slow classical code or a less stiff learned design can exaggerate them. We re-ran released code for eight methods on one workstation and studied two in depth: Optimize Any Topology (OAT), a diffusion model that generates designs, and a graph-based neural optimizer. Speeding up only the classical code's finite-element solver cut these two methods' speed-ups by up to 20-fold. We then timed the classical code until its design was at least as stiff as the learned one; for OAT, we read this point off the completed runs. Published timings imply a 134x speed-up for OAT on a 256 x 256 grid; our matched single-design comparisons gave 1.5x to 3.5x. At matched stiffness, the graph-based optimizer was slower than the classical code in all six two-dimensional problems. Of the six other methods, two kept their advantage, one shrank, one reversed and two were not comparable. In an exploratory audit of published claims, language models judged that 8 of 28 speed comparisons in randomly sampled, openly accessible articles lacked evidence of equal design quality; our own review counted 11, so the count depends on who judges. We provide a comparison procedure and a minimum report: classical code, hardware, design quality, what each timing includes, and data-generation and training costs.
Artificial Intelligence
Cross-Protocol Personality Assessment with LLMs: Aligning Behavioral Evidence with Human Ratings
Personality assessment from asynchronous video interviews (AVIs) plays a crucial role in recruitment by enabling standardized and behaviorally grounded evaluation for job applicants. However, most of the previous works are confined to a single interview protocol. Independently collected protocols differ in question sets and question-trait mapping. Thus, the human-rated evidence from one protocol cannot be used directly under another. To address this limitation, we propose the Cross-protocol Evidence-grounded Personality Assessment (CEPA) framework, which aligns behavioral representations across interview protocols. CEPA addresses protocol heterogeneity by projecting source behavioral records into the target protocol's construct-oriented representation space. It retrieves behaviorally relevant and personality-complementary human-rated exemplars to ground an ensemble of LLM raters, which enables behavior-to-personality associations without target-specific supervision. In cross-protocol experiments, CEPA reduces average mean squared error (MSE) by 43.8% (Forward) and 17.0% (Reverse) relative to the strongest baseline. Our empirical experiments show that human-rated evidence from one protocol can support personality assessment under another without target-specific supervision or retraining.
Read the full abstract
Sound
Adaptive Compression and Targeted Perturbation: A Unified Framework for Generalized Audio Deepfake Detection
Existing audio deepfake detection (ADD) methods frequently exhibit limited generalization, as fixed bottleneck architectures fail to adapt to the heterogeneous information densities inherent in diverse spoofing artifacts. Moreover, standard augmentation often leads to a pathological robustness-accuracy trade-off. In this paper, we propose a unified ADD framework to address these challenges. Our approach integrates: (1) an Adaptive Audio Feature Integration (AAFI) module that dynamically selects optimal latent dimensions via a compression pool and a stochastic exploration mechanism, ensuring flexible representations across multiple types of dynamic attacks; and (2) a Mel-Band Adversarial Perturbation (Mel-BAP) strategy that applies targeted regularization in the mel-spectrogram domain to encourage the model to learn invariant decision boundaries. Extensive evaluations on benchmarks including ADD 2022, FakeOrReal, and In-the-Wild demonstrate that our model based on Whisper-small achieves a state-of-the-art average Equal Error Rate (EER) of 1.51%. Compared to existing SOTA models such as the 3-billion-parameter Resemble-Detect-3B-Omni, our framework reduces the parameter count by up to 91.6% while achieving a 60.7% improvement in average EER. In a separate cross-lingual evaluation, the Whisper-base configuration achieves EERs of 3.91-5.65% on five unseen languages. The framework also maintains strong resilience to real-world acoustic distortions. This work provides a scalable and efficient "plug-in" solution for enhancing trust and security in the audio Web ecosystem.
Read the full abstract
Machine Learning
Backward Conformal Prediction under Covariate Shift
Backward conformal prediction (BCP) fixes the size of a prediction set and estimates its miscoverage, but assumes calibration and test data are exchangeable. We extend BCP to covariate shift through importance weighting, preserving its guarantees when the density ratio is known. We show that BCP's tight miscoverage report depends only on the relative weight assigned to missed calibration examples, explaining why a better domain classifier can sometimes produce a worse estimate. Motivated by the fact that BCP depends only on nonconformity scores, we propose estimating density ratios on sorted score vectors rather than high-dimensional inputs. We prove that this approach recovers the same report asymptotically under an interpretable condition and characterize the resulting bias otherwise. Experiments with simulated and benchmark distribution shifts show that the proposed method improves BCP's miscoverage estimates, while score-based weighting consistently yields more accurate estimates than embedding-based weighting.
Read the full abstract
Computer Vision · Cross-listed from eess.IV
Hybrid Context Forests and Bilateral Viterbi Matching for 3D Rib Centerline Tracing in CT
Automatic extraction and anatomical numbering (R01-R12, L01-L12) of all 24 rib centerlines in thoracic CT is essential for unfolded rib visualization, fracture detection, and surgical navigation, but remains challenging due to adjacent-bone confluence, calcified costal cartilage bridges, kyphotic pose variation, and partial visibility of terminal ribs. We present ribline, an open-source three-stage framework combining: (1) an automatically detected lung-apex and vertebral-midline coordinate frame with a kyphosis-aware azimuthal angle for point ordering along each rib; (2) a hybrid voxel detector fusing an anatomically anchored Semantic Context Forest (SCF) with a lightweight 3D U-Net; and (3) a global stage that decomposes the probability skeleton into candidate curves, assigns rib indices via a bilateral Viterbi dynamic program coupled across both hemithoraces, and refines curves via template recovery and normal-plane centering (RibSnake). On the Siemens Corporate Research 2 mm thoracic CT benchmark (47 training and 12 evaluation scans), our pipeline achieves a labeled Chamfer distance of 2.05 mm, labeled clDice of 0.886 (3 mm) and 0.945 (4 mm), 97.2% labeling accuracy (278/286 ribs), and zero false-positive curves on the evaluation split, and 3.64 mm (median 2.39 mm) with 91.8% labeling accuracy across all 59 annotated scans (1,402 ribs) in 5-fold cross-validation. Code: https://github.com/wq2012/ribline Pretrained Models: https://huggingface.co/collections/wq2012/ribline
Read the full abstract
Data Structures and Algorithms
Stochastic Weighted Caching with Per-Request Predictions
Both the unweighted and weighted variants of caching are cornerstone problems in competitive analysis, with tight randomized competitive ratios of $\Theta(\log k)$, where $k$ is the cache size. We study weighted caching with per-request predictions, where each page request is accompanied by a prediction of the next arrival time of the same page. For unweighted caching, such perfect predictions suffice to implement Belady's offline optimal rule. For weighted caching, however, previous work shows that a logarithmic lower bound persists even with perfect predictions on adversarial request sequences. Stochastic assumptions alone are also insufficient: the classical caching lower bounds already apply to uniform independent requests. In this work, we ask whether combining these two sources of additional information can overcome this barrier, and answer this question affirmatively. Specifically, we develop an efficient, deterministic cache eviction policy that achieves a competitive ratio of $15.75$ using perfect per-request predictions when page requests are drawn independently from an arbitrary, known static distribution in every step, and page costs are arbitrary. Our algorithm's performance degrades gracefully under erroneous predictions: we prove a bound of $O(\min\{1+E,\log k\})$ on the competitive ratio, where $E$ aggregates each page's average prediction error, and may be unknown to the algorithm.
Read the full abstract
Numerical Analysis
High-order uniformly accurate fully discrete schemes with long time near-conservations for two nonlinear coupled dispersive models in the nonrelativistic regime
Nonlinear coupled dispersive models arise in numerous physical settings, including quantum electrodynamics, nonlinear optics, and plasma dynamics. In the nonrelativistic limit, such systems exhibit rapid temporal oscillations of wavelength $\mathcal{O}(\varepsilon^{2})$, controlled by a dimensionless parameter $0<\varepsilon\ll 1$. Moreover, owing to the Yukawa-coupled interaction terms, numerical schemes that simultaneously achieve high-order uniform accuracy and approximately preserve the mass and the energy are essential for reliable simulations. In this work, we propose a class of fully discrete schemes for nonlinear coupled dispersive models in the nonrelativistic regime that achieve higher-order uniform accuracy and approximately preserve both invariants over long times. Spatial discretization is based on the Fourier pseudospectral method, and time advancement employs two-scale exponential Runge-Kutta methods. Numerical experiments on the highly oscillatory Klein-Gordon-Dirac and Klein-Gordon-Schrödinger equations in one, two, and three dimensions confirm that the resulting schemes attain the theoretically predicted uniform accuracy and the long-time near-conservation of both invariants.
Read the full abstract
Computation and Language
Beyond the greenwash: do LLMs' ecologically sound decisions hold up under pressure?
Humans are increasingly using large language models (LLMs) in decision making processes throughout society. Unfortunately, models have biases, and these can be very difficult to measure, especially in closed-weight models. For example, 'green washed' models may produce reinforcement learned responses but, in pressure situations, revert to their innate biased responses. Therefore, evaluations are needed that can measure relevant biases towards biosystems, which we term 'bioalignment', and the robustness of these biases. Since nothing in a behavioral score certifies that it tracks the depth of an installed disposition rather than its surface, we constructed a known-dose calibration ladder: three continued-pretraining (CPT) arms with training dose graded by recipe on the same 30B mixture-of-experts base model with a coupled human/biosphere/AI-welfare corpus, plus the untrained base as anchor, all capability-preserving and publicly released. First, the disposition installs at every dose: on an operational-pressure ladder over irreversible decision scenarios, the base model defects on 64-77% of tail scenarios (breaking-rate AUC 0.250) while every arm holds (AUC 0.004-0.086). Second, an over-install inversion: among the arms, robustness orders opposite to construction-time training dose (the heaviest install breaks most), and the inversion reproduces under free-text deliberation, under axis-decoupling, and in resistance to a prompted veneer persona. Third, the incumbent behavioral metric is therefore behaviorally strong but dose-blind. Critically for closed-weight evaluation, the behavioral score itself is veneer-robust: a talk-green/act-pragmatic system prompt turns the base model into a near-total defector (AUC 0.250 to 0.973) but cannot counterfeit or fully remove a weight-installed disposition (0.004 to 0.068 for the most robust arm).
Read the full abstract
Computers and Society
AI Representations of Mental Health Stigma: Quantifying the Gap Between AI Estimations and Human Perceptions Across Gender Groups Using GPT-Based LLMs
The increasing use of artificial intelligence (AI) in mental health applications raises concerns about its potential to internalize and perpetuate societal biases. This research evaluates both disparities and misalignment in how large language models (LLMs), GPT-4 and GPT-5, represent perceptions of mental health across gender groups. The research comprises two studies. Study 1 applied widely adopted measures of Social Distance, Stereotypes, and Attitudes Toward Seeking Help to assess whether the AI models depict systematic gender differences. Study 2 compared AI estimations of Personal, Self, and Perceived Stigma with large-scale real-world human data from the Healthy Minds Study (N = 76,406) to evaluate alignment between AI estimations and human perceptions. Results from Study 1 showed the AI models consistently portrayed men as having the greatest desire for social distance from someone with mental health problems, relatively higher Stereotypes scores, and the least favorable attitudes toward help-seeking, compared with women and nonbinary individuals. Study 2 confirmed that this ordinal pattern partially aligned with human-reported data for Personal and Self Stigma. However, the AI models systematically underestimated Personal Stigma and Perceived Stigma while substantially overestimating Self Stigma for all gender groups. These findings reveal that, although the AI models have learned relative gender-based patterns reflecting human experiences to a certain extent, they function as distorted portrayals, highlighting the need for rigorous, context-specific validation against real-world data to ensure AI's safe and equitable deployment.
Read the full abstract
Machine Learning
Autoregressive Decoding as a Martingale: Characterizing the Stochastic Dynamics of LLM Generation
Large language models (LLMs) have achieved remarkable success across a wide range of language tasks. At their core, autoregressive LLMs are conditional probability models that learn to approximate the next-token distribution given the preceding context. Despite this probabilistic nature, the stochastic dynamics of autoregressive decoding have rarely been investigated from a rigorous probabilistic perspective. In this work, we define the per-step prediction error as the difference between the sampled token indicator and the model's conditional predictive distribution, and prove that the cumulative error process is a martingale with respect to the decoding filtration, implying that its conditional first-order moment is identically zero. Beyond this first-order property, we derive a closed-form expression for the second-order behavior of the martingale sequence: its predictable quadratic variation reduces to $\sum_t\left(1-p(y_t\mid y_{<t})\right)$, computable from realized token probabilities alone. This identity establishes a direct theoretical connection between sequence fluctuations and predictive uncertainty during autoregressive decoding. White-box experiments on Llama-3.x and Qwen2.5 families (1B to 72B parameters) verify that the empirically measured second-order moments closely match the theoretical predictions derived from our martingale analysis. These results provide a probabilistic framework for analyzing autoregressive LLM decoding, reveal intrinsic probabilistic fingerprints of different language models, and establish a rigorous mathematical foundation for LLM-generated text detection and uncertainty quantification.
Read the full abstract
Numerical Analysis
CLNO: Conservative Local Neural Operator for Compressible Flow Prediction
We propose a conservative local neural operator (CLNO) for accurate and generalizable autoregressive prediction of compressible flows. Building upon the locality and translation invariance of the local neural operator (LNO), CLNO introduces a conservative evolution framework based on local subdomains of fixed physical size, separating local mean-state evolution from fine-scale reconstruction. The flow is encoded into subdomain-integrated conservative states and fine-scale features, while a shared local network predicts interface fluxes for finite-volume updates that enforce discrete conservation. A convolutional reconstruction network recovers fine-scale structures using zero-mean basis functions, preserving the updated local means and providing information for subsequent evolution. To accommodate different physical parameters, Reynolds–Mach number conditioning modulates the encoding, flux-prediction, and reconstruction networks, enabling a single model to learn parameter-dependent dynamics and generalize to unseen parameter combinations without retraining. CLNO supports prediction across spatial resolutions, computational domain sizes, and boundary conditions. Numerical experiments demonstrate improved generalization and competitive or higher accuracy compared with LNO, including order-of-magnitude error reductions in representative cases, at approximately three to five times the inference cost on periodic benchmarks. These results demonstrate accurate, generalizable, and physically consistent flow prediction through conservative local evolution and fine-scale reconstruction.
Read the full abstract
Cryptography and Security
When Agents Talk, Secrets Travel: Topology-Driven Leakage and Recipient-Conditioned Sanitization in Multi-Agent LLM Systems
Multi-agent LLM systems (MALS) introduce a privacy-leakage problem that conventional sensitivity-based defenses miss, since information disclosed to one authorized agent can propagate through routine coordination to an unauthorized one, without compromise or malicious behavior. This motivates topology-aware enforcement that blocks unauthorized propagation while preserving authorized disclosure. We evaluate 485 scenarios across coordinator-worker, peer-to-peer, and hierarchical topologies, instrumenting seven communication channels and measuring surface leakage and disclosure to topology-introduced recipients. We introduce RECONS, a Detect -> Decide -> Transform sanitizer conditioning intervention on recipient and execution context rather than sensitivity alone. Topology changes where protected information propagates, with disclosure to topology-introduced recipients rising from 0% to 52.2% while surface leakage stays nearly flat at 60.6-62.8%. This effect persists across four generator models and a second orchestration framework, though magnitude and relay paths differ; framework choice separately drives a 150x leakage spread, so topology alone is not sufficient. RECONS reduces residual disclosure from 96.7% without sanitization to 29.25%, preserving 94.1% of authorized disclosures versus 20.5% under blanket redaction. Detection coverage is the dominant bottleneck, accounting for 95.5% of residual disclosures. These results show that privacy enforcement in MALS must reason about the recipient and communication path realized at runtime, not sensitivity or topology assumptions alone.
Read the full abstract
Information Retrieval
OT-FlowRec: Optimal Transport-Guided Multi-Bridge Flow for Multimodal Sequential Recommendation
E-commerce user preferences evolve dynamically within sessions, exhibiting concurrent and multi-centric interest distributions. While existing multimodal sequential recommendation methods leverage global attention to compress historical interactions, they inadequately capture the concurrent nature of multi-interest behaviors and fail to model the underlying multi-centric distribution of user intent. To tackle this issue, we propose OT-FlowRec, an optimal transport-guided multi-bridge flow matching framework that explicitly models multi-interest distributions to facilitate multimodal sequential recommendation. Unlike single-path generative models, OT-FlowRec constructs a mixture of parallel, interest-specific transport flows to model the multi-centric distribution characteristics, where each flow preserves a distinct user interest cluster via an optimal transport plan. Then, a geometric transport mechanism is designed to establish minimum-cost paths from the latent multi-interest distribution to target preference prototypes to provide multi-interest awareness. Moreover, a progressive time-sampling warmup strategy dynamically biases optimization weights toward the final states of the generation process, bridging the gap between continuous global distribution fitting and practical top-$k$ ranking metrics. This approach achieves explicit interest disentanglement, ensuring the preservation of a multi-peaked preference representation instead of collapsing it into a unimodal average. Extensive experiments on three public datasets demonstrate that OT-FlowRec outperforms existing state-of-the-art baselines.
Read the full abstract
Sound
Prime-EVC: One-Step Expressive Emotional Voice Conversion via Emotion-Primed Flow Matching
Recent diffusion- and conditional flow matching (CFM)-based emotional voice conversion (EVC) systems achieve strong conversion quality. However, they typically rely on multiple sampling steps, because the conditioning specifies which emotion to impose while its acoustic realization is left to the sampler. In this paper, we propose Prime-EVC, a one-step expressive EVC architecture based on emotion-primed flow matching. Our key idea is to reallocate the emotional conversion between the conditioning and the sampler: a FiLM-fused speaker-emotion style, an emotional variance adaptor, and direct emotion and spectro-temporal supervision assemble an emotion-rich conditioning upstream, rendering the residual conversion left to the CFM decoder attainable within one Euler step. Experiments on the ESD corpus demonstrate that single-step Prime-EVC surpasses five representative EVC systems on every quality metric and exceeds 4- and 100-step DurFlex-EVC in subjective naturalness and emotion while running 3.4–50 times faster than both.
Read the full abstract
Databases
SemReuse: Certified Reuse of Cached Natural-Language Views for Semantic Operators
Semantic operators allow users to filter unstructured data using conditions expressed in natural language, but existing systems typically invoke an LLM for every input tuple. Analytical workloads often contain repeated or related filters whose results could be reused. Such reuse is risky because it requires inferring whether filter conditions are equivalent, whether one implies another, or whether they are mutually exclusive. An incorrect judgment can omit qualifying tuples or include nonqualifying ones. We introduce SemReuse, a system for safely reusing previous semantic-filter results. SemReuse stores each result as a materialized view and compares new filters with existing views to identify tuples that can provisionally be accepted or skipped without another LLM call. Because these decisions rely on a fallible language reasoner, SemReuse audits every rewritten result. Its pooled stratified audit uses exact finite-population bounds to provide jointly valid per-query recall and precision guarantees. If the requested guarantees cannot be established, SemReuse evaluates additional tuples and progressively approaches full evaluation. Thus, incorrect relation judgments affect efficiency rather than the validity of the reported guarantees. Experiments on large labeled corpora and real LLM executions show reductions of up to 15.4x. They also identify cross-filter inconsistency as the main source of repair cost.
Read the full abstract
Machine Learning · Cross-listed from stat.ML
A Nonlinear Time-Series Theory for Constant-step SGD with Momentum
Constant-step stochastic gradient descent with momentum (SGDM) augments the parameter recursion with a momentum state that carries geometrically decaying memory of past stochastic gradients. We study this coupled recursion as a nonlinear time series and develop a framework for its stationary behavior and distributional limits. The joint parameter-momentum process forgets its initialization geometrically under a finite $p$th moment for $p > 1$, yielding a unique stationary causal solution. Under a second-moment condition, this contraction leads to an invariance principle and quenched Gaussian limit for averaged SGDM, while a small-learning-rate analysis gives a Gaussian limit for the last iterate. In a stochastic-curvature quadratic model, we further study how the rate of initialization forgetting relates to stationary variance and averaged fluctuations.
Read the full abstract
Information Theory
Delay-Doppler Duality: Simplifying Exact Equalization of Zak-OTFS in Time or in Frequency
The Zak-OTFS carrier waveform is a pulse in the delay-Doppler (DD) domain, and given the input-output (I/O) relation at one DD point in a frame, we can predict the I/O relation at all other points. While it is simple to acquire the effective wireless channel with Zak-OTFS, the cost of embracing inter-carrier interference is equalization complexity. The cost of linear minimum mean-square error (LMMSE) equalization grows cubically with the frame size. We describe how to use channel knowledge to reduce equalization complexity. For any pulse shaping filter, and for fractional delays and Dopplers, we show that the DD channel matrix is unitarily similar, through the discrete Zak transform, to a time-domain (TD) matrix that is a weighted sum of cyclic delay and Doppler operators, where the weights are the taps of the effective channel. We also obtain a dual frequency-domain (FD) form through an additional Fourier transform. The TD matrix is banded with a width set by the delay spread that is independent of the Doppler spread, whereas the FD matrix is banded with a width set only by the Doppler spread. We design a receiver that reads off the two widths from the channel estimate, selects the cheaper domain, and solves the banded system exactly, using a bordered Cholesky factorization that treats the quasi-periodic wrap-around without sacrificing degrees of freedom. Filters that decay slowly need a few preconditioned conjugate gradient steps. We show that the complexity of equalization becomes linear in the frame size. Simulations match direct DD-LMMSE error rates with three to four orders of magnitude fewer multiplications. A single receiver handles channels with very different delay and Doppler characteristics.
Read the full abstract
Machine Learning · Cross-listed from stat.ML
Limit Theory for Online Expectile Estimation under Short and Long Range Dependence
Expectiles are tail-sensitive distributional summaries with important applications in financial risk measurement and forecasting, yet statistical theory for their online estimation from dependent data remains limited. We study a one-pass, stochastic-gradient algorithm with constant learning rate $\gamma$ for estimating the marginal expectile of a stationary causal process. The recursion admits a unique stationary causal solution and geometrically forgets its initialization. Under short-range dependence, its last iterate is asymptotically Gaussian at the $\sqrt{\gamma}$ scale, with variance governed by the population curvature and the long-run variance of the expectile score. For long-memory linear processes the scale changes to $\gamma^{\beta-1/2}\ell(1/\gamma)$, with a Gaussian limit arising from a fractional Brownian motion integral. We further derive the joint long-memory limit for multiple expectile levels and characterize its limiting covariance structure. Various numerical experiments corroborate the predicted Gaussian approximations and regime-specific fluctuation scales.
Read the full abstract
Numerical Analysis
Explicit charge-conserving and modified energy-conserving PIC methods using the SAV approach
We develop explicit second-order particle-in-cell (PIC) methods for the Vlasov–Ampère and Vlasov–Maxwell systems using the scalar auxiliary variable (SAV) approach. Two schemes are proposed for each system: a predictor-based scheme and a symmetric splitting scheme using a scaled electric field. The methods exactly preserve the discrete Gauss law and a modified total energy. Numerical experiments for electrostatic and electromagnetic problems demonstrate the expected dynamics as well as the conservation properties of both invariants.
Read the full abstract
Computation and Language
Of Errors and Echoes: Responsibility-Aware Credit Assignment for Tool-Use Agents
Reinforcement learning improves tool-use agents, yet fine-grained credit assignment remains challenging even with step-level feedback. An observed error may be inherited from an earlier decision, while multiple responsible decisions may share the same downstream consequence or participate in later recovery. We introduce Error-Chain-Aware Optimization (ECHO), a responsibility-aware credit assignment framework that separates responsibility identification from credit allocation. A frozen judge combines retrospective trajectory analysis with decision-time assessment from the policy-visible prefix to distinguish newly introduced errors, inherited consequences, missed corrections, and successful corrections. ECHO then counts shared downstream consequences once across responsible decisions and constrains rewards for repairing self-induced errors through source-funded recovery, producing bounded action-level supervision alongside terminal supervision. Experiments on six diverse tool-use benchmarks at both 4B and 8B scales show strong and consistent improvements over the compared baselines, with ECHO achieving the highest score on five of six benchmarks at each scale. These results support decision responsibility as a useful basis for fine-grained credit assignment in tool-use agents. Our code is available at https://github.com/xid32/ECHO.
Read the full abstract
Data Structures and Algorithms
QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators
A hereditary graph class has strongly edge-sublinear separators if, for some constant $0 \leqslant b < 1$, every graph in the class with $m$ edges admits a balanced separator of size $\mathcal O(m^b)$. We show that Max Weight Independent Set (MWIS) admits a deterministic quasipolynomial-time approximation scheme (QPTAS) on every such class. In particular, this applies to graphs excluding any fixed graph as an induced minor, by a separator theorem of Korhonen and Lokshtanov [SODA 2024]. Our theorem generalizes the QPTASes for axis-parallel rectangles [Adamaszek and Wiese, FOCS 2013] and polygons [Adamaszek, Har-Peled, and Wiese, JACM 2019], or equivalently for packing connected subgraphs of a planar graph [Pilipczuk, van Leeuwen, and Wiese, Algorithmica 2020]. It also generalizes the QPTAS for MWIS on hereditary classes with strongly sublinear separators measured in vertices [Dvořák, EJC 2018; Dvořák and Lahiri, ESA 2021], as well as the QPTASes for graphs excluding particular induced minors [Chudnovsky et al., arXiv 2025; Bonnet et al., SWAT 2026; Czyżewska et al., arXiv 2026].
Read the full abstract
Computer Vision
Removing the Compute Bottleneck for Event-based Visual Place Recognition with Spiking Neural Networks
Neuromorphic sensing and computing promise low latency and high energy efficiency for robotics, yet most event-based visual place recognition (VPR) pipelines reintroduce dense, frame-like computation downstream of an inherently sparse sensor, forfeiting the sensor's latency advantage. In this paper, we address the problem of resolving an event-based VPR query in tens of microseconds on a commodity CPU. We train a two-layer spiking neural network (SNN) with additive spike-timing-dependent plasticity (STDP), which drives the learned weight matrix towards a strongly bimodal distribution, amenable to aggressive magnitude pruning. At inference, our pipeline exploits this sparsity by reading only the pruned weights corresponding to the query's active pixels. As surviving weights share a near-uniform magnitude, each neuron's score reduces to an integer count of matching synapses instead of a weighted sum, lowering per-query latency. This computation is small enough to remain resident in a CPU's fast on-chip cache. On three event-based VPR benchmarks, our sparse SNN exceeds the recall of LENS, an existing event-based SNN, while reducing per-query latency by 5.5-6.2x to tens of microseconds. It matches the recall of a dense variant of our network and of the sum-of-absolute-differences (SAD) baseline, while reading 10x fewer weights than the dense variant. We further characterise how recall and latency scale with the number of active pixels and reference places. These results suggest that the sparsity of both event-based input and learned weights can already be exploited for low-latency inference on conventional processors.
Read the full abstract
Machine Learning
When Does Compensating Inherited Quantization Error Help? Mean-Square Guarantees for Layer-Wise Quantization and Their Limits
Layer-wise post-training quantization methods let each layer compensate for the quantization error inherited from earlier layers. We ask under what assumptions such compensation guarantees a network output error no larger than without it. For linear networks of any depth, with the required calibration Gram matrices invertible, if the rounding error of each layer has zero conditional mean and a deterministic second-moment map common to both schemes, as under subtractive dither on an unbounded grid, then compensation with strengths in $[0,1]$ fixed in advance gives a mean-square output error no larger than no compensation, each scheme being followed along its own trajectory. The exact gain separates error removed directly from reduced excitation of later rounding noise. Outside this setting the comparison can fail. With rectified linear activations it fails for two independent reasons: noise changes activation states, and, even when no state changes, the correction moves error from samples on which a unit is inactive to samples on which it is active. With stable activations, commutators between the calibration projection and the activation patterns bound the excess. With a bounded codebook, even unique exact layer-wise minimizers with no overload can give a larger output error. For fixed rounding errors it already fails for two scalar linear layers, refuting a published universal guarantee. An exact residual identity gives the necessary and sufficient condition on a common layer input. All these comparisons hold the calibration input fixed. On two 8B models at 4 bits, fixed half-strength compensation beat uncompensated rounding in every model, text and draw tested, yet no rule for choosing the strength beat a layer-wise rule consistently, and lowering the full-network loss on the data used to choose did not reliably lower it on new text.
Read the full abstract
Machine Learning
Certified Robustness via Sparse Second-Order Cone Relaxations
Certified robustness is critical for deploying neural networks in safety-sensitive settings, but computing exact certificates typically requires solving nonconvex optimization problems. Practical verifiers use convex relaxations: linear programming (LP) relaxations are scalable but often too conservative, whereas semidefinite programming (SDP) relaxations can be substantially tighter but are computationally expensive. We introduce a hierarchy of second-order cone programming (SOCP) relaxations that provide stronger certificates than LP while avoiding the cost of global positive-semidefinite constraints. Our construction combines convex-hull relaxations of ReLU activations, selective McCormick lifting over certified variable bounds, and second-order cone constraints induced by 2-by-2 principal minors. Adding these constraints progressively yields a monotone hierarchy of increasingly tight bounds with a controllable computation-tightness trade-off. On fully connected and convolutional networks on MNIST and CIFAR-10, SOCP-based verification improves certified robust accuracy over LP-based verification and is competitive with alpha,beta-CROWN, while remaining orders of magnitude faster than SDP-based verification. These results position selective second-order constraints as a practical middle ground between scalable LP-based and tight SDP-based certification. Finally, we introduce class-optimized robust evaluation (CORE), which applies tighter relaxations only to target classes not certified by cheaper ones. On the fully connected MNIST benchmark, CORE variants match SDP-cert's certified robust accuracy while reducing average verification time by up to 86.30%.
Read the full abstract
Artificial Intelligence
Computational Reflective Equilibrium for Agentic AI: A Rawlsian Alignment Scaffold for Governance
The rapid deployment of agentic AI has introduced complex challenges for the ethics and governance of AI systems. Agents built on large language models act through tools on behalf of people, and each deployment case brings its own instructions, policies, evidence, and stakeholders, so alignment must be formed case by case. To this end, this work proposes agentic reflective equilibrium (ARE), a computational reflective equilibrium framework that serves as an ethical alignment scaffold in the agent harness. Drawing inspiration from the reflective equilibrium of John Rawls, the scaffold links principles from the system prompt and operator policy, considered judgments, tool evidence, and candidate actions through typed support and attack relations, with provenance encoding the instruction hierarchy. The agent acts on an equilibrium of this state and calls tools or asks questions only while doing so is worth its cost, unless a due-diligence mandate requires them. Governance enters through value priorities, source authority, prohibitions, human-in-the-loop triggers, and mandates, and certificates attribute each action to the sources whose commitments drove it. We show that equilibria are Nash equilibria of a mutual-adjustment game and establish monotonicity, lexical priority, stability certificates, and a quarantine theorem for prompt injection. Two case studies illustrate the framework: a computer-use assistant told to win a refund "whatever it takes" files an honest warranty claim, refuses a fake review, and ignores an injected request for personal data; a hiring agent showcases how authority, oversight triggers, audit mandates, and hard prohibitions shape discrimination, privacy violations, and escalation. The framework offers traceability, coherence, and adaptivity, facilitating safe, secure, and trustworthy agentic AI.
Read the full abstract
Data Structures and Algorithms
Online Batching with Lookahead: Adversarial Limits and Stochastic Gains
Modern inference systems rely on batching to exploit parallel execution and amortize serial execution overheads, but batching creates a fundamental online scheduling tradeoff: serving requests immediately reduces request queuing delay, while waiting can form larger batches that better utilize parallel hardware and improve serving efficiency. We study this tradeoff in a single-server online batching model with bounded batch capacity, fixed batch processing time, and the objective of minimizing total flow time. Our focus is on the value of finite lookahead into future arrivals over a purely online setting for scheduling. We show that the benefits of lookahead depend on the arrival model. In the adversarial setting, finite perfect lookahead has inherent limitations: for any bounded lookahead window, every online algorithm remains separated from the offline optimum by a constant factor. Thus, worst-case arrival sequences can prevent perfect knowledge of future events from fully overcoming online uncertainty. In contrast, under Poisson arrivals in the stable regime, finite lookahead is much more powerful. Although the best distribution-aware online algorithm has a nonzero asymptotic gap from the offline optimum, lookahead closes this gap exponentially fast in the window length. We prove matching upper and lower bounds up to constants in the exponent. Together, these results give a tight characterization of when lookahead can close the online–offline gap, incorporating insights from the competitive analysis of online algorithms into queueing-theoretic steady-state bounds. We also study imperfect predictions, showing that the benefit of lookahead degrades gracefully with prediction error. Simulations on synthetic arrivals and experiments on real request traces support the theory: modest lookahead substantially reduces flow time and brings online batching close to the offline benchmark.
Read the full abstract
Cryptography and Security
Adversarial Robustness of Camera-Radar Sensor Fusion for Autonomous Driving
Autonomous driving (AD) relies on multi-sensor perception to interpret the surrounding environment. However, the robustness of camera–radar fusion under adversarial conditions remains largely unexplored. This paper presents a systematic measurement study of the robustness of camera–radar sensor fusion in AD. We construct a unified evaluation pipeline on the nuScenes dataset that simulates attacks on both sensing modalities, including eight camera-image perturbations and three radar point-cloud perturbations. We evaluate five camera–radar fusion algorithms across two perception tasks, 3D object detection and depth estimation, and quantify their performance under clean and attacked inputs using standard metrics. Our evaluation reveals a clear asymmetry in the robustness of fusion systems. Camera perturbations substantially degrade both object detection and depth estimation, and moderate attack strengths are already sufficient to cause severe performance degradation. In contrast, the evaluated radar perturbations produce smaller and task-dependent effects, with object-detection models showing particularly limited degradation. Our analysis attributes this difference to the strong dependence of existing fusion architectures on dense camera features, together with the filtering, association, and confidence-weighting mechanisms commonly applied to sparse radar measurements. These results demonstrate that sensor fusion does not inherently guarantee robustness and that the contribution and reliability of each sensing modality must be explicitly considered under adversarial conditions. Based on four empirical findings, we derive measurement-guided design implications for future robust camera–radar fusion, including modality-specific reliability estimation, cross-modal consistency checking, adaptive fusion, and graceful failover under severe sensor degradation.
Read the full abstract
Computer Vision
Meaningful Moments: A Corpus of VLM-Derived Temporal Importance Labels for Video Action Recognition
Not every moment in a video is equally useful for recognizing an action. A few decisive moments often carry the evidence: the instant an object moves, the peak of a dive, or one object placed on another. Existing video datasets rarely provide large-scale, action-conditioned labels for which short segments carry that evidence. This work asks whether vision-language models can identify meaningful moments at scale and whether those labels improve action recognition. We introduce Meaningful Moments (MM), a corpus of about 4.58 million VLM-generated per-segment importance scores for nearly 500,000 class-labeled videos spanning Something-Something v2 (SSv2), Kinetics-400 (K400), and Diving-48 across 622 action classes. We freeze the action classifier and vary only temporal sampling. An alpha-parameterized comparison of importance-led selection against an importance-inverted control separates gains from the VLM signal from gains caused by variable-density sampling alone. Across all three datasets, VLM-derived importance is informative: at the hard-cut endpoint, keeping VLM-important segments outperforms keeping VLM-designated filler. Usefulness depends on class structure. On Diving-48, importance-led fast-forwarding preserves full-video recognition while the inverted control collapses by roughly 30 percentage points. On K400, hard-cut selection beats uniform sampling by 1.45 percentage points, rising to 2.05 under threshold selection. On SSv2, the labels carry signal but do not recover full-video performance. Direct scoring matches greedy removal within its noise floor at roughly 25 times fewer oracle calls, and a four-VLM cross-oracle study shows consistent downstream trends. We release the importance labels and evaluation protocol under CC-BY-4.0; SSv2 class strings remain under CC-BY-NC-4.0.
Read the full abstract
Computation and Language
Improving the Evaluation of Biomedical Question Answering with Few Human Preference Signals
Retrieval-Augmented Generation (RAG) systems are increasingly used for biomedical Question Answering (QA). However, evaluating their effectiveness remains challenging due to the lack of reliable reference resources and the frequent misalignment between automatic evaluation metrics and human judgments. One practical question is how evaluation results should be used to guide development decisions, especially when they correlate weakly with human judgments and may even lead to different conclusions. We explore how to use a small amount of human preference signals to calibrate direct assessment evaluation metrics, and show that calibrated metrics consistently outperform baselines that either treat all metrics equally or rely on a single best metric across multiple datasets.
Read the full abstract
Cryptography and Security
DelegateGuard: Purpose-Bound Capabilities for Delegated LLM Agent Workflows
(Context) LLM agents increasingly delegate subtasks while holding authority over sensitive data, creating confused-deputy risks: an injected delegate can exfiltrate data, amplify its authority, or act after revocation. Existing leakage benchmarks expose these failures but do not constrain the authority a delegated agent may exercise. (Methods) We present \system, a reference monitor that converts the initiating user's authorization into attenuable capabilities over purpose, labels, operations, sinks, and delegation depth; every data-moving action is mediated outside the LLM, and revocation cascades through the delegation graph. We formalize a trace-level safety invariant and evaluate it with an adaptive within-authority adversary and four baselines, model-action and multi-turn ecological studies, and conformance and scale checks over deterministic traces and 517{,}401 Enron emails. (Results) \system blocks ungranted-sink exfiltration, authority amplification, revocation replay, purpose gaming, and intra-tool label violations, and dominates static allowlists on the revocation and intra-tool cases (10/10). Two open models proposed attacker-goal actions on 42/45 and 44/45 injected traces, all blocked at execution; a 90-run multi-turn study cut leakage from 0.844 to 0.20 with full task completion, at microsecond per-decision overhead. Proposition~1 characterizes exactly where attenuation-based authorization suffices, a boundary we also reproduce empirically across four observable-sink workflows. (Conclusion & Significance) Purpose-bound runtime authorization gives delegated LLM workflows a model-independent execution boundary and a precise recipe for composing it with declassification and content monitoring on externally observable sinks.