Transforming and Encoding FTS for SAT Solving: What Helps, What Hurts (Extended Version)
Summary
This paper investigates how to encode factored planning tasks (FTS) into SAT, proposing multiple encoding strategies and analyzing the impact of task transformations on SAT-based planning performance. It aims to extend SAT solving to more compact planning representations beyond heuristic search.
View Cached Full Text
Cached at: 06/01/26, 09:23 AM
# Transforming and Encoding FTS for SAT Solving: What Helps, What Hurts (Extended Version) Source: [https://arxiv.org/abs/2605.30563](https://arxiv.org/abs/2605.30563) [View PDF](https://arxiv.org/pdf/2605.30563) > Abstract:Factored tasks are a classical planning representation that extends SAS\+ with limited forms of disjunctive preconditions, conditional effects, and angelic nondeterminism\. This allows for a more compact representation of tasks than traditional formalisms such as STRIPS or SAS\+, and supports a wide range of task transformations\. However, existing planning approaches for factored tasks have been limited to heuristic search methods\. In this work, we investigate how to encode factored tasks in SAT\. We propose several ways to encode the tasks, focusing on different strategies for translating the factored transition relation into propositional logic\. We also analyze how to exploit parallelism at various levels in this setting and study the impact of common task transformations on the performance of SAT\-based planners\. ## Submission history From: Gregor Behnke \[[view email](https://arxiv.org/show-email/cec7f8d2/2605.30563)\] **\[v1\]**Thu, 28 May 2026 20:50:52 UTC \(662 KB\)
Similar Articles
Accelerated Fourier SAT (AFSAT): Fully Realising a GPU-based Symmetric Pseudo-Boolean SAT Solver
This paper presents Accelerated Fourier SAT (AFSAT), a GPU-accelerated solver for pseudo-Boolean satisfiability based on continuous local search. It improves upon prior proof-of-concept implementations by supporting heterogeneous constraints and leveraging JAX for parallel computation.
How to Fine-Tune a Reasoning Model? A Teacher-Student Cooperation Framework to Synthesize Student-Consistent SFT Data
This paper introduces TESSY, a teacher-student cooperative framework for fine-tuning reasoning models that generates on-policy SFT data by decoupling generation into capability tokens (from teacher) and style tokens (from student), addressing catastrophic forgetting issues when using off-policy teacher data.
Contrastive targeted SFT as a mechinterp method - has anyone mapped causal dependency interactions this way? [D]
A researcher shares an experimental plan for identifying causal dependencies between capability dimensions in a 31B model using contrastive targeted SFT and circuit tracing, seeking feedback on methodology and related work.
Transformers Linearly Represent Highly Structured World Models
This paper demonstrates that transformers trained on Sudoku solving traces build structured world models organized by domain constraints, and identifies a sparse, monosemantic circuit responsible for the naked-single decision rule. The work provides a fully interpretable algorithmic account of transformer reasoning on a combinatorial task.
FocuSFT: Bilevel Optimization for Dilution-Aware Long-Context Fine-Tuning
The paper introduces FocuSFT, a bilevel optimization framework that enhances long-context language model performance by addressing attention dilution through parametric memory. It demonstrates significant improvements in accuracy and context engagement on benchmarks like BABILong and RULER.