Probabilistic Language Tries: A Unified Framework for Compression, Decision Policies, and Execution Reuse

• URL: http://arxiv.org/abs/2604.06228v1
• Date: Sun, 29 Mar 2026 21:24:26 GMT
• Title: Probabilistic Language Tries: A Unified Framework for Compression, Decision Policies, and Execution Reuse
• Abstract summary: We introduce language tries (PLTs), a unified representation that makes explicit the prefix structure implicitly defined by any generative probabilistic model over sequences.<n>We also introduce a hybrid compression architecture decomposing any dataset into a covered majority and a sparse residual store, connecting arithmetic coding with Kolmogorov-style program representations and rate-distortion theory.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We introduce probabilistic language tries (PLTs), a unified representation that makes explicit the prefix structure implicitly defined by any generative model over sequences. By assigning to each outgoing edge the conditional probability of the corresponding token or action, a PLT simultaneously serves as: (i) an optimal lossless compressor via frequency-weighted interval encoding, generalizing arithmetic coding to model-conditioned distributions; (ii) a policy representation for sequential decision problems including games, search, and robotic control; and (iii) a memoization index that lets repeated inference queries be answered by structured retrieval rather than full model execution. The central technical result is a prior-guided caching theorem: under a stationary generative distribution, a PLT-guided cache achieves strictly lower expected inference cost than any empirical-frequency cache for all query counts below a threshold that grows with the concentration of the prior. This converts O(n^2) transformer attention cost into an expected cost of p_r * O(log N) + (1 - p_r) * O(n^2), where p_r is the prior-estimated reuse probability and N is the artifact store size. We further introduce a hybrid compression architecture decomposing any dataset into a PLT-covered majority and a sparse residual store, connecting arithmetic coding with Kolmogorov-style program representations and rate-distortion theory. We instantiate the framework across chess, web search, robotics, organizational workflows, and LLM inference, demonstrating that compression, decision making, and computational reuse are all derived from a single probability measure on sequence space.

Related papers

• Planning-aligned Token Compression for Long-Context Autonomous Driving [95.59023657139208]
  We propose a planning-aligned working memory framework built on conditional VQ-VA.<n>Compression is conditioned on both historical trajectory and a learned planning intent.<n>We evaluate on high-signal dynamic scenarios where historical context is most critical for behavior correctness.
  arXiv  Detail & Related papers  (2026-06-05T17:16:21Z)
• Mitigating Bias in Locally Constrained Decoding via Tractable Proposals [73.78736135699953]
  Existing locally constrained decoding approaches enforce constraints by myopically masking out next tokens.<n>Recent work uses sequential Monte Carlo methods to mitigate such biases, but designing effective proposal distributions or potential functions remains a key challenge.<n>We propose a generic approach to construct proposals and potentials for SMC sampling from $p_mathrmlm( cdot mid mathrmconstraint)$.
  arXiv  Detail & Related papers  (2026-06-01T08:58:18Z)
• The Expressivity Boundary of Probabilistic Circuits: A Comparison with Large Language Models [49.67598869075125]
  In autoregressive language modeling, Probabilistic Circuits (PCs) lag behind Transformer-based large language models (LLMs)<n>We show that structured-decomposable PCs can match Transformer separation rank on vtree-aligned partitions, but that this capacity is limited to partitions aligned with the fixed routing structure.<n>We further prove that decomposable PCs are strictly more expressive than structured-decomposable ones, though effectively optimizing them remains an open challenge.
  arXiv  Detail & Related papers  (2026-05-13T03:22:10Z)
• A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
  We introduce a structure-aware framework for distributed quantum optimization.<n>We find that for a search space of size $N$, our framework achieves $O(sqrtN)$ query complexity up to processors and separator dependent factors.<n>We show that structure-aware decomposition delivers a practical path to scalable distributed quantum optimization on quantum networks.
  arXiv  Detail & Related papers  (2026-03-08T15:15:52Z)
