sampling.cpp 16.6 KB
Newer Older
1
/**
2
 * llama.cpp - commit 3f1ae2e32cde00c39b96be6d01c2997c29bae555 - do not edit this file
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 *
 * MIT License
 *
 * Copyright (c) 2023-2024 The ggml authors
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

#include "sampling.h"

29
#include "common.h"
30

31
32
#include <cmath>
#include <unordered_map>
33

34
35
36
37
38
// the ring buffer works similarly to std::deque, but with a fixed capacity
// TODO: deduplicate with llama-impl.h
template<typename T>
struct ring_buffer {
    ring_buffer(size_t cap) : capacity(cap), data(cap) {}
39

40
41
42
    T & front() {
        if (sz == 0) {
            throw std::runtime_error("ring buffer is empty");
43
        }
44
45
        return data[first];
    }
46

47
48
49
    const T & front() const {
        if (sz == 0) {
            throw std::runtime_error("ring buffer is empty");
50
        }
51
52
        return data[first];
    }
53

54
55
56
    T & back() {
        if (sz == 0) {
            throw std::runtime_error("ring buffer is empty");
57
        }
58
        return data[pos];
59
60
    }

61
62
63
64
65
    const T & back() const {
        if (sz == 0) {
            throw std::runtime_error("ring buffer is empty");
        }
        return data[pos];
66
67
    }

68
69
70
71
72
73
74
75
76
    void push_back(const T & value) {
        if (sz == capacity) {
            // advance the start when buffer is full
            first = (first + 1) % capacity;
        } else {
            sz++;
        }
        data[pos] = value;
        pos = (pos + 1) % capacity;
77
78
    }

79
80
81
82
83
84
85
86
87
    T pop_front() {
        if (sz == 0) {
            throw std::runtime_error("ring buffer is empty");
        }
        T value = data[first];
        first = (first + 1) % capacity;
        sz--;
        return value;
    }
88

89
90
91
    const T & rat(size_t i) const {
        if (i >= sz) {
            throw std::runtime_error("ring buffer: index out of bounds");
92
        }
93
        return data[(first + sz - i - 1) % capacity];
94
95
    }

96
97
98
99
100
101
102
103
    std::vector<T> to_vector() const {
        std::vector<T> result;
        result.reserve(sz);
        for (size_t i = 0; i < sz; i++) {
            result.push_back(data[(first + i) % capacity]);
        }
        return result;
    }
104

105
106
107
108
109
    void clear() {
        // here only reset the status of the buffer
        sz = 0;
        first = 0;
        pos = 0;
110
111
    }

112
113
    bool empty() const {
        return sz == 0;
114
115
    }

116
117
    size_t size() const {
        return sz;
118
119
    }

120
121
122
123
124
125
    size_t capacity = 0;
    size_t sz = 0;
    size_t first = 0;
    size_t pos = 0;
    std::vector<T> data;
};
126

127
128
struct gpt_sampler {
    gpt_sampler_params params;
129

130
131
    struct llama_sampler * grmr;
    struct llama_sampler * chain;
132

133
    ring_buffer<llama_token> prev;
134

135
    std::vector<llama_token_data> cur;
136

137
    llama_token_data_array cur_p;
138

139
140
    void set_logits(struct llama_context * ctx, int idx) {
        const auto * logits = llama_get_logits_ith(ctx, idx);
141

142
143
144
145
146
147
148
149
150
151
152
153
154
        const int n_vocab = llama_n_vocab(llama_get_model(ctx));

        cur.resize(n_vocab);

        for (llama_token token_id = 0; token_id < n_vocab; token_id++) {
            cur[token_id] = llama_token_data{token_id, logits[token_id], 0.0f};
        }

        cur_p = { cur.data(), cur.size(), -1, false };
    }
};

std::string gpt_sampler_params::print() const {
155
156
157
158
159
160
    char result[1024];

    snprintf(result, sizeof(result),
            "\trepeat_last_n = %d, repeat_penalty = %.3f, frequency_penalty = %.3f, presence_penalty = %.3f\n"
            "\ttop_k = %d, tfs_z = %.3f, top_p = %.3f, min_p = %.3f, typical_p = %.3f, temp = %.3f\n"
            "\tmirostat = %d, mirostat_lr = %.3f, mirostat_ent = %.3f",
161
162
163
            penalty_last_n, penalty_repeat, penalty_freq, penalty_present,
            top_k, tfs_z, top_p, min_p, typ_p, temp,
            mirostat, mirostat_eta, mirostat_tau);
164
165
166
167

    return std::string(result);
}

168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
struct gpt_sampler * gpt_sampler_init(const struct llama_model * model, const struct gpt_sampler_params & params) {
    llama_sampler_chain_params lparams = llama_sampler_chain_default_params();

    lparams.no_perf = params.no_perf;

    auto * result = new gpt_sampler {
        /* .params = */ params,
        /* .grmr   = */ llama_sampler_init_grammar(model, params.grammar.c_str(), "root"),
        /* .chain  = */ llama_sampler_chain_init(lparams),
        /* .prev   = */ ring_buffer<llama_token>(std::max(32, params.n_prev)),
        /* .cur    = */ {},
        /* .cur_p  = */ {},
    };

    llama_sampler_chain_add(result->chain,
            llama_sampler_init_logit_bias(
                llama_n_vocab(model),
                params.logit_bias.size(),
                params.logit_bias.data()));

    llama_sampler_chain_add(result->chain,
            llama_sampler_init_penalties(
                llama_n_vocab  (model),
                llama_token_eos(model),
                llama_token_nl (model),
                params.penalty_last_n,
                params.penalty_repeat,
                params.penalty_freq,
                params.penalty_present,
                params.penalize_nl,
                params.ignore_eos));

    if (params.temp > 0.0f) {
        if (params.mirostat == 0) {
            for (const auto & cnstr : params.samplers) {
                switch (cnstr) {
                    case GPT_SAMPLER_TYPE_TOP_K:
                        llama_sampler_chain_add(result->chain, llama_sampler_init_top_k    (params.top_k));
                        break;
                    case GPT_SAMPLER_TYPE_TOP_P:
                        llama_sampler_chain_add(result->chain, llama_sampler_init_top_p    (params.top_p, params.min_keep));
                        break;
                    case GPT_SAMPLER_TYPE_MIN_P:
                        llama_sampler_chain_add(result->chain, llama_sampler_init_min_p    (params.min_p, params.min_keep));
                        break;
                    case GPT_SAMPLER_TYPE_TFS_Z:
                        llama_sampler_chain_add(result->chain, llama_sampler_init_tail_free(params.tfs_z, params.min_keep));
                        break;
                    case GPT_SAMPLER_TYPE_TYPICAL_P:
                        llama_sampler_chain_add(result->chain, llama_sampler_init_typical  (params.typ_p, params.min_keep));
                        break;
                    case GPT_SAMPLER_TYPE_TEMPERATURE:
                        llama_sampler_chain_add(result->chain, llama_sampler_init_temp_ext (params.temp, params.dynatemp_range, params.dynatemp_exponent));
                        break;
                    default:
                        GGML_ASSERT(false && "unknown sampler type");
                }
225
            }
226
227
228
229
230
231
232
233
234
235
            llama_sampler_chain_add(result->chain, llama_sampler_init_softmax());
            llama_sampler_chain_add(result->chain, llama_sampler_init_dist(params.seed));
        } else if (params.mirostat == 1) {
            llama_sampler_chain_add(result->chain, llama_sampler_init_temp(params.temp));
            llama_sampler_chain_add(result->chain, llama_sampler_init_mirostat(llama_n_vocab(model), params.seed, params.mirostat_tau, params.mirostat_eta, 100));
        } else if (params.mirostat == 2) {
            llama_sampler_chain_add(result->chain, llama_sampler_init_temp(params.temp));
            llama_sampler_chain_add(result->chain, llama_sampler_init_mirostat_v2(params.seed, params.mirostat_tau, params.mirostat_eta));
        } else {
            GGML_ASSERT(false && "unknown mirostat version");
236
237
        }
    } else {
238
239
240
241
242
243
244
245
246
247
        if (params.n_probs > 0) {
            // some use cases require to sample greedily, but still obtain the probabilities of the top tokens
            // ref: https://github.com/ggerganov/llama.cpp/pull/9605
            //
            // the following will not produce exactly the same probs as applyging softmax to the full vocabulary, but
            // it is much faster, since we avoid sorting all tokens and should give a good approximation
            llama_sampler_chain_add(result->chain, llama_sampler_init_top_k(params.n_probs));
            llama_sampler_chain_add(result->chain, llama_sampler_init_softmax());
        }
        llama_sampler_chain_add(result->chain, llama_sampler_init_greedy());
248
249
250
251
252
    }

    return result;
}

