跳到正文
研踪PaperTrail

YOUR RESEARCH, IN SIGHT

让下一篇重要论文，不再错过。

覆盖计算机全学科，以 AI 为快捷入口。关注方向、作者和关键词，把发现变成持续的研究积累。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+0新增论文
+0其中 AI 相关
+1已有论文修订
+100新增 AI 导读

arXiv 最近完成扫描：2026-11-08 04:03 · 全站最近入库：2026-11-07 17:43各信源进度 →

统计口径与数据新鲜度

统计 2026-11-07 04:42 — 2026-11-08 04:42（北京时间） · 点击数字查看对应简报；AI 相关包含在新增论文内。

最近完成检查：2026-11-08 04:03最近发现新增版本：2026-11-07 17:43库内论文最新更新时间：2026-11-06 02:59

每分钟刷新已保存的数据。空检查不代表采集异常；新收录可能包含历史论文。AI 导读按新增版本计数。

17,100 已收录论文14,661 AI 相关4,056 有修订112 HF 社区发现

浏览论文库

研究日报 / 周报 →按信源浏览 →

时间范围跟随排序：版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常，查看状态 →

找到 17,100 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-08 04:02（北京时间）
新论文 · v1arXiv:2611.04755

iMED: A Multi-Endoscope Dataset for Surgical 3D Perception

Sierra Bonilla, Fengyi Jiang, Chinedu Nwoye, Jingpei Lu, Kailey Reardon, Humphrey W. Chow, Francisco Vasconcelos, Sophia Bano 等 10 位作者

原文摘要

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.

cs.CV · cs.RO

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04754

Bounded AUKS: A Novel Evaluation Metric for Anomaly Detection via Bounded Area Under the Kolmogorov--Smirnov Curve

Yanshuo Zhang, Juan Du

原文摘要

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.

cs.CV

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04753

Logarithmic Comparison-Query Complexity for EF1 Allocations

Zehan Lin, Shengxin Liu, Biaoshuai Tao, Shengwei Zhou

原文摘要

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.

cs.GT

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04751

What Does It Mean to Remove an Edge? Intervention-Aware Fidelity for Graph Neural Network Explanations

Rocco Mattia Di Mauro, Marco Grassia, Giuseppe Mangioni

原文摘要

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.

cs.LG

查看论文
arXiv ↗PDF ↗
版本更新 · v6arXiv:2409.15955

A Historical Trajectory Assisted Optimization Method for Zeroth-Order Federated Learning

Yu Cai, Canxi Huang, Zike Li, Jing Gong, Xiaoyu He

原文摘要

Federated learning heavily relies on distributed gradient descent techniques. In the situation where gradient information is not available, the gradients need to be estimated from zeroth-order information, which typically involves computing finite-differences along isotropic random directions. This method suffers from high estimation errors, as the geometric features of the objective landscape may be overlooked during the isotropic sampling. In this work, we propose a non-isotropic sampling method to improve zeroth-order gradient estimation. The method uses historical solution trajectories to identify a promising subspace and constructs a non-isotropic Gaussian smoothing that balances exploitation in this subspace with global exploration. We implement this method in zeroth-order federated settings, and show that the convergence rate aligns with existing ones while introducing no significant overheads in communication or local computation. The effectiveness of our proposal is verified on several numerical experiments in comparison to several commonly-used zeroth-order federated optimization algorithms. The experiments cover both independent and identically distributed data and heterogeneous client data distributions.

cs.LG · cs.AI

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04748

Mass Scaling Laws for Energy-Optimal Horizontal Multirotor Flight

Ayush Patnaik, Nicolas Michel, Leonard Baursfeld, Davide Scaramuzza, Xinfan Lin

原文摘要

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.

cs.RO · eess.SY

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04747

TAPES: Task-Aligned Joint Predictive Pretraining for Transaction Event Sequences

Ruobing Zuo, Weiyu Han, Huilin He, Haoyu Jiang, Ze Zhao, Jie Sheng, Xiao Tan, Shuai Chen 等 9 位作者

原文摘要

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.

cs.LG · cs.AI

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2611.01047

How Close to the Theme? Similarity-Label Conditioning for Game Music Generation

Shangxuan Luo, Zixun Guo, Jinjie Shi, Joshua Reiss

原文摘要

