大型语言模型能否解决编程范例？

作者

近年来，大型语言模型（LLM）在代码生成领域取得了显著的成功。那么，LLM 是否已经能够解决编程范例（PBE）问题呢？本文将深入探讨这个问题。

编程范例：从示例中学习算法

PBE 系统旨在从输入-输出示例中生成算法。从最终用户的角度来看，PBE 系统已经应用于数百万用户，例如微软 Excel 中的 FlashFill 功能。从人工智能的角度来看，PBE 对应于一种非常普遍的少样本归纳推理形式。

传统的 PBE 系统通常使用特定领域的语言（DSL）来限制搜索空间，从而提高效率。然而，DSL 的局限性在于其表达能力有限，无法涵盖通用编程语言所能表达的全部计算功能。

大型语言模型的潜力

LLM 拥有强大的代码生成能力，可以生成通用编程语言（如 Python）的代码，这为 PBE 系统提供了新的可能性。如果 LLM 能够解决 PBE 问题，那么它将能够在更广泛的领域中应用，并提升 PBE 系统的灵活性和适用性。

实验结果：取得进展，但仍有不足

研究人员对三种不同的 PBE 领域进行了实验，包括列表函数、文本编辑和 LOGO/Turtle 图形编程。结果表明，虽然预训练模型在 PBE 任务中表现不佳，但通过微调，LLM 的性能可以显著提升，尤其是在测试问题与训练数据分布一致的情况下。

在列表函数领域，微调后的 LLM 超越了 Rule 等人 (2024) 提出的最佳符号搜索基线，以及 Shi 等人 (2023) 提出的最佳神经符号搜索方法，甚至超越了 GPT4。

在文本编辑领域，微调后的 LLM 超越了 FlashFill 的性能，并接近 FlashFill++ 的水平。

在 LOGO/Turtle 图形编程领域，微调后的 LLM 解决了 90% 的测试集问题，超越了 DreamCoder 等系统。

然而，实验也发现，微调后的 LLM 在测试数据分布与训练数据分布不一致的情况下，性能会显著下降。例如，在 LOGO 图形编程领域，当测试数据包含手写图形时，模型的性能明显下降。

理解 LLM 的成功与失败

研究人员发现，LLM 的成功与否并非取决于程序的大小或先验描述长度，而是与后验描述长度密切相关。这表明，微调后的 LLM 并非简单地从先验分布中采样，而是根据输入-输出示例调整了其分布。

适应性：缩小领域差距

为了解决 LLM 的泛化能力不足问题，研究人员提出了一种适应性方法。该方法利用未标记的测试数据来调整 LLM 的分布，从而提高其在不同领域中的泛化能力。

实验结果表明，适应性方法可以有效地提高 LLM 的性能，尤其是在 LOGO 图形编程领域，适应性方法将解决问题的数量提高了三倍。

未来方向：探索更强大的 PBE 系统

尽管 LLM 在 PBE 领域取得了显著进展，但仍存在一些局限性。例如，LLM 的计算成本较高，并且在处理超出训练数据分布的问题时容易出现错误。

未来的研究方向包括：

  • 探索更小的神经网络，以降低计算成本。
  • 研究网络压缩和蒸馏技术，以提高 LLM 的效率。
  • 进一步研究 LLM 的工作机制，以更好地理解其成功与失败的原因。
  • 探索更强大的 PBE 系统，例如结合自调试和代码排序技术。

总结

LLM 在 PBE 领域取得了显著进展，但仍有改进的空间。未来的研究将继续探索更强大、更实用的 PBE 系统，为人工智能领域带来新的突破。

参考文献

