跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+758新增论文
+578其中 AI 相关
+94已有论文修订
+95新增 AI 导读

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

统计口径与数据新鲜度

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

最近完成检查:2026-11-17 04:58最近发现新增版本:2026-11-17 04:58库内论文最新更新时间:2026-11-14 02:59

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

24,106 已收录论文20,158 AI 相关7,049 有修订112 HF 社区发现

浏览论文库

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

找到 24,106 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-17 04:57(北京时间)
版本更新 · v2arXiv:2609.35453

Hermite Brings a Laptop: Analyzing Frieze-Jerrum Rounding Yields Improved Approximations for Clustering Problems

David García-Soriano, Atsushi Miyauchi

原文摘要

The Frieze-Jerrum rounding is a standard tool for rounding SDP relaxations of graph partitioning and clustering problems, assigning nodes to at most $k$ clusters using $k$ independent Gaussian vectors. Its analysis hinges on the collision probability $P_k(ρ)$ that two nodes whose SDP vectors have inner product $ρ$ are assigned to the same cluster. No tractable closed form for $P_k$ is known for $k\geq 4$, making it difficult to certify approximation guarantees and hindering the systematic search for better algorithms. We develop a Hermite-coefficient certification framework to derive accurate and tractable bounds on $P_k$. Using the Hermite expansion of Gaussian noise stability, we express $P_k$ as a power series with nonnegative coefficients, reduce these coefficients to one-dimensional Gaussian integrals, and certify finitely many of them, yielding rigorous bounds on $P_k$ over the entire correlation range. Our framework yields strengthened polynomial-time approximations for several clustering problems. For MaxAgree Correlation Clustering, we derive a $0.7818$-approximation, the first improvement in two decades over the $0.7666$ ratio of Swamy (2004). We also improve the best known ratios for the variant with at most $K$ clusters, MaxAgree$[K]$ (e.g., from $0.77$ to $0.8151$ for $K=3$). For Max $K$-Cut we resolve, via a structural property of the Hermite expansion, a conjecture of de Klerk et al. (2004) characterizing the Frieze--Jerrum approximation ratio for every $K\ge3$; we show that this ratio is tight, and determine it to within $10^{-6}$ accuracy for $K\le16$. Finally, we reduce the additive approximation error for modularity maximization from $0.42084$ (Kawase et al., 2021) to $0.3790$. On the hardness side, we show that approximating Maxagree within $0.802+ε$ is Unique Games-hard via a construction in Gaussian space analyzed by Borell's inequality.

cs.DS

新论文 · v1arXiv:2611.04913

EP-LVMQA: Evidence-Preserving Coarse-to-Fine Localization for Low-Quality Long Video Moment Question Answering

Guoning Chen, Zhexun Hu, Yifan Wei, Yixuan Weng, Bin Li, Yufei Zhao

原文摘要

Long instructional videos are increasingly used in medical education, industrial training, and procedural knowledge transfer, yet their evidence is often incomplete or unreliable: subtitles may be missing, ASR noisy, OCR sparse, and decisive actions briefly shown without narration. Existing VideoQA systems typically return labels or free-form text, making answer support difficult to inspect. We study Long Video Moment Question Answering (LVMQA), where a system returns timestamped answer-supporting evidence. We propose EP-LVMQA, an evidence-preserving coarse-to-fine framework comprising an Uncertainty-Aware Multimodal Evidence Timeline, a Coarse Evidence Planner, and an Evidence-Conditioned Fine Localizer. An evidence card transfers planner scores, matched cues, source-confidence proxies, modality-specific evidence, neighboring context, and a temporal prior between the latter two modules. On MedVidQA, EP-LVMQA achieves 26.1 R1@0.5 and 31.8 mIoU, improving the strongest non-ours results by 6.3 and 5.1 points. It raises Suff.@2 and Ver.@2 to 25.4 and 22.6, gains of 9.5 and 8.8 points. Under matched low-quality perturbations, average relative degradation is reduced from the strongest non-ours value of 14.6% to 11.1%. On Ego4D-NLQ and QVHighlights, EP-LVMQA remains broadly comparable to established task-specific localization methods.

cs.CV

新论文 · v1arXiv:2611.04912

MiCaDe: Online LiDAR-Camera Miscalibration Change Detection for Autonomous Driving

Carlo Sgaravatti, Riccardo Pieroni, Matteo Corno, Sergio M. Savaresi, Luca Magri, Giacomo Boracchi

原文摘要

Reliable multi-sensor perception in autonomous vehicles requires accurate calibration between cameras and LiDAR. However, calibration drift is often unavoidable in long-term deployments: vibrations, thermal effects, and minor mechanical shocks may alter the relative pose between sensors, leading to systematic errors in downstream fusion tasks. We propose MiCaDe (Miscalibration Change Detection), an online solution detecting when the extrinsic LiDAR-camera calibration parameters are no longer accurate by means of sequential change detection. MiCaDe requires no calibration targets, or modification of the perception stack, providing low false-alarm rates with negligible computational overhead. Our key insight is that 3D and 2D bounding boxes produced by standard object detectors should remain geometrically consistent under correct calibration. By matching cross-modal detections, we derive geometric consistency metrics that serve as sensitive indicators of extrinsic drift. These metrics are aggregated into fixed-size batches and scored against a reference distribution, producing a likelihood stream that is monitored by a Change Point Model (CPM). Crucially, the CPM accumulates statistical evidence over time, enabling detection of subtle drifts that would otherwise go unnoticed. Experiments on multiple long-sequence datasets and on a real-world dataset with physically induced miscalibration confirm reliable detection under diverse conditions. Code available at: https://github.com/CarloSgaravatti/MiCaDe.

