Advanced Topics in Large Language Models

Contents

• Introduction and overview
• 0. Recap and how to use the seminar
• 1. Evaluation: contamination, judge bias
• 2. Reasoning: chain-of-thought, RLVR
• 3. Long context: RoPE, ring attention, RAG or LC?
• 4. Memory: episodic, vector stores, GraphRAG
• 5. Mixture-of-Experts
• 6. Alternative architectures: SSM, Mamba, RWKV
• 7. Efficiency: speculative decoding, quantization
• 8. LLMs × graphs: the LLGA crossroads
• 9. Agents: planning, tools, multi-agents
• 10. Open problems
• Exercises / Labs
• Projects and assessment
• References

Introduction and overview

Audience: an engineer or researcher who already reads LLM papers and wants a critical filter. Empirical first: we start from claims that do not survive a closer look — a “magic” chain-of-thought that fails out of distribution, a million-token context in which information gets lost in the middle — and only then study the work behind them: RLVR, MoE, Mamba, agents, contamination-aware evaluation.

The module is a reading seminar on the current research fronts of LLMs: evaluation, reasoning, long context and memory, architectures, efficiency, graphs, agents and open problems.

What you will be able to do

• Read an LLM research paper critically: claims, evidence, protocol, what the authors do not say;
• Explain model reasoning: chain-of-thought, reinforcement learning with verifiable rewards (RLVR);
• Analyze long-context techniques (RoPE, ring attention) and arbitrate between long context and RAG;
• Compare agent memories: episodic, vector stores, GraphRAG;
• Explain how mixture-of-experts architectures and alternatives to transformers (SSM, Mamba, RWKV) work and why they matter;
• Speed up inference with speculative decoding and quantization, quantifying the trade-offs;
• Analyze the LLMs × graphs crossroads and agent architectures (planning, tools, multi-agents);
• Evaluate an LLM without deceiving oneself: benchmark contamination, LLM judge bias, open problems.

Official objectives and syllabus

Official course description not published (S3/S4 catalog empty): as of the start of the 2026 academic year, the “LLGA 2 – Semestre 3” and “LLGA 2 – Semestre 4” tracks of the 2026-2027 SynapseS catalog still list no courses, and the master’s wiki indicates that the detailed M2 program is “under development” (period 2: “to be completed soon”).

The program below therefore reflects the master’s brochure (period 2), which announces a research seminar, with an indicative volume of ~24 h; these course materials are calibrated to that volume (see the session plan below).

The instructors of this proposed course are not confirmed; the cited papers and standards form the foundation, and the LLGA (LLMs & Graphs) group of École Polytechnique will provide the guest sessions when relevant.

The following table maps each brochure theme to the course sections; the materials’ own additions are marked “going beyond the syllabus”.

Where this course fits in the program

An M2 module offered in period 2 and preselected by the Graph × LLM route of the home page: a research seminar, it assumes the foundations are laid and works through readings and discussions rather than ex cathedra lectures.

Prerequisites: Large Language Models, the mandatory foundation that every chapter goes beyond (architecture and mixture-of-experts in ch. 2, training, alignment, inference); and one Deep Learning course, Deep Learning (P1) or Deep Learning P2, for attention, recurrent networks and training costs. Advanced Deep Learning is not assumed: the few tools used from outside these courses (FFT convolution, prefix scan, Optimal Brain Surgeon) are defined where they are needed.

Downstream: it is the direct preparation for the research internship and the PhD — each chapter ends with open questions that are as many internship topics — and for R&D jobs, where the competitive edge is played on a six-month head start in reading the literature.

Course outline

• Recap and how to use the seminar — the LLM foundation recapped, and the method: how one reads, discusses and presents a paper here.
• Evaluation: contamination, judge bias — why leaderboards are wrong, and how to evaluate honestly: the critical tools used in every later session.
• Reasoning: chain-of-thought, RLVR — have the model unfold a reasoning, then train it on verifiable rewards.
• Long context: RoPE, ring attention, RAG or LC? — extend the window, and the real industrial question: put everything in context or retrieve?
• Memory: episodic, vector stores, GraphRAG — give memory beyond the window, from vector storage to knowledge graphs.
• Mixture-of-Experts — immense models of which only a few experts activate: training, routing, savings.
• Alternative architectures: SSM, Mamba, RWKV — thinking beyond attention: promises and measured realities.
• Efficiency: speculative decoding, quantization — serve faster and cheaper, with their effects on quality.
• LLMs × graphs: the LLGA crossroads — reasoning on structures, GraphRAG, graph foundation models: the master’s signature.
• Agents: planning, tools, multi-agents — models that plan, call tools and collaborate.
• Open problems — the map of research fronts as it takes shape this year.
• Exercises / Labs — minimal reproductions: RoPE, speculative decoding, a small contamination-free evaluation.
• Projects and assessment — proposed solo and group subjects, a mock written exam and a grading rubric.
• References — the pivot papers of each chapter, with their rebuttals.

Session plan

24 h in class (announced) = 8 sessions of 3 h. The volume is the indicative ~24 h given by the master’s brochure for this research seminar (the SynapseS 2026–2027 sheet is not yet published); no session-by-session programme is published, so the split below is our proposal for covering these notes in that time. Since the module is a reading seminar, every chapter, open problems included, is discussed in class.

Level 1 = foundations (reviews, definitions, first worked examples), 2 = core methods, 3 = advanced theory and open problems; the level never goes down from one session to the next.

Self-study, outside the 24 h: none — the preparatory reading of each session’s pivot papers (about 1 h per session) is part of the seminar format.

How to study this module

