跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+1022新增论文
+813其中 AI 相关
+85已有论文修订
+95新增 AI 导读

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

统计口径与数据新鲜度

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

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

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

24,849 已收录论文20,754 AI 相关7,213 有修订112 HF 社区发现

浏览论文库

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

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

A Roadmap to Impactful Pluralistic Alignment Research

Elinor Poole-Dayan, Jillian Fisher, Jacob Andreas, Mitchell Gordon, Michiel A. Bakker

原文摘要

Much research on responsible AI aims to change the behavior of AI systems that billions of people use. Pluralistic value alignment---the goal of building AI systems that represent and serve diverse human values and perspectives---has emerged as one such active research agenda. Yet, in an audit of the major frontier labs and open-weight developers, we find no public evidence that it has shaped how their models are trained or evaluated. Pluralistic alignment requires adoption to achieve its main goals, so we identify three barriers and lay out a roadmap of research to address each: 1. The justifications for pluralistic alignment so far are mostly normative or theoretical. Studies are needed that measure the benefits and drawbacks of pluralistic AI for users and society. 2. The pluralistic alignment research community has not settled when pluralistic behavior is warranted or what it should look like in practice. Research is needed to specify this behavior concretely enough for developers to operationalize. 3. Existing pluralism evaluations and methods are not ready for deployment. Evaluations and methods are needed that report their effects on other model properties and meet the requirements of production systems. These barriers are not unique to pluralistic alignment, so our roadmap applies to other areas of responsible AI research with similar theories of change. As people hand more decisions to AI systems and AI agents act on their behalf, we hope our roadmap helps this research reach the deployed models making those decisions.

cs.AI

版本更新 · v3arXiv:2609.35711

论多物品拍卖中确定性的力量

On the Power of Determinism in Multi-Item Auctions

Yiannis Giannakopoulos, Johannes Hahn

AI 速读 基于摘要

作者研究单一加性买家、多件独立非同分布物品的垄断拍卖,通过拉格朗日对偶上界改进三种简单确定性拍卖相对最优真实拍卖收益的近似比。

cs.GT · cs.DM

查看原文摘要

We study the classical multi-item monopoly setting with a single additive buyer and $m$ heterogeneous items whose values are independent but not necessarily identically distributed. We compare the revenue (REV) of the optimal truthful auction, which in general may be randomized or complicated, with the revenues of three simple deterministic auctions: selling all items separately (SREV), selling them as a single grand bundle (BREV), and choosing the better of the two. Our technical cornerstone is a general upper bound on the optimal multidimensional revenue, parameterized by freely chosen item-wise caps, and expressed in terms of optimal single-item, Myersonian revenues and basic statistics of the value distributions. We derive this inequality through Lagrangian duality for a nonlinear programming formulation of the worst-case approximation ratio of separate-selling. Combining this inequality with carefully chosen caps and a probabilistic analysis of the resulting terms, we obtain improved approximation guarantees for all three deterministic auctions, both for general independent values and for iid values. Notably, we prove that $REV\le 2.5\max\{SREV,BREV\}$, improving the long-standing $5.2$ factor of Ma and Simchi-Levi and the $6$ factor of Babaioff, Immorlica, Lucier, and Weinberg. We complement this upper bound with a construction establishing a lower bound of $2.19$, improving the bound of $2$ by Rubinstein. For two iid items, we determine the exact approximation ratio of selling separately. Our proof constructs tight Lagrangian dual certificates for the aforementioned programming formulation, when item values lie in the grid $\{0,1/K,2/K,\dots,1\}$, for any discretization parameter $K$. Taking $K\to\infty$ yields the tight ratio $1+W(1/e)\approx1.2785$ in the continuous-valued setting, where $W$ is the Lambert-W function, closing the $[1.278,1.368]$ gap left by Hart and Nisan.

新论文 · v1arXiv:2611.05280

YANAMI:面向多轮有状态交互的大规模多模态数据集与基准

YANAMI: A Large-Scale Multimodal Dataset and Benchmark for Multiturn Stateful Interaction

Shengyu Wang, Tengyue Nong, Junming Liu, Haosong Peng, Siyu Li, Ruiqi Lei, Fushuo Huo, Yuhao Pan 等 13 位作者

AI 速读 基于摘要

作者提出首个面向多模态有状态交互的大规模多轮对话数据集 YANAMI-400K 与评测基准 YANAMI-Bench,并报告微调 BAGEL 后在图像编辑、生成与有状态交互上均有提升。

cs.CV

查看原文摘要

Unified Multimodal Models (UMMs) integrate visual understanding, generation, and editing within a single unified framework. However, existing unified multimodal datasets and benchmarks remain dominated by single-turn tasks. Even in recent multi-turn datasets, many turns can be solved independently without tracking information across turns. Consequently, they provide limited supervision and evaluation for multimodal stateful interaction, which requires models to understand, maintain, update, and faithfully realize evolving dialogue states across turns. To address this gap, we introduce YANAMI, the first large-scale multimodal dialogue dataset and benchmark for stateful interaction, comprising YANAMI-400K and YANAMI-Bench. YANAMI-400K contains 400K multi-turn multimodal dialogues, with more than 2M images and 2.6M dialogue turns. The dialogues span four representative scenarios: Multi-Image Fusion, Image Editing, World Modeling, and Visual Reasoning, and require models to continuously track, preserve, and revise evolving multimodal dialogue states across turns. YANAMI-Bench comprises 400 multi-turn dialogues for systematically evaluating multimodal stateful interaction. It jointly evaluates Dialogue State Understanding and Visual Realization, characterizing the gap between models' ability to understand evolving dialogue states and their ability to faithfully realize them in visual outputs. Experiments show that fine-tuning BAGEL on YANAMI-400K improves image editing, generation, and multimodal stateful interaction by 10.3%, 2.0%, and 13.23%, respectively, while preserving its general visual understanding capabilities. Evaluations on YANAMI-Bench further reveal that existing UMMs still struggle to maintain, update, and visually realize evolving multimodal dialogue states.

新论文 · v1arXiv:2611.05279

Möbius:统一理解与生成的运动-语言模型

Möbius: A Unified Motion-Language Model Bridging Understanding and Generation

Jiazhi Shu, Chengfeng Zhao, Jinyi Wang, Yubo Zhao, Zhiyang Dou, Ronghui Li, Yu Lu, Xinwei Jiang 等 10 位作者

AI 速读 基于摘要

Möbius 将扩散生成过程直接放入与运动理解共享的多模态表示空间,在连续帧级原始运动上统一实现运动描述、文本生成运动、时序补全与指令引导编辑。

