iiinova — where your digital self keeps evolving

Alex Lew @alexlew.bsky.social · 06/07/2025

As a way of evaluating the model (rather than the variational family or inference method)

Alex Lew @alexlew.bsky.social · 06/07/2025

By contrast, of course, a good VI method should give good posteriors. If better posteriors give worse predictions, it's the model's fault, not the VI method's

110

Alex Lew @alexlew.bsky.social · 06/07/2025

Yes, I agree... It's a very (non-Bayesian) ML-inflected way of looking at things, where the whole game is to maximize predictive accuracy on new data, and the training data D is just instrumental to this goal.

110

Alex Lew @alexlew.bsky.social · 06/07/2025

Right, I think if you're trying to estimate P*, it's okay that Method 2 is inconsistent. The way you "spend more compute" in Method 2 is by choosing a bigger/more expressive variational family q, not taking more samples from a fixed variational family. So consistency isn't quite the right property

100

Alex Lew @alexlew.bsky.social · 06/07/2025

Oh -- I agree it doesn't make sense to choose q1 or q2 based on the quantity! Or at least, if you do that, you're just fitting the model q(θ)p(D'|θ) to the held-out data D', not doing posterior inference anymore.

110

Alex Lew @alexlew.bsky.social · 05/07/2025

(Though even if you use approach 2, it is probably better to use q as a proposal within IS, rather than using it directly to substitute the posterior)

110

Alex Lew @alexlew.bsky.social · 05/07/2025

We can't sample p(θ|D) exactly, so consider two procedures for sampling θ from distributions _close_ to p(θ|D): 1 - run MCMC / SMC / etc. targeting p(θ|D) 2 - run VI to obtain q(θ) then draw independent θs from q via simple MC Not obvious that Method 1 always wins (for a given computational budget)

120

Reposted by Alex Lew

Tomer Ullman @tomerullman.bsky.social · 22/05/2025

not sure how to get this across to non-academics but here goes, Imagine if you were suddenly told 'we decided not to pay your salary', that's kind of what the grant cuts felt like. Now imagine if you were suddenly told 'we are going to set your dog on fire', that's what this feels like:

1836091

Reposted by Alex Lew

Ben Lipkin @benlipkin.bsky.social · 13/05/2025

Want to use AWRS SMC? Check out the GenLM control library: github.com/genlm/genlm-... GenLM supports not only grammars, but arbitrary programmable constraints from type systems to simulators. If you can write a Python function, you can control your language model!

161

Reposted by Alex Lew

Ben Lipkin @benlipkin.bsky.social · 13/05/2025

Many LM applications may be formulated as text generation conditional on some (Boolean) constraint. Generate a… - Python program that passes a test suite. - PDDL plan that satisfies a goal. - CoT trajectory that yields a positive reward. The list goes on… How can we efficiently satisfy these? 🧵👇

2136

Reposted by Alex Lew

João Loula @joaoloula.bsky.social · 25/04/2025

#ICLR2025 Oral How can we control LMs using diverse signals such as static analyses, test cases, and simulations? In our paper “Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo” (w/ @benlipkin.bsky.social, @alexlew.bsky.social, @xtimv.bsky.social) we:

176

Alex Lew @alexlew.bsky.social · 25/02/2025

I'd love to see these ideas migrated to Gen.jl! But there are some technical questions about how best to make that work.

000

Alex Lew @alexlew.bsky.social · 25/02/2025

Hi, thanks for your interest! The pedagogical implementations can be found at: Julia: github.com/probcomp/ADE... Haskell: github.com/probcomp/ade... The (less pedagogical, more performant) JAX implementation is still under active development, led by McCoy Becker.

120

Alex Lew @alexlew.bsky.social · 10/02/2025

- Daphne Koller had arguably the first PPL paper about inference-in-Bayesian-models-cast-as-programs - Alexandra Silva has great work on semantics, static analysis, and verification of probabilistic & non-det. progs - Annabelle McIver does too - Nada Amin has cool recent papers on PPL semantics

091

Alex Lew @alexlew.bsky.social · 10/02/2025

DeepSeek's implementation isn't public, and maybe I'm misinterpreting their paper. But the TRL reimplementation does appear to follow this logic. github.com/huggingface/... Curious what people think we should make of this! 8/8

github.com

trl/trl/trainer/grpo_trainer.py at 55e680e142d88e090dcbf5a469eab1ebba28ddef · huggingface/trl

Train transformer language models with reinforcement learning. - huggingface/trl

030

Alex Lew @alexlew.bsky.social · 10/02/2025

The usual KL penalty says: try not to wander outside the realm of sensible generations [as judged by our pretrained model]. This penalty says: try not to lose any of the behaviors present in the pretrained model. Which is a bit strange as a fine-tuning objective. 7/

271

Alex Lew @alexlew.bsky.social · 10/02/2025

When we differentiate their (Schulman's) estimator, pi_ref comes back into the objective, but in a new role. Now, the objective has a CrossEnt(pi_ref, pi_theta) term. KL(P,Q) = CrossEnt(P,Q) - Entropy(P), so this is related to KL, but note the direction of KL is reversed. 6/

$**Mathematical formulation of an alternative KL estimator and its gradient.** The alternative KL estimator is defined as: \[ \widehat{KL}_\theta(x) := \frac{\pi_{\text{ref}}(x)}{\pi_\theta(x)} + \log \pi_\theta(x) - \log \pi_{\text{ref}}(x) - 1 \] From this, it follows that: \[ \mathbb{E}_{x \sim \pi_{\text{old}}} [\nabla_\theta \widehat{KL}_\theta(x)] = \nabla_\theta \mathbb{E}_{x \sim \pi_{\text{old}}} \left[ \frac{\pi_{\text{ref}}(x)}{\pi_\theta(x)} + \log \pi_\theta(x) \right] \] Approximating when $\pi_{\text{old}} \approx \pi_\theta$, we get: \[ \approx \nabla_\theta \mathbb{E}_{x \sim \pi_{\text{ref}}} [-\log \pi_\theta(x)] + \nabla_\theta \mathbb{E}_{x \sim \pi_{\text{old}}} [\log \pi_\theta(x)] \] The annotated explanation in purple states that this results in: \[ \text{CrossEnt}(\pi_{\text{ref}}, \pi_\theta) - \text{CrossEnt}(\pi_{\text{old}}, \pi_\theta) \] where $\text{CrossEnt}(\cdot, \cdot)$ denotes cross-entropy. ---- alt text generated by ChatGPT$

131

Alex Lew @alexlew.bsky.social · 10/02/2025

Interestingly, if they were *not* using this estimator, and instead using the standard estimator, pi_ref would not affect the gradient at all! More evidence that there's something odd about their approach. And maybe one reason they turned to Schulman's estimator. 5/

$**Mathematical explanation of the standard KL estimator and its gradient.** The standard KL estimator is defined as: \[ \widehat{KL}_\theta(x) := \log \pi_\theta(x) - \log \pi_{\text{ref}}(x) \] From this, it follows that: \[ \mathbb{E}_{x \sim \pi_{\text{old}}} [\nabla_\theta \widehat{KL}_\theta(x)] = \nabla_\theta \mathbb{E}_{x \sim \pi_{\text{old}}} [\log \pi_\theta(x)] \] Annotated explanation in purple states that this term represents the *negative cross-entropy from $\pi_{\text{old}}$ to $\pi_\theta$.* -- alt text automatically generated by ChatGPT$

130

Alex Lew @alexlew.bsky.social · 10/02/2025

This means GRPO is not optimizing the usual objective. What objective *is* it optimizing? Well, it depends on the particular KL estimator they are using. A few people have noticed that GRPO uses a non-standard KL estimator, from a blog post by Schulman. 4/

$Text from the GRPO paper: And different from the KL penalty term used in (2), we estimate the KL divergence with the following unbiased estimator (Schulman, 2020): KL(pi_theta || pi_ref) = pi_ref(o_{i,t} | q, o_{i,<t}) / pi_theta(o_{i,t} | q,o_{i,<t}) - log pi_ref(o_{i,t} | q, o_{i,<t}) / pi_theta(o_{i,t} | q,o_{i,<t}) - 1 which is guaranteed to be positive.$

120

Alex Lew @alexlew.bsky.social · 10/02/2025

GRPO instead directly differentiates the KL estimator, evaluated on samples taken from pi_old (the LM before this update). But the point of policy gradient is that you can't just "differentiate the estimator": you need to account for the gradient of the sampling process. 3/

$**Mathematical formulation of the GRPO (Group-Relative Policy Optimization) objective and its gradient.** The objective function is defined as: \[ J_{\text{GRPO}}(\theta) = \mathbb{E}_{x \sim \pi_\theta} [R_\theta(x)] - \beta \cdot \mathbb{E}_{x \sim \pi_{\text{old}}} [\widehat{KL}_\theta(x)] \] The gradient of this objective is: \[ \nabla J_{\text{GRPO}}(\theta) = \nabla_\theta \mathbb{E}_{x \sim \pi_\theta} [R_\theta(x)] - \beta \cdot \mathbb{E}_{x \sim \pi_{\text{old}}} [\nabla_\theta \widehat{KL}_\theta(x)] \] Annotated explanations in purple indicate that the first term is *unbiasedly estimated via the group-relative policy gradient*, while the second term is *not* the derivative of the KL divergence, even when $\pi_{\text{old}} = \pi_\theta$. ---- (alt text automatically generated by ChatGPT)$

150

Alex Lew @alexlew.bsky.social · 10/02/2025

RL for LMs often introduces a KL penalty term, to balance the "maximize reward" objective with an incentive to stay close to some reference model. A way to implement is to modify the reward, so E[R~]=E[R] - KL term. Then you can apply standard RL (e.g. policy gradient). 2/

$**Mathematical expression describing KL-penalized reinforcement learning objective.** The objective function is given by: \[ J(\theta) = \mathbb{E}_{x \sim \pi_\theta} [R_\theta(x)] - \beta \cdot D_{\text{KL}}(\pi_\theta, \pi_{\text{ref}}) \] Rewritten as: \[ J(\theta) = \mathbb{E}_{x \sim \pi_\theta} [\tilde{R}_\theta(x)] \] where: \[ \tilde{R}_\theta(x) := R_\theta(x) - \beta \cdot \widehat{KL}_\theta(x) \] \[ \widehat{KL}_\theta(x) := \log \pi_\theta(x) - \log \pi_{\text{ref}}(x) \] Annotations in purple indicate that $ R_\theta(x) $ represents the reward, and $ \widehat{KL}_\theta(x) $ is an unbiased estimator of the KL divergence. ---- (alt text generated by ChatGPT)$

150

Alex Lew @alexlew.bsky.social · 10/02/2025

@xtimv.bsky.social and I were just discussing this interesting comment in the DeepSeek paper introducing GRPO: a different way of setting up the KL loss. It's a little hard to reason about what this does to the objective. 1/

Also note that, instead of adding KL penalty in the reward, GRPO regularizes by directly adding the KL divergence between the trained policy and the reference policy to the loss, avoiding complicating the calculation of the advantage.

3509

Alex Lew @alexlew.bsky.social · 30/12/2024

Yeah — would be interesting to know if the pattern holds for today’s larger models! (This paper was done 1.5 years ago, in academia, using open models)

010

Alex Lew @alexlew.bsky.social · 30/12/2024

Furthermore, regardless of training procedure, the models are still autoregressive probabilistic sequence models, so they can be understood as optimal “autocompleters” for *some* data distribution. “If this is our conversation so far, what word would an assistant probably say next?”

020

Alex Lew @alexlew.bsky.social · 30/12/2024

Hm, I think the base LMs are quite interesting. From the DPO paper: sampling 128 completions from a base model, and then selecting the sample with highest reward under the RLHF reward model, performs similarly to actual RLHF.

A plot from the Direct Preference Optimization paper, comparing various methods of aligning LMs to preference data.

230

Alex Lew @alexlew.bsky.social · 08/12/2024

If you're interested in a PhD at the intersection of machine learning and programming languages, consider applying to Yale CS! We're exploring new approaches to building software that draws inferences and makes predictions. See alexlew.net for details & apply at gsas.yale.edu/admissions/ by Dec. 15

Probabilistic and differentiable programming at Yale — fully funded PhD positions starting Fall 2025! Apply by Dec. 15.

Do a PhD at the rich intersection of programming languages and machine learning.

17322

Alex Lew @alexlew.bsky.social · 28/11/2024

Agreed re GMMs, but fitting latent-variable generative models is a fundamental problem in ML, and I suspect variational and adversarial approaches will both be in textbooks many years from now—even if no one uses, e.g., vanilla VAEs for image generation

071

Alex Lew @alexlew.bsky.social · 25/11/2024

Maybe you'd count it as "indirect utility" but most of those papers were written *for* peer review, which likely encouraged authors to do more thorough experiments, be more careful with their claims, read more of the related work, etc. (Of course writing "for review" can also have negative effects.)

080

Reposted by Alex Lew

Eugene Vinitsky 🍒 @eugenevinitsky.bsky.social · 23/11/2024

Kind of a broken record here but proceedings.neurips.cc/paper_files/... is totally fascinating in that it postulates two underlying, measurable structures that you can use to assess if RL will be easy or hard in an environment

e introduce the effective horizon, a property of
MDPs that controls how difficult RL is. Our analysis is mo-
tivated by Greedy Over Random Policy (GORP), a simple
Monte Carlo planning algorithm (left) that exhaustively ex-
plores action sequences of length k and then uses m random
rollouts to evaluate each leaf node. The effective horizon
combines both k and m into a single measure. We prove
sample complexity bounds based on the effective horizon that
correlate closely with the real performance of PPO, a deep
RL algorithm, on our BRIDGE dataset of 155 deterministic
MDPs (right).

815029

Alex Lew @alexlew.bsky.social · 23/11/2024

I'm not against text-to-speech as, e.g., a browser plug-in, or a way to increase accessibility for people who prefer to listen than to read. But it sucks to see big media companies replacing talented voice actors with this way-inferior AI narration

100

Alex Lew @alexlew.bsky.social · 23/11/2024

Yeah, text-to-speech has clearly made great strides and the better ones are not "robotic" per se. But like, listen to Sedaris above and then listen to one of the New Yorker AI voices, e.g. here. It's a generic voice-from-nowhere, with no personality

newyorker.com

Why A.I. Isn’t Going to Make Art

To create a novel or a painting, an artist makes choices that are fundamentally alien to artificial intelligence.

100

Alex Lew @alexlew.bsky.social · 23/11/2024

The New Yorker used to have human narrators do pretty great audio versions of selected articles. But then they quietly switched to generic, lifeless AI (with no indication until you click "Listen"). Occasionally they'll still have a human reader, like Sedaris here, and the contrast is insane

281

Reposted by Alex Lew

Evan Peck @peck.phd · 20/11/2024

Trying something new: A 🧵 on a topic I find many students struggle with: "why do their 📊 look more professional than my 📊?" It's *lots* of tiny decisions that aren't the defaults in many libraries, so let's break down 1 simple graph by @jburnmurdoch.bsky.social 🔗 www.ft.com/content/73a1...

921577458

Alex Lew @alexlew.bsky.social · 21/11/2024

(and - measure-valued optimization does not imply that you are approximating a measure - measure-valued approximation of a measure does not imply that you are optimizing)

130

Alex Lew @alexlew.bsky.social · 21/11/2024

hmm, you think "approximation" is a subset of "optimization"? I think of IS/SMC e.g. as unbiased measure-valued estimators of a measure (each run produces a random measure, and on average, it is equal to the target). To me, variational implies "measure-valued optimization for measure approximation"

230

Reposted by Alex Lew

xuan (ɕɥɛn / sh-yen) @xuanalogue.bsky.social · 21/11/2024

mixtures of circuit approximations of algorithms, I tell you! kernel methods in the space of (short, propositional) programs!! why memorize and interpolate answers when you can memorize and interpolate answer-producing procedures??

2275

Alex Lew @alexlew.bsky.social · 21/11/2024

hahah wow! new algorithm for character-level surprisals: ask a human who (1) knows the language in question and (2) stares at logprobs all day

120

Alex Lew @alexlew.bsky.social · 21/11/2024

(Beyond the title, @xtimv.bsky.social gave a talk at MIT last week about the algorithm they're using to compute these character-level surprisals, efficiently marginalizing over possible tokenizations, and it's really cool!)

050

Alex Lew @alexlew.bsky.social · 21/11/2024

Surprisal of title beginning with 'O'? 3.22 Surprisal of 'o' following 'Treatment '? 0.11 Surprisal that title includes surprisal of each title character? Priceless [...I did not know titles could do this]

Screenshot of the title of the paper "On the Proper Treatment of Tokenization in Psycholinguistics." Over each letter, the authors have plotted the surprisal of the letter (-log p(this letter | context)).

2102

Alex Lew @alexlew.bsky.social · 20/11/2024

yep! (see also Monte Carlo EM) seems like one reasonable way to understand the relationship between VI and VAEs (VI used to approximate the intractable p(data; params))

030

Alex Lew @alexlew.bsky.social · 20/11/2024

Fair 😅 I think if you see “inference” as both “getting the posterior” and “getting the marginal likelihood,” then it makes sense to see this as VI: we get the marginal using VI, then (separately?) optimize it. Maybe not “classical VI,” though back in the day people did do e.g. “Variational EM”!

100

Alex Lew @alexlew.bsky.social · 20/11/2024

there are applications like the VAE, where you are fitting a latent-variable model to data via MLE-ish means, and using VI to approximately marginalize the latent variable. Can view as minimizing KL(p_data(y) * q_latent(x | y; phi) || p_model(x, y; theta)) wrt phi and theta

110

Alex Lew @alexlew.bsky.social · 20/11/2024

Thanks!! Wasn't involved in this project (this is @xuanalogue.bsky.social and Lance Ying) but I appreciate it :) Excited to follow your stuff at .txt as well!

030

Alex Lew @alexlew.bsky.social · 19/11/2024

This is a very cool integration of LLMs + Bayesian methods. LLMs serve as *likelihoods*: how likely would the human be to have issued this (English) command, given a particular (symbolic) plan? No generation, just scoring :) A Bayesian agent can then resolve ambiguity in really sensible ways

Examples of the CLIPS agent from Zhi-Xuan, Ying et al. 2024 resolving ambiguity in human instructions.

27217

Alex Lew @alexlew.bsky.social · 18/11/2024

It's interesting just how recent this shift was. Autodiff existed but hadn't been adopted by the ML community. Justin Domke had a blog post in 2009 lamenting that so many papers claimed "an efficient algorithm for gradients" as a key technical contribution justindomke.wordpress.com/2009/02/17/a...

justindomke.wordpress.com

Automatic Differentiation: The most criminally underused tool in the potential machine learning toolbox?

Update: (November 2015) In the almost seven years since writing this, there has been an explosion of great tools for automatic differentiation and a corresponding upsurge in its use. Thus, happily,…

3425

Alex Lew @alexlew.bsky.social · 18/11/2024

Hi Bluesky! My claim to fame is the development of the Alexander Hamiltonian Monte Carlo algorithm. Younger researchers may not realize due to Moore's Law (Lin-Manuel Miranda becomes roughly half as cool every two years), but back when this was published in 2021, it was considered mildly topical

Algorithm box from the joke paper "Alexander Hamiltonian Monte Carlo."

A proof of the main theorem from the paper, which is that the algorithm "eventually converges to the room where it happens, if the user is willing to wait for it."

2446