Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference

0:00Imagine you're staring down a massively complex puzzle, right? One of those sprawling thousand-step monstrosities. Oh, yeah. The ones where one wrong move at, like, step four means the whole thing just collapses at step 900. Exactly. And historically, dealing with a puzzle like that meant you just had to guess your way to the very end, place the final piece, and only then do you realize you messed up hours ago. So you sweep the pieces off the table, sigh, and, you know, start completely over. It's incredibly frustrating. Right. But imagine a different scenario. Imagine you have a little angel sitting on your shoulder and at every single step, before you even commit your hand to placing a piece, that angel whispers in your ear.

0:42This is nudging you away from the dead ends. Yeah, steering you toward the paths that actually lead to the solution. You never waste your time marching down a doomed timeline. And that dynamic, that real-time step-by-step guidance is the fundamental shift happening right now at the absolute leading edge of artificial intelligence. It really is. It's a massive departure from how we typically interact with these systems. I mean, if you look at the broader landscape of AI, there's been this obsession with training compute just pumping endless data into a model for months and hoping it gets smarter.

1:15Right. But what we are looking at today is a shift toward inference compute. We're moving away from treating a trained model as a black box that just instantly spits out a finished product. Instead, we're actively, you know, invading the generation phase, intervening while the AI is in the middle of thinking. So welcome to today's deep dive. We are getting into the architecture of reasoning today. The overarching topic is exploring this technique called sequential Monte Carlo or SMC and how it uses process reward models to course correct an AI token by token. And just to set the expectations for you listening, we aren't talking about some clever prompting trick here or like an ad hoc software hack.

1:55No, not at all. Our mission today is to unpack the rigorous mathematical blueprints, the hard theoretical computer science, and honestly, the incredibly strange ways that real world math problems completely fracture those theoretical rules. Yeah, that part is wild. But to really appreciate why SMC is making such waves, we kind of have to look at the incredibly wasteful baseline it replaces. Okay, let's start there. The baseline. Right. So the baseline is a method called best of N. And to understand why it's so inefficient, you have to remember that generating tokens, you know, those individual chunks of words an AI produces, is a sequential computationally expensive process.

2:35Every single word costs GPU power. Exactly. So let's say you give an AI a brutal logic puzzle. In the best event approach, the AI generates, say, 32 complete, entirely independent answers. It runs 32 separate tracks all the way to the finish line. It does. And then at the very end of the process, a separate evaluation model looks at those 32 finished products and just picks the best one. Wow. So you're willingly paying the computational tax to generate 32 full sequences, knowing with absolute certainty that 31 of them are going straight into the trash. Right. And the tragedy is many of those discarded sequences probably made a fatal logic error on the very first sentence.

3:12But the algorithm blindly forced the model to generate the remaining four paragraphs anyway, burning compute on a ghost. I mean, if we think about the AI's generation process like running a maze, Best of N feels completely absurd. It's like taking 32 mice, blindfolding them and just dumping them at the entrance. Just letting them loose. Yeah. They run blindly, bouncing off walls, committing to terrible pests, and you just stand at the exit with your fingers crossed, hoping at least one of them accidentally stumbles onto the cheese. It is a computationally disastrous use of mice. Highly inefficient.

3:44So let's contrast that with guided generation. This uses what's called a process reward model, or PRM. So instead of standing at the exit of the maze waiting to judge the final outcome, a PRM evaluates the AI's work token by token or step by step. Right. It numerically scores the partial generations as they're happening. And this is where sequential Monte Carlo, or SMC, steps in as the operational engine. It's a particle filtering algorithm. Okay, particle filtering. Yeah. So in this context, think of each partial generation, like each attempt at a sentence as a particle. As the underlying language model generates tokens, the SMC algorithm asks the PRM to evaluate those particles in real time.

4:25And if it gets a bad score. If a particle gets a low score, meaning it's heading down a bad path, SMC adaptively prunes it. It terminates that specific generation track immediately. But if a particle gets a high score, SMC replicates it. It multiplies the promising paths. Oh, so this is the walkie-talkie upgrade for our mice. Exactly. Under SMC, the mice aren't blindfolded anymore. Every few feet, they check in with central command. And the mice that hit a dead end, they don't just stay there bumping into the wall. the system instantly teleports them to the exact location of the mice who are making great progress.

4:58And once they teleport to that strong position, they clone themselves and the whole pack keeps searching outward from there. The teleporting mice analogy captures the core mechanic perfectly. I mean, it's all about the reallocation of computational power. Compute is a finite resource, so you want to spend your processing budget exploring the neighborhoods of good ideas. Right. By killing off the doomed paths early, SMC frees up the AI to explore, like, slight nuanced variations of the paths that are actually working. Exactly. Okay, so the mechanics of pruning and cloning make intuitive sense. But intuition is cheap in computer science.