cs.CV · cs.LG

版本更新 · v3arXiv:2609.09091

Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space Stability

Tom Gur, Longcheng Li

原文摘要

We show that one-way one-round quantum-LOCAL algorithms cannot $4$-color directed cycles with high probability. This is the first lower bound in the high-probability quantum LOCAL setting that goes beyond the non-signaling and bounded-dependence models, exploiting the structure of distributed quantum algorithms. Our proof establishes a bidirectional connection between distributed quantum computing and extremal combinatorics. We obtain our lower bound by proving a Mantel-type stability theorem for weighted matrix spaces.

quant-ph · cs.DC

版本更新 · v3arXiv:2604.15001

COEVO: Co-Evolutionary Framework for Joint Functional Correctness and PPA Optimization in LLM-Based RTL Code Generation

Heng Ping, Peiyu Zhang, Shixuan Li, Wei Yang, Anzhe Cheng, Shukai Duan, Xiaole Zhang, Paul Bogdan

原文摘要

LLM-based RTL code generation methods increasingly target both functional correctness and PPA quality, yet existing approaches decouple the two objectives, optimizing PPA only after full correctness is achieved. Sequential multi-agent pipelines, evolutionary search with binary correctness gates, and hierarchical reward dependencies all discard partially correct but architecturally promising candidates. Moreover, existing methods reduce the multi-objective PPA space to a single scalar fitness that obscures the trade-offs among area, delay, and power. To address these limitations, we propose COEVO, a co-evolutionary framework that unifies correctness and PPA optimization within a single evolutionary loop. COEVO formulates correctness as a continuous co-optimization dimension alongside area, delay, and power, enabled by an enhanced testbench with fine-grained scoring. The framework allows PPA-promising but partially correct candidates to guide the search toward jointly optimal solutions, and further employs four-dimensional Pareto-based non-dominated sorting to preserve the PPA trade-off structure without manual weight tuning. On VerilogEval 2.0 and RTLLM 2.0, COEVO surpasses all agentic baselines across four LLM backbones. With GPT-5.4-mini, COEVO achieves 97.5\% and 94.5\% Pass@1 and attains the best PPA on 43 out of 49 synthesizable RTLLM 2.0 designs.

cs.AI

新论文 · v1arXiv:2611.04907

Cool Graphs: Active Property Search Towards Quantum Nano-Refrigerators

Sofia Blyufer, Amir Kleiner, Uri Peskin

原文摘要

Nanodevices that absorb energy from their thermal environment can act as quantum refrigerators. Finding suitable configurations, however, is a needle-in-a-haystack problem: the many-body state space scales exponentially with the size of the device, where each candidate configuration requires an expensive quantum-chemical computation. We introduce a search framework that couples a Graph Variational Autoencoder (GVAE) with an uncertainty-driven Active Learning (AL) loop to efficiently identify energy-absorbing configurations in electronic junctions with a 2D "working material" to be optimized. The GVAE maps physical parameters - site energies, coupling matrices, temperature - into a smooth latent space that distinguishes cooling from dissipative parameter regimes, achieving a classification discriminability of $0.920 \pm 0.004$ on held-out configurations and $0.895 \pm 0.010$ on unseen extrapolation topologies. An AL pipeline based on Monte Carlo dropout then targets the decision boundary, iteratively selecting the candidates where the model is least certain for simulation. Over 32 AL cycles, the uncertainty-driven strategy discovers energy absorbing systems at rates consistently exceeding the random baseline across all tested topologies (where only 1.9-8.4% of configurations exhibit the desired property), providing a data-efficient pathway for navigating a combinatorically large design space. The learned latent space organizes configurations along physically interpretable axes, that correlate with underlying microscopic model parameters. This hints at the existence of "cooling coordinates" - low-dimensional, physically interpretable quantities separating cooling from non-cooling regimes. Our framework, thus, paves a new way towards effective cooling of nanoscale electronic information processing devices, to reduce the environmental footprint of high performance computing.

cs.LG

新论文 · v1arXiv:2611.04903

Heads That Write, Not Just Point: Image Retrieval Heads in Vision-Language Models

Junsung Park, Sangwon Yu, Donghun Kang, Yeongtak Oh, Jaewon Jeong, Gyeongtae Yoo, Han Cheol Moon, Jungbeom Lee 等 9 位作者

原文摘要

Large vision-language models (LVLMs) can process interleaved text and multiple images in a single context, but how they internally identify the image relevant to a question remains poorly understood. We study this grounding step as in-context image retrieval and introduce ICIR-MCQ, a controlled probe for head-level analysis of image retrieval. Using each head's attention mass over image-token spans, we first identify sparse pointer heads that reliably point to the target image. These heads transfer beyond the probe: a single pointer head is competitive with external vision-language retrievers on a naturalistic multi-image retrieval benchmark, showing that LVLMs contain a strong internal image retrieval signal. Attention alone, however, shows where a head reads from, not what its output passes on to later layers, so we introduce a complementary output-side analysis. For each head, we train a lightweight image retriever on its value-weighted output and use it to identify writer heads, whose outputs contain enough information to identify the target image. Surprisingly, the pointer and writer criteria select substantially different head sets, with only 35 to 47 heads overlapping among the top-100 heads under each criterion. Targeted set-partition ablations show that the heads most important for standard multi-image inference are concentrated in this pointer-writer intersection, while heads selected by only one criterion show less consistent separation from random-head controls. The most consistent causal effects arise from heads selected by both the attention-based pointer and output-side writer criteria. Code and data: https://github.com/parkquasar/Image-Retrieval-Heads.

cs.CV · cs.CL

新论文 · v1arXiv:2611.04902

