profile pic
⌘ '
raccourcis clavier
Search

Radix tree

  • Étiquette

    • publié à

    • modifié à

    • durée

      2 min de lecture

    • source

      llms.txt

    A prefix trie in which each node that is the only child is merged with its parent.

    By Claudio Rocchini - Own work, CC BY 2.5, wikimedia

    result: number of all internal nodes is at most the radix rr of the tree, where r=2x∀x∈Rd∩x≥1r=2^{x} \forall x \in \mathbb{R}^d \cap x \ge 1

    Edge can be labelled with sequences of elements as well as single elements.

    key at each node is compared chunk-of-bits, where quantity of bits in any given chunk is the radix rr of the radix tree:

    • r=2r=2 then radix trie is binary, which minimise sparsity at the expense of maximising trie-depth
    • r≥4r \ge 4 is a power of two, then it is a r-ary trie, which lessen the depth at the expense of some sparseness

    Lookup pseudocode:

    "\\begin{algorithm}\n\\caption{Lookup}\n\\begin{algorithmic}\n\\State $\\text{traverseNode} \\gets \\text{root}$\n\\State $\\text{elementsFound} \\gets 0$\n\\While{traverseNode $\\neq \\text{null} \\land \\neg \\text{traverseNode}.\\text{isLeaf}() \\land \\text{elementsFound} < \\text{length}(x)$}\n \\State nextEdge $\\gets$ select edge from traverseNode.edges where edge.label is a prefix of $x.\\text{suffix}(\\text{elementsFound})$\n \\If{nextEdge $\\neq \\text{null}$}\n \\State traverseNode $\\gets$ nextEdge.targetNode\n \\State elementsFound $\\gets$ elementsFound + length(nextEdge.label)\n \\Else\n \\State traverseNode $\\gets$ null\n \\EndIf\n\\EndWhile\n\\State \\Return traverseNode $\\neq \\text{null} \\land \\text{traverseNode}.\\text{isLeaf}() \\land \\text{elementsFound} = \\text{length}(x)$\n\\end{algorithmic}\n\\end{algorithm}"

    Algorithm 5 Lookup

    1:traverseNode←root\text{traverseNode} \gets \text{root}

    2:elementsFound←0\text{elementsFound} \gets 0

    3:while traverseNode ≠null∧¬traverseNode.isLeaf()∧elementsFound<length(x)\neq \text{null} \land \neg \text{traverseNode}.\text{isLeaf}() \land \text{elementsFound} < \text{length}(x) do

    4:nextEdge ←\gets select edge from traverseNode.edges where edge.label is a prefix of x.suffix(elementsFound)x.\text{suffix}(\text{elementsFound})

    5:if nextEdge ≠null\neq \text{null} then

    6:traverseNode ←\gets nextEdge.targetNode

    7:elementsFound ←\gets elementsFound + length(nextEdge.label)

    8:else

    9:traverseNode ←\gets null

    10:end if

    11:end while

    12:

    13:return traverseNode ≠null∧traverseNode.isLeaf()∧elementsFound=length(x)\neq \text{null} \land \text{traverseNode}.\text{isLeaf}() \land \text{elementsFound} = \text{length}(x)

    complexity

    Permits lookup, deletion, insertion in O(k)O(k) rather than O(log⁡n)O(\log n)

    Normally k≥log⁡nk \ge \log n, but in a balanced tree every comparison is a string comparison requires O(k)O(k) worse-case time. Whereas in a trie all comparison require constant times, but takes mm comparisons to look up a string length mm

    Vous pourriez aimer ce qui suit

  • latent space
  • Giles Deleuze
  • Existentialism
  • Open-loop system
  • regularization
  • GPU programming
  • Convolutional Neural Network
    • Attention
    (Vaswani et al., 2023) Attention operates on a sequence of query Q, key K and value V vector. Attention matrix of a sequence then computed as: A(Q, K, V) = \text{softmax}(\frac{Q \cdot K^{T}}{\sqrt{d}})V \space \space \text{ for } Q_{L \times d}, K_{L \times d}, V_{L \times d} Muti-head Attention Allows the model to jointly attend to information from different representation subspaces at different positions: \begin{aligned} \text{MHA}(Q,K,V) &= \text{concat}(\text{head}_1, \cdots, \text{head}_n) W^O \\ &\text{where } \space \text{head}_i = \text{A}(QW_i^O, KW_i^O, VW_i^O) \\ W^O & \in \mathbb{R}^{hd_v \times d_{\text{model}}} \end{aligned} Group-Query Attention by (Ainslie et al., 2023) idea: reduce number of KV heads n_k to a fraction n_k^{'} = \frac{n_q}{k} of number of query heads n_q (evenly dividing the query heads into n_k groups with r heads) RadixAttention Implemented in (Zheng et al., 2024) where they maintain a LRU eviction policy to maintain relevant KV cache for all requests within a radix tree radix tree setup: key: sequence of tokens value: KV cache tensor (stored in GPU in a paged layout) dynamic evolution of the radix tree in response to various requests.