5:37How do we mathematically guarantee that this works? I mean, it's one thing to say we prune the bad paths. But if we're operating in a space of near-infinite possible word combinations, how do we prove the algorithm will actually find the right answer without needing infinite computing power? And that is the crux of the math here. The blueprint establishes what are known as non-asymptotic guarantees. Non-asymptotic, okay. Right, in plain English, that just means we don't need infinite time or infinite particles to calculate our margin of error. We can predict exactly how well the algorithm will perform using a finite number of particles like your 32 mice.

6:12Got it. And the math proves this works by identifying two strict non-negotiable criteria, basically two pillars that must stand for the whole thing to hold up. Okay. Let's test the foundation. What's the first pillar? The first is bounded action level coverage. Essentially, the base language model must possess the foundational capability to generate the correct next step on its own, at least, you know, a fraction of the time. Okay, so if a specific word or logical step is absolutely required to solve a problem, the base model's internal probability of generating that word cannot be zero. Right.

6:48You can't reward a mouse for taking the correct left turn if the mouse physically does not possess the ability to turn left. If the underlying AI doesn't have the raw knowledge buried somewhere in its weights, the most brilliant process reward model in the world has nothing to amplify. Precisely. You cannot amplify a zero probability. So assuming the base model has bounded action-level coverage, we move to the second pillar, which is bounded chi-square divergences. Bounded chi-square divergences. Yeah. This rule governs the PRM itself, the judge. When the PRM looks at a partial sequence, it's estimating the expected final reward.

7:24The rule dictates that this estimate must be reasonably close to the true expected reward, on average. Okay, wait. I have to pause you there and push back on this idea of reasonably close. because we are dealing with AI judges. Anyone who has used a language model knows they hallucinate. Oh, absolutely. They get confused by context, they lose the plot, and they will confidently give an absolutely terrible answer, a perfect score. So if the PRM is the angel on the shoulder, what happens when the angel has a psychotic break? Doesn't a wildly hallucinated score cause the whole teleporting mice system to collapse because suddenly you're cloning bad paths and pruning the correct ones?

8:02It is the most vital vulnerability to question, and honestly, addressing it is where the math in this framework truly shines. The beauty of the bounded chi-square divergence criterion is that it tolerates what statisticians call heavy-tailed errors. Heavy-tailed errors. Yeah, meaning the PRM does not have to be flawless. In fact, it can occasionally be spectacularly, catastrophically wrong. But how does it survive that? If it heavily rewards a grommage path, shouldn't the algorithm flood all its compute into that garbage path? It survives because Chai-square divergence measures average case closeness, not worst case closeness.

8:38Oh, I see. Yeah. As long as the PRM's scoring distribution generally aligns with reality across the aggregate, the algorithm mathematically absorbs those rare, massive hallucinations. The errors just get washed out by the sheer volume of particles making good average case decisions. That feels incredibly robust. We have a system that can tolerate a flawed base model by printing its mistakes, and it can tolerate a hallucinating judge by relying on the statistical aggregate. But in reading through this architecture, there is a massive bottleneck, right? Even with both pillars standing, standard sequential Monte Carlo hits a mathematical wall based entirely on being short-sighted.

9:18Ah, yes, the bottleneck of myopia. It is one of the most counterintuitive findings in the whole thing. The math reveals that even if you possess a mythical, 100 % perfect process-reward model like, A judge that never hallucinates and perfectly scores every single step standard SMC still demands an enormous computational budget. Really? Yeah. Specifically, the number of particles required has to scale with the square root of the horizon length. It's written as big omega square root of H. Okay. With the horizon length being the total number of steps or tokens in the entire sequence. So if I have an output that requires a thousand tokens, I can't just use a handful of particles.

9:59I have to scale my compute dramatically just to not fail, even with a flawless judge. Why? Where is the friction coming from if the judge isn't making mistakes? Well, the friction comes from how standard SMC decides who lives and who dies. It normalizes weights. When those particles check in, the algorithm doesn't evaluate them in a vacuum. It normalizes their scores against the rest of the group. Because they're evaluated relatively, the particles actually interfere with each other. Oh, wow. Yeah. If one particle happens to get a very high score early on, the normalization process mathematically suppresses the weights of all the other particles.

10:33It aggressively prunes them, which leads to a catastrophic collapse in diversity. You end up with all your mice clumped on one path, effectively blinding you to other potentially better routes. So the particles are essentially cannibalizing each other's compute based on early relative success. How do we stop them from competing? The researchers solved this by introducing a variant called sequential Monte Carlo with rejection sampling, or SMCRS. Rejection sampling? Yes. They abandoned the relative normalization entirely. Instead of comparing particles against each other, SMCRS evaluates each particle completely independently against the PRM's absolute standard.

