betaFeedback

WorksComputer Science

Modeling LLM Reasoning Dynamics with Structural Representations

Abstract

Language-model reasoning alternates between sustained activities and local operations. We study how this temporal structure predicts continuation and the computation needed to analyze it. T/E/S combines text, local events, and spans of activity. Across reasoning and information-seeking tasks, events and spans improve next-outcome prediction in 70 of 76 evaluation groups for a Transformer and 74 of 76 for Qwen with LoRA. Span duration and preceding events are associated with transitions, and retaining event history across span boundaries improves prediction. We formulate budget-allocation counting and action-conditional continuation queries, prove counting hardness under explicit encodings, and derive conditions for affordable decision certification. In finite-process experiments, bounds that cancel shared continuation mass recover the same optimal actions as full dynamic programming while reducing mean inference CPU time by 77.7%. On 71 held-out HotpotQA and MuSiQue questions, a compact structural observer improves prediction of whether a fixed inference procedure finishes within a CPU allowance: Brier loss falls from 0.0836 to 0.0756. An annotation audit identifies substantial errors in that observer, separating this computational result from semantic validation of its features.

Introduction

A language-model agent can continue reasoning, retrieve evidence, revise a candidate, or answer. The useful action depends on the reasoning already performed. Evaluating the alternatives is itself a computation: a controller may spend more estimating the value of another retrieval round than it saves by avoiding that round. We investigate both the evolving reasoning process and the cost of querying a model of its continuation.

We use computational availability operationally. A specified inference procedure must return an estimate or an action certificate within a declared allowance. This concerns a concrete model, algorithm, and input; it does not classify individual prefixes into worst-case complexity classes. Exact probabilities may be difficult to compute even when the preferred action is easy to identify. Conversely, an inexpensive estimate need not improve on an action that a direct text controller already selects.

The project repository is available at https://github.com/karpovilia/reasoning.

Our contributions are threefold. (1) We characterize duration, local events, and retained history in annotated reasoning and measure their complementary predictive value. (2) We formalize exact counting and budgeted continuation analysis, then specialize decision bounds to shared future states. (3) We evaluate inference-cost prediction and selective analysis on saved paired retrieval continuations, with a separate audit of the structural observer. The counting reductions and concentration arguments apply established theory; the empirical contribution is their connection to observable reasoning and measured inference cost.

Section 3 introduces T/E/S and the structural evidence. Section 4 defines the computational queries and certificates. Sections 5 and 6 evaluate finite processes and retrieval decisions. Section 7 examines annotation transfer. Proofs and additional comparisons appear in the appendix.

T/E/S separates a local check from the surrounding derivation

Figure 1. T/E/S separates a local check from the surrounding derivation. Modes can recur; only the observed prefix is available for prediction.

Related work

ReasonOps segments reasoning using rules and clusters of sentence-opening phrases [18]; ReasoningFlow represents discourse relations between steps [19]. We distinguish local operations from sustained modes, then model elapsed duration and event history within and across modes. Hidden semi-Markov models make duration explicit [41]; Hawkes and neural Hawkes processes model event-history effects [11, 20].

Self-consistency and Tree of Thoughts allocate computation across possible solutions [38, 40]. ThoughtTerminator and REFRAIN study stopping generation [23, 34]. Rational metareasoning instead asks which computations are worth performing [12, 32]. Our inference-timing experiment addresses this latter question using the evolving trace, with direct text control as a comparison.

Counting complexity, approximate counting, and sequential uncertainty provide the theoretical tools [9, 10, 15]. We separate their guarantees from the accuracy of a learned process. Exact inference in a finite representation, or a valid confidence interval within it, does not by itself validate the representation of the underlying language model.

Reasoning structure and prediction

Representation. A question is one task; a trace is one generated solution. A segment is a completed text fragment under a fixed segmentation rule. A span is a continuous interval assigned a reasoning mode. Mode and event vocabularies are specified for each benchmark in the annotation instructions. For example, mathematical and scientific tasks use modes such as derivation, exploration, and verification, and events such as backtracking, subgoal completion, and failed attempt. Training and evaluation retain the vocabularies of the corresponding annotation schemes. Several events can occur in one segment. END means natural termination, whereas commitment means adopting an answer and can precede END. A–B–A denotes the order of reasoning modes: for example, derivation →\to verification →\to derivation again. A and B denote distinct modes; each of the three intervals may span several segments.

Data. The structural experiments use 56,783 traces from 4555 questions, including 16,497 fully and 997 partially annotated traces. Repeated attempts are available for 4195 questions. Tasks cover

MATH/MATH500, BBH, GPQA, HLE, HotpotQA, and MuSiQue [13, 17, 22, 31, 35, 36, 39].

Models. Trace generators include Qwen at 4–122B parameters, gpt-oss-20b/120b, DeepSeek R1 distillations, Gemma, and DeepSeek V4 Flash [4, 7, 8, 21, 24, 26, 27, 28, 29]. Annotation models assign events and spans; prediction models forecast their continuation; controllers select an action. These roles have different weights and training objectives. The annotation protocol uses Claude Opus 4.8 and DeepSeek Flash/Pro [1, 5, 6]. Appendix B describes the prediction and observation models.

