Artificial Intelligence
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
All of arXiv
Saturday 3 October
Large language models (LLMs) are increasingly used to generate, complete, and transform information in settings where their outputs can shape consequential decisions, raising concerns about their impact on demographic disparities. In this context, causal inference provides a principled basis for assessing fairness, because it attributes observed disparities to the mechanisms that generated them, which a purely statistical approach cannot do even with infinite data. In LLM generation, a query may request several causally related variables, each of which is both an outcome of interest and a possible cause of other outputs, and the information supplied in the prompt need not follow a topological or a temporal order. This calls for methods that can analyze and selectively remove disparities from such a flexible generation process. In this paper we introduce Causally Fair Generation with LLMs (CFG, for short). CFG extracts relevant concepts, grounds generation in a reference population and causal diagram, and removes user-selected causal effects. CFG also allows pathways deemed justifiable for the task's utility to be retained, which is known in legal literature as business necessity. Further, we provide formal guarantees for our method when eliminating all discriminatory causal effects in the adapted population model, under appropriate causal assumptions. We evaluate CFG with four LLMs in three real-world settings based on population data and on a synthetic dataset with a known causal ground truth.
Quantum Physics
Imaginarity as a resource in Shor's algorithm
We investigate the sequential version of Shor's order-finding algorithm from the perspective of the imaginarity of quantum channels. By fixing an eigenbranch of the modular multiplication unitary and a target output path, the process is effectively decomposed into a real diagonal factor and a residual phase channel. We find that for the ideal residual phase channel, the three trace-norm induced imaginarity measures are all equal. On good output paths, a smaller residual imaginarity corresponds to a higher single-block success probability. By combining the branch-wise probabilities, we obtain the exact ideal success probability of the sequential order-finding protocol and derive lower and upper bounds in terms of residual phase-channel imaginarity. We further extend the analysis to noisy residual phase channels, and obtain the lower and upper bounds on the noisy success probability. These results clarify the role of imaginarity of channels in Shor's algorithm and provide a refined perspective on quantum-resource behavior in ideal and noisy sequential quantum algorithms.
Read the full abstract
Cryptography and Security
CHAMP: Cayley HAshing with Matrix Products
Cayley hash functions hash binary strings by representing the bits of the message as elements of a semigroup and multiplying the corresponding elements. This gives Cayley hash functions useful homomorphic properties. Here, we propose CHAMP, a Cayley hash function based on products of 2 by 2 matrices over a finite field, and discuss its security, implementation, and performance.
Read the full abstract
Machine Learning
LocusRL: Diagnosing LLM Reward and Policy Interventions in Competitive Games
Large language models can intervene in reinforcement learning through both reward design and action selection, yet aggregate performance offers an incomplete account of what these interventions actually do. Similar returns can conceal different learning mechanisms, while plausible rewards can induce undesirable behavior. We introduce LocusRL, a diagnostic framework that connects controlled reward-policy comparisons with audits of reward judgments, signal delivery, optimization objectives, and executed actions. The framework traces performance differences to testable explanations and checks targeted corrections through executable rules and counterfactual replay. Across two evaluation batches covering ten Connect Four training seeds, we uncover seed-dependent reversals in intervention effects and show how tracing actual updates changes their interpretation: historical Qwen training operates through reward-weighted teacher-action likelihood. A separate matched three-seed reward-direction experiment distinguishes sensitivity to a learning signal from its usefulness. With terminal rewards held fixed, a sign-reversed dense oracle yields a 2.8% aggregate win rate, compared with 57.2% for terminal-only training and 46.7% for the positive dense oracle. Thus, a reward can strongly influence learning without improving performance. At the decision level, counterfactual replay verifies a winning correction to a diagnosed action error. Complementary experiments in Leduc and reward-validation studies in Goofspiel extend the analysis to imperfect-information settings, revealing how reference-label definitions and validation-data exposure affect intervention assessment. Together, these findings show why evaluating LLM interventions requires tracing how their outputs become learning signals and actions. LocusRL turns aggregate outcomes into actionable diagnoses and verifiable corrections.
Read the full abstract
Computational Complexity
Strictly Unfriendly $k$-Partitions: Sharp Degree Thresholds and ETH-Based Lower Bounds
We present a complete complexity classification and fine-grained analysis for the Strictly Unfriendly $k$-Partition problem ($\text{SU}k\text{P}$), which asks whether the vertices of a graph can be partitioned into $k$ classes such that every vertex has strictly more neighbors in each of the other $k-1$ classes than in its own. We first establish a sharp tractability-intractability threshold with respect to the maximum degree $\Delta$: for $k \in \{2, 3\}$, $\text{SU}k\text{P}$ is solvable in polynomial time when $\Delta \le 2$, but becomes $\mathbf{NP}$-hard and ETH-hard immediately on subcubic graphs ($\Delta = 3$), resolving the degree limitations in prior work and establishing subcubic graphs as the precise frontier of intractability. Furthermore, under the Exponential Time Hypothesis (ETH), we establish the first fine-grained lower bounds via direct reductions from $(3,3)$-SAT. On general graphs, we establish a uniform lower bound across all partition parameters $k \ge 2$, revealing a striking complexity convergence where the core exponential complexity remains invariant despite technical divergences in gadget constructions. On subcubic graphs, we formally quantify the "cost of sparsity," deriving explicit lower bound constants to demonstrate how enforced structural degree restrictions degrade reduction efficiency.
Read the full abstract
General Economics
A study on healthcare expenditure in Italian regions via Symbolic Regression
The study of the factors driving the dynamics of healthcare spending is of paramount importance to guide policymakers in the allocation of resources and to measure the effectiveness of the healthcare system under consideration. The identification of these drivers can be supported by the use of machine learning techniques, which enable the discovery of hidden patterns within vast amounts of data. In contrast to black-box methods, Symbolic Regression (SR) is an approach that allows for the identification of analytical models that explicitly capture the functional relationships within the data, thus enhancing interpretability. In this paper, we present the use of SR for identifying the drivers of healthcare expenditure in Italian regions. Given the dynamic and complex nature of this phenomenon, we generated several models based on distinct temporal windows, enabling us to analyze the drivers across different time horizons. In addition to identifying the main drivers based on variable frequency in the generated models, we also conducted a study on recurring substructures. The results show that SR was able to generate models with a good level of predictive accuracy for private healthcare expenditure, enabling a reliable analysis of its driving factors, but failed to do so for public healthcare expenditure.
Read the full abstract
Artificial Intelligence
RAGrasp: Geometry-Semantic Template Retrieval and Grasp Transfer
We present RAGrasp, a retrieval-augmented pipeline for planar parallel-jaw grasping from a compact set of locally collected, grasp-annotated RGB-D (color and depth) templates. Unlike task-specific predictors trained primarily on large public or synthetic grasp datasets, RAGrasp requires no end-to-end retraining for a new deployment.Its template memory is constructed from observations collected with the deployment camera, robot, and gripper in the target workspace, thereby aligning stored examples with the local sensing and embodiment conditions. The system uses self-supervised DINOv2 visual fea- tures together with appearance and depth cues to prompt the Segment Anything Model 2 (SAM2), which isolates the query object. A two-stage geometry-semantic retrieval cascade then selects a template, and a confidence gate chooses one of two grasp- transfer estimators. The transferred grasp is refined using mask- support and silhouette-contact constraints before calibrated 2D- to-3D conversion. In real-world trials, RAGrasp achieves 20/20 successful grasps on seen objects and 19/20 on unseen objects. Within the evaluated setting, the results demonstrate deployment- specific grasp adaptation from limited local annotation and tolerance to the tested viewpoint and illumination changes.
Read the full abstract
Artificial Intelligence
CRAFT: An Agentic Spreadsheet Form Filling System with Template Awareness
Spreadsheet form filling requires agents to consolidate external evidence, ground values to precise cells, and preserve irregular template structure. Errors in early edits can overwrite labels or misalign fields, undermining later decisions. We propose CRAFT, a template-aware agent framework that connects reflective validation to constrained local repair. Instead of treating reflection as a free-form request to regenerate the workbook, CRAFT grounds detected errors to spreadsheet regions, restores corrupted template state when necessary, and re-grounds plausible writable slots before subsequent edits. A Rectangle-Aware Slot Grounder (RASG) proposes writable cells, while label-slot hints and protected regions constrain subsequent edits. We introduce FormFillBench, with 327 forms across Instruction-Only and Multi-File tracks. Compared with the strongest baselines, CRAFT improves pair accuracy by 8.51 and 23.38 percentage points on these tracks, respectively. Component-removal experiments support structural adjudication and slot re-grounding within the pipeline, and the framework retains its relative advantage among the methods evaluated with a second backbone. The code and benchmark FormFillBench are available at https://github.com/Glllllly/CRAFT.
Read the full abstract
Cryptography and Security
Guess My Weight: Profiled Side-Channel Recovery of Floating-Point Neural-Network Weights
Neural-network parameters deployed on embedded devices may be exposed through physical side-channel leakage during inference. Existing side-channel attacks on floating-point neural-network parameters have often targeted reduced numerical precision, while recovering the complete IEEE-754 representation remains considerably more challenging because of the large and structured 32-bit candidate space. We present a profiled template attack for bit-exact recovery of an IEEE-754 single-precision neural-network weight from power measurements. The attack targets the floating-point multiplication between a known input and a first-layer weight. During profiling, multivariate Gaussian templates are learned from randomized network configurations using Hamming-weight classes of the multiplication result, while the remaining network parameters act as nuisance variables. To efficiently search the structured 32-bit floating-point candidate space, we use a hierarchical coarse-to-fine-to-exact procedure that progressively increases both the numerical and leakage-model resolution. Experiments on a ChipWhisperer-Lite with an Arm Cortex-M4 demonstrate recovery of the exact float32 representation of the target weight. In the evaluated setting, the attack reaches a bit-exact success rate of 99% with 171 traces and 100% from 263 traces onward. These results demonstrate that profiling can enable practical full-precision extraction of floating-point neural-network parameters from physical leakage.
Read the full abstract
Functional Analysis
A relaxation to the post-composition approach to metric-valued Sobolev maps
We establish that the definition of Sobolev mappings from metric measure spaces to metric spaces relying on the post-composition approach of Ambrosio-Reshetnyak admits, under certain transparent assumptions on the spaces, an equivalent reformulation that is substantially weaker than the principal version. In detail, the corresponding definition requires maps of this kind to meet two successive tests in order to be called Sobolev: first a ”qualitative” one and then a ”quantitative” one. At the same time, our result allows the relevant conclusion to be drawn based solely on the ”qualitative” part. Remarkably, the conditions on the spaces sufficient for this to hold fit entirely into the singular flavor of the subject. More explicitly, such a phenomenon emerges if either the source space is of finite Hausdorff dimension and satisfies the Sobolev-to-Luzin-Lipschitz property or the target space is of finite Hausdorff dimension. All this provides a significant generalization of several earlier achievements on the topic.
Read the full abstract
Mathematical Physics
Supersymmetric semi–infinite cohomology and $N = 2$ superconformal structures
We study supersymmetric semi-infinite cohomology and its $N = 2$ superconformal structure via the BRST reduction of an $N = {\frac{3}{2}}$ superconformal structure on the super-affine vertex algebra associated to a super Manin pair arising from the Kazama–Suzuki $N = 2$ condition. Moreover, we realize super coset models in terms of relative supersymmetric semi-infinite cohomology.
Read the full abstract
Artificial Intelligence
What Does a Harness Buy? Tokens, Mostly
A coding agent is a language model wrapped in a harness: the system prompt, the tool set, and the context management that turn a chat model into something that can work inside a repository. Production harnesses ship releases daily, vendors advertise pass-rate gains from harness changes, and leaderboards mix harnesses freely. What is rarely measured is how much the harness itself moves the score when the model is held fixed. We run five models through three production harnesses, Claude Code, mini-SWE-agent, and OpenCode, on SWE-bench Verified, and rerun the same configurations to calibrate how much a score moves when nothing changes but the run. On 447 tasks and the two models we ran there, Claude Code and mini-SWE-agent, the heaviest and the lightest harness, are equivalent within five points. On a 45-task hard subset and five models, swapping the harness flips as many tasks as rerunning the same harness, 13% in both cases, and the tasks a harness wins in one run are not the tasks it wins in the next. The one harness effect that clears the noise is a loss, not a gain: OpenCode trails by up to 9 points on the large pool, and on one model half of that gap sits in runs its output cap cut short. What the harness does decide is the bill. With the same model, the same tasks, and one price list, cost per task differs by up to 3x across harnesses. The gap is set at the first call, by the preamble of system prompt and tool schemas each harness sends with every step, and scaled by the number of steps; per-step growth and per-call tool output differ far less. The provider's price for cached input scales the bill and does not reorder it. The rerun data also give the resolution a harness comparison needs: at the discordance we observe, 45 tasks catch a 13-point gap only half the time and no gap with 80% power, and 447 tasks resolve 5 points, still coarser than the gains many harness changes claim.
Read the full abstract
Computer Vision
Video2World: Benchmarking Coding Agents for Interactive World Modeling from Embodied Videos
Building interactive simulators from real-world observations is a promising way to scale embodied data, but current pipelines still rely heavily on manual environment construction and calibration. We study whether frontier foundation models and coding agents can automate this process end to end. We formulate autonomous video-to-simulation as a software engineering task in which an agent observes an embodied video, constructs the corresponding simulated environment and robot behavior, and iteratively refines the result through execution feedback. To evaluate this capability, we introduce Video2World, a benchmark comprising 222 reconstruction instances derived from 189 robot and human demonstration videos. Video2World measures reconstructed worlds along geometric fidelity, dynamic fidelity, and functional correctness, capturing spatial perception, physical reasoning, and executable interaction. Evaluating 9 frontier coding-agent systems reveals a sharp improvement in Task success beginning with Claude Opus 5, rising from below 5% to over 15%, while substantial gaps to human-assisted reconstruction remain. We further find that worlds that look better could work worse: better visual fidelity does not always lead to higher task success. This echoes the broader gap between perceptual realism and factual correctness observed in generative models.
Read the full abstract
Spectral Theory
Block numerical ranges for linear relations
Linear relations are multivalued generalizations of linear operators whose spectral properties are closely linked to the stability of differential-algebraic equations. Consequently, reliable spectral enclosures are of considerable interest. In this note, we extend the established concept of the block numerical range from operators to linear relations by means of a range representation. Unlike the classical numerical range, the resulting block numerical range may be nonconvex and can therefore detect gaps in the spectrum. We establish fundamental properties of this new notion and derive corresponding spectral enclosure results. Finally, we illustrate the theory with a numerical example comparing the block numerical ranges obtained from different constructions. As an application, we obtain an explicit left-half-plane spectral bound for a class of port-Hamiltonian DAEs.
Read the full abstract
Artificial Intelligence
MERCI Cards: An LLM Evaluation and Deployment Framework for High-Stakes Domains
As LLMs are increasingly deployed in high-stakes professional workflows, engineers and researchers require principled protocols to systematically track, monitor, and improve model performance across deployment cycles. We present a mathematical framework for iterative LLM evaluation and deployment, and demonstrate its application to AI systems used in criminal justice. Our framework formalizes LLM integration in high-stakes, high-risk, and resource-constrained domains across model selection, rubric design, evaluations and deployment via a weighted multi-objective optimization. We demonstrate that MERCI Cards can guide improvements of the system across deployment iterations, direct developer attention toward under-performing areas, and focus user attention on validation and error-correction in the LLM's outputs.
Read the full abstract
Artificial Intelligence
Asking Earns Nothing: Scoring the Decision to Act in BFCL Multi-Turn
An agent that lacks the information it needs should ask rather than act, and the task definitions of agent leaderboards say so. BFCL multi-turn builds two of its four categories around a turn on which the model is supposed to ask, and its scorer never looks at that turn: the gold trajectory there is empty, the checker skips it, and the scripted user cannot answer, so asking earns nothing, guessing costs nothing on that turn, and asking twice loses the item. The benchmark also contains the control experiment for that decision. A should-ask item is a base item with one piece of information removed from one turn, so the same request appears twice at the same turn index, once complete and once not: on the first the model should make the call that changes the world, on the second it should ask. We score one decision per pair, whether the model attempted a world-changing call on that turn, read off the stored trajectories with no LLM judge; acting always and asking always both score 50. On the 223 pairs that pose this decision, gpt-5.4 attempts the call on 83.4% of the complete turns and holds back on 78.0% of the incomplete ones, the best decision accuracy of seven models at 80.7%; on the same items the official score ranks it sixth and puts first a model that lands in the middle here. One added line telling gpt-5.4 not to ask pushes it toward acting on both sides of the pair, so its decision accuracy shows no detectable change, while its official score rises by 13.5 to 23.5 points on the two should-ask categories and on the base twins; the opposite line, telling gemma-4-31B-it to ask first, improves its decision by 4.5 points and gains no official score. The score moves with the push toward action, not with the decision. We release the pairs, a turn-level scorer that runs on any BFCL output directory without an API key, and 31 manually verified bad items.
Read the full abstract
Differential Geometry
Clifford Actions and the Algebra of Double Forms
Let $V$ be an oriented Euclidean vector space and let $\D(V)=\Lambda V^*\otimes\Lambda V^*$ be the algebra of double forms. The two exterior factors carry natural factorwise exterior and interior multiplication operators and therefore two commuting Clifford actions. The central result of the paper is an intrinsic realization of these Clifford actions inside Greub's composition algebra. For $a\in V^*$ we introduce the inhomogeneous double form \[ \chi_a=((1\otimes a)-(a\otimes1))e^g, \] prove that the $\chi_a$ satisfy the Clifford relations for the composition product, and establish the exact regular-action formulas \[ C_R(a)\omega=\chi_a\circ\omega, \qquad C_L(a)\omega=-\omega\circ\chi_a. \] For $h\in\D^{1,1}$ this yields a canonical four-component decomposition of the coupled left–right Clifford action into exterior multiplication, double contraction and two generalized Bianchi operators. For the metric double form $g$ these four operators generate two commuting $\mathfrak{sl}_2$ actions. The construction extends canonically to arbitrary bidegree. In bidegree $(2,2)$ its degree-preserving component admits a direct comparison with the double-form extension of the sharp product: for every $R\in\D^{2,2}$, \[ \Gamma_{1,1}(R)(\omega)=\frac14R\#\omega. \] The point of this identity is not a new definition of $R\#$, which is already constructed from Clifford commutators, but the fact that it appears canonically as the central homogeneous component of the higher left–right Clifford transform. As an application, the algebraic quadratic map $\mathcal Q(R)=-\frac14R\#R$ satisfies \[ \mathcal Q(R)=-\Gamma_{1,1}(R)R, \] and its linearization at $R$ is the operator $-2\Gamma_{1,1}(R)$. For curvature tensors this is the sharp contribution to the Ricci-flow reaction term.
Read the full abstract
Machine Learning
COSMOS: Soft Mechanism Mixtures with Verifiable Routing for Long-Horizon PDE Forecasting
Neural operators offer an efficient alternative to classical PDE solvers, but most learn a monolithic map per equation family and discretization. Real systems are compositional: transport, diffusion, wave, and reaction processes can act simultaneously. Existing mixture-of-experts operators typically use sparse top-$K$ routing, although concurrent physics is naturally a blend rather than a discrete choice. We propose COSMOS (Cooperative Operator Specialists with Mechanism-level Operator Soft-routing), a soft mechanism-mixture neural operator. Four process-biased specialists remain active at every step and are continuously mixed by a learned gate, with their features fused by a small network. Specialists share a coarse latent grid, while a zero-initialized full-resolution residual restores detail lost through the bottleneck. We also introduce an operator-splitting compositional benchmark with known mixture weights $w^\star$ per trajectory. Against family-tuned FNO under 20-step rollouts, an initial 3-seed evaluation suggested gains on diffusion–reaction, parity on Navier–Stokes, and weaker shallow-water performance. An 11-seed audit showed that the diffusion–reaction gain was unstable, motivating caution in small-seed rollout comparisons and precluding a reliable accuracy-win claim on these families. Ablations show that uniform routing or removing the specialist mixture substantially degrades stable-regime rollouts. On the labeled benchmark, dense soft routing yields $2.2\times$ lower error than hard top-1 routing at identical fusion; using generator weights $w^\star$ at inference further lowers rollout error to $0.034$, diagnosing limitations of the learned gate. However, routing labels do not align with the specialists' intended mechanisms: COSMOS supports compositional accuracy, not mechanism identity.
Read the full abstract
Machine Learning
UnAct: Gradient-Free Unlearning via Targeted Activation Intervention
Machine unlearning seeks to remove the influence of designated training data from a trained model without retraining from scratch. Retrain-free methods such as Selective Synaptic Dampening (SSD) and its label-free variant LFSSD avoid full retraining but still require backpropagation and parameter importance computed over the entire dataset. We ask: what happens when a deletion request arrives with only a few images of the class to be forgotten? To answer this question, we introduce UnAct, a gradient-free class-unlearning method that needs only forward passes over the forget images. UnAct scores late-layer units by their responses, attenuates the most responsive connections, and repeats this for up to 20 rounds using no gradients, no labels, and no retained data. On ResNet-18 trained with CIFAR-10, CIFAR-20, and CIFAR-100, UnAct is competitive with SSD and LFSSD when forgetting entire classes and, unlike them, never collapses the network when forget data is scarce. On ResNet-18, across all tested sizes, UnAct's retain accuracy stays within 2.5 points of retraining, while SSD and LFSSD, at their full-class operating points, lose up to 86 points on some classes. With five forget images on CIFAR-10, UnAct's distance to retraining is 0.21 points, against 67 for LFSSD and 90 for SSD, and re-selecting SSD's threshold at each size with an oracle does not close the gap. In preliminary transfer to ViT-B/16, UnAct's distance to retraining is 11.5 against 33.7 for SSD, and a request is 19x faster than SSD when SSD computes its importance at request time. The code is available at https://github.com/abdulmuizz0903/UnAct
Read the full abstract
Computer Vision
AgroGround: Multi-Granularity Grounded Recognition in Agriculture
Agricultural visual models are typically evaluated for either recognition or localization, but reliable diagnosis requires identifying what is present and localizing the evidence. Agricultural visual question answering (VQA) datasets carry rich semantic labels but rarely link them to image regions, and adding such annotations by hand is costly at scale. We introduce AgroGround, a large-scale dataset for grounded agricultural recognition: identifying plant diseases and other agricultural targets and localizing their image regions. An automated pipeline converts the labels of eight agricultural VQA datasets into annotations for disease lesions and whole objects, producing 794,850 instruction examples. Healthy images provide negative supervision for disease queries, teaching the model to return empty predictions. We fine-tune a shared vision-language model on known-target grounding instructions combined with instructions requiring both recognition and localization. We evaluate predicted identities, regions, joint correctness, and healthy-image abstention on 1,480 human-verified images disjoint from all training data. Grounding-only fine-tuning reduces recognition accuracy from 51.8% to 29.1%, while adding recognition-and-localization instructions raises it to 72.6%. With images and annotations held fixed, combining the two formats raises joint accuracy from 19.2% to 43.3% at comparable grounding. Healthy negatives raise abstention on healthy images to 95.0%, and reinforcement learning improves lesion-level grounding. The resulting 2B model exceeds its annotation teacher in grounding F1 on our benchmark and on the external PlantSeg test set. AgroGround establishes a benchmark for grounded agricultural recognition, measuring joint correctness of identity and localization along with abstention on healthy images. The code is available at https://github.com/AB-Abdulla/AgroGround.
Read the full abstract
Machine Learning
On the Trade-off Between Information Loss and Generalization in Sparse Attention
To mitigate the quadratic complexity bottleneck of the Transformer, sparse attention has emerged as a pivotal technology. Despite the extensive empirical success of sparse Transformers, the theoretical understanding of sparse attention remains fragmented. In particular, two fundamental questions remain unclear: (1) How does sparsification affect the information fidelity of attention mechanisms? (2) How does this information loss interact with the generalization behavior of the model? To bridge this gap, this paper proposes a systematic analysis of the Jensen-Shannon (JS) divergence and of the generalization gap of sparse attention mechanisms. Specifically, we first characterize the approximation error via the JS divergence. Through an order-statistics-based concentration analysis of the truncation mass alpha — where the attention scores are assumed to be independent and identically distributed sub-Gaussian random variables with parameter sigma — the JS divergence between the full attention distribution and the sparse attention distribution is shown to admit the closed form log 2 + ((1 - alpha)/2) log(1 - alpha) - ((2 - alpha)/2) log(2 - alpha). Subsequently, we derive a generalization bound through Rademacher complexity, quantified by O(gamma * sqrt(M/n) * (sqrt(log(3eL/M)) + sqrt(pi)/2)). Furthermore, building on a mutual-information-based generalization bound together with an entropy and covering-number analysis of the sparse hypothesis class, we obtain the sparsity-dependent generalization bound O(sqrt((M/(2n)) * (log(eL/M) + log(1 + 2/epsilon)))). Our analysis shows that sparsity reduces the complexity of the considered hypothesis class while introducing approximation error that can be quantified by the JS divergence. These findings provide a theoretical characterization of the trade-off between information fidelity and generalization in sparse Transformer architectures.
Read the full abstract
Computational Complexity
Nonuniform QCPH Collapse Implies QCPH Collapse
Despite the importance of the non-uniform Polynomial-Time Hierarchy (PH/poly) in classical complexity understanding the collapse conditions of the Polynomial-Time Hierarchy (PH), a quantum equivalent of PH/poly has yet to be studied in the literature. We introduce the non-uniform computational Quantum Polynomial-Time Hierarchy (QCPH/mpoly), the quantum equivalent of PH/poly, and show that it collapses if and only if QCPH, the quantum equivalent of PH introduced by Gharibian et al. (comput. complex. 2022), also collapses. We also show that QCPH collapses if coQCMA is contained in QCMA/mpoly. These results are analogous to those of Yap (TCS 1983) commonly used to invoke the collapse of PH in classical complexity. QCPH/mpoly is analogous to QCPH with non-uniform quantum verifier circuits.
Read the full abstract
Machine Learning
Measuring Effective Data Resolution in Guided Diffusion Posteriors
Guided diffusion samplers are increasingly used to reconstruct physical fields from sparse observations, but standard diagnostics do not say how much of the reconstruction was actually determined by the data. We introduce effective data resolution for black-box generative posteriors: a comparison between the resolution warranted by the inverse problem, $\mathrm{dof}_{\mathrm{ref}}$, and the resolution realised by the sampler, $\mathrm{dof}_{\mathrm{samp}}$. A perturbation estimator measures $\mathrm{dof}_{\mathrm{samp}}$ and the spatial map $R(x,x)$ from sampler queries alone. We validate the estimator against exact references and use it to study guided diffusion. The resulting measurements show that guidance weight can strongly alter apparent information transfer, that mean, spread and resolution are not jointly corrected by one weight even with an exact prior and score, and that resolution fidelity does not follow reliably from the apparent principledness of a guidance rule.
Read the full abstract
Astrophysics of Galaxies
Feedback-Driven Interaction of Expanding Molecular Clouds in the LDN 1204-Sh2 145-Sh2 140 Complex
We present a multi-wavelength study of an extended molecular cloud hosting the LDN 1204, Sh2 145, and Sh2 140 regions to investigate the interplay between stellar feedback, cloud dynamics, and star formation. Infrared images reveal two semi-arc/shell-like structures (extent 14-18 pc) associated with known massive O-type stars. Herschel temperature and column density maps identify one hub-filament system (HFS) candidate toward both LDN 1204A and LDN 1204B sub-regions, with peak column densities of 3.1 x 10^23 and 1.3 x 10^23 cm^-2, respectively. These sub-regions are located at the periphery of the Sh2-145 H ii region. Molecular line data reveal a large arc-/shell-like cloud resolved into two kinematically distinct components spanning -15 to -9.5 km s^-1 and -9 to -3 km s^-1. Each component exhibits an arc-/shell-like morphology, is centered on one of the massive stars, and displays an inverted C-shaped position-velocity structure, indicating expansion driven by its associated H ii region. Both LDN sub-regions are located at the projected interface of the two expanding cloud components. Young stellar objects (YSOs), particularly Class I YSOs, are concentrated toward these sub-regions, while moment 2 maps reveal enhanced velocity dispersion, suggesting increased turbulent motions at the interface. Altogether, the presence of dense filaments, candidate hub-filament systems, and active star formation in LDN 1204 sub-regions demonstrates that feedback driven shell expansion and interaction compressed the gas at the interface, establishing the necessary conditions for filaments and ongoing star formation. These results highlight the important role of feedback-driven cloud interactions in regulating dense structure formation and star formation in molecular clouds.
Read the full abstract
Probability
Seed thresholds and degree variance in heterogeneous bootstrap percolation with growing degrees
We study bootstrap percolation with independent vertex thresholds taking values one and two, with threshold-one probability $(1-c/d)/d$ for fixed $c>0$. The seed set is chosen uniformly among sets of a prescribed deterministic size, independently of the graph and thresholds. We prove threshold statements at fixed relative margins. For uniform simple graphs with prescribed nonnegative integer degrees of even sum and exact mean $d$, assume $\max_i|d_i-d|\le C\sqrt d$ and $c+1-v_n\ge\kappa>0$, where $v_n=\operatorname{Var}(D)/d$ and $C,\kappa$ are fixed. When $d\to\infty$ and $d=o(n^{1/7})$, the leading seed scale is $n(c+1-v_n)^2/(2d^4)$, without requiring a limit of $v_n$. At fixed relative margins below and above this scale, the final active set has size $O(n/d^3)$ and $n-o(n)$, respectively, with high probability. For regular graphs, the supercritical conclusion strengthens to full activation. For $G(n,d/n)$, the same $O(n/d^3)$ and $n-o(n)$ conclusions hold when $d\to\infty$ and $d^5/n\to0$, with seed scale $nc^2/(2d^4)$. Thus regular and independent-edge graphs have different coefficients at the same asymptotic mean degree. Local exploration estimates yield explicit inactive remainders and survive conditioning on simplicity in the prescribed model. We also quantify the precision obstruction to static inclusion transfer and compute deterministic response-barrier corrections, without identifying a shrinking random critical window.
Read the full abstract
Machine Learning
MaDeL: Manifold-Decomposed Feature Losses for Generative Modeling
Generative models are often trained with isotropic objectives such as mean-squared error. For data concentrated near a low-dimensional manifold, however, such losses conflate displacement along the manifold, which may represent valid variation, with displacement away from it, which produces invalid samples. This mismatch is especially problematic in sparse, highly constrained domains, where ambient-space regression can encourage off-manifold interpolation. We ask whether a generative objective can distinguish manifold-parallel variation from manifold-orthogonal deviation directly from data, without explicitly estimating the manifold. We introduce a manifold-decomposed feature loss (MaDeL) that learns complementary representations from corrupted observations: one is trained to recover the clean sample, while the other is trained to recover the corruption. We show that, under a feature bottleneck, their Jacobians align with the tangent and normal spaces, exactly for linear manifolds and locally for smooth manifolds. Together, these representations define an anisotropic objective that separately measures intrinsic variation and off-manifold deviation. Across synthetic, Earth and climate science, and torsion-angle benchmarks, MaDeL improves support recovery and average angular $W_1$ under single-step sampling; on protein backbones, it reduces steric clashes across one- and few-step sampling budgets.
Read the full abstract
Artificial Intelligence
CORE-RL: Confidence-Oriented Reliability Evaluation of Black-Box Reinforcement Learning Policies
The deployment of Reinforcement Learning (RL) agents in critical domains must be preceded with a pipeline to evaluate the alignment of the RL agent with complex multi-objective specifications and robustness under real-world environmental drift. However, to protect intellectual property, the RL agent may be delivered for evaluation as opaque executable or remote API, which makes traditional evaluation techniques based on the internals of the policies infeasible. To address this gap, CORE-RL: Confidence-Oriented Reliability Evaluation of black box RL policy is proposed in this paper. The CORE-RL pipeline introduces a Unified Reliability Metric that formally integrates early task termination and safety constraint violations, preventing unsafe policies from masking failures through premature episode halts. By subjecting the policy to a noise certification envelope of perceptual noise, actuation noise and change in environment dynamics, the pipeline computes the finite-sample Clopper-Pearson bounds on unified reliability metric and Hoeffdings' lower bound on reward and safety cost. The pipeline then defines safe operational design domain to report high-confidence certificates for safety and expected performance. Experiments on continuous control tasks demonstrate the CORE-RL pipeline's ability to automatically reject non-compliant policies and map the safe Operational Design Domain (ODD) of safety-aware policies. Thus CORE-RL provides an evaluation framework towards a quantitative, transparent and reproducible, statistical rationale necessary to safely evaluate, compare, and deploy black box RL solutions.
Read the full abstract
Game Theory
Maximizing $p$-Mean Social Welfare in the High-Multiplicity Setting: Few Agent Types and Few Item Types
The $p$-mean welfare objective unifies several classical social welfare criteria for the allocation of indivisible goods. We study its maximization under additive nonnegative utilities when item and agent multiplicities are encoded in binary. For every fixed finite rational $p<1$, $p\neq0$, we show that the problem is $\mathsf{NP}$-hard with only two item types. Nash welfare ($p=0$) and egalitarian welfare ($p=-\infty$) are NP-hard with three item types. These results hold both for computing an optimal allocation and for rational-threshold decision, and the utilities and threshold can be required to be positive integers. We also show that maximizing $p$-mean social welfare is strongly NP-hard with one agent type and an unrestricted number of item types, for every fixed finite rational $p<1$ and for $p=-\infty$. A quantitative gap in this reduction rules out an FPTAS in the latter setting unless $\mathsf{P}=\mathsf{NP}$. On the positive side, for a fixed number of item types and an arbitrary number of agent types, we give an FPTAS for every fixed $p\in\mathbb Q\cup\{-\infty\}$. Its running time is polynomial in the compact input length and in $1/\varepsilon$, and it returns a compressed allocation. For a fixed number of agent types and an unrestricted number of item types, we give a PTAS for every fixed finite rational $p<1$, also in the fully compact model. We further give explicit compact-model proofs of the classical exact allocation algorithms for one item type, and for egalitarian welfare with two item types. These results essentially settle the complexity and approximability of $p$-mean welfare maximization with few item types and/or few agent types, leaving only the exact complexity of Nash welfare maximization with two item types unresolved in the small-item-type classification.
Read the full abstract
Soft Condensed Matter
Compression-controlled dynamic buckling in thin soft sheets
We investigate experimentally the dynamic phase transition from compressed to buckled phases for thin sheets of rubber. We find that the rubber strips enter a highly compressed, metastable state when compression speed is high. During the compressed phase, higher modes grow, followed by mode coarsening. Mode growth is accompanied by an expansion of length while the system is still being compressed. We measure the forces and length of the sheet to confirm this, and we develop a mechanism for how modes grow and coarsen during dynamical buckling. The influence of crucial control parameters in the experiments, such as the material cross section and compression speed, on the buckling dynamics, are explained theoretically.
Read the full abstract
Adaptation and Self-Organizing Systems
Collective Sensing as Emergent Bayesian Inference
Collective behavior in animal groups is routinely described in cognitive language: fish schools sense gradients, swarms compute, colonies decide. These formulations often leave open what the collective is inferring, what computational object is represented, or how that representation arises from microscopic interactions. Here we develop that description quantitatively in a simulation based on the canonical model of collective sensing in fish schools (Berdahl et al., 2013), in which collective gradient sensing emerges from individuals that do not estimate gradients themselves: agents only modulate their speed in response to local light intensity and respond to simple social forces from neighbors. We show that these local rules admit a mesoscopic Bayesian reinterpretation at the level of the school, and hypothesize that the collective dynamics realize approximate inference on a generative model of how darkness gradients drive inter-individual speed differences. The resulting school-level inference process yields a posterior distribution over the local darkness gradient, whose statistics vary with environmental structure and relate systematically to collective motion and sensing performance. The school can therefore be described, in a Bayesian-mechanical sense, as a distributed inferential system without requiring individual agents to perform probabilistic belief updates themselves. This yields a quantitative, falsifiable account of collective sensing as emergent inference, and a concrete bridge from collective behavior to Bayesian mechanics.