Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End

0:00What if I told you that in artificial intelligence, making a problem 10 ,000 times longer doesn't actually make it any harder to learn. Yeah, it sounds totally counterintuitive. Seriously. Imagine trying to solve a maze. You'd think a maze with 10 ,000 turns is, you know, mathematically harder to master than a maze with just 10 turns. Oh, absolutely. We are totally conditioned to believe longer tasks are inherently more complex to teach. But when we look at the mathematical bedrock of how AI models actually generate thoughts, well, that assumption gets turned completely upside down. Right. And that is exactly what this deep dive is all about today.

0:38Whether you're building these systems or maybe you're trying to get better outputs from them at work or you're just like insanely curious about how thinking is mathematically quantified, you're going to get a massive aha moment today about the architecture of learning. Yeah, we are looking at the math of sample complexity, which is literally just the number of training examples you need to teach a system to hit a specific level of accuracy. Exactly. We're diving into how an AI learns to reason by looking at two totally different teaching methods. You've got end-to-end supervision, where you only reward the final answer, and then chain-of-thought supervision, where you reveal all the hidden intermediate steps.

1:15And I love this because we aren't just talking about theory here. We are looking at rigorous mathematical proofs of how learning scales. But before we get to the cheat code that breaks those scaling rules, we really need to define the playing field. Right. The foundation of modern large language models is built on something called autoregressive generation. Okay, let's unpack this. Autoregressive generation. It sounds intimidating, but at its core, how does it actually work? So autoregressive simply means producing things one at a time based on what you've already produced. Think of an underlying next token generator.

1:49Its entire job, like its only job, is to look at a sequence of tokens. And those could be words or numbers, right? Exactly. Words, numbers, whatever. It maps out the very next single token. So it's like my phone predicting the next word in my text message over and over again. It doesn't write the whole sentence at once. It just guesses the, then it guesses dog, then barked. Precisely. And when you force a system to iterate that process for a certain number of steps, you get a chain of intermediate tokens. Let's call that number of steps the generation length, or just T. Okay, Kate, got it. So if you ask an AI to solve a complex logic puzzle and it takes 50 distinct steps to reach the final answer, your generation lengths, your T, is 50.

2:30Okay, I have my T. Now, how do we actually teach the system to get the right answer at the end of that 50-step chain? The research highlights a brilliant analogy here. Oh, the master mathematician analogy. I love this one. Yeah, imagine trying to learn advanced math from a master mathematician. There are two distinct ways you could approach your apprenticeship. The first is the end-to-end method, E2E. Right. In this scenario, you ask the master a question. The master goes into a locked room, thinks for an hour, and slides a perfectly polished final proof under the door. You only ever see the input and the final output.

3:04Which is a really stark contrast to the second method, which is chain of thought supervision, or QTT. In this apprenticeship, you are actually sitting in the room with the master mathematician. You witness the whole process. Exactly. You see the intermediate ideas, the scratch pad calculations, the false starts. You see the examples they test, the approaches they abandon, the partial structures they build. You are observing the entire internal trajectory that connects the initial question to the final answer. Wait, let me push back here for a second. Isn't end-to-end what machine learning has traditionally relied on for years?

3:40It is, yeah. Like you feed an input into a neural network, it gives an output, and you basically punish or reward it based on whether that final output was right or wrong. It's how we train computers to play chess or recognize pictures of cats. Right. Why do we need a completely new mathematical framework to tell us how that works? Well, it's a fantastic question, and you're right. Traditional machine learning thrived on the end-to-end model. But chess moves and image recognition are very different from long-form reasoning. How so? Because as tasks become more complex, that generation length, our variable t, grows significantly.

4:15And the math shows us that as t grows, the traditional end-to-end method hits a brutal bottleneck. If a system is generating a massive chain of reasoning, holding it accountable only for the final output creates mathematical friction. So because it's generating the answer step-by-step, but only getting a grade at the very end, it doesn't know which of its 50 steps actually caused it to fail. Exactly. The mathematics prove that learning just the final answer after a long chain of hidden thoughts requires exponentially more effort. In statistical terms, it demands a vastly higher sample complexity.