Attending to Memory Writes Reduces Seed Variability in Recurrent Length Generalization

Sungwoo Goo, Hwi-yeol Yun, Sangkeun Jung

原文摘要

Recurrent memory requires learning useful updates, but attention added to assist learning can also compromise length generalization. We study bounded delta attention: causal attention over uncorrected update proposals whose bounded correction enters the recurrent update. Its implementation in TraceRelay combines additive phase recurrence with attention computed before a parallel scan. On prefix-supervised modulo-5, trained at lengths 1--40, three findings characterize its behavior at length 80. First, upper delta attention attains $70.81\pm8.26$% accuracy across seven seeds, versus $69.21\pm22.42$% for the local-attention recurrent baseline (mean $\pm$ sample SD): a 63.2% reduction in SD with a similar mean. Upper state attention also reduces variation, reaching $74.75\pm6.24$%, so this benefit is not unique to update-level attention. Disabling the upper delta correction retains $70.62\pm8.60$%. Second, blocking gradients at the delta-attention inputs changes accuracy to $65.25\pm12.40$% in the matched seven-seed comparison, increasing SD by 50.2%. It also delays a 99% validation threshold on average among the same six seeds that reach it; the 95% threshold is reached earlier on average with input-gradient blocking across all seven seeds. Third, lower delta attention exhibits substantially less extrapolation degradation than lower state attention: 62.60% versus 19.40%, against a 71.06% baseline. Removing its correction reduces accuracy to 22.56%; its advantage over lower state attention also persists under input-gradient blocking. These observations motivate bounded update-level attention as a recurrent learning scaffold, combining reduced seed variation with less severe degradation in a placement where state attention fails.

cs.LG

新论文 · v1arXiv:2611.04901

Near-Linear Lower Bounds for Testing Directed Acyclicity

Artur Czumaj, Pan Peng, Yuyang Wang

原文摘要

We study testing acyclicity of directed graphs in the bounded-degree incidence-lists model, where a tester can query the outneighbors of a vertex but not its inneighbors. Despite significant effort, no tester with $o(n)$ queries is known, while the best established lower bounds are $\widetildeΩ(n^{5/9})$ for one-sided testers (Chen, Randolph, Servedio, and Sun, 2022) and $Ω(n^{1/3})$ for two-sided testers (Bender and Ron, 2002). We show that a query exponent arbitrarily close to one is necessary: for every fixed $η\in(0,1)$, there exists a constant $\varepsilon_η>0$ such that, for every constant $d\ge2$, every randomized adaptive two-sided $\varepsilon_η$-tester for acyclicity of simple $n$-vertex directed graphs whose indegrees and outdegrees are at most $d$ makes $Ω(n^{1-η})$ queries. Our proof overcomes two barriers. First, in previous constructions, the acyclic part of the graph is easy to recognize, which helps an algorithm stay inside the cyclic part. We hide a high-girth cyclic core inside a hierarchy of acyclic masking regions, in which each region imitates the levels below it and can be told apart from them only through rare events, and an iterated information-theoretic argument shows that every exploration observes only small, low-diameter forest components of the core. Second, a two-sided tester may exploit the statistics of collisions without ever seeing a cycle, and at a near-linear budget collisions are unavoidable. We compare complete transcripts with those of an acyclic input built on a fixed core by counting injective embeddings of the observed forest: in high-girth cores, all connected collision patterns of bounded order contribute identically, which makes the two transcript distributions statistically indistinguishable.

cs.DS

版本更新 · v2arXiv:2610.42010

TurnTurk-GPT: Text-Based Turn-Taking Prediction for Turkish

Ahmet Tuğrul Bayrak, Fatma Nur Korkmaz, Nur Yağmur Tuncer, Mustafa Sertaç Türkel

原文摘要

This paper presents TurnTurk-GPT, a text-based turn-taking predictor for Turkish obtained by fine-tuning a Turkish GPT-2 model with the TurnGPT objective on synthetic and real dialogue, and evaluates it on real Turkish conversation against rule baselines, a zero shot Turkish language model and a widely used multilingual end-of-turn detector. Evaluation uses word-level decision points on unpunctuated, lower-cased text approximating the output of streaming speech recognisers, recording-disjoint and speaker-disjoint folds, nested threshold selection and paired cluster bootstrap tests. TurnTurk-GPT outperforms the multilingual detector under both recording-disjoint and speaker-disjoint evaluation. Its gain over a zero-shot Turkish language model is largest for speakers seen in training, while on unseen speakers it matches this strong baseline. Removing the suffixes of the turn-final word reduces AP by up to 44%, against 2% for a sentence-internal word, locating the Turkish end-of-turn cue in verb-final morphology. Synthetic dialogue alone yields the weakest trained model, and when a speaker pauses the zero-shot and multilingual baselines remain close to chance. The model and the evaluation protocol are publicly released.

cs.CL

新论文 · v1arXiv:2611.04900

The Power of Bidegeneracy for Hypergraph Data Structures

Marco Bressan, Stefano Clemente, Giacomo Fumagalli, Daniel Paul-Pena, C. Seshadhri

原文摘要

