Skip to content

Official Inference Code of EAGLE-4

19.4 KB
Raw Blame
# Copyright 2026 Eagle AI Corp.
# SPDX-License-Identifier: LicenseRef-Eagle-4-Source-Available

"""EAGLE-Harness draft-tree kernels against PyTorch references."""

import sys

import numpy as np
import pytest
import torch

pytest.importorskip("tvm_ffi", reason="TokenSpeed round kernels require apache-tvm-ffi")

from eagle_harness.tokenspeed.tree_round.ops.tree import (
    eagle_harness_draft_depth_update,
    eagle_harness_stable_topk_desc,
    eagle_harness_update_node_data,
    eagle_harness_work_deltas,
    eagle_harness_write_verify_tree,
)

pytestmark = pytest.mark.skipif(
    not torch.cuda.is_available(), reason="CUDA GPU is required"
)

_DEVICE = "cuda"


@pytest.mark.parametrize("k", [2, 4, 8])
def test_update_root_children(k):
    bs, columns = 3, 65
    generator = torch.Generator().manual_seed(k)
    scores = torch.rand((bs, k), generator=generator).to(_DEVICE)
    tokens = torch.randint(0, 1000, (bs, k), generator=generator).to(_DEVICE)
    # Row strides may differ between the pool and the work/sort lists.
    pool_scores = torch.full((bs, columns), -1.0, device=_DEVICE)
    pool_tokens = torch.full((bs, columns), -1, dtype=torch.int64, device=_DEVICE)
    work = torch.full((bs, 64 + k), -1.0, device=_DEVICE)
    sort = torch.full((bs, 64), -1.0, device=_DEVICE)
    eagle_harness_update_node_data(pool_scores, pool_tokens, work, sort, scores, tokens)
    for target in (pool_scores, work, sort):
        assert torch.equal(target[:, 1 : k + 1], scores)
        assert (target[:, 0] == -1).all()
        assert (target[:, k + 1 :] == -1).all()
    assert torch.equal(pool_tokens[:, 1 : k + 1], tokens)


def _count(value: int) -> torch.Tensor:
    """A device int32 ``[1]`` count, as the drafter's round state holds them."""
    return torch.tensor([value], dtype=torch.int32, device=_DEVICE)


def _distinct_scores(rows: int, cols: int, generator: torch.Generator) -> torch.Tensor:
    """Scores in (0, 1) whose values and products almost surely never tie."""
    return (torch.rand((rows, cols), generator=generator) * 0.98 + 0.01).to(_DEVICE)


@pytest.mark.parametrize("n,k", [(5, 5), (1024, 64)])
def test_stable_topk_desc(n: int, k: int) -> None:
    generator = torch.Generator().manual_seed(n)
    # Few distinct values: ties must keep the lower index first. A padded row
    # and columns past n (as in a captured graph) are never read or written.
    cols = min(n + 3, 1024)
    scores = (torch.randint(0, 8, (4, cols), generator=generator).float() / 8).to(
        _DEVICE
    )
    values = torch.full((4, k + 2), -1.0, device=_DEVICE)
    indices = torch.full((4, k + 2), -1, dtype=torch.int64, device=_DEVICE)
    eagle_harness_stable_topk_desc(
        scores, _count(3), _count(n), _count(k), values, indices
    )
    expected = torch.sort(scores[:3, :n], dim=-1, descending=True, stable=True)
    torch.testing.assert_close(values[:3, :k], expected.values[:, :k], rtol=0, atol=0)
    torch.testing.assert_close(indices[:3, :k], expected.indices[:, :k], rtol=0, atol=0)
    assert (values[3] == -1).all() and (values[:, k:] == -1).all()


