阅读列表:3

1. GCD: [2305.13971] Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning

   • Saibo Geng,Martin Josifoski, Maxime Peyrard,Robert West
   • EMNLP2023; Ar5iv

   当前可控生成的问题：

   • 如果不用高质量的数据微调，LLM 还是很难采样出可靠的结构化序列，因此引入 grammar constrained decoding
   • 当前大部分 GCD 都在特定任务上（such as parsing or code generation），本文想做一个抽象并泛化，论证 GCD 可以在更多任务上适用
   • argue that GCD can serve as a unified framework for structured NLP tasks in general.
   • 为此，引入了 input-dependent grammars, 语法是由输入决定的，因此不同输入可以有不同结构化的输出，在三类任务上展示了效果：
     • information extraction
     • entity disambiguation
     • constituency parsing.
   • 作者认为 GCD 在监督数据少的情况下有很大应用空间

   要确认的问题：

   • code generation 和 parsing 如何使用了 GCD
   • 作者如何形式化定义 GCD 问题？
   • 是否考虑了分词问题
   • 未来研究点是什么，还值得哪些研究

   作者围绕 closed information extraction (cIE), entity disambiguation(ED), or constituency parsing (CP) ，这些任务是要求在某个词库内的选择词汇

   从 intro 来看，作者实际是编写了一个类似 parser 的算法，把文法语言翻译成了能够限制 transformer 输出的结构，作者做的是类似设计正则语言，实际是一个设计了一个 DSL, 解释器是解码策略。个人觉得这是一个好的 idea

   过去的研究对每个问题都要用单独的 finite-state automata or trie-based data structure 来实现，每次实现是很繁琐的。

   有些语法规则是要基于输入序列的，比如 dependency parsing

   提到了一般我们是写 Grammar level 的语法，但是我们需要在 Token level 进行限制。 用的是 Grammatical Framework （GF）来定义字粒度语法和 subword 粒度语法 可以定义抽象语法和具体语法，而在本文中对应的就是字粒度和 subword 粒度语法

   局限和未来工作 :

   以下提到了 token-level 和 subword 相关问题，但不确定

   This approach is, however, not principled and relies on a specific tokenizer. We therefore believe that a principled approach for defining token-level grammars is an interesting direction for future work.

   提到的另一个 future work 是如何编写高效的 incremental parser

引用了 GCD2023

1. GP4DSL: [2305.19234] Grammar Prompting for Domain-Specific Language Generation with Large Language Models

   • Bailin Wang, Zi Wang, Xuezhi Wang, Yuan Cao, Rif A. Saurous, Yoon Kim
   • Bailin Wang ：About me - Parsing Papers → Epoch 7
   • MIT, deepmind/google, NeurIPS 2023 Ar5iv

   解决核心问题是：

   • 要生成可执行的 DSL 代码，光靠 in-context-learning 的一些例子是不够的
   • DSL 在 LLM 预训练数据集里是很少的，而且一直有新的 DSL 出现

   做法是：

   • 把 ICL 中的 few-shot example 改成一个 BNF 文法，先预测文法，再从文法 parsing 出特定语言
   • 这种做法和 step by step 思想类似，先生成中间状态，只不过后面的解析是形式化的，可以用来操作 LLM?
   • 和 GCD 有许多相似之处

   未来研究：

   • 似乎又只有应用层和更复杂场景？或者高效采样问题

引用了： GCD2023

和 KCTS2023

[2310.09044] KCTS: Knowledge-Constrained Tree Search Decoding with Token-Level Hallucination Detection

• Sehyun Choi, Tianqing Fang, Zhaowei Wang, Yangqiu Song

• EMNLP2023 Ar5iv

  针对的是 LLM 幻觉问题，要引入事实知识，在解码的时候用一个判别器来引导模型生成符合事实的文本，同时 token level 的预测器来预测未来的 reward, 如果 reward 低了说明偏离事实，用的是 Reward Inflection Point Approximation (RIPA). baseline 是微调方法，微调方法对数据和计算要求都更高

  对句子判断是否 hallucination 的方法是，用 NLI 中蕴含的方式，即 LLM 输出的句子 y 蕴含某个事实

