Information Theory for ML13 / 16

Module 13. Reasoning in LLMs: computation, search, and information

Choose your answers and select “Check”. Numbers accept a decimal point, comma, or simple fraction. Answers and drafts are saved in this browser and shared between RU/EN.

Checked: 0 / 25 · Correct: 0

Question 13.1.1

13.1. What changes when a model “thinks longer”

Which statement best describes a long reasoning chain?

One correct optionAIt is always proof of understandingBIt can serve as a scratchpad, but by itself guarantees neither correctness nor causal faithfulnessCIt necessarily contains external facts absent from the promptDReasoning quality is determined only by token count

A) It is always proof of understanding

B) It can serve as a scratchpad, but by itself guarantees neither correctness nor causal faithfulness

C) It necessarily contains external facts absent from the prompt

D) Reasoning quality is determined only by token count

Answer and explanation

Correct answer: B. Trajectory length is a computational resource and an observable artifact, not a correctness certificate.

Question 13.2.1

13.2. Amortization, scratchpads, and search

When does sequential generation become explicit search?

One correct optionAWhen the answer contains a formulaBDuring any autoregressive generationCWhen temperature is zeroDWhen the system preserves alternatives, receives feedback, or can revise an earlier choice

A) When the answer contains a formula

B) During any autoregressive generation

C) When temperature is zero

D) When the system preserves alternatives, receives feedback, or can revise an earlier choice

Answer and explanation

Correct answer: D. One long trajectory remains one trajectory; search requires alternatives and a procedure for selection, branching, or backtracking.

Question 13.2.2

13.2. Amortization, scratchpads, and search

What is the correct status of the analogy between an LLM and Solomonoff induction?

One correct optionAEvery LLM inherits universal dominance guaranteesBA Transformer literally sums over all computable programsCThe analogy proves universal optimality of practical LLMsDIt is a useful research lens, not a theorem about a finite trained model

A) Every LLM inherits universal dominance guarantees

B) A Transformer literally sums over all computable programs

C) The analogy proves universal optimality of practical LLMs

D) It is a useful research lens, not a theorem about a finite trained model

Answer and explanation

Correct answer: D. A practical LLM does not implement the universal semimeasure and does not inherit its guarantees.

Question 13.3.1

13.3. Why intermediate tokens can help

Why can a sequential working state help with parity?

One correct optionAIt changes the correct answerBIt adds new training dataCIt implements a serial computation after which the answer is accessible to a restricted readoutDIt increases the entropy of the original input

A) It changes the correct answer

B) It adds new training data

C) It implements a serial computation after which the answer is accessible to a restricted readout

D) It increases the entropy of the original input

Answer and explanation

Correct answer: C. Computational accessibility changes; the input data do not.

Question 13.4.1

13.4. New information or new computation?

Let $C=G_\theta(X,U)$ with $U\perp Y^*\mid X$ . What is $I(Y^*;C\mid X)$ ?

One correct optionAZeroB

H(C)

I(X;C)

DAlways infinite

A) Zero

B) $H(C)$

C) $I(X;C)$

D) Always infinite

Answer and explanation

Correct answer: A. Given X, the internal chain is conditionally independent of the correct answer.

Question 13.4.2

13.4. New information or new computation?

Why can a restricted model nevertheless become more accurate after constructing a scratchpad?

One correct optionAThe data-processing inequality is violatedBConditional mutual information becomes negativeCThe scratchpad always retrieves a hidden answer from training dataDThe available computational procedure changes, not the true conditional entropy of the task

A) The data-processing inequality is violated

B) Conditional mutual information becomes negative

C) The scratchpad always retrieves a hidden answer from training data

D) The available computational procedure changes, not the true conditional entropy of the task

Answer and explanation

Correct answer: D. Sequential steps and working memory may let the model transform the same evidence more effectively.

Question 13.4.3

13.4. New information or new computation?

Which object can add new Shannon information about $Y^*$ beyond $X$ ?

One correct optionAAn external observation

O

with

I(Y^*;O\mid X)>0

BParaphrasing an internal chainCRereading the same promptDLowering the sampling temperature

A) An external observation $O$ with $I(Y^*;O\mid X)>0$

B) Paraphrasing an internal chain

C) Rereading the same prompt

D) Lowering the sampling temperature

Answer and explanation

Correct answer: A. Retrieval, sensors, hidden tests, or environmental feedback may supply evidence absent from the input.

Question 13.4.4

13.4. New information or new computation?

What does the model’s predictive entropy after an intermediate step measure?

One correct optionAThe exact probability that the reasoning is correctBThe true conditional entropy

H(Y^*\mid X,C)

CThe concentration of the model’s own predictive distributionDThe causal faithfulness of the chain

A) The exact probability that the reasoning is correct

