OKLMdocumentation v1.0.3
On this page

Plan: On-Device Kernel Auto-Tuning Pass for the LLM Interpreter

Status: planned, not started.

Goal: add a Magnitude-style optimization pass that, on first load of a model, tries alternative configurations of each hot kernel on the actual hardware, keeps the fastest one that produces identical output, and caches the result so later loads are instant.

This document is written for Claude Code to execute. Work through the phases in order. Each phase ends with acceptance criteria; do not start the next phase until they pass. Commit at the end of each phase with a message of the form tune: phase N - <summary>.


Ground rules

  • Numerics never change. A tuned configuration is only accepted if its output matches the reference configuration (see the correctness gate in Phase 3). A speedup that changes a single logit is a bug, not a win.
  • Default path stays intact. If tuning is disabled, fails, times out, or the cache is corrupt, the interpreter must run exactly as it does today. Every change is additive and guarded.
  • Measure before and after. No performance claim without a number from the harness in Phase 1.
  • Small diffs. One kernel family or one subsystem per commit. If a change touches more than ~400 lines, split it.
  • Ask before: changing the model file format, changing the public API of the interpreter, adding a dependency, or deleting any existing kernel.
  • Don't guess the codebase. Phase 0 exists so that every later phase edits real files, not imagined ones.

Phase 0 — Discovery (read-only)

Map the interpreter before writing code. Produce docs/tuning/00-codebase-map.md with the answers to:

  1. Language, build system, test runner. How do I build, run, and test? What's the exact command for each?
  2. Backends. Which compute backends exist (CPU, Metal, CUDA, Vulkan, etc.)? Where is backend selection made?
  3. Kernel inventory. List every compute kernel on the forward path. For each: file, function name, backend, the shapes it sees at prefill vs decode, and whether it's already parameterized in any way (tile size, thread count, block size, etc.). Expect roughly: matmul / quantized matmul (GEMM + GEMV), attention (QK^T, softmax, PV), RMSNorm/LayerNorm, RoPE, SiLU/GeLU + gating, embedding lookup, LM head, KV cache read/write, dequantization.
  4. Dispatch point. Where does the interpreter decide which kernel implementation to call for a given op? Is there a single dispatch table, or are calls hard-wired?
  5. Hot path. Profile one prefill (512 tokens) and one decode run (128 tokens) on a small model. Record the time share of each kernel. This drives the tuning budget in Phase 3.
  6. Model load path. Where are weights loaded, and where is the earliest point at which model architecture, quantization type, and tensor shapes are all known?
  7. Config/state storage. Where does the interpreter already persist anything (config file, cache dir)? Use the same location convention for the tuning cache.
  8. Determinism. Given fixed inputs, is the forward pass bit-identical across runs on each backend? If not, why (atomics, reduction order, threading)? This decides whether the correctness gate can be bitwise or needs a tolerance.

Acceptance: 00-codebase-map.md exists, every kernel on the hot path is listed with file:line, and the profile table sums to ~100% of forward time.


Phase 1 — Benchmark harness and reference oracle

Build the measurement tools everything else depends on.

1.1 Microbenchmark per kernel

  • bench/kernel_bench.<ext>: runs a single kernel with a given config and realistic shapes, warms up, times N iterations, reports median and p90 in µs. Must accept shapes from the command line so prefill (large M) and decode (M=1) are both covered.
  • Pin threads / use the same GPU queue the interpreter uses, so numbers transfer.

1.2 End-to-end benchmark

  • bench/e2e_bench.<ext>: loads a model, runs prefill on a fixed 512-token prompt, then 128 decode steps with greedy sampling. Reports prefill tok/s, decode tok/s, time-to-first-token, peak memory.
  • Output JSON so runs can be diffed. Store a baseline in bench/baselines/<device>-<model>.json.

