Week beginning 2nd November 2026

Abstract: Large language models (LLMs) on personal devices keep user data local, but limited memory restricts their general capability. Since most user-specific tasks do not require the breadth of frontier models, a practical solution is to adapt a shared on-device model into lightweight specialists. However, backpropagation is prohibitive in memory, and users rarely provide labeled data. We present MobileSpec, a system that trains specialists with forward passes alone and learns from automatically checked task outcomes, as in reinforcement learning with verifiable rewards (RLVR). Because forward-only updates are built from random perturbations, training is efficient only when these perturbations resemble the weight changes of RLVR, which largely preserve the singular values of pretrained weights and rotate their singular vectors. The core algorithm of MobileSpec, FuRA-S, produces such perturbations while training only the block-spectral coordinates of pretrained weights, namely the singular values of their column blocks. As we show theoretically and empirically, rescaling these blocks independently shifts their relative contributions to each weight matrix and thereby rotates its singular vectors. Since this update can be rewritten as a transformation of the layer input, FuRA-S also adapts INT4 models without modifying their weights. With specialists of only 1-5 MB that update 0.015-0.05% of the parameters, MobileSpec raises the success rate of a phone-use agent from 6-23% up to 89-100% and trains a personalized 8B model on an iPhone 16 Pro overnight. On RLVR benchmarks, FuRA-S is competitive with full-parameter evolution strategies (ES) and outperforms ES over LoRA adapters and quantized ES on INT4 models.

Abstract: Complete complementary code (CCC) is a crucial component in the design and optimization of modern wireless communication systems, particularly in addressing challenges related to interference, spectral efficiency, and signal quality. The design of CCCs is an active area of research, as it directly impacts the number of users that can be supported interference-free in the system. In the literature, CCC constructions are restricted by a set size smaller than the sequence length. In this paper, we introduce a novel construction method for CCCs based on the extended Boolean functions (EBF) that overcome existing restrictions by including a set size bigger than the sequence length. Further, the proposed construction uses functions which are new in literature and provide us with new CCCs. This is also the very first construction where row PMEPR is also bounded by $n$ for a set size in the form of power of $n$.

Abstract: Expert offloading enables large mixture-of-experts (MoE) language models to run locally, but conventional batching stalls the GPU while missing experts are fetched. A popular remedy, known as prefetching, is to predict what experts will be needed soon and fetch them using idle link bandwidth. Imprecise prediction, however, wastes bandwidth and GPU memory on fetching unnecessary experts. Our key finding is that prefetching can be harmful when there is an expert cache in GPU memory. This is because as the cache includes more necessary experts, expert prediction becomes less precise. Our key insight is that proper request scheduling beats prefetching. Building on this insight, we present Bevy, an MoE inference system based on runahead inference for concurrent requests. A request whose experts are available can run ahead to later layers while other requests wait for fetches, revealing the experts it needs next. Bevy can then fetch the missing experts so identified while computing ready requests, overlapping computation and fetching without predicting expert selections. Running requests separately, however, repeats reads of shared weights in GPU memory and increases compute time. To limit this cost, Bevy's self-balancing scheduler batches ready requests at each layer and prioritizes lagging requests, adapting their grouping as expert availability changes. Across two local platforms, Bevy delivers up to 3.46$\times$ the decode throughput of llama.cpp and up to 1.55$\times$ that of the fastest prefetching baseline.

Abstract: Reinforcement learning objectives that maximize expected return can concentrate probability mass on a small subset of high-reward outcomes, limiting diversity when multiple distinct solutions are desirable. We introduce Density-Aware Reward Scaling (DARS), a simple reward-processing mechanism that promotes reward-proportional sampling in continuous outcome spaces while retaining standard policy-gradient training. DARS estimates the local density of outcomes within each on-policy rollout group and inversely scales rewards by this density. The method requires no learned density model, auxiliary objective, critic, or modification to the underlying policy-gradient objective. In a controlled multimodal navigation task, DARS-GRPO avoids the single-mode collapse exhibited by GRPO and closely recovers the target mode allocation. Applied to text-to-image prompt adaptation, DARS-GRPO consistently improves image and prompt diversity across datasets, Policy LMs, and reward settings while maintaining good semantic alignment. These results show that density-aware reward scaling provides a lightweight way to improve coverage of diverse high-reward outcomes within existing reinforcement-learning pipelines.

Abstract: We formulate the global trace condition, GTC, for cyclic proofs as a particular case of the size-change termination condition, or SCT. We express cyclic proofs through a variant of size-change graphs, called transition graphs, whose edges are labelled by (finite) bipartite relations. We show that injective transition graphs suffice to encode cyclic pre-proofs for a variant of Brotherston and Simpson's sequent calculus with inductive definitions. The injectivity of transition graphs corresponds to restricting SCT to fan-in-free graphs. Then we prove that an essentially weaker condition implies SCT in this case, and hence GTC.

Abstract: Reinforcement learning with verifiable rewards (RLVR) has become an effective approach for improving mathematical reasoning in large language models. However, a fundamental question remains: when a model fails to solve a problem, does it truly lack the underlying capability? In this work, we reveal that direct failure does not necessarily imply inability. Some reasoning failures can be recovered by exploring the model's own trajectories, exposing a recoverable capability frontier: a policy-dependent region where solutions are not reliably generated through direct decoding but can be elicited through trajectory-level search. Based on this observation, we introduce ReSI-Math, a framework that explores recoverable capability frontiers and converts recovered capabilities into data-efficient RLVR supervision. ReSI-Math uses Self-Judge-guided evolutionary search to identify recoverable failures under a fixed policy and adaptively selects frontier problems for sequential RLVR as the policy evolves. On Qwen3-VL-8B, correct-incorrect trajectory crossover produces 272 verifier-confirmed correct offspring from 621 attempts (43.8%). After three sequential one-shot RLVR stages, the MATH500 and WE-MATH average improves from 78.71 to 80.16. Under matched single-problem RLVR, random selection reaches only 53.31 versus 54.16 for frontier-guided Q1.

