Commit 08a9b3589 for llama.cpp

commit 08a9b358939e8c99f9e3299bb2584ffd7b285f52
Author: Marcus Tillmanns <maddimax@gmail.com>
Date:   Tue Nov 17 15:37:25 2026 +0100

    llama : keep the k-pool layout prefix on sequence edits (#32137)

    * llama : keep the k-pool layout prefix on sequence edits

    Assisted-by: Claude Code

    * llama : address review of the k-pool layout update

    * Append and edit share one branch, using stale > sq.pos_min.
    * LLAMA_KPOOL_VERIFY=1 checks every update against a full rebuild. The scan moved into kpool_scan() so the check can reuse it.
    * The test turns the check on for its rollback context, skips -sm tensor, and drops kimi-k31.
    * Two comments that were no longer true are fixed.

    Assisted-by: Claude Code

    * llama : check the k-pool layout update in debug builds instead of LLAMA_KPOOL_VERIFY

    * llama : remove the k-pool layout verification

    * llama : inline the k-pool scan again

    * remove dangling new line

    * do not search twice

    ---------

    Co-authored-by: Aman Gupta <amangupta052@gmail.com>
    Co-authored-by: Alexey Kopytko <alexey@kopytko.com>

diff --git a/src/llama-memory-hybrid-idx.cpp b/src/llama-memory-hybrid-idx.cpp
index da1747649..2e19576f1 100644
--- a/src/llama-memory-hybrid-idx.cpp
+++ b/src/llama-memory-hybrid-idx.cpp
@@ -412,16 +412,28 @@ const llama_memory_hybrid_idx::kpool_layout & llama_memory_hybrid_idx::kpool_lay

         sq.strm = unified ? 0 : mem_idx->get_stream(s);

-        if (mem_idx_stale[s] == POS_CLEAN && !sq.cells.empty() && !sp.empty() &&
-                sq.pos_min == sp.begin()->first) {
-            for (auto it = sp.upper_bound(sq.cells.back()); it != sp.end(); ++it) {
+        // an append (POS_CLEAN) or an edit after pos_min keeps every cell and pool before the stale position
+        // speculative decoding edits the end of the sequence on each rejected draft, a full rebuild there costs O(n_ctx) per step
+        const llama_pos stale = mem_idx_stale[s];
+        bool keep = !sq.cells.empty() && !sp.empty() && sq.pos_min == sp.begin()->first && stale > sq.pos_min;
+        if (keep) {
+            if (stale != POS_CLEAN) {
+                const auto cut = std::lower_bound(sq.cells.begin(), sq.cells.end(), std::make_pair(stale, uint32_t(0)));
+                sq.cells.erase(cut, sq.cells.end());
+                while (!sq.pools.empty() && sq.pools.back() + kpool > sq.cells.size()) {
+                    sq.pools.pop_back();
+                }
+                sq.j_next = sq.pools.empty() ? 0 : sq.pools.back() + kpool;
+            }
+            auto it = stale == POS_CLEAN ? sp.upper_bound(sq.cells.back()) : sp.lower_bound(std::make_pair(stale, uint32_t(0)));
+            for (; it != sp.end(); ++it) {
                 sq.cells.push_back(*it);
             }
+            keep = sq.cells.size() == sp.size();
         }

-        // the appended tail accounts for every cell only if nothing before it was dropped, but an edit can
-        // regroup a sequence without changing its cell count, so a stale sequence must rebuild regardless
-        if (sq.cells.size() != sp.size() || mem_idx_stale[s] != POS_CLEAN) {
+        // a new sequence, an edit at or before pos_min, or cells that do not match: group the whole sequence again
+        if (!keep) {
             sq.cells.assign(sp.begin(), sp.end());
             sq.pools.clear();
             sq.j_next  = 0;
diff --git a/src/llama-memory-hybrid-idx.h b/src/llama-memory-hybrid-idx.h
index 59940dbb8..85a2a91ec 100644
--- a/src/llama-memory-hybrid-idx.h
+++ b/src/llama-memory-hybrid-idx.h
@@ -86,7 +86,8 @@ public:

     // Which cells of a sequence make up which pool of kpool consecutive positions (or cells, in order mode).
     // It is kept here because it outlives the batch: pools are fixed by the positions relative to the
-    // sequence's first one, so a ubatch only ever appends to it. Sequence edits drop it, see mem_idx_stale.
+    // sequence's first one, so a ubatch only ever appends to it. A sequence edit drops it from the stale
+    // position on, or all of it for an edit at or before the first position, see mem_idx_stale.
     struct kpool_layout;

     const kpool_layout & kpool_layout_update();
diff --git a/tests/test-llama-archs.cpp b/tests/test-llama-archs.cpp
index 147d5b536..8b3d4bb86 100644
--- a/tests/test-llama-archs.cpp
+++ b/tests/test-llama-archs.cpp
@@ -1019,6 +1019,58 @@ static bool check_causal_attn_toggle(
     return ok;
 }

+// speculative decoding: each step decodes a token and 0 to n_draft_max drafts, then rejects the drafts
+// the logits of the token must match a decode without drafts
+static double check_draft_rollback(llama_model * model, const std::vector<llama_token> & tokens, const std::vector<float> & logits_ref) {
+    const uint32_t n_vocab     = llama_vocab_n_tokens(llama_model_get_vocab(model));
+    const uint32_t n_tokens    = tokens.size();
+    const uint32_t n_draft_max = 2;
+
+    llama_context_params ctx_params = llama_context_default_params();
+    ctx_params.n_ctx           = 0;
+    ctx_params.n_threads       = 4;
+    ctx_params.n_threads_batch = 4;
+    ctx_params.n_ubatch        = 64;
+    ctx_params.n_rs_seq        = n_draft_max;
+
+    llama_context_ptr lctx(llama_init_from_model(model, ctx_params));
+    if (!lctx) {
+        throw std::runtime_error("failed to create llama context");
+    }
+
+    common_batch batch(lctx.get());
+    for (uint32_t pos = 0; pos < n_tokens/2; pos++) {
+        batch.add(tokens[pos], pos, 0, false);
+    }
+    if (llama_process(lctx.get(), LLAMA_PROCESS_TYPE_DECODE, batch.get())) {
+        throw std::runtime_error("failed to decode batch");
+    }
+
+    std::vector<float> logits;
+    std::vector<float> ref;
+    for (uint32_t pos = n_tokens/2; pos < n_tokens; pos++) {
+        batch.clear();
+        batch.add(tokens[pos], pos, 0, true);
+        const uint32_t n_draft = pos % (n_draft_max + 1);
+        for (uint32_t i = 1; i <= n_draft; i++) {
+            batch.add((tokens[pos] + i) % n_vocab, pos + i, 0, true);
+        }
+        if (llama_process(lctx.get(), LLAMA_PROCESS_TYPE_DECODE, batch.get())) {
+            throw std::runtime_error("failed to decode batch");
+        }
+
+        const float * logits_ith = llama_get_logits_ith(lctx.get(), 0);
+        logits.insert(logits.end(), logits_ith, logits_ith + n_vocab);
+        ref.insert(ref.end(), logits_ref.begin() + (size_t) pos*n_vocab, logits_ref.begin() + (size_t) (pos + 1)*n_vocab);
+
+        if (!llama_memory_seq_rm(llama_get_memory(lctx.get()), 0, pos + 1, -1)) {
+            throw std::runtime_error("failed to reject the drafts");
+        }
+    }
+
+    return nmse(ref, logits);
+}
+
 static bool moe_mandatory(const llm_arch arch) {
     switch (arch) {
         case LLM_ARCH_FLINT:
@@ -1446,6 +1498,18 @@ static int test_backends(const std::string & arch_filter, const size_t seed, con
                             }
                             test_ok = false;
                         }
+
+                        // the k-pool layout is updated in place when drafts are rejected
+                        // TODO: the meta backend aborts with n_rs_seq > 0 (view of permuted tensor not implemented)
+                        if ((arch == LLM_ARCH_QWEN4EXP || arch == LLM_ARCH_GLM5_NEXT) && dc.split_mode != LLAMA_SPLIT_MODE_TENSOR) {
+                            const double nmse_rollback = check_draft_rollback(model_and_ctx_dev.first.get(), tokens, logits_dev);
+                            if (!(nmse_rollback <= 1e-4)) {
+                                if (test_ok) {
+                                    status_nmse = "\033[1;31mFAIL\033[0m (rollback)";
+                                }
+                                test_ok = false;
+                            }
+                        }
                     }

                     if (llama_arch_supports_save(arch) && dc.split_mode != LLAMA_SPLIT_MODE_TENSOR) {