253
254
255
256
257
258
259
void gpt_sampler_free(struct gpt_sampler * gsmpl) {
    if (gsmpl) {
        llama_sampler_free(gsmpl->grmr);

        llama_sampler_free(gsmpl->chain);

        delete gsmpl;
260
261
262
    }
}

263
264
265
266
void gpt_sampler_accept(struct gpt_sampler * gsmpl, llama_token token, bool accept_grammar) {
    if (accept_grammar) {
        llama_sampler_accept(gsmpl->grmr, token);
    }
267

268
    llama_sampler_accept(gsmpl->chain, token);
269

270
    gsmpl->prev.push_back(token);
271
272
}

273
274
void gpt_sampler_reset(struct gpt_sampler * gsmpl) {
    llama_sampler_reset(gsmpl->grmr);
275

276
    llama_sampler_reset(gsmpl->chain);
277
278
}

279
280
281
282
283
284
285
286
287
struct gpt_sampler * gpt_sampler_clone(gpt_sampler * gsmpl) {
    return new gpt_sampler {
        /* .params = */ gsmpl->params,
        /* .grmr   = */ llama_sampler_clone(gsmpl->grmr),
        /* .chain  = */ llama_sampler_clone(gsmpl->chain),
        /* .prev   = */ gsmpl->prev,
        /* .cur    = */ gsmpl->cur,
        /* .cur_p  = */ gsmpl->cur_p,
    };
288
289
}

