Talks

Abstract: What does it actually take to train a strong language model? Published research makes it look clean: strategic architecture choices, carefully curated data, enough compute, and a tidy set of ablations where every decision seems obvious in hindsight. But those reports are written with a fair bit of rosy retrospection. They don't capture the 2 a.m. debugging sessions, the loss spikes that appear from nowhere, or the subtle tensor-parallelism bug that quietly sabotages a run for days. The reality is messier and more iterative, and most of the decisions that actually mattered never make it into the final paper. In this lecture I'll walk through the nuts and bolts of training an LLM end to end, from pretraining over trillions of tokens to post-training with reinforcement learning. 

Speaker's Bio: Lewis is a Senior Research Scientist at Hugging Face, where he leads the post-training team to develop fully open models, datasets, and training recipes for the AI community. In a former life he was a theoretical physicist studying the low-energy sector of the Standard Model and developing precision tests for indirect dark matter searches.

This seminar is part of the CERN STEAM Academy Seminar Series. 

Networking cocktail will follow the seminar. 

00:00:00 Slide 1
00:02:02 Slide 2
00:04:16 Slide 3
00:04:34 Slide 4
00:06:38 Slide 5
00:08:14 Slide 6
00:09:37 Slide 7
00:11:07 Slide 8
00:12:40 Slide 9
00:13:54 Slide 10
00:14:59 Slide 11
00:15:15 Slide 12
00:16:10 Slide 13
00:17:18 Slide 14
00:18:21 Slide 15
00:19:00 Slide 16
00:20:38 Slide 17
00:23:29 Slide 18
00:28:31 Slide 19
00:29:50 Slide 20
00:30:11 Slide 21
00:30:38 Slide 22
00:33:01 Slide 23
00:34:23 Slide 24
00:36:02 Slide 25
00:37:31 Slide 26
00:39:30 Slide 27
00:40:27 Slide 28
00:43:13 Slide 29
00:44:22 Slide 30
00:46:02 Slide 31
00:46:51 Slide 32
00:49:10 Slide 33
00:50:40 Slide 34
00:51:19 Slide 35
00:54:06 Slide 36
00:54:21 Slide 37
00:54:35 Slide 38
00:55:36 Slide 39
00:56:02 Slide 40
00:58:53 Slide 41
01:01:11 Slide 42
01:01:39 Slide 43
01:04:28 Slide 44
01:06:26 Slide 45
01:06:38 Slide 46
01:06:52 Slide 47
01:07:51 Slide 48
01:08:17 Slide 49
01:08:30 Slide 50
01:09:26 Slide 51
01:10:17 Slide 52
01:11:34 Slide 53
01:13:29 Slide 54
01:16:42 Slide 55
01:19:25 Slide 56
01:19:59 Slide 57
01:22:25 Slide 58
01:22:41 Slide 59
01:24:56 Slide 60
01:25:33 Slide 61
01:27:05 Slide 62
01:28:16 Slide 63
01:29:55 Slide 64
01:31:11 Slide 65
01:32:37 Slide 66

The red-blue pebble game is a well known two-player game on graphs that has been used in the past as a tool to analyze complexity measures in several computation models as well as proof systems. We define a new way to measure the cost of the game, the blue cost, which only counts the number of pebbles that are colored blue during the game. This new measure characterizes exactly several space bounds in tree-like and negative Resolution.

In particular we prove that for any unsatisfiable formula $F$, the clause space requirements of the formula in tree-like Resolution, exactly coincide with the minimum blue pebbling cost of the game played on a refutation graph of $F$ (not necessarily a tree). This exactly parallels the known result for general Resolution in terms of the standard black pebble game, and improves the existing approximated characterization of tree-like space in terms of reversible pebbling.

