偏序上上下文学习的可识别性与序维度限制

# 部分序上上下文学习的可识别性与序维度限制  
来源：https://arxiv.org/html/2608.14004  
Faizanuddin Ansari  
附属机构：印度统计研究所  
附属机构：印度加尔各答  
附属机构：[[email protected]](mailto:[email protected]?subject=[From%20arXiv]%20PosetICL%20Paper)  
Swagatam Das  
附属机构：印度统计研究所  
附属机构：印度加尔各答  
附属机构：[[email protected]](mailto:[email protected]?subject=[From%20arXiv]%20PosetICL%20Paper)  

###### 摘要  
上下文学习通常被形式化为从函数的示例中进行推断。然而，部分序结合了传递性、反对称性和不可比性，因此一个有限的提示可能无法确定一个查询的比较关系。我们发展了一种部分序上上下文学习的理论，该理论分离了逻辑可识别性、提示教学成本、结构复杂性以及形式化坐标解码器类的精确容量。版本空间语义使背景知识和开世界与闭世界假设变得显式。对于包含正负比较的有限开世界提示，我们证明了一个精确的完成三歧性定理：在对正示例进行自反对传递闭包之后，一个查询会被强制为真，或因为每个真实完成都会创建一个循环或违反负示例而被强制为假，或者保持真正的模糊性。对于一个已知的 \(n\) 元素全集，我们将开世界教学数表征为覆盖数加上一个阻塞集击中数，证明其在所有 \(n\) 元素偏序集上的最大值为 \(n(n-1)\) 且由反链唯一达到，并将阻塞项识别为开世界而非完整哈斯语义的精确成本。我们形式化了依赖于提示的 \(s\) 坐标解码器，并使用经典的坐标序等价关系得到一个精确的表示边界：维度至多为 \(s\) 是必要且充分的，而宽度至多为 \(s\) 是一个方便的充分条件。  

###### 附录摘要  
本附录提供了扩展的证明、边界情况检查，以及正文中确定性模糊性示例背后的精确枚举结果。结果使用前缀 S，开头的映射将每个正文中的结果链接到此处的相应陈述。我们还给出了完整的类最大化教学论证、开世界与闭世界教学的比较、精确的坐标解码器能力边界，以及结构概览表背后的细节。  