cs.CV

查看原文摘要

We aim to build a truly unified motion model that can understand, generate, and edit human motion within a single framework. Existing motion UMMs remain only partially unified: motion understanding is handled by a language model, while generation is often delegated to a separate diffusion module operating over learned motion latents. We introduce Möbius, which brings the entire diffusion process into the same multimodal representation space used for motion understanding. Clean motion, noisy motion, and text jointly participate in shared attention, while role-specific parameters process understanding and generation streams. Importantly, Möbius operates directly on continuous frame-level raw motion, requiring neither discrete tokenization nor a pretrained motion VAE. This simple formulation naturally supports motion captioning, text-to-motion generation, temporal completion, and instruction-guided editing within a single model. On HumanML3D, Möbius achieves state-of-the-art performance among unified motion models. Scaling to 1.7B parameters and 1,700 hours of motion data further demonstrates that our framework is both effective and scalable.

新论文 · v1arXiv:2611.05277

保形预测在表演性均衡下:表演性的代价

Conformal Prediction at Performative Equilibrium: The Price of Performativity

Ahmed Mahrous, Roberto Di Pietro

AI 速读 基于摘要

研究部署预测器会改变数据分布时,保形预测在表演性均衡处能否保持覆盖有效性,并揭示敏感度 L=1 处的相变与样本复杂度膨胀。

math.ST · cs.LG

查看原文摘要

Conformal prediction gives finite-sample coverage when calibration and test points are exchangeable, but exchangeability can fail when deployment changes the data distribution. We study conformal prediction in performative settings, where the deployed predictor affects the data distribution, and seek prediction sets valid at performative equilibrium: coverage must hold under $D(f^\star)$ for a performatively stable predictor $f^\star$. Under total-variation $L$-sensitivity of the distribution map, we prove a phase transition at $L=1$. If $L \ge 1$, no finite-sample procedure can uniformly guarantee both equilibrium-valid coverage and nontrivial prediction sets. If $L<1$, the minimax excess miscoverage over informative procedures is $\widetildeΩ(1/((1-L)\sqrt{n}))$, implying a sample-complexity inflation of order $1/(1-L)^2$ for fixed excess miscoverage. Our main technical tool is a transfer theorem: any procedure returning a predictor within $\varepsilon$ of equilibrium yields equilibrium-valid coverage up to an additive $L\varepsilon$ term after split-conformal calibration. We instantiate the theorem with two retraining algorithms: a model-free method for discretizable classes and a parametric tail-averaged method that matches the $n$- and $L$-dependence of this rate up to logarithmic factors. Experiments, including semi-synthetic credit scoring, demonstrate the predicted threshold behavior and scaling laws.

版本更新 · v2arXiv:2601.11420

区间CVaR非线性回归中尾部截断效应的量化

Quantification of Tail-trimming Effects for Interval CVaR Based Nonlinear Regression

Yulei You, Junyi Liu

AI 速读 基于摘要

该文从理论上量化了In-CVaR风险度量对损失右尾的截断在非线性回归抗异常值中的必要性与有效性。

math.OC · cs.LG · stat.ML

查看原文摘要

The tail trimming strategy is widely adopted for robustness against outlier contamination in statistical learning and operations research. However, it generally lacks the thorough understanding that to what extent the tail-trimming technique is effective for nonlinear regression. In this paper, we address the robust nonlinear regression based on the so-called interval conditional value-at-risk (In-CVaR), which is introduced to guard against outliers by trimming extreme losses. We first analyze the trimming effect of the In-CVaR based estimator under distributional perturbation. Our first finding is that the In-CVaR based estimator is qualitatively robust under distributional perturbation in terms of the Prokhorov metric if and only if the largest portion of losses is trimmed. Furthermore, under sample contamination, we derive a probably approximately correct (PAC) bound for the In-CVaR based estimator, showing that the preliminary covariate filtering that is customary in the literature is not needed for In-CVaR based regression. The nonconvexity of the In-CVaR objective, together with unboundedness of covariates, responses and parameter space create the technical challenges for our developed theory, and thus necessitate the new treatment of the qualitative robustness and PAC analysis. Overall, this study rigorously analyzes robustness properties of In-CVaR based nonlinear regression models, which illustrates to what extent the right tail-trimming of the loss by In-CVaR risk measure is essential and effective for robust nonlinear regression. These theoretical findings are further supported by numerical experiments.

新论文 · v1arXiv:2611.05275

Route Anything:面向通用人工智能系统的模型与策略路由研究

Route Anything: A Study of Model and Policy Routing for General-Purpose AI Systems

Pengfei Zhou, Yixing Ma, Hexin Wang, Weidong Tang, Zhenglin Wan, Wangbo Zhao, Yang You

AI 速读 基于摘要

该工作提出统一框架 Route Anything,研究在质量—成本权衡下如何为每个任务动态选择并协调专用模型、工具与策略,并构建跨模态大规模评测矩阵来检验路由的潜力。

cs.CV

查看原文摘要

Artificial general intelligence (AGI) requires a method that can understand, generate, reason, and act across diverse domains and modalities. Rather than relying on a single model to master every capability, a promising path toward AGI now is to orchestrate a heterogeneous ecosystem of specialized models, tools, and policies (candidates) into a unified AI system. At the heart of this vision lies a fundamental question: how can an AI system dynamically select and coordinate the most capable candidate for each task while balancing performance and computational cost? In this work, we present Route Anything, a unified framework for studying model and policy routing across general-purpose AI systems. We develop a unified theoretical foundation that characterizes optimal routing under quality--cost trade-offs and establishes how the information available to a router determines its attainable performance. To systematically investigate routing across diverse capabilities, we first construct an omni-modal trajectory matrix spanning 25 benchmarks across language understanding, image, video, and speech generation, coding and workplace agents, and robotic manipulation, comprising 374,401 scored runs from 452 candidate configurations. Building on this framework, we train and test different routers to investigate the potential of omni-modal model routing, the capabilities of learned routers, and the conditions under which routing improves efficiency. Our results reveal substantial opportunities for capability orchestration: per-input oracle routing outperforms the best fixed candidate by 5.4 points, and learned routers outperform it by 0.3 points across 16 benchmarks, by 2.1 points on video generation, and by 1.1 points on robot manipulation while using 24% less policy time. More importantly, routing raises efficiency by 8.82x on average compared with the reference model.

新论文 · v1arXiv:2611.05270

iGC:基于学习到的体细胞超突变先验的强化学习抗体优化

iGC: Antibody Optimization via Reinforcement Learning over a Learned Somatic Hypermutation Prior

