Check cited sources

Learn it

Words to know

citation

A reference from an answer to the source document it is based on, usually by id.

grounding

Tying each claim in an answer to a source the model was given, so that the claim can be checked.

hallucination

Something a model states with confidence that is not in its sources or is not true, such as an invented source id.

How it works

1. Put the retrieved ids in a set, so that looking one up is fast.
2. Go through the citations in order.
3. A citation that is not in the set is unknown. Report it once, the first time it appears.

Worked example

Input
citations = ["a", "x", "x", "y"]
retrievedIds = ["a", "b"]

Output
["x", "y"]

The answer cites two ids that were never retrieved. x is cited twice and reported once, and the order of first appearance is kept.

Why it matters

The first portfolio project returns source ids with every answer. This check is its first line of defence. Grounding, which is checking that the source really supports the claim, comes after it.

Your turn

Find the citations in an answer that do not point at any retrieved document.

citations

the source ids the answer cites, in order; an id can appear more than once

retrievedIds

the ids of the documents that were retrieved for this request

Returns

The cited ids that were not retrieved, each one once, in the order they first appear. If every citation is known, or there are none, an empty list.

Input
citations = ["a", "x", "x", "y"]
retrievedIds = ["a", "b"]

Output
["x", "y"]

Input
citations = ["a"]
retrievedIds = ["a"]

Output
[]

Input
citations = ["b", "a", "b"]
retrievedIds = []

Output
["b", "a"]

The checks also try

• no citations at all
• unknown ids out of alphabetical order
• repeats on both sides
• an id that differs only by a capital letter
• many unknown ids with longer names
• an id that is also a built-in name

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Where to start

   You need two memories: the ids that were retrieved, and the unknown ids you have already reported.

2. Hint 2: The key step

   Walk the citations in order. An id goes into the result only if it was not retrieved and you have not added it before.

3. Hint 3: The outline

   Make a set known from retrievedIds, an empty set reported, and an empty list unknown. For each citation: if it is not in known and not in reported, add it to unknown and to reported. Return unknown.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Step by step

1. The ids that were retrieved for this request. A set answers whether an id is in it with one fast check, however many documents were retrieved.
2. An id that was not retrieved and not reported yet. The second set remembers what is already in the result, so an id cited three times is still reported once.
3. Report it, in the order it first appeared. Walking the citations in order and adding at the end keeps first-appearance order, so the output is the same on every run.

The same numbered steps are the comments in the solution.

function solve(citations, retrievedIds) {
  // 1. The ids that were retrieved for this request
  const known = new Set(retrievedIds);
  const reported = new Set();
  const unknown = [];
  for (const cited of citations) {
    // 2. An id that was not retrieved and not reported yet
    if (!known.has(cited) && !reported.has(cited)) {
      // 3. Report it, in the order it first appeared
      unknown.push(cited);
      reported.add(cited);
    }
  }
  return unknown;
}

def solve(citations, retrievedIds):
    # 1. The ids that were retrieved for this request
    known = set(retrievedIds)
    reported = set()
    unknown = []
    for cited in citations:
        # 2. An id that was not retrieved and not reported yet
        if cited not in known and cited not in reported:
            # 3. Report it, in the order it first appeared
            unknown.append(cited)
            reported.add(cited)
    return unknown

Watch out

• An empty result is not a pass mark for the answer. It says every cited id was retrieved, not that any cited document supports what the answer claims.
• Keep the order of first appearance. Sorting the result changes that order.
• In JavaScript: Use a Set, not a plain object: known["constructor"] is found on an empty object. A Set also keeps the order items were added in, so [...new Set(citations)] drops repeats and keeps first appearance.
• In Python: In Python set(citations) - set(retrievedIds) finds the right ids, but a set has no fixed order. Walk the list instead.

Check yourself