CHORUS: Zero-shot Hierarchical Retrieval and Orchestration for Generating Linear Programming Code

📄 arXiv: 2505.01485v1 📥 PDF

作者: Tasnim Ahmed, Salimur Choudhury

分类: cs.AI, cs.CL

发布日期: 2025-05-02

备注: This paper has been accepted for presentation at the 19th Learning and Intelligent Optimization Conference (LION 19)

💡 一句话要点

CHORUS：零样本分层检索与编排，用于生成线性规划代码

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

关键词: 线性规划 代码生成 检索增强生成 大型语言模型 分层检索

📋 核心要点

  1. 现有方法在利用大型语言模型生成线性规划代码时，缺乏有效的知识检索和利用机制，导致生成质量不高。
  2. CHORUS通过分层检索增强生成框架，结合精心设计的提示和结构化解析器，提升了LLM生成线性规划代码的性能。
  3. 实验表明，CHORUS显著提升了开源LLM在NL4Opt-Code基准上的性能，甚至超越了更强大的闭源模型。

📝 摘要（中文）

线性规划（LP）问题旨在寻找约束条件下目标的最优解。这类问题通常需要领域知识、数学技能和编程能力，对非专业人士构成重大挑战。本研究探讨了大型语言模型（LLMs）在生成特定求解器LP代码方面的效率。我们提出了CHORUS，一个检索增强生成（RAG）框架，用于从自然语言问题陈述中合成基于Gurobi的LP代码。CHORUS采用分层树状分块策略处理理论内容，并基于文档中的代码示例生成额外的元数据，以促进自包含、语义连贯的检索。CHORUS的两阶段检索方法，以及随后的交叉编码器重排序，进一步确保了上下文相关性。最后，精心设计的提示和带有推理步骤的结构化解析器显著提高了代码生成性能。在NL4Opt-Code基准上的实验表明，与基线和传统RAG相比，CHORUS显著提高了开源LLM（如Llama3.1 (8B)、Llama3.3 (70B)、Phi4 (14B)、Deepseek-r1 (32B)和Qwen2.5-coder (32B)）的性能。它还使这些开源LLM能够超越或匹配更强大的基线GPT3.5和GPT4的性能，同时需要的计算资源要少得多。消融研究进一步证明了专家提示、分层分块和结构化推理的重要性。

🔬 方法详解

问题定义：论文旨在解决非专业人士难以将自然语言描述的线性规划问题转化为求解器特定代码的问题。现有方法，特别是直接使用大型语言模型或传统RAG方法，在处理复杂的线性规划问题时，由于缺乏领域知识和精确的代码生成能力，效果不佳。

核心思路：论文的核心思路是利用检索增强生成（RAG）框架，通过分层检索相关知识和代码示例，结合专家设计的提示和结构化解析器，引导大型语言模型生成高质量的线性规划代码。这种方法旨在弥合自然语言描述和求解器代码之间的差距。

技术框架：CHORUS框架包含以下主要模块：1) 分层知识库构建：将理论内容进行树状分块，并为代码示例生成元数据。2) 两阶段检索：首先进行粗略检索，然后使用交叉编码器进行重排序，以确保上下文相关性。3) 专家提示：使用精心设计的提示引导LLM进行代码生成。4) 结构化解析器：带有推理步骤的解析器，用于提高代码生成的准确性。

关键创新：CHORUS的关键创新在于其分层检索策略和专家提示的结合。分层检索能够更有效地找到与问题相关的知识和代码示例，而专家提示则能够引导LLM更好地利用这些信息。此外，结构化解析器的使用也提高了代码生成的可靠性。

关键设计：分层知识库构建采用树状结构，允许从粗到细的检索。元数据生成包括代码示例的描述、输入输出等信息。两阶段检索中的交叉编码器使用预训练模型进行微调，以提高重排序的准确性。专家提示包含问题描述、相关知识和代码示例，并引导LLM逐步推理和生成代码。结构化解析器定义了代码生成的语法规则和推理步骤。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

CHORUS在NL4Opt-Code基准测试中，显著提升了开源LLM的性能。例如，Llama3.1 (8B)、Llama3.3 (70B)、Phi4 (14B)、Deepseek-r1 (32B)和Qwen2.5-coder (32B)的性能均得到了大幅提升，甚至超越或匹配了GPT3.5和GPT4等更强大的基线模型，同时所需的计算资源更少。消融实验也验证了专家提示、分层分块和结构化推理的重要性。

🎯 应用场景

该研究成果可应用于自动化代码生成、教育领域和优化问题求解等场景。通过CHORUS，非专业人士可以更轻松地将实际问题转化为线性规划模型，并自动生成可执行的代码，从而降低了使用线性规划的门槛，加速了问题求解过程。未来，该技术可扩展到其他优化问题和编程语言。

📄 摘要（原文）

Linear Programming (LP) problems aim to find the optimal solution to an objective under constraints. These problems typically require domain knowledge, mathematical skills, and programming ability, presenting significant challenges for non-experts. This study explores the efficiency of Large Language Models (LLMs) in generating solver-specific LP code. We propose CHORUS, a retrieval-augmented generation (RAG) framework for synthesizing Gurobi-based LP code from natural language problem statements. CHORUS incorporates a hierarchical tree-like chunking strategy for theoretical contents and generates additional metadata based on code examples from documentation to facilitate self-contained, semantically coherent retrieval. Two-stage retrieval approach of CHORUS followed by cross-encoder reranking further ensures contextual relevance. Finally, expertly crafted prompt and structured parser with reasoning steps improve code generation performance significantly. Experiments on the NL4Opt-Code benchmark show that CHORUS improves the performance of open-source LLMs such as Llama3.1 (8B), Llama3.3 (70B), Phi4 (14B), Deepseek-r1 (32B), and Qwen2.5-coder (32B) by a significant margin compared to baseline and conventional RAG. It also allows these open-source LLMs to outperform or match the performance of much stronger baselines-GPT3.5 and GPT4 while requiring far fewer computational resources. Ablation studies further demonstrate the importance of expert prompting, hierarchical chunking, and structured reasoning.