Measuring In-Context Computation Complexity via Hidden State Prediction

• URL: http://arxiv.org/abs/2503.13431v1
• Date: Mon, 17 Mar 2025 17:56:14 GMT
• Title: Measuring In-Context Computation Complexity via Hidden State Prediction
• Authors: Vincent Herrmann, Róbert Csordás, Jürgen Schmidhuber,
• Abstract summary: We show that a neural sequence model's ability to predict its own future hidden states correlates with the intuitive interestingness of the task.<n>We propose a novel learned predictive prior that enables us to measure the novel information gained in each step.<n>Our metric predicts the description length of formal languages learned in-context, the complexity of mathematical reasoning problems, and the correctness of self-generated reasoning chains.
• Score: 33.504027525492056
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Detecting when a neural sequence model does "interesting" computation is an open problem. The next token prediction loss is a poor indicator: Low loss can stem from trivially predictable sequences that are uninteresting, while high loss may reflect unpredictable but also irrelevant information that can be ignored by the model. We propose a better metric: measuring the model's ability to predict its own future hidden states. We show empirically that this metric -- in contrast to the next token prediction loss -- correlates with the intuitive interestingness of the task. To measure predictability, we introduce the architecture-agnostic "prediction of hidden states" (PHi) layer that serves as an information bottleneck on the main pathway of the network (e.g., the residual stream in Transformers). We propose a novel learned predictive prior that enables us to measure the novel information gained in each computation step, which serves as our metric. We show empirically that our metric predicts the description length of formal languages learned in-context, the complexity of mathematical reasoning problems, and the correctness of self-generated reasoning chains.

Related papers

• Language Models Can Predict Their Own Behavior [28.80639362933004]
  We show that internal representation of input tokens alone can often precisely predict, not just the next token, but eventual behavior over the entire output sequence.<n>We leverage this capacity and learn probes on internal states to create early warning (and exit) systems.<n>Specifically, if the probes can confidently estimate the way the LM is going to behave, then the system will avoid generating tokens altogether and return the estimated behavior instead.
  arXiv  Detail & Related papers  (2025-02-18T23:13:16Z)
• Learning Latent Graph Structures and their Uncertainty [63.95971478893842]
  Graph Neural Networks (GNNs) use relational information as an inductive bias to enhance the model's accuracy. As task-relevant relations might be unknown, graph structure learning approaches have been proposed to learn them while solving the downstream prediction task.
  arXiv  Detail & Related papers  (2024-05-30T10:49:22Z)
• Extracting Usable Predictions from Quantized Networks through Uncertainty Quantification for OOD Detection [0.0]
  OOD detection has become more pertinent with advances in network design and increased task complexity. We introduce an Uncertainty Quantification(UQ) technique to quantify the uncertainty in the predictions from a pre-trained vision model. We observe that our technique saves up to 80% of ignored samples from being misclassified.
  arXiv  Detail & Related papers  (2024-03-02T03:03:29Z)
• Uncovering the Missing Pattern: Unified Framework Towards Trajectory Imputation and Prediction [60.60223171143206]
  Trajectory prediction is a crucial undertaking in understanding entity movement or human behavior from observed sequences. Current methods often assume that the observed sequences are complete while ignoring the potential for missing values. This paper presents a unified framework, the Graph-based Conditional Variational Recurrent Neural Network (GC-VRNN), which can perform trajectory imputation and prediction simultaneously.
  arXiv  Detail & Related papers  (2023-03-28T14:27:27Z)
• Semantic Strengthening of Neuro-Symbolic Learning [85.6195120593625]
  Neuro-symbolic approaches typically resort to fuzzy approximations of a probabilistic objective. We show how to compute this efficiently for tractable circuits. We test our approach on three tasks: predicting a minimum-cost path in Warcraft, predicting a minimum-cost perfect matching, and solving Sudoku puzzles.
  arXiv  Detail & Related papers  (2023-02-28T00:04:22Z)
• Local Evaluation of Time Series Anomaly Detection Algorithms [9.717823994163277]
  We show that an adversary algorithm can reach high precision and recall on almost any dataset under weak assumption. We propose a theoretically grounded, robust, parameter-free and interpretable extension to precision/recall metrics.
  arXiv  Detail & Related papers  (2022-06-27T10:18:41Z)
• Uncertainty estimation of pedestrian future trajectory using Bayesian approximation [137.00426219455116]
  Under dynamic traffic scenarios, planning based on deterministic predictions is not trustworthy. The authors propose to quantify uncertainty during forecasting using approximation which deterministic approaches fail to capture. The effect of dropout weights and long-term prediction on future state uncertainty has been studied.
  arXiv  Detail & Related papers  (2022-05-04T04:23:38Z)
• NUQ: Nonparametric Uncertainty Quantification for Deterministic Neural Networks [151.03112356092575]
  We show the principled way to measure the uncertainty of predictions for a classifier based on Nadaraya-Watson's nonparametric estimate of the conditional label distribution. We demonstrate the strong performance of the method in uncertainty estimation tasks on a variety of real-world image datasets.
  arXiv  Detail & Related papers  (2022-02-07T12:30:45Z)
• Neuro-Symbolic Entropy Regularization [78.16196949641079]
  In structured prediction, the goal is to jointly predict many output variables that together encode a structured object. One approach -- entropy regularization -- posits that decision boundaries should lie in low-probability regions. We propose a loss, neuro-symbolic entropy regularization, that encourages the model to confidently predict a valid object.
  arXiv  Detail & Related papers  (2022-01-25T06:23:10Z)
• Uncertainty Intervals for Graph-based Spatio-Temporal Traffic Prediction [0.0]
  We propose a Spatio-Temporal neural network that is trained to estimate a density given the measurements of previous timesteps, conditioned on a quantile. Our method of density estimation is fully parameterised by our neural network and does not use a likelihood approximation internally. This approach produces uncertainty estimates without the need to sample during inference, such as in Monte Carlo Dropout.
  arXiv  Detail & Related papers  (2020-12-09T18:02:26Z)
• Explaining the Behavior of Black-Box Prediction Algorithms with Causal Learning [8.256305306293847]
  Causal approaches to post-hoc explainability for black-box prediction models have become increasingly popular.<n>We learn causal graphical representations that allow for arbitrary unmeasured confounding among features.<n>Our approach is motivated by a counterfactual theory of causal explanation wherein good explanations point to factors that are "difference-makers" in an interventionist sense.
  arXiv  Detail & Related papers  (2020-06-03T19:02:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.