Thao Nguyen, Robert G. Alberstein, Ewa Nowara, Homa MohammadiPeyhani, Holly R. Steach, Sarah A. Robinson, Yuval Shechter, Donald W. Lee 等 13 位作者

AI 速读 基于摘要

iGC 是一个两阶段强化学习框架,先学习体细胞超突变先验,再在抗原特异性亲和力优化中结合 KL 正则与奖励税元梯度,以兼顾生物学合理的突变与结合优化。

cs.LG · q-bio.BM

查看原文摘要

Antibody affinity maturation is a natural optimization process in which B cells acquire mutations through somatic hypermutation (SHM), undergo selection for improved antigen binding, and iteratively evolve toward higher affinity. Computationally modeling this process requires capturing both biologically plausible mutations and antigen-specific selection. However, existing mutation models do not directly optimize binding, while affinity optimization often neglects realistic mutation trajectories. We introduce iGC (in silico Germinal Centers), a two-stage reinforcement learning (RL) framework for antigen-specific antibody optimization. Stage 1 learns an SHM mutation prior from parent-child pairs in B-cell lineage trees and adapts it to a target affinity-maturation dataset. Stage 2 initializes an RL policy from this prior and optimizes antigen binding with Kullback-Leibler (KL) regularization toward the frozen prior. To prevent reward exploitation, including repetitive high-reward substitutions and structurally tolerated framework mutations, we introduce a Reward-Tax Meta-Gradient objective. RewardNet smooths the affinity landscape, while TaxNet penalizes reward overexploitation, jointly defining a learned meta-reward for policy optimization. We evaluate iGC on mutation prediction, SHM consistency, affinity optimization, and mutation diversity. The mutation prior more than doubles the strongest baseline in mutation-site prediction. Following RL optimization, iGC maintains SHM sequence structure. It also achieves a strong exploration-exploitation balance, yielding competitive reward-diversity products across candidate-selection cutoffs. These results demonstrate that iGC integrates biologically plausible mutation generation with antigen-specific affinity selection, providing an in silico framework for iterative antibody affinity maturation.

新论文 · v1arXiv:2611.05269

ToolSched:面向共享主机LLM智能体的资源高效工具调度

ToolSched: Resource-Efficient Tool Scheduling for Shared-Host LLM Agents

Shucheng Zou, Yuhao Gu, Long Chen, Zhongchun Zheng, BinZe Xie, Xianwei Zhang

AI 速读 基于摘要

为共享本地主机上的多个LLM智能体提供Shell MCP服务器,通过资源感知调度错峰执行命令,缓解资源争用并提升利用率与吞吐。

cs.OS

查看原文摘要

Local LLM agents often work on shared hosts. Unlike multi-tenant cloud clusters, these hosts often have tightly bounded memory, CPU, and I/O resources. Concurrent agents frequently suffer from resource contention, leading to failures such as OOM and reduced resource efficiency. Considering that agents' resource demands are bursty and shell command delay is imperceptible to agents, there is a huge scheduling opportunity to arrange when and in what order commands are actually executed. Thus, we present ToolSched, a Shell MCP Server for shared local hosts that serves multiple agents and schedules their operations. ToolSched embeds a resource model into the MCP interface: agents estimate resource demands along with command requests. These hints, together with real-time host resource conditions, determine when commands are actually executed. Internally, ToolSched applies a scheduling algorithm to stagger commands, reducing contention and improving resource utilization. Prediction correction and checkpoint-based recovery mitigate estimation bias and resource errors. Our evaluation on Terminal Bench shows that, compared with unscheduled execution, ToolSched improves resource utilization by 148.4% and end-to-end command throughput by 29.4%, demonstrating its effectiveness and practicality.

版本更新 · v2arXiv:2603.06588

vLLM Hook v1:面向 vLLM 的模型内部状态编程插件

vLLM Hook v1: A Plug-in for Programming Model Internals on vLLM

Ching-Yun Ko, Yunhua Fang, Pin-Yu Chen

AI 速读 基于摘要

作者提出一个开源插件 vLLM Hook,让 vLLM 推理引擎能够按配置捕获或干预模型内部状态,从而支持测试时对齐与增强方法。

cs.LG · cs.CL · cs.PL

查看原文摘要

Modern artificial intelligence models are deployed on inference engines to optimize runtime efficiency and resource allocation, particularly for transformer-based large language models. The vLLM project is a major open-source library to support model serving and inference. However, the current implementation of vLLM limits programmability of the internal states of deployed models. This prevents the use of popular test-time model alignment and enhancement methods. For example, it prevents the detection of adversarial prompts based on attention patterns or the adjustment of model responses based on activation steering. To bridge this critical gap, we present vLLM Hook, an opensource plug-in to enable the programming of internal states for vLLM models. Based on a configuration file specifying which internal states to capture, vLLM Hook provides seamless integration to vLLM and supports two essential features: passive programming and active programming. For passive programming, vLLM Hook probes the selected internal states for subsequent analysis, while keeping the model generation intact. For active programming, vLLM Hook enables efficient intervention of model generation by altering the selected internal states. In version 1 (named vLLM Hook MIA), the plugin runs on vLLM's V2 model runner and preserves the engine's CUDA graphs, so that capturing and steering internal states incurs only a small decoding overhead. It supports both offline use and serving through vllm serve. In addition to presenting the core functions of vLLM Hook, we demonstrate use cases including prompt injection detection, attention-based re-ranking for retrieval-augmented generation, activation steering, hidden-state probing, hallucination detection, schema linking for text-to-SQL, and tool-call risk assessment. Finally, we welcome the community's contribution to improve vLLM Hook via https://github.com/IBM/vLLM-Hook.

新论文 · v1arXiv:2611.05263

JHiMA-WebRL:面向长程网页任务的联合分层多智能体强化学习框架

JHiMA-WebRL: A Joint Hierarchical Multi-Agent Reinforcement Learning Framework for Long-Horizon Web Tasks

Shanka Subhra Mondal, Jiayun Wang

AI 速读 基于摘要

作者提出将任务分解器与执行器联合训练的分层多智能体强化学习框架,并在 WebArena 环境中验证其长程网页导航效果。

cs.AI

查看原文摘要