Composers develop music from an original idea, controlling how similar each new section is to it, from near repetition to new material. Game music needs this often, as its material repeats over long play. Music models, however, rarely learn to control similarity from real pieces. We further train a pretrained MIDI model on section pairs from Super Mario pieces. A label states each pair's similarity, and a context vector summarises the given section, or context. For 157 test contexts, the model generates six outputs per label. Twelve measures score the outputs; one main measure each covers melody, pitch content, rhythm and note length. On average, outputs requested as similar are more similar to their context than those requested as dissimilar, and not to other pieces. All twelve measures favour them; each main measure stays significant after correction for multiple tests. On melody, the gap comes mainly from more frequent restatement of the context's melody. Against an otherwise identical model without a label, only the request for high similarity makes outputs more similar. In a listening test, ratings followed melodic overlap with the context most closely of all measures.

cs.SD · cs.LG · eess.AS

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04744

Optimal (Randomized) Compact Routing Schemes

Shiri Chechik, Avi Kadria, Gur Lifshitz, Liam Roditty

原文摘要

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.

cs.DS · cs.NI

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04742

Approximation Algorithms for Multi-Criteria Network Design Problems

Mehrshad Taziki, Ali Vakilian

原文摘要

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.

cs.DS

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04740

A RISC-V Simulator for the Tenstorrent Tensix Architecture

Nick Brown, Daniyal Arshad

原文摘要

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.

cs.DC · cs.AR

查看论文
arXiv ↗PDF ↗
版本更新 · v4arXiv:2405.17506

Subspace Node Pruning

Joshua Offergeld, John Chidiac, Marcel van Gerven, Nasir Ahmad

原文摘要

Node pruning is the art of removing computational units such as neurons, filters, attention heads, or even entire layers to significantly reduce inference time while retaining network performance. In this work, we show that a broad family of importance measures, from activation-based to Fisher-based, share a common quadratic form. Through a lower-triangular change of basis, this form yields a pruning subspace in which entire nodes can be removed while the impact of the lost units is simultaneously recovered via linear least squares. Furthermore, the importance measures within our subspace are decoupled and additive through an orthogonalization of the layer activations, allowing multi-node pruning within layers without interference between importance scores. Our method, Subspace Node Pruning (SNP), outperforms the compared baselines on VGG-16 and ResNet-50 on ImageNet. On OPT-125M and LLaMA-2 7B, SNP matches the state-of-the-art LLM Surgeon at a 40-shot schedule and outperforms it whenever fewer shots are used, all without any retraining after pruning.

cs.LG · cs.CV · cs.NE

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04736

Smallest Multiplicative Stretch for an $α$-APASP Below $\widetilde O \left(n^ω\right)$ Runtime

Lakshay Saggi, Ariel Sapir

原文摘要

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})$.

cs.DS

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04734

TEXMET: A Deep Learning Benchmark for Archaeological Textile Reconstruction

Muhammad Hamza Zafar, Davit Gigilashvili, Jon Yngve Hardeberg

原文摘要

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.

cs.CV · cs.DL

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2608.25213

Pseudorandom Functions in $\mathsf{NC}^1$ from LWE/LPN/CDH (Or: How to Build Low-Depth PRFs, Generically)

Youlong Ding, Aayush Jain, Ilan Komargodski

原文摘要

We obtain new $\mathsf{NC}^1$-computable pseudorandom functions (PRFs) from various standard assumptions, resolving several long-standing open problems. Concretely, for the first time, we obtain $\mathsf{NC}^1$-computable PRFs: (1) from the \textbf{Learning With Errors (LWE)} assumption with a polynomial modulus-to-noise ratio, improving upon prior low-depth constructions that required Ring-LWE with super-polynomial ratios [Banerjee-Peikert-Rosen, EUROCRYPT 2012]; (2) from the \textbf{Learning Parity with Noise (LPN)} assumption, removing the need for structured LPN variants [Boyle et al., FOCS 2020], [Ding-Jain-Komargodski, STOC 2025], [Ding-Jain-Komargodski, TCC 2026]; (3) from the \textbf{Computational Diffie-Hellman (CDH)} assumption; prior works relied on the stronger Decisional Diffie-Hellman (DDH) or generalized Diffie-Hellman (GDH) assumptions [Naor-Reingold, FOCS '97, J. ACM '04]. Technically, our results follow from a new generic transformation that converts weak PRFs computable in depth $d(n) = Ω(\log n)$ to (strong) PRFs computable in depth $O(d(n))$. Roughly speaking, our approach combines \emph{tapering} the internal state of the classical GGM tree (so that the per-leveldepth decreases geometrically) with a two-stage security proof that transitions from a computational to an information-theoretic argument.