We show that the blue pebbling cost is also well suited for analyzing the space requirements of the lifted pebbling formulas $Peb_G[\vee]$ and $Peb_G[\oplus]$ in the two Resolution restrictions. In the case of tree-like Resolution, the clause space of $Peb_G[\vee]$ asymptotically coincides with the blue cost of the underlying graph $G$.
For the case of negative Resolution, we obtain almost matching upper and lower bounds for the space in the two classes of lifted formulas, similar to the ones existing for general Resolution.

We also prove a close to optimal space separation between tree-like and negative Resolution, presenting a class of formulas with $n$ variables that require clause space $\Omega(\frac{n}{\log n})$ in negative Resolution, but have constant space tree-like refutations. This contrasts with the fact that negative Resolution can simulate tree-like Resolution with a small increase in size.

The Lovász-Theta function of a graph is an important function which can be used to analyze several fundamental properties of a graph. In particular, the Lovász-Theta function is an upper bound on the Shannon capacity of a graph and the Lovász-Theta function of the complement of a graph is always between the clique number and the chromatic number of the graph.
 
For a random G(n,1/2) graph, it has long been known that the Lovász-Theta is a constant times the square root of n but the exact constant was unknown. In this work, we resolve this question by showing that with high probability, the Lovász-Theta function of a random graph is (1+o(1)) times the square root of n.

To prove this result, we give an intricate and novel construction of a candidate solution for the dual SDP for the Lovász-Theta function and show that with high probability, it is feasible and has value (1+o(1)) times the square root of n. In this talk, I will describe our construction and give intuition for why it works.

The weak rank principle formalises the following algebraic fact: a matrix $A$ cannot be factorised as the product $XY$ when $X$ has fewer columns than the rank of $A$. We study the complexity of this principle in algebraic proof systems and show that it can be used as a proof complexity generator, with applications to the hardness of lower bound formulas.

An overview of recent developments in topological methods for use in separating pseudodeterministic and randomized communication complexity as well as tightly determining the sign rank of the gap-hamming problem.

Techniques involve Z2-equivariant topology and the design of replicable learning algorithms.

Linearity testing is a fundamental property testing problem with many applications to several areas of TCS. It can be construed as testing for "polymorphisms" of the ternary Boolean predicate EvenParity. We prove an analogous statement for all predicates over the Boolean alphabet, and for some predicates over larger finite alphabets. Joint work with Yaroslav Alekseev appearing in FOCS 2026 (under the title "Approximate Polymorphisms").

Consider the following algorithm for finding a falsified clause of an unsatisfiable CNF formula, given an assignment: sequentially check each clause to see if it is falsified. As the formula is unsatisfiable, the algorithm clearly finds a falsified clause. However, proving that this algorithm is correct (outputs a falsified clause on every unsatisfiable CNF formula) is tantamount to showing NP=coNP! In this talk we will look at provably correct algorithms which find falsified clauses for subsets of unsatisfiable formulas, and show that these are equivalent to certain strong proof systems. Doing so will allow us to prove that two strong, and seemingly different, proof systems G1 and implicit resolution are polynomially equivalent, and develop a theory of provable reductions in TFNP.

We study the average-case hardness of establishing that a graph does not have a large clique in both proof and communication complexity. We show exponential lower bounds on the length of cutting planes and bounded-depth resolution over parities refutations of the binary encoding of clique formulas on randomly sampled dense graphs. Moreover, we show that the randomized communication complexity of finding a falsified clause in these formulas is polynomial.

Based on joint work with de Rezende, Engström, Ghannane, and Riazanov that appeared at ICALP'26.

"We exhibit supercritical trade-off for monotone circuits, showing that
there are functions computable by small circuits for which any small
circuit must have depth superlinear or even super-polynomial in the number
of variables, far exceeding the linear worst-case upper bound.  We obtain
similar trade-offs in proof complexity, where we establish the first
size-depth trade-offs for cutting planes and resolution that are truly
supercritical, i.e., in terms of formula size rather than number of
variables, and also show supercritical trade-offs between width and size
for treelike resolution.
  