290
291
void gpt_perf_print(const struct llama_context * ctx, const struct gpt_sampler * gsmpl) {
    // TODO: measure grammar performance
292

293
294
295
296
297
298
299
    if (gsmpl) {
        llama_perf_sampler_print(gsmpl->chain);
    }
    if (ctx) {
        llama_perf_context_print(ctx);
    }
}
300

301
302
llama_token gpt_sampler_sample(struct gpt_sampler * gsmpl, struct llama_context * ctx, int idx, bool grammar_first) {
    gsmpl->set_logits(ctx, idx);
303

304
305
306
    auto & grmr  = gsmpl->grmr;
    auto & chain = gsmpl->chain;
    auto & cur_p = gsmpl->cur_p; // initialized by set_logits
307

308
309
    if (grammar_first) {
        llama_sampler_apply(grmr, &cur_p);
310
311
    }

312
    llama_sampler_apply(chain, &cur_p);
313

314
    GGML_ASSERT(cur_p.selected != -1 && "no selected token during sampling - check your sampling configuration");
315

316
    const llama_token id = cur_p.data[cur_p.selected].id;
317

318
319
320
    if (grammar_first) {
        return id;
    }
321

322
323
324
325
    // check if it the sampled token fits the grammar
    {
        llama_token_data       single_token_data       = { id, 1.0f, 0.0f };
        llama_token_data_array single_token_data_array = { &single_token_data, 1, -1, false };
326

327
        llama_sampler_apply(grmr, &single_token_data_array);
328

329
330
331
        const bool is_valid = single_token_data_array.data[0].logit != -INFINITY;
        if (is_valid) {
            return id;
332
333
334
        }
    }

335
336
337
    // resampling:
    // if the token is not valid, sample again, but first apply the grammar sampler and then the sampling chain
    gsmpl->set_logits(ctx, idx);
338

339
340
    llama_sampler_apply(grmr,  &cur_p);
    llama_sampler_apply(chain, &cur_p);
341

342
    GGML_ASSERT(cur_p.selected != -1 && "no selected token during re-sampling - check your sampling configuration");
343

344
345
    return cur_p.data[cur_p.selected].id;
}
346