A hypergraph $H = (V,E)$ describes a set system over a vertex universe $V$. Hypergraphs are increasingly popular in network science, as they represent interactions between subsets of vertices. A natural challenge is to design a data structure for $H$ to quickly answer basic questions about it, e.g. how many neighbors a vertex $v$ has or whether a hyperedge contains a vertex subset $S$. Such questions are trivial for graphs, for which we simply inspect the adjacency list. The gold standard, from a data structures perspective, would be near-linear time preprocessing and query answering in (poly)logarithmic time. Since this is unlikely for arbitrary $H$, we ask for well-motivated hypergraph properties that can make such a goal possible. We introduce bidegeneracy, a measure of hypergraph sparsity that strictly generalizes many other measures, including bounded degree, bounded rank, and bounded $\infty$-degeneracy. We show that bounded bidegeneracy yields fast hypergraph data structures. For a large set of fundamental queries, including their listing and sampling versions, we obtain near-linear preprocessing and (poly)logarithmic query time. Moreover, direct reductions from assumptions like the Orthogonal Vectors Conjecture suggest that, without assumptions on the input, these structures require almost-quadratic preprocessing or almost-linear query time. We use bidegeneracy to compute a compressed representation of $H$ and perform careful reductions to stabbing and searching problems in $\mathbb{R}^d$. Our framework significantly extends the well-studied "partial matching" problem of finding database entries through wildcard search. It also uncovers an intriguing connection between hypergraph sparsity, compression, and the complexity of hypergraph primitives. We also find remarkably low bidegeneracy in hypergraph datasets from the literature, suggesting practical consequences.

cs.DS · cs.DB · cs.DM

新论文 · v1arXiv:2611.04899

Knowledge Graph Lakehouse: A Cloud-Native Architecture for Managing Enterprise Knowledge Graphs at Scale

Bashar Ahmad, Christoph G. Schuetz, Loris Bozzato

原文摘要

Modern data architectures for integrating heterogeneous data sources to discover actionable knowledge include the data warehouse, the data lake, and the data lakehouse, which combines the flexibility of the data lake with the structured data management capabilities of the data warehouse through metadata, indexes, and caching. Enterprise knowledge graphs (KGs) offer an alternative approach to such integration for the purposes of data analysis, but handling them at scale must address the Three Vs of big data: volume, velocity, and variety. Contextualized KGs (CKGs) meet part of that challenge by enriching facts with contextual information, yet many applications require only a context-specific subset of that knowledge. We propose the Knowledge Graph Lakehouse (KG Lakehouse), a cloud-native microservice architecture that adapts the data lakehouse paradigm for management of CKGs at scale. The KG Lakehouse indexes incoming source documents along configurable context dimensions and stores these documents in a data lake, from which application-specific CKGs are constructed on demand instead of maintaining a single, monolithic KG. We realize the proposed architecture as a proof of concept, with independently deployable services built from established cloud technology; context dimensions and format-specific document handling enter as configuration, leaving the architecture independent of the application domain. We evaluate the implemented system in experiments on a distributed cluster deployment.

cs.DB

新论文 · v1arXiv:2611.04898

Local Distributed Computation under Crash Failures

Diana Ghinea, Fabian Kuhn, Chen-Da Liu-Zhang, Zahra Parsaeian

原文摘要

We study deterministic algorithms for locally checkable graph problems in the synchronous LOCAL model with crash failures, where a crashing node may send messages to only some neighbors. We introduce consistent neighborhoods: partial radius-$R$ views that agree locally across surviving edges and are complete without crashes. For $R=T+\ell+1$, these views allow local simulation of $T$-round fault-free algorithms that remain correct on subgraphs, satisfying constraints wherever the radius-$\ell$ checking neighborhood contains no crash. On graphs with at most $n$ nodes and maximum degree at most $Δ\geq3$, we construct these views in $O(\min\{n,(Δ-1)^R,RΔf\})$ rounds when a crash bound $f\geq1$ is globally known; the first two bounds require no knowledge of $f$. For $Δ=2$ or girth greater than $2R$, including forests, $O(R)$ rounds suffice. Our upper bounds are essentially tight in suitable parameter regimes. One crash can force $Ω(n)$ rounds even for $R=3$ on diameter-two graphs. For each fixed $Δ\geq3$ and sufficiently large $R$, we prove a $(Δ-1)^{R-O(\sqrt R)}$ lower bound even with crashes restricted to round beginnings. We also prove an $Ω(ΔRf)$ lower bound when $R\geq4\lceil\log_{Δ-1}f\rceil+4$ and $n\geqΔRf$. For locally checkable labeling (LCL) problems, we preserve $O(\log^* n)$ complexity under any number of crashes whenever this bound holds without faults on all graphs with a fixed degree bound. In contrast, we construct an LCL on graphs of maximum degree at most five with fault-free complexity $Θ(\log n)$ and crash-tolerant complexity $Θ(n)$. Finally, any fault-free sinkless-orientation algorithm can be transformed to tolerate any number of crashes with only one additional round, guaranteeing correctness even at surviving nodes adjacent to crashes.

cs.DC · cs.DS

版本更新 · v2arXiv:2610.35848

Exploring the Tractability Frontier of Hylland-Zeckhauser Models

Ioannis Panageas, Avi Shein, Shayan Taherijam, Vijay V. Vazirani

原文摘要

The Hylland-Zeckhauser (HZ) mechanism provides a market-based approach to one-sided matching, making efficient equilibrium computation central to its implementation. Under bi-valued utilities, it admits a strongly polynomial-time algorithm [VY], whereas with four values per buyer, the problem is PPAD-hard under inverse polynomial approximation [CCPY]. To understand the tractability boundary, we study two extensions of the bi-valued case: a third linear utility value and separable concave utilities with two common slopes. For every fixed rational $a\in(0,1)$, we prove that computing a normalized additive $\varepsilon_{*}(a)/N$-equilibrium in an $N$-buyer HZ market is PPAD-complete for some constant $\varepsilon_{*}(a)>0$, even when all utilities belong to the same prescribed set $\{0,a,1\}$. This resolves the main question left open by [VY, CCPY]: whether three utility values already suffice for PPAD-hardness. Assuming the PCP-for-PPAD conjecture, we strengthen the above-stated result to constant additive-error hardness. For the concave extension, we compute an exact equilibrium in strongly polynomial time with two marginal utility slopes common across goods for each buyer and arbitrary rational buyer-good breakpoints. With three common marginal slopes, suitable breakpoints encode the three valued linear case, yielding PPAD-hardness. Thus, our paper identifies two thresholds separating tractable and intractable cases of HZ models with utility functions specified by utility values or marginal slopes. In both cases, the tractability threshold lies between two and three.

