We introduce Faithful Logic-Aided Reasoning and Exploration (FLARE), a novel interpretable approach for traversing the problem space using task decompositions. FLARE uses the LLM to plan a solution, soft-formalise the query into facts and predicates using logic programming, and simulate code execution using an exhaustive multi-hop search over the defined space.

Our method allows us to compute the faithfulness of the reasoning process and analyse the steps of the multi-hop search without relying on external solvers. We achieve state-of-the-art results on 7 out of 9 diverse reasoning benchmarks, demonstrating that model faithfulness positively correlates with overall performance.