Skip to content
TheChatArchiveThe Chat Archive
Claudeclaude-opus-4-20250514-thinking-16k· AnthropicHugging Face LMArena Human Preference 140K

Untitled conversation

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Metallama-4-maverick-03-26-experimental’s answer.
  1. User
    pub struct RadixTree {
        /// This is the root of the radix/prefix tree
        /// This will only contain root blocks
        root: SharedRadixBlock,
    
        /// This is a global lookup table for all blocks which will let you jump into
        /// the radix tree at any point
        /// Lookup is best case O(1) and worst case O(N); however, even constant in-time
        /// could be expensive if N is large
        /// We should monitor the size of this table and consider using a proper radix tree.
        /// Transitioning to a radix tree only would require a change in the messaging structure
        /// as the entire prefix would need to be sent. Alternatively, we could use block_depth
        /// integers to indicate how many blocks to skip and use a radix/prefix tree at each level.
        lookup: HashMap<WorkerId, HashMap<ExternalSequenceBlockHash, SharedRadixBlock>>,
        /// The time buffer the radix tree should check when considering frequence of block accesses
        expiration_duration: Option<Duration>,
    }
    
    impl Default for RadixTree {
        fn default() -> Self {
            Self::new()
        }
    }
    
    impl RadixTree {
        /// Create a new `RadixTree`.
        ///
        /// ### Returns
        ///
        /// A new `RadixTree`.
        pub fn new_with_frequency(expiration_duration: Option<Duration>) -> Self {
            Self {
                root: Rc::new(RefCell::new(RadixBlock::new())),
                lookup: HashMap::new(),
                expiration_duration,
            }
        }
    
        pub fn new() -> Self {
            Self::new_with_frequency(None)
        }
    
        /// Traverse the radix tree to find the best match for a given sequence of [`LocalBlockHash`]es.
        ///
        /// ### Arguments
        ///
        /// * `sequence` - A vector of `LocalBlockHash` representing the sequence to match.
        /// * `early_exit` - A boolean indicating whether to exit early if a single match is found.
        ///
        /// ### Returns
        ///
        /// An `OverlapScores` representing the match scores.
        pub fn find_matches(&self, sequence: Vec<LocalBlockHash>, early_exit: bool) -> OverlapScores {
            let mut scores = OverlapScores::new();
            let mut current = self.root.clone();
            let now = Instant::now();
            for block_hash in sequence {
                let next_block = {
                    let current_borrow = current.borrow();
                    current_borrow.children.get(&block_hash).cloned()
                };
                if let Some(block) = next_block {
                    scores.update_scores(&block.borrow().workers);
    
                    if let Some(expiration_duration) = self.expiration_duration {
                        let mut block_mut = block.borrow_mut();
    
                        while let Some(access_time) = block_mut.recent_uses.front() {
                            if now.duration_since(*access_time) > expiration_duration {
                                block_mut.recent_uses.pop_front();
                            } else {
                                break;
                            }
                        }
                        scores.add_frequency(block_mut.recent_uses.len());
                        block_mut.recent_uses.push_back(now);
                    }
    
                    if early_exit && block.borrow().workers.len() == 1 {
                        break;
                    }
    
                    current = block;
                } else {
                    break;
                }
            }
    
            scores
        }
    
        /// Apply a [`RouterEvent`] to the radix tree.
        ///
        /// ### Arguments
        ///
        /// * `event` - The `RouterEvent` to apply.
        pub fn apply_event(&mut self, event: RouterEvent) {
            let (worker_id, event) = (event.worker_id, event.event);
            let (id, op) = (event.event_id, event.data);
            tracing::trace!(id, "Store operation: {:?}", op);
    
            let worker_lookup = self.lookup.entry(worker_id).or_default();
    
            match op {
                KvCacheEventData::Stored(op) => {
                    // find the parent block - if the parent exists it must be on our worker, if not,
                    // we check the radix tree's root to find it.
                    // this is the single most expensive lookup
                    let current = match op.parent_hash {
                        Some(parent) => worker_lookup.get(&parent),
                        None => Some(&self.root),
                    };
    
                    let mut current = match current {
                        Some(current) => current.clone(),
                        None => {
                            tracing::warn!(
                                worker_id = worker_id.to_string(),
                                id,
                                parent_hash = ?op.parent_hash,
                                "Failed to find parent block; skipping store operation"
                            );
                            return;
                        }
                    };
    
                    for block_id in op.blocks {
                        let mut inner = current.borrow_mut();
                        let block = match inner.children.get(&block_id.tokens_hash) {
                            Some(block) => block.clone(),
                            None => {
                                // create new block - automatically added to the lookup table
                                let new_block = worker_lookup
                                    .get(&block_id.block_hash)
                                    .cloned()
                                    .unwrap_or_else(|| Rc::new(RefCell::new(RadixBlock::new())));
    
                                // insert into radix tree
                                inner
                                    .children
                                    .insert(block_id.tokens_hash, new_block.clone());
    
                                new_block
                            }
                        };
    
                        // add our worker_id to the block
                        block.borrow_mut().workers.insert(worker_id);
    
                        // add the block to the worker_id lookup table
                        worker_lookup.insert(block_id.block_hash, block.clone());
    
                        // drop inner so we can shift current to this block
                        drop(inner);
    
                        current = block;
                    }
                }
                KvCacheEventData::Removed(remove) => {
                    // tracing::trace!(id, "KV Remove Operation: {:?}", op);
                    // let mut worker_lookup = self.lookup.get(&worker_id).expect("Worker not found");
    
                    for block in remove.block_hashes {
                        // entry in radix tree
                        // a small optimization would be to get the next block from the reduced set of children
                        // in order to apply this optimization, we would need to know the list of blocks is always sorted
                        // by parent -> child relationship
                        let entry = match worker_lookup.get(&block) {
                            Some(entry) => entry.clone(),
                            None => {
                                tracing::warn!(
                                    worker_id = worker_id.to_string(),
                                    id,
                                    "Failed to find block to remove; skipping remove operation"
                                );
                                continue;
                            }
                        };
    
                        let mut guard = entry.borrow_mut();
                        guard.workers.remove(&worker_id);
                        if guard.workers.is_empty() {
                            // if no worker are using this block, that is true for all children
                            guard.children.clear();
                        }
                        // remove the block from the lookup table
                        worker_lookup.remove(&block);
                    }
                }
                KvCacheEventData::Cleared => {
                    self.clear_all_blocks(worker_id);
                }
            }
        }
    
        pub fn remove_worker(&mut self, worker: WorkerId) {
            if let Some((_, blocks)) = self.lookup.remove_entry(&worker) {
                blocks.iter().for_each(|(_, block)| {
                    block.borrow_mut().workers.remove(&worker);
                });
            }
        }
    
        pub fn clear_all_blocks(&mut self, worker: WorkerId) {
            // Check if the worker has any blocks to clear
            if let Some(blocks) = self.lookup.get(&worker) {
                let blocks_to_clear: Vec<_> = blocks.values().collect();
    
                // Remove the worker from each block's workers set
                blocks_to_clear.iter().for_each(|block| {
                    block.borrow_mut().workers.remove(&worker);
                });
    
                // Clear the worker's blocks
                if let Some(worker_blocks) = self.lookup.get_mut(&worker) {
                    worker_blocks.clear();
                }
            }
        }
    }
    

    这是一个为LLM提供kv cache查询的Radix Tree,请讲解实现的思路和细节

  2. Claude Assistant

    这个 Radix Tree 实现是为 LLM 的 KV cache 查询优化设计的分布式前缀树结构。让我详细讲解其设计思路和实现细节:

    核心设计思路

    1. 数据结构设计

    pub struct RadixTree {
        root: SharedRadixBlock,  // 根节点
        lookup: HashMap<WorkerId, HashMap<ExternalSequenceBlockHash, SharedRadixBlock>>, // 全局查找表
        expiration_duration: Option<Duration>,  // 访问频率统计的时间窗口
    }
    

    这里采用了混合索引策略:

    • 树形结构:用于前缀匹配查询
    • 哈希表索引:实现 O(1) 的快速定位

    2. 分布式缓存管理

    系统支持多个 Worker 节点共享 KV cache:

    • 每个 RadixBlock 记录了拥有该块的所有 Worker ID
    • lookup 表按 Worker ID 分组,便于管理各 Worker 的缓存块

    3. 核心功能实现

    查找匹配(find_matches)

    pub fn find_matches(&self, sequence: Vec<LocalBlockHash>, early_exit: bool) -> OverlapScores {
        let mut scores = OverlapScores::new();
        let mut current = self.root.clone();
        
        for block_hash in sequence {
            // 沿着前缀路径遍历
            if let Some(block) = current.borrow().children.get(&block_hash) {
                // 更新匹配分数
                scores.update_scores(&block.borrow().workers);
                
                // 访问频率统计
                if let Some(expiration_duration) = self.expiration_duration {
                    // 清理过期的访问记录
                    // 记录新的访问时间
                    // 更新频率分数
                }
                
                // 早退优化:如果只有一个Worker拥有该块,可以提前结束
                if early_exit && block.borrow().workers.len() == 1 {
                    break;
                }
            }
        }
    }
    

    设计亮点:

    • 前缀匹配:找出与输入序列最长公共前缀的缓存块
    • 评分机制:根据匹配长度和访问频率计算得分
    • 早退优化:当找到唯一匹配时可提前结束

    事件处理(apply_event)

    支持三种操作:

    1. 存储操作(Stored):

      // 找到父节点
      let current = match op.parent_hash {
          Some(parent) => worker_lookup.get(&parent),
          None => Some(&self.root),
      };
      
      // 逐个插入新块
      for block_id in op.blocks {
          // 创建或更新节点
          // 更新 worker 集合
          // 更新查找表
      }
      
    2. 删除操作(Removed):

      • 从节点的 workers 集合中移除 worker ID
      • 如果节点不再被任何 worker 使用,清理其子节点
      • 更新查找表
    3. 清空操作(Cleared):

      • 批量清理特定 worker 的所有缓存块

    4. 性能优化策略

    1. 双重索引:

      • 树形结构用于前缀查询
      • HashMap 提供 O(1) 的直接访问
    2. 引用计数智能指针:

      type SharedRadixBlock = Rc<RefCell<RadixBlock>>;
      
      • 使用 Rc<RefCell<>> 实现共享可变性
      • 避免数据复制,提高内存效率
    3. 访问频率优化:

      • 使用滑动时间窗口统计访问频率
      • 优先选择频繁访问的缓存块

    5. 实际应用场景

    在 LLM 推理中,这个 Radix Tree 可以:

    1. 前缀共享:多个请求如果共享相同的前缀(如系统提示词),可以复用已缓存的 KV 值
    2. 分布式缓存:多个 Worker 节点可以共享缓存,提高资源利用率
    3. 智能路由:根据匹配度和访问频率,将请求路由到最合适的 Worker

    6. 潜在改进点

    代码注释中提到的一些考虑:

    • 当前的 lookup 表在规模很大时可能成为瓶颈
    • 可以考虑使用纯 radix tree 实现,但需要改变消息结构
    • 可以使用分层的 radix tree 来优化查找性能

    这个实现巧妙地平衡了查询效率和内存使用,特别适合 LLM 的 KV cache 场景,其中前缀共享是常见模式。

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.