Duration, events, and returns. In 5142 completely annotated traces, transition frequency varies with elapsed mode duration. For BBH it rises from 7.6% after one segment to 13.5% after 9–16; for HLE it falls from 54.3% to 7.2%. In the broader TRAIN/DEV audit, failed-attempt events precede a next-segment mode change in 36.7% of cases versus 11.8% for positions matched on solver, mode, elapsed duration, and trace position. Subgoal completion gives 28.1% versus 7.4%. These are conditional associations.

Local events and modes are distinct: 24.7% of verification events occur outside verification mode. In a separate whole-trace check, 22 verification labels lie inside derivation after excluding run-edge segments. Annotated returns occur in 4021 of the 5142 complete traces (78.2%). Recurrence is descriptive here; the comparison of samples and annotation protocols is discussed in Limitations.

Complementary predictive roles. We predict whether the next segment remains in the current mode, changes mode, or terminates, with destination mode and next-segment events as additional targets. Questions are kept together across repeated solutions, solvers, and annotation versions. On the shared 282-question validation partition, adding E/S to text lowers three-outcome negative log-likelihood (NLL) in 70 of 76 solver–benchmark–annotation groups for a segment Transformer (Appendix B) and 74 of 76 for Qwen with LoRA. NLL is negative natural-log probability, in nats per scored outcome; lower is better. Median relative reductions are 7.0% and 9.3%. Both architectures improve in all 32 groups with at least ten evaluation questions.

Table 1 shows the main input ablation. Common position, length, and solver features remain in every row. The best Qwen configuration, including an auxiliary annotation-corruption objective during training, reaches a main multitask score of 0.593, approximately 0.59; this score combines transition, destination-mode, and event losses and is not a single-target NLL.

InputsTransformerQwen
Text0.8510.698
Text+events0.8050.685
Text+spans0.7340.603
Text+events+spans0.7190.598

Table 1. Input ablation across corpus solvers: 282 validation questions. Weighted multitask loss; lower is better.

Spans provide most of the overall gain; events add predictive information, especially for subsequent events. In the first matched Qwen training, adding events to text and spans lowers next-event binary cross-entropy from 0.281 to 0.249. The 98.75% paired question-bootstrap interval for the difference is [−0.042, −0.023]. The corresponding structural-step NLL changes from 0.502 to 0.499, with interval [−0.006, 0.001]. Thus the event contribution depends on the predicted target.

An explicit probabilistic approximation. We approximate structural continuations using current mode, span age, text state, and two event-memory vectors. Each memory coordinate represents an event type; its update specifies decay and retention across boundaries. This construction permits controlled changes to duration, event generation, and persistence. GRU and Neural Hawkes provide accuracy references on the same prefixes. The explicit model has 11,685 parameters, versus 24,623 and 42,063; GRU has the best next-step NLL and Neural Hawkes the best continuation energy scores (Appendix B).

With state-computation parameters fixed and output models refitted, conditioning events on the next mode improves reproduction of event co-occurrence by 9.1%; retaining accumulated event history improves event counts by mode by 4.6%. Resetting both memory vectors at boundaries increases next-step NLL from 0.565 to 0.571, with a paired 95% interval excluding zero. In this experiment, earlier events remain useful after a change of activity.

Counting and choosing computation

The query. For observed prefix hh, first action aa, fixed subsequent policy π\pi, and additional solver budget BB, define

pMa(h,B)=Pr⁡(Y=1,C≤B∣h,do⁡(a),π).(1)p_M^a(h,B) = \Pr(Y = 1, C \le B \mid h, \operatorname{do}(a), \pi). \tag*{(1)}

Here YY denotes a correct terminal answer and CC the additional cost. For each query, we fix action aa, such as retrieving more evidence or answering, and evaluate the success probability under that choice. Utility QM(a)Q_M(a) can instead be the expectation of a declared bounded payoff. A structural simulator requires an outcome model or scored continuations to connect its events to correctness. Observation and analysis costs are reserved or deducted before fixing the execution budget.

Exact counting. Consider nn tasks, each with one available additional solution attempt. We choose which attempts to execute within a budget. Attempt ii has a binary-encoded integer cost cic_i and a rational expected increase pi∈[0,1]p_i \in[0,1] in the probability of solving its task correctly. For budget BB and required expected increase RR in the number of solved tasks, the number of feasible sets I⊆{1,…,n}I \subseteq\{1,\ldots,n\} is

N(B,R)=∣{I:∑i∈Ici≤B, ∑i∈Ipi≥R}∣.(2)N(B,R) = \left|\left\{I : \sum_{i \in I} c_i \le B,\ \sum_{i \in I} p_i \ge R\right\}\right|. \tag*{(2)}

Claim 1. With binary-encoded inputs, counting feasible attempt sets N(B,R)N(B,R) is #P-complete. Exact computation of the success probability in (1) is #P-hard even for finite processes with succinct transitions and polynomially bounded continuation length. Appendix A specifies the encoding conditions and reductions.

The proof reduces #SubsetSum to our query by making the cost and expected gain of each attempt proportional to the same number. The budget and gain constraints then hold together exactly for subsets with the prescribed sum. Appendix A gives the complete reductions.

For an explicitly enumerated finite model with EE edges and horizon HH, budget dynamic programming costs O(H(B+1)E)O(H(B+1)E) arithmetic operations. The bound is pseudo-polynomial in a binary-encoded budget. To select actions, the Bellman recursion computes success probability after each available action, accounting for the remaining budget and steps. It selects the action with the highest success probability. This calculation requires a model of state transitions and terminal outcomes.

