Motivation

Part of Ngram series #21052

This PR removes the old fixed trie/SAM draft-budget split. Instead of reserving draft tokens with external_sam_budget, trie and each loaded SAM are treated as candidate sources scored by score = source_prior * (w_specificity * specificity + w_confidence * confidence) where w_specificity and w_confidence are normalized from the user-provided weights. Sources are merged in score order, and the final merged tree is capped only by num_draft_tokens.

This lets multiple external corpora participate in drafting without hard partitioning draft capacity across trie and SAMs.

Followed by #22569 which benchmarks this PR's effect on accept length across some experiments

Modifications

• Add C++ external-corpus SAM support for Ngram, including suffix automaton
  matching, root-result merging, and multi-corpus management.
• Wire the feature through FFI / Python / worker plumbing so external corpora
  can be loaded and used during Ngram speculative decoding.
• Replace static trie/SAM budget allocation with score-ordered source merging.
  Remove external_sam_budget and min_trie_share; keep
  trie_source_prior, match_specificity_weight, and
  match_confidence_weight as source-ranking knobs.
• Update unit/spec coverage for external corpus loading, multi-SAM merge
  behavior, server args, and the output-as-corpus accept-length regression.
• Update design docs to match the non-budgeted merge model.

Accuracy Tests

Passed:

• python3 -m pytest test/registered/unit/spec/test_ngram_corpus.py -k "TestNgramCorpusExternalSam or TestNgramCorpusMultiSam"
• python3 -m pytest test/registered/unit/server_args/test_server_args.py -k "NgramExternalSamArgs"
• python3 -m pytest test/registered/spec/test_ngram_speculative_decoding.py -k "TestNgramSpeculativeDecodingFlashinfer and output_as_corpus_boosts_accept_length"

See #22569 for extra benchmarks on accept length

Speed Tests and Profiling

See #22569 for extra benchmarks on accept length

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 and Merge Process

1. Ping Merge Oncalls to start the process. See the PR Merge Process.
2. Get approvals from CODEOWNERS and other reviewers.
3. Trigger CI tests with comments or contact authorized users to do so.
   • Common commands include /tag-and-rerun-ci, /tag-run-ci-label, /rerun-failed-ci
4. After green CI and required approvals, ask Merge Oncalls or people with Write permission to merge the PR.