@pytest.mark.parametrize("node_count,verify_num", [(1, 16), (7, 16), (14, 16)])
def test_work_deltas(node_count: int, verify_num: int) -> None:
    bs, topk = 3, 4
    generator = torch.Generator().manual_seed(node_count)
    # One padded row past the live ones, as in a captured graph.
    work = torch.ones((bs + 1, verify_num + topk), device=_DEVICE)
    work[:bs] = 0.0
    work[:bs, :node_count] = (
        _distinct_scores(bs, node_count, generator).sort(dim=-1, descending=True).values
    )
    work[:bs, node_count : node_count + topk] = (
        _distinct_scores(bs, topk, generator).sort(dim=-1, descending=True).values
    )
    deltas = torch.empty(topk + 1, device=_DEVICE)
    live_rows = torch.tensor([bs], dtype=torch.int32, device=_DEVICE)
    counts = _count(node_count), _count(verify_num)
    eagle_harness_work_deltas(work, deltas, live_rows, counts[0], topk, counts[1])
    unpadded = torch.empty(topk + 1, device=_DEVICE)
    eagle_harness_work_deltas(
        work[:bs], unpadded, live_rows, counts[0], topk, counts[1]
    )
    # A zero node count queues no deltas.
    untouched = torch.full((topk + 1,), -1.0, device=_DEVICE)
    eagle_harness_work_deltas(work, untouched, live_rows, _count(0), topk, counts[1])
    eagle_harness_work_deltas(work, untouched, _count(0), counts[0], topk, counts[1])

    assert torch.equal(deltas, unpadded) and (untouched == -1).all()
    expected = []
    for j in range(topk + 1):
        merged = work[:bs, : node_count + j].sort(dim=-1, descending=True).values
        expected.append(merged[:, : min(node_count + j, verify_num)].sum(-1).mean())
    torch.testing.assert_close(deltas, torch.stack(expected), rtol=1e-6, atol=1e-6)


def _work_deltas_reference(
    work: np.ndarray, bs: int, node_count: int, verify_num: int, topk: int, rows: int
) -> np.ndarray:
    """The work deltas in the kernel's float32 order: each row's merge summed
    in turn, then a halving tree over 256 threads, or 512 above 256 rows,
    whose padded rows hold zeros."""
    threads = 256 if rows <= 256 else 512
    out = np.zeros(topk + 1, dtype=np.float32)
    for j in range(topk + 1):
        sums = np.zeros(threads, dtype=np.float32)
        for row in range(bs):
            head, tail = work[row, :node_count], work[row, node_count:]
            a = b = 0
            total = np.float32(0.0)
            for _ in range(min(node_count + j, verify_num)):
                va = head[a] if a < node_count else np.float32(0.0)
                vb = tail[b] if b < j else np.float32(0.0)
                if va >= vb:
                    total, a = np.float32(total + va), a + 1
                else:
                    total, b = np.float32(total + vb), b + 1
            sums[row] = total
        half = threads // 2
        while half:
            sums[:half] = sums[:half] + sums[half : 2 * half]
            half //= 2
        out[j] = np.float32(sums[0] / np.float32(bs))
    return out


@pytest.mark.parametrize(
    "bs,rows",
    [(1, 1), (3, 4), (16, 32), (31, 32), (32, 32)],
)
def test_work_deltas_sum_order(bs: int, rows: int) -> None:
    """Bit for bit the kernel's summation order up to 512 rows (padded rows
    past the live ones, as in a captured graph); up to 256 live rows the
    256- and 512-thread halving trees give the same bits."""
    node_count, verify_num, topk = 7, 16, 4
    generator = torch.Generator().manual_seed(bs)
    work = torch.zeros((rows, verify_num + topk))
    work[:bs, :node_count] = _distinct_scores(bs, node_count, generator).cpu()
    work[:bs, :node_count] = work[:bs, :node_count].sort(-1, descending=True).values
    tail = _distinct_scores(bs, topk, generator).cpu().sort(-1, descending=True).values
    work[:bs, node_count : node_count + topk] = tail
    work[bs:] = 1.0
    deltas = torch.empty(topk + 1, device=_DEVICE)
    eagle_harness_work_deltas(
        work.to(_DEVICE),
        deltas,
        _count(bs),
        _count(node_count),
        topk,
        _count(verify_num),
    )
    expected = _work_deltas_reference(
        work.numpy(), bs, node_count, verify_num, topk, rows
    )
    assert np.array_equal(deltas.cpu().numpy(), expected)
    if bs <= 256:
        other = _work_deltas_reference(
            work.numpy(), bs, node_count, verify_num, topk, 512 if rows <= 256 else 256
        )
        assert np.array_equal(other, expected)