• Read each paper before the session, in a first twenty-minute pass (abstract, figures, protocol), then a second targeted pass: the seminar only works if everyone has read.
• For each paper, write down the sentence “the central claim is X, proven by Y, fragile because Z”: it is the module’s single exercise, do it every week.
• Present at the board when it is your turn: explaining RoPE or speculative decoding without slides is the best rehearsal for a PhD interview.
• Systematically cross with the other modules: long context dialogues with the RAG Ops of ML Ops, agents with Speech Technology, ch. 8 with your graph courses.
• Follow two or three preprint sources after each chapter: the module above all teaches you to stay up to date by yourself.

0. Recap and how to use the seminar

This chapter states what the seminar assumes from earlier modules and explains how a session works: one pivot paper, read before class, dissected and then criticized with a common grid.

1. Evaluation: contamination, judge bias

Every later session asks whether a paper’s numbers can be trusted, so the seminar starts with the tools to answer that question: how test data leaks into training, how biased LLM judges are, and how to report a score honestly. A concrete scene: a state-of-the-art benchmark score that turns out to be inflated because the test set was in the training data.

1.1. Contamination: when the test leaks into training

1.2. LLM judges: useful, biased, calibratable

MT-Bench (Zheng et al., 2023) validates the LLM judge: GPT-4 agrees with expert human verdicts more than 80% of the time, the same level as the agreement between two humans (about 81%, ties excluded). This legitimizes its industrial use (ML Ops module ch. 5), but the biases are systematic.

Wang et al. (ACL 2024) show that a simple order swap flips a substantial share of verdicts — “not fair evaluators”.

HELM (Liang et al.) answers with the holistic: same models, dozens of scenarios, multiple metrics (accuracy, calibration, robustness, bias, toxicity…), published protocol — evaluation as a slow science versus the leaderboard as a fast sport.

# N-gram contamination detection (sketch, thresholds to calibrate)
def ngrams(s, n=13):  return {" ".join(s.split()[i:i+n]) for i in range(len(s.split())-n+1)}

def overlap(test_item, pretrain_index):     # pretrain_index: set of shingles
    q = ngrams(test_item.question) | ngrams(test_item.answer)
    return len(q & pretrain_index) / max(len(q), 1)

# measurement: overlap distribution per benchmark -- a non-negligible mass
# above 0.8 on "public" items (GSM8K-like) = contamination signal

2. Reasoning: chain-of-thought, RLVR

Can a language model be made to reason better, either by letting it write intermediate steps or by training it on problems whose answers can be checked? This session reads the papers that introduced chain-of-thought and self-consistency, compared process and outcome rewards, and showed with DeepSeek-R1 that reinforcement learning on verifiable rewards makes long reasoning emerge.

2.1. Chain-of-thought and self-consistency

The prompt “let’s think step by step” triggers the generation of an intermediate reasoning chain z before the answer y — and the gains emerge with scale (clear from ~10¹¹ parameters in the original study): the model allocates compute tokens to the problem. The formal reading:

2.2. Process vs outcome rewards

Training a reward model on the final answer (ORM, outcome) is noisy: an answer that is right by chance receives the same reward as a clean reasoning. Lightman et al. build PRM800K (800,000 step-by-step labels given by humans) and train a PRM (process reward model): at equal labeling budget, the PRM selects better solutions on MATH than the ORM — supervision of the process is more informative than that of the outcome.

Immediate limit: step-by-step labeling is expensive and subjective; hence the idea of automating verification…

2.3. RLVR: verifiable rewards and the emergence of reasoning

3. Long context: RoPE, ring attention, RAG or LC?

A model trained on short sequences must be made to read much longer ones, and one must decide whether to give it everything or only retrieved excerpts. This session reads how rotary positions are extended, how exact attention is distributed over GPUs, and what the comparisons between long context and RAG really show.

3.1. RoPE: position by rotation

3.2. Extending the window: interpolation and YaRN

Positional interpolation (Chen et al., 2023): trained with angles up to L, one serves L' = sL by compressing the positions m \mapsto m/s — the model sees only angles already covered. Chen et al. extend LLaMA (7B to 65B) from 2,048 to 32,768 tokens within 1,000 fine-tuning steps.

The defect of PI is that it divides every frequency by s, so the high frequencies, which tell neighbouring tokens apart, are squeezed too. YaRN interpolates only the low frequencies.

Result: Llama 2 extended to 64k and 128k tokens with 10× fewer training tokens and 2.5× fewer training steps than the previous methods.

3.3. Ring attention: cutting the memory cost in a ring

Scale reached: 4M-token contexts for a 7B model on 32 A100 GPUs (32× the best memory-efficient baseline), 16M tokens for a 3B model on a TPUv4-1024 pod. The same online softmax drives FlashAttention (LLMs ch. 2).

3.4. RAG or long context? Lost in the middle and the hybrid router

“Lost in the Middle” (N. Liu et al., 2023): when the information is placed in the middle of a long context, performance collapses in a U shape (beginning and end favored) — a 128k window does not “read” its 128k uniformly.

The RAG vs LC dossier: Li et al. (2024) compare systematically on long-context tasks: with sufficient resources, long context wins on average (retrieval can miss the needle).

But RAG remains much more economical — and their Self-Route (the model estimates whether the query is answerable with the retrieved excerpts; if not, the whole document is sent) stays close to LC quality at a much lower cost: 39% less with GPT-4o, 65% less with Gemini-1.5-Pro.

Xu et al. (ICLR 2024) complete the picture: retrieval improves models whatever the window (4k/16k/32k), and a 4k + retrieval approaches a 16k without retrieval — RAG is not dead, it is complementary.