Decision certificates. For each action, we construct an interval [LM(a),UM(a)][L_M(a), U_M(a)] containing its expected utility. If one lower bound exceeds every competing upper bound, further refinement cannot change the choice provided the intervals are valid. Values can be estimated by repeatedly simulating a continuation from the same prefix, using fresh independent random numbers in each run. Intervals are constructed to retain their stated coverage probability when computation stops based on the results obtained so far [15].

These calculations certify an action under the continuation distribution specified by model MM. Certification for the real LLM also requires a bound on model error: if the expected utility error for action aa is at most βa\beta_a, we expand its interval by βa\beta_a on each side and check action separation again.

Shared continuations across actions. Choosing an action does not always require computing its exact utility. Suppose Q0=q(F)/2Q_0 = q(F)/2 and Q1=q(F)/2+1/2Q_1 = q(F)/2 + 1/2, where q(F)q(F) is the probability that a uniformly random assignment satisfies Boolean formula FF. Computing either QQ exactly recovers the number of satisfying assignments, whereas Q1−Q0=1/2Q_1 - Q_0 = 1/2 is known immediately. Selecting action 1 therefore requires no computation of q(F)q(F).

In a reasoning model, different first actions can lead to the same future state. When subsequent behavior from that state is identical, the common contribution can be subtracted when comparing actions. Let gag_a be the total probability of already evaluated successful continuations, and μa(x)\mu_a(x) the probability of reaching an unevaluated state xx after action aa. Each unresolved continuation is counted once, at the state where its expansion currently stops. State xx includes the remaining budget and steps, event memory, and the rule for subsequent actions. Let V(x)∈[0,1]V(x) \in[0,1] be the probability of eventual success from xx. Then Qa=ga+∑xμa(x)V(x)Q_a = g_a + \sum_x \mu_a(x)V(x). Put k=ga−gbk = g_a - g_b and d(x)=μa(x)−μb(x)d(x) = \mu_a(x) - \mu_b(x). We obtain

k+∑xmin⁡(d(x),0)≤Qa−Qb,Qa−Qb≤k+∑xmax⁡(d(x),0).(3)\begin{aligned} k + \sum_x \min(d(x),0) &\le Q_a - Q_b,\\ Q_a - Q_b &\le k + \sum_x \max(d(x),0). \tag*{(3)} \end{aligned}

The interval width is ∑x∣d(x)∣\sum_x |d(x)|. Accounting for shared continuation probability reduces it by 2∑xmin⁡(μa(x),μb(x))2\sum_x \min(\mu_a(x),\mu_b(x)) relative to separate action bounds. Cancellation requires matching continuation distributions from the complete state; common mode alone does not ensure this.

Reducing action-selection time

For each action, the model defines the probability of completing the task successfully within the remaining budget. We compare three ways of choosing the action with the highest success probability, testing whether stopping probability computation early preserves the choice while reducing computation time. Finite processes with known transitions provide an exact reference for evaluating early stopping. The experiment covers 32 models and 404 queries from different prefixes. Each query compares three first actions under a fixed subsequent action rule.

MethodCPU time, ms ↓
Full probability computation12.94
Early selection with separate bounds5.62
Early selection with shared continuations2.88

Table 2. Action selection on 404 queries to finite-process models. All methods select the same actions as full computation.

The reference method computes each action’s success probability in full using dynamic programming. A second method progressively refines separate probability intervals and stops when the best action is determined. A third uses the same stopping criterion but accounts for shared continuations when comparing actions through Equation (3). Their common contribution cancels in the difference, potentially identifying the better action earlier.

Models have 24 or 96 states, horizons of 4, 8, 16, or 32 steps, and budget ⌈1.5H⌉\lceil1.5H \rceil. All methods use exact integer arithmetic. CPU timing covers the full decision calculation: transition processing, storing intermediate results, bound computation, and stopping. Model construction and reference verification are outside the timed calculation. We take the median of five timings per query, then average using fixed instance and configuration weights.

The shared-continuation method selects the same actions as full computation in 2.88 rather than 12.94 ms on average, reducing CPU time by 77.7%. Relative to early selection with separate bounds, the reduction is 48.8%. The paired instance-bootstrap 95% interval for the difference from full computation is [−10.50, −9.63] ms. With 24 states and horizon four, accounting for shared continuations is slower than separate bounds because of additional calculations.

Choosing whether to continue retrieval

Paired actions and models. The controller chooses whether to retrieve more evidence or answer from the information already collected. We measure the CPU time needed to compare these actions using a continuation model and test whether that cost can be predicted from the prefix. We use saved HotpotQA and MuSiQue continuations produced by Qwen3.6-35B-A3B-FP8 [30]. After two tool rounds, one branch answers and the other permits up to four further retrieval rounds from the same prefix. Fitting uses 141 questions, development 37, and final evaluation 71 distinct full questions: 36 HotpotQA and 35 MuSiQue, with 194 prefixes and 388 completed branches. Six reserved calibration questions are unused. Whole-question separation and subquestion-family overlap are distinguished in Limitations.