4:49We need to know exactly how much harder it gets to learn a process as the number of reasoning steps increases. Okay, let's dig into that scaling wall. If I'm teaching an AI using just the final answer, so end-to-end, how bad does the math actually get as T gets longer? Well, in the end-to-end regime, the sample complexity scales with T. But what the findings reveal is that it doesn't just scale in one predictable way. There is a remarkably rich taxonomy of growth rates. A taxonomy of growth rates. What does that look like? Subject to some mild conditions, the difficulty can grow at any rate between a flat constant and a linear rate.

5:23They call it a monotone-sabbatative rate. Monotone-sabbatative. Meaning what, exactly? Monotone means it only goes one direction, right? And it only gets harder. Yes, the difficulty goes up as the problem gets longer. But the curve of how it gets harder is incredibly varied depending on the specific type of problem. Oh, I see. Like for one type of logic puzzle, making the problem 10 times longer might only require twice as much training data. That's a logarithmic growth. For another problem, making it 10 times longer might require 10 times the data, which is linear growth. And it can be essentially any mathematical curve in between those two bounds.

6:00So if T is the number of turns in a maze, end-to-end learning is like being blindfolded and pushed into the maze. Right. You make 50 turns, and at the end, someone just yells wrong or right. The longer the maze, the harder it is to blindly guess the correct sequence. But what you're saying is, depending on the shape of the maze, the difficulty scales differently. What's fascinating here is that that is a brilliant way to visualize it. And the mathematical landscape of this end-to-end scaling is so diverse, so infinitely varied, that the mathematicians had to use something called a diagonalization argument just to prove a negative about it.

6:35A diagonalization argument. That sounds like graduate-level geometry. What does that actually mean? It's a classic, very elegant technique in mathematical analysis. Imagine you have an infinite list of numerical sequences, and you want to find a single master sequence that will eventually outpace or dominate every single one of them. Okay, following you so far. The diagonalization argument proves that no matter what master sequence you propose, I can always construct a new sequence that evades it. I'm trying to picture this. Is it kind of like an unbeatable game of rock, paper, scissors? Exactly like that, yeah.

7:08Like, if I'm trying to find one single master move that wins every time, you can mathematically prove that no matter what move I pick, you can always construct the exact counter move to beat me. Yes, that is exactly the dynamic. In this context, the researchers wanted to know if there was a single combinatorial dimension or a single mathematical rule that could characterize all these different ways that end-to-end learning gets harder. And the diagonalization argument proves that no such single rule exists. Right. The landscape of how the difficulty grows is simply too complex. You cannot capture all the ways the sample complexity might grow with just one mathematical parameter.

7:49Okay, so end-to-end learning scales poorly, and worse, its difficulty is incredibly unpredictable as the problem gets longer. It's a mess. Total mess. If we are trying to build AI that can reason through thousands of steps, the blindfold method isn't going to cut it, which opens the door to the alternative. what mathematically happens when we take the blindfold off. Ah, what happens when we expose all those hidden steps using chain of thought supervision. Yeah, exactly. This is where the mathematics completely flip. With chain of thought supervision, the sample complexity becomes completely independent of the generation length T.

8:23Here's where it gets really interesting. Independent. Completely. Like, zero penalty. Completely independent. It does not matter if the reasoning chain is 10 steps long or 10 ,000 steps long. Wow. The number of examples you need to learn the underlying rules of the task does not increase with the length of the problem. Having access to those intermediate reasoning steps completely eliminates the penalty for long generation lengths. That is wild. If you're prepping for a massive presentation at work, this is like realizing you don't need to memorize the entire 50-page slide deck, which is the end-to-end way.

9:00Right. You just need to learn the underlying core framework the author used to write the slides, which is the chain of thought way. That's a great way to put it. But how does that actually work mechanically? How does seeing the steps literally erase the length penalty in the math? It comes down to a mathematical mechanism we can call inflation. Let's walk through it. Think about a single chain of thought example where the system takes 50 steps to reach an answer. In an end-to-end model, that is just one single training example. We have the starting prompt and the final output at step 50. But in a chain of thought model, because you see every step, you can take that single 50-step demonstration and inflate it into 50 separate ordinary training examples for your base generator.