cs.CC

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04731

Tree Covers for Directed Graphs: Distance Oracles, Routing Schemes and Spanners

Shiri Chechik, Gur Lifshitz

原文摘要

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.

cs.DS

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04730

Finding Integer Roots of Polynomials in Nearly Optimal Time

Yansong Feng, Itamar Nir

原文摘要

Let $f\in\mathbb Z[x]$ be a polynomial of degree $n$ with integer coefficients of absolute value less than $2^b$. Using Pan's approximate factorization theorem, we give a deterministic algorithm that finds all distinct integer roots of $f$ in $\widetilde O(nb)$ bit operations. This matches the bit size of the input up to logarithmic factors and does not require $f$ to be square-free. Since we were unable to verify parts of the running time analysis of Pan's theorem, we also give a self-contained deterministic algorithm with running time $\widetilde O(nb+\min(n,b)^3b^2)$, which is $\widetilde O(nb)$ whenever $b\leq n^{1/4}$. This answers a question of Harvey and Hittmeir (2022), who asked whether integer roots can be found deterministically in quasilinear time, conditionally on Pan's theorem, and unconditionally for $b\leq n^{1/4}$. The fastest previous deterministic algorithm, due to Nir, takes $\widetilde O(n^{3/2}b)$ bit operations and works only for square-free polynomials. Instead of $p$-adic lifting, we combine approximate complex root finding with exact polynomial evaluation. We first approximate the complex roots of the polynomial formed by the top $\min(n,b)+1$ coefficients of $f$. Every integer root $r$ of $f$ with $|r|\geq 2$ lies within distance $2$ of some complex root of this truncated polynomial. Rounding the real parts of the approximate roots therefore gives a list of $O(\min(n,b))$ candidate integers that is guaranteed to contain all integer roots of $f$. Although a single candidate can have up to $b$ bits, a bound via the Mahler measure shows that the bit lengths of all candidates sum to $O(b)$. This allows us to test all candidates by exact multipoint evaluation in $\widetilde O(nb)$ bit operations.

math.NT · cs.DS · cs.SC

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04728

SPOD: Recovering Suppressed Temporal Evidence in Video-LLMs via Single-Pass Orthogonal Decomposition

Yangguang Lin, Quan Fang, Xiaoyan Liu, Zefan Xu

原文摘要

Video Large Language Models (Video-LLMs) have achieved strong performance on many video understanding tasks, yet remain vulnerable to temporal hallucination in time-sensitive reasoning scenarios such as scene transition understanding and event ordering. Existing solutions either require costly retraining or introduce inefficient multi-pass inference and external supervision at test time. In this work, we show that temporal evidence is already encoded in Video-LLM hidden representations but is not fully exploited during standard inference. Motivated by this observation, we propose Single-Pass Orthogonal Decomposition (SPOD), a training-free framework that recovers suppressed temporal evidence through analytical hidden-state manipulation in a single forward pass. SPOD consists of two components: Frame Distinctiveness Analysis (FDA), which identifies salient frames from middle-layer hidden-state geometry, and Temporal Delta Subspace (TDS), which constructs orthogonal temporal and prior subspaces from weighted inter-frame hidden-state differences. By decomposing final hidden states into temporal, prior, and residual components and rescaling them independently, SPOD enhances dynamic information, suppresses static appearance bias, and preserves complementary information. Experiments on VidHalluc, EventHallusion, and VideoMMMU show that SPOD consistently outperforms strong inference-time baselines across temporal reasoning tasks and model architectures while retaining near-vanilla inference efficiency. These results suggest that improving temporal reasoning in Video-LLMs may depend not only on additional supervision, but also on recovering temporal evidence already present in their internal representations. Our code is available at https://github.com/VioAgnes/SPOD.

cs.CV

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2607.17555

Volatility-Aware Extreme Event Detection in High-Frequency Financial Markets

Maorufa Zaman, Haris Md Sahed

原文摘要

