Pick few-shot examples within a word budget

A prompt must fit the context window, so a program often chooses which examples to include.

What to build

A program that ranks few-shot examples by how many query words they share and keeps as many as fit a word budget.

Requirements

  • The fixed cost is the word count of the instruction plus the word count of the line Input: QUERY Label:.
  • An example costs the word count of the line Input: X Label: Y.
  • Rank the examples by the number of different lower-case words that their input X shares with the query, highest first, lower number first on a tie.
  • Go through the ranking and keep an example if the total stays at most the budget; otherwise skip it and go on.
  • Print ranked: and all example numbers (from 1) in rank order, used: and the kept numbers in rank order (or none), and words: and the final total.

Input

Line 1: the budget. Line 2: the instruction. Line 3: n. Then n lines of the form X => Y. The last line is the query.

Output

Three lines.

Constraints

1 ≤ n ≤ 20. The fixed cost may already be larger than the budget; then nothing is kept.

Example

Input:

25
Label the review.
3
great phone => positive
it broke after two days => negative
phone works well => positive
does the phone work well

Output:

ranked: 3, 1, 2
used: 3, 1
words: 21

Why it works

Examples that share words with the query are the most useful, and the greedy pass spends the limited budget on them first while still letting small examples fill the gaps.

Examples

Example 1 · Input
25
Label the review.
3
great phone => positive
it broke after two days => negative
phone works well => positive
does the phone work well
Expected output
ranked: 3, 1, 2
used: 3, 1
words: 21
Example 2 · Input
14
Answer.
2
a b => c
a => b
a
Expected output
ranked: 1, 2
used: 1, 2
words: 13

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Score an example by the number of different lower-case words its input shares with the query.

Hint 2

Sort by score from high to low, lower index first on a tie, then take examples in that order while the total still fits the budget.

Hint 3

An example that does not fit is skipped, but later (smaller) ones may still fit.

Solution

Show one correct solution (try it yourself first)
budget = int(input())
instruction = input()
n = int(input())
examples = []
for _ in range(n):
    x, y = input().split(" => ")
    examples.append((x, y))
query = input()
q = set(query.lower().split())
score = [len(q & set(x.lower().split())) for x, _ in examples]
order = sorted(range(n), key=lambda i: (-score[i], i))
total = len(instruction.split()) + len(f"Input: {query} Label:".split())
used = []
for i in order:
    x, y = examples[i]
    cost = len(f"Input: {x} Label: {y}".split())
    if total + cost <= budget:
        used.append(i)
        total += cost
print("ranked: " + ", ".join(str(i + 1) for i in order))
print("used: " + (", ".join(str(i + 1) for i in used) if used else "none"))
print(f"words: {total}")

Lesson: Prompt engineering →