CodeGraph Explore 集群饥饿修复全解析：CG-36 确定性测量与簇间预算再分配机制

CodeGraph 的 codegraph_explore 工具在把代码上下文塞进有限 token 信封时，存在一个隐蔽缺陷：单个文件内部的"簇"（cluster，即按相邻性聚合的代码片段）分配是"全有或全无"的——榜首簇被整块拿走后，排名靠后的簇要么整体放下、要么整体丢弃，导致高相关文件的预算被浪费、答案代码被低分文件"顺走"。本文基于仓库中的 CG-36 基准文档 explore-cluster-starvation-cg36.md，完整还原这一缺陷的成因、误诊过程、两处修复、六仓库套件验证结果，以及配套落地的探针脚本、hermetic 夹具与回归测试，并逐条对照 src/mcp/tools.ts 中的实际实现代码，讲清"簇间预算再分配"这一修复的源码级细节。

读完本文，你将掌握：Explore 响应预算从文件级分配到簇级选择的完整链路、MIN_CHARS/FILE_OVERHEAD 等关键常量的实际作用、饥饿缺陷为何对"信封总量"类探测不可见、以及如何用配对式（pair-based）指标对上下文投递质量做可门禁化的回归测量。

一、缺陷本体：簇选择的"全有或全无"

在 CG-36 之前的实现里，一个文件的簇选择规则是：

• 排名第一的簇总是被拿走——如果它超出该文件的预算，就收缩（shrink）到能装下的高重要度完整符号区间；
• 它下面的每一个簇都先按完整形态渲染，然后要么整块放入剩余空间、要么被整体丢弃。

问题在于：如果一个文件的榜首簇非常琐碎（trivial），真正的答案代码就整个被丢掉了。以基准文档中的真实测量为例（基线为 feature/CG-24 分支尖端 76ab1fe）：

repo	文件	score	reserved	spent	share
django	db/models/sql/query.py	83	7,947	1,923	24%
django	contrib/admin/filters.py	18	2,271	8,057	355%
okhttp	.../RealInterceptorChain.kt	86	6,058	1,474	24%
okhttp	.../CallServerInterceptor.kt	20	1,974	5,832	295%

score 83 的文件只花掉自己预留预算的四分之一，而 score 18 的文件却拿走了自己预留的 3.5 倍。

这个缺陷之所以长期不可见，是因为响应始终看起来是"满"的：未花掉的预留额会按 CG-31 的设计原样结转（carry forward）给排名靠后的文件，于是低分文件拿走了这些字节，而所有"信封份额"类指标仍然显示健康。这是 CG-36 对测量方法论最重要的启示：只看响应总量永远发现不了投递错误，必须看每个文件的预留-实际消耗对账。

簇排名顺序为何如此

簇的排序逻辑可以直接在源码中确认。src/mcp/tools.ts 中的排序比较器按以下优先级依次比较：

1. hasSpine（是否承载流程主干/调用路径）——主干簇优先，因为渲染出的调用链本身就是流程类问题的答案；
2. maxImportance（簇内最高符号重要度）；
3. 密度 score / span；
4. 总分 score；
5. 更小的 span（跨度）。

这一顺序是刻意的、有保护性的——后面会说明它为何不能动。

二、误诊纠正：问题不在密度排名

原始 issue 给出了两个候选修复点，并怀疑第一个：簇排名在 hasSpine → maxImportance 之后用密度（score / span）平局决胜，这在结构上偏向"小而琐碎"的簇胜过"大而承载答案"的簇。

但把簇集合 dump 出来之后，结论相反——在两个真实案例里，输掉的都是 maxImportance，而不是密度：

django/db/models/sql/query.py   budget 10,135   spent 1,923
  KEPT    1379–1400   span   22   score  14   maxImp 6   (check_related_objects — 一个胶水符号)
  DROPPED  306– 929   span  624   score 290   maxImp 3   (133 members: 整个 Query 类)