• DecompressionLM: Deterministic, Diagnostic, and Zero-Shot Concept Graph Extraction from Language Models [24.759051210517658]
  DecompressionLM is a stateless framework for zero-shot concept graph extraction.<n>Our method targets three limitations of common decoding-based probing approaches.
  arXiv  Detail & Related papers  (2026-01-30T22:56:56Z)
• Dynamic Large Concept Models: Latent Reasoning in an Adaptive Semantic Space [56.37266873329401]
  Large Language Models (LLMs) apply uniform computation to all tokens, despite language exhibiting highly non-uniform information density.<n>We propose $textbfDynamic Large Concept Models (DLCM)$, a hierarchical language modeling framework that learns semantic boundaries from latent representations and shifts from tokens to a compressed concept space where reasoning is more efficient.
  arXiv  Detail & Related papers  (2025-12-31T04:19:33Z)
• Bottlenecked Transformers: Periodic KV Cache Consolidation for Generalised Reasoning [16.35681450323654]
  Transformer LLMs have been shown to exhibit strong reasoning ability that scales with inference-time compute.<n>We give a theoretical justification as to why memory (re)consolidation via KV cache rewrites is beneficial for improved reasoning.<n>Our model sees consistent performance gains over vanilla Transformers and pause-token augmented baselines, with gains of up to +6.6pp for selected tasks/backbones.
  arXiv  Detail & Related papers  (2025-05-22T17:33:49Z)
• Structural Entropy Guided Probabilistic Coding [52.01765333755793]
  We propose a novel structural entropy-guided probabilistic coding model, named SEPC.<n>We incorporate the relationship between latent variables into the optimization by proposing a structural entropy regularization loss.<n> Experimental results across 12 natural language understanding tasks, including both classification and regression tasks, demonstrate the superior performance of SEPC.
  arXiv  Detail & Related papers  (2024-12-12T00:37:53Z)
• CREPO: An Open Repository to Benchmark Credal Network Algorithms [78.79752265884109]
  Credal networks are imprecise probabilistic graphical models based on, so-called credal, sets of probability mass functions. A Java library called CREMA has been recently released to model, process and query credal networks. We present CREPO, an open repository of synthetic credal networks, provided together with the exact results of inference tasks on these models.
  arXiv  Detail & Related papers  (2021-05-10T07:31:59Z)
• Probabilistic Generating Circuits [50.98473654244851]
  We propose probabilistic generating circuits (PGCs) for their efficient representation. PGCs are not just a theoretical framework that unifies vastly different existing models, but also show huge potential in modeling realistic data. We exhibit a simple class of PGCs that are not trivially subsumed by simple combinations of PCs and DPPs, and obtain competitive performance on a suite of density estimation benchmarks.
  arXiv  Detail & Related papers  (2021-02-19T07:06:53Z)
• On Compression Principle and Bayesian Optimization for Neural Networks [0.0]
  We propose a compression principle that states that an optimal predictive model is the one that minimizes a total compressed message length of all data and model definition while guarantees decodability. We show that dropout can be used for a continuous dimensionality reduction that allows to find optimal network dimensions as required by the compression principle.
  arXiv  Detail & Related papers  (2020-06-23T03:23:47Z)
• Supervised Learning for Non-Sequential Data: A Canonical Polyadic Decomposition Approach [85.12934750565971]
  Efficient modelling of feature interactions underpins supervised learning for non-sequential tasks. To alleviate this issue, it has been proposed to implicitly represent the model parameters as a tensor. For enhanced expressiveness, we generalize the framework to allow feature mapping to arbitrarily high-dimensional feature vectors.
  arXiv  Detail & Related papers  (2020-01-27T22:38:40Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  junction tree algorithm is the most general solution for exact MAP inference with run-time guarantees. We propose a new graph transformation technique via node cloning which ensures a run-time for solving our target problem independently of the form of a corresponding clique tree.
  arXiv  Detail & Related papers  (2019-12-27T13:30:29Z)

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.