Predicting extreme price movements in high-frequency financial markets is a challenging task due to non-stationarity, heavy-tailed return distributions, and severe class imbalance. In particular, rare but impactful events are often difficult to detect using conventional modeling approaches, which typically treat extreme movements as isolated observations. This study proposes a volatility-aware approach for extreme event detection using high-frequency Bitcoin limit order book (LOB) data. Motivated by empirical evidence of volatility clustering, the target formulation is extended to incorporate both large future returns and high-volatility regimes. This redefinition increases the proportion of informative samples and aligns the learning objective with the underlying market dynamics. Using a tree-based model (XGBoost) with time-series cross-validation and imbalance-aware evaluation, the proposed method achieves a Precision-Recall AUC of approximately 0.40, significantly outperforming the baseline formulation with a PR-AUC of around 0.06. This represents more than a sixfold improvement in detecting rare events. The results highlight that target design plays a critical role in financial machine learning, often exceeding the impact of model complexity. By incorporating volatility structure into the labeling process, the proposed approach provides a more effective and realistic framework for extreme event detection in high-frequency cryptocurrency markets.

cs.LG

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2609.34091

From Perturbation Sensitivity to Sparse Autoencoder Feature Interpretation: An EEG Foundation-Model Case Study

Yucong Cao, Chenqi Li, Tingting Zhu

原文摘要

Sparse autoencoders (SAEs) split a model's internal activity into many sparse units, or latents, and a latent is often named after a concept when removing that concept from the input changes its activity. We identify a consequential confound in this inference: if removing the concept changes the input more than the comparison edit does, a larger response may reflect a larger edit rather than the concept. Brain-signal (electroencephalography, EEG) models provide a controlled test, because how much an edit changes the EEG input can be measured directly. We measure the SAE response as the change in how often each latent is active, averaged over all latents. Across 27 combinations of model, dataset, and layer, removing the 8--12 Hz alpha band changes this response 7.33 times as much as removing an equally wide 30--34 Hz control band, but it also changes the signal far more. Matching the two edits per trial on squared time-domain distortion lowers the mean ratio to 1.42, with 19 of 27 combinations above one. Matching thus substantially reduces, but does not eliminate, the alpha--control contrast. The residual supports relative sensitivity under this single control, not general spectral specificity or an individual alpha-representing latent. We use an evidence-to-claim map to separate what this comparison supports from stronger claims of specificity and feature semantics.

cs.LG

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04725

Self-stabilising approximate clock synchronisation requires linear time

Joel Rybicki

原文摘要

Synchronising the clocks of processes is a fundamental problem in distributed computing. We consider message-passing systems in which processes start in an arbitrary initial state (self-stabilisation) and up to $f$ processes may be non-transiently faulty. It is well known that synchronising clocks \emph{exactly} is at least as hard as consensus and requires $Θ(f)$ time. In contrast, without self-stabilisation, clocks can be synchronised \emph{approximately} much faster, in time independent of the number of non-transient faults [Srikanth and Toueg, JACM 1987; Welch and Lynch, Inf. Comput. 1988]. In this work, we show that deterministic self-stabilising approximate clock synchronisation tasks require $Ω(f)$ time to stabilise. This gives the first non-trivial time lower bound for these tasks, whose time complexity has remained open for over two decades [Dolev and Welch, JACM 2004; Dolev, Függer, Schmid and Lenzen, JACM 2014]. In particular, this answers the open question whether self-stabilising approximate clock synchronisation tasks are as hard as consensus or as easy as approximate agreement [Lenzen and Rybicki, JACM 2019]. The results show that guaranteeing \emph{both} transient and non-transient fault-tolerance simultaneously is expensive even for approximate synchronisation tasks. The lower bounds hold in a very strong model: the faulty processes can only crash, the local clocks of processes have no clock drift, and the message delay is bounded and known to all processes. The proof is based on a combinatorial topological argument showing that no fast finite-state protocol can ensure that the clocks behave consistently across all executions. To our knowledge, this is the first use of topological arguments to prove time lower bounds in the self-stabilising setting.

cs.DC

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2604.26707

CurEvo: Curriculum-Guided Self-Evolution for Video Understanding

Guiyi Zeng, Junqing Yu, Yi-Ping Phoebe Chen, Chen Xu, Wei Yang, Zikai Song

原文摘要

