Learning Randomized Reductions
作者: Ferhat Erata, Orr Paradise, Thanos Typaldos, Timos Antonopoulos, ThanhVu Nguyen, Shafi Goldwasser, Ruzica Piskac
分类: cs.LG, cs.CC, cs.PL, cs.SE
发布日期: 2024-12-24 (更新: 2026-01-17)
💡 一句话要点
Bitween：利用线性回归和神经符号方法自动学习随机自归约
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 随机自归约 自校正器 线性回归 神经符号方法 大型语言模型 自动化学习 函数性质
📋 核心要点
- 传统RSR的发现依赖专家手动推导，成本高昂且效率低下，缺乏自动化方法。
- Bitween通过线性回归学习RSR，Agentic Bitween利用LLM动态发现查询函数，实现RSR的自动学习。
- 实验表明，Bitween优于现有符号方法，Agentic Bitween能发现新的RSR属性，提升了RSR发现能力。
📝 摘要（中文）
函数f的自校正器利用一个黑盒预言机计算f，该预言机在大多数输入上是正确的，并将其转换为一个在每个输入上都以高概率正确的预言机。自校正器适用于任何随机自归约（RSR）的函数，其中给定点x处的f值可以通过计算随机相关点上的f来恢复。虽然RSR能够实现强大的自校正能力，并在复杂性理论和密码学中具有应用，但它们的发现在传统上需要专家的手动推导。我们提出了Bitween，一种用于自动学习数学函数随机自归约的方法和工具。我们做出了两个关键贡献：首先，我们证明了我们基于线性回归的学习框架优于包括遗传算法、符号回归和混合整数线性规划在内的复杂方法，用于从相关样本中发现RSR。其次，我们引入了Agentic Bitween，一种神经符号方法，其中大型语言模型动态地发现用于RSR属性发现的新型查询函数，利用vanilla Bitween作为推理和验证的工具，超越了先前文献中使用的固定查询函数（x+r，x-r，x·r，x，r）。在RSR-Bench（我们包含80个科学和机器学习函数的基准测试套件）上，vanilla Bitween超越了现有的符号方法，而Agentic Bitween利用前沿模型发现新的RSR属性以发现查询函数。
🔬 方法详解
问题定义：论文旨在解决自动发现随机自归约（RSR）的问题。现有方法依赖于专家手动推导，过程繁琐且耗时，缺乏通用的自动化工具。此外，已有的方法通常只考虑预定义的查询函数，限制了RSR的发现范围。
核心思路：论文的核心思路是利用机器学习技术，特别是线性回归和大型语言模型（LLM），来自动学习RSR。通过从相关样本中学习函数的关系，并结合LLM的推理能力，可以有效地发现新的查询函数，从而扩展RSR的发现范围。
技术框架：Bitween框架包含两个主要组成部分：vanilla Bitween和Agentic Bitween。vanilla Bitween使用线性回归从相关样本中学习RSR。Agentic Bitween则利用LLM动态生成新的查询函数，并使用vanilla Bitween进行验证。整体流程如下：首先，Agentic Bitween利用LLM生成候选查询函数；然后，vanilla Bitween使用线性回归验证这些查询函数是否满足RSR的性质；最后，选择满足RSR性质的查询函数，并将其添加到查询函数库中。
关键创新：论文的关键创新在于引入了Agentic Bitween，这是一种神经符号方法，它利用LLM动态发现新的查询函数。与传统方法中使用的固定查询函数不同，Agentic Bitween能够探索更广泛的查询函数空间，从而发现新的RSR属性。这种方法结合了LLM的推理能力和线性回归的验证能力，实现了RSR的自动学习。
关键设计：Agentic Bitween的关键设计在于如何利用LLM生成有效的查询函数。论文采用了一种迭代的方式，首先使用少量的样本训练一个初始的LLM模型，然后使用该模型生成候选查询函数。接着，使用vanilla Bitween验证这些查询函数是否满足RSR的性质。最后，根据验证结果更新LLM模型，并重复上述过程。这种迭代的方式可以逐步提高LLM生成有效查询函数的能力。
🖼️ 关键图片
📊 实验亮点
实验结果表明，vanilla Bitween在RSR-Bench基准测试套件上超越了现有的符号方法。Agentic Bitween能够发现新的RSR属性，并利用前沿模型发现查询函数。这些结果表明，该方法在RSR自动学习方面具有显著的优势。
🎯 应用场景
该研究成果可应用于密码学、复杂性理论和机器学习等领域。例如，可以利用自动发现的RSR构建更强大的自校正器，提高系统的可靠性和安全性。此外，该方法还可以用于分析和理解各种数学函数的性质，为科学研究提供新的工具和视角。
📄 摘要（原文）
A self-corrector for a function $f$ takes a black-box oracle computing $f$ that is correct on most inputs and turns it into one that is correct on every input with high probability. Self-correctors exist for any function that is randomly self-reducible (RSR), where the value $f$ at a given point $x$ can be recovered by computing $f$ on random correlated points. While RSRs enable powerful self-correction capabilities and have applications in complexity theory and cryptography, their discovery has traditionally required manual derivation by experts. We present Bitween, a method and tool for automated learning of randomized self-reductions for mathematical functions. We make two key contributions: First, we demonstrate that our learning framework based on linear regression outperforms sophisticated methods including genetic algorithms, symbolic regression, and mixed-integer linear programming for discovering RSRs from correlated samples. Second, we introduce Agentic Bitween, a neuro-symbolic approach where large language models dynamically discover novel query functions for RSR property discovery, leveraging vanilla Bitween as a tool for inference and verification, moving beyond the fixed query functions ($x+r$, $x-r$, $x \cdot r$, $x$, $r$) previously used in the literature. On RSR-Bench, our benchmark suite of 80 scientific and machine learning functions, vanilla Bitween surpasses existing symbolic methods, while Agentic Bitween discovers new RSR properties using frontier models to uncover query functions.