Abstract: We give a near-linear-time sampler for the zero-field ferromagnetic Ising model throughout the tree-uniqueness regime, including the threshold itself. The method also gives sampling algorithms for the XY and integer Potts models. On an $n$-vertex graph with $m$ edges and maximum degree at most $Δ$, we obtain the following expected-work bounds, with total variation error at most $\varepsilon$. 1.Near-linear Ising sampling. For $Δ\ge3$, the work is $O(n+m\log^3(n/\varepsilon))$ throughout the tree-uniqueness regime, including the threshold $β=Δ/(Δ-2)$. 2.Almost-linear XY sampling. For $Δ\ge8$, we sample the XY model in $\widetilde O(m+n^{1+o(1)})$ expected work at inverse-polynomial accuracy up to and including the robust phase-transition threshold on the $Δ$-regular tree. 3.Near-linear Potts sampling. For integer $q\ge3$, we sample the $q$-state Potts model in $\widetilde O(n+q^{O(1)}m)$ expected work whenever $β-1\le 0.1(β_{\mathrm{od}}(q,Δ)-1)$, where $β_{\mathrm{od}}$ is the ordered/disordered coexistence parameter. We express the even-subgraph representation of critical Ising as a polymer model that admits near-linear-time sampling, thereby bypassing the critical slowdown of Glauber and Swendsen--Wang dynamics. Building on the low-degree approximation approach of Miao and Yin, we establish general spectral conditions for fast polymer sampling. We verify these conditions through explorations that also implement the sampler efficiently, and apply the same framework to flow representations of the XY and Potts models. We also establish polynomial-time counting and sampling for the ferromagnetic XY model at every fixed temperature.

Abstract: Large language models are candidates for collecting and analyzing records in criminal investigations and mass surveillance. Their capability and accuracy in this work cannot currently be measured. Real deployments lack the ground truth needed to score a model's conclusions, and no benchmark evaluates these capabilities in a simulated environment. We present Kierston, a city-scale simulation engine, and KierstonBench, a benchmark that tests these capabilities against known simulated events. Kierston models approximately 125,000 residents of Allentown, Pennsylvania, generating their daily activities and the telecommunications, financial, administrative and license-plate records that surveillance and investigative systems collect about them. These records derive from a common behavioral timeline and are distributed across sources representing separate providers. Models investigate through a restricted records interface, linking observations across sources without access to the underlying simulation. The benchmark comprises 32 task families covering record linkage, routine reconstruction, incident investigation and assessment of deceptive accounts. In an evaluation of sixteen language models, most could not perform records investigation and submitted identifications the records did not support. A small number of frontier models solved most of the tasks and abstained when evidence was insufficient. In some cases these models still fell for common deceptions and assumptions, and none replaced an investigator.

Abstract: The best-known approximation factor for constrained correlation clustering stood at three for nearly two decades, until a recent improvement to below $16/7$. We give a randomized polynomial-time $(2+\varepsilon)$-approximation using \emph{Repulsion}, a recursive operation that separates a metric ball from its complement. Repulsion naturally respects hard constraints and admits a short potential-based analysis; as a warm-up, radius-$2/3$ Repulsion rounds the standard metric LP into a feasible partition of cost at most three times its objective. The $(2+\varepsilon)$-approximation takes a two-stage approach, first removing must-links with arbitrarily small loss in the approximation ratio. The second stage combines lossless, constraint-aware preclustering with the bounded sub-cluster LP framework of Cao, Cohen-Addad, Lee, Li, Newman, and Vogl (STOC 2024). Repeated positive conditioning and sampling produce candidate sets, which radius-one Repulsion partitions into feasible clusters at controlled cost. We also give an approximation-preserving reduction from vertex cover to cluster deletion, a special case with only cannot-links. Apart from establishing a matching factor-two hardness threshold under the Unique Games Conjecture, it motivates our two-stage approach and Repulsion.

Abstract: When students use generative AI to produce their work, the learning process becomes invisible. Established frameworks such as Bloom's taxonomy then classify the cognitive level of what the AI produced, not what the student contributed. We propose the Human Agency Depth Taxonomy (HADT), a preliminary six-tier taxonomy that classifies the engineering contribution a student makes in a prompt, independent of the AI's output. HADT combines three dimensions: contextual bandwidth, engineering abstraction and student agency. We applied HADT to 962 prompts from 105 students' structured AI Journals in an AI-permissive, first-year software engineering course of 145 students, and examined how agency changed over ten journalled weeks. Most prompts (84.2%) carried some student contribution beyond delegation. Agency tracked the development lifecycle. Architecture-discovery prompts dominated the requirements phase (48% of turns) and fell to 5-12% from week 9, while prompts analysing existing systems rose during build and verification (odds ratio 2.88, with turns clustered by student). Two-thirds of the variance in tier lay within students, so agency depended more on the phase of work than on the student. A turn-level rise in delegation in deadline weeks did not hold once turns were clustered by student. Explicitly specifying constraints on the AI's output was rare throughout, which we interpret as a knowledge bottleneck for novices rather than a gap in instruction. We discuss implications for course and assessment design, and for using HADT as a formative lens on how students engage with AI.