For this computational experiment, a frozen compact MiniLM-based observer produces E/S [33, 37]. It is a separate model from the main Qwen observer used in earlier prefix-prediction experiments. The process model generates structural continuations and action-conditioned outcome/cost estimates. A separate ridge predictor estimates whether the fixed inference algorithm will obtain a model-relative certificate within an allowance. Text baselines retain hashed text, MiniLM embeddings, counters, and frozen text-based quality/cost forecasts. T+S and T+E+S add observer outputs to those same inputs.

Predictor inputsBrier ↓
Counters and length0.0926
Text + counters0.0836
Text + counters + observed spans0.0767
Text + counters + observed E/S0.0756

Table 3. Predicting inference availability for Qwen3.6 retrieval: 71 HotpotQA/MuSiQue questions. Lower Brier loss is better.

RuleF1 ↑TokensCPU, ms
Always answer0.43395610.0
Always retrieve0.533714100.0
Direct text control0.51871369271.8
Inference selected by T0.51841372276.8
Inference selected by T/E/S0.51921372278.8
Matched random calls0.51921371281.2

Table 4. Qwen3.6 retrieval on 71 HotpotQA/MuSiQue questions: F1, full output tokens, controller CPU. Averages include four budgets.

Inference uses up to 1024 paired simulated continuations, horizon 512 structural steps, and a fixed sequence of refinement depths. Utility is answer F1 minus declared input/output-token penalties. We measure three independent random runs per prefix, 582 in evaluation. Availability at 25, 50, 100, or 250 ms means that a certificate was obtained within that measured CPU allowance. A failed computation is missing, not a negative availability label.

Predicting availability. Brier loss is the mean squared difference between predicted probability and observed availability. We average over the three runs, all four budgets, prefixes within questions, and then questions equally. All predictors and action rules are fixed before final answer outcomes are opened.

The prespecified E/S-versus-text difference is −0.0080, with paired 95% question-bootstrap interval [−0.0122, −0.0037], a relative reduction of 9.5%. Most of the gain is already present with spans. This predicts the runtime of a fixed learned computation; the semantic accuracy of its observation layer is evaluated separately in § 7.

Selecting inference calls. At predicted availability at least 0.8, the controller invokes inference; otherwise it uses direct text control. If no certificate is returned, it also uses the direct text action. The four nominal CPU allowances are prediction targets, not hard timeouts: all realized CPU, including overruns, is charged. A matched random rule preserves the number of calls within each benchmark. The E/S selection rule uses 2.34 ms less controller CPU than matched random calls, with 95% interval [−4.21, −0.61] ms. Their F1 difference is 0.00002, with interval [−0.00146, 0.00175]. Against direct text control, F1 changes by 0.00058, with interval [−0.00078, 0.00252], while CPU increases by 7.05 ms. Mean full input-token counts are 11,225 versus 11,179. Thus predicting inexpensive analysis does not in this experiment produce a better answer-quality/total-cost trade-off than direct text control. CPU measures include observation, feature preparation, prediction, and invoked inference; zero controller CPU for fixed actions does not mean zero generation cost.

Relation to direct computation control. Other experiments use structure to choose solver actions directly. On 361 MATH and GPQA questions with two solutions each, E/S reduces Qwen3-4B-Thinking output tokens by 4% relative to length-and-confidence control and by 0.8% relative to matched text control, with observed accuracy differences between +0.01 and +0.20 percentage points across the two contrasts and uncertain answer labels. On 65 HotpotQA questions, the structural controller uses 110 tool calls versus 134 for always permitting retrieval, with F1 0.565 versus 0.542. Relative to text control it uses 6% fewer calls at the same F1, but more output tokens, 1045 versus 984. These experiments establish particular action/cost effects; they use different cohorts and do not evaluate selective probabilistic analysis.

Reliability of structural observation

To examine the compact observer used in § 6, DeepSeek V4 Flash labels 72 fixed source segments from 24 questions in two passes with access only to the observed prefix. It sees the question and assistant text only up to the target segment, without detector outputs or answer outcomes. There are 142 valid responses out of 144. Agreement gives known labels for 384 of 432 event cells and 44 mode labels; disagreement is masked. A subsequent source review leaves one additional event cell unresolved.

On the original common mask shared by the compared methods, MiniLM event precision is 0.110, recall 0.421, and F1 0.175, versus F1 0.759 for the earlier source-reviewed labels. An intention filter raises MiniLM F1 only to 0.220. The detector often treats plans to check or search as completed operations. These predictions are present in the process-model inputs, so their errors are relevant to interpretation of the inference-timing experiment. Appendix § 11 gives the full comparison and the larger single-pass diagnostic. The audit concerns this compact observer; it does not measure the main Qwen detector.

Conclusion

Reasoning traces exhibit temporal structure that extends beyond isolated steps. Sustained activities differ in duration, local events are associated with transitions, and retained event history improves continuation prediction. T/E/S makes these properties explicit and improves predictive models across tasks and solvers.

The computational analysis separates estimating an exact probability from choosing an action. Shared future-state mass can cancel in a comparison, allowing the same decision with less inference work. On retrieval traces, structural-observer features also predict whether a fixed analysis will finish within a CPU allowance. The action-selection experiment exposes the additional requirement: useful timing must improve a decision enough to repay observation and analysis. Evaluating the main detector against compatible reference annotations and testing revised controllers on fresh question families are the next steps toward that objective.

Limitations