okhttp .../RealInterceptorChain.kt   budget 6,058   spent 1,474
  KEPT      16–  44   span   29   score  44   maxImp 6   (包声明 + import 块)
  DROPPED  113– 373   span  261   score 171   maxImp 3   (73 members: 拦截器链本身)

maxImportance 排在前面是刻意且必要的——正是它阻止了 Alamofire 的 Session.swift 把预算输给文件头部的属性列表（该文件 perform/didCreateURLRequest/task 等方法位于约 200 行的密集低重要度声明之下）。因此排名顺序一行未动，真正的杠杆是第二个修复点：不要整体丢弃落败的簇。

三、修复内容：两处站点，同一条规则

修复的核心规则一句话概括："只要剩余空间还值得构成一个代码段，就把它保住"——这正是 CG-26 在文件之间已经验证过的教训，现在被应用到簇之间。

3.1 选择阶段：后位簇收缩进剩余空间

在 src/mcp/tools.ts 的选择循环中，修复后的逻辑是：

// Later clusters used to be all-or-nothing: rendered whole, then taken
// only if the whole thing fit the remainder. ...
// So a later cluster is shrunk INTO the remainder by the same whole-member
// rule the first one already uses — CG-26's between-FILES lesson ...
// applied between CLUSTERS.
const room = cap - projectedChars - GAP_MARKER.length;
if (room < EXPLORE_ALLOCATION.MIN_CHARS) continue;
const section = renderCluster(rc.c, room, room);
const text = sectionText(section.parts);
if (text.length === 0) continue;
// The never-empty floors inside the windowing may overrun `room` ...
// The first cluster is allowed that overshoot — an empty section is worse —
// but a later one is not.
if (projectedChars + text.length + GAP_MARKER.length > cap) continue;

要点：

• 后位簇现在收缩进文件预算的剩余部分，使用的与第一个簇相同的"完整成员"规则（绝不从方法体中间截断）；
• 当剩余空间低于 MIN_CHARS（700 字符，定义见 src/mcp/tools.ts）时，剩余空间装不下一个可读的完整代码块，因此保持丢弃而不是产生一堆碎片——碎片反而会成为下一次调用去重逻辑必须绕开撕扯的对象；
• 一个不对称细节：永不空（never-empty）的窗口下限可能让渲染结果超出 room。第一个簇被允许这种超射（空段落更糟），但后位簇不允许——因为它超出的部分实际花掉的是排名更低文件的名额。

MIN_CHARS = 700 的语义在源码注释中解释得很清楚：低于这个长度，一片代码装不下一个完整的方法，而"碎片严格劣于指针——它会迫使调用者发起本工具正是要预防的 Read"。它同时是分配器的地板：allocateExploreBudget 中"人人先拿 MIN_CHARS，剩余部分按权重切分"（src/mcp/tools.ts）。

3.2 上限修剪阶段：先重渲染再丢弃

第二处站点是渲染上限（renderCeiling）修剪：当一段的精确成本超出上限时，最弱的已选簇会被重新渲染进剩余空间，而不是直接整块丢弃。源码实现见 src/mcp/tools.ts：

// The weakest cluster is SHRUNK into the room that is left before it is
// dropped (CG-36). Dropping it whole makes this loop as all-or-nothing as
// the selection above it was, and at the same cost: on excalidraw's
// `typeChecks.ts` the estimate missed by 13 chars and a 1,512-char cluster
// — the file's highest-SCORING one, last only because rank breaks ties on
// density — was thrown away to pay for it.
...
if (room >= EXPLORE_ALLOCATION.MIN_CHARS && !reshrunkOnce.has(weakest)) {
  reshrunkOnce.add(weakest);
  const reshrunk = renderCluster(clusters[weakest]!, room, room);
  ...
}