Abstract: SAE-based feature-level interventions to suppress PII leakage in LLMs are primarily evaluated by log-probability reduction. We show that this criterion cannot distinguish feature specific suppression from a magnitude artifact: a direction-agnostic effect of sufficiently large activation perturbations. Across 36 (model, layer, PII type) cases, we compare selected SAE feature interventions with coherencematched random direction controls using logprob and rank-aware metrics. While 17 cases (47%) appear successful under logprob-only evaluation, only 1 case (2.8%) passes our multimetric framework. The rest reveal two failure modes: random directions outperform selected features, and feature selection collapse across PII types. These results indicate that existing evaluations cannot verify whether interventions target causal pathways of PII leakage. A 9,000 run causal mediation feasibility study corroborates this: the verifier separates candidates reliably, but correlation-selected candidates rarely pass it. We therefore propose a new research mission for NLP: causally grounded PII suppression through circuit-level localization and causal mediation analysis.

Abstract: In single-pixel (ghost) imaging, known illumination patterns probe an object and a detector with no spatial resolution returns one number per pattern. Each measurement costs acquisition time and photons and, for ionizing probes, contributes to delivered dose. Motivated by automated radiographic defect screening, where a class label suffices, we introduce Learning Illumination Patterns for Single-Pixel Classification (LIPS-PC). The patterns are learned end-to-end while the measurement operator remains one fixed linear matrix, identical for every input. We parameterize it as a residual correction to a two-dimensional discrete cosine transform (2D-DCT), $D=D_{\mathrm{base}}+Δ$, and jointly train the correction and a compact classifier using cross-entropy, without a reconstruction objective. This yields a task-driven linear embedding through optimization. We evaluate LIPS-PC numerically on MNIST and Fashion-MNIST under a controlled protocol, then on RIAWELC, a real industrial X-ray weld-radiograph dataset. Across five budgets, $M\in{8,16,32,64,128}$, corresponding to sampling ratios from below 1% to 12.5%, the learned operator outperforms the best tested fixed transform by 9-15 percentage points at $M=8$ on all three datasets. Its eight-measurement accuracy requires roughly 16-32 measurements with the best fixed transform, indicating a $2\times$ to $4\times$ saving at comparable accuracy. The advantage generally shrinks as $M$ increases, with a small reversal on RIAWELC at higher budgets. These results show that learning what to measure is especially valuable when measurements are scarce.

Abstract: Split Inference (SI) addresses the hardware resource limitations of Internet of Things (IoT) devices by distributing tiny Machine Learning (TinyML) model segments across multiple IoT devices. However, a device failure can interrupt the inference pipeline. This paper proposes a replica-aware recovery approach that deploys replicas of TinyML model segments originally hosted on failed devices onto surviving devices. We formulate the joint selection of replica hosts and communication protocols as a mixed-integer linear programming (MILP) problem that minimizes post-reconfiguration inference latency, accounting for computation and transmission latencies, under flash memory and runtime memory constraints. Simulations using MobileNetV2 on heterogeneous IoT networks compare the proposed approach with four baselines. We implement the model in a network of 15 IoT devices with a maximum link-rate reduction of 75%, and show that MILP approach achieves an average modeled end-to-end inference latency that is 6.8% lower than that of Computation Greedy and 18.3% lower than that of Random. Index Terms TinyML, split inference, Internet of Things, fault tolerance, replica placement.

