选择与截断：真实增量成本下的启发式

选择问题先于提示措辞

第一章已经给出完整wire与冻结词元计数。本章设候选集合为U，每个候选有来源身份、quote和检索分数，目标是在总容量内保留对任务有用的证据。理想效用可以是最终答案所需事实的覆盖，但运行时通常不知道完整答案，项目因此用检索融合分数作为选择代理。这个代理不是任务成功概率。我们比较head、rank、density三种真实选择器，并提供truncate作为会丢事实的基线；每次加入候选都按完整wire重编码准入。

head按候选身份排序，遇第一个装不下的条目就停止，模拟简单取前面材料的做法。rank按融合分数顺序，装不下某条则跳过继续看后面。density每轮重新计算所有剩余候选加入后的实际词元增量，以分数除有效增量排序，选当前可装的最高者。三者使用同一候选池与容量，只改变选择规则。不能让优化方案拿到更多资料，再把差异都归因于算法；候选池、版本和分词器必须冻结。

动态成本与可行性

令当前选择为S，候选u的实际增量为 $\Delta T(u\mid S)=T(\mathrm{render}(S\cup\{u\}))-T(\mathrm{render}(S))$。由于格式和合并，它不是固定的正文token数。density使用 $score(u)/\max(1,\Delta T)$ 作为排序值，分母下限一只是避免零或负增量时除法异常，不改变实际容量检查。真正接受仍要求试写后的完整T加预留不超过C。启发式可能选择不理想，但不能因此超预算。

这个问题与背包相似，但当前成本和效用并不满足固定可加背包的全部前提。引用头部可重复、BPE可跨边界合并、多个候选可能重复同一事实，检索分数也不是独立价值。即使在标准固定成本背包中，按密度贪心对不可分物品也不保证最优。项目没有证明近似比例，不把名称“密度”当数学最优性承诺；完整任务集会实际记录它保留了什么以及有没有覆盖要求。

完整算例一：固定成本下贪心也会输

用一个明示为独立正控制的小背包：容量四，候选甲成本三、价值五，候选乙丙各成本二、价值三。甲密度五除三大于一点五，贪心先选甲后剩一，价值五；乙丙一起成本四、价值六，更好。这个反例只讨论固定可加成本，已经足够推翻“密度必最优”；真实wire的非可加性更不能自动加强保证。项目的价值是预算准入精确而启发式结果可比较，不是偷偷把一个经验规则写成定理。

from itertools import combinations
items=[('A',3,5),('B',2,3),('C',2,3)]
chosen=[];left=4
for item in sorted(items,key=lambda x:-x[2]/x[1]):
    if item[1]<=left:chosen.append(item);left-=item[1]
best=max(sum(x[2] for x in subset)
         for n in range(4) for subset in combinations(items,n)
         if sum(x[1] for x in subset)<=4)
assert sum(x[2] for x in chosen)==5 and best==6
print(chosen,best)

完整算例二：顺序停止与跳过的区别

仍以明确构造的固定成本说明一项机制：剩余预算四，第一候选成本五，后面两项各成本二。head立即停止，保留零项；rank跳过第一项，可保留后两项。两者不需要改检索器，差异来自遇到装不下材料时的行为。实际项目使用真实编码后的成本重演同一问题，完整报告保留head/rank/density与全文/压缩两种表示共一百零八组结果。课程不只展示密度胜出的请求，后续评估还会列没有差异或基线更好的情况。

判断改进时也要区分候选粒度。全文模式以整份文档为单位，某份很长的相关文档可能装不下；保真压缩模式把通过门槛的文档变成可单独引用的原始行。粒度变化会让选择更灵活，但每行也重复来源头部，整体全部打包未必更省。第三章的压缩门槛保证候选总体未丢声明，第二章的选择仍可能在有限预算下丢重要行。这两个损失发生在不同阶段，评价时应分别记录。

截断需要同时守住文本与证据

truncate模式沿排序尝试候选，放不下时扫描其quote的全部Unicode字符前缀，找最长的完整wire可行前缀。没有用token切片强行解码，也没有假定前缀成本单调。新增truncated标记同样进入完整编码成本。因为扫描每个前缀都重编码，小文本可接受，长文档会很慢；这是为正确边界选的实现，不是生产高性能截断器。候选被裁剪后，source_claims只允许完整可见原文行产生引用，绝不能从未打包的原文后半部补答案。