Recent self-evolution frameworks for video understanding have demonstrated the potential for autonomous improvement from unlabeled videos. However, existing approaches often suffer from weakly controlled optimization and capability progression because they lack structured guidance for generating, evaluating, and reusing supervision throughout the iterative learning process. We present CurEvo, a curriculum-guided self-evolution framework that organizes this loop as a competence-aware progression. Curriculum-Guided Self-Evolution maintains a competence-aware curriculum state and cumulative training pool across iterations. Within this loop, Multi-Dimensional Question Generation supplies complementary supervision, from directly verifiable structural questions for perception to type-conditioned questions for recognition and understanding. Type-Adaptive Evaluation separately assesses question quality and answer reliability with criteria matched to each type's evidence; its scores determine which pairs enter the pool and how the next curriculum state is updated. Across seven backbones and four VideoQA benchmarks, CurEvo consistently improves benchmark accuracy and benchmark semantic score. For Qwen2.5-VL(7B), accuracy rises from 67.84% to 69.91% on ActivityNet-QA and from 76.94% to 79.61% on NExT-QA. CurEvo thus establishes self-generated supervision as a stable route to autonomous video understanding without task-specific human QA annotations during self-evolution.

cs.CV · cs.LG

查看论文
arXiv ↗PDF ↗
版本更新 · v4arXiv:2608.21290

VT-MUSE: Multimodal Unified Sequential Visuotactile Representation Learning for Manipulation

Congsheng Xu, Qiaochu Yang, Fangyuan Shi, Yifan Han, Baijun Chen, Yiming Wang, Haonan Zhao, Zhe Liu 等 12 位作者

原文摘要

We propose VT-MUSE, a Multimodal Unified SEquential representation learning framework for visuotactilemanipulation. Existing approaches often encode visual and tactile observations independently before fusion, limiting their ability to capture fine-grained cross-modal dependencies. Moreover, most methods focus on observations at the current time step and overlook the temporal evolution of contact. VT-MUSE addresses both limitations through a two-stage representation learning framework. In Stage I, modality specific encoders are jointly adapted via cross-modal temporal alignment and masked-view consistency. In Stage II, a conditional variational latent model processes masked visual sequences together with full tactile histories. Auxiliary decoders reconstruct the masked recent visual observations and predict tactile depth changes, encouraging the latent representation to retain both global visual context and local contact dynamics. The learned representation is subsequently integrated into a lightweight Transformer policy through gated cross-attention. On the simulation benchmark, VT-MUSE outperforms the strongest baseline evaluated on all tasks by 11 percentage points and also achieves substantial improvements in real-world experiments.

cs.RO · cs.CV

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04721

Pure Differentially Private Query Release via Laplace Input Smoothing

Zongrui Zou

原文摘要

We study the offline release of a public family of $k$ statistical queries on a database of $N$ records from a public universe of size $d$, under pure $\varepsilon$-differential privacy. We give an efficient algorithm that, with probability at least $1-β$, answers all queries simultaneously to error $$O\left(\min\left\{1,\sqrt{\frac{\log(d/β)\log k}{N\varepsilon}}\right\}\right).$$ The output is a synthetic histogram on the data universe, and its running time depends polynomially on $N,d$ and $k$. This resolves a conjecture of Nikolov and Ullman (2021) with an efficient, polynomial-time construction. Fitzsimons (2026) recently established the same square-root error scale via an information-theoretic construction that relies on a computationally intractable Lipschitz envelope over the exponential space of possible outputs. In contrast, we introduce an input-side smoothing approach: we run a selection-only multiplicative-weights process after a single sparse Laplace perturbation of the input histogram. Departing from standard first-order stability analyses, we investigate the stability of stability by establishing a uniform lower bound on the second-order log-derivatives of the output transcript across $T$ rounds of multiplicative weight updates. We then develop an analytic smoothing principle showing that this curvature bound allows a sparse, coordinate-wise perturbation to guarantee pure differential privacy globally, attaining optimal utility through a conceptually simple, polynomial-time pure-DP mechanism.

cs.DS

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04720

OneTrans-GSR: A Generative Slate Ranking Paradigm Unifying Reranking and Mix-Ranking with One Autoregressive Transformer

Feng Cheng, Yu-Hsuan Huang, Fengyi Wang, Chaofan Zhou, Zhennan Zhu, Huan He, Bo Zhang, Ruoqi Zhang 等 16 位作者

原文摘要