def _bitonic_sort_64(scores: torch.Tensor) -> tuple[torch.Tensor, torch.Tensor]:
    """The kernels' descending sort of each row's ``n <= 64`` scores: a
    bitonic network over 64 positions that skips every pair reaching past
    ``n`` and never swaps ties, so its order (not always fully sorted when
    ``n`` is not a power of two) is a fixed function of the inputs. Returns
    the values and their original positions."""
    rows, n = scores.shape
    values = scores.clone()
    order = torch.arange(n, device=scores.device).repeat(rows, 1)
    size = 2
    while size <= 64:
        stride = size // 2
        while stride:
            lower = [p for p in range(64) if not p & stride and p + stride < n]
            if lower:
                i = torch.tensor(lower, device=scores.device)
                j = i + stride
                vi, vj, oi, oj = values[:, i], values[:, j], order[:, i], order[:, j]
                swap = torch.where((i & size) == 0, vi < vj, vi > vj)
                values[:, i] = torch.where(swap, vj, vi)
                values[:, j] = torch.where(swap, vi, vj)
                order[:, i] = torch.where(swap, oj, oi)
                order[:, j] = torch.where(swap, oi, oj)
            stride //= 2
        size *= 2
    return values, order


def _lane_mask_words(mask: torch.Tensor, lane_mask: torch.Tensor) -> None:
    """Bool ``[rows, K, window]`` lane masks as int64 words: window slot ``j``
    at bit ``j % 64`` of word ``j // 64``, later words zero."""
    window = mask.shape[-1]
    bits = 1 << (torch.arange(window, device=mask.device) % 64)
    for word in range(lane_mask.shape[-1]):
        lo, hi = 64 * word, min(64 * word + 64, window)
        if lo >= hi:
            lane_mask[..., word].zero_()
            continue
        torch.sum(mask[..., lo:hi] * bits[lo:hi], dim=-1, out=lane_mask[..., word])


def _unfused_depth(
    state: dict[str, torch.Tensor],
    masks: list[torch.Tensor],
    child_p: torch.Tensor,
    child_tokens: torch.Tensor,
    expanded: torch.Tensor,
    child_hidden: torch.Tensor,
    depth: int,
    cumu_count: int,
    verify_num: int,
    num_slots: int,
) -> None:
    """The sequence the fused update replaces (the layer-gen and pool-update
    kernels, the next depth's bool ancestor masks ``masks[depth + 1]`` and
    their lane-mask words, the lane increments) on ``state``'s first rows."""
    rows, width, k = child_p.shape
    n = width * k
    row = torch.arange(rows, device=_DEVICE)[:, None]
    path = (child_p * state["scores"][:rows, :width, None]).reshape(rows, n)
    tokens = child_tokens.reshape(rows, n)
    layer, order = _bitonic_sort_64(path)
    best = order[:, :k]
    parent = best // k
    state["frontier_index"][depth % 2][:rows] = cumu_count + best
    state["scores"][:rows] = layer[:, :k]
    state["tokens"][:rows] = tokens.gather(1, best)
    state["hidden"][:rows] = child_hidden[row, parent]
    # Device powf: CUDA pow with a tensor exponent.
    decay = torch.pow(
        torch.tensor(0.9999, device=_DEVICE), torch.tensor(depth + 1.0, device=_DEVICE)
    )
    new = slice(cumu_count, cumu_count + n)
    child = torch.arange(n, device=_DEVICE)
    state["pool_tokens"][:rows, new] = tokens
    state["pool_scores"][:rows, new] = path * decay
    state["pool_depths"][:rows, new] = depth + 1
    state["pool_prev"][:rows, new] = expanded[:, :width].repeat_interleave(k, dim=1)
    state["pool_next"][:rows, new] = -1
    state["pool_side"][:rows, new] = torch.where(
        child % k == k - 1, -1, cumu_count + child + 1
    )
    first_child = cumu_count + k * torch.arange(width, device=_DEVICE)
    state["pool_next"][row, expanded[:, :width]] = first_child
    # Work list, then the sort list's stable rank merge with the children.
    head, kept = min(verify_num, cumu_count), min(verify_num, cumu_count + n)
    merged = torch.cat([state["sort"][:rows, :head], layer], dim=1)
    pos = torch.arange(merged.shape[1], device=_DEVICE)
    above = (merged[:, None, :] > merged[:, :, None]) | (
        (merged[:, None, :] == merged[:, :, None]) & (pos[None, :] < pos[:, None])
    )
    rank = above.sum(-1)
    state["work"][:rows, :head] = state["sort"][:rows, :head]
    state["work"][:rows, head : head + k] = layer[:, :k]
    keep = rank < kept
    state["sort"][row.expand_as(rank)[keep], rank[keep]] = merged[keep]
    # The next depth's ancestors: the parents' rows, then each lane's own slot.
    if (depth + 1) * k <= num_slots:
        window = depth * k
        masks[depth + 1][:rows, :, :window] = masks[depth][row, parent, :window]
        _lane_mask_words(masks[depth + 1][:rows], state["lane_mask"][:rows])
    state["positions"][:rows] += 1
    state["slot_starts"][:rows] += k