## 1 引言  
大型语言模型可以在没有参数更新的情况下，从提示中的演示适应到任务，这种能力被称为上下文学习（ICL）<sup>3</sup> ([1](https://arxiv.org/html/2608.14004#bib.bib1))。许多理论研究从一个未知函数中采样提示，并要求模型预测新输入上的函数值<sup>10</sup> ([2](https://arxiv.org/html/2608.14004#bib.bib2))；<sup>1</sup> ([3](https://arxiv.org/html/2608.14004#bib.bib3))；<sup>5</sup> ([4](https://arxiv.org/html/2608.14004#bib.bib4))；<sup>12</sup> ([5](https://arxiv.org/html/2608.14004#bib.bib5))；<sup>2</sup> ([6](https://arxiv.org/html/2608.14004#bib.bib6))。统计分析在生成假设下表征贝叶斯最优或信息受限的 ICL<sup>14</sup> ([7](https://arxiv.org/html/2608.14004#bib.bib7))。这些表述很有价值，但许多推理任务是关系型的，而非单值的。  

一个部分序 \(\preceq\) 是自反、反对称和传递的，并且可能使某些元素对不可比较。有限偏序集由哈斯图表示，而可比性是在覆盖图的自反对传递闭包中的可达性<sup>7</sup> ([17](https://arxiv.org/html/2608.14004#bib.bib17))；<sup>20</sup> ([18](https://arxiv.org/html/2608.14004#bib.bib18))。因此，偏序集暴露了函数学习抽象可能掩盖的两个困难。首先，缺失的证据与不可比性的证据不同。其次，即使关系被完全指定，其结构可能需要几个独立的序坐标或长的传递证书。先前的一项实证研究引入了线性序和整除关系的提示，并报告了在当前语言模型上的性能饱和<sup>8</sup> ([23](https://arxiv.org/html/2608.14004#bib.bib23))。本研究探讨关系型提示在逻辑上确定了什么，需要多少标签来教学一个有限偏序集，以及哪些偏序集允许通过形式化指定的坐标序表示进行精确解码。  

我们的框架包括一个背景理论 \(\mathcal{B}\)。这一点很重要，因为一个命名“自然数上小于关系”的提示可能允许从预训练中进行语义回忆，而一个仅包含偏序集公理的抽象关系符号则允许多种补全。我们通过版本空间<sup>16</sup> ([21](https://arxiv.org/html/2608.14004#bib.bib21)) 来区分这些情况。我们还区分了开世界语义（未提及的关系可能成立）和闭世界语义（显示的有限哈斯图被声明为完整）<sup>18</sup> ([22](https://arxiv.org/html/2608.14004#bib.bib22))。  

### 贡献。  
(1) 我们使用一个固定已知全集上与演示和背景知识一致的偏序集版本空间，形式化关系型 ICL。  
(2) 我们证明了一个关于包含正负比较的有限开世界提示的精确真/假/未知完成定理，并给出了其每查询的分类成本。  
(3) 我们通过覆盖标签和阻塞集击中问题表征了最优的开世界教学提示，推导了精确的链和反链值，并证明了紧的类最大值 \(n(n-1)\)。  
(4) 我们使用高度、宽度、序维度以及正负证书来组织结构难度，并为依赖于提示的单调坐标解码器建立了一个精确的能力边界。  

### 概述。  
本文从逻辑转向教学、表示和认证。我们首先通过一个固定全集、一个背景理论和一个版本空间形式化关系型提示，明确区分了开世界和闭世界语义。然后我们刻画了何时一个查询的比较被强制为真、被强制为假，或真正模糊，并通过对四个元素偏序集的详尽枚举来说明这种三歧性。接下来，我们确定教学整个有限偏序集所需的标签，并分离出开世界语义产生的额外成本。最后，我们比较代表性的偏序集族，建立坐标序解码器的精确能力边界，分析正负证书，并得出该框架的含义、范围和限制。  

## 2 相关工作与定位  
### ICL 的机制与限制。  
函数学习、隐式优化、贝叶斯和任务表征的 ICL 解释由 <sup>10</sup> ([2](https://arxiv.org/html/2608.14004#bib.bib2))、<sup>1</sup> ([3](https://arxiv.org/html/2608.14004#bib.bib3))、<sup>5</sup> ([4](https://arxiv.org/html/2608.14004#bib.bib4))、<sup>14</sup> ([7](https://arxiv.org/html/2608.14004#bib.bib7)) 和 <sup>13</sup> ([8](https://arxiv.org/html/2608.14004#bib.bib8)) 提出。最近的机械性研究在选定的注意力头或低维激活子空间中发现了任务信息<sup>24</sup> ([9](https://arxiv.org/html/2608.14004#bib.bib9))。同期 2026 年的一篇预印本开发了结构化 ICL 的概念子空间解释<sup>19</sup> ([10](https://arxiv.org/html/2608.14004#bib.bib10))。这些发现启发了下面定义的显式提示依赖坐标解码器。  

### 关系型与图推理。  
LLMs 已在图问题和关系型数据库上进行过研究<sup>21</sup> ([15](https://arxiv.org/html/2608.14004#bib.bib15))；<sup>22</sup> ([12](https://arxiv.org/html/2608.14004#bib.bib12))。同期 2026 年的一篇预印本通过支持可识别性和关系标签覆盖来分析关系型数据库 ICL<sup>4</sup> ([11](https://arxiv.org/html/2608.14004#bib.bib11))。那些设定关注数据库预测。我们转而研究数学偏序集的逻辑补全，并使用序维度作为表示不变量。Transformer 的表达性结果在适当构造下建立了普适性<sup>17</sup> ([13](https://arxiv.org/html/2608.14004#bib.bib13))；<sup>9</sup> ([14](https://arxiv.org/html/2608.14004#bib.bib14))；它们并不意味着一个有限提示能唯一确定其目标。  

### 序理论。  
Dushnik-Miller 维度是交集为一个偏序集的线性扩展的最小数目<sup>7</sup> ([17](https://arxiv.org/html/2608.14004#bib.bib17))；<sup>20</sup> ([18](https://arxiv.org/html/2608.14004#bib.bib18))。有限整除序的维度具有成熟的组合学理论<sup>15</sup> ([20](https://arxiv.org/html/2608.14004#bib.bib20))。我们使用这些经典结果，而不是声称它们是新的；我们的贡献在于它们与一个精确限制的 ICL 表示类的联系。  

## 3 形式模型  
固定一个有限的已知全集 \(U\)。每个目标 \(P=(U, \preceq_P)\) 和背景理论 \(\mathcal{B}\) 中的每个假设都具有相同的论域。我们用 \(\mathcal{D} := (\mathcal{D}^+, \mathcal{D}^-), \quad \mathcal{D}^+, \mathcal{D}^- \subseteq U \times U,\) 来表示提示中的有标签关系证据，其中：  
- • \((x,y) \in \mathcal{D}^+\) 是一个正示例，断言 \(x \preceq_P y\)；  
- • \((x,y) \in \mathcal{D}^-\) 是一个负示例，断言 \(x \not\preceq_P y\)。  

因此，\(\mathcal{D}\) 表示提示的完整有标签演示部分，不包括查询。我们用 \(\|\mathcal{D}\| := \|\mathcal{D}^+\| + \|\mathcal{D}^-\|\) 表示演示的总数。查询 \(q=(a,b) \in U \times U\) 询问是否 \(a \preceq_P b\)。类 \(\mathcal{B}\) 可能还编码了关系语义或完整性假设。固定公共论域 \(U\) 使得每个演示对和每个查询对 \(\mathcal{B}\) 中的每个假设都是明确定义的。  

###### 定义 1（版本空间与可识别性）  
对于一个偏序集 \(P=(U, \preceq_P)\)，令 \(R_P := \{(x,y) \in U^2: x \preceq_P y\}\) 表示其序关系的图。给定一个有标签的演示集 \(\mathcal{D} = (\mathcal{D}^+, \mathcal{D}^-)\)，它在背景理论 \(\mathcal{B}\) 下的版本空间为  
\[
\mathcal{V}_{\mathcal{B}}(\mathcal{D}) = \bigl\{P \in \mathcal{B}: \mathcal{D}^+ \subseteq R_P, \quad \mathcal{D}^- \cap R_P = \varnothing\bigr\}.
\]  
当 \(\mathcal{V}_{\mathcal{B}}(\mathcal{D}) \neq \varnothing\) 时，提示 \(\mathcal{D}\) 在 \(\mathcal{B}\) 下是可满足的。对于一个可满足的提示，如果  
\[
\left\|\left\{\mathbf{1}[a \preceq_P b]: P \in \mathcal{V}_{\mathcal{B}}(\mathcal{D})\right\}\right\|=1,
\]  
则查询 \(q=(a,b)\) 是被识别的。  

一个二元答案规则对于 \((\mathcal{B}, \mathcal{D}, q)\) 是普遍可靠的，如果它对于每个 \(P \in \mathcal{V}_{\mathcal{B}}(\mathcal{D})\) 都返回正确的答案。在开世界语义下，\(\mathcal{B}\) 允许在 \(U\) 上存在超出显式演示或由偏序集公理强制之外的比较，只要不违反任何负示例。在闭世界哈斯语义下，显示的有限有向无环图被声明为完整的哈斯图，并且 \(\mathcal{B}\) 仅包含由该图生成的偏序集。  

## 4 开世界可识别性  
###### 命题 2（可靠答案准则）  
对于 \((\mathcal{B}, \mathcal{D}, q)\)，存在一个普遍可靠的二元答案当且仅当 \(q\) 被识别。  
###### 证明  
如果所有一致的偏序集都给出值 \(v\)，则返回 \(v\) 是可靠的。如果两个一致的偏序集给出不同值，则任一二元输出对其中一个都是错误的；随机化无法保证对两者都正确。∎  
补充命题 S1 给出了全称量化的版本，包括随机化规则的情况和非空版本空间假设。一般准则很简单，但揭示了正确的评估目标。  

下一个定理在对偏序集背景限制最少的情况下，给出了任意有限正负比较提示的精确刻画。对于一个自反关系 \(R\) 和 \(x \in U\)，记 \(\operatorname{Pred}_R(x) = \{u: uRx\}, \quad \operatorname{Succ}_R(x) = \{v: xRv\}.\)  

###### 定理 3（开世界完成三歧性）  
设 \(U\) 有限，\(\mathcal{B}\) 是 \(U\) 上所有偏序集的类，且 \(\mathcal{D} = (\mathcal{D}^+, \mathcal{D}^-)\) 是可满足的。令 \(R = \operatorname{TC}(\mathcal{D}^+)\)，其中 \(\operatorname{TC}\) 表示自反对传递闭包。对于一个查询 \((a,b)\)，恰好以下之一成立：  
1. 1. \(aRb\)，此时查询被识别为真；  
2. 2. \(a \not R b\) 且要么 \(bRa\)，要么 \(\bigl(\operatorname{Pred}_R(a) \times \operatorname{Succ}_R(b)\bigr) \cap \mathcal{D}^- \neq \varnothing\)，此时查询被识别为假；  
3. 3. 以上条件均不满足，此时查询不可识别。  
###### 证明  
可满足性保证存在一个包含 \(\mathcal{D}^+\) 且排除 \(\mathcal{D}^-\) 的偏序集。因此 \(R\) 是反对称的且 \(R \cap \mathcal{D}^- = \varnothing\)；所以 \(P^- = (U, R)\) 本身就是一个一致的偏序集。这种不相交性意味着，在添加 \((a,b)\) 后，只需测试新强制的前驱-后继矩形是否与 \(\mathcal{D}^-\) 相交。  

如果 \(aRb\)，每个包含 \(\mathcal{D}^+\) 的偏序集都包含 \(R\)，所以每个补全都使查询为真。  

现在假设 \(a \not R b\)。偏序集 \(P^-\) 是一个一致的补全，其中查询为假。现在需要决定是否存在一个真实的补全。任何包含 \(R\) 和 \(a \preceq b\) 的偏序集也必须包含每一对 \((x,y)\)，其中 \(xRa\) 且 \(bRy\)，这是由传递性保证的。反过来，添加 \((a,b)\) 后的自反对传递闭包恰好是 \(R_{a,b} = R \cup \bigl(\operatorname{Pred}_R(a) \times \operatorname{Succ}_R(b)\bigr)\)。这个显示的矩形是由传递性强制的。  

关于反向包含，记右边的关系为 \(R'\)。它包含 \(R\) 和 \((a,b)\) 并且是传递的：一个 \(R\) 对与一个矩形对复合，或一个矩形对与一个 \(R\) 对复合，结果仍在矩形内；两个矩形对复合也是如此。因此，包含 \(R \cup \{(a,b)\}\) 的最小自反对传递关系包含在 \(R'\) 中，证明了等式。  

如果 \(bRa\)，那么 \(R_{a,b}\) 包含 \(aRb\) 和 \(bRa\)（其中 \(a,b\) 是不同元素），所以不存在反对称的真实补全。如果显示的笛卡尔积包含一个负示例，那么每个真实补全都违反该示例。因此，第 2 项中的任一条件都强制为假。  

假设没有障碍存在。由于 \(b \not R a\)，添加 \((a,b)\) 不会创建有向循环，所以 \(R_{a,b}\) 是反对称的。根据假设，它也避开了 \(\mathcal{D}^-\) 中的每一对。因此 \(P^+ = (U, R_{a,b})\) 是一个一致的偏序集，其中查询为真，而 \(P^-\) 是一个一致的偏序集，其中查询为假。该查询不可识别。这些替代情况是互斥且完备的。∎  
引理 S2–S3（附录……）