引用了 GP4DSL2023

[2310.15164] LINC: A Neurosymbolic Approach for Logical Reasoning by Combining Language Models with First-Order Logic Provers

• Theo X. Olausson, Alex Gu, Benjamin Lipkin, Cedegao E. Zhang, Armando Solar-Lezama, Joshua B. Tenenbaum, Roger Levy

• EMNLP2023 outstanding; MIT CSAIL; Ar5iv

  这是一篇推理增强文章，主要对比 CoT, 并分析了不同 failures modes 把自然语言给 LLM 做一个 parser 翻译成中间的形式化语言，然后再用一阶逻辑推理器去演绎，使用工具，核心要解决的是：

  双阶段的问题，第一个阶段的错误会被放大： 形式化过程需要完美捕捉前提中的所有相关信息，任何信息的丢失都可能导致错误的结论。由于尚不清楚这种形式化任务与端到端自然语言推理的难度比较，作者的主要兴趣是比较他们的神经符号方法与现有推理策略（例如“思维链”）的差异。这表明，工作重点不在于优化大模型的形式化步骤，而是在于整体比较这些不同的推理方法。

  提到： Modus Tollens, 可以表述为：“如果 P 则 Q，不 Q，因此不 P”

  对推理能力质疑的描述

  These findings suggest that such models may be relying on approximate heuristics based on surface-level statistical patterns in reasoning tasks, rather than consistent, generalizable representations and strategies

  在附录 A 里写了未来可能工作：

  • 其中一个点是用 CFG 限制采样，提到文章是：

1. [2308.01285] Flows: Building Blocks of Reasoning and Collaborating AI

   • Martin Josifoski, Lars Klein, Maxime Peyrard, Yifei Li, Saibo Geng, Julian Paul Schnitzler, Yuxing Yao, Jiheng Wei, Debjit Paul, Robert West
   • Ar5iv, 作者核心团队和 GCD 重叠，作者很多，因为论文包括一个概念性框架描述和一个开源库，库的内容类似 langchain 同时还有额外的可视化支持，因此工程量较大。202312 正在评审中

   本文提出的是一个概念框架：Flows; 同时实现了 aiFlows 库。 结构化使得在竞赛代码任务上有 21 提高，该库还能让人参与交互（目前不太关心） 这是一篇实现通用 agent 的框架

2. Constrained Language Models Yield Few-Shot Semantic Parsers - ACL Anthology

   • Richard Shin, Christopher Lin, Sam Thomson, Charles Chen, Subhro Roy, Emmanouil Antonios Platanios, Adam Pauls, Dan Klein, Jason Eisner, Benjamin Van Durme
   • EMNLP2021; 微软； Ar5iv

   介绍了 semantic parsing 任务：根据自然语言输入生成结构性意义表征（比如 tree），但语言模型输出的是自然语言，因此作者用某种方式使得模型输出一种可以转换成语义表征的形式化的语言

   prompt 对与常见的通用问题是有用额，但对于 task-specific semantic parsing 效果不行，因为任务特定场景的数据很少

3. PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models - ACL Anthology

   • Torsten Scholak, Nathan Schucher, Dzmitry Bahdanau
   • EMNLP2021; Ar5iv

   是在生成 sql 上，这个几乎和微软的 Synchromesh 方法一样，所以微软如何发出这个论文？

   首先提到，(Yin and Neubig, 2018; Lin et al., 2019; Wang et al., 2020). 已经有方法做语法限制的采样了： For a while now it has been possible to restrict auto-regressive decoding to only those token sequences that correctly parse to SQL abstract syntax trees

   接着 (Rubin and Berant, 2021). 在这个范式上继续用 semi-auto-regressive 提高了效率？

   这个范式的问题是： using a custom vocabulary of special control tokens or a custom model architecture, or both.

   作者提到了比以上范式更好的方法： (Suhr et al., 2020; Lin et al., 2020) 直接对 beam 结果进行过滤。

   作者提到了不同限制级别：

   • Lexing
   • Parsing without Guards
   • Parsing with Guards

   这个三年前论文就把问题讲了，我需要重新考虑研究点