cs.GT

版本更新 · v4arXiv:2510.01137

Re-examining low-rank adaptation for private LLM fine-tuning

Ali Dadsetan, Frank Rudzicz

原文摘要

Privacy is a central concern when fine-tuning large language models (LLMs) on sensitive data, and differentially private stochastic gradient descent (DP-SGD) provides formal privacy guarantees. When performance at a fixed privacy level largely saturates on established benchmarks such as GLUE, we ask whether the same performance can be reached with less computation. Both theory and practice show that lower-rank models are better suited to DP training, a property especially relevant for LLMs, whose fine-tuning gradients exhibit a strong low-rank structure. Methods such as DP-LoRA exploit this by expressing each layer's weight update as a sum of only a few non-zero rank-one components. However, we argue that while having few non-zero components is important, the isotropic noise injected by DP-SGD inflates the singular values of the gradient matrix, disrupting their naturally fast decay. We investigate whether this noise-induced spectral distortion slows optimization. Experiments on language classification (GLUE with RoBERTa) and table-to-text generation (E2E and DART with Qwen and Llama models up to 4B parameters) show that partially restoring the original singular-value profile significantly accelerates DP-SGD convergence without compromising privacy guarantees. Our code is available at https://github.com/alidadsetan/re-exam-private-low-rank.

cs.LG

新论文 · v1arXiv:2611.04897

TapeSAC: Automated, Pareto-Optimal Fine-Grained Memory Management for Large Model Training

Kaihui Ren, Yifan Zhao, Zejian Wang, Yingtong Xiong, Xiaoling Zhou, Daohong Xu, Chenhao Guan, Zhikang Mo 等 14 位作者

原文摘要

Selective activation checkpointing (SAC) decides which activations to save for the backward pass and which to recompute: each choice is a point in the plane of peak memory and recomputation time, and the goal is that plane's Pareto frontier. Current practice falls short of this goal. Hand-tuned policies fix a single point that does not adapt when the model, batch or kernels change; PyTorch's SAC reruns each block's forward pass in program order, recomputing values the backward pass never reads; and the memory budget of torch.compile treats recomputation as free or forbidden and selects saved tensors by bytes alone, an assumption that fails for the custom kernels that produce many of a large model's activations. We present TapeSAC, which automates SAC in eager PyTorch without editing the model's forward code. TapeSAC records each block's forward pass at the dispatcher and, during backward, replays only the producers of the values autograd consumes, so saving a tensor eliminates every producer needed only for it. A planner selects the saved tensors from measured recomputation costs under a single limit on step-peak memory. On Qwen3.8-27B and Qwen3.6-35B-A3B, replay alone reduces step time by 3.0% and 1.7% versus full checkpointing at no greater memory cost; memory-aware planning raises these gains to 6.3% and 13.9% under a 90%-of-device-memory limit. The evaluated hand-tuned policies fall short of this memory-recomputation frontier and, on Qwen3.6-35B-A3B, run out of memory at larger batches. Over 500 steps on real data, TapeSAC reduces training time by 8-11%; on Qwen3.5-397B, it is 2.7% faster than a model-specific hand-tuned policy while using 14% less memory.

cs.DC

版本更新 · v2arXiv:2610.21779

FuseAdapt: Parameter-Efficient Multimodal Fusion for Semantic Segmentation with Missing Modalities

Xin Zhang, Robby T. Tan

原文摘要

Multi-modal semantic segmentation benefits from complementary sensors, but this benefit is fragile when some modalities are degraded or missing at test time. Many existing methods rely on dedicated fusion modules or multi-branch cross-modal encoders, and the fusion often becomes unreliable when modalities are absent, leading to substantial performance drops. We propose FuseAdapt, a parameter-efficient framework that performs fusion within the adaptation space of a frozen vision foundation model (VFM), exploring whether VFM priors can serve as an effective shared backbone for multi-modal segmentation. Instead of attaching a standalone fusion network, FuseAdapt assigns each modality a lightweight adaptation branch and performs adaptation-space fusion by keeping Q/V low-rank adaptation private to each modality and routing only FFN low-rank residual activations across modalities inside the frozen backbone. The pretrained VFM remains fixed while modality-specific corrections and explicit cross-modal interaction are learned through the adaptation paths. To handle missing modalities, we further introduce Predictive Modality Modeling (PMM), a direct representation-level objective for cross-modal redundancy. During training, PMM masks a target modality and predicts its embedding from the visible ones, supervised by a teacher target computed under full-modality input. PMM is used only during training and adds no inference-time overhead. Across three multi-modal segmentation benchmarks (MCubeS, DELIVER, MUSES), FuseAdapt consistently improves both modality-complete and modality-incomplete segmentation with a small trainable budget, yielding up to +3.01 mIoU under full modalities and +11.25 mIoU under missing modalities over prior state-of-the-art. Project page: https://devinxzhang.github.io/FuseAdapt-Page/

cs.CV

新论文 · v1arXiv:2611.04894

VisSearch-Bench: Evaluating Long Horizon Visual Search in Multimodal Agents

ZhengXian Wu, Qianhao Nie, Zhuohong Chen, Junjie Gao, Yuyao Zhang, Yunyao Yu, Hangrui Xu, Cheng Cheng 等 13 位作者