1.3 Reference oracle

  • bench/oracle.<ext>: for a kernel + shapes + fixed seeded inputs, computes the output with the current default configuration and stores it. Later configs are compared against this.
  • Comparison function: bitwise equality where Phase 0 showed determinism; otherwise max-abs-diff with a tolerance derived from running the default config twice (tolerance = 2× observed run-to-run noise, floor at float-type epsilon). Document the chosen tolerance per kernel in docs/tuning/01-tolerances.md.

Acceptance: baseline JSON exists for at least one model on the primary dev machine; oracle comparison of default-vs-default passes; running the harness twice gives decode tok/s within 3%.


Phase 2 — Parameterize the kernels

Turn hard-coded constants into a config the dispatcher can vary. One kernel family per commit.

2.1 Config schema

Add a KernelConfig type (or the language's equivalent) per kernel family. Typical knobs:

Kernel Knobs
GEMM (prefill) tile M/N/K, threads per group, register blocking, unroll factor, prefetch depth / software pipelining stages
GEMV (decode) rows per thread, threads per row, SIMD width, how many quant blocks are dequantized per step
Attention KV tile size, heads per group, whether to use online softmax, split-K factor for long context
Norms / RoPE / activations elements per thread, threads per group
Dequant blocks per thread, vectorization width

Each kernel declares its own search space (a list of candidate values per knob) and a validity predicate (e.g., tile must divide the problem size, thread count ≤ device max). Keep the spaces small at first; 50–300 valid combinations per kernel is plenty.

2.2 Make kernels honor the config

  • CPU: template/const-generic instantiation or runtime parameters on the inner loop — prefer compile-time where the language allows so the optimizer sees constants.
  • GPU: either precompile a small set of variants, or JIT/specialize at tune time (Metal function constants, CUDA templates + NVRTC, etc.). Choose whichever your backend already supports; note the choice in docs/tuning/02-parameterization.md.
  • The default config must reproduce today's code path exactly (same constants). Verify with the oracle.

2.3 Dispatch

  • Introduce a single dispatch layer (if Phase 0 found there isn't one) that takes (op, shapes, backend) and returns the kernel + config. Initially it always returns defaults.

Acceptance: all kernels on the hot path read their constants from a config; e2e benchmark with default configs is within noise of the Phase 1 baseline; oracle passes for every kernel at default config.


Phase 3 — The tuner

3.1 Budget

  • Total budget: ~60 s wall clock per model on first load (configurable, default tune.budget_seconds = 60).
  • Split the budget across kernels proportionally to their time share from the Phase 0 profile (re-measured at tune time with a short pre-pass so it reflects this model). A kernel with <2% share gets no budget and keeps defaults.
  • Test-input preparation counts against the budget and is done once per kernel, not once per candidate.

3.2 Search strategy

Start simple, measure, then get fancier only if needed:

  1. Validity filter: drop candidates the predicate rejects.
  2. Coordinate descent from the default: vary one knob at a time, keep the best, iterate until no knob improves. Usually converges in a fraction of a grid search.
  3. If budget remains, random sampling of the full space.
  4. Each candidate: warm up 2 iterations, time 5, take median. Early-exit a candidate if its first timed iteration is >1.5× the current best.

3.3 Correctness gate

  • Every candidate's output is checked against the Phase 1 oracle before it can become "best". A faster-but-wrong candidate is logged and discarded.
  • The final winner is re-validated on a second set of random inputs.

3.4 Shape buckets

  • Decode (M=1) and prefill (M≥32) are tuned separately. Optionally bucket prefill by M (e.g., 32, 128, 512+) if Phase 0 showed the optimum differs.

3.5 Robustness

  • Any exception/compile failure in a candidate → skip it, continue.
  • If a kernel's default config itself fails on this device (e.g., too many threads for the chip), start the search from the nearest valid config, as Magnitude's release notes describe.
  • Hard timeout on the whole pass; on timeout, use the best found so far per kernel.

Acceptance: tune CLI subcommand (or flag) runs the pass on a model and prints a table: kernel, default µs, best µs, speedup, winning config. On the dev machine at least one kernel shows a measurable gain and nothing regresses. Oracle passes for every winner.


Phase 4 — Persistent cache

4.1 Cache key

Hash of: device identifier (GPU name + driver/toolchain version, or CPU model + ISA flags), backend, model architecture, quantization type(s), tensor shapes that affect kernel choice, kernel source version (a hash of the kernel files, so editing a kernel invalidates its entries), tuner version.

4.2 Storage

  • One JSON (or the project's existing config format) file per cache key under the interpreter's existing cache directory: <cache_dir>/tuning/<key>.json.
  • Contents: per-kernel per-shape-bucket winning config, measured µs, timestamp, tuner version.
  • Atomic write (write temp + rename). Corrupt/unreadable file → ignore and retune.

4.3 Invalidation

  • Key mismatch → miss. Entries older than tune.max_age_days (default 90) → retune in the background on next load while using the stale entry.

Acceptance: second load of a tuned model skips tuning and matches the tuned speed; editing a kernel file causes a retune of only that kernel's entries; deleting the cache dir is safe.


Phase 5 — Integration into model load

  • At the point found in Phase 0 step 6: compute cache key → lookup → on miss run tuner → apply configs to the dispatcher.
  • Progress reporting to whatever UI/log the interpreter has ("Tuning kernels for this device: 23/60 s, GEMV 1.4× so far").
  • Flags/config:
    • tune.enabled (default on), tune.budget_seconds, tune.force (ignore cache), tune.cache_dir.
    • --no-tune CLI escape hatch.
  • Tuning runs once per cache key, not per process; concurrent processes should take a file lock so they don't both tune.

Acceptance: fresh install → first load tunes with visible progress → subsequent loads are instant and fast. --no-tune reproduces Phase 1 baseline exactly.


Phase 6 — Validation and regression protection

  1. End-to-end numbers: re-run e2e_bench tuned vs --no-tune on every available device; record in docs/tuning/06-results.md with device, model, quant, prefill/decode tok/s before/after.
  2. Output equivalence: greedy-decode 256 tokens from 5 fixed prompts tuned vs untuned; token sequences must be identical (or logits within the Phase 1 tolerance where non-determinism was documented).
  3. Tests:
    • Unit: cache key stability, cache round-trip, validity predicates, oracle comparison.
    • Integration: tuner on a tiny synthetic model completes under budget and never selects a config that fails the oracle (inject a deliberately wrong kernel variant to prove the gate works).
    • CI: run the untuned path in CI (fast); run tuned path nightly or on a self-hosted runner if one exists.
  4. Docs: user-facing section in the README: what tuning does, how long it takes, how to disable it, where the cache lives.

Acceptance: all tests green; results table populated; equivalence check passes.


Out of scope for this pass (candidate follow-ups)

These are the other things that make an agent-oriented engine fast; they're separate projects, not part of kernel tuning:

  • Speculative decoding with a per-model drafter.
  • Quantized KV cache with memory released when sessions end.
  • Prefix-cache sharing across concurrent sessions.
  • JIT compilation of whole fused graphs rather than per-kernel parameter search.

Suggested file layout

src/tuning/
  config.<ext>        # KernelConfig types + search spaces + validity predicates
  tuner.<ext>         # budget split, search, correctness gate
  cache.<ext>         # key hashing, load/save, locking
  dispatch.<ext>      # op -> (kernel, config) resolution
bench/
  kernel_bench.<ext>
  e2e_bench.<ext>
  oracle.<ext>
  baselines/
docs/tuning/
  00-codebase-map.md
  01-tolerances.md
  02-parameterization.md
  06-results.md
tests/tuning/

Adapt names and extensions to the project's conventions; the structure matters more than the names.


Kick-off prompt for Claude Code

Read docs/kernel-autotune-plan.md in full. Start with Phase 0 only: explore the codebase, run the build and tests, profile one prefill and one decode, and write docs/tuning/00-codebase-map.md. Do not modify any source files in Phase 0. When the acceptance criteria are met, summarize what you found — especially anything in the plan that doesn't match the real codebase — and stop so I can review before Phase 1.