Industrial recommender systems allocate substantial computation to pointwise candidate scoring, yet separate reranking and mix-ranking stages still assemble the final exposure slate using hand-crafted rules and specialized low-capacity models. Mix-ranking combines product cards, short videos, livestreams, and advertising cards supplied by distinct upstream business channels. Although these rules and models encode valuable domain knowledge, they are inherently limited in leveraging additional data and computation. They constrain the combinatorial space of candidate slates and determine objective trade-offs through manual tuning. To enable scalable and effective slate generation, we reformulate reranking and mix-ranking as a unified learning problem whose performance can improve with computation. Specifically, we instantiate this formulation across the reranking and mix-ranking stages and propose OneTrans-GSR, a single decoder-only policy that extends our deployed OneTrans backbone to generate the exposure slate end-to-end. During training, a reward model evaluates complete slates and guides reinforcement learning toward slate-level and long-term objectives. During decoding, business constraints are explicitly enforced. Offline evaluation shows that slate quality consistently improves as reward-model and policy compute increase. Deployed in a large-scale industrial recommendation system, OneTrans-GSR mixes heterogeneous content types within a unified slate. In online A/B tests, it improves GMV/u by 2.63%, advertiser value by 2.06%, and repurchase rate by 2.03%, while reducing end-to-end latency across the reranking and mix-ranking stages by 13%. These results mark a paradigm shift in slate generation: moving beyond human-engineered heuristics toward a general learned policy creates a scalable path for further algorithmic optimization and compute-driven improvement.

cs.IR

查看论文
arXiv ↗PDF ↗
版本更新 · v3arXiv:2610.15897

Review Rarely Beats the Stronger Model: Separating Verification from Capability Transfer in LLM Pipelines

Yirui Zhang, Yash Raj Shrestha

原文摘要

Qwen3-8B reviewing Llama-3.1-8B in math adds 33.2 points, yet Qwen3-8B alone is 6.4 points more accurate than the result. Reviewing another model's answer is usually judged by its gain over the generator. We show that this confuses verification, which adds accuracy beyond either model alone, with capability transfer, where a stronger reviewer supplies answers it could have given on its own. Measured against the stronger model alone, across 48 pairs of 12 open-weight models (3B to 72B) in math, knowledge, code and reasoning, review beats it in only 9 of 96 review directions, and does worse the larger the capability gap. The reason is anchoring: the reviewer mostly follows the generator, discarding its own correct answers. Review costs 2.6 to 2.8 times as much as the stronger model alone, while a selector using the same two calls is 2.7 to 4.2 points more accurate than review and cheaper. Studies of verification should report the stronger model alone, not only the gain over the generator.

cs.CL · cs.AI

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04717

BrainwashedLLM: Jailbreaking via Automated Adversarial Chain of Thoughts Discovery

Masoud Poorghaffar Aghdam, Göktuğ Serdar Yıldırım, Sinem Sav

原文摘要

Large Reasoning Models (LRMs) achieve strong performance on complex tasks by generating explicit Chain-of-Thought (CoT) reasoning, but the safety implications of this intermediate reasoning surface remain underexplored. We demonstrate that the reasoning trace itself is a powerful attack vector. Safety alignment in large models is substantially less robust to malicious reasoning embedded in the context than to direct imperative prompts. We introduce BrainwashedLLM, a weak-to-strong adversarial framework that automates the discovery of reasoning-based jailbreaks. First, we use Group Relative Policy Optimization (GRPO), a Reinforcement Learning (RL) algorithm, with a multi-objective rule-based reward to fine-tune a small, white-box source model to generate adversarial reasoning traces. Crucially, the reward is computed entirely over the source's own reasoning trace. Second, we show that these traces transfer in a zero-shot manner. When traces are injected as input prefixes, they steer larger black-box LRMs to continue the adversarial reasoning and produce harmful outputs, without requiring prompt optimization, gradient access, or any form of output feedback from the target model. Across four state-of-the-art LRMs that span distinct architectures, BrainwashedLLM achieves ASR@5 between 0.74 and 0.98 across targets, within 16 points of query-based baselines, without querying the target during attack construction. To our knowledge, this is the first framework to use RL to directly optimize the CoT of LRMs as an attack surface without any target feedback, and the first to demonstrate zero-shot weak-to-strong transfer of reasoning traces. Our results suggest that exposed CoT is a vulnerability in LRMs and motivate architectural defenses that isolate the reasoning buffer. Warning: This paper contains potentially offensive and harmful text.