原文摘要

Multimodal agents use web and image tools to answer questions beyond their internal knowledge. Some search tasks use images mainly to identify an initial entity, then rely on text retrieval. These tasks offer limited insight into how agents connect information across images, objects, and search steps. We therefore focus on visual context management. This involves organizing and using visual information and linking it to other findings during search. Visually intensive tasks require agents to combine object appearance, local details, or spatial relations with external information. We introduce VisSearch-Bench, with 204 human-written tasks across 7 main domains and 25 subdomains. It covers Set-wise Visual Search, Sequential Visual Search, Hybrid Wide-Deep Search, Competitive Visual Disambiguation, and Visual-Structure-Guided Search. Each task provides a reference answer, traceable evidence, and scoring rules. Accuracy measures complete task success, while Process Score measures the correctness and completeness of individual results and subquestion answers. Across 16 multimodal models, the best system fully solves only 26.47% of tasks, even with search tools. These results highlight the challenge of linking visual evidence with search results to produce complete answers.

cs.CV · cs.AI

新论文 · v1arXiv:2611.04893

Fault-tolerant shallow recurrent decoders for sparse sensing with missing sensor measurements

Matteo Romilio Pasqual, Matteo Tomasetto, J. Nathan Kutz, Andrea Manzoni

原文摘要

Real-world sensing systems are inherently imperfect: sensors may fail, intermittently disconnect, operate with asynchronous sampling rates, and be subject to noise, leading to measurement streams that are irregular, incomplete, and heterogeneous. Nevertheless, sensing strategies for real-time state reconstruction typically assume synchronous and continuously active sensors, a constraint that substantially limits their applicability in operational environments. In this work, we introduce fault-tolerant sparse sensing strategies in the context of shallow recurrent decoders (SHRED) to enable high-dimensional state estimation from sparse, asynchronous, and missing sensor measurements. Specifically, we consider naive imputation strategies, fault-tolerant recurrent temporal encoders, and we introduce four different transformer-based masking mechanisms to make SHRED explicitly aware of sensor availability through the binary data-availability mask. Moreover, we further introduce a multi-step decoding training objective for SHRED, resulting in smoother latent trajectories and more robust predictions. Throughout a synthetic benchmark and three real-world problems in hydrodynamic and ocean modeling, we show that (i) transformer-based masking mechanisms outperform standard imputation techniques and fault-tolerant recurrent architectures, (ii) the multi-step decoding training objective enhances reconstruction fidelity and robustness in the presence of heterogeneous missing-data patterns, while (iii) the computational efficiency of SHRED is preserved, with no additional inference-time overhead.

cs.LG · cs.AI

版本更新 · v2arXiv:2610.41970

When Does Test-Time Search Help World Action Models? An Empirical Audit of Candidate Selection and Simulator Integrity

Jun Liu, Dajie Sun, Zhenglun Kong, Zhenjiang Fan, Peiyan Dong, Fan Yang, Wenbin Zhang, Geng Yuan 等 11 位作者

原文摘要

World-action models increasingly apply test-time scaling, spending extra inference computation on candidate selection and adaptive allocation to improve control. Such gains are credible only when candidates carry exploitable signal, nominal compute savings become real speedup, and evaluation stays reliable. We audit all three on Cosmos Policy and RoboCasa with a premise-first, pre-registered methodology. On clean data, a learned value selector is 1.66 pp worse than random; a hindsight oracle gains only 1.40 pp, with an episode-level interval spanning zero; and 82% of states show identical candidate outcomes, leaving little selection headroom. Token pruning cuts per-forward FLOPs by up to 47% but yields at most a measured 1.15$\times$ end-to-end speedup on the deployed path (1.25$\times$ on a decode-excluded path), short of a 1.5$\times$ target, and our adaptive-allocation experiment is inconclusive under a power gate. We further identify and fix a silent rendering corruption whose rate rises sharply along compute-heavy planning paths while leaving the official direct-policy result unaffected, and release a detector, fix, and scripts. These findings show why test-time scaling should be audited as a chain of premises (decision signal, realized efficiency, evaluationintegrity) rather than by success rate alone. Conclusions are scoped to the tested configuration.

cs.AI

版本更新 · v3arXiv:2610.01421

Robust and leakage-resilient device-independent oblivious transfer in MiniQCrypt

Rishabh Batra, Zhili Chen, Rahul Jain, YaoNan Zhang

原文摘要

Assuming post-quantum one-way functions, we construct device-independent oblivious transfer and bit commitment that tolerate independent honest faults at a constant rate and adaptive, bidirectional quantum leakage between the laboratories at a constant rate. Honest parties use trusted classical computation to operate untrusted quantum devices, which may share arbitrary entanglement and perform joint measurements without assumptions of independence or identical distribution. Security is simulation-based against quantum polynomial-time adversaries and composes sequentially with efficient simulators. For security parameter $λ$ and a prescribed total leakage budget $\ell$, one complete one-bit oblivious transfer uses $Θ(\ell+\log^2λ)$ device coordinates in at most three single-use device windows, including preprocessing, and polynomial classical computation and communication. The leakage budget is shared across these windows. The commitment has efficient simulators against both parties and yields device-independent coin tossing with abort; each uses one window. Completeness of oblivious transfer gives device-independent secure computation with abort for every efficiently computable classical functionality on a fixed number of parties, against static corruption of any proper subset, provided each reached call to oblivious transfer satisfies the device and budget conditions. The construction combines short selectors with code-based choice masking, a global audit, and error correction across field symbols. The commitment extractor changes a classical code coset while leaving the device execution and its leakage unchanged. Sender security uses a global Fourier analysis and a selector-aware Magic Square repetition bound derived from the two-round threshold theorem of Kundu and Tan (2023).

