狡猾的霍比特人解决方案 (Tricksy Hobbitses solution)

“我口袋里有什么？”比尔博大声说道。他是在自言自语，但咕噜以为这是个谜语，吓得要命。
“嘶 - 嘶 - 嘶 - 嘶 - 嘶，”咕噜嘶声道。“它必须给我们三次猜测机会，我的宝贝，三次猜测机会。”
-- 《霍比特人》

背景

商业背景：https://www.kaggle.com/competitions/llm-20-questions
数据背景：https://www.kaggle.com/competitions/llm-20-questions/data

方法概述

• 双重字母二进制搜索 ("alpha") 加上纯在线 LLM 策略
• 基于单元词 (unigram) 的 alpha 代理，专注于长尾单个关键词，并通过 LLM 扩展查找名词短语
• 使用英语语言频率表更快地猜测高概率单词
• 通过 LLM 猜测者自动总结知识以保存和巩固上下文
• 100% 在线 LLM 提问者/猜测者，无预处理或离线问题
• 多模式问题类型以获取关键词的不同信息标签：类别、位置、大小以及枚举 + 拆分
• 回答时用关键词替换主语

流程图

性能评估

• 私有排行榜 (Private LB) 第 2 名 (alpha + LLM)
• 公共排行榜 (Public LB) 最高第 7 名 (仅 LLM)
• 私有排行榜匹配中 89% 的关键词查找率 (仅 alpha) - 见 分析
• 获胜 achieved 的平均奖励为 5.81 (仅 alpha) - 见 分析
• 在竞争性游戏过程中作为 LLM 提问者/猜测者的胜率为 12%
• 在竞争性游戏过程中作为 LLM 回答者的胜率为 11%
• 根据 此处 描述的自定义指标，在仅 LLM 匹配中团队结果排名第 7

源代码

完整代码可在 此处 获取

致谢

非常感谢所有竞争对手和比赛组织者，尤其是：

• Kaoutar @wouldyoujustfocus 和 Chris Deotte @cdeotte 提供的 starter notebooks 此处 和 此处，这无疑节省了我在 Kaggle 环境中让初始代理运行起来的数小时挫折时间
• Matthew S Farmer @matthewsfarmer 发现 了一种让 Llama 3.1 在 Kaggle 上运行的 hack 方法
• Loh-maa @lohmaa 彻底改变了竞争格局

提交详情

我的解决方案包含基于 LLM 增强的 alpha 二进制搜索和没有离线预处理的重度 LLM 代理。

我开始这个竞赛时试图为"things"类别构建一个基于 LLM 的解决方案，寻求首先解决挑战中最难的部分，然后为此构建"places"，结果证明后者变得无关紧要。我很晚才构建 alpha 二进制搜索，一旦很明显最终排行榜顶部会有一簇高胜率的 alpha 代理（这对于保持竞争力是必要的）。

正如我在 这里的评论 中提到的，即使少数代理采用这种策略也足以显著改变竞争动态。

对于 LLM，我使用 Llama 3.1 8B 8-bit 量化版本，没有微调，在我的测试中它略优于 Llama 3.0。

Alpha 提问者/猜测者

我采用了 @lohmaa 公共 notebook 中分享的"Is it Agent Alpha?"握手协议。这似乎是确定回答者是否 equipped 处理 alpha 二进制搜索问题的最直接方式。我想许多顶级回答者都会被编程来处理这种设置。

对于我的关键词数据库，我决定仅使用单词 (unigram) 关键词。我使用这个数据集：https://www.kaggle.com/datasets/rtatman/english-word-frequency 作为起点，通过两个 LLM 查询将 333,333 个单元词条目缩小到 120k：“它是一个有效的英语单词而不是首字母缩写或缩写吗？”和“外行人熟悉吗？”我尝试使用 Llama 进行词性标注以及各种其他过滤器，发现它非常不可靠。因此，我的 120k 数据集仍然充满了我没有花时间进一步过滤的垃圾词。

我的搜索算法尝试在尝试任何短语之前找到关键词的第一个单词。在初始搜索期间，它将在每个有效范围内使用最高频率的未使用单词作为其猜测（试图在其他 alpha 代理之前得到这个词）。

一旦第一个单词被明确识别（或者所有可能的单个单词都被排除考虑），算法进入第二阶段。在这个阶段，我使用 LLM 建议以第一个识别单词开头的可能名词短语。在第一个单词相当通用的情况下（例如"metal"、"electric"等），此策略可能会失败。然而，许多第一个单词会导致非常有意义的 LLM 提示短语（例如，我的代理能够从起始单词"fabric"预测出"fabric glue"。高度特定的术语，如"guinea pig"中的"guinea"无疑也会导致胜利。）

我在公共关键词上做了测试，以确定是否将我的单元词列表截断为 65k、32k 等，以便为更多名词短语猜测留出时间，但发现保持 120k 单元词的长尾提供了最佳性能。由于私有关键词列表似乎偏向于单个单词，我认为这个设计选择在第一阶段提供了非常好的关键词覆盖率。

回答者

我的回答者分两个阶段运行：

阶段 1： 查找字母顺序、列表检查或包含字母类型的问题。在这个阶段，我查找涉及单词拼写或列表检查的常见提示，因为 LLM 倾向于 poorly 回答这些问题类型。然后我使用 LLM 从提示中提取比较单词、字母或列表并计算手动比较。

