{"record":{"id":"357e475e91d6a100","repo":"sgl-project/sglang","slug":"batchmatch-received-an-empty-token-tail","errorCode":null,"errorMessage":"batchMatch received an empty token tail","messagePattern":"batchMatch received an empty token tail","errorType":"exception","errorClass":"std::runtime_error","httpStatus":null,"severity":"error","filePath":"python/sglang/kernels/jit/csrc/ngram_corpus/ngram.cpp","lineNumber":181,"sourceCode":"    trie_result_build_fn = &Trie::buildFrequency;\n    sam_result_build_fn = &SuffixAutomaton::buildFrequency;\n  } else {\n    throw std::runtime_error(\"Unknown match_type: '\" + param_.match_type + \"'. Must be 'BFS' or 'PROB'.\");\n  }\n\n  // All budget values are loop-invariant (mutex_ held, sams_ won't change).\n  const size_t num_sams = sams_.size();\n  const auto total_draft_token_num = param_.get_draft_token_num(tokens.size());\n  const size_t total_sam_budget =\n      num_sams > 0 ? std::min(param_.external_sam_budget, total_draft_token_num) : size_t{0};\n  const size_t per_sam_budget = num_sams > 0 ? total_sam_budget / num_sams : size_t{0};\n  const size_t trie_budget = total_draft_token_num - (per_sam_budget * num_sams);\n\n  Result merged;\n  for (size_t i = 0; i < state_ids.size(); ++i) {\n    const auto& suffix = tokens[i];\n    if (suffix.empty()) {\n      throw std::runtime_error(\"batchMatch received an empty token tail\");\n    }\n\n    auto& state = match_state_[state_ids[i]];\n\n    if (total_sam_budget == 0 || per_sam_budget == 0) {\n      auto res = (trie_.get()->*trie_result_build_fn)(\n          suffix.data(), suffix.size(), suffix.back(), total_draft_token_num, param_, state, total_lens[i]);\n      merged.token.insert(merged.token.end(), res.token.begin(), res.token.end());\n      merged.mask.insert(merged.mask.end(), res.mask.begin(), res.mask.end());\n      continue;\n    }\n\n    auto combined = (trie_.get()->*trie_result_build_fn)(\n        suffix.data(), suffix.size(), suffix.back(), trie_budget, param_, state, total_lens[i]);\n\n    for (const auto& [_, sam] : sams_) {\n      auto sam_res =\n          (sam.get()->*sam_result_build_fn)(suffix.data(), suffix.size(), suffix.back(), per_sam_budget, param_);","sourceCodeStart":163,"sourceCodeEnd":199,"githubUrl":"https://github.com/sgl-project/sglang/blob/0132848349585cfe6aae51c4941cbae872505f8a/python/sglang/kernels/jit/csrc/ngram_corpus/ngram.cpp#L163-L199","documentation":"Each request in the batch must carry a non-empty token tail (the prompt/context suffix used for n-gram matching). An empty tail has no matches possible, so batchMatch rejects it rather than returning garbage.","triggerScenarios":"batchMatch where tokens[i] is an empty vector — e.g. a request whose context tail was truncated to zero, or a newly initialized request with no history.","commonSituations":"First decode step of a request with empty prompt; slicing the context with an off-by-one that yields an empty window; scheduler sending a placeholder request with no tokens yet.","solutions":["Skip/defer requests whose token tail is empty instead of passing them to batchMatch","Fix the tail-construction logic (min length 1, check slice bounds)","Pad or wait until at least one context token exists before matching"],"exampleFix":"// before\nfor (auto& t : tokens) /* ... */ ngram.batchMatch(ids, tokens, lens); // some t empty\n// after\nstd::vector<int64_t> ids2; std::vector<std::vector<int32_t>> toks2; std::vector<size_t> lens2;\nfor (size_t i = 0; i < ids.size(); ++i) if (!tokens[i].empty()) { ids2.push_back(ids[i]); toks2.push_back(tokens[i]); lens2.push_back(lens[i]); }\nauto res = ngram.batchMatch(ids2, toks2, lens2);","handlingStrategy":"validation","validationCode":"for (auto& t : tokens) if (t.empty()) { /* drop or defer that request */ }","typeGuard":"bool tails_nonempty(const std::vector<std::vector<int32_t>>& toks) { for (auto& t : toks) if (t.empty()) return false; return true; }","tryCatchPattern":null,"preventionTips":["Never enqueue requests with zero context tokens for matching","Check slice bounds when cutting the context tail"],"tags":["ngram","empty-input","batch-validation"],"backgroundTag":"empty-input-validation","analyzedSha":"0132848349585cfe6aae51c4941cbae872505f8a","analyzedAt":"2026-08-28T05:10:05.995Z","schemaVersion":2},"datasetVersion":"2026-08-28T06:17:29.519Z"}