java-topology/whitepaper/outreach/llamacpp-0001.md

llama.cpp — CWE-407 Disclosure Brief (llamacpp-0001)

2026-04-13 · Patch available — awaiting upstream merge

Finding

One O(S²) defect in llama.cpp's grammar-constrained sampling. The llama_grammar_advance_stack() and llama_grammar_accept_token() functions use std::find on a vector<vector<ptr>> for stack deduplication, producing O(S²) per accepted token where S = grammar stack count.

The Defects

llamacpp-0001 (PATCHED — HIGH): src/llama-grammar.cpp (two sites)

// Site 1 — llama_grammar_advance_stack:
if (std::find(new_stacks.begin(), new_stacks.end(), curr_stack) == new_stacks.end()) {
    new_stacks.emplace_back(std::move(curr_stack));
}

// Site 2 — llama_grammar_accept_token:
if (std::find(stacks_new.begin(), stacks_new.end(), surviving_stack) == stacks_new.end()) {
    stacks_new.emplace_back(surviving_stack);
}

new_stacks and stacks_new are vector<vector<const llama_grammar_element*>>. std::find compares each stack element-by-element (O(D) per comparison where D = stack depth), then scans S stacks, giving O(SD) per check. Called S times per token, total: O(S²D).

Complexity Proof

At S=100 grammar stacks, D=10 average depth:

• Defective: 100 × 50 (avg) × 10 = 50,000 pointer comparisons per token
• Fixed: 100 × log₂(100) × 10 = ~6,644 comparisons (set with lexicographic ordering)
• ~8× op reduction at S=100. ~64× at S=200.

Impact

llama.cpp is the most widely deployed local LLM inference engine. Grammar-constrained sampling fires on every token when --grammar or JSON schema mode is active in llama-server. Complex grammars (JSON schema, code generation, structured output) produce dozens to hundreds of parallel stacks. The quadratic dedup compounds across thousands of generated tokens.

The Fix

Pass a companion std::set<llama_grammar_stack> alongside the stacks vector. The set uses pointer-based lexicographic ordering (same semantics as existing comparison) for O(log S) insert/lookup:

// After
std::set<llama_grammar_stack> stacks_new_set;
// ... in loop:
if (stacks_new_set.insert(curr_stack).second) {
    stacks_new.emplace_back(std::move(curr_stack));
}

Patch

Fix available: defects/llamacpp-0001/patch/llamacpp-0001-grammar-stacks-new-dedup-quadratic.patch

Single-file patch in src/llama-grammar.cpp. Adds 4-argument overload of advance_stack with shared set, plus set companion in accept_token. ~16× speedup at S=100, ~64× at S=200.

What We Ask

A patch is ready for review.

1. Confirm receipt and assign a GitHub issue reference (ggerganov/llama.cpp).
2. Assess severity — fires on every sampled token in grammar-constrained mode.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the llama.cpp team in the public disclosure. Preferred acknowledgment format welcome.

Contact: see cover email. This brief is confidential until coordinated disclosure.