这一处值得单独点名：在 excalidraw 的 typeChecks.ts 上，段成本估算只差了 13 个字符，却把一个 1,512 字符的簇——该文件得分最高的簇（只因排名用密度平局决胜而排在最后）——整块丢掉只为省下这 13 字符。修复后收回了 excalidraw 1,449 字符损失中的 1,501 字符（含弹性结尾段的补位）。

实现里还有一个防自旋细节：每个簇最多尝试一次重收缩（reshrunkOnce 集合）——第二次尝试说明第一次重渲染并没有省下足够（头部随内容移动了），此时直接丢弃，避免逐字符地磨。

四、套件结果：字节沿评分顺序上移

node scripts/agent-eval/probe-file-spend.mjs 在 6 个仓库上做了干净重建（clean full-rebuilt indexes，CG-33 保证）。下表只列出消耗发生移动的文件；score 是候选的排名分，reserved 是其分配额：

repo	文件	score	reserved	before	after
django	db/models/sql/query.py	83	7,947	1,923	10,082
django	contrib/admin/filters.py	18	2,271	8,057	2,198
django	utils/autoreload.py	12	1,747	3,145	1,709
django	db/models/fields/related_descriptors.py	11	1,660	2,516	1,493
excalidraw	element/src/typeChecks.ts	23	2,740	3,102	2,573
excalidraw	excalidraw/types.ts	14	1,942	819	1,372
okhttp	.../RealInterceptorChain.kt	86	6,058	1,474	6,038
okhttp	.../Interceptor.kt	64	4,697	2,027	4,659
okhttp	.../RealCall.kt	52	3,972	3,628	3,922
okhttp	.../Call.kt	54	4,097	4,097	2,073
okhttp	.../CallServerInterceptor.kt	20	1,974	5,832	1,959
okhttp	androidMain/.../AndroidDns.kt	21	1,999	1,812	0
tokio	task/local.rs	40	4,361	4,599	4,798
tokio	runtime/task/harness.rs	14	1,981	2,565	2,341
gin	routergroup.go	87	5,782	3,273	5,632
gin	tree.go	17	1,693	892	1,969
gin	ginS/gins.go	26	2,213	4,431	2,171
alamofire	Source/Core/Session.swift	34	2,792	2,797	3,396
alamofire	Source/Core/Request.swift	148	9,100	8,865	8,453

每个仓库中字节都沿评分顺序上移。信封总量：

repo	source before	after	Δ	files	ceiling
django	20,878	20,719	−159	6 → 6	24,963 ≤ 25,000
excalidraw	19,652	19,704	+52	8 → 8	24,813 ≤ 25,000
okhttp	18,870	18,651	−219	6 → 5	24,985 ≤ 25,000
tokio	21,607	21,582	−25	5 → 5	24,777 ≤ 25,000
gin	10,776	11,952	+1,176	4 → 4	14,655 ≤ 19,500
alamofire	11,662	11,849	+187	2 → 2	12,862 ≤ 19,500
total	103,445	104,457	+1,012

饥饿标志（starvation flags）：8 → 0。所有仓库都保持在或低于各自的硬上限，净收益 +1,012 源码字符。

五、唯一代价，直白陈述

okhttp 丢掉了排名第 6 的文件 androidMain/.../AndroidDns.kt（score 21，一个平台 DNS 辅助文件，与"拦截器链如何工作"的问题无关），并损失 219 源码字符；换来的是 RealInterceptorChain.kt +4,564 和 Interceptor.kt +2,632——这两个文件才是回答问题的文件。

文档明确指出这不是新缺陷，也不是修复越界。okhttp 的预留额结构性超订（over-subscribed）：分配器在切分 maxOutputChars 时按每文件固定收取 FILE_OVERHEAD = 200（见 src/mcp/tools.ts），而真实头部要 300–500 字符，所以承诺总和（约 22,800 源码 + 约 2,100 真实头部）超过了约 24,760 字符渲染上限能承载的量。owedPayableBelow 机制已经拒绝为"能预见会被丢弃"的文件留字节，而 AndroidDns.kt 恰在那条线之后；它在旧基线上存活只是因为其上方的文件恰好花得少——是运气，不是设计。关闭超订的正确做法是让分配器按每文件头部估算计费而非固定 200，但那比本 issue 的改动范围更大，CG-26 曾刻意保留 FILE_OVERHEAD 作为分配器自己的常量。