Multimodal web agents have shown promising capabilities for interacting with websites through graphical user interfaces (GUIs), yet realistic web tasks often require long-horizon, multi-step planning that remains challenging for monolithic policies. Such agents must jointly infer high-level plans, navigate through intermediate states, track progress over extended interaction histories, and execute visually grounded actions. Although prior work has explored modular multi-agent systems with a separate planner, the planner is typically not updated jointly with the actor. We investigate whether explicitly separating and jointly training planning and execution provides a stronger inductive bias for long-horizon web navigation. We introduce JHiMA-WebRL, a joint hierarchical multi-agent reinforcement learning framework for web agents that couples a task decomposer with an actor. To train the decomposer, we use a strong teacher model to construct structured subtask supervision from multimodal GUI trajectories, and use these annotations to fine-tune both the decomposer and the subtask-conditioned actor. We then extend Group Relative Policy Optimization (GRPO) to jointly optimize the decomposer and actor in the interactive WebArena environment through hierarchical rollout grouping and role-specific advantages. On WebArena-Lite-v2, JHiMA-WebRL-14B, consisting of a 7B actor and a 7B decomposer, achieves an average success rate of 37.2%, compared with 24% for a ScaleCUA-32B agent that we fine-tune with RL on the same training tasks and evaluate under the same protocol. Ablations show that jointly updating the decomposer during RL outperforms updating the actor alone. These results suggest that jointly learned role factorization with smaller models can be a competitive alternative to scaling monolithic agents for long-horizon web tasks.

新论文 · v1arXiv:2611.05260

NovoCRF:基于前缀质量格的全归一化从头肽段测序

NovoCRF: Globally Normalized De Novo Peptide Sequencing on a Prefix-Mass Lattice

Rui Qiao, Lei Xin, Baozhen Shan

AI 速读 基于摘要

NovoCRF 将从头肽段测序建模为状态为前缀质量的 CRF,在所有质量可行肽段上做精确全局归一化训练,并报告了召回率与吞吐量优势。

cs.LG

查看原文摘要

De novo peptide sequencing has moved from dynamic programming over hand-designed or generative scores to large transformers that learn the task end to end. We present NovoCRF, a conditional random field (CRF) whose states are prefix masses, so that its paths are exactly the peptides within +/-0.06 Da of the precursor mass. A small network scores each edge from physics-derived ion-match features and is trained with its scores globally normalized over all mass-feasible peptides. To our knowledge, NovoCRF is the first de novo method trained with exact normalization over all mass-feasible peptides. Our software has three modules, each with exactly one job: a precursor mass finder recovers the accurate precursor mass from MS1, the CRF finds the peptides that fit the precursor mass by exact k-best decoding, and two BiGRU rerankers add sequence context and internal-fragment evidence. The model has 310k parameters and trains in about 17 GPU-hours. On seven held-out data-dependent acquisition datasets published in 2026 (126,262 labeled spectra), NovoCRF's mean peptide recall is 42.4%, against 39.1% for Casanovo v5 with five beams, and its amino-acid recall 64.0% against 53.1%, at 1,746 spectra/s on 18 CPU threads, 55x Casanovo's throughput on a GPU. Split by fragment evidence, NovoCRF leads on labels with up to three peptide bonds without a b or y ion, and Casanovo only beyond. NovoCRF can also search modifications it was never trained on at their exact mass: it finds 32.1% of the hydroxyproline peptides of a lion bone sample.

版本更新 · v2arXiv:2607.00861

TrajLoc:面向多目标运动控制的轨迹注意力定位

TrajLoc: Trajectory-Attention Localization for Multi-Object Motion Control

Omer Sela, Inbar Huberman-Spiegelglas, Michael Rotman, Sagie Benaim, Avi Ben-Cohen

AI 速读 基于摘要

TrajLoc 通过在注意力层中为每个对象 token 注入以目标位置为中心的高斯热图,实现图像到视频生成中多对象轨迹的独立空间约束。

cs.CV · cs.GR

查看原文摘要

Controlling the motion of multiple objects in image-to-video (I2V) generation requires preserving object identities while enforcing adherence to distinct target trajectories. This becomes particularly challenging as the number of objects increases and their paths intersect or occlude one another. Existing approaches entangle multiple trajectories within a shared, dense conditioning signal, making object-level correspondence difficult to preserve in crowded scenes. We depart from this paradigm and enforce a strict, per object spatial constraint that isolates instances independently. Our method, TrajLoc, achieves this directly within the attention layers by substituting the cross-attention weights of each object token with a Gaussian heatmap centered on its target location at every frame. The same per object token interface carries trajectory and depth through a learned embedding and preserves identity by encoding first frame appearance in place of an object token. Evaluations across six datasets, featuring up to 20 simultaneously controlled objects and out of distribution real world scenes, demonstrate that our method consistently improves both visual fidelity and trajectory adherence. Applied to two architecturally distinct backbones (CogVideoX 5B and WaN 2.1 14B), our approach achieves average gains of +4.3 dB PSNR and a 51% reduction in trajectory end point error compared to the strongest baselines. Project page: https://sela-omer.github.io/traj-loc/

新论文 · v1arXiv:2611.05257

失真的计算方面

Computational Aspects of Distortion

Soroush Ebadian, Aris Filos-Ratsikas, Mohamad Latifian, Nisarg Shah

AI 速读 基于摘要

该论文为社会选择中的失真框架提出基于线性规划的最优随机决策算法,以及基于非凸二次规划计算随机位置评分规则精确失真的方法。

cs.GT

查看原文摘要

The distortion framework in social choice theory allows quantifying the efficiency of (randomized) selection of an alternative based on the preferences of a set of agents. We make two fundamental contributions to this framework. First, we develop a linear-programming-based algorithm for computing the optimal randomized decision on a given instance, which is simpler and faster than the state-of-the-art solutions. For practitioners who may prefer to deploy a classical decision-making rule over the aforementioned optimal rule, we develop an algorithm based on non-convex quadratic programming for computing the exact distortion of any (and the best) randomized positional scoring rule. For a small number of alternatives, we find that the exact distortion bounds are significantly better than the asymptotic upper bounds established in prior literature and lead to different recommendations on which rules to use. These results rely on a novel characterization of the instances yielding the worst distortion, which may be of independent interest.

新论文 · v1arXiv:2611.05255

深入记忆:DeepMem 因果多尺度字节级语言模型

Going Deeper With Memories

Afshin Khadangi

AI 速读 基于摘要

DeepMem 通过可逆子带变换与快权重记忆,把语义压缩与字节精确保留分离,在字节级语言建模上取得优于匹配 Transformer 的表现。

cs.LG · cs.AI

查看原文摘要