4. [2201.11227] Synchromesh: Reliable code generation from pre-trained language models.

   • Gabriel Poesia, Oleksandr Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, Sumit Gulwani
   • 微软团队，Ar5iv

   其中包括两个点，一是用 RAG 方式找到 Incontext learning 的例子，让模型输出更符合语法 这里提出的叫做 Constrained Semantic Decoding, 而不是 Syntactical decoing

   重点是第三章对 CSD 的详细描述：类似人用 LSP 进行编程，当输入某个 trigger word 的时候，LSP 会推荐所有可能的选项，比如输入 str. ，补全引擎只会给出 str 对象所包含的方法或者属性，这需要一种 partial parsing 的能力

   (NO_ITEM_DATA:poesiaSynchromeshReliableCode2022)

   在附录 D 和 E 谈到了 CSD BPE 的问题，这是第一次看论文有提到这个问题，而该论文团队是微软，和 guidance 一样，后者也有 token healing 问题

   该论文官方没有公开代码，但有其他人实现了其中的采样 CSD kanishkg/synchromesh: Get language models to generate code reliably. Open source implementation of Synchromesh: Reliable code generation from pre-trained language models. 并且论文一作 Gabriel Poesia 对此有贡献，该作者一直是研究自动数学推理，可以关注

5. NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints - ACL Anthology

   • Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula, Yejin Choi
   • Naacl2021; Ar5iv

   修改历史

   提到了 lexical constraints, 传统方式是在数据集上微调，但本文方法则在解码端优化，任何谓词逻辑限制都可以处理，并且渐进复杂度等于 beam search

   这里的问题是：

   • 什么问题场景下会需要要用到谓词逻辑来限制采样时的 lexicon? 这些例子有说服力吗？放在 gpt4 里还有这个问题吗？这是一个核心问题，要读更多的论文才能回答
   • 如何用谓词逻辑限制 用谓词逻辑可以表达更复杂限制，比如 inflection or synonyms (‘beef’ or ‘steak’ both satisfy the constraint of referring to the steak)

   • 作者如何设计这个算法 将 hard logic 转换成了解码中的 soft penalty ，再基于 beam search 找到近似最优解

     分成了四个限制状态：

     • S1: reversible unsatisfaction: 限制没有完全被满足，但其中包括白名单，可以在后续过程中被满足
     • S2: irreversible unsatisfaction: clause 里只包含黑名单，比如器中吧不允许出现 book, 但目前采样中已经出现，因此约束不可能被满足， 这时候只有重头采样（或者回溯？）
     • S3: reversible satisfaction: 如果限制都是黑名单，那么不采样也满足限制了，但如果一旦采样到一个违禁词，就变成不满足了，因此是 reversible 的
     • S4: irreversible satisfaction: 如果限制中至少包括一个白名单，那么一旦满足该名单，就变成可满足状态了，由于是 CNF 性质，那么该限制永远是 true

     我们只需要对 reversible 的状态，也就是 S1 和 S3 进行追踪 对于 S2 和 S4, 由于都是不可逆，也就是状态不会再变化了，他们都属于 final 形态，实际会被包含在 S1 和 S3 追踪过程中。 作者设计了两个 trie 树，分别追踪 S1 和 S3 也就是以下表格第一列里还没有被满足的白名单和已经被满足的黑名单。 记为 T+ 和 T-, 如果某个白名单被满足，根据 CNF 性质，Clause 将用真，因此进入到状态 S4, 这时就不需要追踪这个 clause 状态了，如果某个黑名单被违反，那么将这个黑名单从 T- 移除，如果某个 clause 的所有黑名单都被违反

     	Unsatisfaction	Satisfaction
     reversible	S1: !book or paper	S3: !book or paper
     irreversible	S2	S4

   • 算法实现的描述是怎么样的？ 在 beam 的基础上使用 pruning, grouping, and selecting 但这里核心还是得看代码，作者是自己实现的还是基于哪个采样库实现的，如何维护这么多 beam 和 trie 状态。 这部分更属于工程或者算法实践，不放在论文阅读中了
   • 作者如何分析复杂度等同于 beam search

   提到数据集： CommonGen, recipe generation 等

   至少提到 6 个受限解码的相关工作，包括：

   • constrained beam search (CBS): 有限状态机来追踪 2^c 所有限制，复杂度太高
   • grid beam search (GBS)
     • dynamic beam allocation for GBS
     • GPU effecient GBS
   • Constrained Generation by Metropolis-Hastings Sampling CGMH
     • Gradient guided CGMH

   问题是，这些算法作者是否有复现对比？

   为什么实验中要区分 Supervised Model 和 Unsupervised Model

   实践价值：

   • 可以尝试很多模型，包括 GPT-2, UniLM-v2, BERT-Gen, BART, T5
   • 可以了解很多测评手段，包括 BLEU, ROUGE, METEOR, CIDEr, and SPICE, concept Coverage
   • 实验设计，比较严谨，包括对训练数据和模型大小的 ablation, 合作者多的话，比如三个人一起做，工作量也不会很大。 对某个数据集，做充分实验，然后对其他类似的，给出核心实验即可。

   (NO_ITEM_DATA:luNeuroLogicDecodingSupervised2021)

   用词： In stark contrast