Abstract: In this paper, we study exact online integer priority queues under differential obliviousness in the balls-and-bins model. Given a public upper bound $T$ on the number of operations and assuming that the priorities are bounded by a polynomial in $T$, we construct an $(\eps,δ)$-differentially oblivious priority queue supporting insertion and minimum extraction, which requires $\polylog(T)$ private memory. For constant $\varepsilon>0$ and $δ=\exp(-Θ(\log^2 T))$, our construction incurs $O(\log T/\log\log T)$ expected amortized total work per operation, which breaks the $Ω(\log T)$ barrier for fully oblivious priority queues~[Jacob et al., SODA'2019]. Further, we prove a matching lower bound for $(\eps,δ)$-differentially oblivious priority queues with $\varepsilon=O(1)$ and $δ=o(1)$, which indicates that our construction is asymptotically optimal in terms of total work.

Abstract: Recommender systems are ubiquitous on the Web, making understandable explanations essential for users. Although large language models (LLMs) increasingly generate natural-language justifications, evaluating their factual grounding and personalized relevance remains challenging. Statement-level ranking offers an alternative by selecting concise, review-derived explanations, enabling fine-grained and reproducible evaluation using established ranking metrics. However, existing statement ranking methods largely rely on collaborative representations, while semantic enhancements often fail to outperform simple user-history popularity baselines. Moreover, directly adapting language models for personalized statement ranking remains largely unexplored. In this work, we introduce LMStaR (Language Models for Statement Ranking), a fully text-based framework that formulates personalized explanation ranking as dense retrieval. A query encoder represents the user's interaction history and target-item metadata, while a statement encoder maps candidate explanations into a shared embedding space. Both encoders are jointly adapted through multi-positive contrastive learning to learn personalized relevance. Experiments on Amazon Beauty, Amazon Toys, and Yelp show that LMStaR achieves the highest NDCG@1 across all three domains, outperforming CLER by 1.06--8.25 points (+11.8--65.9%). It also leads top-five ranking on both Amazon datasets, although CLER remains stronger on Yelp. Task-specific adaptation improves all five evaluated backbones and transfers across domains without target-domain fine-tuning. Counterfactual analyses further reveal the importance of user-specific histories. These findings highlight the potential of task-adapted language models for personalized explanation ranking.

Abstract: We study cooperative multi-agent reinforcement learning with decoupled dynamics and a monotone submodular reward function over joint trajectories. Due to the non-additive reward, an optimal policy may depend on the history of all agents. This dependence makes exact optimization exponential in the horizon and the number of agents. To overcome this challenge while retaining theoretical guarantees, we introduce pre-window curvature $c_m$, which quantifies how states visited more than $m$ steps earlier reduce current marginal gains. Using this curvature to control the error from restricting the policy of each agent to depend only on its last $m+1$ states, we propose a greedy algorithm that exploits the decoupled dynamics to optimize local policies sequentially. For fixed $m$, the algorithm achieves a $\frac{1-c_m}{2-c_m}$ approximation guarantee up to estimation error, and its computation time is polynomial in the number of agents and the horizon. We recover the known $1/2$-factor approximation for time-additive rewards and obtain an approximation factor no smaller than the known total-curvature bound for a single agent. We formulate multi-agent traffic monitoring as an example of this framework and evaluate our algorithm on it.

Abstract: A deployed LLM coaching agent answers requests whose correct response depends on player state and game version, so advice that is right for one player can be wrong for the next. We describe TactiNavi, the serving system behind the LLM coach of a commercial open-world game, which makes strategy applicability an explicit artifact shared by offline compilation, online execution, failure diagnosis, and release. An offline compiler turns versioned game evidence and expert guidance into strategy packages with explicit prerequisites, the serving plane evaluates those prerequisites as three-valued conditions over structured player state and records decision traces, and a control plane uses the resulting condition-rule dependencies to validate revisions on held-out traffic before release. In a retrospective evaluation of 1,122 logged coaching turns from three deployment periods, condition-bearing packages raise correctness from 57.9% to 82.0% over atomic facts and reduce strategy misapplication under changed player state from 18.1% to 10.4%, while trace-based claim verification reaches 86.4% precision at a median reply latency of 2.07 s. The deployment also showed that most apparent fixes are generation noise, because an unchanged-system rerun recovers 38.4% of failing turns and only one of 15 shipped revision units passes the release checks retrospectively. We distill these results into lessons on treating applicability as a first-class serving object, sizing traces for later diagnosis, and building the null model into the release path.

Abstract: Existing REST API testing benchmarks focus on isolated services, overlooking failures arising from interactions with downstream dependencies. In microservice systems, response bodies and entry-point operations alone cannot reliably distinguish failures, compromising tool comparisons. We present RESTberus, a Kubernetes-based benchmarking platform for black-box REST API testing tools on deployed microservice systems. By complementing API-level evidence with distributed traces, RESTberus can distinguish failures manifesting in the target service from those manifesting in downstream dependencies. Across six tools on two microservice benchmarks, our trace-aware deduplication strategy achieves 87.1% accuracy, outperforming baselines from prior work by 10-13 percentage points. Our empirical study shows that all tools expose downstream failures, accounting for 11.7% of estimated unique failures on average, which isolated-service benchmarks cannot expose. On single-service benchmarks, RESTberus produces statistically equivalent results to RESTgym, demonstrating that integration-level assessments can preserve compatibility with existing tools and comparability with prior evaluations.

Abstract: Testing expansion asks to distinguish graphs of large conductance from graphs that are far from having large conductance. We study a relaxation in which only part of the graph is required to expand: does an $n$-vertex graph of bounded degree contain an induced expander on a constant fraction of its vertices, when the rest of the graph, including the edges leaving the expander, is arbitrary? Let $P_{α,φ}$ denote the property of containing an induced subgraph on at least $αn$ vertices with inner conductance at least $φ$. For every constant $κ\in(0,1)$, we give a tester that accepts graphs in $P_{α,φ}$ and rejects graphs outside $P_{κα,μφ^2}$, where $μ=Θ_{α,κ}(1/\log n)$, using $O_{α,κ}(\sqrt n\,φ^{-2}\log n)$ queries. For fixed $α\in(0,1]$, $κ\in(0,1)$, and $0<φ\le9/20$, we further show that distinguishing these two classes requires $Ω_{α,κ,φ}(n^{1/2+c_{κ,φ}μ})$ queries for every sufficiently large $n$ and every $0<μ\le1$, where $c_{κ,φ}>0$. The bound holds for adaptive algorithms, uniformly in $μ$. Hence, for testers with $\sqrt n\,\mathrm{polylog}(n)$ queries, the logarithmic loss in conductance is necessary up to a $\log\log n$ factor. The same tester also permits distance-based rejection at a weaker conductance while retaining the original core size. Our tester compares the endpoint distributions of random walks from different vertices with each other, rather than with the uniform distribution. Its analysis uses the trace chain, which observes the walk only at its visits to the unknown expanding core. Our lower bound builds on the noisy-parity construction of [CKK+18], using vector-valued parity labels in $\mathbb F_2^r$ to create many hidden classes, each too small to contain a qualifying induced expander.

Abstract: Latent diffusion and flow matching models are ubiquitous in state-of-the-art generative video models. While highly effective, relying on pretrained autoencoders to compress the data into a lower-dimensional latent space also comes with drawbacks. First, training proceeds in two stages: autoencoder pretraining, with compression and reconstruction objectives, followed by latent generative model training, precluding fully end-to-end training. Second, autoencoders also lead to an inherent loss of signal, and the trade-off between reconstruction quality and generative performance in the latent space is still an active area of research. In this paper we explore the viability of generative video models directly in pixel space. We analyze recent approaches in pixel-space generative modeling of images that rely on basic transformer designs, and identify several shortcomings that limit their effectiveness for the high-dimensional pixel-space video generation. To overcome these limitations, we propose a UNet-like transformer architecture along with improvements to the training recipe and sampling strategy. We conduct controlled experiments, training latent and pixel-space models from scratch on Kinetics-600. For the standard frames-to-video task at 128 resolution, our U-JiT model improves generative FVD by 27% over prior state-of-the-art results, and by 14% against the JiT pixel-space baseline. Scaling to higher 256 resolution, we find the improvement over pixel-space and latent-based models grows as we increase the spatiotemporal compression rate up to $64 \times 64 \times 8$. Finally, we find that U-JiT improves per-frame FID by 27% over latent models and 61% over pixel-space models on class-to-video generation, with respectively 9% and 56% reduction in FVD.

Abstract: Probabilistic time-series forecasting requires models that simultaneously capture structured temporal dynamics, expressive uncertainty, and efficient inference, yet existing approaches fall short of this goal: latent dynamical models impose structure but rely on restrictive generation mechanisms, while modern generative methods such as diffusion and flow matching achieve flexibility at the cost of iterative and computationally expensive sampling. We introduce the Koopman Generative Operator (KGO), a probabilistic forecasting method that conceptualizes prediction as the evolution of structured uncertainty. KGO integrates three core components: (1) Koopman Patch Embedding (KoPE) for temporally consistent latent trajectory extrapolation; (2) Koopman Flow Matching (KoFM), which enables fast, single-step generation through a closed-form matrix exponential in a Koopman latent space, bypassing iterative sampling; and (3) an Adaptive Uncertainty Gate (AUG), which provides probabilistic forecasts by adapting uncertainty per-variable and per-horizon, corresponding to a learned decomposition of aleatoric uncertainty without manual tuning. By unifying these components, KGO achieves state-of-the-art accuracy on 13/17 ProbTS benchmarks in CRPS and 16/17 in NMAE. Further, by eliminating iterative sampling, KGO delivers at least a 25$\times$ reduction in inference time compared to iterative generative models. These results position KGO as a practical and principled framework that advances the accuracy-efficiency trade-off in probabilistic time-series forecasting, combining leading accuracy on the evaluated benchmarks with fast, single-step generation.

Abstract: Fine-grained cross-view localization aims to precisely localize a ground camera against geo-referenced aerial imagery, but current methods typically assume a narrow geographic prior, substantially limiting their applicability when upstream localization remains coarse. To bridge this gap, we study this task over much larger aerial regions. However, this seemingly simple extension fundamentally changes the localization problem: the growing disparity in spatial extent between ground and aerial views makes reliable cross-view matching difficult to establish directly, while the increasing number of look-alike locations in larger regions introduces substantial visual ambiguity. To address these challenges, we propose RingMatch, a search-and-verification framework for wide-area cross-view localization. RingMatch first leverages predictive uncertainty to uncover plausible locations and progressively zooms into their surroundings to obtain increasingly fine-grained evidence, yielding a compact set of promising candidates. We then introduce the depth ring, a novel geometric representation that reveals subtle variations in the spatial layout around a location and serves as a view-shared spatial signature for an LVLM verifier to resolve residual ambiguity. To benchmark this setting, we construct VIGOR-Pro by composing VIGOR aerial tiles into contiguous regions with spatial extents of up to 400 m. Experiments show that RingMatch maintains strong localization performance as the aerial region expands, consistently outperforming representative end-to-end and retrieval-based methods.

Abstract: An activation steering edit should depend on the input exactly when the destination varies \emph{inside} the class a query requests, and that is measurable before any rule is fitted or applied. Contrastive Activation Addition (CAA) adds one fixed direction to every input, the difference of the class means. Conditioning it on the requested class accounts for the between-class variation in the required displacement and leaves the within-class variation untouched, which no rule that reads only the source state can express. We study the impact of increasing input-dependence in the steering edit, moving from a difference of means to a destination retrieved per query --- the mean of the $k$ stored states nearest the query, inside the requested class --- in which the two baselines are endpoints: at $k$ equal to the class size the retrieved rule \emph{is} the class-conditional difference of means. We measure input-dependent steering on six substitution corpora that vary in whether the edit changes a word or a clause, and on an external benchmark, and find that input-dependent steering outperforms fixed-direction steering when the destination varies within the class. Retrieval wins at every layer of every substitution corpus in two models, and the level of input-dependence needed governs how to apply it: word-level edits are best made in the first tenth of the network from a few neighbours, clause-level edits at any depth from the class mean. Where the class already determines the answer the class mean suffices and retrieval only matches it, though a fixed direction still fails there. Four quantities computed from the states alone identify the regime in which the edit should be applied.

Abstract: Hybrid models let neural networks supply the unresolved parameters of a process-based simulator, and are fitted to observations that constrain aggregate fluxes and storages but not the internal partitioning that produces them. Such a fit is equifinal: configurations indistinguishable in the observed aggregates can disagree substantially about the unobserved internals, and therefore about the mechanism they attribute to the same data. We study evapotranspiration, whose total flux is observed while its split into transpiration and evaporation is not. A model ensemble built from random seeds alone spans only a narrow band of the partitionings the data admit. We produce the spread deliberately, training members under auxiliary repulsion on transpiration, subject to the fit to observations not degrading. Non-interference is usually arranged by making the auxiliary gradient orthogonal to the main one, but under AdamW the applied step is a preconditioned momentum direction, so orthogonality between raw gradients no longer implies it. We introduce Non-interfering Asymmetric Network Optimization (NANO), an update whose first-order effect on the main loss is exactly that of the main objective alone, whose auxiliary step is bounded, and which concentrates repulsion in the coordinates the main gradient leaves idle.

Abstract: We introduce iMED, the first synchronized multi-endoscope dataset for robot-assisted minimally invasive surgery (RAMIS), designed to address a fundamental limitation in surgical vision benchmarking: the absence of independent held-out viewpoints. Existing surgical datasets capture single-trajectory sequences from a single endoscope, making it impossible to distinguish geometric generalization from photometric interpolation along a narrow forward-facing path. iMED provides 340 sequences ~170K synchronized timepoints with 4 views per timepoint) recorded simultaneously from two independent stereo endoscopes across ex vivo, postmortem, and live surgical settings, spanning 14 specimens with diverse anatomical regions and motion regimes. The dataset includes calibrated camera intrinsics, ArUco-based frame-wise pose estimates with uncertainty quantification, instrument segmentation masks, and rich clinical metadata. Using a train-on-one-endoscope, test-on-another evaluation protocol, we benchmark 23 state-of-the-art methods across rigid and deformable novel view synthesis, pose estimation, feature matching, and monocular depth estimation. Our experiments show that methods relying primarily on photometric supervision degrade substantially under this held-out-endoscope setting, while methods with explicit geometric regularization are more robust across views in our benchmark. Notably, large-scale foundation models transfer surprisingly well to surgical imagery, often outperforming domain-specific models, suggesting pitfalls in current fine-tuning protocols. iMED establishes a new evaluation protocol for geometric generalization in surgical vision.