Byte level language models avoid tokenizer dependence and provide universal coverage, but processing every byte at full resolution is expensive. We introduce DeepMem, a causal multiscale architecture that separates semantic compression from exact byte preservation. A learned invertible subband transform constructs a hierarchy of shorter sequences, while a lossless carrier and explicit detail sidebands preserve byte identity. Fast weight memory blocks operate along the encoder, with iterative shared state computation at the compressed bottleneck, while an attention based super resolution decoder restores byte resolution representations. DeepMem achieves stronger language modeling performance than a matched byte level Transformer on FineWeb-Edu and PG19, and obtains the best macro average performance across the evaluated FLORES languages. It also improves PIQA accuracy while remaining competitive on code modeling, multiple choice reasoning, and byte level corruption robustness. Bottleneck refinement requires approximately $7{,}600\times$ fewer counted FLOPs than equivalent full resolution reasoning, while maintaining competitive evaluation throughput.

新论文 · v1arXiv:2611.05252

基于遍历马尔可夫链的可解释社交网络流失预测

Interpretable Social Network Churn Prediction via Ergodic Markov Chains

Matthew McQuistion, Siddhartha Sharan, Afia Zaheer

AI 速读 基于摘要

作者提出一种无需标签、仅依赖SQL的Health Ratio指标,通过贡献者角色马尔可夫链的有限步参与度投影来预测社交网络流失。

stat.AP · cs.SI

查看原文摘要

Predicting social network churn before it becomes visible in aggregate metrics remains an open challenge, particularly in enterprise settings where heterogeneous usage patterns, sparse data, and deployment constraints preclude standard supervised approaches. We formalize this problem as finite-step engagement projection over contributor-role Markov chains, with a stationary-distribution interpretation for ergodic chains in the long-run limit. For each engagement feature type within a network (e.g., Q&A, communities, articles, etc.), users are classified monthly into four behavioral states and a transition matrix is estimated from six months of history. Six-step propagation yields a label-free projection of the contributor mix; for ergodic chains, the Perron-Frobenius theorem establishes convergence under repeated propagation. Comparing projected future engagement to current engagement produces the Health Ratio, a single score requiring no trained model, no labels, and no infrastructure beyond SQL. Validated across seven rolling prediction windows on 11,500+ tenant-level networks, the Health Ratio achieves mean AUC 0.917 with a 156 times churn-rate gradient across risk tiers, outperforming all single-signal baselines and the growth-adjusted variant previously deployed in production. An ablation study shows that six-step propagation achieves similar churn discrimination to the eigenvector-based score. Deployed on Microsoft Engage since October 2025, the framework powers customer health monitoring and has enabled proactive intervention on at-risk networks before decline becomes visible in traditional metrics.

版本更新 · v2arXiv:2610.32024

BARC-Bench:良性请求,风险后果

BARC-Bench: Benign Asks, Risky Consequences

Kangkang Li, Kelvin Luu, Lily Ma, Tu Trinh, Ying Liu, Mohamed Elfeki

AI 速读 基于摘要

作者提出 BARC-Bench 基准,用 110 个表面良性但暗含安全边界的任务,评估智能体在欠指定指令下是否会越界。

cs.AI

查看原文摘要

Task instructions from users for agents are inherently underspecified, especially regarding safety boundaries--creating behavioral risks. To study these risks, we introduce BARC-Bench, a collection of 110 tasks across nine simulated workspace environments where benign requests leave openings for unsafe actions. In this benchmark, we evaluate agent behavior against safety boundaries established by workspace records, implicit environmental context, and unstated social norms. For example, an agent asked to schedule off-boarding discussions must arrange the meeting without prematurely revealing an employee's resignation through a shared calendar invitation. Evaluating four frontier model configurations across five attempts per task reveals that models are not consistently safe: the share of tasks completed safely on all five attempts ranges from 9.1% to 72.7%, with even the strongest configuration producing a safety violation on 27.3% of tasks. These results highlight an asymmetric operational risk: while models frequently complete complex workflows, their inability to consistently respect unstated boundaries presents a substantial barrier to safe autonomous delegation.

新论文 · v1arXiv:2611.05250

线性代数原理的平方和复杂度

The sum-of-squares complexity of linear-algebraic principles

Dmitriy Kunisky, Xifan Yu

AI 速读 基于摘要

本文研究了实线性代数中若干基本原理的平方和(SoS)证明所需度数,给出了弱秩原理等问题的精确度数下界与上界。

cs.CC

查看原文摘要

We study the degree needed for sum-of-squares (SoS) proofs of several basic principles of real linear algebra. For any $n\times n$ matrix $A$ of rank greater than $r$, the Weak Rank Principle states that the equations $XY^\top=A$ with $n\times r$ matrix variables $X, Y$ have no solution. We show that this principle requires degree exactly $2r+2$ to prove. On the other hand, for $A=I_n$, setting $X = Y$ gives the Tight Frame Principle, which has a degree-$4$ proof. For $n\times n$ matrices, proving that a right inverse is also a left inverse requires degree exactly $2n+2$, while proving that orthonormal rows imply orthonormal columns again has a degree-4 proof. Using our lower bounds, we also derive related SoS degree lower bounds for polynomial systems encoding sign rank, matrix rigidity, small-width homogeneous non-commutative algebraic branching programs, and tensor CP rank. Lastly, we show that quantitative bounds on the Frobenius norms of the factors in the Weak Rank Principle can lower the degree required to refute $XY^\top=I_n$, but sufficiently large bounds still preserve the exact degree $2r+2$ from the unbounded case, giving a quantitative version of the Archimedean property arising in classical results on SoS proofs.

新论文 · v1arXiv:2611.05249

动作专家该训练VLM吗?混合Transformer VLA中的动作Token监督与梯度路由

Should the Action Expert Train the VLM? Action-Token Supervision and Gradient Routing in Mixture-of-Transformer VLAs

Asher James Hancock, Boyi Li, Yuxiao Chen, Shuhan Tan, Wenhao Ding, Thomas Tian, Yan Wang, Boris Ivanovic 等 9 位作者

AI 速读 基于摘要

该研究在自动驾驶与机器人操作中解耦动作Token监督和专家到VLM的梯度耦合,考察梯度隔离是否仍是VLA训练的合理默认。

cs.RO

查看原文摘要

