Faster Exact MPE and Constrained Optimization with Deterministic Finite State Automata

• URL: http://arxiv.org/abs/2108.03899v3
• Date: Tue, 9 May 2023 21:44:32 GMT
• Title: Faster Exact MPE and Constrained Optimization with Deterministic Finite State Automata
• Abstract summary: We exploit our concise representation within Bucket Elimination (BE) Results on most probable explanation and weighted constraint satisfaction benchmarks show that FABE often outperforms the state of the art.
• Score: 2.1777837784979273
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a concise function representation based on deterministic finite state automata for exact most probable explanation and constrained optimization tasks in graphical models. We then exploit our concise representation within Bucket Elimination (BE). We denote our version of BE as FABE. FABE significantly improves the performance of BE in terms of runtime and memory requirements by minimizing redundancy. Results on most probable explanation and weighted constraint satisfaction benchmarks show that FABE often outperforms the state of the art, leading to significant runtime improvements (up to 5 orders of magnitude in our tests).

Related papers

• Multi-ResNets for Subspace Preconditioning in Constrained Optimization [3.874563682396874]
  MResOpt is a staged residual neural network architecture for constrained optimization problems.<n>We show that MResOpt supports a learned division labor that keeps iterates on the equality constraint manifold.
  arXiv  Detail & Related papers  (2026-06-04T15:37:55Z)
• LiveFMBench: Unveiling the Power and Limits of Agentic Workflows in Specification Generation [75.05397479715576]
  Large language models (LLMs) and agents have shown promising progress, but their true capabilities and failure modes remain unclear.<n>We present the first systematic and contamination-aware study of LLM- and agent-based formal specification generation for C programs.
  arXiv  Detail & Related papers  (2026-05-02T11:31:33Z)
• CROP: Token-Efficient Reasoning in Large Language Models via Regularized Prompt Optimization [0.0]
  Large Language Models utilizing reasoning techniques improve task performance but incur significant latency and token costs due to verbose generation.<n>We propose Cost-Regularized Optimization of Prompts (CROP), an APO method that introduces regularization on response length.<n>We evaluate our approach on complex reasoning datasets, specifically GSM8K, LogiQA and BIG-Bench Hard.
  arXiv  Detail & Related papers  (2026-04-08T19:31:25Z)
• Autocorrelated Optimize-via-Estimate: Predict-then-Optimize versus Finite-sample Optimal [2.0228793142608588]
  Models that directly optimize for out-of-sample performance in the finite-sample regime have emerged as a promising alternative to traditional estimate-then-optimize approaches.<n>We compare their performance in the context of autocorrelated uncertainties, specifically, under a Vector Autoregressive Moving Average VARMA(p,q) process.
  arXiv  Detail & Related papers  (2026-02-02T09:49:51Z)
• GLOW: Graph-Language Co-Reasoning for Agentic Workflow Performance Prediction [51.83437071408662]
  We propose GLOW, a unified framework for AW performance prediction.<n>GLOW combines the graph-structure modeling capabilities of GNNs with the reasoning power of LLMs.<n>Experiments on FLORA-Bench show that GLOW outperforms state-of-the-art baselines in prediction accuracy and ranking utility.
  arXiv  Detail & Related papers  (2025-12-11T13:30:46Z)
• The Curious Case of In-Training Compression of State Space Models [49.819321766705514]
  State Space Models (SSMs) tackle long sequence modeling tasks efficiently, offer both parallelizable training and fast inference.<n>Key design challenge is striking the right balance between maximizing expressivity and limiting this computational burden.<n>Our approach, textscCompreSSM, applies to Linear Time-Invariant SSMs such as Linear Recurrent Units, but is also extendable to selective models.
  arXiv  Detail & Related papers  (2025-10-03T09:02:33Z)
• MEC-Quant: Maximum Entropy Coding for Extremely Low Bit Quantization-Aware Training [15.099918961133866]
  Quantization-Aware Training (QAT) has driven much attention to produce efficient neural networks.<n>We argue that quantization inevitably introduce biases into the learned representation, especially under the extremely low-bit setting.<n>We propose Entropy Coding Quantization (MEC-Quant), a more principled objective that explicitly optimize on the structure of the representation.
  arXiv  Detail & Related papers  (2025-09-19T01:37:02Z)
• MPQ-DMv2: Flexible Residual Mixed Precision Quantization for Low-Bit Diffusion Models with Temporal Distillation [74.34220141721231]
  We present MPQ-DMv2, an improved textbfMixed textbfPrecision textbfQuantization framework for extremely low-bit textbfDiffusion textbfModels.
  arXiv  Detail & Related papers  (2025-07-06T08:16:50Z)
• MAO: Efficient Model-Agnostic Optimization of Prompt Tuning for Vision-Language Models [37.85176585188362]
  We propose Model-Agnostic Optimization (MAO) for prompt tuning. We introduce a Data-Driven Enhancement framework to optimize the distribution of the initial data. We incorporate an Alterable Regularization module to boost the task-specific feature processing pipeline.
  arXiv  Detail & Related papers  (2025-03-23T17:59:33Z)
