Recursive Decomposition with Dependencies for Generic Divide-and-Conquer Reasoning

📄 arXiv: 2505.02576v1 📥 PDF

作者: Sergio Hernández-Gutiérrez, Minttu Alakuijala, Alexander V. Nikitin, Pekka Marttinen

分类: cs.AI, cs.LG

发布日期: 2025-05-05

💡 一句话要点

提出RDD：一种通用的、可扩展的依赖递归分解推理方法

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 递归分解 依赖关系建模 大型语言模型 推理任务 错误恢复

📋 核心要点

  1. 现有LLM推理方法在复杂问题上扩展性不足，且常需大量任务特定监督。
  2. RDD通过递归分解问题为带依赖的子任务，实现更高效的推理和错误纠正。
  3. 实验表明，RDD在计算效率和性能上优于其他方法，尤其是在复杂任务中。

📝 摘要（中文）

推理任务在许多领域至关重要，尤其是在科学和工程领域。尽管大型语言模型（LLMs）在使用思维链和由粗到精提示等技术在推理任务中取得了进展，但这些方法在性能或执行时间方面仍然无法有效地扩展到复杂问题。此外，它们通常需要为每个新任务提供额外的监督，例如上下文示例。本文介绍了一种可扩展的分解方法，即具有依赖关系的递归分解（RDD），用于解决推理问题，与先前的方法相比，它需要的监督更少。即使在没有任何特定于任务的指导的情况下，我们的方法也可以直接应用于新的问题类别。此外，RDD支持子任务依赖关系，允许子任务的有序执行，以及可以纠正先前步骤中错误的错误恢复机制。我们在两个基准测试中评估了我们的方法，每个基准测试都有六个难度级别，并且在两种上下文设置中：一种具有特定于任务的示例，另一种没有。我们的结果表明，随着任务复杂性的增加，RDD在计算匹配的设置中优于其他方法，同时也更具计算效率。

🔬 方法详解

问题定义：论文旨在解决复杂推理任务中，现有大型语言模型（LLMs）方法扩展性差、需要大量任务特定监督的问题。现有方法，如思维链（Chain-of-Thought）和由粗到精提示（Least-to-Most Prompting），在面对复杂问题时，性能下降且计算成本高昂，并且通常需要针对每个新任务提供额外的上下文示例。

核心思路：论文的核心思路是将复杂的推理问题递归地分解为更小的、相互依赖的子任务。通过这种“分而治之”的策略，降低了每个子任务的难度，使得LLM更容易处理。同时，引入子任务之间的依赖关系，确保子任务按照正确的顺序执行，并允许错误恢复机制纠正先前步骤中的错误。

技术框架：RDD方法包含以下主要阶段：1) 问题分解：将原始问题分解为一系列相互依赖的子任务。2) 子任务执行：按照依赖关系图的顺序执行每个子任务，利用LLM生成子任务的解决方案。3) 错误检测与纠正：在执行过程中检测错误，并利用错误恢复机制纠正错误。4) 结果整合：将子任务的解决方案整合为原始问题的最终答案。

关键创新：RDD的关键创新在于其递归分解和依赖关系建模。与传统的思维链方法相比，RDD能够更有效地处理复杂问题，并且不需要大量的任务特定示例。此外，RDD的错误恢复机制能够提高推理的鲁棒性。RDD方法通过显式地建模子任务之间的依赖关系，实现了子任务的有序执行，这与传统的独立子任务分解方法不同。

关键设计：RDD的具体实现细节包括：1) 分解策略：如何将原始问题分解为子任务，例如，可以使用启发式规则或学习算法。2) 依赖关系建模：如何表示子任务之间的依赖关系，例如，可以使用有向无环图。3) 错误检测与纠正机制：如何检测子任务执行过程中的错误，以及如何利用LLM纠正这些错误。具体的参数设置、损失函数、网络结构等技术细节在论文中未明确给出，可能依赖于具体的LLM和任务。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，RDD在两个基准测试中，随着任务复杂性的增加，在计算匹配的设置下，性能优于其他方法。具体而言，RDD在无需任务特定示例的情况下，仍然能够取得显著的性能提升，并且在计算效率方面也优于其他方法。这些结果验证了RDD方法在复杂推理任务中的有效性和优越性。

🎯 应用场景

RDD方法具有广泛的应用前景，可以应用于科学发现、工程设计、数学问题求解、代码生成等需要复杂推理的领域。该方法能够提高LLM在这些领域的应用效果，降低对人工干预的需求，并有望推动自动化推理技术的发展。未来，RDD可以与其他技术相结合，例如知识图谱、符号推理等，以进一步提高推理能力。

📄 摘要（原文）

Reasoning tasks are crucial in many domains, especially in science and engineering. Although large language models (LLMs) have made progress in reasoning tasks using techniques such as chain-of-thought and least-to-most prompting, these approaches still do not effectively scale to complex problems in either their performance or execution time. Moreover, they often require additional supervision for each new task, such as in-context examples. In this work, we introduce Recursive Decomposition with Dependencies (RDD), a scalable divide-and-conquer method for solving reasoning problems that requires less supervision than prior approaches. Our method can be directly applied to a new problem class even in the absence of any task-specific guidance. Furthermore, RDD supports sub-task dependencies, allowing for ordered execution of sub-tasks, as well as an error recovery mechanism that can correct mistakes made in previous steps. We evaluate our approach on two benchmarks with six difficulty levels each and in two in-context settings: one with task-specific examples and one without. Our results demonstrate that RDD outperforms other methods in a compute-matched setting as task complexity increases, while also being more computationally efficient.