11:13Okay, how does rejection sampling actually do that in practice? Think of it like a dice roll. When a particle completes a step, the PRM gives it a score, say 80%. In rejection sampling, the algorithm essentially rolls a metaphorical 100-sided die. Because the score is 80, the particle has an 80 % chance of surviving to the next round. Oh, I get it. Yeah. It doesn't matter if every other particle scored a 99 or if every other particle scored a 2. Its survival is based solely on its own merit. By removing the interference, if your PRM is highly accurate, SMCRS allows you to sample the exact correct distribution using drastically fewer particles.

11:51So it cures the cannibalization. But even with rejection sampling saving us from that square root scaling, there's still a hard mathematical floor you cannot drop below if your algorithm is myopic, right? Meaning it can only see the current step in the past with zero visibility into the future. Exactly. The math proves that for any myopic particle filtering algorithm dealing with a slightly imperfect PRM, you cannot succeed with a small handful of particles. You absolutely need a specific logarithmic number of particles specifically, big omega of log h over log log h, just to avoid total system failure.

12:25Because without foresight, you are entirely at the mercy of momentary errors. Let me put this in a real world context for you listening. Being myopic in this algorithm is like driving a car in incredibly dense fog. You can only see about five feet in front of your bumper. Your PRM is a GPS on your dashboard. That's a great analogy. Now, your GPS is generally good, but it has a slight margin of error. If you only send one car out into the fog and the GPS glitches for a fraction of a second while you are driving alongside a cliff edge, you're going into the ravine. Game over. And that is exactly why the math demands a fleet.

13:03Because you cannot see the road ahead to verify the GPS's current instruction, you need multiple cars exploring slightly different lanes simultaneously. If you have a wide enough fleet, which that logarithmic formula strictly dictates based on the length of the road trip when the GPS inevitably makes a slight error in one lane, only a few cars go off the cliff. The rest of the fleet survives to catch the GPS's next correction and find the true road. It's brilliant. The math lays out exactly how big your fleet needs to be to survive the fog. But, you know, theory and formulas look beautiful on a whiteboard.

13:36Language isn't a whiteboard. Language is messy, subjective. It's full of weird edge cases. How do you actually test rigorous mathematical bounds on an AI writing text? It requires a highly controlled environment. because the core problem with testing language models is that you usually do not know the exact mathematical target distribution of a good answer. Let's define target distribution for a second. If I ask an AI to write a poem, the target distribution would be an impossibly massive theoretical spreadsheet mapping out the perfect probability for every single word in the English language that could appropriately come next to make it a good poem.

14:13Right. But because good is subjective, that spreadsheet doesn't actually exist for us to check against. Exactly. So to test the math, they had to manufacture a scenario where they did know the exact spreadsheet. They created a prompt switching task using the Quinn 30.6B language model. Okay, prompt switching. Yeah. They started by feeding the AI a creative reference prompt. For example, write a scene about a dragon negotiating peace with the last human kingdom. The AI begins generating probabilities based on a fantasy narrative. You know, dragons, swords, peace treaties. But then they intervene.

14:46They switch the target. They mathematically command the system, tell it as a news article. Oh. Yeah, by doing this, they explicitly define the exact mathematical difference between the reference distribution, the fantasy story, and the new target distribution, the news article. Because they possess the exact probabilities of both, they could intentionally dial the accuracy of the PRM up and down. They injected precise amounts of mathematical noise into the judge to see how the SMC algorithm would react. See, this is where I would expect things to get incredibly messy. You are injecting pure mathematical noise into a creative writing task about a dragon.

15:21I'd expect the AI to just start outputting schizophrenic gibberish that completely breaks the formulas. But it didn't. The theoretical metrics perfectly predicted the real-world sampling error. When they artificially worsened the action-level coverage, the real-world error rate of the SMC algorithm tracked the mathematical prediction beautifully. That's crazy. And when they altered the chi-square divergence by making the PRM more erratic, the error rate again moved in lockstep with the theory. And they measured the success using a very specific lens called the P-log prob discrepancy, right? They didn't just have another AI read the story and give it a thumbs up or thumbs down.

15:58No. They looked directly into the model's internal probability, dials its log probabilities to mathematically calculate exactly how far the SMC's output deviated from that perfect theoretical spreadsheet of a news article. It proved that the dense theoretical computer science actually governs the messy reality of language generation. It completely confirmed the framework. The math dictates the reality. Which makes the final phase of this so mind-bending to me. The theory worked flawlessly for the dragon story. The math predicted the reality perfectly, but then they took this exact same system and they pointed it at something far less subjective than creative writing.

16:37They aimed it at the hardest math problems in the world, and the theory completely fractured. It is a phenomenal contradiction. They put the SMC algorithm up against the best event baseline on two notoriously grueling mathematical benchmarks. AEE, which is the American Invitational Mathematics Examination used to find human math prodigies, and Math 500. Okay, so putting the mice into a maze with incredibly high stakes, what were the results? Well, on a practical level, it was a massive success. SMC using 32 particles consistently crushed the best event approach across almost all individual problems.

