| 8250 | } |
| 8251 | |
| 8252 | void llama_sample_tail_free(struct llama_context * ctx, llama_token_data_array * candidates, float z, size_t min_keep) { |
| 8253 | if (z >= 1.0f || candidates->size <= 2) { |
| 8254 | return; |
| 8255 | } |
| 8256 | |
| 8257 | llama_sample_softmax(nullptr, candidates); |
| 8258 | const int64_t t_start_sample_us = ggml_time_us(); |
| 8259 | |
| 8260 | // Compute the first and second derivatives |
| 8261 | std::vector<float> first_derivatives(candidates->size - 1); |
| 8262 | std::vector<float> second_derivatives(candidates->size - 2); |
| 8263 | |
| 8264 | for (size_t i = 0; i < first_derivatives.size(); ++i) { |
| 8265 | first_derivatives[i] = candidates->data[i].p - candidates->data[i + 1].p; |
| 8266 | } |
| 8267 | for (size_t i = 0; i < second_derivatives.size(); ++i) { |
| 8268 | second_derivatives[i] = first_derivatives[i] - first_derivatives[i + 1]; |
| 8269 | } |
| 8270 | |
| 8271 | // Calculate absolute value of second derivatives |
| 8272 | for (size_t i = 0; i < second_derivatives.size(); ++i) { |
| 8273 | second_derivatives[i] = std::abs(second_derivatives[i]); |
| 8274 | } |
| 8275 | |
| 8276 | // Normalize the second derivatives |
| 8277 | { |
| 8278 | const float second_derivatives_sum = std::accumulate(second_derivatives.begin(), second_derivatives.end(), 0.0f); |
| 8279 | |
| 8280 | if (second_derivatives_sum > 1e-6f) { |
| 8281 | for (float & value : second_derivatives) { |
| 8282 | value /= second_derivatives_sum; |
| 8283 | } |
| 8284 | } else { |
| 8285 | for (float & value : second_derivatives) { |
| 8286 | value = 1.0f / second_derivatives.size(); |
| 8287 | } |
| 8288 | } |
| 8289 | } |
| 8290 | |
| 8291 | float cum_sum = 0.0f; |
| 8292 | size_t last_idx = candidates->size; |
| 8293 | for (size_t i = 0; i < second_derivatives.size(); ++i) { |
| 8294 | cum_sum += second_derivatives[i]; |
| 8295 | |
| 8296 | // Check if the running sum is greater than z or if we have kept at least min_keep tokens |
| 8297 | if (cum_sum > z && i >= min_keep) { |
| 8298 | last_idx = i; |
| 8299 | break; |
| 8300 | } |
| 8301 | } |
| 8302 | |
| 8303 | // Resize the output vector to keep only the tokens above the tail location |
| 8304 | candidates->size = last_idx; |
| 8305 | |
| 8306 | if (ctx) { |
| 8307 | ctx->t_sample_us += ggml_time_us() - t_start_sample_us; |
| 8308 | } |
| 8309 | } |