# Self-Route self-evaluation (sketch) -- RAG first, LC as fallback
def self_route(question, docs, llm, budget):
    snippets = retrieve(question, docs, k=8)          # classic RAG
    verdict = llm(f"Can you answer using ONLY these excerpts? "
                  f"(YES/NO)\n---\n{snippets}", max_tokens=2, temp=0)
    if verdict.strip().upper().startswith("YES"):
        return llm(f"Excerpts:\n{snippets}\nQuestion: {question}")
    return llm(f"Full documents:\n{concat(docs)}\nQuestion: {question}")
    # cost (Li et al. 2024): ~61% of full LC with GPT-4o, ~35% with Gemini-1.5-Pro

4. Memory: episodic, vector stores, GraphRAG

What a model sees is limited by its context window, and what it learned is frozen in its weights. This session compares the ways of giving an LLM a memory beyond both: raw key-value memories, episodic memory streams, memory paged by the model itself, and graph-structured memory.

4.1. A taxonomy of memories

4.2. Three papers, three ideas of memory

• Memorizing Transformers (Wu et al., 2022): an attention layer, non-differentiable, looks up its keys/values in an external memory of (k, v) pairs by nearest neighbors (kNN) over past tokens of the same document. The memory is a FIFO cache, appended with the (k, v) pairs of every processed segment and cleared at each new document. Effective for perplexity, but non-differentiable: no gradient reaches the stored pairs, which go stale as the parameters change.
• Generative Agents (Park et al., 2023): 25 simulated agents in a virtual small town; each agent owns a timestamped memory stream; retrieval scores each memory by a weighted sum of recency, importance and relevance (Proposition 4.1); a reflection process periodically synthesizes the memories into higher-level beliefs (“I should organize a party”), re-injected as memories. The conceptual architecture of every memory-equipped conversational agent.
• MemGPT (Packer et al., 2023): the model becomes its own operating system: main context (RAM) vs external storage (disk), paging driven by function calls the LLM triggers itself (core_memory_append, archival_memory_insert…). Memory management becomes a learned/instructed behavior — the ancestor of the “agent + notepad” loops.
• GraphRAG (Edge et al., 2024): structured memory — an entity graph extracted by an LLM, communities detected (Leiden), hierarchical summaries; global questions (“which themes?”) become a map-reduce over the community summaries, where vector RAG falls apart (cf. Graph ML module ch. 10 for the graph foundations; ML Ops module ch. 6 for the indexing cost).

5. Mixture-of-Experts

A larger model is usually better but costs more per token. Mixture-of-experts layers break this link by activating only a few sub-networks per token; this session reads how the routing works, how the load is balanced, and what the experts actually learn.

5.1. Balancing the experts: the auxiliary loss

5.2. What the experts learn

The Mixtral routing analysis finds no clear specialization by topic — ArXiv, biology and philosophy texts are routed alike, DM Mathematics only slightly differently — but a syntactic one: Python’s self, indentation tokens and consecutive tokens often go to the same expert. The MoE mostly democratizes capacity, not a division of labor by subject.

DeepSeek-V3 pushes two structural innovations: fine-grained experts (more numerous, smaller) + shared experts (always active, capturing cross-cutting knowledge — reducing the redundancy), and FP8 training at scale (14.8T tokens) — the technical report is a systems-engineering course in itself (expert-parallel communication, cf. Emerging ML module ch. 2 on distributed computing).

6. Alternative architectures: SSM, Mamba, RWKV

Attention costs grow with the square of the sequence length and its cache grows linearly. This session reads the architectures that replace it with a recurrent state of fixed size — state space models, Mamba, RWKV — and the hybrids that keep a little attention for exact recall.

6.1. From RNNs to state space models

6.2. Mamba: making the state selective

The LTI SSM is a fixed filter: it cannot choose to memorize or forget depending on the content. Mamba (Gu & Dao, 2023) makes \Delta_t, B_t, C_t functions of the input (linear projections of u_t, through a softplus for \Delta_t), hence \bar A_t, \bar B_t too: the selection.

Cascade consequence: the convolution (prop. 6.2) is destroyed (the kernel depends on position) → back to a recurrence, but parallelizable via the prefix scan (box below) with fused GPU kernels (“hardware-aware”): \mathcal{O}(L) training, \mathcal{O}(1) inference per token and constant state memory — the selling point against the transformer’s KV cache (cf. ML Ops module ch. 3).

Finally, Mamba embeds the SSM inside a gated MLP-style block. Mamba-2 (SSD) will reformulate the SSM as a form of linear attention — the loop with attention comes full circle.

6.3. RWKV and the hybrids

Hybrids: pure SSMs lose on exact recall tasks (copying an association seen a long time ago: the compressed state has no room to keep everything — a recurring critique, cf. the associative recall studies).

Hence mixed architectures: Jamba (AI21, 2024) interleaves attention and Mamba layers at a 1:7 ratio — one attention layer in each block of eight — with an MoE replacing the MLP every other layer, and shows that this one attention layer in eight suffices to restore recall and in-context learning; Griffin/De et al. (2024) alternate recurrence (RG-LRU) and local attention.

The 2024-2026 consensus: attention is irreplaceable for precise retrieval; the SSM excels at long context on a constant memory budget; the hybrid beats both.

7. Efficiency: speculative decoding, quantization

Serving a large model is limited by latency and memory. This session proves why speculative decoding speeds up generation without changing its distribution, and how GPTQ and AWQ quantize weights to 4 bits with little loss.

7.1. Speculative decoding: the small proposes, the large disposes

7.2. Quantization: GPTQ and AWQ

8. LLMs × graphs: the LLGA crossroads