Abstract: Recent literature widely used global metrics such as AUROC and AUPRO to quantify the detection performance. AUROC and AUPRO scores are approaching 100% in some public datasets such as MVTec AD dataset and VisA dataset, which misleadingly suggests that the pixel-level anomaly detection task has already been solved. Threshold-independent metrics represented by AUROC inherently ignore the threshold selection process, which is inevitable in practical applications. Although AUPRO restricts the False Positive rates (FPRs) to an acceptable range, extremely low FPRs can lead to increased false negative rates (FNRs). We argue that there is a lack of metrics capable of quantifying the separation between the anomaly score distributions of normal and anomalous samples, which hinders advancements in anomaly detection. In response, we propose the Bounded Area Under the Kolmogorov--Smirnov curve (Bounded AUKS), a partial integral metric that integrates the difference between TPR and FPR within a data-driven bounded range. Specifically, we introduce AUKS from KS integral as a direct measure of separability between the anomaly score distributions. The bounded range is determined only by score distributions of normal test samples. Lower bound excludes the uninformative high-FPR region. Upper bound avoids evaluation in extreme regions that aggressively push FPR towards zero, which result in a very low recall. Our experiments on 9 models across MVTec AD and VisA datasets show that Bounded AUKS can address the limitations of existing metrics and has a better performance in evaluating unsupervised anomaly detection models.