17:14Actively allocating compute to promising mathematical steps mid-generation works far better than brute forcing full answers. Right. But behind the scenes, the theoretical metrics were screaming that something was wrong. But chi-square divergence. Yes. They were tracking the chi-square divergence, the mathematical measure of how accurate the PRM is compared to the perfect target distribution. According to all the beautiful theory we just laid out, and according to the Dragon Story experiment, a higher theoretical error should guarantee worse performance. The worse your judge is, the worse your output should be.

17:45Right. But on these Amy math problems, it was the exact opposite. A higher theoretical error actually resulted in higher accuracy. I genuinely struggled to wrap my head around this when I was reading it. the worse the PRM fit the theoretical model, the better the AI got at actually solving the complex math problem. How is a mathematically worse judge producing better math? It's driven by a mechanism called inverse temperature, which controls how harsh the PRM behaves. Think of inverse temperature like a bouncer at a club. If you use a high temperature, the bouncer's relaxed. He lets in a diverse crowd, even if they aren't dressed perfectly.

18:22Mathematically, a relaxed PRM creates It's a broad, smooth distribution that closely matches the theory. But when they lowered the temperature, they made the bouncer incredibly harsh and unforgiving. He kicks out anyone who isn't wearing a perfect tuxedo. So a harsh PRM brutally weeds out any particle that looks even slightly incorrect. Right. But mathematically, this extreme harshness destroys the chi-square divergence. It radically warps the probabilities, making the PRM look terribly inaccurate and spiky, according to the smooth theoretical formulas. But practically, that ruthless behavior solved the problems better.

18:59But why does destroying the theoretical distribution help solve the problem? Because of the fundamental nature of the task. The mathematical theory assumes your goal is to perfectly stand by the entire distribution of all possible good answers. Like when writing a news article about a dragon, there are thousands of valid, creative ways to write it, and the theory wants the algorithm to capture that entire diverse spectrum of possibilities accurately. You want a broad distribution, but math is binary. The AI doesn't need to write a creative symphony about how 2 plus 2 equals 4. It just needs to output 4.

19:30Precisely. You do not need a beautifully diverse distribution of various mathematical proofs. You just need one single correct answer. When the harsh PRM ruthlessly kills off the particles, it ruins the broad theoretical distribution, yes. But it acts as an incredible filter for finding a single needle in a haystack. It's the difference between exploring a city to draw a comprehensive, highly accurate tourist map versus frantically searching for your lost keys. If you're drawing the map, you need to capture every alleyway, every coffee shop, and every park with perfect proportion. Exactly. That's what the original theory and the dragon story were doing, mapping the whole space of valid answers.

20:10But if you just want to find your lost keys, you don't care about accurately mapping the rest of the city. You search ruthlessly, and the second you find the keys, the search is over. The harsh PRM doesn't care about mapping the space of all possible mathematical proofs. It just wants the keys. That is the perfect way to conceptualize the disconnect. The rigorous framework they built captures how to approximate a target distribution perfectly. It's a triumph of theory. But the empirical results on the math tasks challenge us to invent an even newer theoretical framework. Wow. Yeah, we need new math that doesn't care about perfectly modeling a distribution, but only cares about the probability of covering at least one correct path.

20:51It shows that in AI, the mathematical theory and the empirical reality are locked in a constant push and pull. Every time we establish a hard rule, the models find a bizarre practical way to make us rewrite it. It is a wild frontier. So bringing all of this together for you listening, we have explored a massive structural shift today. We're watching inference time computing evolve AI from blindly guessing tokens sequentially to actively reasoning via particle filtering. We unpacked how the math proves SMC works, relying on bounded coverage and tolerating heavy-tailed errors from hallucinating judges.

21:24We explored the absolute necessity of rejection sampling to cure particle cannibalization. And most interestingly, we saw how real-world math tasks defy the original formulas, proving that when you only need one right answer, a ruthless, theoretically inaccurate judge is actually the best tool for the job. The transition from predicting to reasoning is happening step by step, particle by particle. Absolutely. And that brings me to a final thought for you to mull over. We spent a lot of time today talking about that myopic limitation, the mathematical proof that because these algorithms can only see the current step in the past, they're doomed to need a massive fleet of particles to survive the fog.

22:05Yeah. But what happens when we crack the code on look-ahead PRMs? Imagine an AI that doesn't just evaluate the step it's currently on, but can pre-simulate the ripple effects of a single word 10 paragraphs down the line before it even types the next letter. If myopia is the ultimate bottleneck forcing us to use massive compute, the transition from just predicting the next word to actively simulating the future is going to rewrite the rules of intelligence entirely. Think about it.