B) The true conditional entropy $H(C)$

C) The concentration of the model’s own predictive distribution

D) The causal faithfulness of the chain

Answer and explanation

Correct answer: C. A model can become more confident while becoming wrong.

Question 13.4.5

13.4. New information or new computation?

If $S_j=(X,C_{\le j})$ and the chain is generated only from $X$ , what is $I(Y^*;C_j\mid X,C_{<j})$ ?

One correct optionAZeroB

I(X;Y^*)

CA positive constantD

H(C_j)

A) Zero

B) $H(C)$

C) A positive constant

D) $H(C_j)$

Answer and explanation

Correct answer: A. The new internal token is not an external observation once the complete input is known.

Question 13.5.1

13.5. What can be measured along a trajectory?

When does a difference in auxiliary-predictor cross-entropies equal $I(Y;S_j\mid S_{j-1})$ ?

One correct optionAWhen the states are nested and the predictor variational gaps are controlledBWhenever the chain has more than one tokenCOnly when

Y

is deterministicDWhenever predictive entropy decreases

A) When the states are nested and the predictor variational gaps are controlled

B) Whenever the chain has more than one token

C) Only when $Y$ is deterministic

D) Whenever predictive entropy decreases

Answer and explanation

Correct answer: A. In general, there is also a lost-information term and a difference between variational gaps.

Question 13.5.2

13.5. What can be measured along a trajectory?

What is the most direct way to study causal faithfulness of a visible chain?

One correct optionAMeasure only its lengthBCount mathematical symbolsCIntervene on intermediate steps and observe how the answer changesDUse only the model’s self-reported confidence

A) Measure only its length

B) Count mathematical symbols

C) Intervene on intermediate steps and observe how the answer changes

D) Use only the model’s self-reported confidence

Answer and explanation

Correct answer: C. Faithfulness is a causal question, so polished prose alone is not enough.

Question 13.5.3

13.5. What can be measured along a trajectory?

What can an unchanged answer after removing an intermediate step mean?

One correct optionAOnly that the system is perfectly correctBEither robust reconstruction or disregard for the visible chainCOnly an evaluation errorDGuaranteed absence of internal computation

A) Only that the system is perfectly correct

B) Either robust reconstruction or disregard for the visible chain

C) Only an evaluation error

D) Guaranteed absence of internal computation

Answer and explanation

Correct answer: B. Additional interventions and independent checks are needed to distinguish the cases.

Question 13.6.1

13.6. One long trajectory or many candidates?

With independent attempts and $p>1/2$ , what happens to majority accuracy as odd $N$ grows?

One correct optionAIt tends to

1/2

BIt tends to oneCIt remains equal to

p

DIt must fall

A) It tends to $O$

B) It tends to one

C) It remains equal to $p$

D) It must fall

Answer and explanation

Correct answer: B. This follows from the binomial formula and the law of large numbers.

Question 13.6.2

13.6. One long trajectory or many candidates?

What do fully correlated errors do to the benefit of voting?

One correct optionAEliminate it: voting is equivalent to one attemptBDouble itCGuarantee accuracy oneDTurn the problem into Bayesian inference

A) Eliminate it: voting is equivalent to one attempt

B) Double it

C) Guarantee accuracy one

D) Turn the problem into Bayesian inference

Answer and explanation

Correct answer: A. Copies of the same error do not create independent evidence.

Question 13.6.3

13.6. One long trajectory or many candidates?

With an ideal verifier, best-of- $N$ succeeds with probability:

One correct optionA

p/N

1-(1-p)^N

p^N

1-pN

A) $O$

B) $1-(1-p)^N$

C) $p^N$

D) $1-pN$

Answer and explanation

Correct answer: B. It is enough for at least one candidate to be correct.

Question 13.6.4

13.6. One long trajectory or many candidates?

Why can selected accuracy under a weak verifier decrease as $N$ grows?

One correct optionAThe chance of encountering a rare incorrect candidate that exploits the scorer increasesBCorrect solutions disappear from the setCThe law of large numbers stops applyingDOracle pass@N must decrease

A) The chance of encountering a rare incorrect candidate that exploits the scorer increases

B) Correct solutions disappear from the set

C) The law of large numbers stops applying

D) Oracle pass@N must decrease

Answer and explanation

Correct answer: A. A larger set improves generator coverage but also creates more opportunities for selection failure.

Question 13.7.1

13.7. In-context learning: when context really brings evidence

In a latent-task model, how do prompt demonstrations fundamentally differ from an internal chain?

One correct optionAThere is no differenceBDemonstrations are always shorterCThe internal chain necessarily uses another tokenizerDDemonstrations may carry new information about the latent task

A) There is no difference

B) Demonstrations are always shorter