六、什么没有变

• 簇排名顺序：hasSpine → maxImportance → 密度 → score → span，一行未动（对应 src/mcp/tools.ts 的排序器）；
• Alamofire Session.swift：密度优先规则所保护的那种形态不但没受损，反而净增 599 字符；
• CG-27 工厂闭包结果：probe-factory-closure.mjs 显示 11 个内部闭包定义中投递 7 个，与基线完全一致；
• CG-31/CG-26 预留不变量：[explore-reservation-invariant.test.ts] 保持绿；每个仓库都停留在硬上限之下；
• 四个分配夹具全部通过——payroll-go、self-query 以及本次新增的两个。

七、落地的可测量设施

为使这一缺陷可长期测量，仓库中随修复一起交付了四类设施：

7.1 常驻探针 probe-file-spend.mjs

scripts/agent-eval/probe-file-spend.mjs 是"每文件预留 vs 实际投递"的常驻扫描。它的关键设计是标志一个配对（pair），而不是单个文件：一个大份额未花掉的文件，同时存在一个得分显著更低却超支的文件。单边单独出现都是合法的（小文件本来就没那么多可说；结转机制正是用来把余量传给下家的）——这也是信封探针永远看不见此缺陷的原因。任一仓库出现标志即退出码 1，因此可以直接做 CI 门禁。

源码中四个阈值参数（scripts/agent-eval/probe-file-spend.mjs）：

const STARVED_SHARE = 0.5;   // spent < half its reservation（花掉不足预留的一半）
const OVERSPEND_RATIO = 1.5; // spent > 1.5x its own reservation（超支超过 1.5 倍）
const SCORE_RATIO = 2;       // ...while scoring less than half the starved file（得分不足被饿文件的一半）
const MIN_RESERVED = 2000;   // 忽略预留额小到不足以说明问题的文件

配对判定逻辑（findStarvation）要求两侧同时成立：被饿方 finalChars < allowance * 0.5 且预留 ≥ 2,000，超支方 finalChars > allowance * 1.5 且 overspent.score * 2 <= starved.score。数据源是 CODEGRAPH_EXPLORE_DEBUG 诊断旁路，因此它测量的是真实出货的分配器，而非从 markdown 反推份额。典型用法：

node scripts/agent-eval/probe-file-spend.mjs            # 需先 npm run build + 全量重建索引
node scripts/agent-eval/probe-file-spend.mjs --json > /tmp/new.json
node scripts/agent-eval/probe-file-spend.mjs --baseline /tmp/base.json
node scripts/agent-eval/probe-file-spend.mjs django --all   # 打印全部文件而非仅标志
CORPUS=/tmp/codegraph-corpus node scripts/agent-eval/probe-file-spend.mjs

其扫描的六仓库套件与查询（scripts/agent-eval/probe-file-spend.mjs）：

const SUITE = [
  { id: 'django', q: 'How does a QuerySet turn into SQL and fetch rows from the database?' },
  { id: 'excalidraw', q: 'How does updating an element re-render the canvas on screen?' },
  { id: 'okhttp', q: 'How does a call go through the interceptor chain to the network?' },
  { id: 'tokio', q: 'How does a spawned task get scheduled and run by a worker?' },
  { id: 'gin', q: 'How does a registered route handler get invoked for an incoming HTTP request?' },
  { id: 'alamofire', q: 'How does a request get built and sent through the session?' },
];

7.2 两个 hermetic 夹具，方向相反