Our results build on a new supercritical width-depth trade-off for
resolution, obtained by refining and strengthening the compression scheme
for the cop-robber game in [Grohe, Lichter, Neuen, and Schweitzer 2023].
This yields robust supercritical trade-offs for dimension versus iteration
number in the Weisfeiler–Leman algorithm, which also translate into
trade-offs between number of variables and quantifier depth in first-order
logic.  Our other results follow from improved lifting theorems that might
be of independent interest.

This is joint work with Susanna F. de Rezende, Noah Fleming, Duri Andrea
Janett, and Shuo Pang presented at STOC '25."

Circuit complexity lower bounds for explicit functions are hard to prove. This has been true anecdotally but has also been backed up by the Natural Proof Barrier framework of Razborov and Rudich, which views lower bound proofs as computational tasks. It states that assuming the existence of a pseudorandom function generator supported on small circuits there is no "natural" lower bound proof that a function does not have a small circuit.

When restricting to constant depth circuits we are able to prove far stronger, subexponential, lower bounds. However improvements on these lower bounds have also been anecdotally hard to prove. We note that most state-of-the-art lower bound proofs for constant depth circuits are computational tasks that are computable by polysize constant depth circuits. More generally, we show that they are "AC0-natural". We then show that "AC0-natural" lower bound proofs cannot significantly improve the state of the art lower bounds. Notably we show this unconditionally by providing a construction of pseudorandom function generators supported on constant depth circuits of subexponential size that fool ALL polysize constant depth circuits. This is proven via the best known lower bounds against constant depth circuits, thereby using the lower bound itself to prove the hardness of improving the lower bound.

"Consider a data structure problem with possible data coming from a set
$\mathcal D$, queries coming from a set $\mathcal Q$, and in the dynamic
case updates coming from a set $\mathcal U$. Then, the current state of
the art in data structure lower bounds is
$t = \tilde\Omega(\log |\mathcal Q|)$ for static data structure
problems, and
$\max(t_{\mathrm q},t_{\mathrm u}) = \tilde\Omega((\log n)^2)$ where
$n = \max(|\mathcal Q|,|\mathcal U|,\log |\mathcal D|)$ for dynamic.

We port Razborov and Rudich's natural-proofs framework to the setting of
static and dynamic data structures in the cell probe model, in a way
that strongly suggests this state of the art is unlikely to be improved
anytime soon. A similar direction was recently taken also by Korten,
Pitassi and Impagliazzo (FOCS 2025) who look at static data structure
lower bounds in a different regime of parameters. Our contribution is:

-   We define notions analogous to pseudorandom functions (PRF). We call
    these primitives *local PRFs*, in the context of static data
    structures, and *local and locally updatable (LLU) PRFs*, in the
    context of dynamic data structures.
-   We then formulate cryptographic conjectures, namely, that secure
    local PRFs and secure LLU PRFs exist, precisely at the frontier
    where we are no longer able to prove static, respectively dynamic,
    data structure lower bounds. If these conjectures are true, it
    follows that the current state of the art in data structure lower
    bounds cannot be improved by a natural proof.
-   We show that (almost) every single known data structure lower bound
    proof is a natural proof, by surveying all lower bounds in the
    literature (known to us). (The only exception is proofs based on
    lifting theorems.)
-   It follows that, if our cryptographic conjecture is true, then all
    known lower bound proof techniques (minus the two exceptions) are
    unable to improve upon the state of the art. (We also present
    obstacles for the two exceptions.)
-   Further, we provide concrete candidate constructions for our two
    pseudo-random primitives. We conjecture that our constructions are
    secure for parameters just above the state-of-the-art lower bounds.
-   We also show that, whether or not they are secure, our candidate
    PRFs at least satisfy the natural properties appearing in all (but
    one) known proofs.
-   So if one is interested in improving upon the state of the art in
    static or dynamic data structure lower bounds, one must either find
    a non-natural method of proving such lower bounds (no such method
    currently exists), or one may as well begin by trying to break our
    PRF candidates."