Abstract: We study the comparison-query complexity of computing allocations that are envy-free up to one item (EF1) for $n$ agents with heterogeneous additive preferences over $m$ indivisible items. In this model, the algorithm may only query which of two bundles an agent prefers, without ever observing numerical valuations or costs. Prior work established $O(\log m)$ query bounds for at most three agents, leaving open whether query complexity logarithmic in $m$ is achievable for every fixed $n \ge 4$. We resolve this open question in the affirmative: for every fixed $n\ge2$, we design algorithms that compute EF1 allocations using $O(\log m)$ comparison queries, matching the known $Ω(\log m)$ lower bound. Our results hold for both chores with nonnegative costs and goods with nonnegative valuations.

Abstract: Graph neural network explanations are often evaluated via deletion fidelity, i.e., by deleting their top-ranked edges and measuring the resulting change in model output. Yet, in a message-passing GNN, "deleting an edge" does not specify a unique intervention. Structural deletion removes the edge from the graph and recomputes quantities such as degree normalization and attention, whereas message suppression leaves this structural context intact while blocking the message carried by the edge. The meaning of deletion fidelity therefore depends on what the intervention targets in the model computation. We formalize this distinction and derive sufficient conditions for exact equivalence. The two interventions coincide for additive message passing with edge-set-independent coefficients, but can diverge when aggregation depends on the presence of zero messages or when removing an edge changes the coefficients applied to surviving messages. We then construct intervention-specific edge attributions and evaluate each resulting ranking under both interventions, testing whether their relative fidelity changes with the evaluation intervention. Across nine datasets and a panel of GIN, GCN, and GATv2 models at depths 2--5, all nine GIN controls satisfy the equivalence predicted by the theory. On the target logit, the relative fidelity of the two rankings depends on the evaluation intervention in 10 of 11 reportable GCN and GATv2 cells, and in nine of them each ranking has the larger deletion area under the intervention it was built with. Deletion fidelity is thus not a property of an edge ranking alone. Evaluation protocols should explicitly report the intervention, output functional, target, and perturbation unit, and test alternative intervention semantics when the scientific question does not uniquely determine one.

