Keep the Useful Candidates Without Losing Their IDs

Keeping the Current Best Candidate Close

BOTIE

Selecting the next best item was an algorithm problem long before a retrieval system had thousands of passages to rank. J. W. J. Williams’ 1964 Heapsort algorithm described a heap: an array organised so an extreme item stays at its root. In his formulation the least item is immediately available, and insertion or extraction repairs the ordering without sorting the entire collection again.

That idea also helps a bounded shortlist. Keep only the best k candidates, with the weakest retained candidate easiest to inspect. A better arrival can replace it. Our workshop uses sorting to show which positions win; the Python challenge builds the bounded heap. Both must preserve passage IDs and the declared tie rule. Efficient selection does not decide whether the retrieval scores identify useful evidence.

Sources for this history

Botie Can Read Five Passages. We Found Fifty Thousand.

A retrieval system assigns scores to passages. Passing every passage to an agent would consume its context and bury the useful evidence. We need a shortlist, and we still need to know which document produced each score.

Sorting is a useful first implementation. When the candidate collection is large, we need not sort every candidate to retain a small shortlist. Keep the current shortlist with its weakest member easy to find. A new candidate replaces that member only if it ranks better. A heap is a data structure that supports this repeated comparison efficiently. Both implementations must agree on what happens at a tie.

This checks selection, not relevance or permission to read the passages.

Step 1 of 1

Scores need their passage identities

Equal scores retain incoming order in this lesson.

For two places, B comes before C. A stable tie rule makes runs comparable.
Passage	Score	Position
manual-A	0.8	0
manual-B	0.9	1
manual-C	0.9	2

manual-A
Score
0.8
Position
0
manual-B
Score
0.9
Position
1
manual-C
Score
0.9
Position
2

For two places, B comes before C. A stable tie rule makes runs comparable.

Keep a candidate together

The score ordering becomes positions that select evidence identities.

Send the agent the right passage IDs

Botie needs the highest scoring passages with their identities intact.

BOTIE

Botie needs the highest scoring passages with their identities intact.

Choose an example

Passage IDs

1

2

3

Retrieval scores

1

2

3

Available context slots

Passage IDs in score order

0B
1A

Follow the operations

1. Passage IDs
1. 0A
2. 1B
3. 2C
2. Retrieval scores
1. 00.8
2. 10.9
3. 20.3
3. Available context slots
```
2
```
4. Rank candidate positions
1. 01
2. 10
5. Gather selected entries
1. 0B
2. 1A
6. Result
1. 0B
2. 1A

This checks selection, not relevance or permission to read the passages.

1. Keep a candidate together

Store a candidate as an identity plus a score and original position. An identity names the evidence; position resolves equal scores. Sorting only the score list throws away the mapping back to text.

The workshop first returns ranked positions. Gather uses those positions to select IDs from the original list.

Keep later permission filters attached to the same records. A highly ranked passage may still be inaccessible to this user.

2. Define the shortlist before choosing a structure

Select descending scores, retaining original order at equal scores. Clamp the requested length naturally to the number of available candidates. A request for zero results returns an empty list.

scores = [0.8, 0.9, 0.9]
ranked positions = [1, 2, 0]
first two IDs = [manual-B, manual-C]

The workshop ranking tool uses sorting for inspectability. The coding challenge uses a heap to express the same selection rule.

An index keeps the evidence attached

Pair an original position with each score before ordering.

Python

scores = [.8,.9,.9]
ranked = sorted(enumerate(scores), key=lambda pair: -pair[1])
print(ranked)

Output

[(1, 0.9), (2, 0.9), (0, 0.8)]

Each tuple contains a position and its score. Python’s stable sort retains input order for the tie.

Check yourself

Which identities survive the ranking?

Question 1 of 2

Which shortlist is correct?

Use the information below.

IDs [A,B,C], scores [0.8,0.9,0.9], k=2. Ties keep input order.

3. Why keep the weakest retained item at the root?

Once the shortlist is full, a new candidate matters only if it outranks the weakest retained one. Comparing with that root avoids sorting every retained candidate on every arrival. Store score and negative original position in the heap so a later equal score is the weaker tie.

For n candidates and shortlist k, a bounded heap uses O(k) auxiliary storage and O(n log k) selection work for k greater than one. Sorting the final k items adds O(k log k).

For small lists, a full sort may be simpler and faster in practice. Measure with realistic workloads instead of treating asymptotic notation as a timing result.

4. Test the uninteresting-looking ties

Distinct random scores miss identity and tie bugs. Include equal scores, negative scores, an empty list, and a shortlist longer than the input.

Ranking quality is a separate evaluation: an efficient shortlist can still contain irrelevant passages. Inspect relevance and answer support after testing selection correctness.

A retrieval agent also needs document permissions and citation preservation beyond this data-structure exercise.