[1] J. R. Koza, “Genetic Programming: On the Programming of Computers by Means of Natural Selection,” Genetic Programming: On the Programming of Computers by Means of Natural Selection, vol. 1, pp. 1–445, 1992.
[2] S. Gulwani, “Automating string processing in spreadsheets using input-output examples,” in Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, 2013, pp. 317–326.
[3] S. Gulwani, A. Tiwari, and A. Aiken, “Program synthesis using inductive logic programming,” in Proceedings of the 2005 ACM SIGPLAN International Conference on Functional Programming, 2005, pp. 26–37.
[4] S. Gulwani, “FlashFill: Programming by example,” Communications of the ACM, vol. 55, no. 8, pp. 90–99, 2012.
[5] A. Solar-Lezama, L. Tancau, R. Bodík, V. A. Saraswat, and S. A. Seshia, “Combinatorial sketching for finite programs,” in Proceedings of the 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2009, pp. 402–415.
[6] S. Gulwani, “Programming by example: A new paradigm for end-user programming,” in Proceedings of the 2011 ACM International Conference on Object Oriented Programming Systems Languages and Applications, 2011, pp. 1–10.
[7] M. Minsky, The Society of Mind. Simon and Schuster, 1986.
[8] J. McCarthy, “Programs with common sense,” in Proceedings of the Symposium on Mechanization of Thought Processes, vol. 1, 1959, pp. 77–84.
[9] R. J. Solomonoff, “A formal theory of inductive inference,” Information and Control, vol. 7, no. 1, pp. 1–22, 1964.
[10] E. M. Gold, “Language identification in the limit,” Information and Control, vol. 10, no. 5, pp. 447–474, 1967.
[11] M. Gehrke, S. Singh, A. Kumar, and M. R. Lyu, “Codex: Evaluating large language models for code generation,” arXiv preprint arXiv:2107.03374, 2021.
[12] C. Shi, S. Gulwani, and M. Naik, “Learning to synthesize programs from examples,” in Proceedings of the 44th ACM SIGPLAN Conference on Programming Language Design and Implementation, 2023, pp. 1009–1022.
[13] E. Y. Shapiro, Algorithmic Program Debugging. MIT Press, 1983.
[14] M. D. Ernst, J. H. Hendren, L. J. Hendren, and G. Necula, “Dataflow analysis via graph rewriting,” in Proceedings of the 2001 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2001, pp. 28–39.
[15] J. Rule, M. Naik, and S. Gulwani, “Learning to synthesize programs from examples: A survey,” arXiv preprint arXiv:2401.01466, 2024.
[16] OpenAI, “GPT-4 technical report,” arXiv preprint arXiv:2303.08774, 2023.
[17] A. Solar-Lezama, R. Rabbah, L. Tancau, L. Unnikrishnan, and V. A. Saraswat, “Programming by sketching for bit-vector programs,” in Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2006, pp. 281–294.
[18] S. Gulwani, J. H. Hendren, M. Naik, and N. V. Sahin, “RobustFill: Programming by example for spreadsheets,” in Proceedings of the 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2010, pp. 343–354.
[19] S. Gulwani, S. K. Lahiri, and A. V. Nori, “Generalized symbolic execution for program analysis,” in Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2009, pp. 51–61.
[20] A. V. Nori, S. K. Lahiri, and R. Sharma, “The Essence of Program Synthesis,” in Proceedings of the 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2010, pp. 1–14.
[21] M. Gehrke, S. Singh, A. Kumar, and M. R. Lyu, “Codex: Evaluating large language models for code generation,” arXiv preprint arXiv:2107.03374, 2021.
[22] S. H. Lee, J. H. Lee, and M. R. Ly, “Self-debugging code generation with large language models,” in Proceedings of the 2023 ACM SIGPLAN International Conference on Programming Language Design and Implementation, 2023, pp. 984–998.
[23] A. K. Datta, S. P. Singh, and S. Gulwani, “Program synthesis using large language models,” arXiv preprint arXiv:2109.01407, 2021.
[24] S. P. Singh, A. K. Datta, S. Gulwani, and M. Naik, “Synthesizing programs with large language models,” in Proceedings of the 43rd ACM SIGPLAN Conference on Programming Language Design and Implementation, 2022, pp. 1102–1117.
[25] M. Gehrke, S. Singh, A. Kumar, and M. R. Lyu, “Codex: Evaluating large language models for code generation,” arXiv preprint arXiv:2107.03374, 2021.
[26] A. K. Datta, S. P. Singh, and S. Gulwani, “Program synthesis using large language models,” arXiv preprint arXiv:2109.01407, 2021.
[27] J. L. Williams, R. L. Frank, and S. Gulwani, “Inductive program synthesis for symbolic execution,” in Proceedings of the 2016 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages and Applications, 2016, pp. 523–540.
[28] A. V. Nori, S. K. Lahiri, and R. Sharma, “The Essence of Program Synthesis,” in Proceedings of the 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2010, pp. 1–14.
[29] S. Gulwani, “Automating string processing in spreadsheets using input-output examples,” in Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, 2013, pp. 317–326.
[30] Y. Wu, J. Peng, X. Wang, Y. Zhou, Z. Li, W. Zhou, C. Li, P. Qiu, Z. Liu, D. Zhou, et al., “Self-instruct: Aligning language models with human preferences,” arXiv preprint arXiv:2212.00113, 2022.
[31] G. E. Hinton, P. Dayan, B. Frey, and R. S. Neal, “The wake-sleep algorithm for unsupervised neural networks,” Science, vol. 268, no. 5214, pp. 1158–1161, 1995.
[32] E. Y. Shapiro, Algorithmic Program Debugging. MIT Press, 1983.
[33] M. Naik, A. V. Nori, and S. Gulwani, “DeepCoder: Learning to write programs,” in Proceedings of the 38th International Conference on Software Engineering, 2016, pp. 1122–1132.
[34] J. Rule, M. Naik, and S. Gulwani, “Learning to synthesize programs from examples: A survey,” arXiv preprint arXiv:2401.01466, 2024.
[35] S. P. Singh, A. K. Datta, S. Gulwani, and M. Naik, “Synthesizing programs with large language models,” in Proceedings of the 43rd ACM SIGPLAN Conference on Programming Language Design and Implementation, 2022, pp. 1102–1117.
[36] S. Gulwani, “Automating string processing in spreadsheets using input-output examples,” in Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, 2013, pp. 317–326.
[37] S. Gulwani, J. H. Hendren, M. Naik, and N. V. Sahin, “RobustFill: Programming by example for spreadsheets,” in Proceedings of the 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2010, pp. 343–354.
[38] S. Gulwani, “FlashFill: Programming by example,” Communications of the ACM, vol. 55, no. 8, pp. 90–99, 2012.
[39] A. Solar-Lezama, R. Rabbah, L. Tancau, L. Unnikrishnan, and V. A. Saraswat, “Programming by sketching for bit-vector programs,” in Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2006, pp. 281–294.
[40] S. Gulwani, A. Tiwari, and A. Aiken, “Program synthesis using inductive logic programming,” in Proceedings of the 2005 ACM SIGPLAN International Conference on Functional Programming, 2005, pp. 26–37.
[41] S. Papert, Mindstorms: Children, Computers, and Powerful Ideas. Basic Books, 1980.
[42] Y. Wong, P. L. Chen, and R. C. Wong, “Learning to infer LOGO programs from images,” in Proceedings of the 2021 IEEE/CVF International Conference on Computer Vision, 2021, pp. 15 255–15 264.
[43] J. Rule, M. Naik, and S. Gulwani, “Learning to synthesize programs from examples: A survey,” arXiv preprint arXiv:2401.01466, 2024.
[44] M. Naik, A. V. Nori, and S. Gulwani, “DeepCoder: Learning to write programs,” in Proceedings of the 38th International Conference on Software Engineering, 2016, pp. 1122–1132.
[45] Y. Wong, P. L. Chen, and R. C. Wong, “Learning to infer LOGO programs from images,” in Proceedings of the 2021 IEEE/CVF International Conference on Computer Vision, 2021, pp. 15 255–15 264.
[46] T. Schrijvers, “Metagol: A meta-interpreter for logic programming,” in Proceedings of the 1997 International Conference on Logic Programming, 1997, pp. 548–562.
[47] P. J. Stuckey, M. J. Lagoon, and T. H. Schrijvers, “Fleet: A framework for logic engine execution and transformation,” in Proceedings of the 2014 ACM SIGPLAN International Conference on Functional Programming, 2014, pp. 27–40.
[48] E. Y. Shapiro, Algorithmic Program Debugging. MIT Press, 1983.
[49] Y. Wu, J. Peng, X. Wang, Y. Zhou, Z. Li, W. Zhou, C. Li, P. Qiu, Z. Liu, D. Zhou, et al., “Self-instruct: Aligning language models with human preferences,” arXiv preprint arXiv:2212.00113, 2022.
[50] J. L. Williams, R. L. Frank, and S. Gulwani, “Inductive program synthesis for symbolic execution,” in Proceedings of the 2016 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages and Applications, 2016, pp. 523–540.

Q: 这篇论文试图解决什么问题？

A: 这篇论文探讨了大型语言模型（Large Language Models，LLMs）在解决编程示例（Programming-by-Example，PBE）问题方面的有效性。PBE 旨在从输入输出示例中生成算法。这项研究的目的是评估 LLMs 是否能够“解决”PBE 问题，即是否能够有效地从少量示例中推断出能泛化到新输入的程序，而不依赖于自然语言的指导。

具体来说，论文试图回答以下几个问题：

  1. LLMs 在 PBE 任务上的表现如何？ 研究者通过在列表、字符串操作和图形编程等经典和非经典领域进行实验，评估了预训练模型在 PBE 上的有效性。
  2. 预训练模型与经过微调的模型在 PBE 上的差异是什么？ 研究者发现预训练模型在 PBE 上表现不佳，但通过微调可以显著提高性能，尤其是在测试问题与微调数据在相同分布的情况下。
  3. 什么因素导致这些模型在 PBE 中成功或失败？ 论文通过实证分析，探讨了模型成功和失败的原因，比如程序大小、先验和后验描述长度等。
  4. 如何实现更好的跨分布泛化？ 研究者提出了一种算法，通过使用少量未标记的数据集来适配 LLMs，以缩小域差距，从而提高模型在不同分布问题上的表现。
  5. LLMs 在 PBE 任务上的潜力和局限性是什么？ 论文不仅探讨了 LLMs 在 PBE 上取得的进展，还指出了它们在某些方面仍然存在的不足。

总的来说，论文试图通过实验和分析，评估 LLMs 在解决 PBE 任务方面的能力和局限，并探索提高模型泛化能力的方法。

Q: 有哪些相关研究？

A: 论文中提到了多项相关研究，以下是一些主要的相关工作：

  1. FlashFill [2, 4]: 一个在电子表格中自动执行字符串处理操作的系统，使用输入输出示例来合成字符串操作宏。
  2. DeepCoder [33]: 一个利用深度学习的程序合成系统，通过示例来指导代码生成。
  3. LambdaBeam [12]: 一个神经程序搜索系统，使用高阶函数和Lambda表达式。
  4. GPT-4 [16]: OpenAI 发布的一个大型语言模型，用于代码生成任务。
  5. DreamCoder [44]: 一个程序合成系统，使用唤醒-睡眠库学习来引导程序合成。
  6. Self-Instruct [30]: 一种通过自我生成指令来对齐语言模型的方法。
  7. Wake-Sleep 算法 [31]: 一种用于无监督神经网络的算法。
  8. RobustFill [18]: 一个在有噪声输入/输出下进行程序学习的系统。
  9. Codet [21]: 一个代码生成系统，通过生成测试来指导代码生成。
  10. Parsel [23]: 一个通过语言模型进行算法推理的系统。
  11. SpreadsheetCoder [5]: 一个用于从半结构化上下文中预测公式的系统。
  12. LOGO/Turtle 图形编程 [42]: 一个用于合成生成目标图像的程序的系统。

这些研究涵盖了从传统的符号搜索方法到利用神经网络和大型语言模型的现代程序合成技术。论文通过与这些相关工作的比较，展示了 LLMs 在 PBE 任务上的潜力和存在的挑战。

Q: 论文如何解决这个问题？

