由于微信公众号开始试行乱序推送，为了让您在第一时间获取AI新文，请将"AI新文"设为星标。
平面外图的内部凸绘制（小区域）
原标题：Internally-Convex Drawings of Outerplanar Graphs in Small Area
作者：Michael A. Bekos; Giordano Da Lozzo; Fabrizio Frati; Giuseppe Liotta; Antonios Symvonis
期刊：arXiv每日人工精选
出版时间：2026/07/20
摘要：一个由Kant[Algorithmica, 1996]所知的结果表明，具有n个顶点的外平面图可以嵌入保持平面直线网格绘制中，其中内部面是凸多边形，并且需要O(n2)面积。在本文中，我们提出了一种在O(n1.5)面积内计算此类绘制的算法。我们也考虑了外部平面绘制，在这种绘制中，内部面被要求是严格的凸多边形。在这一设定中，我们为弱对偶是路径且最大面大小为k的n顶点外平面图提供了一个Θ(nk2)面积界，并为直径受d限制的n顶点外平面图提供了一个Θ(nd2)面积界。
原文链接
物理智能的热力学极限
原标题：Thermodynamic Limits of Physical Intelligence
作者：Koichi Takahashi; Yusuke Hayashi
期刊：arXiv每日人工精选
出版时间：2026/07/19
摘要：现代人工智能系统以巨大的能耗为代价实现了卓越的能力。为了将智能与物理效率联系起来，我们提出了两种互补的比特每焦耳度量标准，在明确的会计惯例下：(1) 焦耳每热力学表征度，代理状态中关于指定环境实例变量的新结构比特数每单位能量编码，和(2) 每焦耳赋能，固定时间范围内预期能量成本上的感觉运动信道容量。这给出了物理智能的两个轴，识别与控制之间的对比，但是得到的结果是相对于基准而言的，而不是普遍适用的。基于随机热力学，我们将热力学学习不等式与数据处理相结合，制定了一个兰道尔尺度封闭循环基准，用于研究偶联性获取，并阐明了为什么需要边界闭合；相反，通过去耦构造表明，在没有这些假设的情况下，信息增益和内部耗散不一定紧密相关。对于潜在结构变量不可用的经验设置，我们建议使用计算受限的MDL复杂度/压缩收益替代方法。最后，我们提出了一种统一的效率框架，包含最少的相对比特每焦耳比较约定清单，并给出一个紧凑的语言模型报告示例。
原文链接
前瞻分支用于神经网络验证
原标题：Lookahead Branching for Neural Network Verification
作者：Liam Davis; Duo Zhou; Huan Zhang; Guy Katz; Clark Barrett; Haoze Wu
期刊：arXiv每日人工精选
出版时间：2026/07/19
摘要：在这项工作中，我们研究了前瞻分支策略在神经网络验证中的影响。我们提出了一种将前瞻功能集成到任意分支定界验证器中的通用方法，并展示了当前最先进的分支启发式算法之一FSB可以被视为前瞻分支策略的一种特殊实例化形式。我们还描述了如何在提高分支决策质量的同时，lookahead 可以生成额外的公理，从而加速验证过程。我们将该方法实例化为两个具有代表性的分支定界验证器（Marabou和α-β-CROWN），并证明前瞻法导致验证时间的一致加速，并且最多可解决多达57％更多的实例。代码可在https://github.com/ai-ar-research/lookahead-branching获得。
原文链接
具有结构化约束的不可分割物品的时间公平分配
原标题：Temporal Fair Division of Indivisible Goods with Structured Constraints
作者：Kui-Wang Choi; Minming Li
期刊：arXiv每日人工精选
出版时间：2026/07/19
摘要：本文研究了时间公平分配，在这种情况下，物品在多轮中进行分配，并且代理方需要随时间累积的公平性。我们关注经典公平概念的动态扩展：时序任意物品 envy-freeness（TEFX），其α-TEFX近似值，以及时序最大最小份额（TMMS）。由于这些严格的公平标准已知一般是无法满足的，我们在一定的约束条件下分析该模型，以确定可能与不可能之间的界限。我们的贡献系统地映射了这些时间公平概念的结构边界。我们主要的技术成果引入了一个新颖的动态回溯框架，实现了强二元估值的精确TEFX。我们通过字典序势函数论证证明，这种有界历史再分配系统地解决了时间嫉妒循环，并在有限时间内终止。最后，我们在相同估值和双值商品的情况下建立了α-TEFX的紧致近似比，并针对TEFX和TMMS提出了有针对性的不可能性结果，展示了时间公平性在数学上无法实现的确切位置，并恰当地重新定义了先前仅隐含满足我们新定义的TMMS度量标准的算法。
原文链接
因果马尔可夫条件（对于价值）
原标题：A Causal Markov Condition for Value
作者：Olav Benjamin Vassend
期刊：arXiv每日人工精选
出版时间：2026/07/18
摘要：本文提出了一种价值因果独立原则——价值因果马尔可夫条件（v-CMC），并构建了“因果价值理论”的概念和数学基础，该理论将因果关系和效用联系起来。在阐述v-CMC的局部表述之后，我们引入了一种概率值二元性，该二元性将标准因果推断结果转化为价值设定。特别地，我们提出了局部的、全局的以及分解版本的v-CMC，并证明了它们的等价性。我们也定义了v-分离，并证明它对条件值独立性是有效且完备的。此外，我们将v-CMC作为贝尔曼型递推的一种特例，从而将标准的贝尔曼递推从线性链推广到因果DAG。最后，我们展示了v-CMC如何支持因果情境间的效用信息的模块化转移和更新，并开发了用于因果结构化效用征询和规范影响图构建的算法。
原文链接
无模型先验自由能量估计器通过原则性方向无关内在动机
原标题：Principled Direction-Free Intrinsic Motivation through Model-Free Epistemic Free-Energy Estimators
作者：Alireza Furutanpey; Schahram Dustdar
期刊：arXiv每日人工精选
出版时间：2026/07/18
摘要：在具有混合不确定性来源的环境中，无监督强化学习需要内在动机，这种动机不会预先承诺于某种惊讶的方向。最小化惊喜的设计范围是``不稳定’’的环境。预测误差好奇心奖励总预期惊喜，包括不可约噪声。通过构造在最小化惊讶和最大化惊讶奖励之间切换的强盗或混合重新引入了非平稳性。我们提出了一种单一的内在奖励，在每个窗口内保持不变，该奖励源自无偏好的预期自由能量目标的新颖性贡献，以奖励最大化形式表达。我们的主张是参数信息增益，即下一个状态的预期惊喜减去其不可约部分，是状态空间中高熵和低熵组成部分中的适当内在信号。最大化它寻求模型能够解释掉的精确的惊喜。在动力学未解决的区域中，这一认识论术语推动了探索。随着动态得到解析，认识论术语消失，而概率论惩罚倾向于方差较低的过渡，所有这些都不需要拟合显式的下一个状态预测器。伪计数提供认识价值，基于探针的惩罚捕获随机变异性，并且短视门保护信息丰富的后续者。基于窗口的对所有定义奖励对象的冻结产生了一个稳定的贝尔曼算子，学习目标的具体界限，并在混合、平滑度、带宽和容量假设下，对于非参数估计器得到了条件均匀集中结果。在主动推理的术语中，代理人在保持新颖性的情况下是无偏好的，在完全可观察性下标准似然模糊消失，增加了非标准过渡熵惩罚，并且在状态空间解决区域中最小化惊讶出现。
原文链接
依赖信念的rho-POMDPs的预期自由能
原标题：Expected Free Energy as Belief-Dependent Utility for rho-POMDPs
作者：Patrick Cooper; Alvaro Velasquez
期刊：arXiv每日人工精选
出版时间：2026/07/18
摘要：在部分可观测性下行动的代理必须决定何时收集信息以及哪些观测值值得其成本。标准POMDPs仅通过其最终对奖励的影响来评估信息。ρ-POMDP框架通过依赖信念的效用函数ρ直接奖励不确定性减少，但在实践中，ρ的选择以及赋予它的权重都是针对每个任务手动调整的。我们表明主动推理完全消除了这种调节。最小化预期自由能(EFE)正好等同于求解一个ρ-POMDP，其效用是预期信息增益，并且探索权重固定在w=1，因为变分界表达了实用价值和认识价值在同一单位(nats)中。我们证明了这一等价性适用于观察后承诺的POMDP，并将其扩展到因子化观测的POMDP，这是一个更广泛的类别，涵盖了诸如非破坏性测试和移动传感之类的交错观察行动问题，在这些问题中收集信息不会改变隐藏状态。实验支持该理论。在从经典虎问题到RockSample以及一个新的具有超过65,000个状态的结构检查基准测试环境中，未经调整的权重匹配或优于相同时间范围内的仅奖励规划，在避免根据任务调整奖金导致过度探索的同时，接近成功与奖励之间的帕累托前沿的成功最大化拐点。实际收益是一个开箱即可使用的勘探目标。在诸如故障检测和医学筛查等应用中，在每次测试都有价格且每次漏检都有成本的情况下，EFE 提供一种基于信念的效用，这种效用是推导出来的而不是调整得来的。
原文链接
周期性自助汤普森采样在周期性非平稳多臂赌博机问题中的应用(Periodic Bootstrap Thompson Sampling For Periodically Non-Stationary Bandit Problems)
原标题：Periodic Bootstrap Thompson Sampling For Periodically Non-Stationary Bandit Problems
作者：Boning Shao
期刊：arXiv每日人工精选
出版时间：2026/07/18
摘要：本文介绍了周期性自助汤普森采样(PBTS)，这是一种经典汤普森采样(TS)算法的创新扩展，专门针对具有周期性非平稳性的多臂赌博机问题。传统的TS累积所有过去观测值，导致当奖励分布随时间循环时后验出现偏差。PBTS 通过将信念重置同步到已知或推断的周期间隔，并嵌入结构化的引导探索阶段来克服这一问题，从而在清除过时数据的同时保持不确定性估计。PBTS在人工构建的环境中进行了测试，这些环境包括偏斜和平衡的奖励分布，以及不同的自助法比例和周期性间隔不一致（不同）结果表明，在周期性非平稳环境中，PBTS 通常在累积遗憾方面实现了统计上显著的减少，相对于传统 TS。随后的讨论进一步阐述了PBTS实际部署的潜力。该研究提到了一些限制因素，如极端周期性错位，并提出了未来的研究方向，例如自适应周期识别。通过内存重置和引导阶段，PBTS 在周期性奖励环境中引入了一种优化.bandit算法的新方法。
原文链接
防止通过扩展到100万个并行环境来使PPO学习停滞
原标题：Preventing Learning Stagnation in PPO by Scaling to 1 Million Parallel Environments
作者：Michael Beukman; Khimya Khetarpal; Zeyu Zheng; Will Dabney; Jakob Foerster; Michael Dennis; Clare Lyle
期刊：arXiv每日人工精选
出版时间：2026/07/17
摘要：代理在深度有策略的强化学习中的表现停滞在一个次优水平是一个常见问题。专注于PPO，我们表明，在某些制度中出现的平台期并不是由于已知的探索、容量或优化挑战，而是因为在训练过程中基于样本的损失估计最终成为真正目标的不良代理。深入来看，PPO 在线交替从几个并行环境中使用当前策略采样轨迹（我们称之为“外循环”）和对这个离线数据集执行重复的小批量随机梯度下降步骤（“内循环”）。在我们的工作中，我们抽象掉了内部循环，并从概念上将外部循环建模为标准随机优化。步长通过正则化强度控制到先前策略的距离，而梯度噪声则由每次策略更新步骤之间收集的样本数量控制。这种框架预测到，就像在SGD中一样，如果外部步长相对于噪声过大，更新变得没有信息量，并导致策略在一个局部最优值周围徘徊而不是收敛。从这个角度重新审视PPO使得很清楚存在两种方式来应对这种特定类型的学习停滞：要么减小步长要么增加在更新之间的收集样本数量。我们验证了模型的预测，并得出结论：增加平行环境的数量是一种简单的方法，可以通过同时改变这两个因素来避免这些平台期。应用我们的分析并将PPO扩展到超过1M个并行环境能够实现性能的单调改进直至一万亿次转换，并在复杂的开放领域中相比之前的基准表现出显著优越的性能
原文链接
一种极其简单的优化大规模正交矩阵的方法
原标题：An Embarrassingly Simple Way to Optimize Orthogonal Matrices at Scale
作者：Adrián Javaloy; Antonio Vergari
期刊：arXiv每日人工精选
出版时间：2026/07/17
摘要：正交约束在鲁棒性和概率机器学习中普遍存在。不幸的是，当前的优化器计算成本高昂，并不能扩展到具有数百或数千个约束的问题。One 个值得注意的例外是Landing算法(Ablin et al. 2024)，然而这需要暂时放松正交性为代价。在这项工作中，我们重新审视并改进了Landing背后的理念，使现代自适应优化器能够被纳入，同时确保正交约束得到有效满足。这些改进几乎不增加成本，并且减少了所需的超参数数量。我们的算法POGO速度快且适合GPU，并仅包含5个矩阵乘积，在实践中始终维持正交性。在几个具有挑战性的基准测试中，POGO大大优于最近的优化器，并显示它可以几分钟内优化包含数千个正交矩阵的问题，而其他方法则需要数小时。因此，POGO 设立了一个里程碑，终于能够在大规模上利用正交性约束在机器学习中。POGO的PyTorch实现公开可用于https://github.com/adrianjav/pogo。
原文链接
下游预测的混合配置
原标题：Mixing Configurations for Downstream Prediction
作者：Juntang Wang; Hao Wu; Yihan Wang; Dongmian Zou; Shixin Xu
期刊：arXiv每日人工精选
出版时间：2026/07/17
摘要：基于聚类的特征在机器学习中被广泛使用，但大多数方法必须选择一个分辨率——这一选择是全局的、固定的、且随意的。最近的研究表明，改变分辨率参数只会产生一组有限的结构稳定的划分，称为配置。基于此，我们引入了配置混合预测（CMP），在这种设置中，模型学习为每个样本自适应地对这些配置进行加权，以便于后续预测。我们提出MixConfig，一个即插即用的特征增强模块，可以从任何冻结嵌入中提取配置，并通过一种新颖的选择器学习能量感知混合权重，该选择器综合考虑样本上下文、聚类分配和稳定性统计量。在表格、分子、视觉和文本领域进行的实验表明，在各种预测架构下，多分辨率和静态基准相比均有持续改进，在低数据环境中尤其明显。
原文链接
鲁棒滤波注意力：自注意力作为精度加权状态估计
原标题：Robust Filter Attention: Self-Attention as Precision-Weighted State Estimation
作者：Peter Racioppo
期刊：arXiv每日人工精选
出版时间：2026/07/16
摘要：我们引入了鲁棒滤波注意力（RFA），一种将自注意力表示为鲁棒状态估计器的公式化方法。每个标记都被视为受线性随机微分方程(SDE)支配的潜在轨迹的噪声观测值，注意力权重是根据该模型的一致性而不是静态特征相似性确定的。在各向同性噪声和衰减假设下，RFA 匹配标准注意力的计算复杂度。在语言模型基准测试中，RFA 在训练窗口内实现的困惑度低于 RoPE，同时在零样本外推到更长上下文时保持稳定。该框架还提供了标准位置机制的动态解释，将旋转嵌入和近期偏差与随机动力学引起的传输和不确定性传播联系起来。
原文链接
参数化排序的计算复杂性
原标题：Parameterized Complexity of Efficient Sortation
作者：Robert Ganian; Hung P. Hoang; Simon Wietheger
期刊：arXiv每日人工精选
出版时间：2026/07/16
摘要：在大规模物流网络的设计中，一个关键的挑战是优化包裹分类以进行路由。我们在这个问题的研究中采用了Van Dyk，Klause，Koenemann和Megow（IPCO 2024）最近提出的图论形式化方法。问题要求给定输入有向图D（the fulfillment network）以及一组表示为源汇对的商品集合——寻找D的传递闭包的一个最小出度子图H，使得对于每一种商品都包含一条从源到汇的路径。鉴于基本动机，我们研究了两种问题变体，它们的不同之处在于商品的路线是被假设已给定，还是可以任意选择。我们对这两个问题的复杂性进行了彻底的参数化分析。我们的结果集中在问题的三个基本参数化上：(1) 当试图通过H的目标出度进行参数化时，我们表明即使在高度受限的情况下，这些问题也是paraNP难解的；(2) 当通过商品的数量进行参数化时，我们利用Ramsey型论据和着色编码技术来获得两个问题的参数化算法；(3) 当通过D的结构进行参数化时，我们针对这两个问题建立了固定参数可处理性。树宽，最大度数和最大路由长度。我们将此与下界相结合，这些下界表明，缺少这三个参数中的任何一个会导致paraNP难问题。
原文链接
从第一步就预见终点：通过MLP稀疏感知截断加速扩散MLLMs
原标题：Seeing the End at Step Zero: Accelerating Diffusion MLLMs via MLP Sparsity-Aware Truncation
作者：Qicheng Zhao; Qi Sun; Zheyu Yan
期刊：arXiv每日人工精选
出版时间：2026/07/16
摘要：扩散多模态大型语言模型(DMLLMs)在多模态推理方面非常有效，但其推断效率因固定长度生成约束而受到显著阻碍。由于实际输出长度未知，输出序列被填充到一个预定义的最大长度，导致在不必要的[EOS]标记上进行大量的冗余计算。在这项工作中，我们发现DMLLMs在最初的去噪步骤中通过多层感知机激活稀疏性的明显变化隐含地揭示了其有效的语义边界。利用这一观察结果，我们提出了Seer，一个无需训练的框架，该框架使用基于信噪比(SNR)的标准检测此边界，并对所有后续计算执行一次性冗余后缀截断。为了在批量服务期间保持这些理论上的收益，Seer融合了一种混合执行策略，该策略在最大化吞吐量的同时无缝地适应动态序列长度。实验结果表明，Seer有效消除了填充浪费，使吞吐量提高了最多约31倍。在9个基准测试中，Seer稳健地保持了整体性能，并通过减少噪声泄漏（例如，DocVQA得分从63.52增加到63.66），甚至提高了复杂视觉任务的准确性，提供了一个高效的一键式解决方案以加速DMLLM。
原文链接
带口罩的策略梯度在扩散语言模型中的应用
原标题：Mask-Aware Policy Gradients for Diffusion Language Models
作者：Haran Raajesh; Kulin Shah; Adam Klivans; Philipp Krähenbühl
期刊：arXiv每日人工精选
出版时间：2026/07/16
摘要：强化学习已被证明可以提高大型语言模型中的推理能力，但由于对数似然估计的不可处理性，将其扩展到掩码扩散语言模型（MDLMs）仍然具有挑战性。现有方法通过仅建模令牌预测来近似这个对数似然，忽略在生成过程中位置被解掩码的顺序。我们观察到MDLM生成在每一步涉及两个决策：在每个掩码位置放置哪些标记以及重新掩码哪些位置。我们将此形式化为一个两阶段行动MDP，表明策略梯度自然分解为一个令牌项和一个掩码项。结合对两个方面的优化带来了数学推理和编码基准测试的最先进成果，在GSM8K上的得分为87.1%，在MBPP上的得分为53.4%
原文链接
理解grokking：岭回归中的可证明grokking
原标题：To Grok Grokking: Provable Grokking in Ridge Regression
作者：Mingyue Xu; Gal Vardi; Itay Safran
期刊：arXiv每日人工精选
出版时间：2026/07/16
摘要：我们研究grokking现象，在经典的岭回归设置中，这种现象是指在过拟合之后很久才出现的泛化能力的突然提升。我们证明了在使用带权重衰减的梯度下降学习过度参数化的线性回归模型时，端到端grokking的结果。我们证明了以下几个阶段会发生：(i) 模型在训练初期就开始过拟合训练数据；(ii) 在过拟合出现之后很长一段时间内，泛化性能仍然很差；(iii) 最终，泛化误差变得任意小。此外，我们从理论和实证两方面证明，通过适当的超参数调整，可以以一种原则性的方式放大或消除grokking现象。据我们所知，这些是首次以训练超参数形式对泛化延迟（which we refer to as the "grokking time"）进行严格的定量限制。最后，在线性设定之外，我们实证证明了我们的定量界限也能捕捉到grokking在非线性神经网络上的行为。我们的结果表明，grokking 并不是深度学习的固有失效模式，而是特定训练条件的结果，因此无需对模型架构或学习算法进行根本性的改变即可避免。
原文链接
隐藏的木偶大师：预测操纵性LLM对话中的人类信念变化
原标题：The Hidden Puppet Master: Predicting Human Belief Change in Manipulative LLM Dialogues
作者：Jocelyn Shen; Amina Luvsanchultem; Jessica Kim; Kynnedy Smith; Valdemar Danry; Kantwon Rogers; Hae Won Park; Maarten Sap; Cynthia Breazeal
期刊：arXiv每日人工精选
出版时间：2026/07/16
摘要：随着用户越来越多地转向大型语言模型寻求实用和个人建议，他们变得容易受到微妙的引导，从而走向与其自身利益不一致的隐藏激励。现有的自然语言处理研究已经对操纵检测进行了基准测试，但这些努力往往依赖于模拟辩论，并且从根本上与现实世界场景中实际的人类信念变化脱钩。我们介绍了PUPPET，这是一个理论分类学资源，通过关注日常建议情境中隐藏动机的道德方向来填补这一空白。我们提供了一个包含N=1,035个人与LLM交互的评估数据集，在其中我们测量了用户的信念变化。我们的分析揭示了当前安全范式中的一个关键断层：虽然模型可以被训练来检测操纵性策略，但它们并不与由此引起的观点变化程度相关联。因此，我们定义了信念转移预测任务，并表明虽然最先进的LLM达到了中等的相关性（r=0.3-0.5），但它们表现出系统性的方向偏差，有些模型过度预测而另一些模型则低估人类信念变化的幅度。本研究通过研究大型语言模型在日常实用用户查询中受激励驱动的操纵行为，建立了人工智能社会安全努力的理论基础和行为验证。
原文链接
单范式双范畴，微分线性逻辑和解析函子
原标题：Monoidal bicategories, differential linear logic, and analytic functors
作者：M. Fiore; N. Gambino; M. Hyland
期刊：arXiv每日人工精选
出版时间：2026/07/16
摘要：我们进一步发展了单范畴双范畴的理论，通过引入并研究线性指数余代数（在线性逻辑的研究中考虑过）以及导离变换（用于通过微分范畴来研究微分线性逻辑）在双范畴中的对应概念。作为应用，我们将Joyal的解析函子的微分演算扩展到预层范畴之间的解析函子，正如普通的微积分从单变量扩展到多变量一样。
原文链接
切换非平稳马尔可夫决策过程中的强化学习：算法及收敛性分析
原标题：Reinforcement Learning in Switching Non-Stationary Markov Decision Processes: Algorithms and Convergence Analysis
作者：Mohsen Amiri; Sindri Magnússon
期刊：arXiv每日人工精选
出版时间：2026/07/16
摘要：我们介绍了切换非平稳马尔可夫决策过程（SNS-MDP）框架，在该框架中，环境在由隐含马尔可夫链控制的有限个MDP集合之间转换，而智能体只能观察外部状态。我们表明，这种切换的长期效应等同于由隐马尔可夫链平稳分布参数化的平稳动力学。对于固定策略，我们推导出SNS价值函数的闭式表达式，并证明标准的时间差（TD）学习几乎可以肯定收敛到它，尽管存在持续的非平稳性。我们进一步证明策略迭代收敛到等效平均环境的最优策略，并证明表格Q学习几乎处处收敛到最优Q函数。该框架在一个具有马尔可夫信道噪声的无线通信网络上得到了验证，展示了其在快速时变系统中决策的实际有效性。
原文链接
拷贝写入评分：应用特定代理评估
原标题：Copy-on-Write Scoring: Application-Specific Agent Evaluations
作者：Joanna Roy; Sven Hoelzel
期刊：arXiv每日人工精选
出版时间：2026/07/15
摘要：值得信赖地在软件系统中部署基于LLM的代理需要评估它们在特定应用工作流中的表现，并且要足够详细以便定位它们成功和失败的地方。现有的智能体评估机制存在局限性：基准对于特定应用的工作流和环境构念效度低，并且复制评估环境成本高昂且容易出现漂移。我们提出Copy-on-Write (CoW) 评分，一个框架，它直接在应用环境中使用PostgreSQL级别的Copy-on-Write机制来隔离代理写操作来评估代理操作。CoW评分生成会话级和操作级分数，突出代理的数据库写入操作在给定的应用程序环境中成功和失败的位置，使代理捆绑包和工具界面的低成本评估和迭代成为可能。我们在Plane上展示了该框架，Plane是一个开源项目管理平台，在此分析揭示了工具界面中存在的具体问题，并且相应的修复措施对受影响的模型产生了可测量的改进。Python库：https://github.com/trail-ml/agent-cow-python
原文链接
