This is an automated email from the ASF dual-hosted git repository.

tlopex pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/tvm.git


The following commit(s) were added to refs/heads/main by this push:
     new 31195a7aeb [Runtime][KVCache] Support incremental checkpoint page 
ranges (#21007)
31195a7aeb is described below

commit 31195a7aeb9dc4c915e2c63343a35559f4768dc8
Author: Akaash Parthasarathy <[email protected]>
AuthorDate: Wed Nov 18 13:44:34 2026 -0800

    [Runtime][KVCache] Support incremental checkpoint page ranges (#21007)
    
    Add checkpoint page-range export/import for a specified sequence prefix.
    This lets clients save committed KV state from a cache that has already
    run ahead and restore it incrementally.
---
 src/runtime/vm/kv_state.cc                         |   6 +
 src/runtime/vm/kv_state.h                          |  41 ++++
 src/runtime/vm/paged_kv_cache.cc                   | 209 +++++++++++++++------
 ...runtime_builtin_paged_attention_kv_cache_cpu.py | 149 ++++++++++++++-
 4 files changed, 345 insertions(+), 60 deletions(-)

diff --git a/src/runtime/vm/kv_state.cc b/src/runtime/vm/kv_state.cc
index b1edd48e3c..f9d5015545 100644
--- a/src/runtime/vm/kv_state.cc
+++ b/src/runtime/vm/kv_state.cc
@@ -76,10 +76,16 @@ TVM_FFI_STATIC_INIT_BLOCK() {
                   &AttentionKVCacheObj::GetLayoutHash)
       .def_method("vm.builtin.attention_kv_cache_export_page_group",
                   &AttentionKVCacheObj::ExportPageGroup)
+      .def_method("vm.builtin.attention_kv_cache_get_checkpoint_metadata_at",
+                  &AttentionKVCacheObj::GetCheckpointMetadataAt)
+      .def_method("vm.builtin.attention_kv_cache_export_page_range",
+                  &AttentionKVCacheObj::ExportPageRange)
       .def_method("vm.builtin.attention_kv_cache_prepare_import",
                   &AttentionKVCacheObj::PrepareImport)
       .def_method("vm.builtin.attention_kv_cache_import_page_group",
                   &AttentionKVCacheObj::ImportPageGroup)
+      .def_method("vm.builtin.attention_kv_cache_import_page_range",
+                  &AttentionKVCacheObj::ImportPageRange)
       .def_method("vm.builtin.attention_kv_cache_finish_import", 
&AttentionKVCacheObj::FinishImport)
       .def_method("vm.builtin.attention_kv_cache_get_sequence_length",
                   &AttentionKVCacheObj::GetSequenceLength)
diff --git a/src/runtime/vm/kv_state.h b/src/runtime/vm/kv_state.h
index 06e0840bde..37878db923 100644
--- a/src/runtime/vm/kv_state.h
+++ b/src/runtime/vm/kv_state.h
@@ -157,6 +157,32 @@ class AttentionKVCacheObj : public KVStateObj {
    */
   virtual void ExportPageGroup(int64_t seq_id, int64_t group_id, ffi::Tensor 
dst) = 0;
 
+  /*!
+   * \brief Get checkpoint metadata for the first `seq_length` positions of a
+   * sequence, as GetCheckpointMetadata would report it at that length.
+   * \param seq_id The id of the sequence whose checkpoint metadata is 
requested.
+   * \param seq_length The checkpointed length, at most the sequence length.
+   * \return JSON string describing runtime layout and logical pages.
+   */
+  virtual ffi::String GetCheckpointMetadataAt(int64_t seq_id, int64_t 
seq_length) const = 0;
+
+  /*!
+   * \brief Export logical pages [page_begin, page_end) of one page group, as
+   * they are for the first `seq_length` positions of the sequence. Positions 
at
+   * or after `seq_length` in the last page are written as zeros, so pages 
below
+   * `seq_length` can be exported while later positions are still appended.
+   * \param seq_id The id of the sequence whose pages are exported.
+   * \param group_id The checkpoint group id to export.
+   * \param seq_length The checkpointed length, at most the sequence length.
+   * \param page_begin The first logical page to export.
+   * \param page_end One past the last logical page to export.
+   * \param dst The destination tensor in page group layout.
+   * \param dst_page_offset The page of `dst` that receives `page_begin`.
+   */
+  virtual void ExportPageRange(int64_t seq_id, int64_t group_id, int64_t 
seq_length,
+                               int64_t page_begin, int64_t page_end, 
ffi::Tensor dst,
+                               int64_t dst_page_offset) = 0;
+
   /*!
    * \brief Prepare sequence state and page tables for checkpoint import.
    * \param seq_id The id of the sequence being imported.
@@ -172,6 +198,21 @@ class AttentionKVCacheObj : public KVStateObj {
    */
   virtual void ImportPageGroup(int64_t seq_id, int64_t group_id, ffi::Tensor 
src) = 0;
 
+  /*!
+   * \brief Import logical pages [page_begin, page_end) of one page group into 
a
+   * prepared sequence. Ranges of a group are imported in increasing order and
+   * may overlap the previous range, which they overwrite; a group is complete
+   * once its ranges cover every logical page without a gap.
+   * \param seq_id The id of the sequence being imported.
+   * \param group_id The checkpoint group id to import.
+   * \param page_begin The first logical page to import.
+   * \param page_end One past the last logical page to import.
+   * \param src The source tensor in page group layout.
+   * \param src_page_offset The page of `src` that holds `page_begin`.
+   */
+  virtual void ImportPageRange(int64_t seq_id, int64_t group_id, int64_t 
page_begin,
+                               int64_t page_end, ffi::Tensor src, int64_t 
src_page_offset) = 0;
+
   /*!
    * \brief Finish a checkpoint import after all page groups have been 
restored.
    * \param seq_id The id of the sequence being imported.
diff --git a/src/runtime/vm/paged_kv_cache.cc b/src/runtime/vm/paged_kv_cache.cc
index 72e2b2e1f6..9894713868 100644
--- a/src/runtime/vm/paged_kv_cache.cc
+++ b/src/runtime/vm/paged_kv_cache.cc
@@ -201,8 +201,11 @@ class PagedAttentionKVCacheObj : public 
AttentionKVCacheObj {
   std::unordered_map<int64_t, Sequence> seq_map_;
   /*! \brief Whether a checkpoint import is waiting for all page groups. */
   bool checkpoint_import_in_progress_ = false;
-  /*! \brief The page groups restored by the current checkpoint import. */
-  std::vector<bool> checkpoint_imported_groups_;
+  /*!
+   * \brief Per page group, the logical pages restored by the current 
checkpoint
+   * import from page 0, or -1 if nothing has been imported yet.
+   */
+  std::vector<int64_t> checkpoint_imported_pages_;
 
   /********************* Sequence Block Structures *********************/
 
@@ -624,7 +627,7 @@ class PagedAttentionKVCacheObj : public AttentionKVCacheObj 
{
   void Clear() final {
     seq_map_.clear();
     checkpoint_import_in_progress_ = false;
-    checkpoint_imported_groups_.clear();
+    checkpoint_imported_pages_.clear();
     free_page_ids_.clear();
     for (int64_t page_id = num_total_pages_ - 1; page_id >= 0; --page_id) {
       free_page_ids_.push_back(page_id);
@@ -945,16 +948,24 @@ class PagedAttentionKVCacheObj : public 
AttentionKVCacheObj {
   }
 
   ffi::String GetCheckpointMetadata(int64_t seq_id) const final {
+    CheckCheckpointSequenceSupported(seq_id);
+    return GetCheckpointMetadataAt(seq_id, seq_map_.at(seq_id).seq_length);
+  }
+
+  ffi::String GetCheckpointMetadataAt(int64_t seq_id, int64_t seq_length) 
const final {
     CheckCheckpointSequenceSupported(seq_id);
     const Sequence& seq = seq_map_.at(seq_id);
+    CheckCheckpointLength(seq, seq_length);
+    // Validate the page table even though only the length is reported.
+    GetNumLogicalPages(seq);
 
     namespace json = tvm::ffi::json;
     json::Object metadata = MakeLayoutMetadata();
     metadata.Set("layout_hash", GetLayoutHash());
     metadata.Set("seq_id", seq_id);
-    metadata.Set("seq_length", static_cast<int64_t>(seq.seq_length));
-    metadata.Set("logical_pages", MakeLogicalPageMetadata(seq));
-    metadata.Set("groups", MakePageGroupMetadata(seq));
+    metadata.Set("seq_length", seq_length);
+    metadata.Set("logical_pages", MakeLogicalPageMetadata(seq_length));
+    metadata.Set("groups", 
MakePageGroupMetadata(GetExpectedNumLogicalPages(seq_length)));
     return json::Stringify(metadata);
   }
 
@@ -967,14 +978,23 @@ class PagedAttentionKVCacheObj : public 
AttentionKVCacheObj {
     TVM_FFI_ICHECK(dst.defined());
     CheckCheckpointSequenceSupported(seq_id);
     const Sequence& seq = seq_map_.at(seq_id);
-    TVM_FFI_ICHECK_GE(group_id, 0)
-        << "PagedAttentionKVCache checkpoint export got invalid group id " << 
group_id << ".";
-    TVM_FFI_ICHECK_LT(group_id, num_layers_)
-        << "PagedAttentionKVCache checkpoint export got invalid group id " << 
group_id
-        << ", but only " << num_layers_ << " groups are available.";
-
     int64_t num_logical_pages = GetNumLogicalPages(seq);
     CheckExportPageGroupTensor(dst, num_logical_pages);
+    ExportPageRange(seq_id, group_id, seq.seq_length, 0, num_logical_pages, 
dst, 0);
+  }
+
+  void ExportPageRange(int64_t seq_id, int64_t group_id, int64_t seq_length, 
int64_t page_begin,
+                       int64_t page_end, ffi::Tensor dst, int64_t 
dst_page_offset) final {
+    CheckCheckpointSequenceSupported(seq_id);
+    const Sequence& seq = seq_map_.at(seq_id);
+    CheckCheckpointGroupId(group_id, "export");
+    CheckCheckpointLength(seq, seq_length);
+    CheckCheckpointPageRange(page_begin, page_end, 
GetExpectedNumLogicalPages(seq_length),
+                             "export");
+    CheckPageRangeTensor(dst, dst_page_offset, page_end - page_begin, 
"ExportPageRange");
+    if (page_begin == page_end) {
+      return;
+    }
     std::vector<int32_t> page_ids = GetCheckpointPageIds(seq, "checkpoint 
export");
 
     if (copy_stream_ != nullptr) {
@@ -982,30 +1002,18 @@ class PagedAttentionKVCacheObj : public 
AttentionKVCacheObj {
     }
 
     ffi::Tensor layer_pages = pages_[group_id];
-    int64_t num_full_pages = seq.seq_length / page_size_;
-    int64_t partial_page_length = seq.seq_length % page_size_;
-    if (partial_page_length != 0) {
-      TVM_FFI_ICHECK_LT(num_full_pages, num_logical_pages);
-      ExportPartialCheckpointPage(layer_pages, page_ids[num_full_pages], dst, 
num_full_pages,
-                                  partial_page_length);
-    }
-
-    int64_t logical_page_index = 0;
-    while (logical_page_index < num_full_pages) {
-      int64_t run_length = 1;
-      while (logical_page_index + run_length < num_full_pages &&
-             page_ids[logical_page_index + run_length] ==
-                 page_ids[logical_page_index] + run_length) {
-        ++run_length;
-      }
-      CopyCheckpointPageRun(layer_pages, page_ids[logical_page_index], dst, 
logical_page_index,
-                            run_length);
-      logical_page_index += run_length;
+    int64_t num_full_pages = seq_length / page_size_;
+    int64_t full_page_end = std::min(page_end, num_full_pages);
+    if (page_begin < full_page_end) {
+      CopyCheckpointPages(layer_pages, page_ids, page_begin, full_page_end, 
dst, dst_page_offset,
+                          /*to_page_group=*/true);
     }
-    if (partial_page_length != 0) {
-      ++logical_page_index;
+    if (page_end > num_full_pages) {
+      // Only the last logical page can be partial.
+      ExportPartialCheckpointPage(layer_pages, page_ids[num_full_pages], dst,
+                                  dst_page_offset + num_full_pages - 
page_begin,
+                                  seq_length % page_size_);
     }
-    TVM_FFI_ICHECK_EQ(logical_page_index, num_logical_pages);
   }
 
   void PrepareImport(int64_t seq_id, ffi::String metadata_json) final {
@@ -1027,7 +1035,7 @@ class PagedAttentionKVCacheObj : public 
AttentionKVCacheObj {
     }
     seq_map_.insert({seq_id, Sequence(&global_block_pool_, block_idx)});
     checkpoint_import_in_progress_ = true;
-    checkpoint_imported_groups_.assign(num_layers_, false);
+    checkpoint_imported_pages_.assign(num_layers_, -1);
     dirty_aux_data_device_ = true;
   }
 
@@ -1043,7 +1051,7 @@ class PagedAttentionKVCacheObj : public 
AttentionKVCacheObj {
     TVM_FFI_ICHECK_LT(group_id, num_layers_)
         << "PagedAttentionKVCache checkpoint import got invalid group id " << 
group_id
         << ", but only " << num_layers_ << " groups are available.";
-    TVM_FFI_ICHECK(!checkpoint_imported_groups_[group_id])
+    TVM_FFI_ICHECK_EQ(checkpoint_imported_pages_[group_id], -1)
         << "PagedAttentionKVCache checkpoint group " << group_id << " was 
already imported.";
 
     int64_t num_logical_pages = GetNumLogicalPages(seq);
@@ -1053,22 +1061,37 @@ class PagedAttentionKVCacheObj : public 
AttentionKVCacheObj {
     if (copy_stream_ != nullptr) {
       DeviceAPI::Get(device_)->SyncStreamFromTo(device_, copy_stream_, 
compute_stream_);
     }
+    if (num_logical_pages > 0) {
+      CopyCheckpointPages(pages_[group_id], page_ids, 0, num_logical_pages, 
src, 0,
+                          /*to_page_group=*/false);
+    }
+    checkpoint_imported_pages_[group_id] = num_logical_pages;
+  }
 
-    ffi::Tensor layer_pages = pages_[group_id];
-    int64_t logical_page_index = 0;
-    while (logical_page_index < num_logical_pages) {
-      int64_t run_length = 1;
-      while (logical_page_index + run_length < num_logical_pages &&
-             page_ids[logical_page_index + run_length] ==
-                 page_ids[logical_page_index] + run_length) {
-        ++run_length;
-      }
-      CopyCheckpointPageRun(src, logical_page_index, layer_pages, 
page_ids[logical_page_index],
-                            run_length);
-      logical_page_index += run_length;
+  void ImportPageRange(int64_t seq_id, int64_t group_id, int64_t page_begin, 
int64_t page_end,
+                       ffi::Tensor src, int64_t src_page_offset) final {
+    CheckCheckpointLayoutSupported();
+    TVM_FFI_ICHECK(checkpoint_import_in_progress_)
+        << "PagedAttentionKVCache checkpoint import has not been prepared.";
+    CheckCheckpointSequenceState(seq_id);
+    const Sequence& seq = seq_map_.at(seq_id);
+    CheckCheckpointGroupId(group_id, "import");
+    int64_t num_logical_pages = GetNumLogicalPages(seq);
+    CheckCheckpointPageRange(page_begin, page_end, num_logical_pages, 
"import");
+    int64_t imported_pages = 
std::max<int64_t>(checkpoint_imported_pages_[group_id], 0);
+    TVM_FFI_ICHECK_LE(page_begin, imported_pages)
+        << "PagedAttentionKVCache checkpoint import of group " << group_id << 
" pages ["
+        << page_begin << ", " << page_end << ") leaves pages [" << 
imported_pages << ", "
+        << page_begin << ") unimported.";
+    CheckPageRangeTensor(src, src_page_offset, page_end - page_begin, 
"ImportPageRange");
+    std::vector<int32_t> page_ids = GetCheckpointPageIds(seq, "checkpoint 
import");
+
+    if (copy_stream_ != nullptr) {
+      DeviceAPI::Get(device_)->SyncStreamFromTo(device_, copy_stream_, 
compute_stream_);
     }
-    TVM_FFI_ICHECK_EQ(logical_page_index, num_logical_pages);
-    checkpoint_imported_groups_[group_id] = true;
+    CopyCheckpointPages(pages_[group_id], page_ids, page_begin, page_end, src, 
src_page_offset,
+                        /*to_page_group=*/false);
+    checkpoint_imported_pages_[group_id] = std::max(imported_pages, page_end);
   }
 
   void FinishImport(int64_t seq_id) final {
@@ -1076,12 +1099,15 @@ class PagedAttentionKVCacheObj : public 
AttentionKVCacheObj {
     TVM_FFI_ICHECK(checkpoint_import_in_progress_)
         << "PagedAttentionKVCache checkpoint import has not been prepared.";
     CheckCheckpointSequenceState(seq_id);
+    int64_t num_logical_pages = GetNumLogicalPages(seq_map_.at(seq_id));
     for (int64_t group_id = 0; group_id < num_layers_; ++group_id) {
-      TVM_FFI_ICHECK(checkpoint_imported_groups_[group_id])
-          << "PagedAttentionKVCache checkpoint import is missing group " << 
group_id << ".";
+      TVM_FFI_ICHECK_EQ(checkpoint_imported_pages_[group_id], 
num_logical_pages)
+          << "PagedAttentionKVCache checkpoint import is missing group " << 
group_id << " pages ["
+          << std::max<int64_t>(checkpoint_imported_pages_[group_id], 0) << ", 
" << num_logical_pages
+          << ").";
     }
     checkpoint_import_in_progress_ = false;
-    checkpoint_imported_groups_.clear();
+    checkpoint_imported_pages_.clear();
   }
 
   int32_t GetSequenceLength(int64_t seq_id) const final {
@@ -2305,6 +2331,47 @@ class PagedAttentionKVCacheObj : public 
AttentionKVCacheObj {
     CheckPageGroupTensor(src, num_logical_pages, "ImportPageGroup");
   }
 
+  void CheckPageRangeTensor(const ffi::Tensor& tensor, int64_t page_offset, 
int64_t num_pages,
+                            const char* api_name) const {
+    std::string error_msg = std::string(api_name) +
+                            " expects the tensor in layout "
+                            
"(1,num_pages,2,num_kv_heads,page_size,qk_head_dim).";
+    TVM_FFI_ICHECK(tensor.defined()) << error_msg;
+    TVM_FFI_ICHECK(tensor.dtype() == kv_dtype_) << error_msg << " The dtype 
mismatches, expected "
+                                                << kv_dtype_ << ", got " << 
tensor.dtype() << ".";
+    TVM_FFI_ICHECK_EQ(tensor.ndim(), 6) << error_msg;
+    TVM_FFI_ICHECK_EQ(tensor.shape()[0], 1) << error_msg << " The group count 
mismatches.";
+    TVM_FFI_ICHECK_EQ(tensor.shape()[2], 2) << error_msg << " The K/V axis 
mismatches.";
+    TVM_FFI_ICHECK_EQ(tensor.shape()[3], num_kv_heads_)
+        << error_msg << " The number of KV heads mismatches.";
+    TVM_FFI_ICHECK_EQ(tensor.shape()[4], page_size_) << error_msg << " The 
page size mismatches.";
+    TVM_FFI_ICHECK_EQ(tensor.shape()[5], qk_head_dim_)
+        << error_msg << " The head dimension mismatches.";
+    TVM_FFI_ICHECK(page_offset >= 0 && page_offset <= tensor.shape()[1] &&
+                   num_pages <= tensor.shape()[1] - page_offset)
+        << api_name << " page offset " << page_offset << " with " << num_pages
+        << " pages is out of range for a tensor of " << tensor.shape()[1] << " 
pages.";
+  }
+
+  void CheckCheckpointGroupId(int64_t group_id, const char* operation) const {
+    TVM_FFI_ICHECK(group_id >= 0 && group_id < num_layers_)
+        << "PagedAttentionKVCache checkpoint " << operation << " got invalid 
group id " << group_id
+        << ", but only " << num_layers_ << " groups are available.";
+  }
+
+  void CheckCheckpointLength(const Sequence& seq, int64_t seq_length) const {
+    TVM_FFI_ICHECK(seq_length >= 0 && seq_length <= seq.seq_length)
+        << "PagedAttentionKVCache checkpoint length " << seq_length
+        << " is outside the sequence length " << seq.seq_length << ".";
+  }
+
+  void CheckCheckpointPageRange(int64_t page_begin, int64_t page_end, int64_t 
num_logical_pages,
+                                const char* operation) const {
+    TVM_FFI_ICHECK(0 <= page_begin && page_begin <= page_end && page_end <= 
num_logical_pages)
+        << "PagedAttentionKVCache checkpoint " << operation << " got page 
range [" << page_begin
+        << ", " << page_end << ") outside the " << num_logical_pages << " 
logical pages.";
+  }
+
   ffi::json::Array MakeAttnKindsMetadata() const {
     ffi::json::Array result;
     for (int64_t layer_id = layer_id_begin_offset_; layer_id < 
layer_id_end_offset_; ++layer_id) {
@@ -2375,14 +2442,14 @@ class PagedAttentionKVCacheObj : public 
AttentionKVCacheObj {
     return os.str();
   }
 
-  ffi::json::Array MakeLogicalPageMetadata(const Sequence& seq) const {
+  ffi::json::Array MakeLogicalPageMetadata(int64_t seq_length) const {
     namespace json = tvm::ffi::json;
     json::Array pages;
-    int64_t num_logical_pages = GetExpectedNumLogicalPages(seq.seq_length);
+    int64_t num_logical_pages = GetExpectedNumLogicalPages(seq_length);
     for (int64_t logical_page_index = 0; logical_page_index < 
num_logical_pages;
          ++logical_page_index) {
       int64_t page_start = logical_page_index * page_size_;
-      int64_t page_length = std::min<int64_t>(page_size_, seq.seq_length - 
page_start);
+      int64_t page_length = std::min<int64_t>(page_size_, seq_length - 
page_start);
       TVM_FFI_ICHECK_GT(page_length, 0);
       json::Object page_json;
       page_json.Set("logical_page_index", logical_page_index);
@@ -2404,10 +2471,9 @@ class PagedAttentionKVCacheObj : public 
AttentionKVCacheObj {
     return num_pages;
   }
 
-  ffi::json::Array MakePageGroupMetadata(const Sequence& seq) const {
+  ffi::json::Array MakePageGroupMetadata(int64_t num_logical_pages) const {
     namespace json = tvm::ffi::json;
     json::Array groups;
-    int64_t num_logical_pages = GetNumLogicalPages(seq);
     for (int64_t local_layer = 0; local_layer < num_layers_; ++local_layer) {
       json::Object group;
       group.Set("group_index", local_layer);
@@ -2472,6 +2538,33 @@ class PagedAttentionKVCacheObj : public 
AttentionKVCacheObj {
     tvm::runtime::CopyFromTo(src_pages.GetDLTensorPtr(), &dst_pages_view, 
compute_stream_);
   }
 
+  /*!
+   * \brief Copy logical pages [begin, end) between a layer's page pool and a 
page
+   * group tensor, one copy per run of physically consecutive pages.
+   */
+  void CopyCheckpointPages(const ffi::Tensor& layer_pages, const 
std::vector<int32_t>& page_ids,
+                           int64_t begin, int64_t end, const ffi::Tensor& 
page_group,
+                           int64_t page_group_offset, bool to_page_group) 
const {
+    int64_t logical_page_index = begin;
+    while (logical_page_index < end) {
+      int64_t run_length = 1;
+      while (logical_page_index + run_length < end &&
+             page_ids[logical_page_index + run_length] ==
+                 page_ids[logical_page_index] + run_length) {
+        ++run_length;
+      }
+      int64_t group_page_index = page_group_offset + logical_page_index - 
begin;
+      if (to_page_group) {
+        CopyCheckpointPageRun(layer_pages, page_ids[logical_page_index], 
page_group,
+                              group_page_index, run_length);
+      } else {
+        CopyCheckpointPageRun(page_group, group_page_index, layer_pages,
+                              page_ids[logical_page_index], run_length);
+      }
+      logical_page_index += run_length;
+    }
+  }
+
   void ExportPartialCheckpointPage(const ffi::Tensor& src, int64_t 
src_page_index,
                                    const ffi::Tensor& dst, int64_t 
dst_page_index,
                                    int64_t valid_length) {
diff --git 
a/tests/python/relax/test_runtime_builtin_paged_attention_kv_cache_cpu.py 
b/tests/python/relax/test_runtime_builtin_paged_attention_kv_cache_cpu.py
index 1663c7eeba..137c503005 100644
--- a/tests/python/relax/test_runtime_builtin_paged_attention_kv_cache_cpu.py
+++ b/tests/python/relax/test_runtime_builtin_paged_attention_kv_cache_cpu.py
@@ -75,9 +75,12 @@ fattention_with_shared_kv = None
 fis_empty = None
 fdebug_get_kv = None
 fget_checkpoint_metadata = None
+fget_checkpoint_metadata_at = None
 fexport_page_group = None
+fexport_page_range = None
 fprepare_import = None
 fimport_page_group = None
+fimport_page_range = None
 ffinish_import = None
 fget_sequence_length = None
 
@@ -103,8 +106,10 @@ def set_global_func(head_dim, dtype, 
layer_sliding_window_size=1024):
     global fclear, fadd_sequence, fremove_sequence, ffork_sequence, 
fenable_sliding_window_for_seq
     global fpopn, fbegin_forward, fend_forward, 
fcommit_accepted_token_tree_nodes
     global fattention_with_fuse_qkv, fattention_with_shared_kv, fis_empty, 
fdebug_get_kv
-    global fget_checkpoint_metadata, fexport_page_group
-    global fprepare_import, fimport_page_group, ffinish_import, 
fget_sequence_length
+    global fget_checkpoint_metadata, fget_checkpoint_metadata_at
+    global fexport_page_group, fexport_page_range
+    global fprepare_import, fimport_page_group, fimport_page_range
+    global ffinish_import, fget_sequence_length
     global ftranspose_append, fcopy_cache, fattn_prefill, fattn_decode
     global \
         fattn_prefill_ragged, \
@@ -137,9 +142,14 @@ def set_global_func(head_dim, dtype, 
layer_sliding_window_size=1024):
     fget_checkpoint_metadata = tvm_ffi.get_global_func(
         "vm.builtin.attention_kv_cache_get_checkpoint_metadata"
     )
+    fget_checkpoint_metadata_at = tvm_ffi.get_global_func(
+        "vm.builtin.attention_kv_cache_get_checkpoint_metadata_at"
+    )
     fexport_page_group = 
tvm_ffi.get_global_func("vm.builtin.attention_kv_cache_export_page_group")
+    fexport_page_range = 
tvm_ffi.get_global_func("vm.builtin.attention_kv_cache_export_page_range")
     fprepare_import = 
tvm_ffi.get_global_func("vm.builtin.attention_kv_cache_prepare_import")
     fimport_page_group = 
tvm_ffi.get_global_func("vm.builtin.attention_kv_cache_import_page_group")
+    fimport_page_range = 
tvm_ffi.get_global_func("vm.builtin.attention_kv_cache_import_page_range")
     ffinish_import = 
tvm_ffi.get_global_func("vm.builtin.attention_kv_cache_finish_import")
     fget_sequence_length = tvm_ffi.get_global_func(
         "vm.builtin.attention_kv_cache_get_sequence_length"
@@ -871,6 +881,141 @@ def 
test_paged_attention_kv_cache_import_page_group_round_trip():
     verify_debug_kv_equal(src_cache, dst_cache, 0, metadata["seq_length"] + 1)
 
 
+def export_page_ranges(kv_cache, seq_length, page_begin):
+    page_end = (seq_length + page_size - 1) // page_size
+    shape = (1, page_end - page_begin, 2, num_kv_heads, page_size, head_dim)
+    groups = []
+    for layer in range(num_layers):
+        group_data = tvm_tirx.runtime.empty(shape, dtype=dtype, device=device)
+        fexport_page_range(kv_cache, 0, layer, seq_length, page_begin, 
page_end, group_data, 0)
+        groups.append(group_data)
+    return groups
+
+
+def test_paged_attention_kv_cache_incremental_checkpoint_round_trip():
+    global head_dim, sm_scale, dtype
+    head_dim = 64
+    dtype = "float32"
+    sm_scale = head_dim ** (-0.5)
+    set_global_func(head_dim, dtype)
+    src_cache = create_kv_cache(head_dim, dtype, RopeMode.NONE, False)
+
+    cached_k = {}
+    cached_v = {}
+    base_length = page_size * 2 + 3
+    apply_attention(src_cache, RopeMode.NONE, [(0, base_length)], cached_k, 
cached_v)
+    assert fget_checkpoint_metadata_at(src_cache, 0, base_length) == 
fget_checkpoint_metadata(
+        src_cache, 0
+    )
+    base = [group.numpy() for group in export_page_ranges(src_cache, 
base_length, 0)]
+
+    # Append past the base, including a speculative tail that is popped. Pages
+    # below the base length must export identically while later positions grow.
+    apply_attention(src_cache, RopeMode.NONE, [(0, page_size * 2)], cached_k, 
cached_v)
+    apply_attention(src_cache, RopeMode.NONE, [(0, 3)], cached_k, cached_v)
+    fpopn(src_cache, 0, 3)
+    cached_k[0] = cached_k[0][:, :-3, ...]
+    cached_v[0] = cached_v[0][:, :-3, ...]
+    for layer, group in enumerate(export_page_ranges(src_cache, base_length, 
0)):
+        np.testing.assert_array_equal(group.numpy(), base[layer])
+    np.testing.assert_array_equal(base[0][0, 2, :, :, 3:, :], 0)
+
+    tip_length = base_length + page_size * 2
+    delta_begin = base_length // page_size
+    delta = export_page_ranges(src_cache, tip_length, delta_begin)
+    metadata_json = fget_checkpoint_metadata_at(src_cache, 0, tip_length)
+    assert json.loads(metadata_json)["seq_length"] == tip_length
+
+    dst_cache = create_kv_cache(head_dim, dtype, RopeMode.NONE, False)
+    fprepare_import(dst_cache, 0, metadata_json)
+    for layer in range(num_layers):
+        base_data = tvm_tirx.runtime.tensor(base[layer], device=device)
+        fimport_page_range(dst_cache, 0, layer, 0, delta_begin + 1, base_data, 
0)
+        with pytest.raises(RuntimeError, match="unimported"):
+            # The base ends at a partial page; its last page must be 
overwritten
+            # by the delta, which starts there, before later pages.
+            fimport_page_range(
+                dst_cache, 0, layer, delta_begin + 2, delta_begin + 3, 
delta[layer], 2
+            )
+        fimport_page_range(dst_cache, 0, layer, delta_begin, delta_begin + 3, 
delta[layer], 0)
+        if layer == 0:
+            with pytest.raises(RuntimeError, match="missing group"):
+                ffinish_import(dst_cache, 0)
+    ffinish_import(dst_cache, 0)
+    assert fget_sequence_length(dst_cache, 0) == tip_length
+    verify_debug_kv_equal(src_cache, dst_cache, 0, tip_length)
+
+    dst_cached_k = {0: cached_k[0].copy()}
+    dst_cached_v = {0: cached_v[0].copy()}
+    random_state = np.random.get_state()
+    apply_attention(src_cache, RopeMode.NONE, [(0, 1)], cached_k, cached_v)
+    np.random.set_state(random_state)
+    apply_attention(dst_cache, RopeMode.NONE, [(0, 1)], dst_cached_k, 
dst_cached_v)
+    verify_debug_kv_equal(src_cache, dst_cache, 0, tip_length + 1)
+
+
+def test_paged_attention_kv_cache_page_range_bounds_and_offsets():
+    global head_dim, sm_scale, dtype
+    head_dim = 64
+    dtype = "float32"
+    sm_scale = head_dim ** (-0.5)
+    set_global_func(head_dim, dtype)
+    src_cache = create_kv_cache(head_dim, dtype, RopeMode.NONE, False)
+    fadd_sequence(src_cache, 0)
+
+    # Preserve whole-group export/import of a sequence with no tokens.
+    empty_metadata = fget_checkpoint_metadata(src_cache, 0)
+    dst_cache = create_kv_cache(head_dim, dtype, RopeMode.NONE, False)
+    fprepare_import(dst_cache, 0, empty_metadata)
+    empty = tvm_tirx.runtime.empty((1, 0, 2, num_kv_heads, page_size, 
head_dim), dtype, device)
+    for layer in range(num_layers):
+        fexport_page_group(src_cache, 0, layer, empty)
+        fimport_page_group(dst_cache, 0, layer, empty)
+    ffinish_import(dst_cache, 0)
+    assert fget_sequence_length(dst_cache, 0) == 0
+
+    fclear(src_cache)
+    length = page_size + 3
+    apply_attention(src_cache, RopeMode.NONE, [(0, length)], {}, {})
+    expected = export_page_ranges(src_cache, length, 0)
+    padded = tvm_tirx.runtime.tensor(
+        np.full((1, 4, 2, num_kv_heads, page_size, head_dim), -1, 
dtype=dtype), device=device
+    )
+    for bad_length in [-1, length + 1]:
+        with pytest.raises(RuntimeError, match="outside the sequence length"):
+            fget_checkpoint_metadata_at(src_cache, 0, bad_length)
+    for group_id, begin, end, offset in [
+        (-1, 0, 1, 0),
+        (num_layers, 0, 1, 0),
+        (0, -1, 1, 0),
+        (0, 2, 1, 0),
+        (0, 0, 3, 0),
+        (0, 0, 2, -1),
+        (0, 0, 2, 3),
+        (0, 0, 2, 2**63 - 1),
+    ]:
+        with pytest.raises(RuntimeError, match="group id|page range|out of 
range"):
+            fexport_page_range(src_cache, 0, group_id, length, begin, end, 
padded, offset)
+    wrong_dtype = tvm_tirx.runtime.empty(padded.shape, "float16", device)
+    with pytest.raises(RuntimeError, match="dtype"):
+        fexport_page_range(src_cache, 0, 0, length, 0, 2, wrong_dtype, 0)
+
+    fprepare_import(dst_cache, 0, fget_checkpoint_metadata_at(src_cache, 0, 
length))
+    for layer in range(num_layers):
+        fexport_page_range(src_cache, 0, layer, length, 0, 2, padded, 1)
+        data = padded.numpy()
+        np.testing.assert_array_equal(data[:, 1:3], expected[layer].numpy())
+        np.testing.assert_array_equal(data[:, [0, 3]], -1)
+        # An empty range at the end of a partially filled page is a no-op.
+        fexport_page_range(src_cache, 0, layer, length, 2, 2, padded, 0)
+        np.testing.assert_array_equal(padded.numpy(), data)
+        with pytest.raises(RuntimeError, match="out of range"):
+            fimport_page_range(dst_cache, 0, layer, 0, 2, padded, 3)
+        fimport_page_range(dst_cache, 0, layer, 0, 2, padded, 1)
+    ffinish_import(dst_cache, 0)
+    verify_debug_kv_equal(src_cache, dst_cache, 0, length)
+
+
 def test_paged_attention_kv_cache_remove_sequence(kv_cache_and_config):
     kv_cache, rope_mode, support_sliding_window = kv_cache_and_config
     if support_sliding_window and rope_mode == RopeMode.NORMAL:

Reply via email to