Can an LLM reason about a graph, and what is the best way to give it one? This session reads the benchmarks that test LLMs on serialized graphs, the study showing how much the serialization matters, and the hybrid that feeds a GNN encoding of a retrieved subgraph to the LLM.

8.1. The “bare” LLM facing serialized graphs

8.2. Hybridizing: GNN encoders and graph tokens

A second family, graph instruction tuning, teaches a frozen LLM to read graph tokens, as LLaVA teaches it to read image tokens.

8.3. Map of the field (the “roadmap”)

The last column uses the taxonomy of Graph ML 10.2, shared with Advanced GNN 8.3.

8.4. LLMs that complete knowledge graphs

Many true triples (h, r, t) are missing from any knowledge graph. KG completion ranks candidate tails t for a query (h, r, ?). Embeddings such as TransE (Graph ML ch. 6) or its rotation variant RotatE score triples by geometry alone; an LLM adds the entities’ text and its pre-training knowledge.

• Triples as text (KG-BERT, Yao, Mao & Luo, 2019): a fine-tuned BERT scores “head [SEP] relation [SEP] tail”, written with entity descriptions — one forward pass per candidate.
• Instruction tuning (KG-LLM, Yao et al., 2023): LLaMA-7B and ChatGLM-6B, fine-tuned on triples written as prompts, beat ChatGPT and GPT-4 on triple classification and relation prediction.
• Retrieve, then rerank in context (KICGPT, Wei et al., 2023): a RotatE model returns the top-m candidates; a frozen LLM reranks them with KG triples of the same entity and relation as demonstrations. No training; the gain is largest on long-tail entities, which the embedding saw rarely.

Evaluation: filtered MRR and Hits@k on FB15k-237 and WN18RR. A caution from ch. 1: Freebase facts are largely on Wikipedia, so an LLM may remember a “missing” triple rather than infer it.

# Same task, three encodings: a "talk like a graph" experiment in 10 lines
# (enc_degree, a degree-sorted edge list, is our variant, not one of the paper's nine)
def enc_edges(G):     return "\n".join(f"{u} -- {v}" for u, v in G.edges())
def enc_degree(G):    # edges sorted by decreasing endpoint degree
    d = dict(G.degree())
    es = sorted(G.edges(), key=lambda e: -(d[e[0]] + d[e[1]]))
    return "\n".join(f"{u} -- {v}" for u, v in es)
def enc_incident(G):
    return "\n".join(f"{u} : " + ", ".join(map(str, G[u])) for u in G)

for enc in (enc_edges, enc_degree, enc_incident):
    acc = run_gpt(enc(G), task="connectivity", n=100)
    print(f"{enc.__name__:14s} acc={acc:.2f}  tokens~{len(enc(G))//4}")

9. Agents: planning, tools, multi-agents

An agent is an LLM that acts in a loop: it reasons, calls a tool, reads the result and continues. This session reads the papers that defined this loop, taught models when to call tools, let them learn from their failures in context, and organized several agents together — and asks how reliable long chains of actions can be.

9.1. ReAct: reasoning and acting

The ReAct prompt alternates reasoning traces (Thought) and actions (Action / Observation) within a single trajectory: the model unrolls “thought → action → observation → thought → …”. On FEVER (fact checking), ReAct beats pure chain-of-thought (accuracy 60.9 against 56.3): the world answers, so it hallucinates fewer facts. On HotpotQA it stays below CoT (exact match 27.4 against 29.4) because uninformative search results derail its reasoning; the best scores (35.1) come from combining ReAct with self-consistent CoT.

On ALFWorld and WebShop the comparison is with acting alone and with imitation or RL agents, and ReAct wins clearly: 71% success on ALFWorld against 45% for Act-only and 37% for BUTLER — the observations are interpreted.

It becomes the default grammar of agents — that of the native “function calls” of current LLMs. RL link ch. 7: ReAct is a policy over an interaction tree; the chain-of-thought, its narrative value function.

9.2. Toolformer: learning where to call the tools

9.3. Reflection, multi-agent, and the question of emergence

• Reflexion (Shinn et al., 2023): after a failure, a verbal feedback (self-generated or from the environment) is stored and re-injected at the next attempt — “verbal RL”: improvement happens in the context, not in the weights. Striking gains on HumanEval and ALFWorld at zero training cost.
• CAMEL (Li et al., 2023): two agents role-play (user/assistant) to generate instruction data — the multi-agent conversation as a data synthesis engine.
• AutoGen (Wu et al., 2023): a framework where configurable agents (LLM, human, tool) converse programmatically — the industrial design pattern of multi-agent teams (orchestrator, critics, executors), to be connected to the guardrails and the tracing of the module ML Ops ch. 8.

10. Open problems

The seminar ends with problems that no one has solved yet: the finite stock of human text, the risk of training on generated data, and updating a model without retraining it. Each is a source of internship and thesis topics.

10.1. Data exhaustion

The answers in progress:

• synthetic data (models generate their own training material — with the risk of model collapse: Shumailov et al. show, on Gaussian mixtures, VAEs and a small language model (OPT-125m), that recursive training on generated data erodes the distribution tails — diversity collapses generation after generation);
• data efficiency (tokens counted, curriculum, “quality over quantity”);
• new sources (audio, video, interactions);
• rights — the question becomes legal (AI Act: copyright policy of GPAI — Explainability, Security and Privacy of LLMs ch. 10) before being purely technical.

10.2. Continual learning

LLMs are frozen at publication: any change requires a new training run or a fine-tune (with its train: catastrophic forgetting of earlier capabilities, safety regression — ML Ops module ch. 2 and 7).

