# PLE n-gram hash ids (`ple_ngram_ids`) | ServingStudio Kernel Library

Hash each token's preceding n-grams into per-head embedding-table ids.

For every scheduled token, the kernel finds its request, walks back ngram_context_len predecessor tokens (from this step or the request's saved context, stopping at an end-of-sequence token) and, for each n-gram order and hash head, mixes the tokens with per-position multipliers by XOR and maps the hash into that head's table range.

Category: Other. Interactive page: https://servingstudio.cs.washington.edu/kernels.html?kind=ple_ngram_ids. All kernel kinds: https://servingstudio.cs.washington.edu/kernels.md.

## Formula

- `id[t, h] = offset[h] + (XORᵢ<n(h) token[t − i]·mult[i]) mod size[h]`
- `bytes = num_tokens · (4 + 8 · ngram_context_len · heads_per_ngram) + small context reads`

## How it is measured

GPU kernel time from CUPTI activity records, averaged over repeated launches in one capture. The L2 cache is flushed before each launch, so the numbers are cold-cache times. Only _ple_ngram_ids_kernel is counted. Tokens are split into num_reqs near-equal requests; ids are checked bit for bit against the fork's own eager PyTorch path (compute_ngram_ids on CPU tensors).

## Caveats

- TFLOPS is not computed.

## Arguments

| Argument | Type | Unit | Meaning |
| --- | --- | --- | --- |
| `num_tokens` | number | tokens | Scheduled tokens. |
| `num_reqs` | number | requests | Requests the tokens belong to. |
| `ngram_context_len` | number | tokens | Predecessor tokens per request (ngram_size − 1). |
| `heads_per_ngram` | number | heads | Hash heads per n-gram order. |

## Metrics

- Time (`time_ms`, ms)
- Throughput (`tflops`, TFLOPS)
- Memory bandwidth (`memory_bandwidth_gbps`, GB/s)
- Energy (`energy_j`, J)

## Backends

- `vllm_triton`: The fork's ple_ngram_ids (_ple_ngram_ids_kernel). any CUDA GPU.

## Measured rows

40 rows in all.

| GPU | Backend | Precision | Rows |
| --- | --- | --- | --- |
| NVIDIA B200 | `vllm_triton` |  | 40 |

## Used by these deployments

- [Qwen3.8 Flash Next NVFP4: vLLM, one GPU, MTP speculative decoding](https://servingstudio.cs.washington.edu/models/Qwen3.8-Flash-Next-NVFP4/qwen4_exp_vllm_nvfp4_gdn_qsa_moe_speculative.md) (`Qwen3.8-Flash-Next-NVFP4/qwen4_exp_vllm_nvfp4_gdn_qsa_moe_speculative`)

## API

- This kind: https://servingstudio.cs.washington.edu/api/public/v1/kernels/ple_ngram_ids
- Measured rows: https://servingstudio.cs.washington.edu/api/public/v1/kernels/ple_ngram_ids/rows (filter by any column, such as `?gpu=NVIDIA%20H200`; `format=csv` for CSV)
- Configs the public deployments ask of it: https://servingstudio.cs.washington.edu/api/public/v1/kernels/ple_ngram_ids/configs

## Torch reference

What the kind computes, as Torch code (`profiling/runners/ple/ple_ngram_ids.py` in ServingStudio Sim):

```python
"""Profile the PLE n-gram hash ids (``ple_ngram_ids``).

``vllm_triton`` times the fork's ``ple_ngram_ids`` on ``num_tokens`` random
token ids split into ``num_reqs`` near-equal requests, with random per-request
``ngram_context``. Token ids and the context are int32 on the device, as
production passes them (``input_batch.input_ids`` and ``model_state.ngram_context``),
so Triton specializes the same kernel. Multipliers, head sizes and offsets come from the fork's own
``Qwen4ExpNGramEmbedding`` helpers for a 248,320-token vocabulary and
20M-row heads (the values only change hash results, not the work).

The reference is the fork's eager path: ``compute_ngram_ids`` takes it when the
inputs are CPU tensors. Ids must match bit for bit.
"""

from __future__ import annotations

from types import SimpleNamespace

from profiling.profilers.energy import Energy
from profiling.profilers.timer import Timer
from profiling.runners.exceptions import KernelLaunchFailed, OOMError, ProfilerNotImplemented
from profiling.runners.metrics import ComputeMetrics

KIND = "ple_ngram_ids"
_KERNEL_NAME = "_ple_ngram_ids_kernel"
_VOCAB = 248_320
_EOS = 248_044
_HEAD_ROWS = 20_000_000


def validate_args(
    num_tokens: int, num_reqs: int, ngram_context_len: int, heads_per_ngram: int
) -> None:
    # The kernel has no size limits of its own: tokens tile the grid, and the
    # context length and head count are constexprs it unrolls over.
    for name, value in (
        ("num_tokens", num_tokens),
        ("ngram_context_len", ngram_context_len),
        ("heads_per_ngram", heads_per_ngram),
    ):
        if type(value) is not int or value < 1:
            raise ValueError(f"{name} must be a positive integer")
    if type(num_reqs) is not int or not 1 <= num_reqs <= num_tokens:
        raise ValueError("num_reqs must be an integer in [1, num_tokens]")


def logical_bytes(num_tokens: int, ngram_context_len: int, heads_per_ngram: int) -> int:
    """int32 token ids read, int64 ids written (the small context reads are left out)."""
    return num_tokens * (4 + 8 * ngram_context_len * heads_per_ngram)


def query_start_loc(num_tokens: int, num_reqs: int) -> list[int]:
    """Near-equal request boundaries."""
    return [num_tokens * r // num_reqs for r in range(num_reqs + 1)]


def profile_ple_ngram_ids_vllm_triton(
    num_tokens: int, num_reqs: int, ngram_context_len: int, heads_per_ngram: int
) -> ComputeMetrics:
    """Time one n-gram id launch."""
    validate_args(num_tokens, num_reqs, ngram_context_len, heads_per_ngram)
    try:
        import torch
        from vllm.models.qwen4_exp.nvidia.ngram_embedding import Qwen4ExpNGramEmbedding as Emb
        from vllm.models.qwen4_exp.nvidia.ops.ple import ple_ngram_ids
    except ImportError as exc:
        raise ProfilerNotImplemented(f"{KIND}:vllm_triton requires the vLLM fork") from exc
    try:
        device = torch.device("cuda", torch.cuda.current_device())
        ngram_size = ngram_context_len + 1
        heads = ngram_context_len * heads_per_ngram
        mult = Emb._make_layer_multipliers(
            ngram_size=ngram_size, unigram_vocab_size=_VOCAB, seed=1234, ple_dense_layer_id=0
        )
        sizes = [_HEAD_ROWS + 2 * h + 1 for h in range(heads)]
        offsets = [sum(sizes[:h]) for h in range(heads)]
        gen = torch.Generator().manual_seed(0x1D5)
        tokens = torch.randint(0, _VOCAB, (num_tokens,), generator=gen)
        tokens[torch.rand(num_tokens, generator=gen) < 0.01] = _EOS
        context = torch.randint(0, _VOCAB, (num_reqs, ngram_context_len), generator=gen)
        qsl = torch.tensor(query_start_loc(num_tokens, num_reqs), dtype=torch.int32)
        host = dict(
            layer_multipliers=torch.tensor(mult, dtype=torch.long),
            ngram_heads_vocab_sizes=torch.tensor(sizes, dtype=torch.long),
            ngram_heads_offsets=torch.tensor(offsets, dtype=torch.long),
        )
        module = SimpleNamespace(
            ngram_size=ngram_size,
            heads_per_ngram=heads_per_ngram,
            eos_token_id=_EOS,
            _shift_precompute=Emb._shift_precompute,
            _shift_apply=Emb._shift_apply,
            **host,
        )
        ref = Emb.compute_ngram_ids(module, tokens, qsl, context)
        dev = {k: v.to(device) for k, v in host.items()}
        d_tokens = tokens.to(device, torch.int32)
        d_qsl = qsl.to(device)
        d_ctx = context.to(device, torch.int32)
        out = torch.empty(num_tokens, heads, dtype=torch.int64, device=device)

        def launch() -> None:
            ple_ngram_ids(
                d_tokens, d_qsl, d_ctx, dev["layer_multipliers"], dev["ngram_heads_vocab_sizes"],
                dev["ngram_heads_offsets"], _EOS, heads_per_ngram, output=out,
            )

        launch()
        torch.cuda.synchronize()
        mismatches = int((out.cpu() != ref).sum())
        if mismatches:
            raise KernelLaunchFailed(f"{KIND} ids differ from the eager path: {mismatches}")
        time_ms = Timer.cupti(launch, kernel_name=_KERNEL_NAME)
        energy_j = Energy.perf(launch, per_iter_time_ms=time_ms)
    except torch.OutOfMemoryError as exc:
        raise OOMError(f"{KIND}:vllm_triton ran out of memory") from exc
    except (KernelLaunchFailed, ProfilerNotImplemented):
        raise
    except Exception as exc:
        raise KernelLaunchFailed(f"{KIND}:vllm_triton failed: {exc}") from exc
    nbytes = logical_bytes(num_tokens, ngram_context_len, heads_per_ngram)
    return ComputeMetrics(
        time_ms=float(time_ms),
        tflops=0.0,
        memory_bandwidth_gbps=float(nbytes / (time_ms / 1000.0) / 1e9),
        energy_j=float(energy_j),
    )


__all__ = [
    "logical_bytes",
    "profile_ple_ngram_ids_vllm_triton",
    "query_start_loc",
    "validate_args",
]
```

---

This page as Markdown: https://servingstudio.cs.washington.edu/kernels/ple_ngram_ids.md. A guide to the whole site for AI agents: [llms.txt](https://servingstudio.cs.washington.edu/llms.txt).
