跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

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

全站更新概况

+479新增论文
+361其中 AI 相关
+64已有论文修订
+95新增 AI 导读

arXiv 最近完成扫描:2026-11-16 01:34 · 全站最近入库:2026-11-16 21:56各信源进度 →

统计口径与数据新鲜度

统计 2026-11-16 01:45 — 2026-11-17 01:45(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-16 01:34最近发现新增版本:2026-11-16 21:56库内论文最新更新时间:2026-11-14 02:59

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

23,827 已收录论文19,941 AI 相关6,922 有修订112 HF 社区发现

浏览论文库

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

找到 17,708 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-16 01:33(北京时间)
新论文 · v1arXiv:2611.05669

The Harmonic Online $k$-Server Algorithm Is Poly(k)-Competitive

Yichen Huang

原文摘要

The online $k$-server problem is one of the most fundamental problems in online algorithms. In this problem, $k$ servers are located in a metric space and serve a sequence of requests at points in the metric space by moving a server there. The Harmonic algorithm is a very natural algorithm: it chooses a server with probability inversely proportional to its distance from the request. It is also highly efficient, being memoryless and answering each request in $O(k)$ time. However, its competitive ratio has remained unsettled between the $O(2^k \log k)$ upper bound (Bartal and Grove, JACM 2000) and the $k(k+1)/2$ lower bound (Raghavan and Snir, 1994, IBM J. Res. Dev.). We prove that Harmonic is $2k^4$-competitive on every metric space against adaptive online adversaries. Our analysis uses a potential combining corrected electrical energy with the distances of online servers to their assigned adversary locations.

cs.DS

新论文 · v1arXiv:2611.05668

Sundance: A Simple SMT Solver for Program Verification

Amar Shah, Benjamin F. Jones, Can Cebeci, Jason Z. S. Hu, Lee A. Barnett, Rémi Delmas, Marijn Heule, Bryan Parno 等 9 位作者

原文摘要

We present Sundance, an SMT solver for program verification written in about 13,600 lines of Rust. Sundance combines the Cadical SAT solver with congruence closure, linear arithmetic, algebraic datatypes, and pattern-based quantifier instantiation. Sundance produces eDRAT proofs for every unsat answer. On 21,531 queries from Verus, Dafny, and F*, Sundance is comparable to existing solvers, with 26--38 times fewer lines of code than Z3 and cvc5. We further show that its components can be swapped for Z3's arithmetic solver, MiniSat, and the Semper e-graph. We have open sourced Sundance.

cs.LO

版本更新 · v2arXiv:2610.24973

A Bulow-Klemperer Theorem for Bundling and Improved Approximation Bounds for Simple Auctions

Yichen Huang

原文摘要

We study simple auctions for one additive bidder whose values for $m$ items are independent. Write $\mathrm{REV}$ for the optimal revenue, $\mathrm{SREV}$ and $\mathrm{BREV}$ for the optimal revenues from separate selling and grand bundling, and $\mathrm{BSPA}_2$ for the grand-bundle second-price revenue with two independent bidders. For independent regular items, we prove $\mathrm{REV} \le \mathrm{BSPA}_2 \le 2\,\mathrm{BREV}$. Thus, one additional bidder lets a reserve-free second-price auction for the grand bundle match the optimal revenue from one bidder, regardless of the number of items. This gives a Bulow-Klemperer theorem for bundling and resolves an open question of Beyhaghi, Cai, Feng, Li, and Weinberg (EC 2025) on whether constant competition suffices for bundling. The factor-$2$ bundling approximation is also tight. For general independent items, we prove $\mathrm{REV} \le \mathrm{SREV} + \frac{π^2}{6}\mathrm{BREV} \le 2.645 \max\{\mathrm{SREV}, \mathrm{BREV}\}$. This improves the previous approximation factors of $6$ from Babaioff, Immorlica, Lucier, and Weinberg (FOCS 2014, JACM 2020) and $5.2$ from Ma and Simchi-Levi (AISTATS 2021). For the lower bound, we construct an instance in which pricing three disjoint bundles earns more than $2.11\max\{\mathrm{SREV},\mathrm{BREV}\}$, improving the previous lower bound of $2$ from Rubinstein (ITCS 2016). Together, these results narrow the tight approximation ratio to the range $[2.11, 2.645]$.

cs.GT · econ.TH

版本更新 · v4arXiv:2606.28079

GTI-mSEMP Framework : A Proposed Framework to Simulate Malware Propagation with Inclusion of Attacker-Defender Strategy

Shadeeb Hossain, Elias Calboreanu, Kristopher Wilson

原文摘要

The rapid proliferation of automated, multi-vector malware threats poses a significant risk to heterogeneous, resource constrained cyber-physical networks. Conventional epidemiological models often treat security defenses as static parameters, failing to capture the strategic, asymmetric maneuvers between an attacker and a defender. To address the gap, this paper proposes a Game-Theory-Integrated Modified Multi- Wireless Sensor Epidemic Malware Propagation (GTI-mSEMP) framework. This paper analyzed and compared the operational trajectories of Susceptible (S) and Recovered (R) node populations across three different operational regimes: Balanced Matchup, Exploit Surge and Hardened Defense. Numerical simulation results capture the real-time transient dynamics of the network state variables, demonstrating how the epidemic curve shifts when either the defensive or offensive scaling vectors hold an efficiency advantage. The proposed mathematical and numerical framework provides a rigorous foundation that can be deployed in highly adversarial network environments to evaluate dynamic malware propagation and predict localized node population states.

cs.CR · cs.GT · cs.NI

版本更新 · v2arXiv:2609.13044

Robust Policy Optimization via Adversarial Importance Sampling

Amine Andam, Jamal Bentahar, Mustapha Hedabou

原文摘要

Significant progress has been made in safeguarding Deep Reinforcement Learning (DRL) policies against input perturbations. Developing robust DRL involves three main stages: algorithm design, implementation, and evaluation. In this work, we identify and address a key limitation at each stage. First, we introduce Adversarial Importance Sampling (Advis), a method that estimates and optimizes worst-case returns directly from trajectories already collected during standard training. Advis satisfies three desirable criteria that prior work does not jointly achieve: it requires no additional environment interactions, no auxiliary networks, and captures long-term robustness. Second, we introduce advrl, a modular PyTorch library that provides clean, single-file implementations of existing robustness methods and adversarial attacks, enabling rapid prototyping and reproducible evaluations. Third, we revisit evaluation under learned adversaries and show that optimal adversarial hyperparameters do not transfer across agents, which can lead to an overestimation of robustness when using a limited set of attacker configurations. Accordingly, we evaluate policies against a large and diverse set of attackers, using 6 to 14 times more configurations than prior work. Finally, experiments on continuous control environments show that Advis achieves stronger worst-case performance and greater training efficiency than existing baselines.

cs.LG

新论文 · v1arXiv:2611.05666

Revisiting Critic Estimation in Soft Actor-Critic Algorithms

Jan Felix Kleuker, Koen Ponse, Aske Plaat, Thomas M. Moerland

原文摘要

Soft Actor-Critic (SAC) is a widely used deep reinforcement learning algorithm that combines entropy regularization with an actor-critic architecture. Standard implementations rely on one-step temporal-difference learning of Q-functions, yet alternative critic design choices remain underexplored. In this work, we revisit three such choices: learning soft advantages instead of soft Q-values, the use of multi-step return targets, and the training of multi-step critics from replay buffer data. Keeping the policy objective fixed, we compare the six critic variants these choices generate: (i) advantage and (ii) dueling-advantage critics learned from one-step transitions, and $λ$-return and soft Generalized Advantage Estimation (GAE) critics learned either (iii, iv) on-policy or (v, vi) from replayed trajectory segments. Each variant is evaluated across an entire random hyperparameter search on fourteen tasks, treating the hyperparameters as part of the algorithm. Learning soft advantages instead of soft Q-values does not improve performance, and the soft GAE critic adds nothing over the simpler $λ$-return critic. What does improve performance, most clearly on continuous control, is training a $λ$-return critic on replayed trajectory segments, even without importance weighting or trace cutting. This extends earlier evidence that uncorrected multi-step targets work well under replay to the full soft $λ$-return, entropy terms included. By design, the underlying ideas studied here extend beyond SAC, and our empirical findings aim to encourage their application to a broader class of reinforcement learning algorithms.

cs.LG

版本更新 · v2arXiv:2608.07163

Rate-Fidelity Control for Wide-Area Quantum Links

Connor Clayton, Cory Nunn, Quinn Carmack, Wayne McKenzie, Anne Marie Richards, Xiaodi Wu, Bobby Bhattacharjee

原文摘要

Quantum network links must distribute entanglement at high rates while satisfying application-specified fidelity demands. However, wide-area deployed fiber links suffer from polarization drift which destabilizes end-to-end fidelity and forces periodic compensation. Current deployments often use active stabilization with fixed control policies, and improvements generally stem from advances in quantum hardware. Meanwhile, software control remains relatively underexplored. Here, we formulate quantum link operation as a joint control problem over tunable rate-fidelity tradeoffs and uncontrollable link drift. From this framework, we construct a link control protocol that dynamically adapts source pump power and polarization compensation to maximize entanglement distribution rate subject to a minimum fidelity constraint. We evaluate the protocol through trace-driven simulations driven by data from a 64 km deployed optical fiber. Compared with optimized static policies, our adaptive controller improves mean entanglement distribution rate by 14% over a 24 hour trace, without requiring any offline policy optimization. Our results show that software-based physical layer control can provide a practical mechanism for improving near-term quantum link performance without requiring additional quantum hardware.

quant-ph · cs.NI

新论文 · v1arXiv:2611.05658

Beyond Accuracy: Information-Theoretic Decoder Evaluation Under Latent Intent

Tasha Kim, Benjamin Ballyk, Anson Lei, Ingmar Posner, Oiwi Parker Jones

原文摘要

A central challenge in assistive brain-to-robot control is decoding a user's latent intent from complex and noisy brain signals. Prior approaches evaluate decoders as single-trial classifiers with accuracy-based metrics, but this neglects the inherently sequential nature of assistive control. Since a planner must integrate intermittent, noisy decoder outputs over time, single-step accuracy can only be a proxy when predicting downstream task performance. We formalize brain-to-robot control as a partially observable Markov decision process (POMDP), and prove that there is a sharp phase transition: regret is uniformly bounded across the horizon as long as pairs of goals are all decoder-distinguishable, but grows linearly otherwise. We show that a single channel statistic, the worst-pair Chernoff information $Γ_{\min}$ sets this boundary. Then, we derive a closed-form regret predictor $U_{\mathrm{id}}(C)$, that can be computed from any confusion matrix in $O(K^2)$ time. Across two domains spanning orthogonal information channels, we show that $U_{\mathrm{id}}$ predicts cumulative planning regret beyond what accuracy can explain. We then highlight a pathological accuracy trap, in which two decoders have identical validation accuracy 35.1% on real EEG data (BNCI2014001 subject 5) but result in a difference of $9.6\times$ in held-out regret, which $U_{\mathrm{id}}$ predicts. Same-signal control confirms $U_{\mathrm{id}}$'s advantage with decoders that span independent feature channels. Ultimately, our work provides a drop-in diagnostic to evaluate and select sensors and decoders in sequential assistive control.

cs.LG · cs.RO

新论文 · v1arXiv:2611.05652

Quantifying Trait-State Hierarchy in EEG Foundation Model and Signal Processing Embeddings

Anusha Madapura, Aditya Kommineni, Shrikanth Narayanan

原文摘要

Electroencephalography (EEG) measures brain activity through recording electrical potentials of the scalp. EEG recordings capture two distinct sets of characteristics in the signal: (1) \emph{Traits} -- information that remains relatively constant over the course of a recording session, such as subject identity, age, and sex; (2) \emph{States} -- signatures that encode responses to external stimuli, including visual, auditory, and motor information. There is limited understanding of how different EEG modeling features (signal processing and foundation models) encode state and trait characteristics. In this work, we quantify state- and trait-level features captured by EEG embeddings using a hierarchy metric and kNN purity on Brain-Computer Interface dataset trials, and find that a majority of EEG features form a macro-trait hierarchy (embeddings form trait-level clusters with micro-states within). Our linear probe results indicate that this hierarchy structure leads to suboptimal state distinguishability, negatively impacting BCI performance of EEG foundation models. To mitigate this, we explore normalization techniques that reduce trait-specific information in embeddings and provide a $\sim$ 10\% improvement in balanced accuracy for state classification. Additionally, we observe that when fine-tuning models for downstream state decoding, embedding spaces transform from macro-trait to macro-state hierarchies, which in turn lead to better state decoding.

cs.AI · cs.LG

版本更新 · v3arXiv:2606.18902

SAGE: Stochastic Prompt Optimization via Agent-Guided Exploration

Ziyi Zhu, Luka Smyth, Saki Shinoda, Jinghong Chen

原文摘要

Context engineering has emerged as a primary lever for improving AI systems without parameter updates. Recent work showing that textual gradients do not function as real gradients motivates treating automatic prompt optimization (APO) as black-box search. We introduce SPO (Stochastic Prompt Optimization), a framework for stochastic search over prompt space, and compare three strategies of increasing sophistication: error-informed random search, a genetic algorithm with evolutionary operators, and SAGE (SPO via Agent-Guided Exploration), a multi-agent pipeline with diagnostic code execution. Across three benchmarks, no single strategy dominates; effectiveness depends on the interaction of landscape structure with error type. We further deploy SAGE on a mental-health chatbot under a continuous optimization paradigm, where it compounds eight cycles of individually-noisy A/B tests into a statistically robust gain in next-day retention. We argue that coupling qualitative diagnosis with quantitative validation is what makes agentic optimization effective for open-ended task-oriented dialogue.

cs.CL

版本更新 · v2arXiv:2607.01546

The General Stability of Ranking

Houming Chen, H. V. Jagadish

原文摘要

Rankings derived from weighted scoring functions are widely used in university rankings and employment candidate evaluations. Since ranking weights are often chosen by organizations or analysts, ranking stability asks whether a reported ranking persists under reasonable weight changes. Prior work defines volume-based stability as the fraction of the weight space that induces the target ranking exactly. This exact-match requirement can be too blunt: once a perturbed weight vector produces a different ranking, exact stability gives it no credit, whether the change replaces the top-ranked item or only swaps two nearly tied lower-ranked items. We propose general stability, a distance-based generalization that aggregates ranking regions according to a user-defined distance from the target ranking. This lets users specify which ranking changes matter in the application, while recovering exact stability as a special case. We extend existing methods and identify distance properties that permit faster general-stability computation with accuracy guarantees. Our sampling algorithm, $GSC_{md}$, can take exponential time in the worst case, but a property we call uniform boundedness gives a sample budget independent of database size and dimension at fixed accuracy and confidence. We develop Prefix-GSC, a sampling optimization that reduces sorting for distances satisfying a further property, tail decay with bounded influence. We also develop Conv-SC to approximate stability through convex volumes for distances satisfying a property we term quasiconvexity. Experiments on seven real-data sources and generated inputs show how distance affects robustness conclusions and when the algorithms save time. On three 500-item university datasets, Prefix-GSC achieves median query speedups of $1.22$--$1.98\times$ over $GSC_{md}$ at 2% relative error and 95% confidence, including method setup.

cs.DB

新论文 · v1arXiv:2611.05646

ARIDA - Active railway infrastructure dataset annotation using neural network predictions

Maximilian Dornik, Christian Sieberichs, Simon Geerkens, Alexander Braun

原文摘要

Modern railway perception requires large comprehensive image datasets, but creating them is slowed by manual labeling, especially for track polylines and other complex infrastructure geometry. This paper presents the Active Railway Infrastructure Dataset Annotation framework, a railway-specific semi-automated pipeline that converts instance predictions from a mask scoring instance segmentation network into bounding-boxes, polygons, polylines, and paired polylines. To keep automatic track geometry annotation reliable without ground truth, it applies confidence thresholds and an unique contour-agreement quality score as an acceptance gate. An active learning loop ranks remaining images by uncertainty and adapts the number of manual queries per cycle. This is achieved through a novel quantity control mechanism, in which easy images are auto-accepted and human effort targets hard cases. Experiments on disjoint, diverse imagery and time-sequential, redundant imagery quantify effort reduction and accuracy trade-offs, achieving about two thirds reduction in the disjoint regime and up to 93% in the sequential regime. The study also provides guidance for initial label budgets and stopping to avoid over-annotation.

cs.CV

新论文 · v1arXiv:2611.05643

Data-Efficient Scaling-Law Discovery for Recommendation Systems via Coupled Hyperparameter Scaling

John Martabano Landy, Louis C. Tiao, Yao Xuan, Luc Kien Hang, Rupinder P. Khandpur, Arvind M. Vepa, Srinidhi Raghavendran, Anirudh Agrawal 等 13 位作者

原文摘要

Large-scale ranking and recommendation models of Web platforms benefit from increased compute much as large language models do, and their scaling behavior is broadly power-law in form. Yet ranking models have heterogeneous architectures which makes their scaling law less straightforward than that of LLMs. We address how to discover the scaling law of an arbitrary ranking model efficiently. We introduce a scaling layer, which groups primitive architecture parameters into semantically coherent groups and defines how they co-vary, inducing a mapping from a low-dimensional space of hyper-hyperparameters into the full architecture space. On top of it, Axia fits scaling-informed surrogates, selects configurations by a posterior-based acquisition criterion, and returns a Pareto frontier from which per-model operating points are validated -- replacing exhaustive sweeps with a small number of informative runs. A fleet-level evaluation protocol, computed on a fixed representative model set under matched trial budgets, makes refinements to either component measurable. Our contribution is an automated system that learns model-specific complexity-quality relationships and gives uncertainty-aware guidance for allocating compute across a heterogeneous model ecosystem. Across 34 model iterations in two development cycles on Meta's ads ranking and retrieval system, the workflow yielded a mean 0.66% offline normalized-entropy improvement and 0.36% cumulative online lift.

cs.LG · cs.IR

新论文 · v1arXiv:2611.05642

Runway Characters: Serving a 57B Video Diffusion Transformer for Real-Time Conversation

Rohan Agarwal, Robin Andeer, Alex Armbruster, Bennett Arthur, Michail Christos Doukas, Piero Esposito, Qiming Fang, Aron Filkey 等 33 位作者

原文摘要

Conversational video characters must generate video as fast as it plays, for one user at a time: at 24 fps, a sustained 166.7 ms per four-frame chunk at batch size one, with only a few chunks of buffering. We describe the system behind Runway Characters, which serves a $\approx$57B-parameter autoregressive video diffusion transformer (four denoising passes per chunk) at 704$\times$1088 and 24 fps on four H100 GPUs with a voice agent in the loop. Each chunk takes 240 attention calls, each reading a 5,788-slot KV cache in which only 757 tokens are new, and 29% of the original step was whole-cache work repeated in every call. We move that work to write time (a ring cache, RoPE and FP8 quantization applied once per write, and a delta rotation when positions reset), fuse the tensor-parallel all-reduce into the FP8 GEMM with in-switch reduction, and give the decoder that turns latents into video frames its own GPU. Without the fused kernel, our optimizations cut the diffusion step from 240.9 to 159.3 ms (1.51$\times$, 24.5 fps sustained) with no detected degradation in lip-sync scores; the fused kernel, rolled back once in production and since re-enabled, reaches 147.4 ms (1.63$\times$, 43% of FP8 peak). In seven weeks of production the worker averaged above 23.5 fps in 99.5% of sessions that streamed for at least a second, and our pipeline takes 0.49 s of a 2.1 s median conversational turn. On the same GPUs, the two open-source real-time video systems we benchmarked, at four denoising passes, miss real time or add over a second of latency (one by estimate), at a third to half of our resolution.

cs.DC

新论文 · v1arXiv:2611.05638

VIPBench: A Human-Aligned Benchmark for Voice Identity Perception in the Age of Voice Cloning

Xudong Tang, Matthew Groh

原文摘要

Speaker-recognition benchmarks test how accurately a model recovers the speaker label of a recording, treating voice identity as a property of the person who produced it. However, these benchmarks do not evaluate how humans perceive voice identity. Whether a listener hears two voices as the same person has consequences for intellectual property rights, cybersecurity, and everyday life. We introduce the Voice Identity Perception benchmark (VIPBench), which contains 124,876 same-or-different judgments from 1,290 listeners on 9,800 recording pairs from 100 public figures. The pairs include real recordings, voice clones generated by a text-to-speech system, and morphs between two speakers' voices. We also define four tasks that evaluate the alignment between speaker-representation models and human identity perception. The first two tasks measure how well a model's similarity score predicts the proportion of listeners who respond "same" and the majority response. The other two measure whether a model and listeners find the same speaker pairs similar, and whether a model's relationship to listener judgments holds equally for real and synthetic recordings. We evaluate eleven publicly available speech models. Listener judgments diverge from speaker labels most often for voice clones: in 41% of responses, listeners judged a clone and a real recording of the same speaker to be different people. No model reaches the noise ceiling; the best model explains 61% of the explainable variance. Models trained with speaker labels align with listeners better than self-supervised models do, yet a model with a 12% error rate on speaker labels aligns with listeners as well as models with error rates below 2%. VIPBench enables the evaluation of speaker models against human perception on real, cloned, and morphed speech, and our results motivate training speaker models directly on listener judgments.

cs.SD · cs.AI · cs.CY · cs.MM

新论文 · v1arXiv:2611.05636

Route to Remember: Adaptive Memory Selection for LLM Agents

Zeyu Fang, Jun Yin, Yongsheng Mei, Xu Han, Chaitali Joshi, Zhongkai Sun, Jie Hao, Bin Guo 等 11 位作者

原文摘要

The memory of production agents is increasingly becoming a bottleneck and is built almost exclusively from text: key points are extracted from out-of-limit context and retrieved into context at query time. Therefore, every new query incurs an additional cost that grows with the accumulated history. Weight memory is a complementary alternative that internalizes knowledge into model parameters and answers with no context at all, and has recently proven effective in self-evolving agents for internalizing skills and behaviors. However, its application in episodic and semantic memory, such as user-specific facts, remains comparatively unexplored, and a gap remains between earlier attempts at weight memory and text-based systems regarding recall performance. We study how to make weight memory competitive as a long-term factual store by applying on-policy self-distillation (OPSD). It trains a context-free student from a teacher, which is the same model conditioned on the user's memory, together with a verify-then-regenerate router that lets weight and text memory each cover the queries they handle best. On the HaluMem benchmark, OPSD matches or surpasses strong text-memory baselines, including full-context prompting and retrieval systems, while reading fewer tokens per query. We further conduct an extensive study that characterizes the behavior of weight memory and analyzes how different training recipes affect its performance. As agent harnesses move toward persistent, multi-session deployments, these results position weight memory as a practical, low-cost component of agent memory and provide insights into feasible training and evaluation protocols for combining it with retrieval.

cs.AI

新论文 · v1arXiv:2611.05633

Spatio-Temporal Multi-Order Interaction for Video Recognition

Kevin D. Nguetche, Lilian Hollard, Eric Granger, Marco Pedersoli

原文摘要

Many temporal approaches for video recognition rely on explicit cross-channel aggregation projections, which have quadratic complexity in the number of channels, introducing significant computational overhead. In addition, the spatio-temporal representation used for video recognition is biased either toward local order interactions (for CNNs) or toward global order interactions (for transformers). Starting from the multi-order spatial representation of MogaNet, our method introduces two complementary contributions to tackle these problems. First, for the temporal modelling, we introduce parallel multi-order processing with depthwise-only convolutions and implicit gating-based aggregation, which is linear in the number of channels, inducing a considerable computational reduction. Second, we propose a dual interaction between spatial and temporal dimensions, which allows a better spatio-temporal representation without increasing the computational cost. By combining these two contributions, our proposed VideoMogaNet achieves performance on par with or better than state-of-the-art action recognition approaches across multiple video benchmarks (UCF101, HMDB51, Kinetics-400, Diving48), while considerably reducing the cost of the temporal branch.

cs.CV · cs.AI · cs.LG

新论文 · v1arXiv:2611.05632

Assurance-Conditioned Continuous Authorization for Autonomous AI Agents

Mehdi Shajari

原文摘要

Autonomous software agents can act through tools, delegate work, and change their models or execution environments while earlier authorizations remain in flight. We present Assurance-Conditioned Continuous Authorization (ACCA), an approach designed to be harness-independent, for maintaining operational authority according to currently justified assurance. It distinguishes evidence validity from contextual applicability, derives assurance claims from eligible evidence, and resolves a multidimensional effective-authority envelope within a principal-declared ceiling and applicable policy. A typed dependency graph supports selective re-evaluation of authorization-relevant changes. An authority epoch changes when effective authority changes; a distinct optional authorization-basis version supports revalidation of action-specific authorization conditions. Protected effect-time enforcement can reject stale actions before a consequential resource change, subject to the available commit mechanism. A compositional Domain Governance Profile expresses domain-specific semantics without granting authority. Controlled scenario tests implemented as a regression suite using a trading profile exercise default-deny rules, evidence-conditioned contraction and recovery, policy divergence, selective non-response, and stale-action rejection at a local gateway before the simulated-broker boundary. The study establishes implementation-level evidence in one domain, not a cross-domain guarantee of harmful-behavior prevention.

cs.AI · cs.CR

版本更新 · v3arXiv:2610.34474

Unconditional Lower Bounds for the Fredman--Khachiyan Algorithms for Monotone Boolean Duality Testing

Khaled Elbassioni

原文摘要

We prove unconditional lower bounds on the number of recursive calls made by the two algorithms of Fredman and Khachiyan (1996) for monotone Boolean duality testing, as a function of the explicit input size $N$. For Algorithm A we show a lower bound of $N^{Ω(\log N)}$ on the dual pairs $(\HH_k,\LL_k)$ obtained from the read-once family of Gurvich and Khachiyan. The proof lower-bounds the number of leaves of every binary decision tree computing the function by the modulus of its multilinear polynomial evaluated at a complex point of the unit circle. It therefore applies to every choice of branching variables and, more generally, to the class of two-child variable-restriction procedures whose terminal calls have polynomially bounded decision-tree complexity. On this family the number of calls is exactly $N^{Θ(\log N)}$. For Algorithm B, a symmetric specialization of the polynomial padding construction of Kobayashi, Kurita, and Wasa, with full polynomial blocks, yields at least $q^{(t-1)k-t(t-1)/2}$ calls, where $k=4t^2$ and $q=Θ(t^2)$; as a function of $N$ this is $N^{Ω(\sqrt{\log N/\log\log N})}$ along an infinite family. The same padded family forces Berge multiplication, for every edge ordering, to generate an intermediate family of size $N^{Ω(\sqrt{\log N/\log\log N})}$. In an appendix we show that applying the padding construction directly to Algorithm A gives $Ω(2^n)$ calls on a dual pair obtained from an unsatisfiable $n$-variable formula, which is only $N^{Ω(\sqrt{\log N/\log\log N})}$ in terms of the input size. No complexity-theoretic assumption is used. The proofs allow every branching-variable choice permitted by the respective algorithm. They concern the original recursive procedures, counting every invocation separately, without sharing calls or adding positive stopping tests.

cs.CC · cs.DS

新论文 · v1arXiv:2611.05626

Exact signal recovery from generative priors with sigmoid output activation

Matthew S. Scott, Yaniv Plan, Özgür Yılmaz

原文摘要

We show exact signal recovery in generative compressed sensing for feedforward neural networks with piecewise-linear activations and a final sigmoid activation, with no assumption of expansivity. Consider a ReLU network of depth $d$ with a sigmoid final activation, whose input layer, of dimension $k$, is the narrowest, and let $K$ be the geometric mean of the widths of its layers. We show that, with high probability, all signals of the range whose entries lie in $[δ, 1 - δ]$ are uniformly recovered from $m \gtrsim k(d \log(K/k) + \log(1+\log(1/δ)))$ measurements.

cs.IT · eess.SP · stat.ML

版本更新 · v2arXiv:2610.21257

Fractional Power-of-Two Quantization for Efficient and Effective Multiplier-Free LLM Inference

Sunghyun Wee, Geunjae Choi, Hyeonjin Kim, Suyoung Kim, Nojun Kwak

原文摘要

Large Language Models (LLMs) demand efficient inference, where the multiply-accumulate (MAC) operations in linear projections dominate compute and energy cost. Post-training quantization (PTQ) reduces this cost by mapping weights and activations to low-bit integers. Power-of-Two (PoT) weight quantization promises efficient multiplier-free LLM inference via shift-add logic, but suffers significant accuracy degradation at low bit-widths due to its coarse base-2 quantization grid. We introduce Fractional PoT (FPoT), a base-$\sqrt{2}$ (half-octave) fractional PoT grid that achieves practical 4-bit weight quantization while preserving a fully integer shift-add datapath. The method combines (i) the base-$\sqrt{2}$ weight grid with uniform integer activations, (ii) a calibration-time grid-alignment refinement absorbed into the static per-channel scale, and (iii) a lightweight 1-adder $\sqrt{2}$ approximation whose error is absorbed during weight calibration via approximate-grid quantization, yielding a processing element (PE) with significantly fewer gates than a 4-bit integer multiplier. On Llama-3-8B with 4-bit weight and activation quantization, FPoT improves zero-shot commonsense reasoning performance by 8.72% relative to the PoT baseline, while maintaining performance close to the uniform integer baseline, with only a negligible 0.4%p degradation. These results hold across various configurations spanning seven models and three bit-widths. Furthermore, FPoT can be integrated with state-of-the-art LLM PTQ methods, demonstrating framework-agnostic applicability.

cs.LG · cs.AI

新论文 · v1arXiv:2611.06954

Certified folding-free deformable image registration: A whole-cell Jacobian certificate and a sequential variational solver

Baihan Zhao, Zicong Zhou, Guojun Liao

原文摘要

Registration maps propagate labels, measure local volume change, and map results back through their inverses; requiring invertibility. Voxelwise checks can miss folds between grid points. We study the canonical continuous extension of a nodal displacement field by trilinear interpolation and give a test that proves its Jacobian determinant positive in every grid cell or rejects the map. The test is rigorous under IEEE 754 binary64 arithmetic (correct rounding, no contraction). With a fixed boundary, certification implies a bi-Lipschitz homeomorphism of the image domain. We introduce SeqVP, built around this certificate. A proximal Jacobian-determinant-curl formulation yields inner problems whose penalties on changes in the map, Jacobian determinant, and curl vanish to first order at the current iterate. The method decreases a fixed outer energy up to a floating-point resolution guard and certifies every committed iterate. After certified initialization, stopping at any time returns a folding-free map. A Poisson-preconditioned gradient method with Jacobian-aware step prediction and affine-scaling damping, initialized by certified handoff from an uncertified binary32 pre-optimizer, handles a 1 mm brain MRI with about 2e7 unknowns in 90 s on one GPU. On 49 held-out OASIS pairs, SeqVP achieves mean Dice 0.821 over 35 structures and 0.889 over 4 tissue classes, with certified zero folding. Gains are 0.022 and 0.025 over ANTs SyN, and 0.022 and 0.023 over uniGradICON with instance optimization at equal time (paired, Holm-adjusted p < 0.001), but maps are rougher. SeqVP is level with ANTs on LPBA40, behind it on IBSR18, and ahead of all label-free baselines on 20 large-deformation pairs. On fields from nine methods, the certificate finds non-positive-Jacobian cells in every ANTs SyN map (median 10, missed by voxelwise checks) and in maps from NiftyReg, ConvexAdam, uniGradICON, and TransMorph.

cs.GR · math.AP

版本更新 · v3arXiv:2610.03792

What Do Verifiable Rewards Teach Video-Language Models About Time? A Controlled Multi-Model Study

Avyay Sadhu, Patrick Cooper

原文摘要

Reinforcement learning from verifiable rewards (RLVR) has produced large reasoning gains in language models, and verifiable video benchmarks make the recipe directly applicable to causal-temporal video question answering. We present a controlled study of what RLVR actually teaches video-language models about temporal structure. We fine-tune four open models with group relative policy optimization (GRPO) under three data recipes using annotated synthetic questions, self-supervised real-video pretext tasks, and a one-to-one mixture, plus a targeted real-video augmentation arm. We evaluate the model-recipe grid on 105 CLEVRER questions with one correct option and on two real-video transfer sets. The 8B ordered gain is 4.8 points (95% video-bootstrap CI [-5.6, 15.1]), while blind accuracy increases 10.5 points ([0.9, 20.6]). The 4B model gains an accuracy advantage for ordered over shuffled frames. On the real-video sets, the 8B synthetic-only checkpoint loses 26.7 and 25.2 points, with smaller regressions under mixed and augmented recipes. In a separate scene-disjoint, single-gold Qwen3-VL-8B experiment, supervised fine-tuning (SFT) and GRPO each complete 1,200 updates at three fixed seeds. GRPO minus SFT is -3.89 points in ordered accuracy (nominal 97.5% video-bootstrap CI [-7.36, -0.45]) and -2.78 points in ordered-minus-shuffled accuracy ([-6.60, 0.87]). Transfer differences are sensitive to parseability. Intervals quantify test-video uncertainty conditional on the fitted runs. The results show why benchmark accuracy, transfer, and presented-order sensitivity need to be evaluated separately.

cs.CV

版本更新 · v5arXiv:2512.20773

DIAL: Direct Iterative Adversarial Learning for Realistic Multi-Turn Dialogue Simulation

Ziyi Zhu, Olivier Tieleman, Caitlin A. Stamatis, Luka Smyth, Thomas D. Hull, Daniel R. Cahn, Jinghong Chen, Matteo Malgaroli

原文摘要

Realistic user simulation is crucial for training and evaluating multi-turn dialogue systems, yet creating simulators that accurately replicate human behavior remains a significant challenge. An effective simulator must expose the failure modes of the systems under evaluation. This work introduces Direct Iterative Adversarial Learning (DIAL), an adversarial framework that iteratively enhances user simulator realism through a competitive dynamic between a generator (user simulator) and a discriminator. When applied to mental health support, a domain characterized by diverse failure types and a critical dependence on realistic user behavior for failure detection, DIAL restores lexical diversity diminished by supervised fine-tuning and drastically reduces discriminator accuracy. The resulting simulator exhibits a strong correlation between simulated and real failure occurrence rates while maintaining low distributional divergence of failure modes. These findings indicate that DIAL is a promising method for developing realistic user simulators in multi-turn dialogue, facilitating reliable and cost-effective system evaluation prior to deployment.

cs.CL

版本更新 · v2arXiv:2610.36418

When the Application Layer Is Disposable: Putting Integrity Constraints Back in the Database

Hasara Kalumin, Amol Deshpande

原文摘要

Integrity constraints have been central to the relational model since its inception. However, beyond keys, single-row CHECKs, and referential integrity, most constraints are enforced by application layers today. SQL ASSERTIONs, standardized in SQL-92, remain poorly supported by major RDBMSs. This has become increasingly unacceptable due to two developments. First, LLM-driven applications and agents increasingly issue queries and updates directly against databases, bypassing application layers where invariants reside. Such code may be generated on demand and discarded afterwards, making the database the only durable component that can encode and enforce these invariants. Second, natural constraints in higher-level conceptual models, such as E/R and property graphs, become fragmented across relations under mappings chosen for performance. The resulting multi-relation constraints lack direct database support, and only some can be efficiently enforced using existing mechanisms such as triggers. These developments motivate an overhaul of how constraints are defined, mined, managed, and enforced in data management systems. As a first concrete step, we introduce constraint indexes, which represent constraints spanning multiple relations as transactional access paths, and implement a proof of concept as a PostgreSQL extension. Constraint indexes enforce constraints arising from distributed inheritance hierarchies, folded relationships, and folded weak entities, as well as cardinality bounds and functional dependencies, at low overhead relative to no enforcement. Across these workloads, they outperform the better of the correctness-preserving baselines by up to 2.41 times. We also show that LLM-driven writers frequently violate unenforced constraints and behave erratically when provided with a list of constraints to enforce. We close by discussing a few research challenges raised by this agenda.

cs.DB

版本更新 · v2arXiv:2610.38970

Communication-Efficient Clustered Federated Learning in Non-IID Wireless Networks

Martin Isaksson, Rickard Cöster, Šarūnas Girdzijauskas, Seif Haridi

原文摘要

Current and emerging mobile networks face increasing privacy, scalability, and performance challenges as distributed learning becomes essential for advanced 6G services. These challenges are amplified by the presence of non-IID data, naturally arising in heterogeneous wireless environments, that degrade the performance of standard Federated Learning (FL) approaches. To address non-IID data across clients, we propose a Clustered Federated Learning (CFL) framework that assigns clients to specialized models during training. Data-domain clustering initializes model-based clustering, enabling identification and exploitation of client similarities without sharing raw data while reducing communication cost. Motivated by mmWave beam selection, we evaluate our methods on a wireless simulation dataset (DeepMIMO) and complement it with two non-IID benchmarks (FEMNIST, Rotated CIFAR-10) to isolate different non-IID characteristics. Our best configurations improve accuracy over IFCA by 4.8 pp on DeepMIMO and 10.6 pp on FEMNIST while reducing downlink data volume by 83.1 % on FEMNIST compared to IFCA. We demonstrate that different clustering strategies suit different non-IID characteristics. These results show that our CFL methods enable resource-efficient, and high-performance distributed learning in future 6G networks.

cs.LG

版本更新 · v3arXiv:2607.17082

OTAP: Structure-Aware Optimal Transport for Evaluating Planning and Execution in Agent Trajectories

Babak Barazandeh, Subhabrata Majumdar, George Michailidis

原文摘要

Large language model agents solve tasks by generating trajectories that interleave planning, tool calls, and intermediate results. Current evaluation metrics reduce such a trajectory to a binary success flag, compare it against a reference by exact matching, or delegate judgment to another language model. A success flag cannot distinguish sound solutions from lucky ones, nor explain why runs fail. Exact matching penalizes valid plans reordered or decomposed differently. We reframe trajectory evaluation as a distance between the agent's execution graph and a set of valid solution graphs, and instantiate it via an unbalanced fused Gromov-Wasserstein transport problem over attributed dependency graphs. The resulting score, termed OTAP (Optimal Transport for Agentic Planning), is a normalized discrepancy score. Its idealized, globally minimized entropy-free objective is invariant to dependency-preserving relabelings of a fixed graph and has a redundant-insertion sensitivity analysis under stated assumptions. Its unbalanced marginals handle missing or hallucinated steps without forcing a match; granularity invariance remains an open problem that soft coupling mitigates only in part. On controlled perturbations and three public benchmarks, OTAP separates valid from invalid trajectories in a regime where semantics-only metrics score below chance. Its performance is encouraging across these settings, while controlled edge-noise experiments reveal sensitivity to dependency extraction. Where a formal verifier exists, strict surface metrics predict validity better than OTAP does, which places OTAP in open-ended domains where no verifier is available. A blinded study of 236 trajectories finds the strongest agreement with OTAP among the six compared metrics. Structure-aware baselines achieve higher clean-graph AUROC, while OTAP has the smallest absolute AUROC decline under the tested edge noise.

cs.AI · cs.CL · cs.LG

版本更新 · v2arXiv:2610.12438

Parallel Edge Ranking of Trees

Jeff Giliberti, MohammadTaghi Hajiaghayi, Changki Yun

原文摘要

In this work, we prove that computing the edge ranking of a tree in parallel is P-Complete, and complement this hardness with new algorithmic results for both PRAM and the MPC model. An optimal tree edge ranking assigns positive integer ranks to the edges such that any two edges with the same rank are separated by an edge of higher rank, while minimizing the highest rank. Although an optimal edge ranking, which minimizes the maximum rank, can be computed in polynomial time sequentially, its parallel complexity has remained open for almost 35 years [de la Torre, Greenlaw, Schäffer, SODA'93] and was listed as an open problem in Limits to Parallel Computation [Greenlaw, Hoover, Ruzzo, 1995]. Specifically, we show that deciding whether a tree has edge ranking at most $K$ is P-complete, already for trees of diameter at most six. Our reduction encodes monotone circuit evaluation into a greedy allocation procedure underlying known sequential algorithms. Using a rooted product of trees, we further prove that computing an edge ranking within constant additive error remains P-hard. On the algorithmic side, we break the long-standing 2-approximation barrier by designing a deterministic NC algorithm that computes an $(1+o(1))$-approximate edge ranking. Second, we show that P-completeness can be bypassed in Massively Parallel Computation (MPC) with strongly sublinear local memory: we give a deterministic algorithm that computes an optimal edge ranking of an $n$-vertex, diameter-$D$ tree in $O(\log D + \frac{n^{3/4}D^{1/4}}{S})$ rounds with $S = Θ(n^{3/4+δ})$ local memory, for $δ\in (0, 1/4)$, requiring only $O(1)$ rounds on the hard diameter-six instances. This result reinforces the separation between $\mathsf{NC}$ and what can be computed efficiently in MPC.

cs.DS

版本更新 · v2arXiv:2611.02197

Conditional Diffusion-Based Generation of T2-Weighted Prostate MRI for Clinically Significant Prostate Cancer Classification

Xavier Rafael-Palou, Alejandro Vergara-Richart, Ignacio Iborra Roncales, Carmen Prieto-de-la-Lastra, Andreu Antolin-Redondo, Juan Morote, Ana Jimenez-Pastor

原文摘要

Scarce and unrepresentative training data limit the performance of prostate MRI prediction models. Synthetic T2-weighted (T2W) MRI may augment training data containing clinically significant prostate cancer (csPCa) and transition zone (TZ) lesions. In this retrospective, single-center, ethics-committee-approved study, we developed a conditional generative model for T2W prostate MRI extending MAISI-v2 with csPCa class, zonal, and lesion-mask-guided conditioning, incorporating a relative advantage weighted loss fine-tuned on 1,303 patients (1,654 lesions). Fidelity was assessed by incremental ablation, and downstream utility was evaluated with T2W-based csPCa classifiers across five simulated training-data scenarios, each testing 18 synthetic-data configurations. The proposed model reduced Fréchet inception distance (FID) from 13.28 (pretrained MAISI-v2) to $2.04 \pm 0.06$ internally (PI-CAI: $3.83 \pm 0.51$). Synthetic augmentation significantly increased AUC in all five scenarios (+0.027 to +0.088; adjusted $p = 0.016$--$0.043$), though cross-institutional augmentation of PI-CAI yielded a non-significant gain (+0.013; $p = 0.397$). Overall, our model improved T2W MRI fidelity, and synthetic images improved csPCa classification under simulated data constraints, although benefit did not transfer significantly across institutions.

cs.CV

新论文 · v1arXiv:2611.05616

LACS: Distribution-Sensitive Label-Agnostic Confidence Selection for Dynamic Data Pruning

Heejin Choi

原文摘要

Training on large datasets motivates selecting which examples receive expensive training computation. Fixed quotas determine the amount of pruning in advance, while absolute confidence cutoffs depend on the score scale. We study a population-relative alternative that adapts the threshold and retained count together. We introduce LACS (Label-Agnostic Confidence Selector), a training-time rule based on maximum predictive confidence, requiring neither labels at selection time nor per-example gradients. LACS removes examples at or above a log-mean-exp reference plus a margin. We characterize its sensitivity to score gaps and mass, and derive an exact no-pruning condition. For $0<ρ<1$, the removed fraction is at most $ρ$ and at least one example remains. The unsigned score permits both confidently correct and confidently wrong examples to be removed. Seven evaluation settings include neural training, language modeling, and boosting. Neural execution studies reduce backward-active rows by 10-35%; on CIFAR-10, 29% fewer backward rows accompany accuracy means of 89.77% versus 89.82% for full CE. At a matched backward budget and number of optimizer updates, LACS is 1.0 pp above small-batch training and 1.2 pp above random selection over five seeds. Across 14 tabular datasets, quadratic boosting reduces mean test error from 23.36% to 22.96%. Its full training replays use about 30% fewer fitting rows; these counters span a different horizon from validation-selected accuracy. In one RBF-SVM case study, elapsed time falls by 37% with slightly lower error. These findings separate selective-work reduction from realized acceleration: the current exact-current-score neural implementation uses an additional scoring forward, so its backward sparsity does not yet translate into wall-clock acceleration. This overhead is an execution choice rather than a requirement of the selection rule.

cs.LG