quant-ph · cs.CR

新论文 · v1arXiv:2611.04889

NP-Hardness and a PTAS for Maximum Interval Multicover, with Applications to Dense Subgraphs

Morteza Alimi, Tobias Mömke, Alexandru Popa, Michael Ruderer

原文摘要

Given intervals and points on a line, each point with a demand, and a budget $K$, Maximum Interval Multicover asks for at most $K$ intervals that satisfy as many points as possible, a point being satisfied if it lies in at least as many chosen intervals as its demand. One application is committee elections in which each candidate is approved by consecutive voters and voters have individual demands. Xu, Ran and Zhang introduced the problem and gave a $1/2$-approximation; the objective is not submodular when demands exceed one. Li, Tu, Zhang and Cao gave a polynomial-time approximation scheme (PTAS) for the minimization counterpart, unweighted partial interval multicover, and asked for its complexity. We prove that both problems are NP-hard, even for intervals of equal length; as their optima are integers bounded by the input size, neither has a fully polynomial-time approximation scheme unless $\mathrm{P}=\mathrm{NP}$. We then give a PTAS for Maximum Interval Multicover, also for arbitrary nonnegative nondecreasing rewards for the coverage of each point. Building on a decomposition from Nonner's PTAS for Densest $k$-Subgraph on interval graphs, our scheme cuts the line into pieces at a small loss and solves every piece exactly. The key dynamic program handles intervals crossing a common point by choosing an interleaving of their left and right endpoints rather than sweeping along the line; it needs only two counters to track these intervals. The same algorithm yields PTASes on convex bipartite graphs for Bipartite Dense Subgraph, improving on the ratio $2/3$ of Backer and Keil for the subclass of bipartite permutation graphs, and on interval graphs for Maximum $k$-Vertex Cover and weighted clique counts.

cs.DS

版本更新 · v2arXiv:2510.23316

Efficient Repair of (k+2, k) Degraded Read Friendly MDS Array Codes With Sub-packetization 2

Jie Li, Xiaohu Tang

原文摘要

In this paper, we present two constructions of degraded read friendly (DRF) MDS array codes with two parity nodes and a sub-packetization level of 2 over small finite fields, applicable for any arbitrary code length. The first construction achieves the smallest repair bandwidth among all existing constructions with the same parameters, and is asymptotically optimal with respect to the lower bound on the average repair bandwidth characterized by Zhang et al. The second construction supports two repair mechanisms, depending on whether computation within the helper nodes is permitted or not during the node repair process, thereby optimizing either the repair bandwidth or the rebuilding access.

cs.IT

版本更新 · v2arXiv:2606.01275

Domination-Avoiding Learning Agents Cannot Collude

Noam Nisan, Emmanuel Zerah

原文摘要

An influential paper of Calvano et al. empirically demonstrated that Q-learning agents spontaneously collude when placed as sellers that compete on prices in a natural market model. More recent results of Fish et al. empirically demonstrated that similar collusion happens with commercial LLMs. We formally prove that such collusion can also happen with external-regret-minimizing agents. We identify a very general class of agents, which we term Domination-Avoiding agents, that provably do not collude in such markets. This class contains all Mean-Based agents and all internal-regret-minimizing agents, as well as others such as Multiplicative-Weight agents with variable learning rate and contextual variants thereof. More generally we show that, in any game, this class of agents is guaranteed to jointly learn to almost never play strategies that are eliminated by repeated elimination of purely dominated strategies.

cs.GT

新论文 · v1arXiv:2611.04887

FourSight: Stable FP4 RL Post-Training via Sequence Filtering and Sparse Channel Compensation

Yining Wei, Tianyuan Wu, Gu Gong, Yuechen Tao, Yinghao Yu, Xiaowen Chu, Wei Wang

原文摘要

Reinforcement learning (RL) post-training increasingly targets low-bit deployment, with NVFP4 weight-and activation quantization (W4A4) becoming the state-of-the-practice format. However, integrating NVFP4 into RL degrades rollout quality and amplifies cross-engine training-inference mismatch (TIM), destabilizing training. We show that these failures are concentrated rather than uniform - severely mismatched tail tokens concentrate in a few outlier sequences, while policy weights remain largely intact and quantization error concentrates in a few high-variance activation channels. Guided by this, we present FourSight, an algorithm-system co-design with two targeted solutions: TIM-aware sequence filtering that excludes drifted trajectories from policy updates, and sparse precision compensation that keeps only top-variance channels in BF16 while retaining native NVFP4 elsewhere. We further design a fused SpliceGEMM kernel with specialized prefill and decode datapaths to minimize overhead. FourSight sustains near-BF16 accuracy and strong FP4 deployment quality across models and engines, while improving step-to-accuracy by 1.76-2.60x and staying within 2.3% of FP4 step time up to 120B-scale models.

cs.AI · cs.LG

新论文 · v1arXiv:2611.04886

Modelling lock-in of AI adoption through skill erosion

Renaud Lambiotte

原文摘要

Generative AI can improve immediate performance but may erode the human skills required for future work. We study a model in which individuals tend to imitate successful peers, while their independent skills grow with practice and erode with reliance on AI. Because each agent's skill reflects their history, non-users and AI users develop different skill distributions, which we derive exactly. Skill erosion can produce bistability and hysteresis between a low-adoption, high-skill state and a high-adoption, low-skill state. When agents rarely change behaviour at random, the two transitions are asymmetric. A single AI user spreads through a population of experts only if AI-assisted work earns more than expert work, whatever the timescale of skill adaptation. A single non-user, by contrast, can lead an AI-dependent population back to independent work only if they regain enough skill before returning to AI, which becomes easier the more persistent behaviours are. As AI improves, adoption can jump abruptly, and a sufficiently long increase in its benefit, such as a period of low prices, can leave a population relying on AI after the benefit has returned to its initial value. Skill erosion thus creates a history-dependent switching cost that can make widespread AI adoption difficult to reverse.