• tests/fixtures/starved-cluster-ts/——django 与 okhttp 形态的还原体。目标文件 src/pipeline/chain.ts 里，榜首簇是文件头部的 describeChain 一行胶水函数（与入口点相邻，因而携带文件内最高每符号重要度），而真正承载答案的 RequestChain 类（proceed → advance → writeAndRead 流程）位于簇间隙阈值之外、形成第二个大簇。在 CG-24 基线上该夹具失败（仅花掉预留的 28.8%，proceed 与 writeAndRead 均未投递）；带修复后通过。
• tests/fixtures/dense-header-ts/——Session.swift 形态的字节级锚点。目标 src/net/session.ts 在 perform 方法上方有 20+ 个相邻低重要度声明（文件中最密集区域），查询点名 perform/didCreateURLRequest/task 三个方法，它们必须继续赢得预算。这是反向砝码：如果未来某次改动让密度重新压过重要度，这个夹具会失败。两个夹具必须一起读、一起满足。

7.3 回归测试门禁

tests/explore-cluster-starvation.test.ts 通过 npm test 把两个夹具钉死在套件里。它的断言结构分两层：

1. 夹具形状自检（"如果这里腐化了，下面的门禁就毫无意义"）：目标文件必须走 clusters 渲染路径、两个符号在行号上相隔足够远以保证独立成簇、目标文件必须拿到最大分配额（allowance > 4000 且大于所有其他文件）；
2. 行为门禁：finalChars / allowance > 0.6（故意定得远低于修复前后的两个实际值 28.8% 与 131%，使普通预算波动不会打红套件）、响应必须包含流程两端的具体函数签名（如 async proceed(request: PipelineRequest)、private async writeAndRead(request: PipelineRequest)）、且响应总长不超过 hardCeiling。

测试通过 CODEGRAPH_EXPLORE_DEBUG 侧车文件获取分配诊断报告（ExploreDiagnosticReport），而不是解析响应文本本身——这正是"必须看预留对账，不能只看渲染结果"的方法论落地。

八、方法论注记：为什么渲染出的 markdown 什么都看不出来

基准文档最后的方法论段落值得所有做上下文预算优化的开发者借鉴：

• 簇选择的缺陷在渲染出的 markdown 中不可见。要看见它，必须在 dist/mcp/tools.js 的 let assembled = assembleSection(chosenIndices); 之前打补丁，日志输出 fileBudget / projectedChars / 每个已排名簇的 span、score、maxImportance、是否被选中及成员列表。只读响应会让成员选择效应看起来像预算效应。
• 构建间源码字符数的差异不自动等于回归：excalidraw 第一刀上的 −1,449 字符并非分配丢失，而是弹性结尾段（elastic epilogue）扩张进了一段 13 字符记账误差释放出的空间。
• 该缺陷的完整验证链是"确定性测量"而非 agent A/B：agent 运行太有噪声，看不出 2K 级别的位移，所以声明只针对"字节去了哪个文件"，并用干净重建的索引（CG-33）排除索引漂移干扰。

九、总结

CG-36 修复的价值在于它同时交付了三样东西：一个具体缺陷的修复（簇间"收缩进剩余空间"规则，两处站点：选择循环与上限修剪）、一个可门禁的测量方法（配对式饥饿标志 + 确定性探针，而非 agent A/B）、一组方向相反的回归锚点（starved-cluster-ts 与 dense-header-ts 两个夹具，防止修复本身在未来被回退）。所有结论均可在仓库中复核：核心实现在 src/mcp/tools.ts 的 EXPLORE_ALLOCATION 常量表、allocateExploreBudget 与簇选择/上限修剪循环；测量设施在 scripts/agent-eval/probe-file-spend.mjs；回归门禁在 tests/explore-cluster-starvation.test.ts。同系列的 CG-24、CG-26、CG-27、CG-30、CG-31 基准文档位于 docs/benchmarks/，可作为理解 Explore 预算分配演化全线的入口。