9:40Oh, I see. Because at step 1, it sees the prompt and learns the first token. Then at step 2, the input is the prompt plus the first token, and it learns the second token. Exactly. You learn step 1. Then you learn step 2, given step 1. Then you learn step 3, given steps 1 and 2. one long 50-step demonstration isn't just one lesson it provides a wealth of individual bite-sized lessons for the next token generator so you are learning the core rules of generation directly at every single node rather than trying to guess the overarching rule from the final outcome yes and when it has all these individual lessons it can do something the math refers to a stable sample compression schemes I know we are throwing around big terms today but let's ground this.

10:24Yeah. What is the system actually compressing? When you have a massive data set of these step-by-step lessons, a stable sample compression scheme allows the system to identify a very small, highly stable subset of crucial examples that define the entire rule set. Okay. So it's like finding the load-bearing pillars of a building. You don't need to memorize the exact location and weight of every single brick to understand how the building stands up. Exactly. If you can just identify the four or five critical load-bearing pillars, you've essentially compressed the structural blueprint of the whole building.

10:58That is a perfect analogy. Because Chain of Thought provides such direct, step-by-step data, the system can optimally identify those load-bearing pillars, the fundamental rules of the logic, without getting bogged down by the sheer number of bricks or the length of the generation. It achieves an optimal learning state. Okay, I'm sold on Chain of Thought. This complete independence from the length of T sounds like a mathematical cheat code. But I have to ask, it sounds almost too good to be true. Are there scenarios where this magic trick breaks down? Like, are there problems where even showing the work doesn't help?

11:30This raises an important question. And yes, there are pathological edge cases, and the mechanics of why they break down are fascinating. The chain of thought cheat code only works if the base class of knowledge is inherently learnable in the first place. Inherently learnable? How do we know if something is learnable? In learning theory, we measure this learnability using something called the VC dimension. You can think of VC dimension as a measurement of constraints. If a problem space has a finite VC dimension, it means there are actual underlying rules to be learned. It is constrained. So a finite VC dimension means the problem isn't just random noise.

12:07There is a pattern to be found. What happens if the VC dimension is infinite? If the base class is totally unconstrained, meaning it has an infinite VC dimension, chain of thought learning is utterly impossible. You can show the system every step of the process forever, and it will never learn to generalize because there are no stable underlying rules driving the next token. That makes intuitive sense to me. Total chaos cannot be learned, even if you watch the chaos unfold step by step. If I show you 100 videos of dice being rolled, it doesn't matter how closely you watch the intermediate bounces, you can't predict the next roll.

12:42Exactly. But the mathematical findings point out a deeply bizarre quirk when you look at these unconstrained, infinite dimension problems. Yeah, this is where the math gets genuinely strange. For some of these completely unconstrained, unlearnable classes, the ability to learn oscillates wildly based purely on whether the generation length, RT variable, is an even or an odd number. Wait, wait, wait, you're losing me. Just based on parity. Odd or even. Yes. The mathematics prove that for some of these pathological problems, if the generation length T is an even number, the problem suddenly becomes trivially learnable using end-to-end supervision.

13:20In fact, its VC dimension drops to zero, meaning you literally require zero training examples to know the answer. Hold on. How do you learn something with zero examples just because the length is an even number? Explain the mechanism there. Okay. Think about a mechanism like a simple light switch. But imagine the rule of the system forces the switch to be flipped at every single step. If the switch starts in the off position and your generation length T is an even number, say two steps or 50 steps. Right, if it's back and forth. Exactly. You mathematically know with absolute certainty that the switch will end up back in the off position.

13:55The specific structure of the pathological problem collapses on itself at even intervals. The output becomes completely predictable regardless of the input, so it requires zero examples to learn. Okay, I see. Because it's an even number of steps, the actions cancel each other out, and I don't need any data to know the final state. But what happens if we change T to an odd number? If you change T to an odd number, if you just add one single step to the generation length, the problem becomes entirely unlearnable. With an odd number of steps, the switch ends up in the on position, but the system relies on an unconstrained variable that was introduced during the sequence.

