ArborKV: Structure-Aware KV Cache Management for Scaling Tree-based LLM Reasoning

Recent progress in LLM reasoning has increasingly shifted from single-pass generation to explicit search over intermediate reasoning states. Tree-of-Thoughts (ToT) organizes inference to tree-structured search with branching and backtracking, but it substantially amplifies the key--value (KV) cache: retaining KV states for a frontier of partial trajectories quickly becomes a memory bottleneck that limits throughput and constrains search depth and width under fixed hardware budgets. We address this challenge by observing that KV reuse in ToT-style inference is governed by search dynamics: near-term decoding depends primarily on the active branch and its ancestors, whereas inactive subtrees have low short-term reuse probability yet must remain recoverable for backtracking. Motivated by this, we propose **ArborKV**, a structure-aware eviction framework that couples a lightweight value estimator with a tree-aware allocation policy, and performs purely token-extractive eviction with lazy rehydration to support revisits. Experiments on ToT-style reasoning benchmarks show that ArborKV achieves up to $\sim4\times$ peak KV-memory reduction while preserving near-full-retention accuracy, enabling larger search configurations under fixed device budgets that would otherwise run out of memory.

Large language models can solve difficult problems more effectively when they explore several possible solution paths, but this process quickly uses a large amount of computer memory. We propose ArborKV, a method that manages this memory by following the structure of the model’s search. It keeps more information for the current and promising paths, removes less urgent information from inactive paths, and restores it only when needed. This allows models to perform broader reasoning searches with much lower memory use while largely preserving accuracy.