Skip to content

Run frontier MoE models on hardware you already own — pure C, zero deps, experts streamed from disk. Tiny engine, immense model. 🐦

C
10.6 KB
Raw Blame
/* spec_draft.h -- what a speculative verify should carry, and whether drafting pays.
 *
 * An engine with a verify forward (several rows in one forward, each computed the way a
 * decode step computes it, so the rows that stand give the logits plain decoding gives)
 * can take its drafts from any source: its MTP head, or the context itself. This header
 * holds the parts that do not depend on the engine; it has no engine state and no clock.
 *
 *   spec_lookup   prompt lookup: the longest n-gram (max_n down to min_n tokens) that ends
 *                 the token history and also occurs earlier in it, at its most recent earlier
 *                 occurrence; the up to k tokens that followed it there are the proposal.
 *                 Code edits, quotes and repeated structure give long runs of accepted
 *                 drafts; free text gives few proposals, and short ones.
 *
 *   SpecGate      how many drafts a verify should carry. Per source it keeps the running
 *                 probability a_j that draft j is accepted when the drafts before it were,
 *                 the measured seconds T(n) of a forward of n rows, and the measured seconds
 *                 d a source spends on each draft past its first. The depth k it picks
 *                 maximizes the expected tokens per second of a verify against a plain step:
 *                     value(k) = E(k) / cost(k)
 *                     E(k)     = 1 + a_1 + a_1 a_2 + ... + a_1 ... a_k   (tokens it yields)
 *                     cost(k)  = (T(k+1) + (k-1) d) / T(1)              (in decode steps)
 *                 and drafts only when value(k) > 1 (k = 0 is a plain step, value 1). A row
 *                 count not measured yet costs T(1) (1 + (n-1) rho), rho fitted from the
 *                 multi-row forwards that ran (SPEC_RHO0 until one has). Every SPEC_PROBE
 *                 picks the gate tries one draft deeper than its best (so an estimate the
 *                 gate stopped feeding can recover; every SPEC_PROBE_NEW while that deeper
 *                 verify's cost has fewer than 3 measurements), and after SPEC_REFRESH
 *                 forwards with no plain step it takes one, so T(1) stays measured.
 *
 * Neither ever changes a token: every proposal goes through the engine's verify, which
 * keeps exactly what plain decoding produces. They change how many forwards that takes.
 *
 * Callers: qwen38_core.h (MTP drafts and prompt lookup, combined) and qwen36.c (prompt
 * lookup). docs/speculative.md describes how another engine with a verify path wires it. */
#ifndef COLI_SPEC_DRAFT_H
#define COLI_SPEC_DRAFT_H

#include <stdlib.h>
#include <string.h>

#define SPEC_MAX_DRAFTS 8          /* positions the gate tracks (an engine's verify may take fewer) */
#define SPEC_PROBE      16         /* every this many picks, one draft deeper than the best */
#define SPEC_PROBE_NEW  4          /* the same while that deeper row count is barely measured */
#define SPEC_REFRESH    64         /* forwards with no plain step before the gate takes one */
#define SPEC_RHO0       0.5        /* a row's extra cost, relative to one row, before any is measured */
#define SPEC_ACC_W      16.0       /* the acceptance's memory, in verifies */
#define SPEC_T_W        8.0        /* a forward time's memory, in forwards */

enum { SPEC_SRC_MTP = 0, SPEC_SRC_LOOKUP = 1, SPEC_NSRC = 2 };

typedef struct {
    double acc[SPEC_NSRC][SPEC_MAX_DRAFTS];   /* a_{j+1}: P(draft j+1 accepted | drafts 1..j accepted) */
    double acc_w[SPEC_NSRC][SPEC_MAX_DRAFTS]; /* weight behind it (a prior's pseudo-count first) */
    double t[SPEC_MAX_DRAFTS + 2];            /* T(n), seconds of a forward of n rows; t_w 0 = not measured */
    double t_w[SPEC_MAX_DRAFTS + 2];
    double rho, rho_w;                        /* a row's extra cost relative to one row */
    double d[SPEC_NSRC], d_w[SPEC_NSRC];      /* seconds a source spends per draft past its first */
    int picks[SPEC_NSRC];                     /* picks so far (the probe's clock) */
    int since_plain;                          /* forwards since the last plain step */
    int off;                                  /* 1: every proposal drafted in full (tests, fixed depths) */
    /* the run's counts, for the engines' report lines */
    unsigned long long prop[SPEC_NSRC][SPEC_MAX_DRAFTS], hit[SPEC_NSRC][SPEC_MAX_DRAFTS];
    unsigned long long verifies[SPEC_NSRC], probes[SPEC_NSRC], declined[SPEC_NSRC];
} SpecGate;