def _assert_bitwise_equal(actual: torch.Tensor, expected: torch.Tensor, name: str):
    assert torch.equal(actual.view(torch.uint8), expected.view(torch.uint8)), name


# K=2/4/8, including the sign bit of the 64-slot lane mask.
@pytest.mark.parametrize(
    "rows,max_rows,k,steps",
    [(3, 5, 2, 32), (3, 5, 4, 17), (3, 5, 8, 9), (32, 32, 8, 4)],
)
def test_draft_depth_update_matches_the_unfused_sequence(
    rows: int, max_rows: int, k: int, steps: int, disabled: bool = False
) -> None:
    """A round of depths at random widths: from the same forward outputs the
    fused update leaves every buffer bit-identical to the unfused sequence,
    ties included (few distinct probabilities and path scores); rows past
    ``rows`` (graph padding of the buffers) stay untouched."""
    gen = torch.Generator(device=_DEVICE).manual_seed(1000 * rows + 10 * k + steps)
    hidden_size = 1032  # 129 16-byte vectors per row
    nodes, verify = max(1024, k * k * steps), max(64, k * (steps + 1) + 1)
    num_slots = (steps - 1) * k
    words = (num_slots + 63) // 64

    def ints(shape, high=1000):
        return torch.randint(-1, high, shape, generator=gen, device=_DEVICE)

    def ties(shape):
        return torch.randint(1, 5, shape, generator=gen, device=_DEVICE) / 4

    state = {
        "pool_tokens": ints((max_rows, nodes)),
        "pool_scores": torch.rand((max_rows, nodes), generator=gen, device=_DEVICE),
        "pool_depths": ints((max_rows, nodes)),
        "pool_prev": ints((max_rows, nodes)),
        "pool_next": ints((max_rows, nodes)),
        "pool_side": ints((max_rows, nodes)),
        "work": torch.rand((max_rows, verify + k), generator=gen, device=_DEVICE),
        "sort": ties((max_rows, verify)).sort(dim=-1, descending=True).values,
        "tokens": ints((max_rows, k)),
        "scores": ties((max_rows, k)),
        "hidden": torch.randn(
            (max_rows, k, hidden_size), generator=gen, device=_DEVICE
        ).to(torch.bfloat16),
        "frontier_index": ints((2, max_rows, k)),
        "positions": ints((max_rows, k)),
        "slot_starts": ints((max_rows,)),
        "lane_mask": ints((max_rows, k, words), 1 << 62),
    }
    # Depth 1's lane masks: lane r sees its own slot.
    state["lane_mask"][:rows] = 0
    state["lane_mask"][:rows, :, :1] = (1 << torch.arange(k, device=_DEVICE))[:, None]
    fused = {name: t.clone() for name, t in state.items()}
    # The unfused sequence's bool masks per depth: stale ancestors, own slots.
    masks = [torch.empty(0)]
    for s in range(1, steps):
        mask = torch.rand((max_rows, k, s * k), generator=gen, device=_DEVICE) < 0.5
        mask[:, :, (s - 1) * k :] = torch.eye(k, dtype=torch.bool, device=_DEVICE)
        masks.append(mask)
    root_children = torch.arange(1, k + 1, device=_DEVICE).repeat(rows, 1)

    def fused_update(
        child_p, child_tokens, expanded, child_hidden, width, depth, cumu_count
    ):
        eagle_harness_draft_depth_update(
            child_p, child_tokens, expanded, child_hidden, fused["tokens"][:rows],
            fused["scores"][:rows], fused["hidden"][:rows],
            fused["frontier_index"][depth % 2][:rows], fused["pool_tokens"][:rows],
            fused["pool_scores"][:rows], fused["pool_depths"][:rows],
            fused["pool_prev"][:rows], fused["pool_next"][:rows], fused["pool_side"][:rows],
            fused["work"][:rows], fused["sort"][:rows], fused["positions"][:rows],
            fused["slot_starts"][:rows], fused["lane_mask"][:rows], _count(width),
            depth, _count(cumu_count), _count(verify_num), num_slots,
        )  # fmt: skip

    cumu_count = 1 + k
    verify_num = int(torch.randint(1, 65, (1,), generator=gen, device=_DEVICE))
    for depth in range(1, steps):
        width = int(torch.randint(1, k + 1, (1,), generator=gen, device=_DEVICE))
        # The lane forward's outputs: K children per lane, the first width expanded.
        child_p = ties((rows * k, k)).view(rows, k, k)
        child_tokens = ints((rows * k, k)).view(rows, k, k)
        child_hidden = torch.randn(
            (rows * k, hidden_size), generator=gen, device=_DEVICE
        ).to(torch.bfloat16)
        expanded = [
            root_children if depth == 1 else s["frontier_index"][(depth + 1) % 2][:rows]
            for s in (state, fused)
        ]
        if disabled:
            fused_update(
                child_p,
                child_tokens,
                expanded[1],
                child_hidden.view(rows, k, -1),
                0,
                depth,
                0,
            )
            torch.cuda.synchronize()
            for name, expected in state.items():
                _assert_bitwise_equal(fused[name], expected, name)
            return
        _unfused_depth(
            state, masks, child_p[:, :width], child_tokens[:, :width], expanded[0],
            child_hidden.view(rows, k, -1), depth, cumu_count, verify_num, num_slots,
        )  # fmt: skip
        fused_update(
            child_p, child_tokens, expanded[1], child_hidden.view(rows, k, -1), width,
            depth, cumu_count,
        )  # fmt: skip
        cumu_count += width * k
        for name, expected in state.items():
            _assert_bitwise_equal(fused[name], expected, f"{name} at depth {depth}")