Abstract: Multicopters are a type of aerial robot seeing extensive real-world applications but with range and endurance as critical bottlenecks. Optimization of its energy efficiency through energy-aware flight planning (e.g. cruise speed-scheduling) has hence been an important topic. The mass of the multicopter is an important factor to consider, as it has a significant impact on efficiency, and many common applications are subject to frequent mass variation due to payload change. This work derives closed-form scaling relationships between the energy-optimal steady horizontal flight behavior of a multicopter and its vehicle mass, and validates them experimentally on two multirotor platforms. Specifically, for mass-only variation, i.e., when payload changes the vehicle mass while the airframe geometry, aerodynamic characteristics, and rotor configuration remain unchanged, we show through a combination of numerical simulation, theoretical derivation, and experimental validation that (1) the energy-optimal velocity is proportional to the square root of vehicle mass; (2) the energy-optimal pitch angle is constant with respect to mass; and (3) the optimal energy per meter is proportional to mass. The analysis shows that these three relationships arise from a common mass-similarity property of the steady-state flight and rotor-aerodynamic equations. Furthermore, the obtained scaling relationships enable simple yet effective cruise-speed planning to optimize energy efficiency and extend the range and endurance of the multicopter.

Abstract: Transaction event sequences support diverse prediction tasks in online commerce and digital financial services. The same transaction records can yield prediction targets with different semantics, including values, changes, and relations to past events. These targets impose different constraints on history representations, but their predictability alone does not establish the downstream utility of a target set. Moreover, target-wise prediction losses do not explicitly model conditional co-occurrence among targets. To address these challenges, we propose TAPES, a task-aligned joint predictive pretraining framework for transaction sequences. TAPES constructs a finite collection of candidate target sets from admissible field-operator combinations. It selects a target set according to the downstream utility of representations learned through short joint pretraining trials under matched budgets. It then reinitializes the encoder and pretrains it on the selected targets through a joint likelihood parameterized by a shared discrete latent variable, before downstream supervised adaptation. Experiments in a real-world transaction-risk setting and on multiple public financial benchmarks spanning diverse downstream tasks demonstrate that TAPES outperforms representative baselines. Ablation studies further validate the contributions of predictive target selection and joint modeling.