cs.AI · physics.soc-ph

版本更新 · v2arXiv:2610.17613

MAS-Gate: Unlocking Multi-Agent System Lifecycle via Node-Centric Quantification

Hehai Lin, Zixuan Wang, Ming Yan, Peidong Wang, Shilei Cao, Minzhi Li, Bosheng Ding, Juepeng Zheng 等 9 位作者

原文摘要

Large language model (LLM)-based multi-agent systems (MAS) can solve complex problems beyond the reach of a single agent by decomposing tasks and coordinating complementary capabilities. Despite extensive research on MAS, existing work largely focuses on specific aspects or individual phases of their development and operation, resulting in fragmented perspectives with objectives and signals that are difficult to reconcile across these different settings. To bridge these disconnected perspectives, we conceptualize MAS development and operation as a three-phase lifecycle spanning design-time orchestration before execution, runtime intervention during execution, and post-hoc attribution after execution, and introduce MAS-Gate, a unified node-centric quantification applicable across these phases. Modeling each execution as a directed acyclic graph, MAS-Gate combines within-node utility, which estimates a node's contribution through changes in reference-answer likelihood, with inter-node strength, which approximates semantic uptake and potential downstream reach. We adapt this shared quantification to three objectives: providing a structure-aware dense reward for Orchestrator training, training an Editor to act on execution prefixes using paired rewards from completed edited and unedited trajectories, and supplying risk-ranked nodes as auxiliary evidence for LLM-based post-hoc attribution. Experiments spanning interaction environments, knowledge-intensive multi-hop question answering, general reasoning, and post-hoc attribution demonstrate that MAS-Gate improves workflow construction, targeted runtime editing, and LLM-assisted error localization over corresponding phase-specific baselines. Together, these results establish MAS-Gate as a unified structural interface for improving MAS generation, dynamic editing, and error attribution throughout the lifecycle.

cs.AI · cs.MA

新论文 · v1arXiv:2611.04885

DLER: Dual-Logit Experience Replay for Online Continual Learning

Huiwei Lin, Shanshan Feng, Kong Aik Lee

原文摘要

Online continual learning aims to continuously train neural networks on a non-stationary data stream in a single pass. Rehearsal-based methods alleviate catastrophic forgetting by replaying stored samples, but the imbalance between current and previous data often leads to predictions biased toward current classes. Many approaches have been proposed to overcome the forgetting problem by correcting the bias; however, they still need to be improved in an online fashion. By decomposing the dot-product logits into an angle factor and a norm factor, our analysis reveals that the angle factor efficiently captures novel knowledge but is particularly susceptible to prediction bias, whereas the norm factor helps preserve historical knowledge. Based on these observations, we propose Dual-Logit Experience Replay (DLER), which exploits dual-logits for both model optimization and memory management. Specifically, DLER learns current samples using cosine logits and incorporates additional dot-product logits when replaying previous samples to mitigate prediction bias. To strengthen dual-logit learning under limited replay memory, an auxiliary supervised contrastive objective promotes angular compactness within each class, extending corrections learned from limited replay samples to other samples of the same class. Meanwhile, we introduce a memory update strategy that preferentially retains samples for which dot-product prediction assigns a higher probability to the correct class than cosine prediction, aligning sample selection with dual-logit training. Extensive experiments on three datasets demonstrate the effectiveness of DLER, particularly under limited memory budgets.

cs.LG

新论文 · v1arXiv:2611.04884

Best-of-Many-Worlds MMS Allocation for Chores with Sublinear Disposals

Zehan Lin, Xiaowei Wu, Shengwei Zhou

原文摘要

We study randomized allocations (lotteries) of indivisible chores under additive costs and introduce the notion of MMS1, which requires each agent's bundle to satisfy the maximin share (MMS) bound after the removal of at most one chore. Our main result establishes that every instance admits an ex-ante proportional lottery in whose support every allocation is MMS1 and all but $o(n)$ agents satisfy MMS. Consequently, every realized allocation can be made MMS by disposing of at most $o(n)$ chores. The proposed framework further achieves ex-ante proportionality alongside ex-post $4/3$-MMS, $o(n)$-AMMS, or $1$-out-of-$d$ MMS for $d=(1-o(1))n$. These guarantees substantially improve upon state-of-the-art bounds for MMS allocation for chores with disposal or subsidy, best-of-both-worlds fairness, approximate AMMS, and ordinal MMS approximations.

cs.GT · cs.DS

新论文 · v1arXiv:2611.04883

Reproducibility in open-source RISC-V HW flows

Peter Kourzanov, Anmol Anmol

原文摘要

Open-source hardware is booming. To prevent fragmentation, encourage collaboration and reuse we propose the RISC-V to join forces with Reproducible Builds communities and concentrate innovation potential where its needed most: creation of new micro-architectures, IPs and their integration into new SoCs and applications. To facilitate this goal, we chose Guix, a rigorous solution for reproducible software artefacts. We apply it to dependency management & reproducibility problems in open-source hardware and show the validity of the approach, taking CVA6 as a running example. The end result - a fully reproducible collection of packaged tests, emulation, simulation and cycle-accurate models - shows a promising workflow that could (in future) scale to support larger RISC-V community with reusable software & hardware components for next-generation platforms.

cs.SE