Continual learning targets incremental updating: replay of a core of experiences, regularization toward the previous weights, additive modules (successive LoRAs — LLMs 4.3, versioned in ML Ops ch. 7), model merging (combining the weights of specialists — simple averages, TIES: surprising and under-theorized results).

The Yu et al. (2024) survey maps the field; the honest assessment: no scheme dominates yet, and the success criterion itself is blurry (remember what, from how many versions back?).

10.3. Other fronts — and conclusion of the seminar

• Memory vs context vs weights (ch. 3-4): where should knowledge be stored — parameters, KV, external index? The marginal cost of each byte differs by three orders of magnitude; the answer will depend on serving economics (ML Ops module ch. 3-4);
• Reasoning beyond the verifiable (ch. 2): extending reliable rewards beyond math/code;
• Safety at scale: statistical alignment facing competing objectives (Explainability, Security and Privacy of LLMs ch. 5–6);
• Interpretability as a science: from probing tools (linear probes, sparse autoencoders) to verifiable mechanisms (Explainability, Security and Privacy of LLMs ch. 1–3);
• LLGA: the LLM × graphs confrontation (ch. 8) remains an open construction site — serialization, GNN-LLM hybrids, incremental GraphRAG: your internship topics.

Exercises / Labs

1. ★ Reading notes (running thread). One sheet per session (claim / evidence / costs / reproducibility / LLGA link) on the pivotal paper; two sheets graded in depth: DeepSeek-R1 (ch. 2) and G-Retriever (ch. 8).
2. ★ Self-consistency (ch. 2). On a GSM8K sample: greedy vs self-consistency (k = 5, 20); plot accuracy vs k and accuracy vs cost (tokens); check that voting on the final answer extracted beats voting on the raw chain — why?
3. ★ Speculative decoding (ch. 7). Code the draft/verify scheme with residual re-sampling; verify empirically thm. 7.2 (count the tokens/iteration for measured \alpha); find the optimal \gamma for (\alpha, c) measured on your machine.
4. ★ Contamination (ch. 1). The ch. 1 n-gram detector on a small corpus; build 20 re-generated variants of a toy benchmark; measure the raw/variant gap for two models — and the judges’ asymmetry (alternating order) on MT-Bench-like setups.
5. ★★ Toy RLVR (ch. 2). Implement a mini-GRPO (cf. LLMs module ch. 5) with a binary format reward on a small model; observe the lengthening of the generations — a domestic “aha moment”; discuss reward hacking (does the model cheat the format?).
6. ★★ RoPE and extension (ch. 3). Numerically verify prop. 3.2 (dot products invariant under translation); extend a small model 512 → 2048 by interpolation then by YaRN (Definition 3.3); compare perplexity and a recall task (needle) before/after.
7. ★★ Simulated ring attention (ch. 3). Implement blockwise attention with ring passing over 4 simulated “GPUs” (processes), with the online-softmax recurrence of Proposition 3.4; verify exactness vs dense attention; measure communication vs compute (overlap).
8. ★★ Agent memory (ch. 4). Build a memory stream with the recency/importance/relevance triptych (prop. 4.1); add the reflection loop; test on 20 simulated sessions; ablation of each component of the score.
9. ★★ MoE routing (ch. 5). Load Mixtral (open weights) and instrument the router; measure the load distribution per expert over 3 corpora (code, math, prose); reproduce the specialization figure — and its variability; implement the auxiliary loss of Switch on a toy MoE and show the balancing.
10. ★★ SSM scan (ch. 6). Implement the SSM recurrence then the prefix scan (prop. 6.2 for the LTI case; selective version for Mamba); compare the GPU memory of the three modes (recurrence / FFT convolution / scan) on L = 8k; test the exact recall of a distant association — transformer vs SSM (the ch. 6 critique).
11. ★★ Agents (ch. 9). A ReAct agent with 3 tools, one of them unreliable (bad output); measure per-step p and the p^k law (prop. 9.2); add Reflexion and measure gain vs cost; multi-agent ablation: 2 “specialized” agents vs 1 agent with the same token budget.
12. ★★★ Graph encodings (ch. 8). Reproduce “Talk like a Graph” on 3 NLGraph tasks × the 3 encodings of the ch. 8 code, plus one of the paper’s nine encodings that the code does not cover (friendship, for instance); test the hypothesis “it is the structure, not the length” by matching lengths; a light G-Retriever: replace the PCST with a weighted shortest path and compare.
13. ★★★ Mini-review (ch. 10). Write a 4-page “position paper”: “In 2030, will knowledge live in the weights, the context or the index?” — drawing on at least six chapters of the seminar and two modules of the master.
14. ★★★ Graph tokens and LLM knowledge-graph completion (ch. 8). A reading half and a reproduction half.
    • Reading: compare GraphGPT and LLaGA (Definition 8.3) with the grid of ch. 0 — what is trained, what is frozen, and what the zero-shot transfer tables really support.
    • Reproduction, a simplified KICGPT: on 500 test queries of FB15k-237, rank the gold tail among the top 20 candidates of a RotatE model (PyKEEN). Compare RotatE alone with an open 7–8B instruction model that reranks the 20 candidates, with and without KG triples as demonstrations; report filtered MRR and Hits@1.
    • Check with the tools of ch. 1 whether the LLM’s gain comes from memorized Wikipedia facts: rerun on queries whose entity names are replaced by codes.

Projects and assessment

The fiche of this module displays no assessment: the SynapseS 2026–2027 sheet is not published and the wiki gives no modality for the M2 courses (see the introduction), so the official assessment is “not displayed”. Everything below is a proposal. It keeps the seminar’s running deliverable, the reading-note portfolio of Ex. 1, adds one project (solo or in a group) and a mock written exam.