实际截断实验选择schedule全文，任务要求该文档全部三个字段，预算由一个实际可行的半篇前缀wire计算。结果仍可保持总词元不超限且UTF-8有效，却只覆盖部分字段。若在生成时偷偷从数据库补回剩余原文，就会制造“截断没有影响”的假结果；项目有专门负对照：只打包标题时，不能从全文原始资料生成任何事实claim。源文档存在和模型上下文可见是两种支持，必须同时满足。

前缀不单调的可执行反例

令字节b、c先合并成词元二百五十八，再把a与该词元合并成二百五十九。ab没有可用合并，内容长度二；abc先得到a、bc再合并为abc，内容长度一。加BOS/EOS后分别四与三。若预算三，较长abc可行而较短ab不可行。项目truncate_text遍历全部字符边界，返回abc；依赖单调二分可能停在a。这个示例解释实现选择的必要性，不用仅仅“代码比较复杂”掩盖算法前提。

from vendor import ByteBPE
from context import truncate_text
small=ByteBPE([(98,99),(97,258)])
assert len(small.encode('ab'))==4 and len(small.encode('abc'))==3
assert truncate_text('abc',small,3)['text']=='abc'
print('non-monotone prefix checked')

排序、并列与重复内容

分数相同用稳定身份排序，避免字典遍历或文件顺序使结果漂移。相同事实若以多个候选重复出现，不应在覆盖率中重复加分；输出按来源行身份去重。去重本身也有边界：两个版本文本恰相同但状态不同，不能只按文本合并并绕过撤销。版本过滤先于候选构造，选中的身份必须仍是当前有效来源。第四章会给出状态转移与历史重放，避免把旧高分片段留在当前上下文。

第一类验证是容量与文本：完整重编码、解码回wire、输入加预留和实际输出均不超限；截断不切坏UTF-8。第二类是任务和可见证据：覆盖率从有效源事实自动生成的集合计算，裁剪后看不到的行不能引用。预算通过只证明能装下，不证明装的是有用材料。课程后续用删除关键证据的反事实进一步检查输出是否依赖真正打包的内容，而不是调用者暗中读取全库答案。

练习与项目增量

循环不变量与终止性

把预算正确性写成归纳步骤比观察几题没有超限更强。初始selected为空，pack首先计算空证据wire并检查其长度加reserve不超limit；这建立循环不变量。每次接受一条候选前，都对selected加该候选完整重编码，只有真实长度满足同一不等式才替换selected。因此无论密度分数是否合理、增量是否为负，已接受状态仍满足预算。跳过或停止不改变selected，也保持不变量；最后返回前再编码与断言是实现的独立末端检查。

终止不依赖“每步token数变大”。remaining起初有M条，每个继续的循环至少移除一条候选：接受、rank跳过或truncate处理都会pop；head和density没有可行选项时直接break。因此最多处理M次有限候选。若把代码改成装不下就放回队尾，可能反复处理同一条，原终止证明就失效。负增量只影响密度分母钳制，不是while可能无限运行的理由。

密度策略的代价也不等于一次排序。每轮扫描所有剩余候选并重编码试写后的完整wire，总试算次数最多$M+(M-1)+\cdots+1$，等于$M(M+1)/2$；每次编码成本还随当前wire长度增长。这里用真实小数据换清晰不变量，不能把代码称为线性高效打包。缓存必须绑定当前selected、序列化和tokenizer，因为BPE非可加；缓存单片段成本并直接相加会破坏第一章的容量契约。

本章增量是四种可执行打包策略与安全字符前缀扫描。第三章继续检查候选在选择之前是否已经因压缩丢失限定词；第四、五章再保证候选来自有效记忆和稳定检索。只有这些依赖闭合，最终比较才是在研究上下文，而不是在不同资料和预算之间随意挑成绩。

# pack
def pack(query,ranked,tokenizer,limit,reserve):
    raise NotImplementedError('pack')

# pack
def pack(query,ranked,tokenizer,limit,reserve):
 if type(limit)is not int or type(reserve)is not int or limit<1 or reserve<1:raise BudgetError('positive integer budget')
 selected=[]
 if len(tokenizer.encode(render_context(query,selected),boundaries=True))+reserve>limit:raise BudgetError('base context exceeds budget')
 for row in ranked:
  trial=render_context(query,selected+[row])
  if len(tokenizer.encode(trial,boundaries=True))+reserve<=limit:selected.append(dict(row))
 wire=render_context(query,selected);return {'selected':selected,'rendered':wire,'context_tokens':len(tokenizer.encode(wire,boundaries=True))}