阶段 2： 我使用 LLM 回答问题。一个非常重要的发现是，如果在尝试回答之前将关键词替换回提示中，LLM 的准确性会大大提高。因此，我的算法首先使用 LLM 确定句子的主语，然后用关键词替换主语。然后它回答问题。

我的性能指标表明，我的回答者在非 alpha 剧集的回答者中排名前 4%。

在线 LLM 提问者

我的 LLM 不使用任何离线或预先准备的问题。我曾经构建过一个离线提问者机器人，但确定我的在线 LLM 更好，所以我的最终提交仅使用我的在线机器人。
LLM 以四种不同的模式运行，按顺序处理：

1. 类别 (Category)
2. 位置 (Location)
3. 大小 (Size)
4. 枚举 + 拆分 (Enumerate+Split)

类别模式

在类别模式期间（通常是前 12 个问题），LLM 寻求将其当前的“类别”划分为两个 separate 非重叠空间，从"things that are tangible objects"开始。为此，我使用以下提示：

Divide the category "[prior category] that are [category]" into two broad, clearly-defined, non-overlapping sub-categories, ensuring that all [prior category] that are [category] fall into one category or the other, but not both. Respond with the names of the two sub-categories separated by a comma only. Do NOT repeat the original category. Use common phrasing. Each sub-category must be a noun or noun phrase.

对于这个提示，category 指的是最具体的已知类别，prior category 指的是前一步找到的类别。

提示产生两个子类别候选。我依次测试两者。如果一个返回'yes'响应，算法采用这个作为其当前类别并继续深入。如果两个都没有返回'yes'，则对另外两个子类别候选重复相同的过程。在连续四次失败或总共 12 个问题后，算法进入下一个模式。

我在前进之前需要正面确认，并且小心不要假设否定响应意味着相反的是真的，因为实际上我的类别划分可能无法覆盖 100% 的可能实例。

例如，对于关键词"fox"，这种方法通常会确定关键词类似于："a terrestrial mammal that is a predator"或"a predator that is a forest stalker"。

位置模式

在位置模式中，我枚举关键词可能被发现的可能位置，使用以下提示：

Provide several broad categories of locations where [prior category] that are [category] are most often located. Respond with the category names in comma-separated format only.

然后，算法使用最多 5 个问题来询问关键词是否位于每个枚举的位置。一旦返回正面响应，该位置被存储以供将来参考，算法进入其大小模式。

大小模式

在“大小”模式期间，LLM 基本上重述两个问题：Is it small? Is it large? 希望这两个中的一个能返回正面结果。

枚举 + 拆分模式

一旦类别、位置和大小模式都已耗尽，LLM 默认回退到其枚举 + 拆分模式。这实际上是我编码进入竞赛的第一个条目，并且在提出聪明问题方面仍然相当不错。它分两个阶段运行：枚举可能的选择，然后创建一个问题来拆分选择。

在枚举阶段，我使用以下提示：

Create a list of 30 [prior category] that are [large/small] [category] typically located in or at [location], matching the following description: [summary – see below]. The things must be unique, diverse, [category items] and as different as possible from each other. The [category items] must be common examples of [category items] and representative of a range of different possible options. The things must represent examples of as many different categories of [category items] as possible. The answer should be returned as a comma-separated list with no additional verbose output. None of the [category items] may be repeated. Each item in the list should be as different as possible from the prior item. No words in the list may be repeated. Respond with the comma-separated list only. Order the responses according to the most likely or common choices according to the criteria above.

上面提到的 summary maintained 在猜测者代码中，我将在稍后更详细地描述。

这个提示倾向于生成一个相当好的列表，包含 30 个左右可能是关键词的代表性事物示例。然后我尝试找到一个问题将列表分成两半，如下所示：

Create a simple yes-or-no question, responding with the question only and no introduction or additional verbose details. The question should broadly categorize and divide the following into two equally-sized lists: [output from the prior prompt] Do not include questions similar, equivalent, or directly opposite to the following: [all prior questions] Ensure that the question is simple, unambiguous, clear, and can be answered either yes or no. Do not create compound questions. The question may explore different aspects or characteristics of the list items including size, appearance, function, location, usage, and other defining characteristics. The question should create a general or broad classification of the two categories and should not be overly specific.

有时这个提示会导致一个非常巧妙的查询。其他时候它会问相当琐碎、重复或抽象的问题。所以这是碰运气的。但是，如果我之前的模式工作得相当好，并且我有具体的类别、位置和大小可以使用，这个默认模式通常可以提出智能问题来进一步缩小选择集。或者，至少，我争取时间来尝试在我已知的类别/位置/大小内进行更多猜测。

在线猜测者

我的猜测者以段落形式保持对其对关键词理解的运行总结。在每个问题和答案之后，它将更新总结以反映获得的新信息（并丢弃冗余或冲突的数据）。我发现，当给 LLM 提供对象的 nice 自然语言描述时，它的表现比让它每一轮都试图解析一堆是/否问题要好。这个总结既被猜测者使用，也被上面描述的“枚举 + 拆分”模式使用。

我发现这种自动总结通常允许我的猜测者从不可靠回答者提供的错误答案中恢复，实际上提供了一致信息的更大注意力。

在选择答案时，猜测者使用上面描述的默认模式的第一个提示来枚举 30 个可能的关键词选项。在排除已经做出的猜测（或在公共关键词列表中）后，我的算法简单地猜测第一个呈现的选择，因为那是 LLM 认为最可能的答案。