HELIX Columnar Embedding — Design Proposal

Status: PROPOSED. Pivot from lossy GKQ spectral compression of the embedding matrix toward a row-addressed sparse fetch over the existing HELIX transport.

Companion artifacts:

• validate-columnar-embed.py — bandwidth measurement script.
• COLUMNAR_BANDWIDTH_REPORT.md — locked numbers for Qwen2.5-0.5B-Instruct.

1. Problem

The current GKQ v2 encoder is required to ship the embedding tensor as a spectral-rank-K block (rank-3, rank-64, rank-256 variants were all tried) or as a dense block. Both options are bad for a bandwidth-bound distributed inference fabric:

• Spectral rank-K is lossy. Empirically, rank-256 SVD of a Qwen0.5B 24-layer model still produced gibberish at decode time. LLM weight matrices carry rich rank structure across the full vocab; truncating to even a few hundred singular vectors throws away information the model materially uses.
• Dense ship is huge. token_embd.weight for Qwen2.5-0.5B-Instruct is 151,936 × 896 × 4 B = 519.31 MB (fp32). It alone dominates the GKQ knot (cited 543 MB / 648 MB total observed; the small delta is dtype/packing). For a distribution mechanism whose value proposition is "ship knots cheaply, run anywhere," shipping half a gigabyte of dense embeddings to every node per cold start is a non-starter — and ranks the lower bound of per-node wall-clock at the network's slowest hop.

A different shape of compression is needed: one that gives zero quality loss and exploits the structure of how the embedding tensor is actually accessed, not just how it factors algebraically.

2. Insight

Per-session token access is extremely sparse.

A real measurement (see COLUMNAR_BANDWIDTH_REPORT.md) on Qwen/Qwen2.5-0.5B-Instruct across six workloads:

Even the long-context workload (628 tokens of mixed English literary prose) only ever touches 109 distinct vocab IDs. The bandwidth-bound cost of shipping a full 519 MB matrix to satisfy a request that reads 109 rows of 3,584 bytes each (381.5 KB) is absurd. A row-addressed store closes the gap to within 0.07% of the dense ship — and to within 0.002% under multi-session amortization.

3. Architecture: HELIX columnar embed

Wire format. A row-aligned binary file, row-major, no per-row framing:

file[i * row_bytes : (i+1) * row_bytes]  =  embedding[token_id = i]
row_bytes = hidden_dim * dtype.itemsize

For Qwen2.5-0.5B-Instruct: row_bytes = 896 * 4 = 3584 B at fp32, or 1792 B at fp16 / bf16. Total file size is unchanged from the dense matrix (519 MB fp32 / 260 MB bf16), but the file is now range-fetchable: any HTTP byte-range request Range: bytes={i*3584}-{(i+1)*3584-1} returns exactly the embedding for token_id = i.

Index. Trivial. Row i lives at byte offset i * row_bytes. No B-tree, no hash map sidecar, no manifest indirection — just multiplication. R2 (Cloudflare) already serves HTTP range requests; no infra change.

Optional sidecar (embed-rows.idx). Only needed if rows are heterogeneous. Examples:

• Mixed precision per row (e.g. ASCII tokens in fp16, long-tail Unicode in fp8 to amortize storage).
• Quantized rows where the dequant header (scale/zero) lives inline with the row payload.

For a homogeneous fp32/fp16/bf16 store, skip the sidecar entirely.

Cache policy. Per-node LRU over recently-fetched rows. The multi-tenancy win is the headline number: BOS, EOS, common BPE pieces (the, ,, ., leading-space variants) saturate the warm set in the first few sessions, and from then on the marginal per-session cost is just the cold-row tail. Measured: across 100 random sessions drawn from the workload mix, with a top-100 warm seed (350 KB), the total cold bytes paid across all 100 sessions was 647.50 KB — a global ratio of 0.001876% against ship-dense-per-session, or 99.998124% bandwidth saved.

4. Integration with fat-station (sketch only)

This document does not touch any .rs source. Two flags should be added to fat-station in a follow-on PR:

• --columnar-embed <URL>: source of the row store. The existing HttpBackend already issues range-fetches; either extend it or introduce ColumnarEmbedBackend whose responsibility is:
  1. Hold (row_bytes, vocab_size) once.
  2. Translate a token_id (or a batch of them) into a byte-range request.
  3. Maintain an in-process LRU keyed by token_id.
• --embed-cache-rows N: in-memory row cache size, default 8192 (~28 MB at fp32 / ~14 MB at fp16 — well within edge-node budgets and enough to cover the warm tail of realistic multi-tenant traffic).

The forward-pass change is local: where the model currently reads token_embd.weight and indexes it densely, it instead calls embed.row(token_id) per input position. Pipeline coalesces row fetches across a batch into a single multi-range or N parallel range requests.

The first --columnar-embed reads cost one round-trip per cold row; on a warm node the cache absorbs them.

5. Handling lm_head

The same matrix (when untied) is consulted at every decode step to compute logits = hidden @ lm_head.T, requiring all vocab rows for argmax. Naive sparse fetch cannot work here. Three options, ranked by how much of the win they preserve:

(a) Tied embeddings (Qwen-style). tie_word_embeddings: true: one matrix is shared as both input lookup and output projection. Columnar fetch handles the input lookup; the output projection still needs the full matrix resident at decode time — but it's the same matrix, fetched once per node and amortized across the lifetime of that node. Net per-node cold-start cost: ~50% of dense (one full pull instead of per-session re-ships), and the per-session cost on a warm node remains the sparse input-lookup win.

(b) Cache lm_head once, amortize across N decoded tokens. Even for untied models, lm_head is static for the lifetime of the model. Pull it once on first decode, retain it. After ~100 generated tokens the per-token marginal cost of holding it is zero.

(c) Speculative top-k. Precompute a coarse vocab-tree sketch (~5 MB) that narrows candidate token IDs to the top-50 likely at each decode step, then sparse-fetch only those lm_head rows for the exact argmax. Approximate, but >>99% bandwidth saved. Pair with a fallback to (b) when the sketch's top-50 confidence drops below a calibrated threshold.

For the Phase A pivot, (a) is enough: it covers Qwen, Phi, Llama-3, and any model with tied embeddings — i.e., most of the targets actually in play for the distributed-inference fabric today.

6. Why this kills the GKQ rank-3 dead end

Spectral compression sacrificed quality for size. Rank-3 was small but unusable; rank-256 was usable in synthetic tests but degenerated on real 24-layer Qwen inference. The space between "small enough to ship" and "good enough to use" wasn't there.

Columnar embed has a different shape:

• Zero accuracy loss. Rows are stored exact (down to the requested dtype). No SVD, no truncation, no kernel approximation. The rows are bit-identical to what the model would have indexed dense.
• Bigger bandwidth wins than rank-3. Rank-3 saved ~99% of bytes at catastrophic quality cost. Columnar saves 99.93%–99.998% depending on workload and amortization — at zero quality cost.
• GKQ's right role. Spectral GKQ moves from "the bandwidth scheme" to "a small sketch payload for cache-miss fallback paths and for representations that genuinely are low-rank" (some attention weight matrices have observed low effective rank — those keep their spectral blocks). Embedding and lm_head are the wrong tensors for that.

7. Compatibility with GKQ v2

The encoder gets one new optional behavior: flag any dense tensor block as columnar-eligible in its block header (a single reserved bit; the v2 format already has unused header bits). The loader on the consumer side honors the following priority order when resolving a tensor read:

1. If --columnar-embed is provided and the GKQ knot has a columnar-eligible flag set for this tensor name and the URL responds with the expected Content-Length = vocab_size * row_bytes, route reads of that tensor through ColumnarEmbedBackend.
2. Else fall back to the dense block in the GKQ knot.
3. Spectral blocks remain untouched: they're for genuinely-low-rank tensors, not for embedding/lm_head.

This is backward compatible: existing GKQ v2 knots have the flag bit clear and continue to load dense. New knots can advertise columnar availability without breaking any consumer.

8. Numbers

From COLUMNAR_BANDWIDTH_REPORT.md (regenerate with python3 validate-columnar-embed.py):

• Full embed (Qwen0.5B fp32): 519.31 MB.
• Per-session columnar fetch, range 94.50 KB (qa_short) – 381.50 KB (long_context).
• Per-session bandwidth saved: 99.928% – 99.982%.
• 100-session multi-tenant amortization: total bytes paid = 997.50 KB (warm seed 350 KB + 647.50 KB cold tail) vs naive dense-per-session = 50.71 GB. Saved: 99.998124%.

At fp16 / bf16 the per-row size halves; the ratio against dense ship is unchanged (both numerator and denominator halve), but absolute bytes on the wire drop accordingly.

9. Roadmap

• Phase A (this PR). Spec + validation script + locked numbers report. No .rs changes.
• Phase B (separate, after fat-station coordination). Rust ColumnarEmbedBackend impl, --columnar-embed and --embed-cache-rows flags wired through fat-station's forward path, R2 upload of a real Qwen columnar embed file. Acceptance: a Qwen0.5B decode session bootstraps from a cold node with <500 KB embedding bytes transferred (vs the current 519 MB).
• Phase C. lm_head speculative top-k vocab sketch for untied models; calibrated fallback when the sketch's confidence drops. Acceptance: full Llama-3-8B decode session bootstraps with <50 MB total embedding+lm_head bytes transferred per node.

Appendix A: Why not just gzip / zstd the dense matrix?

Tried implicitly: weight matrices have near-uniform entropy after training, so generic entropy coding gives ~10–15% savings. Useful but nowhere near the 4–6 orders of magnitude that columnar sparsity gives, and incurs decompression CPU at every node. Column sparsity is the right axis because access is sparse; entropy coding is the wrong axis because the bits are high-entropy.

Appendix B: Why not Bloom-filter the row IDs and prefetch?

A Bloom prefilter would help if we wanted to speculatively warm rows ahead of a request — but tokenization is fast and exact, so we already know the precise row IDs before the forward pass starts. The honest prefetch is "tokenize, dedupe, issue range fetches in parallel before the embed lookup." No probabilistic structure needed.