The projects exercise objectives O3 (large language models) and O5 (graphs × LLMs) at their core, with O7 (hands-on practice: budgets, reproducible harnesses) and O8 (trustworthy evaluation: contamination, judges, hallucinations). The graph and agent subjects prepare the Year 2 transverse projects Y2.1 (graph-based question answering), Y2.2 (verifiable rewards) and Y2.4 (agent reliability).

Solo projects

1. [Solo · ≈ 20 h] An honest leaderboard: contamination and judge calibration. Question: how much of a benchmark score survives a contamination check, and how far can an LLM judge be trusted? Chapters used: ch. 1, 2.
   • Implement a reusable harness: the 13-gram overlap detector of ch. 1 run against a public pre-training sample (a shard of Dolma, Soldaini et al., 2024), and 20 or more regenerated variants of GSM8K items (Cobbe et al., 2021) with new numbers and names. Report each score as the raw / variant / overlap triple of Proposition 1.2.
   • Calibrate an open LLM judge on the 3.3k expert votes of the MT-Bench human judgments (Zheng et al., 2023), in both answer orders; measure agreement, the position-flip rate and a verbosity bias (pad correct answers).
   • Models: two or three open instruction models of 1–8B parameters, on a free GPU tier.
   • Deliverables: code, a 4–6 page report, a 10-minute talk. Success: every score given with a 95% interval and its variant gap; the judge’s agreement with humans, with an interval, set against the 81% human–human level (ties excluded).
2. [Solo · ≈ 20 h] Paper study: speculative decoding meets 4-bit quantization (Leviathan, Kalman and Matias, 2023). Question: does Theorem 7.2 predict the measured speedup, and what does quantizing the target cost in acceptance and quality? Chapters used: ch. 7, 1.
   • Implement speculative sampling with residual resampling (Definition 7.1) for a pair that shares a tokenizer, such as Qwen2.5-0.5B-Instruct as draft and Qwen2.5-3B-Instruct as target, on a free T4 GPU.
   • Measure the acceptance rate per domain — prose (WikiText-103), code (HumanEval prompts), math (GSM8K) — the tokens per target pass, and the best draft length from the speedup formula of exam question 2.
   • Quantize the target with GPTQ and with AWQ (7.2). Re-measure acceptance, latency, memory, GSM8K accuracy and the refusal rate on 100 AdvBench prompts (Zou et al., 2023), not only perplexity.
   • Deliverables: code, a 4–6 page report, a 10-minute talk. Success: measured tokens per pass within 10% of the theorem at the measured acceptance rate, or the gap explained (acceptances are correlated); a speed–memory–quality table with intervals.

Group projects

1. [Group of 4 · ≈ 30 h each] Paper study: serialize, retrieve or encode? A KG-QA bake-off around G-Retriever (He et al., 2024). Question: under a fixed token budget, when does a structural component beat serialization or long context — the open question of ch. 8? The subject connects this module to Graph ML ch. 10 and Advanced GNN 8.3, and is a light version of Y2.1. Chapters used: ch. 3, 4, 8.
   • Data: the WebQSP and SceneGraphs splits released with G-Retriever; one open LLM of 1–8B parameters for all systems.
   • Member 1: serialization — Talk-like-a-Graph encodings of the 2-hop subgraph (Proposition 8.1), and a long-context baseline that stuffs the graph up to the budget (ch. 3).
   • Member 2: GraphRAG — Leiden communities, their summaries, local and global search (ch. 4; Graph ML 10.1).
   • Member 3: a light G-Retriever — PCST or shortest-path subgraph, a GNN and one graph token, frozen LLM (Definition 8.2).
   • Member 4: the harness — Hit@1, a hallucination rate (answers naming entities absent from the graph), tokens and cost per query, an LLM judge calibrated as in ch. 1.
   • Deliverables: code, a 6–8 page report, a 15-minute talk. Success: the four systems at the same budget, Hit@1 with intervals per question type, and a reasoned answer to the open question of ch. 8 for these data.
2. [Group of 3 · ≈ 30 h each] Does RLVR teach graph algorithms or just select them? Question: the “select or create” debate of ch. 2, on the master’s own domain. The subject connects this module to LLMs ch. 5 (GRPO) and Reinforcement Learning ch. 5. Chapters used: ch. 2, 8.
   • Tasks: NLGraph-style connectivity, shortest path and topological sort on random NetworkX graphs, with rewards checked exactly by NetworkX (Definition 2.2). Train on 5–15 nodes; test on 20–40 nodes and on an unseen encoding (Proposition 8.1).
   • Member 1: mini-GRPO with LoRA on Qwen2.5-0.5B- or 1.5B-Instruct (TRL library), logging accuracy and generation length (2.3).
   • Member 2: the distillation baseline — supervised fine-tuning on verifier-filtered traces of a larger open model, at equal compute.
   • Member 3: the test of Yue et al. (2025) — pass@k of the base and trained models for k up to 256. If RLVR only selects, the base model catches up at large k.
   • Deliverables: code, a 6–8 page report, a 15-minute talk. Success: in- and out-of-distribution accuracy with intervals for the base, RLVR and distilled models, and pass@k curves that decide between the two readings on this domain.