6. [2205.12615] Autoformalization with Large Language Models

   • Yuhuai Wu, Albert Q. Jiang, Wenda Li, Markus N. Rabe, Charles Staats, Mateja Jamnik, Christian Szegedy
   • Ar5iv; Google; NeurIPS2022

   在 semantic parsing 、代码生成之外出现了一个新的描述 Autoformalization(自动形式化), 是将自然语言数学自动转换为形式验证和证明的过程。 我们惊人地发现，大型语言模型可以正确地将相当一部分（25.3%）数学竞赛问题完美地转化为 Isabelle/HOL 中的形式化规范。 通过对自动形式化定理进行训练，改进了之前推出的神经定理证明器，从而证明了这一过程的实用性。我们的方法在 MiniF2F 定理证明基准上取得了最新成果，将证明率从 29.6% 提高到 35.2%。

   这里是一种训练方法 作者报告： https://www.youtube.com/watch?v=_pqJYnQua58

1. CODE2ICL: [2311.09519] Leveraging Code to Improve In-context Learning for Semantic Parsing
   • Ben Bogin, Shivanshu Gupta, Peter Clark, Ashish Sabharwal
   • Ar5iv

2. 2019 Constrained Decoding for Neural NLG from Compositional Representations in Task-Oriented Dialogue - ACL Anthology

   • Anusha Balakrishnan, Jinfeng Rao, Kartikeya Upasani, Michael White, Rajen Subba
   • ACL2019, Meta 团队

   该问题出现在 task-oriented conversational systems, 这实际是一个需要调用工具的对话系统，比如 siri 聊天可以进行网页搜索。

   使用传统形式语言生成中树结构来引导生成，有一些概念：

   • MR: meaning representations

   Reference 1 JJ’s Pub is not family friendly, but has a high customer rating of 5 out of 5. It is a restaurant near the Crowne Plaza Hotel.

   Reference 2 JJ’s Pub is not a family friendly restaurant. It has a high customer rating of 5 out of 5. You can find it near the Crowne Plaza Hotel.

   E2E MR name[JJ’s Pub] rating[5 out of 5] familyFriendly[no] eatType[restaurant] near[Crowne Plaza Hotel]

   完整三个例子如上，这能说明什么

   这三个例子展示了如何将自然语言描述转换为结构化的语义表示（Meaning Representation, MR）。两个参考回应（Reference 1 和 2）虽然在措辞上有所不同，但传达了相同的信息：JJ's Pub 是一个顾客评分高、不适合家庭、靠近 Crowne Plaza Hotel 的餐馆。E2E MR 则是将这些信息以结构化格式展现，清晰地列出了餐馆的名称、评分、家庭友好度、类型和位置。这种转换是自然语言生成和理解任务中常见的，特别是在需要从自然语言文本中提取并结构化信息的应用场景中。