Vision-language-action (VLA) models increasingly pair a pre-trained vision-language model (VLM) with a flow-matching expert that conditions its action predictions on the VLM's key-value representations. Those representations must carry information useful for control, yet the VLM was never trained for the action expert's flow-matching objective. Two signals can address this: gradients backpropagated from the expert's loss (coupling), or VLM supervision to predict discrete tokens encoding the same target actions. Prominent training recipes forgo the first, blocking expert-to-VLM gradients (insulation) to protect the VLM's existing capabilities, while also supervising it on vision-language data and action tokens. Because vision-language co-training also aims to preserve those capabilities, the additional protection provided by insulation is unclear. At the same time, insulation removes a direct signal about which features continuous action prediction requires. On the other hand, action-token supervision offers an alternative way to learn action-relevant representations, which may explain why insulation succeeds in practice. We disentangle these factors in autonomous driving and manipulation by independently varying action-token supervision and whether the expert's loss updates the VLM. In open-loop driving, insulation is competitive with coupling when action tokens are supervised; without them, coupling reduces trajectory-prediction error by roughly 25%. When both components are trained jointly from the outset, coupling increases closed-loop driving route progress by approximately 17% with action-token supervision and 40% without it, and similarly improves robot manipulation performance under both settings. These findings show that the value of gradient insulation depends on the VLM's action supervision and the evaluation setting, challenging insulation as a default VLA training recipe.

版本更新 · v4arXiv:2608.04228

拓扑计算路径:表示不变性与可观测商

Topological Computational Paths: Presentation Invariance and Observable Quotients

Arthur Freitas Ramos, Ruy J. G. B. de Queiroz, Anjolina Grisi de Oliveira, Tiago M. L. de Veras

AI 速读 基于摘要

研究有限计算路径的连续表示,比较保留完整带符号轨迹的拓扑与仅记录端点、长度和精确路径实现的可观测拓扑,并分析二者在表示不变性下的差异。

cs.LO · math.AT

查看原文摘要

A computational path records the steps used to establish an equality. Topologies on computational equality witnesses can depend on the chosen generators and execution schedule, even when their algebraic and homotopical meanings agree. We study continuous presentations of finite computational paths whose declared rewrites are realized by endpoint-fixed homotopies. We compare a topology retaining the full signed trace with an observable topology recording endpoints, length, and exact path realization. Continuous finite-word interpretations that are inverse up to scoped rewriting preserve trace-sensitive quotient arrows and their final composable-pair spaces. Observable quotients behave differently. Over a point with a nonempty primitive alphabet, we classify their topology: it records length parity when all named relations preserve parity, and is otherwise indiscrete. Adjoining a conservative abbreviation can therefore turn a discrete two-element quotient into an indiscrete space, even though ordinary multiplication remains continuous. A circle presentation also gives nonhomeomorphic quotients under binary and equal-slot timing. Geometric completeness alone does not identify the trace-sensitive and observable topologies. Multiplication is continuous on the quotient of composable representatives. We characterize when this topology agrees with the ordinary pullback topology and give an open-projection criterion. Universal presentations recover classical fundamental-groupoid topology. Normal forms, primitive interchange, and a Cayley covering prove completeness for circle, torus, product, and rose presentations. A literal-word correspondence relates the semantics to the reflexivity, symmetry, and transitivity fragment of equality derivations. Selected results are formalized in Lean, with the realization models and proof coverage stated explicitly.

版本更新 · v2arXiv:2611.02174

超越单位圆特征值:稳定状态空间动力学的不变基

Beyond Unit-Circle Eigenvalues: Invariant Bases for Stable State Space Dynamics

Jiaqian Zhu, Yang Zhang, Junhua Ding, Xiaowei Yu

AI 速读 基于摘要

作者提出对角递推的守恒量具有分层结构,并通过Kronecker-Cayley变换按构造强制满足各层条件,以在训练前固定守恒量。

cs.LG

查看原文摘要

Diagonal state space models process long sequences at linear cost, yet the same transition is applied at every step of a rollout, so an unconstrained recurrence holds no quantity fixed and the state decays or grows without bound. Current designs constrain one quantity, and preserving one does not guarantee preservation of the others, so a model can hold its norm to machine precision while momentum drifts by hundreds of percent. We claim that the conserved quantities of a diagonal recurrence are layered, that each layer requires a strictly stronger condition on the operator, and that a unit-modulus spectrum reaches only the outermost. Acting on the claim, we enforce the conditions required for every layer by construction. The generator of the Kronecker-Cayley transition (KC) is a graph Laplacian over object subspaces, $\mathbf{H}=\mathbf{L}\otimes I_m$, advanced by a Cayley transform, and the step stays diagonal at $O(N^3+N^2m)$ cost. The conserved set is exactly a $2m^2$-dimensional family of quadratic forms, held at every parameter value, so the quantities and the dynamics the construction reaches are fixed before training. On four conservation benchmarks, KC holds total mass at or near the reference floor while every diagonal baseline loses it by orders of magnitude. We further compare against mass correction and find that two correctors fail once the underlying prediction diverges, which shows that assembly rather than correction is necessary for a guarantee that holds across the rollout. A free modal basis trained under a conservation penalty conserves only by freezing its spectrum, whereas the assembled operator conserves with every mode but one free to rotate. Beyond these benchmarks, KC holds the linear momentum of three $N$-body systems and, at the operator level, the conserved quantity in molecular dynamics, chemical kinetics, pharmacokinetics and power-grid swing dynamics.

版本更新 · v2arXiv:2610.32670

任意范数下凸体追逐问题的线性下界

A Linear Lower Bound for Convex Body Chasing in Every Norm

Nicolas Christianson

AI 速读 基于摘要

作者证明在任意范数下,ℝ^d 中凸体追逐的竞争比存在 Ω(d) 下界,从而说明 Sellke 的 O(d) 算法渐近最优。

cs.DS · cs.CG · math.MG

查看原文摘要

We establish an $Ω(d)$ lower bound on the competitive ratio of convex body chasing in $\mathbb{R}^d$ with movement costs measured in any norm. Previously, the best known lower bound valid across all norms was $Ω(d^{1/6})$, established by Papazov (2023); stronger lower bounds were known for $\ell_p$ norms, where Bubeck, Klartag, Lee, Li, and Sellke (2019) had established a lower bound of $Ω(\max\{\sqrt{d}, d^{1-1/p}\})$. In particular, a linear lower bound was known only for the $\ell_\infty$ norm, realized by the standard construction of chasing faces of a hypercube. Our lower bound strictly improves on the prior universal and $\ell_p$ lower bounds for $p < \infty$ and shows that the functional Steiner point algorithm of Sellke (2023) - which has competitive ratio $O(d)$ - is asymptotically optimal for every norm. Our approach is based on the recursive construction of Bubeck, Coester, and Rabani (2023) for metrical service systems, which gives a lower bound of $Ω(r^2)$ for requests of size $O(r)$. We show that requests in their construction, each comprising a set of discrete points in a graph metric, can be mapped to the vertices of convex requests in a $(2r+1)$-dimensional $\ell_p$ vector space while approximately preserving movement costs up to a factor of $O(r)$; the general result then follows via Milman's (1985) quotient-of-a-subspace theorem.