14:34Even with full chain of thought supervision, no amount of data can teach the system the rules because the underlying base class is still infinite. It goes from requiring zero examples to being mathematically impossible to learn just by changing the length from even to odd. That is deeply unsettling. It means we cannot just blindly throw data at an AI and assume that showing it the steps will magically teach it to reason. Right, we can't. We have to mathematically guarantee that the problem space has constraints. Otherwise, we fall into these pathological traps where learning breaks down over something as trivial as whether a number is odd or even.

15:12Exactly. It highlights the danger of assuming AI can learn anything. And this brings up the need to measure those constraints, especially when we are forced to use end-to-end learning. Because sometimes we don't have the chain of thought data. Sometimes we only have the final answers. Right. So to understand how bad the scaling will be in those cases, the mathematicians introduced a new combinatorial tool called the autoregressive tree dimension. Okay, the autoregressive tree dimension. Let's visualize this. I'm assuming we are talking about a literal decision tree. Yes, imagine drawing a massive decision tree on a whiteboard.

15:44You start with a single prompt at the root. From there, every possible first word the AI could generate branches out. Then, from each of those words, every possible second word branches out. So very quickly, you get a massive, sprawling tree of every possible sequence of thoughts the system could have. Right, the tree of possibilities. So what is the autoregressive tree dimension actually looking for inside that massive tree? It is looking for something specific called perfectly embedded leveled subtrees. Okay, translate that for me. What does a perfectly embedded leveled subtree look like on my whiteboard?

16:20It means looking for a section of the tree that branches infinitely and symmetrically in every direction, with no dead ends and, well, no constraints. If a system has a finite autoregressive tree dimension, it means its generation tree does not look like that. Okay, so it has dead ends. Exactly. It means the tree has structural constraints. It has dead ends. It doesn't branch perfectly infinitely. And why do we care if the tree has dead ends? Because if the tree is constrained in this specific way, if the autoregressive tree dimension is finite, the mathematics provide a safety net. It guarantees that the end-to-end sample complexity will only grow logarithmically rather than linearly.

16:58Ah. Logarithmic growth is much more manageable. So if the tree of possibilities isn't perfectly dense and infinitely branching, end-to-end learning might actually survive a longer chain of thought. Right. Making the problem 10 times longer might only require a tiny bit more data instead of 10 times more data. It's not as efficient as the chain of thought cheat code, but it means the problem doesn't become impossible. Precisely. The tree dimension gives us a mathematical guarantee that the difficulty won't explode completely out of control as the reason gets longer, as long as that tree dimension is finite.

17:33So what does this all mean? We've waded through some incredibly dense foundational mathematics today. We started with the idea of learning from a master mathematician, and we've unpacked how teaching an autoregressive system isn't just about throwing final products at a neural network. It really isn't. The math unequivocally proves that exposing the internal trajectory of thought, the chain of thought, fundamentally rewrites the rules of sample complexity. It completely severs the tied relationship between how long a problem is and how difficult it is to learn. And if we pull back to the big picture, it proves that the future of complex problem solving relies heavily on showing the work, not just outputting the final answers.

18:13By revealing the intermediate steps and allowing the system to inflate those steps into distinct lessons, we bypass the immense mathematical friction that makes end-to-end learning so costly and unpredictable over long reasoning chains. Which leaves you with a final reflection to mull over today. The strict mathematics of machine learning have essentially proven that exposing a vulnerable, intermediate chain of thought is the absolute most efficient way to achieve mastery. If exposing the internal trajectory of thought is the mathematical key to overcoming hard limits in artificial intelligence, what does that imply about our own human communication?

18:48Think about how you operate. The next time you're trying to persuade a colleague or teach someone a complex new skill, ask yourself, are you just handing them your polished end-to-end conclusion and expecting them to just figure it out? Or are you actually brave enough to share your chain of thought?