static inline void spec_gate_init(SpecGate *g, int off) {
    memset(g, 0, sizeof *g);
    g->off = off;
    for (int j = 0; j < SPEC_MAX_DRAFTS; j++) {
        /* priors, worth two verifies each: an MTP head is trained to be right, and each
         * draft past the first reads the head's own state instead of the model's */
        g->acc[SPEC_SRC_MTP][j] = j == 0 ? 0.8 : j == 1 ? 0.6 : 0.5;
        g->acc[SPEC_SRC_LOOKUP][j] = 0.5;
        g->acc_w[SPEC_SRC_MTP][j] = g->acc_w[SPEC_SRC_LOOKUP][j] = 2.0;
    }
    g->rho = SPEC_RHO0; g->rho_w = 1.0;
}

static inline void spec_ema(double *x, double *w, double v, double memory) {
    if (*w < memory) *w += 1.0;
    *x += (v - *x) / *w;
}

/* A forward of `rows` rows took `seconds` (a plain step, or a verify). */
static inline void spec_gate_forward(SpecGate *g, int rows, double seconds) {
    if (rows < 1 || rows > SPEC_MAX_DRAFTS + 1 || !(seconds > 0.0)) return;
    spec_ema(&g->t[rows], &g->t_w[rows], seconds, SPEC_T_W);
    if (rows == 1) { g->since_plain = 0; return; }
    g->since_plain++;
    if (g->t_w[1] > 0.0 && g->t[1] > 0.0) {
        double r = (seconds / g->t[1] - 1.0) / (rows - 1);
        if (r < 0.0) r = 0.0;
        if (r > 4.0) r = 4.0;
        spec_ema(&g->rho, &g->rho_w, r, SPEC_T_W);
    }
}

/* A source spent `seconds` on one draft past its first (an MTP head's extra step). */
static inline void spec_gate_draft_cost(SpecGate *g, int src, double seconds) {
    if (src < 0 || src >= SPEC_NSRC || !(seconds >= 0.0)) return;
    spec_ema(&g->d[src], &g->d_w[src], seconds, SPEC_T_W);
}

/* A verify's drafts from `src` were judged: the first `accepted` stood, and `judged` of
 * them were looked at (accepted + 1 after a rejection; accepted when every draft stood, or
 * when the generation ended before the rest were reached: those say nothing). */
static inline void spec_gate_result(SpecGate *g, int src, int judged, int accepted) {
    if (src < 0 || src >= SPEC_NSRC || judged < 1) return;
    if (judged > SPEC_MAX_DRAFTS) judged = SPEC_MAX_DRAFTS;
    if (accepted > judged) accepted = judged;
    g->verifies[src]++;
    for (int j = 0; j < judged; j++) {
        g->prop[src][j]++;
        if (j < accepted) g->hit[src][j]++;
        spec_ema(&g->acc[src][j], &g->acc_w[src][j], j < accepted ? 1.0 : 0.0, SPEC_ACC_W);
    }
}

/* T(n) in units of T(1): measured, or the fitted line. */
static inline double spec_gate_rows_cost(const SpecGate *g, int rows) {
    if (rows <= 1) return 1.0;
    if (rows <= SPEC_MAX_DRAFTS + 1 && g->t_w[rows] > 0.0 && g->t_w[1] > 0.0 && g->t[1] > 0.0)
        return g->t[rows] / g->t[1];
    return 1.0 + (rows - 1) * g->rho;
}

/* The expected tokens a verify of k drafts from src yields, and that per unit of time
 * against a plain step (value 1). */