The structural prediction results use validation data and several annotation protocols. The 78.2% return rate and the 33.3% rate in a separate 90-trace whole-annotation sample describe different task/model compositions and procedures; recurrence frequencies alone do not establish long-range dependence. Machine repeat agreement is not human truth. The compact MiniLM observer has substantial semantic errors, and the main Qwen detector’s comparison on the new RAG reference set is not yet complete. Consequently, the inference-timing result supports prediction of the measured computation with its actual feature set, rather than validated recognition of reasoning events on that domain.

The 71-question retrieval evaluation excludes complete fitting questions, but six of 35 MuSiQue questions share atomic subquestions with fitting, and nine belong to connected fitting families. A post-hoc family bootstrap retains the sign of the Brier difference but does not remove that overlap. Results are specific to a fixed model, inference procedure, and CPU configuration. Exact synthetic certificates do not certify real LLM correctness; the latter requires separate model-error bounds. Retrieval control is evaluated through saved paired branches; common-prefix wall time is unavailable, so absolute end-to-end latency is not reported. The used evaluation questions remain unavailable for retuning or a fresh confirmation.

Ethical considerations

We study public reasoning and question-answering benchmarks and saved model-generated continuations. Structural labels describe text, not a model’s private internal reasoning or the truth of its statements. Incorrect event detection could cause premature stopping or unnecessary computation, so action quality and cost are reported together. This revision does not introduce deployment or user requests or new claims of human annotation. Generative assistance was used in drafting and translation; empirical values are tied to recorded results.

Proofs and inference conditions

Counting allocations. Membership in #P follows by guessing one inclusion bit per item and checking both rational inequalities in polynomial time. Exact sums of binary-encoded rationals have polynomial bit length. For hardness, use positive-integer #Subset-Sum [10]. For an instance a1,…,an,Ba_1,\ldots,a_n,B, set A=∑iaiA=\sum_i a_i, ci=aic_i=a_i, pi=ai/Ap_i=a_i/A, and R=B/AR=B/A. Both bounds hold exactly when ∑i∈Iai=B\sum_{i\in I}a_i=B, giving a bijection between solutions with polynomial encoding length. Trivial empty or zero-total instances can be handled separately. Expected gains are additive over distinct tasks; the proof does not assume additive success probabilities for repeated attempts on the same task.

Continuation probabilities. The process state and transition circuit have polynomial encoding length; the horizon and random-bit use are polynomially bounded, and the terminal predicate is computable in polynomial time. For the reduction, the state stores the item index and accumulated integer sum. At each of nn steps it chooses a fair bit and adds aia_i to both the sum and cost if included. The terminal predicate is sum≥B\mathop{\rm sum}\geq B; feasibility requires cost ≤B\leq B. Thus its success probability is #SubsetSum/2n2^n. An exact rational answer recovers the integer count by polynomial-time scaling. More generally, a polynomial fair-bit bound can be padded to a fixed length; counting accepted random strings is in #P. This does not claim #P membership for an arbitrary rational-valued function or for processes with unspecified real transitions.

Finite budget dynamics and Bellman recursion. Let Vh(x,b)V_h(x,b) be the probability of success within hh further steps and budget bb. Success is absorbing with value one; failure, negative budget, or exhausted horizon without success has value zero. For a fixed action policy and a finite transition/cost kernel PP, use