A: 论文通过以下步骤和方法解决大型语言模型（LLMs）在编程示例（PBE）问题上的应用和效果评估：

  1. 实验设计：在列表操作、字符串处理和图形编程（LOGO/Turtle）等不同领域进行实验，以测试LLMs在多种编程任务上的表现。
  2. 基本提示（Basic prompting）：使用预训练模型直接从输入输出示例生成程序，通过提示（prompting）方式进行。
  3. 微调（Fine-tuning）：为了提高性能，论文提出使用微调方法。这包括从小型手动构建的种子数据集开始，然后通过LLM生成新的程序和输入，通过执行程序来获取输出，从而构建一个用于微调的数据集。
  4. 自举数据生成：使用种子数据集通过LLM生成大量训练数据，这些数据随后用于微调LLM，使其能够根据输入输出生成程序。
  5. 适应性（Adaptation）：为了解决模型在新分布问题上的泛化能力不足，提出了一种适应性算法，通过迭代预训练、测试和将解决的问题添加回种子数据集来进行模型适应。
  6. 性能评估：通过与现有的符号搜索算法和商业系统（如FlashFill）进行比较，评估微调后的LLM在各个领域内的性能。
  7. 成功与失败的原因分析：研究了影响LLM在PBE任务中成功或失败的因素，包括程序大小、先验和后验描述长度等。
  8. 跨分布泛化（Out-of-distribution generalization）：探讨了LLM在训练数据分布之外的问题上的泛化能力，并使用适应性方法来提高这种能力。
  9. 实验结果：展示了微调后的LLM在各个领域的测试集上的性能，以及与现有技术的比较。
  10. 讨论与展望：基于实验结果，讨论了LLM在PBE任务中的潜力和局限性，并对未来的研究方向提出了展望。

通过这些方法，论文不仅评估了LLMs在PBE任务上的能力，还提出了提高其性能和泛化能力的具体策略。

Q: 论文做了哪些实验？

A: 论文中进行了一系列实验来评估大型语言模型（LLMs）在编程示例（PBE）任务上的表现。以下是实验的主要内容：

  1. 领域选择：实验涵盖了三个不同的领域：列表函数、文本编辑宏和图形程序设计（LOGO/Turtle）。
  2. 数据集准备：为每个领域准备了种子数据集，并使用这些种子数据集通过LLM生成大量训练数据。
  3. 微调模型：使用生成的数据集对DeepSeekCoder LLM进行微调，以提高其在特定PBE任务上的性能。
  4. 性能评估：
    • 在列表函数领域，使用了Rule等人2024年的数据集和Shi等人2023年的数据集。
    • 在文本编辑领域，使用了SyGuS问题和PROSE问题数据集。
    • 在图形程序设计领域，使用了Wong等人的LOGO/Turtle程序数据集。
  5. 基本提示方法：通过给定输入输出示例，直接使用预训练的LLM生成程序。
  6. 微调方法：评估微调后的LLM在各种PBE任务上的性能，包括列表函数、文本编辑和图形设计任务。
  7. 适应性方法：测试了适应性算法，通过在不同分布的问题上进行迭代训练，以提高模型在新问题上的泛化能力。
  8. 跨分布泛化测试：在训练和测试数据分布不一致的情况下，评估模型的泛化能力。
  9. 成功与失败因素分析：分析了影响模型成功或失败的因素，如程序大小、先验和后验描述长度。
  10. 与现有技术比较：将微调后的LLM与现有的符号搜索算法和商业系统（如FlashFill）进行比较。
  11. 定量结果分析：通过定量分析，展示了微调模型在各个领域的性能，包括解决问题的百分比和所需的搜索预算。
  12. 定性结果分析：提供了微调模型生成的程序示例，以及它们在特定任务上的表现。

这些实验结果表明，经过微调的LLM在PBE任务上取得了显著的进步，尤其是在特定领域内。同时，实验也揭示了模型在跨分布泛化方面的局限性，并提出了改进策略。

Q: 有什么可以进一步探索的点？

A: 论文中提出了一些可以进一步探索的点，以下是几个主要的研究方向：

  1. 更小的神经网络模型：研究者提到使用7B到33B大小的神经网络进行PBE可能对大多数终端用户不实用。因此，研究更小的神经网络模型及其在PBE任务上的有效性是一个重要的方向。
  2. 网络压缩和蒸馏：对于微调后的模型，研究网络压缩和蒸馏技术，以减少模型大小并提高效率，同时保持或提高性能。
  3. 自调试策略：尽管论文没有探索自调试策略，但这些策略可能有助于提高PBE的性能。研究如何让LLM尝试调试自己生成的代码，以改进不通过测试用例的代码。
  4. 代码生成排名方法：研究不同的方法来从LLM生成的程序集合中选择输出，这可能比简单的基于示例过滤更复杂。
  5. 提高跨分布泛化能力：尽管适应性方法在一定程度上提高了模型的泛化能力，但需要进一步研究如何更有效地处理分布外问题。
  6. 深入理解模型成功和失败的原因：研究者发现后验似然是预测模型成功的一个重要因素，但需要更深入地理解特定问题如何影响神经网络的后验分布。
  7. 更广泛的PBE任务和领域：扩展PBE任务的范围，探索LLMs在更多不同领域和更复杂的编程任务上的表现。
  8. 实际部署和用户研究：将PBE系统部署到实际环境中，并进行用户研究，以评估其在现实世界中的有效性和可用性。
  9. 与其他AI技术的集成：探索将LLMs与其他AI技术（如强化学习或元学习）结合，以进一步提高PBE系统的性能。
  10. 模型的可解释性和透明度：提高LLMs在PBE任务中的可解释性，以便更好地理解其决策过程。
  11. 模型的健壮性和安全性：研究如何提高模型在面对错误输入或恶意攻击时的健壮性和安全性。

这些方向可以帮助研究者更深入地理解LLMs在PBE任务上的能力，并推动该领域的进一步发展。

Q: 总结一下论文的主要内容

A: 这篇论文的主要内容可以总结如下：

  1. 研究背景：编程示例（Programming-by-Example，PBE）是一种通过输入输出示例生成算法的技术。PBE对于用户和AI领域都具有重要意义，因为它涉及到从少量示例中进行归纳推理，而不需要自然语言的指导。
  2. 研究目的：论文探讨了大型语言模型（LLMs）在PBE任务上的表现，并评估它们是否能够“解决”PBE问题。
  3. 实验设计：研究者在列表操作、字符串处理和图形编程（LOGO/Turtle）等不同领域进行实验，以测试预训练和微调后的LLMs在PBE任务上的有效性。
  4. 方法论：
    • 基本提示：直接使用预训练模型根据输入输出示例生成程序。
    • 微调：通过自举方法从小型种子数据集生成大量训练数据，然后微调LLM以提高性能。
    • 适应性：提出一种算法，通过迭代预训练、测试和将解决的问题添加回种子数据集来适应新的分布。
  5. 实验结果：
    • 微调后的模型在列表函数、文本编辑和图形设计任务上表现出色，超过了现有的符号搜索算法和商业系统。
    • 微调模型通常需要多次尝试才能生成正确的程序，但相比传统方法，所需的搜索空间较小。
    • 模型在跨分布泛化上存在挑战，但适应性方法能够在一定程度上提高其性能。
  6. 分析与讨论：
    • 研究者分析了影响模型成功或失败的因素，发现后验描述长度是预测成功的重要因素。
    • 论文讨论了LLMs在PBE任务上的潜力和局限性，并提出了未来研究方向。
  7. 结论：LLMs在PBE任务上取得了显著进展，能够解决多种编程问题，但仍然存在一些挑战，特别是在跨分布泛化方面。
  8. 相关工作：论文还讨论了与PBE相关的其他研究工作，包括传统的符号搜索方法、LLMs作为归纳推理器的应用，以及自我调试和代码排名方法。
  9. 局限性：论文指出了研究的局限性，包括模型大小对于实际部署的挑战，以及对于模型成功和失败原因理解的深度。
  10. 未来工作：提出了未来研究的方向，如探索更小的网络模型、提高跨分布泛化能力、深入理解模型的决策过程等。

论文通过一系列实验和分析，展示了LLMs在PBE任务上的应用潜力，并为未来的研究提供了方向。

发表评论