1 of 168

Large Language Models

Lecture 16

Efficient LLM Decoding

Krishnendu Ghosh

2 of 168

Forward Pass through an LLM

3 of 168

Forward Pass through an LLM

4 of 168

Forward Pass through an LLM

5 of 168

Forward Pass through an LLM

6 of 168

Forward Pass through an LLM

7 of 168

Forward Pass through an LLM

8 of 168

Forward Pass through an LLM

9 of 168

Forward Pass through an LLM

10 of 168

Forward Pass through an LLM

11 of 168

Forward Pass through an LLM

12 of 168

Inference through an LLM

13 of 168

Inference through an LLM

14 of 168

Inference through an LLM

15 of 168

Inference through an LLM

16 of 168

Inference through an LLM

17 of 168

Inference through an LLM

18 of 168

Inference through an LLM

19 of 168

Inference through an LLM

20 of 168

Inference through an LLM

21 of 168

Inference through an LLM

22 of 168

Inference through an LLM

23 of 168

Inference through an LLM

24 of 168

Inference through an LLM

25 of 168

Inference through an LLM

26 of 168

Inference through an LLM

27 of 168

Inference through an LLM

28 of 168

Why we need efficient inference?

29 of 168

Inference through an LLM

30 of 168

Inference through an LLM

31 of 168

Inference through an LLM

32 of 168

Inference through an LLM

33 of 168

Inference through an LLM

34 of 168

Inference through an LLM

35 of 168

Inference through an LLM

36 of 168

Inference through an LLM

37 of 168

Inference through an LLM

38 of 168

Inference through an LLM

39 of 168

Inference through an LLM

40 of 168

Inference through an LLM

41 of 168

Inference through an LLM

42 of 168

Inference through an LLM

43 of 168

Inference through an LLM

44 of 168

Inference through an LLM

45 of 168

Inference through an LLM

46 of 168

Inference through an LLM

47 of 168

Inference through an LLM

48 of 168

Inference through an LLM

49 of 168

Inference through an LLM

50 of 168

Inference through an LLM

51 of 168

Inference through an LLM

52 of 168

Inference through an LLM

53 of 168

Inference through an LLM

54 of 168

Inference through an LLM

55 of 168

Inference through an LLM

56 of 168

Inference through an LLM

57 of 168

Inference through an LLM

58 of 168

Inference through an LLM

59 of 168

Inference through an LLM

60 of 168

Inference through an LLM

61 of 168

Inference through an LLM

62 of 168

Inference through an LLM

63 of 168

Inference through an LLM

64 of 168

Inference through an LLM

65 of 168

Inference through an LLM

66 of 168

Inference through an LLM

67 of 168

Inference through an LLM

68 of 168

Inference through an LLM

69 of 168

Inference through an LLM

70 of 168

Inference through an LLM

71 of 168

Inference through an LLM

72 of 168

Two stages of LLM inference

73 of 168

74 of 168

Inference through an LLM

75 of 168

Memory Usage of KV cache

76 of 168

Memory Usage: Example OPT-13B

77 of 168

Memory Usage: Example OPT-13B

78 of 168

Memory Management of KV Cache

79 of 168

Memory Management of KV Cache

80 of 168

Memory Management of KV Cache

81 of 168

Memory Management of KV Cache

82 of 168

Memory Management of KV Cache

83 of 168

Memory Management of KV Cache

84 of 168

Memory Management of KV Cache

85 of 168

Memory Management of KV Cache

86 of 168

Memory Management of KV Cache

87 of 168

Memory Layout for 13B-OPT model

on A100 (40GB)

88 of 168

vLLM

Efficient KV cache management

89 of 168

vLLM

Efficient KV cache management

90 of 168

KV Blocks

91 of 168

KV Blocks

92 of 168

KV Blocks

93 of 168

Physical vs Logical KV Blocks

94 of 168

Physical vs Logical KV Blocks

95 of 168

Physical vs Logical KV Blocks

96 of 168

Physical vs Logical KV Blocks

97 of 168

Physical vs Logical KV Blocks

98 of 168

Physical vs Logical KV Blocks

99 of 168

Physical vs Logical KV Blocks

100 of 168

Physical vs Logical KV Blocks

101 of 168

Physical vs Logical KV Blocks

102 of 168

Physical vs Logical KV Blocks

103 of 168

Physical vs Logical KV Blocks

104 of 168

Physical vs Logical KV Blocks

105 of 168

Physical vs Logical KV Blocks

106 of 168

Physical vs Logical KV Blocks

107 of 168

Physical vs Logical KV Blocks

108 of 168

Physical vs Logical KV Blocks

109 of 168

Physical vs Logical KV Blocks

110 of 168

Dynamic Block Mapping

111 of 168

Sharing KV blocks

in parallel sampling

112 of 168

Sharing KV blocks

in parallel sampling

113 of 168

Sharing KV blocks

in parallel sampling

114 of 168

Sharing KV blocks

in parallel sampling

115 of 168

Sharing KV blocks

in parallel sampling

116 of 168

Sharing KV blocks

in parallel sampling

117 of 168

Sharing KV blocks

in parallel sampling

118 of 168

Sharing KV blocks

in parallel sampling

119 of 168

Sharing KV blocks

in parallel sampling

120 of 168

Sharing KV blocks

in parallel sampling

121 of 168

Memory efficiency of vLLMs

122 of 168

Paged Attention

123 of 168

How vLLM & Paged Attention

results in efficient inference?

124 of 168

HuggingFace vs TGI (2023)

125 of 168

System Architecture and

Implementation

126 of 168

127 of 168

Flash Attention - Recap

128 of 168

Flash Attention - Recap

129 of 168

Flash Attention - Recap

130 of 168

Flash Attention - Recap

131 of 168

Flash Decoding

132 of 168

Benchmarking on CodeLlama-34B

133 of 168

Inference through an LLM

134 of 168

Inference through an LLM

135 of 168

Inference through an LLM

136 of 168

Inference through an LLM

137 of 168

Speculative decoding

138 of 168

How to Guess?

139 of 168

How to Guess?

140 of 168

Example from HumanEval dataset

141 of 168

Speculative Sampling

142 of 168

Speculative Sampling

143 of 168

Algorithm

144 of 168

Algorithm

145 of 168

Algorithm

146 of 168

Rejection Sampling

147 of 168

Rejection Sampling

148 of 168

Rejection Sampling

149 of 168

Wall time speedup:

Illustration on an encoder-decoder model

150 of 168

Results

151 of 168

How to guess?

152 of 168

153 of 168

Medusa

154 of 168

How to train multiple LM heads?

155 of 168

Tree Attention

156 of 168

Prune the tree!

157 of 168

Prune the tree!

158 of 168

Acceptance Criteria

159 of 168

Impact of the Threshold

160 of 168

Results

161 of 168

How to guess?

162 of 168

Results

163 of 168

How to guess?

164 of 168

Lookahead Decoding

165 of 168

Summary

166 of 168

Continuous Batching

167 of 168

Continuous Batching

168 of 168

Source: https://lcs2-iitd.github.io/ELL881-AIL821-2401/lectures/