← 返回 PaperDaily 大模型与智能体

竞争比1/2+Θ(1/n)终被证明，算法竟出自LLM之手

这篇论文的价值不在结果本身，而在于过程：一位资深学者和ChatGPT来回讨论几个小时，就给一个悬而未决多年的在线算法问题画上了句号。算法本身只有三行伪代码，但背后是顶会级别的证明思路。对于关心“LLM到底能不能做科研”的读者，这是一份难得的真实样本。

龙哥读论文 阅读 3 查看原文
#AI科研 #人工智能
竞争比1/2+Θ(1/n)终被证明，算法竟出自LLM之手
原论文信息如下：
论文标题:
Asymptotically Tight Fractional Online Matching Under Edge Arrivals
发表日期:
2026年08月

发表单位:
Technion（以色列理工学院）

原文链接:
https://arxiv.org/pdf/2608.23350v1.pdf
在线匹配是理论计算机科学里一个被反复咀嚼了几十年的经典问题。简单说，就是图的边一条一条地到达，每条边到达时必须立刻决定要不要选它进入匹配，选中之后就不能反悔。目标是让最终选出的匹配尽可能大。这个问题之所以迷人，是因为它在现实世界里有一大堆影子：广告投放、出租车派单、器官捐献匹配，甚至直播平台的流量分配，都可以抽象成这个模型。
在这篇由以色列理工学院（Technion）学者David Wajc撰写的短文中，算法本身只有三行伪代码，其核心思路来自OpenAI的ChatGPT Sol——一个基于单个提示词就给出的建议。研究者跟ChatGPT来回讨论了几个小时，把证明过程做了梳理和补全，最终把边到达模型下分数在线匹配的竞争比下界从之前的1/2+exp(-Θ(n))大幅提升到1/2+Ω(1/n)，至此这个下界与已知上界1/2+O(1/n)在渐近意义下完全闭合。
这个问题本身已经困扰研究者很多年，一直存在一个“渐进空隙”：已知最好的算法能达到1/2+exp(-Θ(n))的竞争比，而已知的不可能性界限是1/2+O(1/n)。这个空隙虽然看起来很小，但就是差着那么一口气。现在，这口气被一个基于LLM辅助推导出来的算法给补上了。论文作者在文中坦言，这个结果本身对专家来说“可能兴趣有限”，但它提供了一个极其有趣的案例：一个简单的研究问题如何在大语言模型的辅助下被快速解决。

引言：一个提示词解决悬而未决的数学问题？

先把这个问题讲透。在线匹配最基础的设定是：一个有n个节点的图，它的边按照某种顺序一条一条到达。每来一条边，算法必须立刻决定要不要把它加入匹配，而且这个决定是不可撤销的。如果两条边共享同一个节点，它们就不能同时被选中。
这里有个关键评价指标叫“竞争比”。它衡量的是：算法在不知未来、只能在线做决定的情况下，最终得到的匹配大小，跟一个“事后诸葛亮”（也就是知道全部输入后能算出的最大匹配）之间的比值。竞争比越高，说明算法的决策质量越接近上帝视角。
最简单的贪心算法——每条边到达就选，如果冲突就跳过——可以稳定拿到1/2的竞争比。换句话说，无论输入多刁钻，贪心算法的输出大小至少是最优匹配的一半。
如果节点的到达顺序是逐步揭示的（顶点到达模型），那结果会好很多，可以做到1/2+Ω(1)的竞争比，也就是说跟1/2之间拉开了一个“常数级别”的差距。但在更严格的边到达模型下，情况就微妙了：你只知道边的顺序，完全不知道节点什么时候出现。此前最好的结果是1/2+exp(-Θ(n))，这个量虽然大于1/2，但小到几乎可以忽略。更让研究者挠头的是，[GKM+19]已经证明，即使是分数算法（允许把一条边“部分选中”），也不可能超过1/2+O(1/n)。换句话说，这个问题的天花板已经知道了，但一直没人能摸到。
而这篇论文的意义，就是把这个天花板一举捅穿：给出了一个竞争比达到1/2+Ω(1/n)的分数算法。注意，这里的关键是Ω(1/n)这个下界与已有的O(1/n)上界在渐近意义上完全匹配，也就是说，这个问题的最优竞争比终于被精确确定为1/2+Θ(1/n)了。
更让人佩服的是，这个算法的核心思路不是来自某位资深教授多年的灵感积累，而是来自ChatGPT Sol。作者的原话是：“该算法是由OpenAI的ChatGPT Sol基于单一提示词提出并分析的。”然后作者跟ChatGPT来回讨论了几个小时，把证明过程梳理成最终的形式。这篇论文因此也带有一种特别的气质：它不是一篇“标准”的研究论文，更像是一份“AI辅助科研”的实验报告。

核心算法：三行伪代码的巧妙设计