cs.CR

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2608.19505

Counting Linear Extensions Faster than $2^n$

Keigo Oka

原文摘要

We give a deterministic algorithm that counts the linear extensions of any $n$-element poset in $O^*(33^{n/6}) \le O^*(1.791^n)$ time and space, breaking the $O^*(2^n)$ barrier of standard order-ideal dynamic programming without assumptions on height, width, or dimension. Our algorithm fixes an antichain $B$ and tracks order ideals only on the remaining core $V \setminus B$. For each element $v \in B$ that has successors in the core, we guess which of those successors appears first in the linear extension, reducing all upper constraints on $v$ to a single deadline. An element $v \in B$ becomes available once all of its core predecessors have been placed; available elements with the same deadline then face identical remaining constraints, so the dynamic program only needs to record how many available elements have each deadline and weight transitions by the number of choices for the next element. Taking $B$ to be a maximum antichain and balancing this dynamic program against a Dilworth chain partition yields an $O^*(1.89^n)$ algorithm. To obtain our main bound, we use a minimum-cut computation in an auxiliary bipartite network to find an antichain $B$ whose comparability neighborhood $R$ satisfies $|B| \ge 5|R|$ while the remainder $V \setminus (B \cup R)$ partitions into stars with at most five leaves. Since a $j$-leaf star has $2^j+1$ independent sets and $(2^j+1)^{1/(j+1)} \le 33^{1/6}$ for $1 \le j \le 5$, combining the star bound on the remainder with our state bound on $B \cup R$ gives $O^*(33^{n/6})$ time and space.

cs.DS

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04715

ZeroGR: Filtering-First Constrained Decoding for Generative Recommendation

Xiangrui Yang, Jiawei Yang, Liang Zeng, Daqian Ding, Ziqian Liu, Bing Tian, Cheng Peng, Yunfeng Zhao 等 12 位作者

原文摘要

Generative recommendation is gaining traction in production, retrieving items by generating their identifiers one token at a time. The generated sequences must identify relevant catalog items, so constrained decoding couples relevance scoring with validity filtering. Because most possible sequences are invalid, scoring before filtering wastes computation on candidates that will be discarded. Our evaluation shows that filtering first can avoid this work with negligible impact on recommendation quality. We present ZeroGR, a filtering-first constrained decoding system for generative recommendation. ZeroGR uses a step-sliced filtering index to reduce GPU memory use by tailoring data representations to each decoding step. Its execution engine adopts shared-slot execution to accelerate data exchange across stages and hybrid projection to adapt computation to workload patterns, thereby reducing execution overhead. During index refreshes, ZeroGR applies layout-guided streaming construction to speed up updates and limit serving interference. Extensive evaluation shows that ZeroGR accelerates the filtering and scoring pipeline by up to $9.9\times$ over representative baselines while reducing GPU index memory use and accelerating index reconstruction.

cs.DB · cs.IR

查看论文
arXiv ↗PDF ↗
版本更新 · v3arXiv:2609.31107

Bayesian Optimization with Fisher Information Geometry: Gradient Bounds and Trust-Region Methods

Saksham Kiroriwal, Julius Pfrommer, Jürgen Beyerer

原文摘要

We study Bayesian optimization (BO) through the lens of information geometry. Pulling back the Fisher information metric through the surrogate posterior map yields a local sensitivity tensor on the input space, which leads to an upper bound on the gradient of reparameterizable acquisition functions (AFs). This view explains vanishing-gradient behavior in high-dimensional BO and provides a common interpretation of heuristics such as RAASP and dimension-scaled lengthscales. The upper bound can also serve as a generic recipe to understand the behavior of new acquisition functions or surrogates in high input dimensions as well. Using the bounds, we also identify necessary conditions for an input location to be an optimizer of the AF for a univariate Gaussian predictive posterior. Building on this analysis, we propose FITR, a trust-region-based BO method that replaces lengthscale-based scaling with local pullback-Fisher weights. FITR is not restricted to GP kernels with explicit lengthscales and easily generalizes to non-isotropic surrogates. FITR shows competitive performance on several benchmarks.

cs.LG · cs.AI · cs.IT

查看论文
arXiv ↗PDF ↗