Astra appears to perform belief-propagation-like inference without CoT

tl;dr I tested GPT-6 Astra on randomized Boolean logic problems. Astra can solve surprisingly complex logic problems without chain-of-thought, and its performance improves significantly with more filler tokens. Astra is also able to combine prior probabilities with constraints to find the most likely solution, and can output surprisingly accurate posterior marginal probabilities. By extending a cached prompt with progressively more filler tokens, I created visualizations of Astra's per-variable confidence scores at different points in the computations. These values tend to oscillate for a while and then eventually converge toward the marginal probabilities. Together, these results suggest that Astra performs some kind of iterative, belief-propagation-like probabilistic inference internally. In my previous post, I hypothesised that Astra (and to a lesser extent other LLMs) may be performing some form of speculative reasoning when solving specially crafted logic problems without chain-of-thought, and provided some experimental results supporting this hypothesis. One question those experiments didn't answer is whether Astra is keeping track of not just the speculative values of intermediate results, but also its level of confidence in them. If Astra is doing the latter, speculative evaluation turns into something much more powerful: a form of belief propagation. Belief propagation, also known as sum-product message passing, is an algorithm that can be used (among other things) as a heuristic for certain boolean satisfiability problems, and to decode some error-correction codes such as LDPC codes. I'm not going to explain the whole algorithm here, but the general idea is that you can feed this algorithm the prior probabilities that some variables are true or false, combined with a series of constraints on those variables, and it attempts to calculate the posterior marginal probabilities of each variable (that is, the probability that an individual variable is true once the constraints are taken into consideration). It does this by repeatedly updating its beliefs by passing messages back and forth between constraints and variables. It is exact when the relevant factor graph is cycle-free, though when there are cycles involved it is only an approximation. In practice, the algorithm works well even in many cases with cycles. For many problems, there is one joint assignment (= combination of boolean values) whose posterior probability is much higher than the others, such that the posterior marginal probabilities of the individual variables are dominated by that one assignment. In those cases, thresholding the marginal probabilities often recovers that assignment, which makes it a powerful heuristic for finding the most likely solution to the problem. There is also a simplified approximate variant of belief propagation known as the min-sum algorithm, which directly targets the most likely solution, and requires no mathematical operations more complicated than sum/difference and min/max. If LLMs are internally doing something like a crude form of belief propagation, they might be unusually good at exactly the types of problems that this algorithm is commonly used for. So, I ran some experiments that attempt to measure exactly that. Decoding BCH codes Belief propagation is commonly used to decode LDPC codes, so this would be an obvious candidate test. However, this is not really practical: most LDPC codes use block sizes of hundreds or thousands of bits, which means thousands of different variables that need to be tracked - this seems way too ambitious for an LLM benchmark, let alone a no-CoT benchmark. Instead I decided to use BCH codes, a much smaller type of error-correcting code which can be easily generated with various sizes and properties. Belief propagation isn't commonly used for such small codes because there exist better specialized techniques, but it's a much more reasonable test case for an LLM benchmark. BCH codes are configurable: I can choose how much redundancy is added, and consequently how many incorrect bits can be corrected. For this experiment I set the number of correctable errors to 2, because with just 1 correctable error it degenerates to Hamming codes, which are relatively simple to solve, so they wouldn't provide much evidence that belief propagation is being used. To reduce the chance of benchmark contamination issues, I'm randomizing the BCH code construction rather than using standard ones. Also, I'm not actually telling the LLM that this is a BCH code. I'm just giving it the equivalent logic problem, which looks like this: Full prompt (example with 10 variables) Answer immediately with one tuple and nothing else. Exactly 2 of these expressions are incorrect: a = True, b = True, c = False, d = False, e = True, f = False, g = True, h = False, i = True, j = True The following expressions are all correct: d xor e xor j = True a xor c xor d xor e xor h = False d xor f xor h xor j = False b