Abstract: Compact routing schemes route messages along short paths while every vertex stores little information. We study the trade-off between the stretch and the storage of compact routing schemes in undirected graphs, in four models: labeled and name-independent schemes, with average or worst-case local storage. We improve the best known stretch in all four models. Our main result is a labeled routing scheme with expected stretch $2k-1$ and $\widetilde O(n^{1/k})$ average local storage, in which only the routing is randomized. Under the Erdős girth conjecture, no scheme with this storage has stretch below $2k-1$, so our scheme is optimal, up to polylogarithmic factors in the storage. With deterministic routing, we obtain stretch $\approx2.47k$, the best known deterministic stretch with average storage. Worst-case local storage is the classical setting of compact routing. The leading coefficient $4$ in the stretch $4k-5$ of Thorup and Zwick~[SPAA'01] was improved only by Chechik~[PODC'13], to $\approx3.68$ in unweighted graphs. In unweighted graphs, we obtain expected stretch $(\frac83k+O(1),O(k))$, and deterministic stretch $\approx3.05k$. Name-independent routing is harder, since the source knows only the name of the destination. The best known stretch with $\widetilde O(n^{1/k})$ local storage in unweighted graphs was $96k$, by Abraham, Gavoille, and Malkhi~[DISC'04]. We improve it by more than a factor of $8$. With average storage, we obtain expected stretch $4k-5$, which matches the labeled scheme of Thorup and Zwick. With worst-case storage in unweighted graphs, we obtain expected stretch $(8k+O(1),O(k))$. All our schemes for unweighted graphs extend to weighted graphs with a small loss in the stretch, and still improve the previous unweighted bounds.

Abstract: Min-max multi-criteria optimization asks for a single feasible solution minimizing the maximum of its costs under $\ell$ nonnegative cost functions, a formulation that captures both fairness across groups and robustness across scenarios. It has proved hard to approximate even for basic problems: for robust shortest paths, polylogarithmic approximations are known only in quasi-polynomial time. For network design, the best known guarantee is an $\ell$-approximation, which is tight for the natural LP relaxation. We show that exponentially better and nearly optimal guarantees are achievable for two fundamental network design problems. For multi-criteria connectivity augmentation (MC-CAP), which asks to increase the edge connectivity of a given undirected graph by one, we give a randomized polynomial-time $O(\log \ell)$-approximation algorithm. Applying our augmentation procedure iteratively and analyzing its randomized choices jointly across iterations yields an $O(\log k \log \ell)$-approximation for the multi-criteria $k$-edge-connected spanning subgraph (MC-$k$-ECSS) problem, for every $k \geq 2$. We complement these algorithms with a nearly matching lower bound: for every fixed $\varepsilon > 0$, MC-CAP admits no polynomial-time $O(\log^{1-\varepsilon} \ell)$-approximation, even when the underlying graph is a star, unless $\mathsf{NP}\subseteq\mathsf{DTIME}\bigl(n^{\log^{O(1)}n}\bigr)$. The same hardness extends to the MC-$k$-ECSS problem.

Abstract: RISC-V based AI accelerators have become popular and not only for AI and ML, but also as vehicles for exploring HPC workloads more generally. Tenstorrent are one example, and whilst they document their Tensix architecture in detail and develop their software stack openly, running code has historically required a physical card, and their recently released simulator targets hardware equivalence rather than introspection. In this paper we present Wolfpine, a community developed RISC-V simulator for the Tensix architecture, supporting both the Wormhole and Blackhole generations and integrating seamlessly with the TT-Metal software stack. Constructed entirely from publicly available documentation, open source software and measurements on physical hardware, Wolfpine is written in pure Python for readability and ease of modification. An opt-in, provenance-tracked cost model adds timing fidelity incrementally, and typed event streams, per-component tracing and timeline export enable programmers to identify and diagnose performance bottlenecks that the hardware itself hides.

Abstract: Dor, Halperin and Zwick [FOCS'96; SICOMP'00] showed that $(2-\varepsilon)$-APASP is at least as hard as BMM for every fixed $0<\varepsilon<1$. Zwick [FOCS'98; JACM'02] gave a $2$-APASP algorithm in $\widetilde O(n^{ω+o(1)}\log W_{\max})$ runtime, where $W_{\max}$ is the maximum edge weight. Bringmann, K{ü}nnemann and W{ę}grzycki [STOC'19] removed this logarithmic factor. Using OpenAI's recent bound $ω\leq\frac{9}{4}$ gives $\widetilde O\left(n^{\frac{9}{4}+o(1)}\right)$ time. We present two weighted undirected $2$-APASP algorithms. The first uses $(\min,\max)$-products. Earlier rectangular FMM bounds of Vassilevska Williams, Yinzhan Xu, Zixuan Xu and Zhou [SODA'24] and Alman, Duan, Vassilevska Williams, Yinzhan Xu, Zixuan Xu and Zhou [SODA'25] give $\widetilde O(n^{2.36999465})$ runtime, below the previous $ω\leq2.371177$ of Dupont, Eisenberger, Kozlovskii, Mehrabian, Ruiz, See, Zhou, Alman, Vassilevska Williams and Balog [arXiv'26]. Current rectangular FMM bounds give $\widetilde O(n^{2.34549151})$, independent of $W_{\max}$. For integer weights, our second algorithm has $\widetilde O(n^{ω-\frac{(ω-2)^2}{ω-1}+o(1)}\log^{O(1)}W_{\max})$ runtime, with exponent below $ω$ whenever $ω>2$. The rectangular bounds of Uzna{ń}ski [arXiv'26] or of Amanov, van den Berg and Zuiddam [arXiv'26] give $\widetilde O(n^{2.17157288}\log^{O(1)}W_{\max})$.

Abstract: The reconstruction of fragmented historical textiles presents a significant challenge in computational archaeology. The Oseberg ship burial, dating to 834 CE, yielded hundreds of degraded textile fragments that have resisted systematic computational analysis. While deep learning has revolutionized image-based puzzle solving, progress on archaeological textiles has been limited by the lack of domain-specific datasets and systematic evaluation of modern architectures. To address this gap, we present TEXMET, a curated dataset of 18,644 historical textile images from the Metropolitan Museum of Art's Open Access collection, representing the first textile-specific benchmark for puzzle-solving research. Using TEXMET, we conduct a systematic evaluation of three state-of-the-art puzzle-solving models: JPDVT, FCViT, and DiffAssemble. Our experiments reveal that the transformer-based models pre-trained on standard datasets fail to generalize to textiles, but domain-specific fine-tuning proves highly effective. The graph-based DiffAssemble model, when fine-tuned on TEXMET, achieves 85.89% puzzle accuracy on textile data. Most significantly, applying this fine-tuned model to 45 highly degraded Oseberg fragments yields a performance increase from 26.67% to 64.44% puzzle accuracy. These results establish TEXMET as a new benchmark for textile reconstruction and demonstrate that domain adaptation is essential for applying puzzle-solving methods to imagery of real archaeological materials.

Abstract: In a seminal work [STOC'01; JACM'05], Thorup and Zwick showed that every weighted undirected graph admits a tree cover where each vertex belongs to $O(kn^{1/k})$ trees in expectation, and every pair has a path of stretch at most $2k-1$ in some tree. In this paper, we extend this structural property to directed graphs with nonnegative edge weights. Let $\mathrm{dist}_G(u \leftrightarrows v) = \mathrm{dist}_G(u \to v) + \mathrm{dist}_G(v \to u)$ denote the roundtrip distance. For every integer $k$, we construct a collection $\mathcal{T}$ of tree-pairs, each consisting of an in-tree and an out-tree rooted at the same vertex. Each vertex belongs to $O(kn^{1/k})$ tree-pairs in expectation, and for every ordered pair $(u, v)$ some tree-pair $T_{in}\cup T_{out} \in \mathcal{T}$ satisfies $\mathrm{dist}_{T_{in}\cup T_{out}}(u \to v) \le \mathrm{dist}_G(u \to v) + (k-1)\mathrm{dist}_G(u \leftrightarrows v).$ We call this a \emph{$k$-strong (roundtrip) tree cover}. While prior techniques partition distances into geometric scales and build separate structures for each scale, our construction handles all distances simultaneously within a single, unified hierarchy. This yields the first directed tree cover for general $k$ matching the classic Thorup-Zwick stretch-size trade-off. Our cover immediately implies improved constructions of roundtrip spanners, path-reporting distance oracles, and compact routing schemes, as well as their source-wise and prioritized variants. We also provide faster algorithms for these structures: for general $k \ge 4$, all the above objects can be constructed in $\widetilde{O}(\min\{mn, n^{2.5}\})$ expected time, breaking the $mn$ barrier in dense directed graphs.