C) The internal chain necessarily uses another tokenizer

D) Demonstrations may carry new information about the latent task

Answer and explanation

Correct answer: D. If I(Z;D)>0, the examples update knowledge about the current rule.

Question 13.7.2

13.7. In-context learning: when context really brings evidence

What is the correct claim about ICL as Bayesian inference?

One correct optionAIt has been proved for every LLM and every promptBBayesian inference is impossible in a TransformerCIt is exact in special generative settings and a useful model beyond themDICL is always nearest-neighbor search

A) It has been proved for every LLM and every prompt

B) Bayesian inference is impossible in a Transformer

C) It is exact in special generative settings and a useful model beyond them

D) ICL is always nearest-neighbor search

Answer and explanation

Correct answer: C. The rigorous result depends on assumptions about data generation and architecture.

Question 13.8.1

13.8. How reasoning models are trained

What does an outcome reward directly evaluate?

One correct optionAFaithfulness of every intermediate stepBThe true causal graph of model computationCThe final checkable resultDThe complete information value of the trajectory

A) Faithfulness of every intermediate step

B) The true causal graph of model computation

C) The final checkable result

D) The complete information value of the trajectory

Answer and explanation

Correct answer: C. Outcome feedback can scale in checkable domains but poorly localizes the source of an error.

Question 13.8.2

13.8. How reasoning models are trained

Why is an RLHF KL anchor not a PAC-Bayes certificate?

One correct optionARLHF has no probabilitiesBPAC-Bayes forbids KLCRLHF is always deterministicDThe KL terms compare different random objects and occur in theorems with different assumptions

A) RLHF has no probabilities

B) PAC-Bayes forbids KL

C) RLHF is always deterministic

D) The KL terms compare different random objects and occur in theorems with different assumptions

Answer and explanation

Correct answer: D. PAC-Bayes concerns distributions over hypotheses, whereas RLHF concerns conditional action or response policies.

Question 13.9.1

13.9. How to evaluate a reasoning system

Which pair of metrics separates generator coverage from verifier quality?

One correct optionAOracle pass@N and selected pass@NBAccuracy and vocabulary sizeCPPL and temperatureDFLOPs and parameter count

A) Oracle pass@N and selected pass@N

B) Accuracy and vocabulary size

C) PPL and temperature

D) FLOPs and parameter count

Answer and explanation

Correct answer: A. Their gap measures the cost of an imperfect selector.

Question 13.9.2

13.9. How to evaluate a reasoning system

Why should reasoning systems be compared under matched budgets?

One correct optionAAll models have the same architectureBAdditional tokens, trajectories, and tool calls are additional resourcesCAccuracy is independent of computeDFLOPs always equal latency

A) All models have the same architecture

B) Additional tokens, trajectories, and tool calls are additional resources

C) Accuracy is independent of compute

D) FLOPs always equal latency

Answer and explanation

Correct answer: B. Without cost accounting, the best scores may correspond to different computational regimes.

Question 13.10.1

13.10. What is proved, observed, and hypothesized?

How should the claim “chain length approximates task computational complexity” be classified?

One correct optionAAs Shannon’s lawBAs a research hypothesis that requires a defined metric and empirical validationCAs a proved universal theoremDAs the definition of mutual information

A) As Shannon’s law

B) As a research hypothesis that requires a defined metric and empirical validation

C) As a proved universal theorem

D) As the definition of mutual information

Answer and explanation

Correct answer: B. Length depends on the model, tokenizer, prompt, and search strategy.

Question 13.10.2

13.10. What is proved, observed, and hypothesized?

What is the main lesson of Snell et al. on test-time compute?

One correct optionAInference compute always replaces pretrainingBEvery smaller model beats a larger oneCBest-of-N is always optimalDThe value of extra compute depends on task difficulty and budget allocation

A) Inference compute always replaces pretraining

B) Every smaller model beats a larger one

C) Best-of-N is always optimal

D) The value of extra compute depends on task difficulty and budget allocation

Answer and explanation

Correct answer: D. Adaptive allocation can be much more efficient than a fixed strategy, but there is no universal monotone guarantee.

Question 13.13.1

13.13. Conclusion: information is not computation

Which concluding principle is most accurate?

One correct optionAReasoning reduces entirely to entropy reductionBEvery long trajectory contains an external factCExtra tokens usually provide time, working memory, search, and verification—not automatically new knowledgeDHigh accuracy guarantees faithful visible reasoning

A) Reasoning reduces entirely to entropy reduction

B) Every long trajectory contains an external fact

C) Extra tokens usually provide time, working memory, search, and verification—not automatically new knowledge

D) High accuracy guarantees faithful visible reasoning

Answer and explanation

Correct answer: C. Data, computation, search, verification, and external observations must be accounted for separately.