Knowledge Stores and Memory for Language Models

A unit on the stores of knowledge a language model can draw on besides passages of text. Entities and the links from text to them, knowledge graphs and how they are queried, ranking entities instead of documents, embeddings that predict missing facts, the model's own weights as an index of documents, and, as reading notes for now, the memory that agents write for themselves. Each article says what it proves, what it cites and what its experiment measured, mostly on this site's own pages read as a knowledge graph.

A language model answers from three kinds of store. The first is outside it and structured: a set of entities with the facts that join them, such as a knowledge graph. The second is the model itself. Its weights hold facts learned in training, and a model can even be trained to act as the index of a collection, producing a document's identifier for a query. The third is written by the model while it works: notes, summaries and observations that an agent keeps from one task or one conversation to the next and reads back later. The earlier units of this collection treated the store as a heap of passages to be ranked. This unit is about stores with more structure, and about what changes when the model does the storing.

The unit moves along that line. It starts with entities: how a mention in text is tied to the entity it names, and what a knowledge graph of such entities is, how it is queried and how its gaps are measured. It then ranks entities rather than documents for a query, and learns vectors for a graph's entities and relations that predict the facts it is missing. Next comes the model as the index. The unit ends with memory written by agents, which this collection records for now as reading notes on the published systems; a reference article on it will follow from the owner's own design work on agent memory.

What the unit assumes

The course's units on retrieval evaluation (in particular ranked retrieval evaluation and its mean reciprocal rank) and on link analysis (PageRank and HITS). From this collection, Text Embeddings and Dense Retrieval for encoders and contrastive training, Similarity Measures for Embeddings, and Retrieval-Augmented Generation for what happens when the reader is a language model. Sets and relations are used throughout; finite automata are defined where they are used, in Knowledge Graphs; the complexity arguments need the definitions of NP and of a polynomial-time reduction.

What is proved, cited and measured

Derived or proved on the pages: the costs of evaluating basic graph patterns (checking a solution is polynomial, deciding whether one exists is NP-complete), the homomorphism theorem for containment of conjunctive queries, and the product construction that evaluates regular path queries in time linear in the graph for a fixed expression; TransE's loss and gradient and the theorem that exact translation collapses symmetric and one-to-many relations, DistMult's symmetry, and the theorem that every real square matrix is the real part of a normal matrix, which underlies ComplEx; the expected reciprocal rank under random tie-breaking; and the condition under which a link-based relatedness measure between entities is positive. Each article lists its own proofs and citations. Cited and not proved: every published measurement, the spectral theorem, the NP-completeness of the clique problem, and the results each article names as cited.

The test bed for most of the unit is this site itself. Its 850 pages at one fixed commit of the source, before this unit was written, form a knowledge graph of 10,105 entities and 39,157 triples. Pages link to pages, belong to topics and carry tags; they cite works, and works have authors. The [[links]] in the pages' text serve as gold annotations of mentions and the entities they name, as Wikipedia's links served the early work on entity linking. The loader is tools/experiments/knowledge-stores/sitegraph.py. Public benchmarks are used where the site is too small or too unlike the literature's data: WN18RR for link prediction and DBpedia-Entity v2 for entity search, each pinned by revision or hash. Seeded experiments follow the site's convention of 30 runs, reported as a median with quartiles, and runs too long for a laptop processor are scaled down, with the scale stated on the page.

Notation

A knowledge graph $G$ is a finite set of triples $(h, r, t)$: a head entity $h$, a relation $r$ and a tail entity $t$, with $h, t \in \mathcal{E}$ and $r \in \mathcal{R}$, and $n_e = |\mathcal{E}|$, $n_r = |\mathcal{R}|$. RDF's terms subject, predicate and object are used only when speaking of RDF. An entity is a node of the graph; a mention $m$ is a span of text that refers to one, with candidate set $C(m)$ and linked entity $e$. Embeddings are vectors $\vec{h}, \vec{r}, \vec{t} \in \mathbb{R}^d$ (or $\mathbb{C}^d$), and a score $f(h, r, t)$ is higher for a more plausible triple. Queries and documents are $q$ and $d$, as in the course.

Entities and graphs

  • Entity Linking: mapping each phrase that names something to its entry in a knowledge base, or to NIL; mention detection, candidates ranked by commonness, a relatedness measure computed from shared in-links with a proof of when it is positive, dense entity retrieval with BLINK, and evaluation, measured on this site with its own links as gold annotations.
  • Knowledge Graphs: the data model (triples, RDF, property graphs, schema in outline); basic graph patterns as conjunctive queries, with what evaluating them costs and when two are equivalent; regular path queries by the product construction; the open- and closed-world assumptions; how completeness is estimated, with a sample of the site's unlinked title mentions judged by a language model; and retrieval from a graph for a language model by subgraphs and verbalized triples.
  • Entity-Oriented Search: answering a query with entities instead of documents; entity descriptions as fielded documents ranked by BM25F, the mixture of language models, PRMS and the fielded sequential dependence model (with its reductions proved), target types and graph links, and entities used to retrieve documents; measured on DBpedia-Entity v2 over all 4.6 million entities.
  • Knowledge Graph Embeddings: TransE derived in full with the relations a translation cannot represent, DistMult and its symmetry, ComplEx and its expressiveness, RotatE in outline; filtered and tie-aware MRR and Hits@k, and the test leakage that produced FB15k-237 and WN18RR; TransE and DistMult trained over 30 seeds on WN18RR and on the site graph.

The model as the index

  • Generative Retrieval: The Model as the Index: a sequence-to-sequence model trained to produce the identifier of the relevant document, so that the model's parameters are the index; the three kinds of document identifier, constrained decoding with a prefix trie and beam search, indexing with generated queries, and GENRE; a small DSI trained on Cranfield with each kind of identifier and compared with BM25 and a dense retriever.

Memory written by agents

  • Memory for Language-Model Agents: what an agent should write, when it should retrieve, and how recency and importance enter the score. This article will be written later, from the owner's design work on agent memory; until then the reading notes below describe the published systems and benchmarks.

Reading notes on knowledge stores and agent memory

Notes on single papers, in the library's reading-note form: each summarizes the paper in our own words and reports its results as the paper's.

How models and agents store knowledge:

How such memory is evaluated:

This unit closes the collection's present sequence. The planned unit on queries and conversations will take up how a question is rewritten and when retrieval should happen at all.