347
348
349
350
351
uint32_t gpt_sampler_get_seed(const struct gpt_sampler * gsmpl) {
    return llama_sampler_get_seed(gsmpl->chain);
}

// helpers
352

353
354
355
llama_token_data_array * gpt_sampler_get_candidates(struct gpt_sampler * gsmpl) {
    return &gsmpl->cur_p;
}
356

357
358
359
llama_token gpt_sampler_last(const struct gpt_sampler * gsmpl) {
    return gsmpl->prev.rat(0);
}
360

361
362
std::string gpt_sampler_print(const struct gpt_sampler * gsmpl) {
    std::string result = "logits ";
363

364
365
366
    for (int i = 0; i < llama_sampler_chain_n(gsmpl->chain); i++) {
        const auto * smpl = llama_sampler_chain_get(gsmpl->chain, i);
        result += std::string("-> ") + llama_sampler_name(smpl) + " ";
367
368
    }

369
370
371
372
373
374
375
376
    return result;
}

std::string gpt_sampler_prev_str(gpt_sampler * gsmpl, llama_context * ctx_main, int n) {
    n = std::min(n, (int) gsmpl->prev.size());

    if (n <= 0) {
        return "";
377
378
    }

379
380
381
382
383
384
385
386
387
    std::string result;
    result.reserve(8*n); // 8 is the average length of a token [citation needed], TODO: compute this from the vocab

    for (int i = n - 1; i >= 0; i--) {
        const llama_token id = gsmpl->prev.rat(i);

        GGML_ASSERT(id != LLAMA_TOKEN_NULL && "null token in the sampling history - should not happen");

        result += llama_token_to_piece(ctx_main, id);
388
389
    }

390
391
392
393
394
395
396
397
398
399
400
401
402
403
    return result;
}

char gpt_sampler_type_to_chr(enum gpt_sampler_type cnstr) {
    switch (cnstr) {
        case GPT_SAMPLER_TYPE_TOP_K:       return 'k';
        case GPT_SAMPLER_TYPE_TFS_Z:       return 'f';
        case GPT_SAMPLER_TYPE_TYPICAL_P:   return 'y';
        case GPT_SAMPLER_TYPE_TOP_P:       return 'p';
        case GPT_SAMPLER_TYPE_MIN_P:       return 'm';
        case GPT_SAMPLER_TYPE_TEMPERATURE: return 't';
        default : return '?';
    }
}
404

405
406
407
408
409
410
411
412
413
std::string gpt_sampler_type_to_str(enum gpt_sampler_type cnstr) {
    switch (cnstr) {
        case GPT_SAMPLER_TYPE_TOP_K:       return "top_k";
        case GPT_SAMPLER_TYPE_TFS_Z:       return "tfs_z";
        case GPT_SAMPLER_TYPE_TYPICAL_P:   return "typ_p";
        case GPT_SAMPLER_TYPE_TOP_P:       return "top_p";
        case GPT_SAMPLER_TYPE_MIN_P:       return "min_p";
        case GPT_SAMPLER_TYPE_TEMPERATURE: return "temperature";
        default : return "";
414
    }
415
}
416