3. [Group of 4 · ≈ 30 h each] A long-lived agent with structured memory. Question: which memory design keeps an agent reliable over many sessions, and at what token cost? The subject uses the tracing of ML Ops ch. 8. Chapters used: ch. 3, 4, 9.
   • Data: the very long conversations of LoCoMo and their questions (Maharana et al., 2024), plus a multi-session task of the group’s choice (research assistant or support desk) with three or more tools.
   • Members 1–3: one memory each — a plain vector store; a Generative-Agents memory stream with reflection (Proposition 4.1); MemGPT-style paging or an entity-graph memory.
   • Member 4: the ReAct agent and the harness — per-step success, the chain law of Proposition 9.2, and the single- versus multi-agent ablation at equal token budget.
   • Deliverables: code, a 6–8 page report, a 15-minute talk. Success: LoCoMo accuracy per question category and tokens per answer for each memory, with intervals; measured task success set against the prediction of Proposition 9.2 from the measured per-step success.

Written exam (proposal)

Format: 2 hours, one handwritten A4 sheet allowed, a non-programmable calculator, four questions. The fiche displays no exam, so this is a mock.

1. Question (5 points). (a) What does a contaminated benchmark score estimate, and which three numbers should a paper report instead of one? (b) Why is the KV cache of a transformer a feature and not only a cost, compared with the state of Mamba or RWKV? (c) Li et al. (2024) find that long context beats RAG on average. Why is RAG still deployed, and what does Self-Route do?

   Expected: (a) a mixture of memory and generalization, so the estimand shifts (Proposition 1.2); report the raw score, the score on regenerated variants and an overlap measure, and read the gap as an interval. (b) The cache stores every past key and value exactly, so any token can be recalled precisely; an SSM or RWKV compresses the history into a fixed-size state and fails exact recall, hence hybrids such as Jamba (6.3).

   3. Cost: RAG sends a few excerpts. Self-Route asks the model whether the excerpts suffice and sends the full context only when they do not: comparable quality for 39% to 65% less cost (3.4).

2. Question (6 points). A draft model’s tokens are accepted with probability 0.8 each. (a) With a draft length of 4, compute the expected number of tokens per target pass (Theorem 7.2). (b) One draft step costs 0.1 target step, so an iteration with draft length \gamma costs 0.1\gamma + 1. Compute the speedup for draft lengths 2, 4, 6 and 7, and give the best one. (c) Two models are 0.5 points apart on a 500-question benchmark. Give the 95% Hoeffding half-width of each accuracy and conclude.

   Expected: (a) (1 - 0.8^5)/0.2 = 3.36 tokens. (b) The speedup is the expected number of tokens divided by the iteration cost: \frac{2.44}{1.2} = 2.03, \quad \frac{3.36}{1.4} = 2.40, \quad \frac{3.95}{1.6} = 2.47, \quad \frac{4.16}{1.7} = 2.45, so the best draft length is 6, and the curve is flat between 5 and 7.

   3. By Theorem 0.3 of Machine Learning, the half-width is \sqrt{\frac{\ln(2/0.05)}{2 \cdot 500}} \approx 0.061, about 6 points, twelve times the gap: the ranking says nothing.

3. Question (5 points). For the Switch loss of Proposition 5.2: (a) with four experts, f = (0.7, 0.1, 0.1, 0.1) and P = (0.6, 0.2, 0.1, 0.1), compute the loss divided by its weight, and compare with uniform routing. (b) Prove that the loss is at least its weight when the loads and the router masses are similarly ordered. (c) Redo (a) with two experts, f = (0.9, 0.1) and P = (0.45, 0.55). What does the result say about the loss?

   Expected: (a) the sum of the products is 0.42 + 0.02 + 0.01 + 0.01 = 0.46, so the ratio is 4 \times 0.46 = 1.84, above the value 1 of uniform routing. (b) Chebyshev’s sum inequality, as in the proof of Proposition 5.2: the average of the products is at least the product of the averages, which is the square of the inverse number of experts.

   3. The sum is 0.405 + 0.055 = 0.46 and the ratio 2 \times 0.46 = 0.92 < 1: an anti-monotone pair goes below the “minimum”. The bound needs co-monotone sequences; the loss is a load proxy, whose gradient (equal to the load) still pushes the loaded experts down.

4. Question (4 points). In ring attention (Proposition 3.4), a device receives the key/value blocks one at a time and updates its running maximum, normalizer and output. Prove by induction that after the last block, the output divided by the normalizer is the exact softmax attention over the whole sequence. Why multiply by e^{m - m'} at each update?

   Expected: invariant after the blocks seen so far: m is their largest score, \ell = \sum e^{s - m} and O = \sum e^{s - m} v. It holds at the start (empty sums, m = -\infty). At an update the old sums are moved to the new reference by the factor e^{m - m'} and the new block adds its terms.

   At the end the common factor e^{-m} cancels in O/\ell, leaving the softmax-weighted average of the values. The rescaling keeps every exponent at most 0 (no overflow) and puts old and new terms on one reference.

Grading rubric (proposal)

The rubric grades the continuous part (portfolio and project); the written exam, if an instructor uses it, is graded on its own.

References

• Reasoning. J. Wei et al., Chain-of-Thought Prompting Elicits Reasoning in Large Language Models, NeurIPS 2022; X. Wang et al., Self-Consistency Improves Chain of Thought Reasoning in Language Models, ICLR 2023; H. Lightman et al., Let’s Verify Step by Step, ICLR 2024; DeepSeek-AI (D. Guo et al.), DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning, 2025 (also in Nature, 2025); N. Lambert et al., Tulu 3: Pushing Frontiers in Open Language Model Post-Training, 2024; Y. Yue et al., Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?, NeurIPS 2025.
• Long context. J. Su et al., RoFormer: Enhanced Transformer with Rotary Position Embedding, 2021; S. Chen et al., Extending Context Window of Large Language Models via Positional Interpolation, 2023; B. Peng et al., YaRN: Efficient Context Window Extension of Large Language Models, 2023; H. Liu, M. Zaharia, P. Abbeel, Ring Attention with Blockwise Transformers for Near-Infinite Context, NeurIPS 2023; N. F. Liu et al., Lost in the Middle: How Language Models Use Long Contexts, TACL 2024; Z. Li et al., Retrieval Augmented Generation or Long-Context LLMs? A Comprehensive Study and Hybrid Approach, EMNLP 2024 industry; P. Xu et al., Retrieval meets Long Context Large Language Models, ICLR 2024.
• Memory. Y. Wu et al., Memorizing Transformers, ICLR 2022; J. S. Park et al., Generative Agents: Interactive Simulacra of Human Behavior, UIST 2023; C. Packer et al., MemGPT: Towards LLMs as Operating Systems, 2023; D. Edge et al., From Local to Global: A Graph RAG Approach to Query-Focused Summarization, 2024 (cf. Graph ML module ch. 10); A. Maharana et al., Evaluating Very Long-Term Conversational Memory of LLM Agents (LoCoMo), 2024.
• MoE. N. Shazeer et al., Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer, ICLR 2017; W. Fedus, B. Zoph, N. Shazeer, Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity, JMLR 2022; A. Q. Jiang et al., Mixtral of Experts, 2024; DeepSeek-AI, DeepSeek-V3 Technical Report, 2024.
• Alternative architectures. A. Gu, K. Goel, C. Ré, Efficiently Modeling Long Sequences with Structured State Spaces (S4), ICLR 2022; A. Gu, T. Dao, Mamba: Linear-Time Sequence Modeling with Selective State Spaces, 2023; B. Peng et al., RWKV: Reinventing RNNs for the Transformer Era, Findings of EMNLP 2023; S. De et al., Griffin: Mixing Gated Linear Recurrences with Local Attention for Efficient Language Models, ICML 2024; O. Lieber et al. (AI21), Jamba: A Hybrid Transformer-Mamba Language Model, 2024; G. E. Blelloch, Prefix Sums and Their Applications, technical report CMU-CS-90-190, Carnegie Mellon University, 1990.
• Efficiency. Y. Leviathan, M. Kalman, Y. Matias, Fast Inference from Transformers via Speculative Decoding, ICML 2023; C. Chen et al., Accelerating Large Language Model Decoding with Speculative Sampling, 2023; E. Frantar, S. Ashkboos, T. Hoefler, D. Alistarh, GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers, ICLR 2023; J. Lin et al., AWQ: Activation-aware Weight Quantization for LLM Compression and Acceleration, MLSys 2024; Y. LeCun, J. S. Denker, S. A. Solla, Optimal Brain Damage, NeurIPS 2 (1990); B. Hassibi, D. G. Stork, Second Order Derivatives for Network Pruning: Optimal Brain Surgeon, NeurIPS 5 (1993).
• LLMs × graphs (the LLGA core). H. Wang et al., Can Language Models Solve Graph Problems in Natural Language? (NLGraph), NeurIPS 2023; B. Fatemi, J. Halcrow, B. Perozzi, Talk like a Graph: Encoding Graphs for Large Language Models, ICLR 2024; X. He et al., G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering, NeurIPS 2024; S. Pan et al., Unifying Large Language Models and Knowledge Graphs: A Roadmap, IEEE TKDE 2024; W. Chen et al., Large Language Models on Graphs: A Comprehensive Survey, 2023; J. Tang et al., GraphGPT: Graph Instruction Tuning for Large Language Models, SIGIR 2024; R. Chen, T. Zhao, A. Jaiswal, N. Shah, Z. Wang, LLaGA: Large Language and Graph Assistant, ICML 2024; Z. Sun, Z.-H. Deng, J.-Y. Nie, J. Tang, RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space, ICLR 2019; L. Yao, C. Mao, Y. Luo, KG-BERT: BERT for Knowledge Graph Completion, 2019; L. Yao, J. Peng, C. Mao, Y. Luo, Exploring Large Language Models for Knowledge Graph Completion, 2023 (ICASSP 2025); Y. Wei, Q. Huang, J. T. Kwok, Y. Zhang, KICGPT: Large Language Model with Knowledge in Context for Knowledge Graph Completion, Findings of EMNLP 2023.
• Agents. S. Yao et al., ReAct: Synergizing Reasoning and Acting in Language Models, ICLR 2023; T. Schick et al., Toolformer: Language Models Can Teach Themselves to Use Tools, NeurIPS 2023; N. Shinn et al., Reflexion: Language Agents with Verbal Reinforcement Learning, NeurIPS 2023; Q. Wu et al., AutoGen: Enabling Next-Gen LLM Applications via Multi-Agent Conversation, 2023; G. Li et al., CAMEL: Communicative Agents for “Mind” Exploration of Large Language Model Society, NeurIPS 2023.
• Evaluation. C. Xu, S. Guan, D. Greene, M.-T. Kechadi, Benchmark Data Contamination of Large Language Models: A Survey, 2024; L. Zheng et al., Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena, NeurIPS 2023; P. Wang et al., Large Language Models are not Fair Evaluators, ACL 2024; P. Liang et al., Holistic Evaluation of Language Models (HELM), TMLR 2023.
• Open problems. P. Villalobos, A. Ho, J. Sevilla, T. Besiroglu, L. Heim, M. Hobbhahn, Will we run out of data? Limits of LLM scaling based on human-generated data, ICML 2024 (first version 2022; Epoch AI project); I. Shumailov et al., AI models collapse when trained on recursively generated data, Nature 2024; H. Yu et al., Continual Learning of Large Language Models: A Comprehensive Survey, 2024.