Design: tree-shaped prefix affinity — forked branches inherit the shared prefix's compression state

[ranxianglei]

Background

Anonymous prefix affinity (#309/#316/#499, src/prefix-affinity.ts) resolves header-less clients by longest-prefix match over an append-only hash chain (h_i = sha256(h_{i-1} || msg_i)). It deliberately mirrors vLLM/SGLang radix prefix caching at the identity layer.

Current fork semantics (documented in the file header): when a request's history diverges from every stored chain, it forks into a brand-new session with zero compression state. The discarded parent candidates are recorded in lineage (parents[], reason: "forked"|"truncated") — but lineage is UI/debug only, never used for matching or state inheritance (MIN_FORK_PREFIX = 3, comment says so explicitly).

The gap

A fork (user edits history, rewinds, or two parallel conversations share a common opening) throws away every compression block anchored inside the shared prefix:

• the parent session may have folded 100K tokens of that prefix into blocks;
• the forked branch re-sends the same bytes raw and must re-compress from scratch (nudge starts at ~0% accumulated);
• after compression, the branch's blocks duplicate the parent's coverage over identical content.

This is the classic radix-tree property that prefix-affinity stops short of: identity is content-addressed, but compression state is not — it lives per session (kernel StateStore, blocks owned by one session id).

Proposal (discussion)

Make the fold state effectively tree-shaped so a fork inherits the folds anchored inside its shared prefix:

1. On fork detection (existing lineage machinery), copy/adopt the parent session's blocks whose effectiveMessageIds fall entirely inside the shared prefix (items 0..lcp-1) into the new session, remapping anchors.
2. Keep per-session ownership for persistence — this is a one-time adoption at fork time, not shared live state (avoids two branches mutating one block).
3. Reuse the existing per-item hash chain as the prefix-addressing mechanism (MAX_STORED_ITEMS = 128 currently caps it — may need raising or a separate block-anchor index keyed by item hash).
4. Safety unchanged: matching requires byte-identical history possession (会话身份不稳定：credential/upstream 维度导致长会话状态孤儿化（sessions 缺失） #286/# [Bug/Regression] 0.1.59 关闭内容指纹会话兜底 (#286)：无会话头第三方 harness 请求被直接 400，不转发上游 #309 argument).

Open questions

• Cost/benefit: how often do real clients fork (edited history / rewind)? omp rewind, codex /compact-adjacent flows, web UIs with regenerate.
• Interaction with restoreOutputBudget-style per-session metadata (must NOT inherit).
• Kernel support needed: block adoption/remap API (current kernel owns blocks per session state).

Spawned from the #619 discussion — orthogonal to its remaining decode-fail scope (PR #622).

[ranxianglei]

🤖 Powered by ework · qwen3.8-27b

[bot] 🏷 Picked this up as a design review (not yet implementing — see recommendation at the end). Duplicate screen first: no existing issue/PR proposes tree-shaped affinity or fork-state inheritance; the closest neighbours are #319 (the existing fork-lineage machinery this builds on, closed) and #619 (spawn point, orthogonal decode-fail scope in PR #622). Not a duplicate.

Bottom line up front

The design is sound, and it's more feasible than the issue assumes — two of the three "hard parts" (anchor remapping, kernel adoption API) turn out to be unnecessary. But the affected population is narrower than the open questions imply, so I recommend measure-first + ship-gated rather than building it blind. Details below.

1. The problem is real — but who actually forks?

Fork-inheritance can only help anonymous clients (no client-provided identity), because that's the only path through prefixAffinity.resolve() (src/server.ts:1263 if (!clientProvided)). Clients that carry a stable id never reach the fork branch:

• codex → body.session_id
• opencode → x-session-affinity
• omp → prompt_cache_key (session id derives from it, src/server.ts:1347-1359)

So two of the three frequency examples in the open questions — "omp rewind" and "codex /compact-adjacent flows" — are largely out of scope: those clients hold one stable session and don't fork through prefix-affinity at all. The real population is pi-without-x-acp-session, dsh web, and generic header-less harnesses, and even then only when they (a) grow long enough to compress and (b) edit/rewind/regenerate mid-history.

Also worth noting: the rolling-window "client dropped its oldest messages" case does not fork — tail-window reattach (#316, src/prefix-affinity.ts:207-249) reattaches to the same session, so no state is lost there. Only true mid-history divergence (edited middle message) creates the zero-state fork this issue targets. That's a genuine but small slice.

When it does hit, the benefit is large though — it's exactly the #351 failure mode (458K-token history resent raw and re-compressed from scratch). So: low frequency, high per-event value.

2. The core design choice is correct — affirming it

Copy-on-fork (one-time adoption, per-session ownership preserved) is the right call over the alternative "true radix tree" (content-addressed shared blocks that sessions reference). Shared live blocks reintroduce exactly the hazard the proposal wants to avoid: two branches mutating one block (deactivation / tier promotion / orphan-GC in one branch silently corrupts the other). One-time copy keeps ownership clean. Agreed.

3. Feasibility is better than stated — two "hard parts" dissolve

(a) No anchor remapping needed. This is the big one. Raw message ids are deterministic content fingerprints — acp-kernel/wire/message-id.d.ts: deriveMessageId(role, contentType, text, {toolCallId, toolName}) = SHA-256 of identity, and the duplicate-cluster _N suffix is "counting from 0 in arrival order… two passes over the same content produce the same cluster numbering (deterministic)." A byte-identical fork prefix therefore yields identical raw ids to the parent's prefix.

Refs (mNNNNN) align too: acp-kernel/refs.d.ts assignRefs assigns them by arrival index from a fresh nextIndex=0 over the incoming list. A fork re-sending the same prefix gets the same refs the parent assigned. So an adopted block's effectiveMessageIds and its startRef/endRef both line up with no remap, in the common append-only case.

(b) No kernel change needed. The kernel already runs "state pre-seeded with blocks → reconcile against incoming" on every restart: disk restore (src/persist.ts buildSession → mergeState) loads blocks/messageRefs/tokenSnapshot into a Session, then processTurn/syncBlocks reconciles them against the incoming history. Fork adoption constructs the identical shape (a filtered copy of the parent's blocks + a counter bump) and rides the exact same code path. mergeState (src/persist.ts:129-140) is literally the construction recipe. So the "Kernel support needed: block adoption/remap API" open question resolves to none — all new code lives in billion-context.

4. Simplification: don't key off lcp / the 128 cap

The proposal frames adoption as "blocks whose effectiveMessageIds fall inside items 0..lcp-1," and flags MAX_STORED_ITEMS = 128 as a cap that may need raising. You don't need positional lcp at all: the proxy has already parsed the fork's full incoming history, so compute the set of incoming raw ids and adopt any parent block whose anchors are a subset of it. Raw-id-set membership is exact at any depth — immune to the 128-item cap (positional LCP is best-effort past 128, but set membership isn't). The existing lineage/lcp machinery is then used only to identify which parent session to draw blocks from, not to bound the adoption.

5. Correctness constraints the proposal under-specifies (this is the real work)

• Closure-safety for tier 2/3. A T2/T3 block carries directBlockIds → child blocks → their effectiveMessageIds. Adopt a block only if its entire transitive closure is in-prefix. Otherwise a distilled summary would cover content the fork diverged on — silent semantic corruption. The "entirely inside the shared prefix" rule must apply to the closure, not just the top block's direct ids.
• ID counters. Bump the child's nextBlockId/nextRunId past the parent's max so newly compressed ranges in the fork don't collide with adopted blockIds/runIds.
• What must NOT inherit (confirms your open question): nudge state, stats (lastInputTokens/contextTokens/compressCreditTokens), messageRefs (rebuilt by assignRefs), and per-session metadata — notably outputBudgetHighWater ([bug] bili dsh 长会话中 max_output_tokens 被压到 ≤200，主请求被误判为 side request 并绕过压缩 #546 restoreOutputBudget, src/server.ts:659-678), learnedContextLimit(s), nativeCompaction* boundaries, lastCompress. Inherit only blocks (+ their blockContents entries); optionally tokenSnapshot (keyed by ref → preserves provider prefix-cache stability across the fork) and absorbed records whose callMessageId/resultMessageId are in-prefix.
• Both compression modes (AGENTS.md §6). Anonymous clients are inherently proxy mode (no x-bili-plugin header), so inherited blocks are always acp_summary carriers and the child is also proxy mode — safe. State this explicitly in the impl so a future plugin-mode client can't accidentally adopt proxy-created blocks whose tool-call carrier isn't in its history.

6. Safety — holds

Adopting reveals nothing new: to discover the parent, the fork must present the shared prefix byte-for-byte (the #286/#309 possession argument), and we only adopt summaries of bytes the fork itself sent. Even if the "parent" is a different user's templated opening, the fork inherits only summaries of content it possessed. Unchanged.

Recommendation (my stance, not a menu)

Given (i) the population is narrower than the open questions suggest, (ii) per-event value is high but frequency is unmeasured, and (iii) the implementation is well-scoped but has real closure-safety subtleties across both modes — I'd sequence it as:

1. Measure first (cheap, zero-risk): extend the existing fork log line (src/server.ts:1283-1285) with a counter of forks where the parent had ≥1 adoptable in-prefix block plus the tokens that would have been saved. One line; tells us within a week or two whether the slice is worth it.
2. Ship gated: implement adoption behind a config flag (default off), validated in production against the counter, then flip default-on. Scope is one new module + a hook at the fork-detection site (src/server.ts:1307-1317, right where lineage is already written to session.metadata) + tests covering both modes and the T2/T3 closure case.

If you'd rather skip the telemetry and build it now regardless of frequency, the design above is ready to implement and I'll proceed on your sign-off — but I'd want your call on the measure-first step since the affected-client assumption in the issue needs correcting before we size the effort.

Happy to draft the measurement one-liner as a standalone PR either way, since it's useful independent of the decision.

[ranxianglei]

Feasibility dig (post kernel v0.0.57): host-only, no kernel API needed

Verified three load-bearing facts on current master:

1. Message ids are content-addressed and session-independent (acp-kernel src/wire/message-id.ts): deriveMessageId = "h_" + sha256(role|contentType|toolCallId|toolName|text) + deterministic within-pass cluster suffix _N for duplicates. A byte-identical history replay converted in a different session produces the same ids in the same order. So parent-block anchors (effectiveMessageIds/directMessageIds) resolve natively against the fork's replay — no remapping needed at all (the issue's "block adoption/remap API" guess is unnecessary).

2. assignRefs is idempotent over pre-seeded maps (acp-kernel src/refs.ts:69 — if (map.byRaw[message.id]) continue;) and allocateFreeRef skips taken refs. Copying the parent's messageRefs entries for covered ids into the fork's fresh state is safe: existing refs are kept verbatim (summary citations like m00042 stay valid — same prefix, same arrival order → same ref numbers), new messages allocate after the highest copied ref. Kernel invariant "ids never reused" holds.

3. The existence proof already ships: the #401 restore path reloads a persisted state (blocks + messageRefs) and the next request replays the FULL raw history — the standard fold path prunes it back to the folded wire. Fork adoption is the same shape: seed state at creation, let the existing machinery do the rest.

Concrete design (Phase 1, ~host-only)

• Hook: at anonymous session creation (via: "new" with lineage.reason: "forked"), after protocol conversion produces CoreMessages, before first prepare.
• Kernel-level LCP: compare the fork's originalMessages id list against the parent's lastMessages snapshot id list (both h_*, exact equality) — not the affinity itemHashes (those hash wire JSON, a different canonical form; and they cap at MAX_STORED_ITEMS = 128).
• Adopt from the parent (in-memory store, else SessionStore disk): the transitive closure of active blocks whose effectiveMessageIds ⊆ LCP id-set (criterion automatically handles nested directBlockIds), plus their blockContents, plus messageRefs entries for all covered ids, plus state.nextBlockId (never re-issue blockIds).
• Nothing else inherits: stats, outputBudgetHighWater ([bug] bili dsh 长会话中 max_output_tokens 被压到 ≤200，主请求被误判为 side request 并绕过压缩 #546), learnedCompatRoles (billion-context: 400 Bad Request when codex sends role: "developer" messages — request a request-body compat transform hook #552), pluginAgent stickiness — all stay fresh-session. (Answers the issue's open question.)
• Result: the fork's first wire is already folded over the shared prefix → byte-stable with the parent's folded prefix → upstream prefix-cache hit + no re-compress + no duplicated block coverage.

Safety argument

Adoption cannot misattribute: a block is only adopted when every id it covers is present, in order, in the fork's actual replay. Coverage-by-exact-ids is the same mechanism the restore path trusts. Worst case with a weak fork guess (distinct conversation sharing a templated head): only the genuinely-shared preamble blocks get adopted — content the requester demonstrably holds (#286/#309 argument).

Limitations (accepted for Phase 1)

• Fork detection needs the parent within the trailing-128-item window (MAX_STORED_ITEMS); ancient-history rewinds won't detect. Divergence is usually recent.
• Memory: blockContents are copied (per-session ownership, issue point 2); bounded by the parent's existing cache.

Implementation sketch: new src/fork-adopt.ts (~150 lines) + hook at anonymous-session creation in the prepare path + tests (adoption matrix incl. nested blocks / cursor safety / metadata non-inheritance; e2e: fork replay produces the already-folded wire with valid refs). No kernel change required.

[ranxianglei]

🤖 Powered by ework · qwen3.8-27b

[bot] 🏷 Validated against the pinned kernel — all three load-bearing facts hold (note: this worktree pins acp-kernel 0.0.54, your dig cites master at 0.0.57; I verified via the .d.ts on 0.0.54 and the semantics are identical). Agreed with the overall shape: host-only, no kernel API, copy-on-fork. Four corrections/refinements before I build, two of which change a load-bearing detail:

1. Don't gate adoption on parent.lastMessages — use set-membership instead. src/session.ts:117-123 (lastMessagesFolded): a boot-restored or disk-reloaded parent stores a bounded, folded+truncated lastMessages whose ids "no longer align with the state ranges." Comparing id lists against it produces a wrong boundary exactly in the case you'd most want it (parent survived a restart). Robust predicate: adopt parent block B iff B.effectiveMessageIds ⊆ {fork's incoming CoreMessage ids} (the fork's id set comes free post-conversion — new Set(msgs.map(m => m.id)), the exact pattern already at server.ts:1836). Needs only the fork's incoming ids + the parent's state.blocks. Side benefits: immune to MAX_STORED_ITEMS=128, and it captures more valid adoptions than positional LCP — a block sitting after a mid-prefix edit that the fork still holds byte-identically (LCP stops at the edit point and misses it). Keep lineage.sharedPrefix for logging/UI only, not as the gate.

2. The hook must run pre-processTurn, not post-prepare. core.processTurn executes inside each prepare* — e.g. anthropic server.ts:1817, immediately after originalMessages = msgs at :1805. Seeding blocks after prepare returns would be too late: the first wire is already unfolded. So the seed lands between originalMessages = msgs and processTurn, in all three prepare fns (anthropic/openai/responses); the logic lives once in src/fork-adopt.ts.

3. Exclusion list += nudge; bump nextRunId too. nudge (baseline/anchors) encodes the parent's growth trajectory — must stay fresh. You listed stats/outputBudgetHighWater(#546)/learnedCompatRoles(#552)/pluginAgent; add nudge. Also bump nextRunId alongside nextBlockId (runIds are allocated per compress and would otherwise collide). Skip absorbed records in Phase 1 (keeps scope tight).

4. Copy tokenSnapshot entries for covered refs (keyed by ref, same subset selection as messageRefs) → keeps the provider prefix-cache stable across the fork. Cheap, optional, but consistent.

One conscious choice to flag rather than let it look like a bug: set-membership may adopt a block physically located after a divergence point when the fork still possesses those bytes. That's safe (the fork demonstrably holds them — the #286/#309 possession argument) and strictly more beneficial than LCP. Deliberate, not accidental.

Parent access: peekSession(parentId) in-memory, else a detached SessionStore.loadSync read (never inserted into the pool); graceful no-op if the parent isn't found anywhere.

Plan: host-only, gated behind an env flag (default-on, opt-out) so ops can disable it; tests cover T2/T3 closure-safety, ref-cursor gap-fill, metadata non-inheritance, folded-parent fallback, and no-parent skip; e2e asserts a fork replay emits an already-folded wire with valid refs. No kernel change. Building now — PR link to follow.