要让没有专业背景的读者也能感受到这个算法的精妙，得先建立几个直觉概念。
首先是“负载”。每个节点v会累积一个负载值ℓ_v，就是所有被选中的、连接到v的边的权重之和。因为这是一个分数匹配，每条边可以只选一部分，比如0.3、0.7，只要保证每个节点的总负载不超过1就行。可以把这个负载理解成一个节点的“忙碌程度”，负载1就是满载，再也没法接新任务了。相应地，残差容量r_v就是1减去当前负载，表示这个节点还剩多少“空间”可以分配给新来的边。
算法的核心决策逻辑是这样的：当一条新边e=(u,v)到达时，它要决定给这条边分配多少权重x_e。分配的上限有两个：端点u剩余的容量和端点v剩余的容量。为了让匹配保持“分数可行”，肯定不能超过这两个值中的较小者。但这里有个聪明的额外约束——算法会考虑两端剩余的容量之和。如果这个和小于1/2，那就什么都不给（x_e=0）；如果大于1/2，就分配一个让两端剩余容量之和正好等于1/2的数量。
简洁地说，算法就是：
    对每条到达的边 e=(u,v)：
    令 r_u 和 r_v 分别为端点 u 和 v 的当前残差容量
    x_e = min( r_u, r_v, (r_u + r_v - 1/2) / 2 取正值 )
    就这么简单。没有复杂的参数调节，没有基于未来信息的预测，甚至没有随机性。它的巧妙之处在于第三个候选值（即两端剩余容量之和减1/2后再除以2），这个值像是一个“智能节流阀”：当两端剩余容量之和较大时，它允许算法多分配一些；当两端剩余容量之和接近1/2时，它就让算法收手，不再继续累积负载。
    这个节流阀带来的直接后果是：处理完一条边之后，要么至少一个端点被“榨干”（负载达到1），要么两个端点的总负载达到至少3/2。这个“要么……要么……”的二分结构，是整个证明的基石。
    awesome and shock
    坦白讲，读到这段的时候，龙哥是有点惊讶的。一个困扰研究者多年的问题，最终的核心算法竟然只有三行伪代码，而这个算法的提出者居然是个大语言模型。虽然这个结果对专家来说可能不算惊艳，但这背后的冲击力确实很强。

    关键引理：边负载二分性与残差松弛

    一个算法的价值不仅在于是什么，更在于为什么它能行。论文用两个关键引理把这个“为什么”牢牢钉死。
    引理一：边负载二分性。这个引理说的是：对于任意一条到达的边e=(u,v)，最终（所有边处理完后）u和v的负载之和至少为1。更进一步，如果最终两条边的端点都没有被完全榨干（即都未饱和），那么它们最终的负载之和至少是3/2。
    这个3/2是怎么来的？关键是“如果两端都未饱和，那么在处理这条边时，x_e因为第三个候选值而起作用”。当一端饱和时，负载之和自然≥1；当两端都未饱和时，要么x_e被第三个候选值卡住，此时处理后两端残差容量之和正好是1/2，也就是负载和是3/2；要么x_e=0，此时说明处理前两端残差容量之和就已经≤1/2，负载和≥3/2。两种情况都指向同一个结论。
    引理二：残差松弛。这个引理说的是：如果某条边被分配了正权重（x_e>0），那么处理完这条边后，它的两个端点的残差容量之和至少为1/2。换句话说，只要算法“出手”了，就一定会给两个端点留下至少一半的松弛空间，防止它们彻底被锁死。
    这个引理的证明藏着一个有趣的技术细节。如果x_e不是被端点残差容量卡住（即x_e既不等于r_u也不等于r_v），那第三个候选值一定是唯一决定x_e的量，此时等式成立，残差之和正好是1/2。如果x_e被某个端点的残差容量卡住了，那说明这个端点自身的残差容量小于按节流阀公式算出的候选值，这迫使两个残差量之间至少相差1/2。于是取值小的那个端点被填满后，剩下的那个端点还有至少1/2的余量。

    竞争比下界证明：从饱和节点到质量守恒

    两条引理备好，接下来要证明的就是本论文的核心定理：算法输出的分数匹配值ALG，至少是OPT/2 + 1/4，进而至少是OPT×(1/2 + 1/(2n))。
    图7：核心不等式——ALG至少是OPT/2加1/4，同时至少是OPT倍的(1/2+1/(2n))
    由于总边权重之和的2倍等于所有节点负载之和（每条边被两个端点各计了一次），这个定理等价于证明一个更直接的式子：
    图8：需要证明的核心等价式——所有节点负载之和减去最优匹配大小至少为1/2
    证明的思路非常优雅。固定一个最优匹配M，它的边数是OPT。把所有节点的总负载按M的边进行分解：匹配中每条边(u,v)贡献一项ℓ_u+ℓ_v-1，没被匹配覆盖的节点w贡献一项ℓ_w。
    图9：总负载与最优匹配的差值分解——沿最优匹配逐条边展开
    根据引理（边负载二分性），M中每条边两端的负载之和≥1，所以每个(ℓ_u+ℓ_v-1)项都非负；未被匹配覆盖的节点的负载更是非负。于是可以进入一个判定：如果M中存在一条边，它的两个端点最终都没饱和，那这条边贡献的差值≥3/2-1=1/2，整个目标立刻达成。
    剩下的难点就在另一种情况：最优匹配M中的每条边，至少有一个端点是饱和的。此时，令S为所有饱和节点的集合。因为M中每条边都贡献了至少一个饱和节点，所以|S|≥OPT。这时，总负载减去OPT就可以向下放缩为：只把V\S（未饱和节点）中积累的负载拿过来，它的大小就足以证明不等式。
    图10：饱和节点集合S的引入——总负载与最优匹配的差至少为未饱和节点的总负载
    于是核心变成证明：一定有至少1/2的质量从饱和节点集合S跨界流到了未饱和节点V\S。这里分两种情况讨论。
    第一种情况：S内部没有一条边被分配了正权重。那所有落在S内部边上的质量都是0，可S里至少有OPT≥1个节点需要被“喂满”到1，这些质量只能来自S与V\S之间的边。所以S与V\S之间分配的权重总和至少是|S|≥OPT≥1≥1/2。质量守恒，达成目标。
    第二种情况：S内部存在一些被分配了正权重的边。取其中最后到达的一条e=(u,v)。在这条边被处理的瞬间，它给两个饱和端点分配了正权重。按照引理（残差松弛性），处理完后u和v的残差容量之和至少为1/2。也就是说，在那之后S内节点们合起来还有半单位以上的“空余”。但最终所有S中的节点都必须付出全部负载才能凑满1，这意味着S的剩余容量在最后必须降到0。从至少1/2降到0，中间必然有至少1/2的质量通过S与V\S之间的边流了出去。
    图11：最后一条S内部正权重边处理完后，S内残差总量至少为1/2
    到这里，就得到了最后的关键不等式：
    图12：最终关键不等式——未饱和节点的总负载至少为1/2，从而证明竞争比
    整个证明的节奏非常流畅：先是两种情况分治，再用“饱和节点”和“质量流动”这两个视角把复杂情况转化为总量平衡，最后借助引理得出半单位的跨界质量。这背后没有高不可攀的数学工具，有的只是一个恰到好处的算法设计和一个清晰的证明思路。

    LLM辅助科研的启示与反思

    论文在第3节“Reflections”里说了一段很坦诚的话：这篇笔记的主要目的，是提供又一个“简单的研究问题可以用大语言模型辅助解决”的例子。作者甚至直言，结果本身对专家而言可能兴趣有限，但它再次抛出了一个更大的问题——在LLM可以快速处理大量“够得着”的问题的时代，什么才是适合初学者的入门研究问题？
    这句话背后其实藏着一个很现实的判断。在线匹配这类问题有一个鲜明特点：问题定义清晰，目标函数明确，约束简单，但边界条件复杂，需要精巧的构造。这类问题在经典文献中已经被反复咀嚼过，对LLM来说，它的训练语料里很可能包含了大量相关讨论，因此“提出一个候选算法”完全在模型的能力范围内。更重要的是，这类问题的验证成本极低——跑一段模拟就能看出算法是否有效，证明过程也是标准技巧的组装。
    但这里也要说句公道话。论文描述的流程是“ChatGPT Sol提出算法并分析，作者进行了数小时的来回讨论，并将展示流线化”。换句话说，算法是模型给的，但识别问题价值、判断证明方向、确认没有逻辑漏洞、把散落的思路整理成严谨论文的，依然是作者。这篇论文真正展示的，不是“AI独立做出了重大数学发现”，而是“AI+人类专家协作，可以显著加速一个中等难度理论问题的攻关”。
    对于正在学习科研的读者，这其实是一个重要的信号。大语言模型正在把“从零推导一个问题”的门槛压低，但把精力花在“提出好问题、设计严格的验证流程、理解证明的深层结构”上，依然是人不可替代的部分。一个能提出候选算法的模型，和一个能判断这个算法是否值得信、为什么成立的研究者，组合起来才会产生这样的成果。
    如果你还有哪些想要了解的，欢迎在评论区留言或者讨论~

    龙迷三问

    下面是龙哥对于大家可能的一些问题的解答：
    这篇论文到底在解决什么问题？以色列理工学者在最新论文中，用简洁到极致的算法（由ChatGPT Sol基于单个提示词建议），将边到达模型下分数在线匹配的竞争比下界提升至1/2+Ω(1/n)，与已知上界匹配，彻底闭合了该问题长达数年的渐进空隙。
    这篇工作最值得看的点是什么？不适用（纯理论论文，无实验）
    这篇工作的边界或风险在哪里？优点：算法极其简洁优雅，仅需一行伪代码即可描述；分析清晰，通过两个关键引理（边负载二分性和残差松弛性）完成了竞争比下界的证明；首次闭合了分数在线匹配在边到达模型下的渐近间隙。缺点：结果本身对领域专家而言增量有限；论文未解决常数因子的精确值；算法仅针对分数匹配，不适用于整数匹配场景。

    龙哥点评

    论文创新性分数：★★★☆☆

    算法极简洁且设计巧妙，但核心想法源于LLM，人的角色更像验证与整理；相对领域内既有技术路线，突破点在于“原来可以达到”这件事本身，而非全新范式。

    实验合理度：★★★★☆

    纯理论证明，无实验对比；但证明逻辑自洽，引理环环相扣，结论与已知上界匹配。若与GKM+19的上界合起来读，定理的边界非常明确。

    学术研究价值：★★★★☆

    闭合了一个经典问题的渐近空隙，且算法极其简洁，非常适合作为教学案例和后续研究起点；“LLM辅助提出算法”的示范效应可能比结果本身更具长期价值。

    稳定性：★★★★☆

    算法是确定性的、无随机性，不依赖输入分布，理论上任何图都能保证相同的竞争比下界；不需要调参，稳定性的前提条件非常干净。

    适应性以及泛化能力：★★★☆☆

    方法针对的是边到达模型下的基数最大化；顶点到达、整体到达等变体已有更优解，算法未展示跨场景迁移能力，泛化范围有限。

    硬件需求及成本：★★★★★

    算法只需要维护每个节点的负载数值，每次边到达只需几次比较和四则运算，无论训练还是推理都没有任何计算压力，任何设备可跑。

    复现难度：★★★★★

    伪代码完整给出，没有超参数、没有训练数据集、没有随机种子，任何人照抄三行代码即可验证；论文也已公开在arXiv上，门槛极低。

    产品化成熟度：★★☆☆☆

    纯理论成果，不面向具体产品；不过“保留缓冲以应对未来”的在线分配思想，可为广告竞价、库存分配、带宽调度等系统提供设计参考，但需要针对业务做大量适配。

    可能的问题：论文篇幅很短，结果本身作者也承认对专家“兴趣有限”；常数因子1/4与上界的常数1/n之间存在尚未闭合的常数差距；LLM在算法发现中具体扮演多大角色、能否独立完成证明难以量化评估，流程可复现性未知。


    主要参考文献

    [1] David Wajc. Asymptotically Tight Fractional Online Matching Under Edge Arrivals. arXiv:2608.23350, 2026. 原论文链接：https://arxiv.org/pdf/2608.23350v1.pdf
    [2] Niv Buchbinder, Danny Segev, and Yevgeny Tkach. Online algorithms for maximum cardinality matching with edge arrivals. Algorithmica, 81(5):1781–1799, 2019.
    [3] Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, and David Wajc. Online matching with general arrivals. In Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS), 2019.
    [4] Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pages 352–358, 1990.
    [5] Euiwoong Lee and Sahil Singla. Maximum matching in the online batch-arrival model. ACM Transactions on Algorithms (TALG), 16(4):1–31, 2020.
    [6] Aranyak Mehta. Online matching and ad allocation. Foundations and Trends® in Theoretical Computer Science, 8(4):265–368, 2013.
    [7] Zhiyi Huang, Zhihao Gavin Tang, and David Wajc. Online matching: A brief survey. ACM SIGecom Exchanges, 22(1):135–158, 2024.

    *本文仅代表个人理解及观点，不构成任何论文审核或者项目落地推荐意见，具体以相关组织评审结果为准。欢迎就论文内容交流探讨，理性发言哦～ 想了解更多原文细节的小伙伴，可以点击"阅读原文"，查看更多原论文细节哦！       

    end
    🎓 理论计算机+AI辅助科研，这条新赛道正热！
    欢迎加入龙哥读论文粉丝群，扫描下方二维码或者添加龙哥助手微信号加群：kangjinlonghelper。一定要备注：研究方向+地点+学校/公司+昵称（如 图像处理+上海+清华+龙哥），根据格式备注，可更快被通过且邀请进群。
    『龙哥读论文』微信群目前包含：图像处理、大模型及智能体、自动驾驶及机器人、AI医疗及AI金融5个群。理论算法、大模型应用，你都能找到同路人！
    wechat_helper dianzan

    转发文章 微博 X LinkedIn Facebook
    龙哥读论文 · PaperDaily

    本文基于龙哥读论文 PaperDaily 数据库整理，结合论文原文与工程视角进行解读。