static inline double spec_gate_value(const SpecGate *g, int src, int k, double *expect) {
    double e = 1.0, p = 1.0;
    for (int j = 0; j < k && j < SPEC_MAX_DRAFTS; j++) { p *= g->acc[src][j]; e += p; }
    double cost = spec_gate_rows_cost(g, k + 1);
    if (k > 1 && g->d_w[src] > 0.0 && g->t_w[1] > 0.0 && g->t[1] > 0.0) cost += (k - 1) * g->d[src] / g->t[1];
    if (expect) *expect = e;
    return k > 0 ? e / cost : 1.0;
}

/* How many of the up to maxk drafts src can offer the next verify should carry: 0 for a
 * plain step. *value gets that depth's value (1 for a plain step). */
static inline int spec_gate_pick(SpecGate *g, int src, int maxk, double *value) {
    if (value) *value = 1.0;
    if (maxk <= 0 || src < 0 || src >= SPEC_NSRC) return 0;
    if (maxk > SPEC_MAX_DRAFTS) maxk = SPEC_MAX_DRAFTS;
    if (g->off) { if (value) *value = spec_gate_value(g, src, maxk, NULL); return maxk; }
    if (g->since_plain >= SPEC_REFRESH) { g->declined[src]++; return 0; }   /* keep T(1) measured */
    int best = 0; double bv = 1.0;
    for (int k = 1; k <= maxk; k++) {
        double v = spec_gate_value(g, src, k, NULL);
        if (v > bv) { bv = v; best = k; }
    }
    /* explore one deeper: every SPEC_PROBE picks, every SPEC_PROBE_NEW while that row
     * count has fewer than 3 measurements (its cost is still the fitted line's guess) */
    int every = best < maxk && g->t_w[best + 2] < 3.0 ? SPEC_PROBE_NEW : SPEC_PROBE;
    if (++g->picks[src] % every == 0 && best < maxk) {
        best++; bv = spec_gate_value(g, src, best, NULL); g->probes[src]++;
    }
    if (!best) g->declined[src]++;
    if (value) *value = bv;
    return best;
}

/* What the gate measured, for a report line: T(1), the cost of the row counts seen (in
 * units of T(1)), the fitted rho, a source's cost per extra draft and its acceptance
 * estimates by position. */
#include <stdio.h>
static inline void spec_gate_describe(const SpecGate *g, int src, char *buf, size_t cap) {
    size_t at = 0;
    if (!cap) return;
    buf[0] = 0;
#define SPEC_PUT(...) do { int w_ = snprintf(buf + at, cap - at, __VA_ARGS__); \
                           if (w_ < 0 || (size_t)w_ >= cap - at) return; at += (size_t)w_; } while (0)
    SPEC_PUT("T(1) %.1f ms, rows", g->t_w[1] > 0.0 ? 1e3 * g->t[1] : 0.0);
    for (int n = 2; n <= SPEC_MAX_DRAFTS + 1; n++)
        if (g->t_w[n] > 0.0) SPEC_PUT(" %d:%.2f", n, spec_gate_rows_cost(g, n));
    SPEC_PUT(", rho %.2f", g->rho);
    if (g->d_w[src] > 0.0) SPEC_PUT(", %.1f ms per extra draft", 1e3 * g->d[src]);
    SPEC_PUT(", acceptance by position");
    for (int j = 0; j < 5; j++) SPEC_PUT(" %.2f", g->acc[src][j]);
#undef SPEC_PUT
}

/* Prompt lookup: up to k tokens proposed for what follows h[0..len), from the most recent
 * earlier occurrence of the longest suffix of n tokens, max_n >= n >= min_n, that has one
 * with at least one token after it. Returns how many were written to out. */
static inline int spec_lookup(const int *h, int len, int min_n, int max_n, int k, int *out) {
    if (!h || !out || k < 1 || min_n < 1 || len < min_n + 1) return 0;
    if (max_n > len - 1) max_n = len - 1;
    for (int n = max_n; n >= min_n; n--) {
        const int *suf = h + len - n;
        for (int i = len - n - 1; i >= 0; i--) {   /* h[i..i+n) against the suffix, h[i+n] after it */
            if (h[i + n - 1] != suf[n - 1] || memcmp(h + i, suf, (size_t)n * sizeof(int))) continue;
            int g = 0;
            for (int j = i + n; j < len && g < k; j++) out[g++] = h[j];
            return g;
        }
    }
    return 0;
}

#endif /* COLI_SPEC_DRAFT_H */