• Performance-driven Constrained Optimal Auto-Tuner for MPC [36.143463447995536]
  We propose COAT-MPC, Constrained Optimal Auto-Tuner for MPC. COAT-MPC gathers performance data and learns by updating its posterior belief. We theoretically analyze COAT-MPC, showing that it satisfies performance constraints with arbitrarily high probability.
  arXiv  Detail & Related papers  (2025-03-10T09:56:08Z)
• DRPruning: Efficient Large Language Model Pruning through Distributionally Robust Optimization [61.492590008258986]
  Large language models (LLMs) deliver impressive results but face challenges from increasing model sizes and computational costs. We propose DRPruning, which incorporates distributionally robust optimization to restore balanced performance across domains.
  arXiv  Detail & Related papers  (2024-11-21T12:02:39Z)
• Respecting the limit:Bayesian optimization with a bound on the optimal value [3.004066195320147]
  We study the scenario that we have either exact knowledge of the minimum value or a, possibly, lower bound on its value. We present SlogGP, a new surrogate model that incorporates bound information and adapts the Expected Improvement (EI) acquisition function accordingly.
  arXiv  Detail & Related papers  (2024-11-07T14:27:49Z)
• Tender: Accelerating Large Language Models via Tensor Decomposition and Runtime Requantization [0.6445087473595953]
  Large language models (LLMs) demonstrate outstanding performance in various tasks in machine learning. deploying LLM inference poses challenges due to the high compute and memory requirements. We present Tender, an algorithm-hardware co-design solution that enables efficient deployment of LLM inference at low precision.
  arXiv  Detail & Related papers  (2024-06-16T09:51:55Z)
• Submodular Framework for Structured-Sparse Optimal Transport [7.030105924295838]
  Unbalanced optimal transport (UOT) has recently gained much attention due to its flexible framework for handling unnormalized measures and its robustness. In this work, we explore learning (structured) sparse transport plans in the UOT setting, i.e., transport plans have an upper bound on the number of non-sparse entries in each column. We propose novel sparsity-constrained UOT formulations building on the recently explored mean discrepancy based UOT.
  arXiv  Detail & Related papers  (2024-06-07T13:11:04Z)
• Spurious Feature Eraser: Stabilizing Test-Time Adaptation for Vision-Language Foundation Model [86.9619638550683]
  Vision-language foundation models have exhibited remarkable success across a multitude of downstream tasks due to their scalability on extensive image-text paired data. However, these models display significant limitations when applied to downstream tasks, such as fine-grained image classification, as a result of decision shortcuts''
  arXiv  Detail & Related papers  (2024-03-01T09:01:53Z)
• FuzzyFlow: Leveraging Dataflow To Find and Squash Program Optimization Bugs [92.47146416628965]
  FuzzyFlow is a fault localization and test case extraction framework designed to test program optimizations. We leverage dataflow program representations to capture a fully reproducible system state and area-of-effect for optimizations. To reduce testing time, we design an algorithm for minimizing test inputs, trading off memory for recomputation.
  arXiv  Detail & Related papers  (2023-06-28T13:00:17Z)
• Performance Embeddings: A Similarity-based Approach to Automatic Performance Optimization [71.69092462147292]
  Performance embeddings enable knowledge transfer of performance tuning between applications. We demonstrate this transfer tuning approach on case studies in deep neural networks, dense and sparse linear algebra compositions, and numerical weather prediction stencils.
  arXiv  Detail & Related papers  (2023-03-14T15:51:35Z)
• Self-Supervised Learning via Maximum Entropy Coding [57.56570417545023]
  We propose Maximum Entropy Coding (MEC) as a principled objective that explicitly optimize on the structure of the representation. MEC learns a more generalizable representation than previous methods based on specific pretext tasks. It achieves state-of-the-art performance consistently on various downstream tasks, including not only ImageNet linear probe, but also semi-supervised classification, object detection, instance segmentation, and object tracking.
  arXiv  Detail & Related papers  (2022-10-20T17:58:30Z)
• DQ-BART: Efficient Sequence-to-Sequence Model via Joint Distillation and Quantization [75.72231742114951]
  Large-scale pre-trained sequence-to-sequence models like BART and T5 achieve state-of-the-art performance on many generative NLP tasks. These models pose a great challenge in resource-constrained scenarios owing to their large memory requirements and high latency. We propose to jointly distill and quantize the model, where knowledge is transferred from the full-precision teacher model to the quantized and distilled low-precision student model.
  arXiv  Detail & Related papers  (2022-03-21T18:04:25Z)
• Risk Guarantees for End-to-End Prediction and Optimization Processes [0.0]
  We study conditions that allow us to explicitly describe how the prediction performance governs the optimization performance. We derive the exact theoretical relationship between prediction performance measured with the squared loss, as well as a class of symmetric loss functions, and the subsequent optimization performance.
  arXiv  Detail & Related papers  (2020-12-30T05:20:26Z)

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.