Vh(x,b)=∑x′,cP(x′,c∣x,a)Vh−1(x′,b−c),a=π(x,b,h).V_h(x,b)=\sum_{x',c}P(x',c\mid x,a)V_{h-1}(x',b-c), \qquad a=\pi(x,b,h).

Optimizing the first and later actions gives the Bellman recursion with max⁡a\max_a outside the sum. Induction on hh proves correctness. Nonnegative integer costs and a finite horizon suffice, including zero-cost transitions. There are H(B+1)H(B+1) copies of each state/edge; rational bit complexity must also be counted. Bounded dependency width offers another route to finite inference [3].

Exact counting hardness does not establish approximation hardness. With independent samples and bounded payoff, additive error ε\varepsilon requires O(ε−2log⁡(1/δ))O(\varepsilon^{-2}\log(1/\delta)) samples; generating those samples has its own cost. Relative error for rare success and general succinct inference are different questions. The FPTAS for #Knapsack concerns its specified counting problem, not every conjunction of budget and success constraints [9].

Shared-mass certificate. Subtract QbQ_b from QaQ_a. For every state with d(x)≥0d(x) \ge0, d(x)V(x)∈[0,d(x)]d(x)V(x) \in[0,d(x)]; otherwise it lies in [d(x),0][d(x),0]. Summing proves (3). Since ∣u−v∣=u+v−2min⁡(u,v)|u-v| = u+v-2\min(u,v) for nonnegative masses, the width reduction follows. Repeating pairwise comparisons against every competitor certifies the best action. When no strict separation is found, exact expansion can continue to the horizon and apply a fixed tie rule. Model-state equality includes the same continuation policy; merging only equal modes is insufficient.

Sampling and model error. For dd actions, independent bounded samples in [0,1][0,1] within each action, and sample mean Q^n(a)\widehat{Q}_n(a), a conservative radius is

rn=log⁡(π2dn23δ)2n.r_n = \sqrt{\frac{\log\left(\frac{\pi^2 d n^2}{3\delta}\right)}{2n}}.

Hoeffding’s inequality [14] and a union bound over a,n≥1a,n \ge1 give simultaneous coverage at least 1−δ1-\delta. Adaptive selection of the next action to sample does not change this event. Clipping Q^n±rn\widehat{Q}_n \pm r_n to [0,1][0,1] permits optional stopping. Other bounded utility ranges require rescaling; tighter confidence sequences are available [15]. These are sufficient theoretical conditions, not a claim that measured simulator certificates cover real answer correctness. If ∣Qreal(a)−QM(a)∣≤βa|Q_{\mathrm{real}}(a)-Q_M(a)| \le\beta_a, expand each interval by βa\beta_a; a positive pairwise lower bound must exceed βa+βb\beta_a+\beta_b to transfer to reality. Learned abstraction errors require the same treatment.

Finite-process implementation. The synthetic comparison uses three first actions and fixed subsequent action zero. All transition weights have denominator 32; after hh layers masses use denominator 32h32^h, permitting exact integer certificates. Shared propagation stores three first-action masses at each common future state. Seeds 128–159 and the full size/horizon grid were fixed before measurement. Confidence intervals resample the 32 instances 5000 times. Exact rational comparisons, zero-budget/horizon cases, and ties were checked outside timing.

Models and experimental protocols

Predictors and losses. The segment Transformer uses frozen 384-dimensional MiniLM embeddings, an 873-to-512 input projection, 12 layers, eight heads, feed-forward width 2048, and a 256-segment window. The separately trained Qwen3-4B-Instruct-2507 predictor uses at most 8192 tokens/256 segments, rank-32 LoRA with α=64\alpha= 64 and dropout 0.05 [16]. Overlapping context is not scored twice. AdamW uses batch 64, weight decay 0.01, clipping at one, 100 warmup updates, then cosine decay. Learning rates are 3⋅10−43\cdot10^{-4} for Transformer/projections and 10−410^{-4} for adapters; training uses eight and two passes. The frozen membership comprises 11,058 training traces from 2150 questions and 1498 validation traces from 282; this is the training subset of the corpus, not a competing corpus count.

The reported multitask score is

L=Avg⁡[Igℓg+(Ig+0.5)Idℓd+0.25Ieℓe].L = \operatorname{Avg}[I_g\ell_g + (I_g + 0.5)I_d\ell_d + 0.25I_e\ell_e].

Here ℓg\ell_g scores STAY/SWITCH/END, ℓd\ell_d the destination mode, and ℓe\ell_e known event labels; indicators mask missing targets. Averaging proceeds over annotation namespaces, positions, traces, and questions. Table 1 averages two initializations for Transformer and Qwen T/T+E+S, and one for Qwen T+E/T+S. The best Qwen’s auxiliary corruption objective edits up to 5% of known positions in half the training traces; two auxiliary losses have weight 0.25. The reported 0.593 excludes auxiliary losses. Structural-step comparison uses 239,866 positions from 282 questions; event comparison uses 77,089 positions from 129 questions with known labels.

Annotation and boundaries. In prediction experiments, mode duration counts consecutive segments of one mode; unknown labels break the run. An explicit same-mode boundary remains a SWITCH target but does not reset that feature. In the generative model, span age resets at every annotated boundary. The particular process-model comparison uses seven modes, including grounding; the evaluated prefix-detector configuration outputs six modes. END marks natural completion; capped continuations are censored and unknown event labels masked.

The main prefix detector is Qwen3-4B-Instruct-2507 [25] with rank-32 LoRA and GRU memory [2], trained once on 376,153 positions from 500 questions before freezing. Its weights differ from Qwen’s continuation predictor. The MiniLM observer in the new timing experiment is a separate compact classifier, not a replacement checkpoint of that detector.

Explicit model comparison. All models in Table 5 use MATH500, GPQA Diamond, and BBH under a fixed full-annotation partition: 443 fitting questions, 51 internal selection questions, and 82 validation questions. Step NLL is scored on 82 questions; structural energy on 57 and remaining-length/END energy on 59 with known targets. Continuations use 132 saved prefixes and 32 samples per prefix up to 2048 characters. An energy score compares simulated and observed summary vectors using mean distance to the observation minus half the mean pairwise simulation distance. Counts use x/(1+x)x/(1+x), lengths the fixed horizon, and structural vectors normalization by d\sqrt{d}; no validation-fitted scaling is used.

ModelNLLStruct.Length/END
Semi-Markov0.5500.1590.289
Explicit memory0.5460.1590.315
GRU0.5290.1600.272
Neural Hawkes0.5330.1540.269

Table 5. Process approximations: MATH500, GPQA Diamond, BBH. NLL in nats/step; two energy scores. Lower is better.

Mode-conditioned event generation is a mixture of products of Bernoulli probabilities. For event indicator e∈{0,1}e \in\{0,1\}, Bern⁡(e;p)=pe(1−p)1−e\operatorname{Bern}(e;p)=p^e(1-p)^{1-e}. A shared sampled next mode induces event dependence even when events are conditionally independent within that component. Memory controls retain state parameters and refit outputs in three repetitions, selecting only on internal fitting data. For retained minus reset history, the next-step NLL difference is −0.0060-0.0060, paired 95% interval [−0.0109,−0.0016][-0.0109,-0.0016], using 10,000 question resamples after averaging repetitions.

Retrieval timing protocol. The new evaluation’s fitting/development questions yield 398/101 prefixes. Text and structural cost predictors share a ridge penalty chosen by five-fold question validation on fitting data; four output probabilities are clipped and made monotone across allowances. Model utility is F1 minus 0.05CoutC_{\mathrm{out}}/4096 and 0.05CinC_{\mathrm{in}}/229376. Refinement depths are 1, 2, 4, . . . , 512 with nominal model-level error parameter 0.01. Fixed features, process models, cost predictors, and routing threshold precede final evaluation. All comparison rules use the same saved action pairs; no branch is generated in response to a selected rule. The post-hoc family bootstrap groups the final questions into 70 units and yields Brier-difference interval [-0.0121, −0.0038].

The earlier 65-question direct retrieval experiment instead calibrates on 25 HotpotQA and 25 MuSiQue questions. Its text/structure cost weights are 0.2/0.1. Structure minus text gives −0.108 tool calls per question, interval [−0.277, 0], and +60.7 output tokens, interval [−7.1, 180.2], with identical F1. This remains a separate experiment from inference timing.

Reference-annotation audit

The audit comprises a primary sample with two passes and an extended sample with one pass. The two prefix-based passes are separate requests to the same model using identical annotation instructions. Their common known mask is defined before comparison; disagreements and missing labels are excluded, not negative examples. The primary common-mask comparison contains 373 event cells from 24 questions and 41 mode labels from 19 questions. Event precision, recall, and F1 use pooled confusion counts weighted so that each question contributes total weight one over its known cells.

The earlier reviewed labels achieve precision 0.822, recall 0.704, and F1 0.759. MiniLM gives 0.110, 0.421, and 0.175; with the intention filter, these become 0.149, 0.421, and 0.220. All three comparisons use the same known cells.

A larger single-pass diagnostic has 5642 accepted responses out of 10,345 requested. On 33,542 known event cells across 154 questions, MiniLM precision is 0.150, recall 0.368, and F1 0.213; mode accuracy is 0.410 on 4396 known labels. This is an unfinished, nonrandom slice under one machine pass, so its scores are diagnostic and not interchangeable with the primary two-pass comparison. Together the two stages contain 5784 accepted responses, not 5784 independent traces or questions. Comparison of the main Qwen detector with the fixed primary set remains incomplete; no aggregate Qwen quality score is inferred from these results.

References

  1. [1]Anthropic. 2026. Introducing Claude Opus 4.8. https://www.anthropic.com/news/claude-opus-4-8.
  2. [2]Kyungyung Chu et al. 2014. Learning Phrase Representations using RNN Encoder–Decoder for Statistical Machine Translation. In EMNLP. https://aclanthology.org/D14-1179/.
  3. [3]Rina Dechter. 1999. Bucket elimination: A unifying framework for reasoning. Artificial Intelligence, 113(1–2):41–85. https://doi.org/10.1016/S0004-3702(99)00059-4.
  4. [4]DeepSeek-AI. 2025. DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning. https://arxiv.org/abs/2501.12948.
  5. [5]DeepSeek-AI. 2026a. DeepSeek-V4-Flash. Model card. Accessed 19 October 2026. https://huggingface.co/deepseek-ai/DeepSeek-V4-Flash.
  6. [6]DeepSeek-AI. 2026b. DeepSeek-V4-Pro. Model card. Accessed 19 October 2026. https://huggingface.co/deepseek-ai/DeepSeek-V4-Pro.
  7. [7]DeepSeek-AI. 2026c. DeepSeek-V4-Flash-0731. Model card. Accessed 19 October 2026. https://huggingface.co/deepseek-ai/DeepSeek-V4-Flash-0731.
  8. [8]Google DeepMind. 2026. Gemma 4 26B A4B IT. Model card. Accessed 19 October 2026. https://huggingface.co/google/gemma-4-26B-A4B-it.
  9. [9]Parikshit Gopalan, Adam Klivans, Raghu Meka, Daniel Stefankovic, Santosh Vempala, and Eric Vigoda. 2011. An FPTAS for #Knapsack and Related Counting Problems. In FOCS. https://www.microsoft.com/en-us/research/publication/an-fptas-for-knapsack-and-related-counting-problems/DOI
  10. [10]Christoph Haase and Stefan Kiefer. 2016. The complexity of the Kth largest subset problem and related problems. Information Processing Letters, 116:111–115. https://doi.org/10.1016/j.ipl.2015.09.015.
  11. [11]Alan G. Hawkes. 1971. Spectra of some self-exciting and mutually exciting point processes. Biometrika 58, 1, 83–90. https://doi.org/10.1093/biomet/58.1.83.
  12. [12]Nicholas Hay, Stuart Russell, David Tolpin, and Solomon Eyal Shimoni. 2012. Selecting Computations: Theory and Applications. In UAI. https://people.eecs.berkeley.edu/~russell/papers/uai12-meta.pdf.
  13. [13]Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Aurora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. 2021. Measuring Mathematical Problem Solving With the MATH Dataset. https://arxiv.org/abs/2103.03874.
  14. [14]Wassily Hoeffding. 1963. Probabilistic Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association 58, 301, 13–30. https://doi.org/10.1080/01621459.1963.10500830.
  15. [15]Steven R. Howard, Aaditya Ramdas, Jon McAuliffe, and Jasmeet Sekhon. 2021. Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2):1055–1080. https://doi.org/10.1214/20-AOS1991.
  16. [16]Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. 2021. LoRA: Low-Rank Adaptation of Large Language Models. https://arxiv.org/abs/2106.09685.
  17. [17]Hugging Face H4. n.d. MATH-500. Dataset card. https://huggingface.co/datasets/HuggingFaceH4/MATH-500.
  18. [18]Daniel Lee, Owen Queen, and James Zou. ReasonOps: Operator segmentation for LLM reasoning traces. ICML 2026 Workshop on Mechanistic Interpretability, 2026. URL https://openreview.net/forum?id=Bx9L0ExZTi; https://arxiv.org/abs/2605.29192.
  19. [19]Jin Lee, Shivam Agarwal, Amruta Parulekar, Siddarth Madala, Dilek Hakkanı-Tur, and Julia Hockenmaier. ReasoningFlow: Discourse structures for understanding LLM reasoning traces. EMNLP 2026 Main Conference, 2026. arXiv:2606.05402v2. URL https://arxiv.org/abs/2606.05402; proceedings: https://aclanthology.org/2026.emnlp-main.670/.
  20. [20]Hongyuan Mei and Jason Eisner. 2017. The Neural Hawkes Process: A Neurally Self-Modulating Multivariate Point Process. In Advances in Neural Information Processing Systems 30. https://proceedings.neurips.cc/paper/2017/hash/6463c88 460bd3bbe25e495c63aa40b-Abstract.html.arxiv.org/abs/1612.09328
  21. [21]OpenAI. 2025. gpt-oss-120b & gpt-oss-20b Model Card. https://openai.com/index /gpt-oss-model-card/.
  22. [22]Phan et al. 2025. Humanity’s Last Exam. https://arxiv.org/abs/2501.14249.
  23. [23]Xiao Pu, Michael Saxon, Wenyue Hua, and William Yang Wang. Thought Terminator: Benchmarking, Calibrating, and Mitigating Overthinking in Reasoning Models. arXiv preprint arXiv:2504.13367, 2025. URL https://arxiv.org/abs/2504.13367.
  24. [24]Qwen Team. 2025a. Qwen3 Technical Report. https://arxiv.org/abs/2505.09388.
  25. [25]Qwen Team. 2025b. Qwen3-4B-Instruct-2507. Model card. Accessed 19 October 2026. https://huggingface.co/Qwen/Qwen3-4B-Instruct-2507.
  26. [26]Qwen Team. 2025c. Qwen3-4B-Thinking-2507. Model card. Accessed 19 October 2026. https://huggingface.co/Qwen/Qwen3-4B-Thinking-2507.
  27. [27]Qwen Team. 2026a. Qwen3.5-122B-A10B. Model card. Accessed 19 October 2026. https://huggingface.co/Qwen/Qwen3.5-122B-A10B.
  28. [28]Qwen Team. 2026c. Qwen3.6-35B-A3B. Model card. Accessed 19 October 2026. https://huggingface.co/Qwen/Qwen3.6-35B-A3B.
  29. [29]Qwen Team. 2026d. Qwen3.8-27B. Model card. Accessed 19 October 2026. https://huggingface.co/Qwen/Qwen3.8-27B.
  30. [30]Qwen Team. 2026. Qwen3.6-35B-A3B-FP8: Model Card. https://huggingface.co/Qwen/Qwen3.6-35B-A3B-FP8.
  31. [31]David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Dianti, Julian Michael, and Samuel R. Bowman. 2023. GPOA: A Graduate-Level Google-Proof Q&A Benchmark. https://arxiv.org/abs/2311.12022.
  32. [32]Stuart Russell and Eric Wefald. 1991. Principles of metareasoning. Artificial Intelligence, 49(1–3):361–395. https://doi.org/10.1016/0004-3702(91)90015-C.
  33. [33]Sentence Transformers. n.d. all-MiniLM-L6-v2. Model card. Accessed 19 October 2026. https://huggingface.co/sentence-transformers/all-MiniLM-L6-v2.DOI
  34. [34]Renliang Sun, Wei Cheng, Dawei Li, Haifeng Chen, and Wei Wang. Stop When Enough: Adaptive Early-Stopping for Chain-of-Thought Reasoning. In Proceedings of ACL, pages 27250–27268, 2026. URL https://aclanthology.org/2026.acl-long.1256/.
  35. [35]Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoc V. Le, Ed H. Chi, Denny Zhou, and Jason Wei. 2022. Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them. https://arxiv.org/abs/2210.09261.
  36. [36]Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. 2022. MuSiQue: Multihop Questions via Single-hop Question Composition. Transactions of the Association for Computational Linguistics, 10:539-554. https://arxiv.org/abs/2108.00573.
  37. [37]Wenhui Wang, Furu Wei, Li Dong, Hangbo Bao, Nan Yang, and Ming Zhou. 2020. MiniLM: Deep Self-Attention Distillation for Task-Agnostic Compression of Pre-Trained Transformers. https://arxiv.org/abs/2002.10957.
  38. [38]Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023. Self-Consistency Improves Chain of Thought Reasoning in Language Models. In ICLR. https://arxiv.org/abs/2203.11171.
  39. [39]Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W. Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. 2018. HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering. https://arxiv.org/abs/1809.09600.
  40. [40]Shun-Zheng Yu. 2010. Hidden semi-Markov models. Artificial Intelligence 174, 2, 215–243. https://doi.org/10.1016/j.artint.2009.11.011.

Paper details

vlnc:W_5sj9rtq5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents