[Spec][Ngram] 1/N: Reference based Speculative Decoding refactor by kpham-sgl · Pull Request #20393 · sgl-project/sglang

kpham-sgl · 2026-03-12T00:30:48Z

Motivation

1/N: Refactor the monolithic C++ Ngram class into a template-based architecture to enable pluggable cache backends (e.g., Suffix Automaton in 2+/N), no behavioural changes (except [NEW] tag).

Modifications

Extract Result, Node, fillResult() into result.h/.cpp (shared across backends)
Extract TrieNode + Trie into trie.h/.cpp (trie data structure + tree building: insert, buildRecency, buildFrequency, squeeze, reset)
Convert Ngram into class Ngram — thin concurrency wrapper that holds both SAM (in later PRs) - for corpus and prefix and running Trie - for decoded tokens
Add comprehensive test suite (test_ngram_corpus.py): golden-output tests for BFS/PROB modes, reset, squeeze/eviction, batch consistency, mask invariants, frequency boosting, recency ordering, etc.
[NEW] Wire match_type parameter through ngram_worker.py
[NEW] Update docs for the above parameter

Future plans

#21052

Accuracy Tests

Pass

python -m pytest test/registered/spec/utils/test_ngram_cache.py -v
python -m pytest test/registered/spec/test_ngram_speculative_decoding.py::TestNgramSpeculativeDecodingTriton -xvs

Benchmarking and Profiling

Checklist

Format your code according to the Format code with pre-commit.
Add unit tests according to the Run and add unit tests.
Update documentation according to Write documentations.
Provide accuracy and speed benchmark results according to Test the accuracy and Benchmark the speed.
Follow the SGLang code style guidance.

Review Process

Ping Merge Oncalls to start the PR flow. See the PR Merge Process.
Get approvals from CODEOWNERS and other reviewers.
Trigger CI tests with comments or contact authorized users to do so.
- /tag-run-ci-label, /rerun-failed-ci, /tag-and-rerun-ci
After green CI and required approvals, ask Merge Oncalls to merge.

gemini-code-assist · 2026-03-12T00:30:51Z

Warning

You have reached your daily quota limit. Please wait up to 24 hours and I will start processing your requests again!

kpham-sgl · 2026-03-13T19:09:45Z

/tag-and-rerun-ci

kpham-sgl · 2026-03-13T19:15:53Z

 | `--speculative-ngram-min-bfs-breadth` | The minimum breadth for BFS (Breadth-First Search) in ngram speculative decoding. | `1` | Type: int |
 | `--speculative-ngram-max-bfs-breadth` | The maximum breadth for BFS (Breadth-First Search) in ngram speculative decoding. | `10` | Type: int |
-| `--speculative-ngram-match-type` | The match type for cache tree. | `BFS` | `BFS`, `PROB` |
+| `--speculative-ngram-match-type` | Ngram tree-building mode. `BFS` selects recency-based expansion and `PROB` selects frequency-based expansion. This setting is forwarded to the ngram cache implementation. | `BFS` | `BFS`, `PROB` |


Open to put these doc change in a separate PR

hnyls2002 · 2026-03-20T06:37:55Z

@kpham-sgl This PR generally looks good, only does some migration and cleanup. For the next PRs:

rename branch_length -> max_trie_depth
Remove max_match_window_size and min_match_window_size. We will match as much as possible in the trie.
Do not do O(max_depth ^ 2) matching, maintain a list of matching status, then update the matching status by O(1) for each anchor
There is a racing condition: when the queue is empty, the insertion may not be done. Please solve that.
Current spin-wait is wrong, which still consumes CPU resources. Use conditional variables for that to avoid busy waiting.

- Rename module/extension (ngram_corpus_cpp), sources, and TrieCache→Trie - Update ngram_worker and registered tests Made-with: Cursor

Align pybind name and Python attribute with actual semantics: Ngram is a concurrency wrapper, not a trie.

hnyls2002 · 2026-03-22T07:23:43Z

/rerun-ut test_ngram_corpus.py

hnyls2002 · 2026-03-22T07:23:57Z

/rerun-ut test_ngram_speculative_decoding.py

github-actions · 2026-03-22T07:46:38Z

❌ No test file found matching test_ngram_corpus.py under test/registered/.

github-actions · 2026-03-22T07:46:42Z

✅ Triggered /rerun-ut on 1-gpu-h100 runner:

cd test/ && python3 registered/spec/test_ngram_speculative_decoding.py

github-actions · 2026-03-22T07:46:48Z

🔗 View workflow run

…-project#20393)

kpham-sgl changed the title ~~[WIP][Spec] 1/N: kp/ref based spec dec refactor~~ [WIP][Spec] 1/N: Reference based Speculative Decoding refactor Mar 12, 2026

kpham-sgl force-pushed the kp/ref-based-spec-dec-refactor branch from edc131f to e35bd8b Compare March 12, 2026 01:15

hnyls2002 assigned hnyls2002 and kpham-sgl Mar 13, 2026

proper refactoring

4ef7157

kpham-sgl force-pushed the kp/ref-based-spec-dec-refactor branch from 209d17d to 4ef7157 Compare March 13, 2026 18:38

kpham-sgl added 2 commits March 13, 2026 18:41

lint

0657507

wire match_type to NgramCache

fcd06fa

kpham-sgl changed the title ~~[WIP][Spec] 1/N: Reference based Speculative Decoding refactor~~ [Spec] 1/N: Reference based Speculative Decoding refactor Mar 13, 2026

kpham-sgl added 2 commits March 13, 2026 19:06