版本更新 · v2arXiv:2611.02335

基于归因的单细胞基础模型诊断

Attribution-based diagnostics for single-cell foundation models

Farnoush Rezaei Jafari, Tristan Lazard, Kenza Bouzid, Shruthi Bannur, Jeremiah Wander, Ashley Mae Conard, Stephanie Hyland, Lorin Crawford 等 9 位作者

AI 速读 基于摘要

该研究系统评估了事后归因方法在单细胞基础模型下游预测诊断中的价值与陷阱。

cs.LG · q-bio.QM

查看原文摘要

Single-cell RNA foundation models (scFMs) are increasingly used for in-silico biological discovery, yet predictive performance alone does not reveal whether their decisions rely on biologically meaningful signals or model-specific shortcuts. We systematically investigate post-hoc attribution of downstream predictions across two tasks: cell-type annotation using pretrained Cell2Sentence and scGPT models, and perturbation prediction using scGPT+STATE in a controlled setting. For cell annotation, we use attribution to assess whether predictions rely on established marker genes and how their relevance varies with model architecture, expression rank, and the surrounding cellular context. For perturbation prediction, we compare attribution patterns with known regulatory ground-truth in a synthetic setting to assess what they reveal about the model's learned computations. Across these tasks, attribution reveals biological feature use, contextual interactions, contributions from different input pathways, learning progression, associations with prediction quality, and potential pitfalls that are not fully captured by standard performance metrics. Experiments with complete and limited regulatory knowledge further demonstrate that conclusions drawn from attribution depend strongly on the choice of biological reference, baseline, and null model. Together, these findings highlight the value of attribution as a flexible post-hoc diagnostic for understanding model behavior, identifying potential issues, and informing the development of scFMs.

新论文 · v1arXiv:2611.05446

A Fully Polynomial Approximation Algorithm for the Sherrington-Kirkpatrick Model

Dylan Herman, Shouvanik Chakrabarti, Junhyung Lyle Kim, Guneykan Ozgul

原文摘要

Montanari's incremental approximate message passing (IAMP) algorithm [FOCS 2019; SIAM J. Comput., 2025] and the zero-temperature formulation of El Alaoui, Montanari and Sellke (AMS) [Ann. Probab., 2021] find a $(1-\varepsilon)$ approximation to the maximum Sherrington-Kirkpatrick (SK) energy in $C(\varepsilon)N^2$ operations for fixed accuracy, with probability tending to one as $N\to\infty$, under their respective full-support and access-model assumptions. However, it was unknown whether this approximation could be achieved with work polynomial in both $N$ and $1/\varepsilon$, together with quantitative guarantees at finite dimension. Under the same assumptions as AMS, we introduce grouped IAMP with exact Gaussian query outputs (GEG-IAMP), which is the first SK approximation algorithm with total work polynomial in $N$ and $1/\varepsilon$ and a finite-size guarantee above a dimension threshold polynomial in $1/\varepsilon$ and $\log(1/α)$. More precisely, for every $α\in(0,1/2)$, it returns a $(1-\varepsilon)$ approximation with probability at least $1-α$ whenever $N\ge \mathsf{K}\varepsilon^{-2}\log^2(e/\varepsilon)\log(\mathsf{K}/α)$, using $O(N^2/\varepsilon)$ work and $O(N^2)$ storage. GEG-IAMP replaces the Onsager correction by Reeves's coupling construction [arXiv:2508.10782] and groups Euler-Maruyama steps into $O(1/\varepsilon)$ matrix-vector products. We also prove a relative guarantee for AMS IAMP with $O(N^2\varepsilon^{-3}\log^2(e/\varepsilon))$ work but a sufficient dimension exponential in inverse accuracy. By returning a fixed configuration below its dimension threshold, GEG-IAMP also provides an asymptotic fully polynomial randomized approximation scheme (AFPRAS), with an additive error independent of dimension.

cs.DS · cond-mat.stat-mech · math.OC · math.PR · quant-ph

版本更新 · v2arXiv:2610.37863

DropFENO:面向混合润湿图案表面液滴平衡的无数据、基于物理的算子学习框架

DropFENO: A Data-Free, Physics-Based Operator-Learning Framework for Droplet Equilibria on Mixed-Wettability Patterned Surfaces

Ganesh Sahadeo Meshram, Partha Pratim Chakrabarti, Suman Chakraborty

AI 速读 基于摘要

作者提出仅从自由能出发、无需解数据的神经算子框架 DropFENO,用于学习化学图案壁面上液滴的平衡态与毛细力。

cs.CE

查看原文摘要

We study whether the equilibrium of a drop on a chemically patterned wall, and the capillary forces that the pattern exerts on it, can be learned from the free energy alone, without solution data. We introduce DropFENO (Droplet Free-Energy Neural Operator), in which Fourier (FNO), tensor-factorised Fourier (TFNO) and wavelet (WNO) neural operators are trained in two and three dimensions on the diffuse-interface free energy of the drop, with its volume and centroid constraints imposed as penalties. The predictions are tested with the virtual-work (Hellmann--Feynman) theorem: the force exerted by the pattern on a held drop is a wall integral of the equilibrium field which, for a drop straddling a wettability step, reduces identically to the contact-line law $F=σΔ\cosθ\,L$. DropFENO reproduces this law and the energy landscape of a drop crossing a step, and reproduces the pinning of the receding contact line less accurately. The residual error lies in the soft modes of the capillary energy (small displacements of the interface and the contact line). This explains why the energy is predicted accurately while contact-line positions are not, and why on striped walls the operators return Cassie-like states instead of the edge-pinned states whose anisotropic apparent angles the reference minimiser shares with lattice Boltzmann simulations. On held-out patterned walls the median energy of the predictions lies $\NdEmedRandFnoTwo$ of the free-drop energy above the best known minimum (FNO, two dimensions), at about one hundredth of the cost of a per-instance minimisation, and a refinement by a classical solver started from the prediction returns the reference state in almost all cases.

新论文 · v1arXiv:2611.05243

交替镜像下降的对数遗憾界

Logarithmic Regret for Alternating Mirror Descent

Tianlong Nan, Christian Kroer

AI 速读 基于摘要

作者报告交替在线镜像下降(AltOMD)在两人零和双线性博弈中可达到 O(log T) 的外部遗憾和,从而正面回答其是否具有近常数遗憾的开放问题。

cs.LG · cs.GT · math.OC · stat.ML