417
418
419
420
421
422
423
424
425
std::vector<gpt_sampler_type> gpt_sampler_types_from_names(const std::vector<std::string> & names, bool allow_alt_names) {
    std::unordered_map<std::string, gpt_sampler_type> sampler_canonical_name_map {
        { "top_k",       GPT_SAMPLER_TYPE_TOP_K },
        { "top_p",       GPT_SAMPLER_TYPE_TOP_P },
        { "typ_p",       GPT_SAMPLER_TYPE_TYPICAL_P },
        { "min_p",       GPT_SAMPLER_TYPE_MIN_P },
        { "tfs_z",       GPT_SAMPLER_TYPE_TFS_Z },
        { "temperature", GPT_SAMPLER_TYPE_TEMPERATURE },
    };
426

427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
    // since samplers names are written multiple ways
    // make it ready for both system names and input names
    std::unordered_map<std::string, gpt_sampler_type> sampler_alt_name_map {
        { "top-k",       GPT_SAMPLER_TYPE_TOP_K },
        { "top-p",       GPT_SAMPLER_TYPE_TOP_P },
        { "nucleus",     GPT_SAMPLER_TYPE_TOP_P },
        { "typical-p",   GPT_SAMPLER_TYPE_TYPICAL_P },
        { "typical",     GPT_SAMPLER_TYPE_TYPICAL_P },
        { "typ-p",       GPT_SAMPLER_TYPE_TYPICAL_P },
        { "typ",         GPT_SAMPLER_TYPE_TYPICAL_P },
        { "min-p",       GPT_SAMPLER_TYPE_MIN_P },
        { "tfs-z",       GPT_SAMPLER_TYPE_TFS_Z },
        { "tfs",         GPT_SAMPLER_TYPE_TFS_Z },
        { "temp",        GPT_SAMPLER_TYPE_TEMPERATURE },
    };
442

443
444
    std::vector<gpt_sampler_type> samplers;
    samplers.reserve(names.size());
445

446
447
448
449
450
451
452
453
454
    for (const auto & name : names) {
        auto sampler = sampler_canonical_name_map.find(name);
        if (sampler != sampler_canonical_name_map.end()) {
            samplers.push_back(sampler->second);
        } else {
            if (allow_alt_names) {
                sampler = sampler_alt_name_map.find(name);
                if (sampler != sampler_alt_name_map.end()) {
                    samplers.push_back(sampler->second);
455
456
457
458
459
                }
            }
        }
    }

460
    return samplers;
461
462
}

463
464
465
466
467
468
469
470
471
std::vector<gpt_sampler_type> gpt_sampler_types_from_chars(const std::string & chars) {
    std::unordered_map<char, gpt_sampler_type> sampler_name_map = {
        { gpt_sampler_type_to_chr(GPT_SAMPLER_TYPE_TOP_K),       GPT_SAMPLER_TYPE_TOP_K },
        { gpt_sampler_type_to_chr(GPT_SAMPLER_TYPE_TFS_Z),       GPT_SAMPLER_TYPE_TFS_Z },
        { gpt_sampler_type_to_chr(GPT_SAMPLER_TYPE_TYPICAL_P),   GPT_SAMPLER_TYPE_TYPICAL_P },
        { gpt_sampler_type_to_chr(GPT_SAMPLER_TYPE_TOP_P),       GPT_SAMPLER_TYPE_TOP_P },
        { gpt_sampler_type_to_chr(GPT_SAMPLER_TYPE_MIN_P),       GPT_SAMPLER_TYPE_MIN_P },
        { gpt_sampler_type_to_chr(GPT_SAMPLER_TYPE_TEMPERATURE), GPT_SAMPLER_TYPE_TEMPERATURE }
    };
472

473
474
    std::vector<gpt_sampler_type> samplers;
    samplers.reserve(chars.size());
475

476
477
478
479
480
    for (const auto & c : chars) {
        const auto sampler = sampler_name_map.find(c);
        if (sampler != sampler_name_map.end()) {
            samplers.push_back(sampler->second);
        }
481
    }
482
483

    return samplers;
484
}