3. [2305.12018] BOLT: Fast Energy-based Controlled Text Generation with Tunable Biases
   • Xin Liu, Muhammad Khalifa, Lu Wang
   • ACL2023 short; Ar5iv
4. [2112.08726] NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics
   • Ximing Lu, Sean Welleck, Peter West, Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ronan Le Bras, Lianhui Qin, Youngjae Yu, Rowan Zellers, Noah A. Smith, Yejin Choi
   • NAACL2022; Ar5iv
5. [2010.12884] NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints
   • Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula, Yejin Choi
   • NAACL 2021; Ar5iv
6. MuCoLa: [2205.12558] Gradient-Based Constrained Sampling from Language Models
   • Sachin Kumar, Biswajit Paria, Yulia Tsvetkov
   • EMNLP 2022; Ar5iv
7. [2202.11705] COLD Decoding: Energy-based Constrained Text Generation with Langevin Dynamics
   • Lianhui Qin, Sean Welleck, Daniel Khashabi, Yejin Choi
   • NeurIPS 2022; Ar5iv

8. [2010.00904] Autoregressive Entity Retrieval

   • Nicola De Cao, Gautier Izacard, Sebastian Riedel, Fabio Petroni
   • ICLR 2021; Ar5iv

   ENTITY RETRIEVAL 和 NER 的区别是什么？ 前者对 entity linking and open-domain question answering 很重要， entity linking 作用是什么

   • Entity Retrieval 是对某个文本进行知识库实体的归类，比如某人写了一个新的文章发布在网上，维基百科机器人读取到了，于是它要给这个文章添加一个或多个与维基百科文章有关的标签，比如可能新的文章是维基百科里关于"正则表达式" 的一部分
   • 另外的应用是带检索的对话系统，比如对话时给出某个知识库里最相关的几个概念的百科页面

   当前方式是把实体的 meta 信息做成向量代表这个实体，然后把上下文编码之后与所有的实体响亮做点积（求 cos 距离），然后求排序求最接近的实体

   提到了 sub-linear search Critically, this formulation enables sub-linear search using modern maximum-inner-product-search libraries (Johnson et al., 2019) and hence supports retrieving from large entity databases

   提到了 Wikipedia title 一般有 6 个 BPE token, 因此在 beam search 的时候确实是在 BPE level 上的

9. GenIE: Generative Information Extraction - ACL Anthology
   • Martin Josifoski, Nicola De Cao, Maxime Peyrard, Fabio Petroni, Robert West
   • NAACL2022; 和上一篇同一个团队
10. [1902.06022] A Fully Differentiable Beam Search Decoder
    • Ronan Collobert, Awni Hannun, Gabriel Synnaeve
    • ICML; Facebook ； Ar5iv
11. [2106.07400] Determinantal Beam Search
    • Clara Meister, Martina Forster, Ryan Cotterell
    • ETH Zürich 和剑桥大学； Ar5iv
    • ACL2021
12. [2211.13813] Multi-label Few-shot ICD Coding as Autoregressive Generation with Prompt
    • Zhichao Yang, Sunjae Kwon, Zonghai Yao, Hong Yu
    • AAAI2023; Ar5iv
    • 医疗 ICD 解码， beam, trie
13. [1902.00592] An end-to-end Generative Retrieval Method for Sponsored Search Engine –Decoding Efficiently into a Closed Target Domain
    • Yijiang Lian, Zhijie Chen, Jinlong Hu, Kefeng Zhang, Chunwei Yan, Muchenxuan Tong, Wenying Han, Hanju Guan, Ying Li, Ying Cao, Yang Yu, Zhigang Li, Xiaochun Liu, Yue Wang
    • Baidu Ar5iv
14. Improved Pseudo Data for Machine Translation Quality Estimation with Constrained Beam Search - ACL Anthology
    • Xiang Geng, Yu Zhang, Zhejian Lai, Shuaijie She, Wei Zou, Shimin Tao, Hao Yang, Jiajun Chen, Shujian Huang

    • huawei

      (NO_ITEM_DATA:zhangOpenVocabularyLearning2019)