Docs for match_type

8c59f16

change binding name

9482d3f

github-actions Bot added documentation Improvements or additions to documentation speculative-decoding npu labels Mar 13, 2026

kpham-sgl marked this pull request as ready for review March 13, 2026 19:09

kpham-sgl requested review from Ying1123, hnyls2002 and merrymercy as code owners March 13, 2026 19:09

github-actions Bot added the run-ci label Mar 13, 2026

kpham-sgl commented Mar 13, 2026

View reviewed changes

hnyls2002 requested changes Mar 20, 2026

View reviewed changes

Comment thread python/sglang/srt/speculative/cpp_ngram/ngram.cpp Outdated

Comment thread test/registered/spec/utils/test_ngram_cache.py Outdated

kpham-sgl mentioned this pull request Mar 20, 2026

[Roadmap] Further Ngram Speculative Decoding Support #21052

Open

19 tasks

kpham-sgl added 2 commits March 20, 2026 21:01

rename

ea6362d

remove template

425b1d5

kpham-sgl requested a review from hnyls2002 March 20, 2026 21:13

kpham-sgl changed the title ~~[Spec] 1/N: Reference based Speculative Decoding refactor~~ [Spec][Ngram] 1/N: Reference based Speculative Decoding refactor Mar 20, 2026

refactor(cpp_ngram): rename ngram_cache→ngram_corpus, trie_cache→trie

ababee0

- Rename module/extension (ngram_corpus_cpp), sources, and TrieCache→Trie - Update ngram_worker and registered tests Made-with: Cursor

hnyls2002 added the high priority label Mar 22, 2026

refactor(cpp_ngram): rename NgramTrie→Ngram, self.trie→self._ngram

7e8fd63

Align pybind name and Python attribute with actual semantics: Ngram is a concurrency wrapper, not a trie.

hnyls2002 approved these changes Mar 22, 2026

View reviewed changes

Merge branch 'main' into kp/ref-based-spec-dec-refactor

90d6ba1

Merge branch 'main' into kp/ref-based-spec-dec-refactor

25b3de5

sgl-project deleted a comment from github-actions Bot Mar 22, 2026

Merge branch 'main' into kp/ref-based-spec-dec-refactor

6c81415

sgl-project deleted a comment from github-actions Bot Mar 22, 2026

hnyls2002 merged commit 6d160b4 into sgl-project:main Mar 22, 2026
36 of 76 checks passed

OrangeRedeng pushed a commit to OrangeRedeng/sglang that referenced this pull request Mar 22, 2026

[Spec][Ngram] 1/N: Reference based Speculative Decoding refactor (sgl…

6cb392b

…-project#20393)

0-693 pushed a commit to 0-693/sglang that referenced this pull request Mar 25, 2026

[Spec][Ngram] 1/N: Reference based Speculative Decoding refactor (sgl…

663a0df

…-project#20393)

dutsc pushed a commit to dutsc/sglang that referenced this pull request Mar 30, 2026

[Spec][Ngram] 1/N: Reference based Speculative Decoding refactor (sgl…

d150fe2

…-project#20393)

JustinTong0323 pushed a commit to JustinTong0323/sglang that referenced this pull request Apr 7, 2026

[Spec][Ngram] 1/N: Reference based Speculative Decoding refactor (sgl…

1f4123f

…-project#20393)

yhyang201 pushed a commit to yhyang201/sglang that referenced this pull request Apr 22, 2026

[Spec][Ngram] 1/N: Reference based Speculative Decoding refactor (sgl…

4fd2af0

…-project#20393)

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[Spec][Ngram] 1/N: Reference based Speculative Decoding refactor#20393

[Spec][Ngram] 1/N: Reference based Speculative Decoding refactor#20393
hnyls2002 merged 12 commits intosgl-project:mainfrom
kpham-sgl:kp/ref-based-spec-dec-refactor

kpham-sgl commented Mar 12, 2026 •

edited

Loading

Uh oh!

gemini-code-assist Bot commented Mar 12, 2026

Uh oh!

kpham-sgl commented Mar 13, 2026

Uh oh!

kpham-sgl Mar 13, 2026

Uh oh!

Uh oh!

Uh oh!

hnyls2002 commented Mar 20, 2026

Uh oh!

hnyls2002 commented Mar 22, 2026 •

edited

Loading

Uh oh!

hnyls2002 commented Mar 22, 2026 •

edited

Loading

Uh oh!

github-actions Bot commented Mar 22, 2026

Uh oh!

github-actions Bot commented Mar 22, 2026

Uh oh!

github-actions Bot commented Mar 22, 2026

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Conversation

kpham-sgl commented Mar 12, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Motivation

Modifications

Future plans

Accuracy Tests

Benchmarking and Profiling

Checklist

Review Process

Uh oh!

gemini-code-assist Bot commented Mar 12, 2026

Uh oh!

kpham-sgl commented Mar 13, 2026

Uh oh!

kpham-sgl Mar 13, 2026

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

hnyls2002 commented Mar 20, 2026

Uh oh!

hnyls2002 commented Mar 22, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

hnyls2002 commented Mar 22, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

github-actions Bot commented Mar 22, 2026

Uh oh!

github-actions Bot commented Mar 22, 2026

Uh oh!

github-actions Bot commented Mar 22, 2026

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

kpham-sgl commented Mar 12, 2026 •

edited

Loading

hnyls2002 commented Mar 22, 2026 •

edited

Loading

hnyls2002 commented Mar 22, 2026 •

edited

Loading