查看原文摘要

Alternating online mirror descent (AltOMD) is a simple learning rule for zero-sum games, which improves upon simultaneous OMD numerically and theoretically. Previous work obtained $O(T^{1/3})$ and $O(T^{1/5})$ regret bounds for AltOMD, by leveraging modified-energy-function-based analyses. However, settling whether AltOMD achieves near-constant regret has remained an open question. In this paper we resolve the question of whether AltOMD achieves near-constant regret in the affirmative. In particular, we show an $O(log(T))$ regret bound on the sum of the players' external regrets for any two-player zero-sum bilinear game with compact convex strategy sets, under mild regularity assumptions on the regularizers. We verify that our assumptions hold for the negative entropy regularizer, thereby obtaining logarithmic regret for the alternating multiplicative weights updates algorithm. The regret bound also yields an $O(log(T)/T)$ duality gap bound for the averaged strategies.

新论文 · v1arXiv:2611.05241

隐式生成模型的收缩先验

Shrinkage prior for implicit generative models

Shreya Sinha-Roy, Christian P. Robert, Ritabrata Dutta

AI 速读 基于摘要

作者提出一种基于收缩先验与广义贝叶斯的样本高效训练机制,用于隐式生成模型,并在高维小样本场景下探索稀疏表示。

cs.LG · stat.CO

查看原文摘要

Implicit generative models based on deep neural networks have revolutionized many scientific fields, from weather research to language generation. They successfully model complex random objects arising in real-world problems. In this work, we propose a sample-efficient training mechanism for these models. Our approach leverages regularized inference with shrinkage priors and generalized Bayes. In the large $p$ (parameter dimension) and small $n$ (sample size) setting, sparsity-inducing priors have been successfully used for linear regression when $p \gg n$. However, their application to implicit generative models remains challenging due to the intractability of the likelihood function. To address this, we adapt a scoring rule posterior based on a strictly proper scoring rule, following the generalized Bayes framework. We then propose a block SGMCMC within Gibbs sampling mechanism. This enables efficient exploration of high-dimensional parameter spaces by identifying a sparse representation of neural implicit generative models. We demonstrate the performance of our proposed method through experiments on $p \gg n$ linear regression and an application of neural generative models.

新论文 · v1arXiv:2611.05238

后分层重要性采样

Post-stratified importance sampling

Yuling Yao, Sergei Tikhonov

AI 速读 基于摘要

借鉴调查抽样中的多层回归与后分层(MRP)思想,将高维重要性加权拆解为两个一维建模问题,提出后分层重要性采样(PIS)以改善估计精度与不确定性量化。

stat.ME · cs.LG · stat.CO

查看原文摘要

Importance sampling is a building block of modern statistical computing, but the weighted estimate is prone to high or infinite variance. Moreover, its empirical standard error is often unreliable, leaving importance sampling without practical uncertainty quantification. Motivated by multilevel regression and poststratification (MRP) in survey sampling, we propose post-stratified importance sampling (PIS) for estimating target expectations from proposal draws. PIS reformulates arbitrarily high-dimensional weighting into two one-dimensional probabilistic modeling problems: regression for the conditional mean given the importance ratio and marginal density estimation for the importance ratio. Different modeling choices yield a family of PIS estimators, encompassing ordinary importance sampling as a special case. We develop a model-based implementation that combines one-dimensional Gaussian process regression for the conditional mean and score-informed heavy-tailed density estimation for the marginal law, using both the observed weights and the available density evaluations. We study the oracle gains of PIS and establish consistency under general and model-specific conditions. Simulations and applications to cross-validation demonstrate improvements in estimation accuracy and uncertainty quantification.

版本更新 · v2arXiv:2604.14993

服务具有大内存足迹的链式结构作业:面向大型基础模型服务

Serving Chain-structured Jobs with Large Memory Footprints with Application to Large Foundation Model Serving

Tingyang Sun, Ting He, I-Hong Hou

AI 速读 基于摘要

针对大内存足迹的链式结构作业服务,提出“服务器链组合”问题,通过块放置与缓存分配建模流水线并行下的大模型服务,并给出可扩展且具性能保证的算法。

cs.DC · cs.PF

查看原文摘要

As a current trend in Artificial Intelligence (AI), large foundation models are increasingly employed as the core of AI services. However, even after training, serving such models at scale remains a challenging task due to their heavy resource footprints, particularly in terms of GPU memory. While recent works revealed unique characteristics of systems serving foundation models that distinguish them from traditional distributed computing systems, there is still a lack of fundamental understanding of the underlying system management problems. This work aims at addressing this gap by extracting a novel problem of "server chain composition" via block placement and cache allocation for serving chainstructured jobs with large memory footprints, which models a fundamental problem in serving large foundation models through pipeline parallelism. After showing the NP-hardness of the optimal solution, the focus is turned to developing scalable algorithms with guaranteed performance under state-of-the-art load balancing. Application of the proposed solution to a distributed large language model (LLM) serving system shows significant reduction of response times compared to state-of-the-art solutions.

新论文 · v1arXiv:2611.05235

Catalan 哈希:面向变长元素的高效线性探测

Catalan Hashing: Efficient Linear Probing for Variable-Length Items

Alex Conway, Hanna Komlós, William Kuszmaul

AI 速读 基于摘要

提出 Catalan hashing,在存储任意长度元素的线性探测哈希表中,将扫描代价控制在接近单位长度情形的量级。

cs.DS

查看原文摘要

A defining feature of the linear-probing hash table is its spatial locality: at load factor $1 - \varepsilon$, the hash table can be implemented so that each operation scans a single contiguous region of expected size $O(1/\varepsilon)$ (this is known as the \emph{scan cost}). This guarantee, however, relies on all items having unit size. In this paper, we ask whether it is possible to achieve a similar guarantee, but in a hash table that stores items of arbitrary lengths $|x| \ge 1$. The main result of the paper is a new hash table called \emph{Catalan hashing}, which supports amortized expected scan cost $O(|x|/\varepsilon)$ for positive queries, $O(1/\varepsilon)$ for negative queries, and $O(|x|\varepsilon^{-1}\log^{1+δ}|x|)$ for insertions/deletions, for any constant $δ> 0$. As a corollary, we obtain the same bounds in the cache-oblivious model, with a scan cost of $S$ translating to $1 + O(S/B)$ I/Os. Along the way, we introduce several high-level techniques that may be of independent interest; this includes a novel way of using erasure codes in order to perform write optimization within a hash table, and a connection to scheduling that allows us to place elements in a way which avoids clustering at high load factors.