def test_disabled_chain_depth_preserves_pool_and_frontier():
    test_draft_depth_update_matches_the_unfused_sequence(3, 5, 1, 7, disabled=True)


@pytest.mark.parametrize("verify_num", [1, 16])
def test_write_verify_tree(verify_num: int) -> None:
    """Ranked nodes' tokens and parent slots, the rest the root with parent -1,
    in each request's row of the next round's maps."""
    bs, nodes, slots = 3, 64, 16
    generator = torch.Generator().manual_seed(verify_num)
    prev = torch.full((bs, nodes), -1, dtype=torch.int64)
    for node in range(1, nodes):
        prev[:, node] = torch.randint(0, node, (bs,), generator=generator)
    tokens = torch.randint(0, 1000, (bs, nodes), generator=generator)
    # An ancestor-first ranking: each node's parent is ranked before it.
    # A padded row past the live ones is never written.
    ranked = torch.zeros((bs + 1, 16), dtype=torch.int64)
    for b in range(bs):
        chosen = [0]
        while len(chosen) < 16:
            node = int(torch.randint(1, nodes, (1,), generator=generator))
            if node not in chosen and int(prev[b, node]) in chosen:
                chosen.append(node)
        ranked[b] = torch.tensor(chosen)
    root = torch.tensor([7, 8, 9, 6], dtype=torch.int32)
    rows = torch.tensor([5, 2, 9, 11], dtype=torch.int64)
    prev, tokens = (torch.cat([t, t[:1]]) for t in (prev, tokens))
    input_map = torch.zeros((12, slots), dtype=torch.int32, device=_DEVICE)
    parent_map = torch.zeros((12, slots), dtype=torch.int32, device=_DEVICE)
    eagle_harness_write_verify_tree(
        ranked.to(_DEVICE), tokens.to(_DEVICE), prev.to(_DEVICE), root.to(_DEVICE),
        rows.to(_DEVICE), input_map, parent_map, _count(bs), _count(verify_num),
    )  # fmt: skip
    assert (input_map[11] == 0).all() and (parent_map[11] == 0).all()

    for b in range(bs):
        want_tokens = [int(root[b])] * slots
        want_parents = [-1] * slots
        for i in range(verify_num):
            node = int(ranked[b, i])
            want_tokens[i] = int(tokens[b, node])
            parent = int(prev[b, node])
            want_parents[i] = ranked[b, :i].tolist().index(parent) if i else -1
        assert input_map[rows[b]].tolist() == want_tokens
        assert parent_map[rows[b]].tolist() == want_parents


if __name__ == "__main__":
    raise SystemExit(pytest.main([__file__, *sys.argv[1:]]))