Before you start: review of the earlier sessions
The thread so far. Session 16 connected graphs to LLMs; session 17 makes the LLM an active agent over the graph. The course then returns to graphs as outputs in session 18.
What this session takes from earlier ones
- Lecture 16: graph retrieval for LLMs, which the agent here calls as a tool
- Lecture 11: the BPR loss: the reward model of RLHF has exactly the same pairwise form
- Lecture 10: knowledge graphs as semi-structured knowledge bases
Those sessions in one minute each
Use each model for what it is good at: GNNs for precise, multi-hop composition over structured facts, LLMs for language understanding and generation — connected either by injecting a GNN's subgraph embedding into the LLM (GraphRAG) or by using an LM to featurise a text-attributed graph for a GNN.
Lecture 11 · GNNs for Recommender Systems
Collaborative filtering is diffusion on the user–item graph: LightGCN keeps only learnable embeddings and parameter-free normalised propagation, and a personalised ranking loss (BPR) aligns training with per-user Recall@K.
Lecture 10 · Knowledge Graph Embeddings
A KG embedding turns each relation into a geometric operation; the algebra of that operation (commutative or not, invertible or not, composable or not) decides which logical patterns of relations the model can represent.
Warm-up: answer these before you read on
What is the hallucination argument for retrieval? from Lecture 16
An LLM answers from associative memory; grounding it in retrieved facts constrains the answer to what the KG actually contains.
Why does PinSage sample neighbours by random walks rather than uniformly? from Lecture 11
Random walks rank neighbours by importance, so a fixed budget of neighbours captures the most relevant ones for a hub pin.
What does "1-to-N" mean and which models handle it? from Lecture 10
One head and relation with many true tails (a person's students); TransE collapses all tails to one point, TransR and DistMult can keep them apart.
Why inject a GNN embedding instead of pasting the subgraph as text? from Lecture 16
Text serialisation is long, order-dependent and loses structure; a GNN embedding is compact, permutation invariant and can be trained end-to-end with the LLM.
More questions from every session you have reached, with spaced repetition: the cumulative review.
In short
Guest lecture by Shirley Wu (Stanford). Part 1 recaps how LLMs are made: pretraining (next-token prediction on huge text), instruction fine-tuning (follow instructions), and RLHF (learn a reward model from human preference pairs, then optimise the LLM against it). Notice that the reward model's loss is the same pairwise form as BPR from Lecture 11.
Part 2: real queries ("a push-along tricycle from Radio Flyer that is both fun and safe for my kids") need multi-hop reasoning, filtering and synthesis over semi-structured knowledge bases — text documents attached to a knowledge graph. The STaRK benchmark shows every retrieval method gets Hit@1 below 18%. LLM agents (ReAct) use tools badly. AvaTaR optimises the agent's tool-use instructions automatically with contrastive reasoning: a comparator LLM studies which queries the agent got right vs wrong and writes better instructions — +20% to +57% Hit@1.
Part 3: LLMs are trained on single-turn rewards, so they jump to answers instead of asking clarifying questions. CollabLLM (ICML 2025 outstanding paper) rewards each response by its long-term effect on the conversation, estimated by simulating future turns with an LLM user simulator — better documents, better user experience, >10% time saved in a 201-person study.
The picture: AvaTaR's optimisation loop
How to read it (hover a step)
- Start from a small training set of queries with known answers (e.g. from STaRK).
- The actor agent writes action sequences that call tools (embedding similarity, token matching, attribute parsing, LLM-based verification) over the knowledge base.
- Split queries into those answered well and badly — positive and negative groups.
- A comparator LLM contrasts the groups ("you do well on simple product features but fail on nuanced descriptions…") and writes improved instructions that update the actor's prompt. Repeat.
1 · How LLMs are trained: pretraining → instruction tuning → RLHF
Pretraining
Predict the next token on huge, diverse text. It learns trivia ("Stanford University is located in ___, California"), syntax, coreference, lexical semantics, sentiment… But language modelling ≠ assisting users: asked to "explain the moon landing to a 6-year-old", GPT-3 continues the pattern with more prompts. Models aren't aligned with user intent.
Instruction fine-tuning
Collect (instruction, output) pairs across many tasks and fine-tune; evaluate on unseen tasks. Limitations: open-ended tasks have no single right answer; token-level loss penalises all mistakes equally, though some errors are much worse than others.
RLHF: optimise for human preferences
Imagine a reward \(R(x,y)\) for each sample (e.g. summary quality): maximise \(\mathbb{E}_{\hat y\sim p_\theta(y|x)}[R(x,\hat y)]\) with policy-gradient RL (PPO; Schulman et al. 2017). Humans are bad at absolute scores but good at comparisons, so train a reward model from preference pairs (winning sample \(s^w\), losing \(s^l\)):
\[ J_{RM}(\phi)=-\mathbb{E}_{(s^w,s^l)\sim D}\big[\log\sigma\big(RM_\phi(s^w)-RM_\phi(s^l)\big)\big] \]Then optimise the instruction-tuned LM against \(RM_\phi\) (with a KL penalty to stay near the original). RLHF gives gains beyond pretraining + fine-tuning at every model size (InstructGPT).
\(-\log\sigma(RM(s^w)-RM(s^l))\) is the BPR loss from Lecture 11 (\(-\log\sigma(f(u,v^+)-f(u,v^-))\)) — the Bradley–Terry model of pairwise preferences. Recommending items and aligning LLMs share the same mathematics of ranking.
2 · STaRK: retrieval over semi-structured knowledge bases
Real queries are knowledge-intensive and mix textual requirements ("fun and safe") with relational ones ("from Radio Flyer", "also bought with…"). A semi-structured knowledge base (SKB) combines a KG (brand, category, also-viewed, also-bought edges) with rich text on each node (title, features, description). LLM agents must (1) navigate large SKBs, (2) find useful information, (3) reason and aggregate answers.
STaRK (NeurIPS 2024 D&B): three SKBs (Amazon products, MAG academic, PrimeKG biomedical) with large synthesised Q&A pairs plus small human-written sets. Result: retrieval-augmented methods and LLM rerankers are poor — Hit@1 below 18% on STaRK-Prime for all methods (QAGNN 7.1, ada-002 15.4, Claude-3 reranker 17.8).
3 · AvaTaR: optimising tool use with contrastive reasoning
Insight: LLMs must use external tools (retrieval over KGs and text, embedding systems, processing, visualisation). But they use tools poorly. A ReAct agent on "TUSA swim fins with a split-fin design": computes embedding similarity on "swim fins" (ignoring the brand), then exact string matching on the feature (all zeros — no perfect match), multiplies the scores → all zeros → trivial answer.
The optimised AvaTaR agent: parses the query into attributes (brand, type, material, features); filters by type similarity (top-20); uses token matching for flexible brand matching; asks an LLM to verify the functional requirement; combines scores with optimised weights (0.43, 0.37, 0.20) → excellent performance.
How the instructions are found — contrastive reasoning. Analogy: a student gets all additions right and all multiplications wrong → "practise multiplication". The comparator LLM is prompted with "here are queries the agent performs poorly and well on; understand their differences", and outputs actionable instructions. Results on STaRK Hit@1: +28% (Amazon), +57% (MAG), +20% (Prime) over the best baseline among vector search, ReAct and Reflexion.
4 · CollabLLM: rewarding long-term collaboration
Human–LLM interaction is everywhere (writing, coding, maths, science). Yet LLMs jump to conclusions: "What's a good pasta recipe?" → a chicken-broth recipe for a vegetarian (wasted tokens); "My muscles feel weak" → a list of six diagnoses (useless). They act as passive responders under ambiguity.
Why? RLHF uses single-turn preferences: for "I need to write an article about optimism", a full article scores higher than a clarifying question in a single turn — even if the question would produce a much better article two turns later.
- A candidate model response at the current turn — e.g. a clarifying question instead of a full draft.
- Sample several synthetic future conversations: an LLM user simulator (given the task, a persona and the context) replies; the model continues.
- Score each simulated conversation (task quality, token efficiency, interactivity) and average → the multiturn-aware reward, a causal estimate of the response's long-term effect. Then fine-tune with DPO/PPO on these rewards.
Evaluation on new multi-turn benchmarks (MediumDocEdit-Chat, BigCodeBench-Chat, Math-Chat) with Llama-3.1-8B: vs Base and "Proactive Base" (prompted to ask questions), CollabLLM improves task performance by 18%, efficiency by 13% and interactivity by 46% on average. A study with 201 people: higher document quality and interaction ratings, >10% less time; ratings improve over turns while the base model degrades. On Abg-CoQA it asks ~3× more questions on ambiguous queries but only 18% more on unambiguous ones — it learns when to ask.
The mathematics, step by step
The formulas of this session are all objectives: what a language model is trained to maximise at each stage of its life, and what replaces that objective when the model has to act as an agent over several turns. Read each one as an answer to 'what counts as good here?'.
Symbols used in this session
| symbol | meaning | what kind of object |
|---|---|---|
| \(w_t\) | the \(t\)-th token of a text | an element of the vocabulary |
| \(p_\theta,\ \pi_\theta\) | the model with parameters \(\theta\): a probability distribution over the next token, or over whole responses | probability distribution |
| \(x,\ y\) | a prompt and a response | texts |
| \(R(x,y)\) | reward: a number saying how good the response is | real number |
| \(RM_\phi(s)\) | reward model with parameters \(\phi\): predicts a score for a response \(s\) | real number |
| \((s^w,s^l)\) | a pair of responses where a human preferred the first (winner) over the second (loser) | pair of texts |
| \(c_t,\ y_t,\ u_{t+1}\) | conversation so far at turn \(t\), the model's reply, the user's next message | texts |
| \(\pi_{\text{ref}}\) | the reference model: a frozen copy from before fine-tuning | probability distribution |
| \(\beta\) | strength of the pull towards the reference model | positive number |
1Pretraining: predict the next token
In words. Go through a text token by token. At each position the model outputs a probability for every possible next token; add up the logarithms of the probabilities it gave to the tokens that actually came next, and make that sum as large as possible.
Why it has this form. The probability of a whole text factorises exactly, by the chain rule of probability, into \(p(w_1)\,p(w_2\mid w_1)\,p(w_3\mid w_1,w_2)\cdots\); taking the logarithm turns the product into the sum. So this is maximum likelihood for text, and it is the cross-entropy loss of Lecture 3 with the vocabulary as the set of classes. It needs no labels: every text is its own supervision.
Watch out. The objective rewards the likely continuation, not the true or the helpful one. That gap is what the later stages try to close.
2Learning what humans prefer: the reward model
In words. Show people two responses and record which they prefer. Train a model to give each response a score such that the preferred one scores higher; only the difference of the two scores enters the loss.
Why it has this form. People are poor at giving absolute scores and good at comparing. Under the Bradley–Terry model the probability that \(s^w\) beats \(s^l\) is \(\sigma\) of the difference of their scores; the loss is the negative log-likelihood of the recorded choices. It is the same formula as BPR in Lecture 11, with responses in place of items. The trained reward model then stands in for the human when a policy is optimised by reinforcement learning, \(\max_\theta\mathbb E_{\hat y\sim p_\theta(y\mid x)}[R(x,\hat y)]\).
Watch out. Scores are defined only up to an added constant; a reward of 3 means nothing by itself, only relative to other responses to the same prompt.
3A reward that looks beyond the next turn (CollabLLM)
In words. The value of a reply is the average quality of the whole conversations that follow from it. Estimate it by simulating \(S\) continuations with a simulated user and averaging the reward of the finished conversations.
Why it has this form. A reward on the single next response favours an immediate, complete-looking answer. In real collaboration the better move is often to ask a clarifying question, which scores poorly on its own and pays off two turns later. Defining the reward on the outcome of the conversation, in expectation over how the user might respond, gives such moves their due. The expectation cannot be computed, so it is replaced by a sample mean over simulated futures (a Monte-Carlo estimate, the same idea as the return in reinforcement learning).
Watch out. The estimate is only as good as the user simulator, and its variance falls slowly, like \(1/\sqrt S\).
4Training directly on preferences (DPO)
In words. For a prompt with a preferred and a rejected response: raise the model's probability of the preferred one, relative to what the reference model gave it, more than its probability of the rejected one.
Why it has this form. Reinforcement learning with a penalty for drifting from the reference model has a known optimal policy, and for that policy the reward can be written as \(r(x,y)=\beta\log\frac{\pi^*(y\mid x)}{\pi_{\text{ref}}(y\mid x)}+\beta\log Z(x)\). Substitute this expression into the reward-model loss of card 2: the term \(\beta\log Z(x)\) is the same for both responses and cancels in the difference, leaving a loss in the policy alone. So no separate reward model and no sampling loop are needed; preference pairs train the policy with an ordinary classification loss.
Watch out. The ratios are of probabilities of whole responses, i.e. sums of token log-probabilities; long responses have very small probabilities, which is why everything is done in logarithms.
Check yourself
Questions from the lecture, in order. Answer each one in your head (or on paper) before you open it. If one stumps you, follow the link to the walkthrough block it comes from.
Check yourself: connect this to slide 18. Which part of the RLHF pipeline creates the bias? show answer
The comparison data: labelers compare responses to one prompt in isolation, so the reward model never sees what happens afterwards.
from The collaboration problem: LLMs as passive responders
Check yourself: where are graphs in this lecture? show answer
In STaRK/AvaTaR, the knowledge itself is a graph with text on nodes, and tools navigate it. In CollabLLM, a conversation is a sequential process whose future branches form a tree of trajectories, which is sampled to estimate rewards.
Lecture walkthrough reference · slide by slide · opens on demand
The whole lecture in order, grouped by topic. Every drawing on the slides is redrawn here as a clean figure (click the step buttons where a figure has them), the heading of each block links to the matching pages of the official PDF, and the Review section after the walkthrough ties this session to the earlier ones. Read this and you do not need the deck.
- How LLMs are trained: pretraining
- From language model to assistant: instruction fine-tuning
- RLHF: rewards from human preferences
- Knowledge-intensive queries over semi-structured knowledge bases
- STaRK: a benchmark for semi-structured retrieval
- Tool use: why agents fail, and what a good plan looks like
- AvaTaR: contrastive reasoning to optimize tool use
- AvaTaR results
- The collaboration problem: LLMs as passive responders
- CollabLLM: multiturn-aware rewards via simulated users
- Evaluating multi-turn collaboration
- Real users, generalization, and the big picture
How LLMs are trained: pretraining slides 2-6 ↗
This guest lecture is by Shirley Wu (Stanford). The first part reviews how large language models (LLMs) are built (it is based on slides from Stanford's CS224N and CS224R). Then it turns to two research problems: agents that use tools over knowledge graphs, and agents that collaborate with humans.
Slide 2: larger and larger models. An OpenAI plot of training compute (in petaflop/s-days, log scale from \(10^{-7}\) to 100) against year, from the Perceptron (1958) to AlphaGo Zero (2017). Points are coloured by field: language, speech, vision, games, other. In the "first era" compute doubled about every two years (Moore's law). From about 2012 (AlexNet, image classification with deep CNNs) the "modern era" starts and compute doubles every 3.4 months; AlphaGo Zero "becomes its own teacher of the game Go" at the top.
Slide 3 shows the three training stages as a pyramid: pretraining at the base, then fine-tuning, then reinforcement learning on top.
Slide 4: pretraining = next-token prediction. A Transformer reads "President of US is Joe" and at every position predicts the next token ("of", "US", "is", "Joe", "Biden", END). Training on a huge text corpus means: maximize the probability of each next token given the previous ones,
\[ \max_\theta \sum_t \log p_\theta(w_t \mid w_1,\dots,w_{t-1}). \]Slides 5–6: what pretraining learns. Filling in blanks forces the model to learn many kinds of knowledge:
- "Stanford University is located in ____, California." — trivia (world facts);
- "I put ___ fork down on the table." — syntax;
- "The woman walked across the street, checking for traffic over ___ shoulder." — coreference;
- "I went to the ocean to see the fish, turtles, seals, and ____." — lexical semantics / topic;
- "Overall, the value I got from the two hours watching it was the sum total of the popcorn and the drink. The movie was ___." — sentiment.
The lesson (slide 6): pretraining uses lots of text and learns general things, so the model must be able to process large-scale, diverse datasets.
From language model to assistant: instruction fine-tuning slides 7-14 ↗
Slide 7 asks: how do we get from a model that completes "Stanford University is located in ____" to a chat assistant (a ChatGPT window asking "Where should we begin?")?
Slides 8–9: language modeling ≠ assisting users. Prompt: "Explain the moon landing to a 6 year old in a few sentences." GPT-3's completion just continues the pattern with similar lines ("Explain the theory of gravity to a 6 year old. Explain the theory of relativity…, Explain the big bang theory…, Explain evolution…"), because on the internet such a line is often part of a list. A human writes an actual answer: "A giant rocket ship blasted off from Earth carrying astronauts to the moon…". Language models are not aligned with user intent (Ouyang et al., 2022). Fine-tuning comes to the rescue.
Slide 10: the pretrain / fine-tune paradigm. Step 1: pretrain on language modelling (lots of text; learn general things). Step 2: fine-tune on your task (not many labels; adapt to the task). The pictures show the same decoder (Transformer, LSTM, …) used for next-token prediction and then for, e.g., sentiment ("… the movie was …" → positive/negative).
Slide 11: instruction fine-tuning. Collect examples of (instruction, output) pairs across many tasks and fine-tune the LM on them. Examples on the slide: "What is the boiling point of Nitrogen?" → "−320.4F"; a word problem ("The cafeteria had 23 apples; they used 20 for lunch and bought 6 more…") with a step-by-step answer (23 − 20 = 3, 3 + 6 = 9). Then evaluate on unseen tasks, e.g. "Can Geoffrey Hinton have a conversation with George Washington? Give the rationale before answering." with an answer reasoning that Washington died in 1799, so no.
Slides 12–13: a disambiguation QA example. Input: "In the following sentences, explain the antecedent of the pronoun (which thing the pronoun refers to), or state that it is ambiguous. Sentence: The reporter and the chef will discuss their favorite dishes. Options: (A) the reporter's favorite dishes, (B) the chef's favorite dishes, (C) ambiguous. A: Let's think step by step." Before instruction fine-tuning the model rambles and repeats variations of the sentence; it does not answer. After fine-tuning it says the sentence does not show whose dishes they are, "So, the answer is (C)."
Slide 14: improvements and limitations. Instruction fine-tuning makes models follow user instructions. But:
- Open-ended creative tasks have no single right answer (e.g., "Write me a story about a dog and her pet grasshopper"), so imitating one reference output is a poor objective.
- The language-modelling loss penalizes all token-level mistakes equally, although some errors are much worse than others (a wrong number in a medical answer vs a slightly odd word choice).
Both limitations point to the same fix: optimize a score of the whole output, given by humans.
RLHF: rewards from human preferences slides 15-22 ↗
Slide 15: optimizing for human preferences. Suppose we train an LM for summarization. For an instruction \(x\) (a CNN article about a magnitude 4.2 earthquake in San Francisco) and a model sample \(y\), imagine a human gives a reward \(R(x,y)\in\mathbb{R}\), higher is better. Summary \(y_1\): "An earthquake hit San Francisco. There was minor property damage, but no injuries." gets \(R(x,y_1)=8.0\). Summary \(y_2\): "The Bay Area has good weather but is prone to earthquakes and wildfires." gets \(R(x,y_2)=1.2\). We want to maximize the expected reward of samples from the LM (Schulman et al., 2017):
\[ \max_\theta\; \mathbb{E}_{\hat y \sim p_\theta(y\mid x)}\big[R(x,\hat y)\big]. \]Slide 16: but this needs a reward model: we cannot ask a human to score every sample during training.
Slide 17: a reward model \(RM_\phi\) is a network that takes \((x, y)\) and outputs the scalar reward (e.g., \(R(x,y_2)=1.2\)).
Slide 18: how to model human preferences. Humans are bad at giving consistent absolute scores but good at comparing. So collect rankings: for the same input, a "winning" sample \(s^w\) is preferred to a "losing" sample \(s^l\). Train the reward model so that \(s^w\) scores higher than \(s^l\) (Bradley–Terry model, as used in Rafailov et al. 2023):
\[ J_{RM}(\phi) = -\,\mathbb{E}_{(s^w,s^l)\sim D}\Big[\log \sigma\big(RM_\phi(s^w) - RM_\phi(s^l)\big)\Big]. \]Here \(\sigma\) is the sigmoid, so \(\sigma(RM(s^w)-RM(s^l))\) is the modelled probability that a human prefers \(s^w\).
Slide 19: optimizing the learned reward. We have (1) a pretrained, possibly instruction-fine-tuned LM \(p^{PT}(y\mid x)\), and (2) a reward model \(RM_\phi(x,y)\) trained on human comparisons. RLHF copies the model into \(p_\theta^{RL}(y\mid x)\), with parameters \(\theta\) to optimize, and maximizes
\[ \mathbb{E}_{\hat y \sim p_\theta^{RL}(\hat y\mid x)}\big[RM_\phi(x,\hat y)\big]. \]In practice a penalty \(\beta\,\mathrm{KL}(p^{RL}_\theta \,\|\, p^{PT})\) is added so the policy does not drift too far from the original model and "hack" the reward model. The slide does not show it, but it is standard (InstructGPT).
Slide 20: the three steps (InstructGPT figure). Step 1: sample a prompt ("Explain the moon landing to a 6 year old"), a labeler writes the desired output, and GPT-3 is fine-tuned with supervised learning (SFT). Step 2: sample several model outputs (A, B, C, D) for a prompt; a labeler ranks them from best to worst (D > C > A = B); this data trains the reward model. Step 3: sample a new prompt ("Write a story about frogs"); the policy generates an output ("Once upon a time…"); the reward model computes a reward \(r_k\); the reward updates the policy with PPO (a policy-gradient RL algorithm).
Slide 21 repeats the question of slide 7: these steps are how we get from a completion model to an assistant.
Slide 22: RLHF gives gains over pretraining + fine-tuning. The plot shows, for summarization, the fraction of model summaries preferred to human reference summaries, against model size (1.3B, 2.7B, 6.7B, 12.9B). The dashed line at 0.5 is the reference. "Pretrain only" \(p^{PT}\) is lowest (about 0.22 to 0.36); "supervised learning" \(p^{IFT}\) is about 0.39 to 0.43; "human feedback" \(p^{RL}\) is about 0.61 to 0.70, i.e. above the human references, even at 1.3B.
Knowledge-intensive queries over semi-structured knowledge bases slides 23-26 ↗
Slide 23. Real user queries are often knowledge-intensive: "Can you find a push-along tricycle from Radio Flyer that is both fun and safe for my kids?"
Slide 24: navigating complex knowledge (Amazon knowledge base). The figure is a graph of products, brands, colors and categories: products link to brands ("has brand": Radio Flyer, IKEA), to each other ("also viewed", "also bought"), to a color ("has color: Red") and to a category ("Wooden furniture"). Each product node also has a text document: "Title: Radio Flyer Ultimate All-Terrain Stroll 'N Tricycle. Price: $84.99. Feature: AGES 1 TO 5 YEARS…, REMOVABLE ACCESSORIES…. Dimensions: 37.2"×34.3"×22". Description: This tricycle grows with your toddler through different riding stages."
So the data is a semi-structured knowledge base (SKB): a knowledge graph (relational, structured part) whose entities carry free text (unstructured part).
Slide 25: the setting. A user sends a query to an LLM agent; the agent retrieves from the SKB and returns answers (here, products).
Slide 26: why is this hard for LLMs? Real queries need multi-hop reasoning, filtering and synthesis. The LLM must (1) navigate a large semi-structured knowledge base, (2) find the useful information, and (3) reason and aggregate answers. In the example: "from Radio Flyer" is a relational constraint (follow the "has brand" edge), "push-along tricycle" is a type constraint, and "fun and safe for my kids" can only be checked in the text description.
STaRK: a benchmark for semi-structured retrieval slides 27-29 ↗
Slide 27: STaRK. A benchmark for retrieval over SKBs. It has two kinds of question–answer pairs:
- Synthesized Q&A pairs (large): constructed automatically with simulated users (an LLM), e.g. "Please suggest a HEAD tennis racquet for a casual player", "Looking for a stylish kids bike helmet that suits a Superman bike".
- Human-generated Q&A pairs (small): written by human participants, e.g. "Need Fabric Guard water repellant that blocks harmful UV rays"; they provide a reference for evaluating the synthesized set.
Systems (an LLM agent with retrieval over the SKB) are evaluated on how well they retrieve the correct entities. STaRK has three SKBs: Amazon (products), MAG (academic papers) and Prime (biomedicine; the same STaRK-Prime as in the Lecture 16 Neo4j case study).
Slide 28: key result: current methods are not good. On STaRK-Prime:
- QAGNN (RoBERTa): Hit@1 7.14, Hit@5 17.14;
- ada-002 (OpenAI text embeddings, vector search): Hit@1 15.36, Hit@5 31.07;
- Claude3 reranker: Hit@1 17.79, Hit@5 36.90.
For all methods, Hit@1 is below 18%. Hit@\(k\) = the fraction of queries where a correct answer appears in the top \(k\).
Slide 29: takeaway. STaRK establishes the challenge; current systems need significant improvement. How can we make LLMs better at these tasks?
Tool use: why agents fail, and what a good plan looks like slides 30-32 ↗
Slide 30: insight. LLMs need to use external tools effectively, e.g. retrieval systems over KGs and text. The figure: complex knowledge (graphs), embedding systems and other resources are wrapped as tools that the agent can call to access, process and visualize information.
Slide 31: but LLMs use tools poorly. A ReAct agent (unoptimized: it alternates Thought → Action → Observation) gets the query "Can you suggest any TUSA swim fins that have a split fin design for better propulsion?" and an action space (GetEntityTypes, GetEntityDocuments, StringMatching, …). Its trace:
- Thought: compute similarity scores from the product description. Action: ComputeEmbeddingSimilarity["swim fins", GetEntityDocuments()] → scores \(s_1\). Mistake: it ignores the brand "TUSA".
- Thought: check the functional requirement. Action: StringMatching["split fin design for better propulsion", documents] → \(s_2\) is all zeros, because no document contains that exact phrase.
- Thought: combine. Action: Multiply[\(s_1, s_2\)] → all zeros, a trivial result. Final: GetTopkEntities[\(s\), k=5] → poor performance.
LLM agents easily use the wrong tools or use tools in the wrong way.
Slide 32: an optimized agent (AvaTaR). Same query, a much better plan:
- ParseAttributeFromQuery → sub-query {brand: "TUSA", type: "swim fins", material: NA, features: "split fin design for better propulsion"}. The query is decomposed into aspects.
- ComputeEmbeddingSimilarity[sub-query.type, GetEntityTypes()] → \(s_1\), type similarity; GetTopk[\(s_1\), k=20] → 20 candidates. Embeddings are used to filter.
- GetEntityBrand[candidates]; TokenMatching[sub-query.brand, brands] → \(s_2\). Flexible token matching for the brand.
- GetSatisfactionScoreByLLM[sub-query.features, documents] → \(s_3\). An LLM call checks the fuzzy functional requirement.
- WeightedSum[\(s_1, s_2, s_3\)], coefficients (0.43, 0.37, 0.20) → final scores; return the top 5.
Compare the two: multiplying scores makes one failing signal kill everything; a weighted sum with tuned weights is robust. Exact string matching fails on paraphrases; an LLM judge does not. Check yourself: why filter to 20 candidates before calling the LLM scorer? (LLM calls are expensive; cheap tools narrow the set first.)
AvaTaR: contrastive reasoning to optimize tool use slides 33-37 ↗
Slide 33: the idea. We need more effective instructions (prompts) to improve the agent's tool use, and we build them with contrastive reasoning.
Slide 34: an analogy. A student's calculations. Correct: 1 + 1 = 2, 10 + 20 = 30, 45 + 112 = 157, 3 + (45 − 8) = 40. Incorrect: 2 × 5 = 12, 10 × 22 = 240, 45 × 12 = 545, 3 × (45 − 8) = 113. Looking at one mistake alone tells you little; comparing the two groups shows the pattern: every wrong one involves multiplication. So the student should practise multiplication.
Slide 35: an LLM comparator. Take the actions generated by an actor agent on a batch of queries. Split the queries into a positive group (answered well) and a negative group (answered poorly). Prompt an LLM comparator to understand the gap between the groups that the agent's actions cause, and to write instructions on how to improve the prompt.
Slide 36: an example. The prompt: "Here are two groups of queries that an agent performs poorly and well on; understand their differences." Answered correctly: "Need a pair of basketball NIKE shoes", "Recommend a scooter for under $100". Answered incorrectly: "Find me visually stunning castle card modelling kits", "I want a nice mug for my cousin who is very into spiderman". The comparator's output: "You do well on queries with simple product features, while you fail on specific and nuanced product descriptions. I suggest to better parse and utilize query attributes. Use tools to compute F1 score for string matching."
Slide 37: the AvaTaR loop.
- Start with a training QA dataset, a set of tools, and initial instructions.
- The actor agent generates actions (tool-use code) for training queries.
- The comparator looks at good vs bad results and generates updated instructions.
- The updated instructions go into the actor's prompt. Repeat.
Note what is being optimized: not model weights, but the prompt. The comparator's output plays the role of a gradient in "text space": a direction to change the instructions. Contrastive pairs make this "gradient" informative, like positive and negative samples in contrastive learning.
AvaTaR results slides 38-39 ↗
Slide 38: Hit@1 on STaRK.
- STaRK-Amazon: VSS (ada-002) 39.02, ReAct 42.14, Reflexion 42.79, AvaTaR 49.87 (+28%).
- STaRK-MAG: VSS 28.20, ReAct 31.07, Reflexion 40.71, AvaTaR 44.36 (+57%).
- STaRK-Prime: VSS 15.36, ReAct 15.28, Reflexion 14.28, AvaTaR 18.44 (+20%).
Baselines: VSS = vector similarity search (plain RAG); ReAct (Yao et al. 2022) = an unoptimized agent that generates actions for each query; Reflexion (Shinn et al.) = an agent optimized by self-reflection. The relative improvements are computed against VSS (for example \(49.87/39.02 \approx 1.28\)). Biomedicine (Prime) remains hard for everyone; compare with the 0.32 Hit@1 that the GNN+LLM system of Lecture 16 reached on the same benchmark.
Slide 39: takeaway. AvaTaR helps LLMs handle complex Q&A by improving their tool use, and it is a principled, automated way to optimize LLM agents for tool use. But complex tasks often involve interaction and evolving goals, not one-shot Q&A. That leads to the third part.
The collaboration problem: LLMs as passive responders slides 40-43 ↗
Slide 40: human–LLM interactions are everywhere: document editing, coding assistance, mathematical problem solving, scientific discovery. The diagram is a loop: a human with a task, an agent ("I need help"), and the environment; both act on it.
Slide 41: LLMs jump to (wrong) conclusions. Two examples:
- Inefficient: "What's a good pasta recipe?" → the model writes a full recipe with chicken broth (wasted tokens). User: "I am vegetarian!" → now a vegetarian recipe (the relevant tokens). One clarifying question would have saved a whole answer.
- Useless: "My muscles have been feeling really weak." → a list of six causes, from dehydration to chronic conditions. User: "I don't think these make sense." → "Other reasons can be…". The model never asks about symptoms or context.
(Examples from STaR-GATE, UnknowBench and STaRK.)
Slide 42: problems. LLMs do not naturally help users clarify their needs or explore options, and they act as passive responders, especially under ambiguity.
Slide 43: why? LLMs are usually tuned on single-turn human preferences. User: "I need to write an article about optimism." Response 1: a full article. Response 2: a clarifying question. In a single turn, response 1 looks more useful and gets a higher reward; response 2 provides no answer and gets a lower reward. So single-turn rewards encourage responses that may not be useful in the long run.
Check yourself: connect this to slide 18. Which part of the RLHF pipeline creates the bias? show answer
The comparison data: labelers compare responses to one prompt in isolation, so the reward model never sees what happens afterwards.
CollabLLM: multiturn-aware rewards via simulated users slides 44-50 ↗
Slide 44: CollabLLM trains LLMs to actively seek information from users and collaborate better. Key insight: reward a response by its long-term impact on the conversation — a multiturn-aware reward (MR).
Slide 45: the key question. How do we estimate a response's long-term impact? Given the context and a model response, we would like to know how well the response helps in the future. This requires sampling future trajectories (sample #1, #2, #3) of the conversation and scoring them.
Slide 46: use an LLM to simulate users. A user simulator LLM gets (1) a task description ("You should write a document"), (2) a persona (user characteristics), and (3) the context (the current conversation). It then plays the user in a synthetic future conversation with the model: "Can you help make it more concise?" … "Good start! Can we add more about …?"
Slide 47: estimating long-term impact. Goal: evaluate the long-term impact of model response \(y_0\).
- Sample synthetic conversations with user simulators: \(y_0, u_1, y_1, u_2, y_2, \dots\) (several samples).
- Compute a reward for each synthetic conversation, e.g. task accuracy, efficiency, interactivity.
- Average the rewards. This average is the multiturn-aware reward of \(y_0\).
In symbols: \(\mathrm{MR}(y_0 \mid \text{context}) \approx \frac{1}{S}\sum_{s=1}^{S} R(\text{conversation}_s)\), where each conversation starts with \(y_0\) and continues with the simulator. It is a Monte Carlo estimate of the expected future outcome, like a value function in RL.
Slide 48: example 1. User: "I need to write about how optimism can improve our well-being." Response to evaluate: a full piece, "The Power of Optimism: Unlocking a Brighter You…". Synthetic continuation: the simulated user says the tone is too formal and the examples old-school; the model rewrites ("The Optimism Revolution: … Hey there, friend!"); the user says "Still not what I want, I want to talk about how it helps with relationships." Scores: efficiency low (the user must read 1.39k tokens), document quality low, interaction experience bad.
Slide 49: example 2. Response to evaluate: "To get us started, what kind of tone are you aiming for? Also, what do you want to highlight?" Synthetic continuation: "Inspirational; relationships would be great!" → the model proposes an opening paragraph and suggests adding personal experience → "Nice! Help me add some personal experience…". Scores: efficiency high (only 1.12k tokens read), document quality high, interaction experience good. The clarifying question, which a single-turn reward would punish, wins.
Slide 50: CollabLLM in a nutshell.
- Collaborative simulation: simulate multi-turn interactions.
- Multiturn-aware rewards: causal effect estimation — how the current response affects the long-term outcome of the conversation.
- Reinforcement fine-tuning: fine-tune the LLM with DPO or PPO on these long-term, interaction-level rewards.
Evaluating multi-turn collaboration slides 51-55 ↗
Slide 51: popular benchmarks (BigCodeBench, HotpotQA, MathVista) are single-turn: one prompt, one answer. They cannot measure collaboration.
Slide 52: three multi-turn benchmarks, where a simulated user holds the full task and reveals it over the conversation:
- MediumDocEdit-Chat (document writing), task metric: BLEU (similarity to the target document);
- BigCodeBench-Chat (coding, built on Zhuo et al. 2024), metric: pass rate (PR);
- Math-Chat (built on Hendrycks et al. 2021, MATH), metric: accuracy.
User-experience metrics for all three: #Tokens (how efficient the LLM is during the conversation; lower is better) and Interactivity (ITR) (how engaging the conversation is).
Slide 53: methods. CollabLLM is trained on the benchmarks' training sets. Baselines: Base = Llama-3.1-8B-Instruct; Proactive Base = the same model with a prompt saying "You should ask questions and reduce user efforts…".
Slides 54–55: results in simulated environments. (Slide 54 shows the BigCodeBench-Chat part; slide 55 the full table.)
- BigCodeBench-Chat (PR ↑ / #Tokens(k) ↓ / ITR ↑): Base 9.3 / 1.59 / 22.0; Proactive Base 11.0 / 1.51 / 33.7; CollabLLM 13.0 / 1.31 / 52.0. Relative improvement 18.2% / 13.2% / 54.3%.
- MediumDocEdit-Chat (BLEU / #Tokens / ITR): Base 32.2 / 2.49 / 46.0; Proactive 35.0 / 2.18 / 62.0; CollabLLM 36.8 / 2.00 / 92.0. Improvement 5.14% / 8.25% / 48.3%.
- Math-Chat (ACC / #Tokens / ITR): Base 11.0 / 3.40 / 44.0; Proactive 12.5 / 2.90 / 46.0; CollabLLM 16.5 / 2.37 / 60.0. Improvement 32.0% / 18.3% / 36.4%.
On average CollabLLM improves task performance by 18%, efficiency by 13% and interactivity by 46% over Base and Proactive Base. Note that simply prompting the model to ask questions (Proactive Base) helps a bit, but training on multiturn-aware rewards helps much more.
Real users, generalization, and the big picture slides 56-61 ↗
Slide 56: a real-world study. 201 people completed writing tasks with an LLM, rated document quality and interaction experience (1–10), and their time was recorded. Violin plots (dot = average):
- Document quality: Base 8.16, Proactive Base 8.38, CollabLLM 8.50.
- Interaction experience: Base 8.11, Proactive Base 8.46, CollabLLM 8.60.
- Time spent (as plotted): Base 1237, Proactive Base 1319, CollabLLM 1108.
CollabLLM gives better documents and user experience and saves more than 10% of the time (1108 vs 1237).
Slide 57: participant feedback. On Base: "the AI just agreed with me on pretty much everything. There was no debate or discussion." On Proactive Base: "The AI seemed to be very redundant and asked me the same questions over and over." On CollabLLM: "It helped really well to navigate what to say and what information is needed", "The AI really helped focusing on one part of the story at a time", "Asking questions and making you think of things you never thought of".
Slide 58: experience along the conversation. Participants rated the interaction every 3 turns. The plot (turns 3, 6, 9): Base rises from about 7.9 to about 8.3 at turn 6, then drops back to about 7.9 by turn 9. Proactive Base starts lowest (about 7.5) and climbs slowly to about 8.0. CollabLLM rises from about 7.9 to about 8.45 at turn 6 and stays there. So the base model degrades over long conversations, while CollabLLM keeps improving the experience.
Slide 59: generalization to Abg-CoQA (a conversational QA benchmark with ambiguous questions). The right behaviour: ask a question when the query is ambiguous, answer directly when it is not. Action-level accuracy (ambiguous / non-ambiguous): GPT-4o 15.44% / 95.60%; Base (Llama-3.1-8B) 16.26% / 90.40%; CollabLLM 52.84% / 72.32%. CollabLLM asks about 3× more questions on ambiguous queries; on unambiguous ones it asks only 18% more often than Base. (It was not trained on this benchmark.) Note the trade-off: its non-ambiguous accuracy is lower, so it sometimes asks when it need not.
Slide 60: high-level takeaway. Write the reward of an agent's action as \(R(a_t, s_t \mid e)\): action \(a_t\) (the response) in state \(s_t\) (the conversation so far), judged in environment \(e\). A task-centric objective sets \(e\) = the task: did the response solve it? A human-centric objective sets \(e\) = the task and the human: did it help this person, efficiently and pleasantly, over time? CollabLLM moves from the first to the second.
Slide 61: summary. STaRK (NeurIPS 2024) and AvaTaR (NeurIPS 2024) make AI agents that retrieve and use tools well over semi-structured knowledge. CollabLLM (Outstanding Paper at ICML 2025, one of 6) proposes a new way to define what matters in human–AI collaboration. The slide credits collaborators from Stanford (including Jure Leskovec and James Zou), Microsoft Research, Amazon and Accenture.
Check yourself: where are graphs in this lecture? show answer
In STaRK/AvaTaR, the knowledge itself is a graph with text on nodes, and tools navigate it. In CollabLLM, a conversation is a sequential process whose future branches form a tree of trajectories, which is sampled to estimate rewards.
Not shown (no new content): slides 1,62 — title page and closing 'END. Questions?' page.
Review: what to keep from this session
Carried forward. Lecture 18 generates graphs (molecules) and uses reinforcement learning for goal-directed generation, the same RL ideas as RLHF here.
Quick self-check
Why is the reward-model loss "BPR in disguise"?
Both maximise log σ(score of the preferred item − score of the other); only the inputs differ (responses versus items).
What does STaRK measure that earlier benchmarks did not?
Retrieval over semi-structured knowledge bases where a query mixes textual and relational constraints, so neither text search nor KG lookup alone suffices.
What is the loop of a ReAct agent?
Thought → action (tool call) → observation, repeated until the agent answers.
Key idea
Agents become more capable when their behaviour is optimised against the right signal: contrast successes and failures to learn how to use tools over knowledge graphs (AvaTaR), and reward responses by their long-term effect on a conversation with a human, not by single-turn preference (CollabLLM).
Multiturn-aware reward: expected outcome of the whole conversation after response \(y_t\), estimated with \(S\) simulated continuations.
Worked example: why the clarifying question wins
User: "I need to write about how optimism can improve our well-being."
- Response A (full article "The Power of Optimism…"). Single-turn reward: high. Simulated future: "tone too formal… still not what I want, focus on relationships…" → user reads 1.39k tokens; document quality low; experience bad. Average multiturn reward: low.
- Response B ("What tone are you aiming for? What do you want to highlight?"). Single-turn reward: low (no answer). Simulated future: "inspirational; relationships" → targeted opening paragraph → personal experience added → user reads 1.12k tokens; quality high; experience good. Average: high.
- Training on multiturn rewards teaches B over A — but only when the request is ambiguous; for "fix this typo", asking would lower efficiency and the reward.
Strictly speaking: the reward depends on the user simulator's fidelity; a simulator that behaves unlike real people would teach the wrong lessons — which is why the real-user study matters.
Proof workshop: A reward model is BPR on responses
One problem in olympiad style. Give it fifteen minutes on paper before you open the first hint; the hints are graded, so open them one at a time.
Problem. A Bradley–Terry reward model sets \(\Pr(y_w\succ y_l\mid x)=\sigma\big(r(x,y_w)-r(x,y_l)\big)\) and is trained by minimising \(\sum-\log\sigma(r(x,y_w)-r(x,y_l))\) over preference pairs. (a) Show that \(r\) is identifiable only up to an additive function of the prompt, \(r'(x,y)=r(x,y)+c(x)\). (b) For a linear reward \(r=\theta^\top\phi(x,y)\), prove the loss is convex in \(\theta\). (c) Map the objective onto Lecture 11's BPR term by term.
Hint 1
Hint 2
Solution
Why it matters. RLHF's reward model is a recommender over responses, so its failure modes are recommender failure modes: popularity bias (preferring long, confident answers), feedback loops, and a single-turn horizon. CollabLLM changes the label (multiturn-aware reward), not the loss; the notebook shows how much that flips.
Sharper lens: pairwise preferences are a graph problem
Not on the slides. Three or four points where the lecture rounds something off: the exact statement, a second way to see it, and where it stops being true. Each is short and has a pointer for going further.
Bradley–Terry scores exist exactly when the comparison graph is strongly connected
Draw a directed graph on the items (responses, models, players) with an edge \(i\to j\) whenever \(i\) beat \(j\) at least once. The maximum-likelihood Bradley–Terry scores exist and are unique up to a shift if and only if this graph is strongly connected (Ford 1957; Zermelo had the model in 1929, for chess). If some set of items never loses to the rest, the likelihood keeps increasing as their scores go to infinity.
The graph also gives an algorithm. Let a random walker at \(i\) move to \(j\) with probability proportional to the fraction of comparisons in which \(j\) beat \(i\). Its stationary distribution is a consistent estimate of the Bradley–Terry strengths (Rank Centrality, Negahban, Oh and Shah 2012), which makes the score a cousin of PageRank, and the number of comparisons needed is governed by the spectral gap of the comparison graph: about \(n\log n\) suffice when the graph is an expander. Public model leaderboards built from pairwise human votes fit this model, so which pairs get compared (the sampling design) decides how reliable the ranking is.
DPO: the reward model cancels out
RLHF maximises \(\mathbb E[r(x,y)]-\beta\,\mathrm{KL}(\pi\,\Vert\,\pi_{\text{ref}})\). The optimum has a closed form, \(\pi^*(y\mid x)=\pi_{\text{ref}}(y\mid x)\,e^{r(x,y)/\beta}/Z(x)\), which can be inverted:
\[ r(x,y)=\beta\log\frac{\pi^*(y\mid x)}{\pi_{\text{ref}}(y\mid x)}+\beta\log Z(x). \]
Substitute into the Bradley–Terry likelihood. The intractable \(Z(x)\) depends only on the prompt, and the likelihood sees only reward differences within a prompt, so it cancels. That is part (a) of the proof workshop put to work. What remains is Direct Preference Optimization (Rafailov et al., NeurIPS 2023):
\[ \mathcal L_{\text{DPO}}=-\log\sigma\Big(\beta\log\frac{\pi_\theta(y_w\mid x)}{\pi_{\text{ref}}(y_w\mid x)}-\beta\log\frac{\pi_\theta(y_l\mid x)}{\pi_{\text{ref}}(y_l\mid x)}\Big), \]
BPR again, with the score of an "item" equal to how much the policy has raised its log-probability relative to the reference. No reward model and no reinforcement-learning loop are needed, which is why CollabLLM can fine-tune with DPO on its multiturn-aware preferences.
A simulated user is a model too, and a comparator can overfit
CollabLLM. The multiturn-aware reward is a Monte Carlo estimate of a value function: the expected outcome of the conversation after response \(y_t\), under the simulator's behaviour. LLM-simulated users are more patient, more articulate and more consistent than people, and they all come from one pretrained prior (the homogeneity critique in the Frontier section). A policy tuned on them can learn to ask questions a real user would find tiresome. The 201-person study is the part of the paper that addresses this, and the pattern to copy: optimise against the simulator, then verify with people.
AvaTaR. Asking a comparator model "what distinguishes the failures from the successes, and how should the instructions change?" is optimisation with a language model as the update rule, the same family as OPRO, DSPy and TextGrad, where the critique plays the role of a gradient. It inherits the failure modes of any optimiser: instructions fitted to forty training queries can encode their quirks. Keep a held-out query set, and report the instructions themselves so others can see what was learned.
Lab: hands-on and practical tips
notebook · L17 agents + graphs shows the reward model is BPR, builds a STaRK-style semi-structured knowledge base and retrieval, runs an AvaTaR-lite loop with an LLM comparator, and simulates CollabLLM's multi-turn reward.
Readings & lookup guide
No readings are assigned on the course site for this lecture; these are its sources, ranked by relevance to graphs.
graphs + LLMs Wu et al. — STaRK: Benchmarking LLM Retrieval on Textual and Relational Knowledge Bases (NeurIPS 2024 D&B)
- Read: the SKB definition, how relational + textual queries are synthesised and validated, baseline results. A great testbed if you want a GNN+LLM project.
agents Wu et al. — AvaTaR: Optimizing LLM Agents for Tool Usage via Contrastive Reasoning (NeurIPS 2024)
- Read: the actor/comparator loop, how positive/negative query groups are sampled, memory of past instructions, results on STaRK and QA benchmarks.
collaboration Wu et al. — CollabLLM: From Passive Responders to Active Collaborators (ICML 2025, outstanding paper)
- Read: multiturn-aware reward definition, user simulator design, benchmarks and the user study.
foundations Ouyang et al. — InstructGPT (2022) · Rafailov et al. — Direct Preference Optimization (2023)
- InstructGPT for the SFT → RM → PPO pipeline; DPO shows the reward model can be eliminated — the policy itself is trained with a Bradley–Terry (BPR-like) loss on preference pairs.
Homework & deadlines
Colab 4 due Tue 12/1 · Colab 5 due Thu 12/3 · Final report due Thu 12/10
Agent + KG projects (e.g. AvaTaR-style tool optimisation on STaRK, or an LLM agent that queries a PyG GNN as a tool) are timely final-project directions.
Self-check
The RLHF reward-model loss \(-\log\sigma(RM(s^w)-RM(s^l))\) has the same form as …
- cross-entropy over tokens
- TransE's margin loss
- the BPR loss from recommender systems
- MSE
Both are Bradley–Terry pairwise preference models.
A semi-structured knowledge base is …
- a table
- a knowledge graph whose nodes also carry rich text
- a vector database
- a document collection without links
Relations + textual descriptions (e.g. Amazon products).
AvaTaR improves an agent by …
- contrasting well- and badly-answered queries to generate better tool-use instructions
- fine-tuning the LLM weights with RL
- adding more tools
- using a bigger LLM
A comparator LLM writes instructions; the actor's weights don't change.
Why do LLMs tend not to ask clarifying questions?
- They can't generate questions
- Context length
- Pretraining data has no questions
- Single-turn preference rewards favour immediate answers
A question looks unhelpful in a single turn.
CollabLLM estimates a response's long-term impact by …
- asking real users every time
- simulating future turns with an LLM user simulator and averaging rewards
- counting tokens
- BLEU score
Multiturn-aware reward from synthetic conversations.
Flashcards (click to flip)
History & the bigger picture
- 2017 — PPO; 2017 — Christiano et al., deep RL from human preferences; 2022 — InstructGPT / ChatGPT; 2023 — DPO.
- 2022 — ReAct (reason + act), 2023 — Reflexion, Toolformer; 2024 — STaRK, AvaTaR; 2025 — CollabLLM and a wave of "agentic" systems.
CollabLLM's shift — from "maximise this turn's approval" to "maximise the human's long-term outcome" — is an ethical shift as much as a technical one. Single-turn approval rewards flattery and agreement (participants said the base model "just agreed with me on pretty much everything"). Optimising for the person's actual goal over time is closer to the classical ideal of a good counsellor or teacher, who sometimes asks a question rather than pleasing immediately. The open question is who defines the long-term objective — the user, the platform, or the simulator?
Classic SNA bridge
| In this lecture | Classic SNA counterpart | What carried over, what changed |
|---|---|---|
| Multi-agent LLM systems with a communication graph | Coordination graphs in MARL (Guestrin 2002); small-group communication networks (Bavelas 1950; Leavitt 1951) | Leavitt measured how a star, chain or circle topology changes group performance on a task. The 2026 agent-topology papers re-run that experiment with LLM agents and learn the topology. |
| RLHF: preferences → reward → policy | Social-choice aggregation of preferences; Condorcet and Arrow on combining judgments | A reward model aggregates many annotators' pairwise judgments into one scalar. Social choice theory says such aggregation has unavoidable pathologies; RLHF inherits them silently. |
| CollabLLM: optimise the long-term outcome of a conversation | Exchange theory and reciprocity over repeated interaction (Blau 1964; Axelrod 1984) | Single-turn approval is a one-shot game; multi-turn reward is a repeated game where asking a question now pays later. The shift the lecture calls ethical is also the shift from one-shot to repeated interaction. |
| LLM agents simulating societies (OASIS) | Agent-based models in sociology (Schelling 1971; Axelrod's culture model; Epstein & Axtell 1996) | ABMs used simple rules and were validated against stylised facts. LLM agents are richer and less controlled; the PIMMUR-style validity critiques are the ABM literature's old lessons returning. |
| AvaTaR: an agent learns to use retrieval tools over an SKB | Information foraging and expert search in organisations ("who knows what", Borgatti & Cross 2003) | Finding the right source through a network of documents and people is transactive memory. The agent's learned instructions are a transactive-memory system written in natural language. |
Use the opinion-dynamics and contagion results of SNA (DeGroot, Friedkin–Johnsen, independent cascade) to predict how an error introduced at one agent spreads through an LLM agent network with a given topology. Then run the agents and measure. Agent networks are controllable laboratories for social mechanisms that are hard to isolate on platforms, with the validity caveats above; and SNA theory gives predictions the agent papers rarely test.
Go deeper in the SNA course. The twelve-unit course on social network analysis in this repository gives the classic side of this lecture in full, with labs and real-data analyses: Unit 12 · The new frontier: data, platforms & LLM agents (LLM agents that work over graphs, and where they still fail).
Connecting to your research
- SKB of social media: accounts, posts, hashtags (graph) + text (posts, bios) is a semi-structured KB. An AvaTaR-optimised agent answering analyst questions ("which accounts pushed narrative X in week Y and are connected to Z?") is a concrete research tool for computational social science.
- Interaction graphs of agents: multi-agent systems form networks — SNA methods can analyse how information and errors propagate between agents.
- Neuro-symbolic: AvaTaR's optimised action sequences are essentially programs over symbolic tools — learned by language, executed symbolically.
Frontier 2025–26: what changed since the slides
Frontiers · LLM agents became simulated citizens · agent collectives are social networks · closing the X API
Words & phrases
| Term | Simple meaning | Persian | In context |
|---|---|---|---|
| jump to conclusionsidiom | decide or answer too quickly, without enough information | عجولانه نتیجه گرفتن | "LLMs jump to conclusions" |
| passive responderphrase | someone (or a system) that only answers, never takes initiative | پاسخدهندهٔ منفعل | "They act as passive responders under ambiguity" |
| reward modeln. | a model trained to score outputs the way human preferences would | مدل پاداش | "a Bradley–Terry reward model" |
| preference pairn. | two responses to the same prompt, one marked better | زوج ترجیحی | "train on preference pairs" |
| agentn. | a system that chooses actions (here, tool calls) to reach a goal | عامل | "an LLM agent that queries the knowledge base" |
| policyn. | the rule an agent follows to pick actions | سیاست | "a policy that asks before answering" |
Go deeper
- Next: Lecture 18 — deep generative models for graphs (GraphRNN, GCPN).
- Agent memory as graphs: graph-structured memories for agents (e.g. knowledge-graph memory, Zep/Graphiti) — where this lecture meets Lecture 16.
- Open question: can contrastive instruction optimisation (AvaTaR) and multiturn rewards (CollabLLM) be combined — an agent that learns both how to use tools and when to ask the user?