PaperlayerView exact revision on arXiv

Source-linked AI summary

Neurosymbolic Routing for Reliable Reasoning on Resource-Constrained Edge Devices

Avyay Sadhu, Alvaro Velasquez, Lekai Chen

arXiv:2609.35833v1cs.AIcs.CL

TL;DR

Small language models on edge devices struggle with structured reasoning, even when symbolic solvers can answer such queries exactly. The paper learns a DFA router to send structured tasks to symbolic engines and reserve the SLM for word problems. On a Raspberry Pi 4B, learned routing reaches 98.3% accuracy at a 512-token budget and outperforms the tool-calling agent with the same solvers.

  • Problem

    Small models that fit on edge devices are unreliable on structured tasks such as arithmetic, algebra, and formal logic, despite those tasks often having exact symbolic solutions.

    Source: §I · p. 1

  • Method

    The system learns a DFA router with L* grammatical inference to dispatch structured queries to symbolic solvers and word problems to the SLM.

    Source: §I · p. 2

  • Results

    98.3% end-to-end accuracy at a 512-token reasoning budget and 78.0% at a 30-token budget, versus 58.7% for a tool-calling agent with the same solvers.

    Source: §X · p. 11

  • Takeaways & Limitations

    Structured queries can be answered by symbolic solvers without invoking the SLM, while word problems remain the model-dependent path.

    Source: §I · p. 1, §X · p. 11

    Word problems require a 512-token budget to reach 93–96% accuracy, consuming roughly seven times the energy of the 30-token setting and more than two minutes of CPU time per prompt.

    Source: §X · p. 11

Abstract

from arXiv · show

Running a language model on edge hardware provides private and low-latency reasoning without a network connection, and yet the small models that fit on such devices are unreliable on the tasks computers are expected to handle well, such as arithmetic, algebra, and formal logic problems. We argue that much of this unreliability is avoidable. Many queries appearing to demand reasoning are in fact structurally deterministic and permit fast and exact symbolic solutions. Therefore, forcing a probabilistic model to approximate them sacrifices accuracy and energy for little benefit. We present a neurosymbolic router that classifies each incoming query and dispatches it to the cheapest correct solver, sending structured tasks to deterministic engines and reserving the small language model (SLM) for open-ended word problems. Instead of hand-coding the routing logic, we learn a deterministic finite automaton (DFA) with the L* grammatical inference algorithm, using the SLM as a membership oracle and labeled data as an equivalence oracle. On a Raspberry Pi 4B (8 GB RAM, no GPU), evaluated on 100 untested prompts from DeepMind Mathematics, GSM8K, and RuleTaker, learned routing attains 100% routing accuracy and 98.3% overall accuracy with a 512-token reasoning budget (93.3% on word problems), compared with 72.0% for the strongest agent baseline, Program-of-Thought, and 58.7% for a tool-calling agent given the same solvers. Since formatted queries never reach the model, the router answers them in 1-11 ms and, in its 30-token configuration, runs 8.8x faster and 2.8x more energy-efficient than Program-of-Thought.

I. INTRODUCTION

Small edge language models struggle with structured tasks despite the availability of exact symbolic solutions, making reliable query recognition the central challenge. The paper proposes learned routing to reserve neural inference for open-ended problems and evaluates it against agent baselines on edge hardware.

I. INTRODUCTION

  • Small CPU-only edge models struggle most on arithmetic, algebra, and formal-logic questions with single correct answers, while structured queries can have exact, faster, cheaper symbolic solutions.The central routing challenge is recognizing such inputs before expensive inference.Source: §I · p. 1
  • The router classifies queries as arithmetic, algebra, logic, or word problems, sending structured categories to deterministic solvers and word problems to the SLM.Only word problems are described as genuinely requiring natural-language comprehension and multi-step reasoning; structured solvers answer in milliseconds.Source: §I · p. 1
  • On the balanced benchmark, structured categories make up three-quarters of queries, so the model is invoked for only a minority; deployment proportions depend on workload.The evaluation uses a Raspberry Pi 4B and 100 held-out prompts from DeepMind Mathematics, GSM8K, and RuleTaker, with three repeats per prompt.Source: §I · p. 2
  • 78.0% task accuracy vs. 58.7% for the tool-calling agent, while L*-learned routing is 2.4× faster and 2.3× more energy-efficient.Against Program-of-Thought, it achieves 6 percentage points higher accuracy than the 72.0% baseline, with 8.8× lower latency and 2.8× less energy per prompt.Source: §I · p. 2

A. Edge Inference

  • Prior edge-inference work explores quantization, pruning, and distillation; this approach is complementary because it reduces queries sent to the SLM rather than optimizing the model.The cited examples include local use where connectivity is unavailable or data must remain on-device.Source: §I · p. 1, A. Edge Inference · p. 2

B. Neurosymbolic AI

The paper places its router among neurosymbolic systems, agent frameworks, grammatical inference, and model-routing approaches. Its design makes routing decisions with a learned DFA before invoking the SLM, while dispatching queries among distinct symbolic and neural solvers.

B. Neurosymbolic AI

  • Routing happens before SLM invocation: a learned DFA makes the decision without inference cost, unlike tool-use approaches that ask the model when to invoke tools.The router dispatches among symbolic engines and neural inference rather than choosing among models of different sizes.Source: B. Neurosymbolic AI · p. 2, E. LLM Routing and Cascading · p. 3

C. Agent Reasoning Framework Baselines

  • Agent baselines represent interleaved reasoning, code generation, and plan-then-execute; each requires one or more SLM steps to decide which tool to invoke.The evaluated frameworks are ReAct, Program-of-Thought, and Plan-and-Solve.Source: C. Agent Reasoning Framework Baselines · p. 2

D. Grammatical Inference

  • Grammatical inference learns formal languages from data; L* uses membership and equivalence oracles, whereas RPNI learns passively from positive and negative examples.The paper presents this as its first application to neurosymbolic query routing on edge devices.Source: D. Grammatical Inference · p. 2

E. LLM Routing and Cascading

  • Unlike model cascades that select among model sizes, this router chooses between qualitatively different solvers: symbolic engines or neural inference..Source: E. LLM Routing and Cascading · p. 3

F. Mathematical Reasoning

  • The paper distinguishes its category-level routing from approaches that use tools within generation, routing entire categories to symbolic solvers rather than individual arithmetic operations.The comparison is to chain-of-thought and tool-augmented mathematical reasoning.Source: F. Mathematical Reasoning · p. 3

A. Overview

  • Each query passes through a category classifier and dispatcher; the final system replaces the development regex classifier with a learned DFA at identical zero inference cost.The dispatcher invokes one of four solver modules.Source: A. Overview · p. 3

1) Solver Naming Convention:

  • The solver labels A1–A6 follow internal development order, not their order of introduction in the paper.The primary mappings are A5 for arithmetic, A4 for algebra, A6 for logic, and A2 for word problems; A1 and A3 are fallback and repair actions.Source: 1) Solver Naming Convention · p. 3

B. Primary Solvers •

The system pairs deterministic arithmetic, algebra, and logic solvers with SLM inference for word problems, while replacing brittle hand-coded routing with a learned classifier. A fallback chain is introduced for primary-solver failures.

B. Primary Solvers •

  • The primary solvers are a safe arithmetic evaluator, SymPy algebra solver, forward-chaining logic engine, and SLM chain-of-thought for word problems.Arithmetic evaluation restricts allowed AST nodes and caps exponents; algebra supports single- and multi-variable linear systems, while the logic engine uses a 50-iteration bound.Source: B. Primary Solvers • · pp. 3–4

C. Classifier Design

  • The learned DFA reaches 100% routing accuracy on held-out prompts with < 0.05 ms classification latency on the Pi, replacing regex rules with patterns learned from data.The earlier regex classifier achieved 100% routing accuracy on the benchmark but was considered brittle because adversarial phrasing could bypass patterns.Source: C. Classifier Design · p. 4

D. Fallback Chains

  • When a primary solver fails, such as when SymPy cannot parse an equation, the system escalates through a fallback chain.Source: D. Fallback Chains · p. 4

E. A6: Forward-Chaining Logic Engine

The logic engine converts RuleTaker-style language into structured facts and rules, repeatedly derives consequences, and evaluates queries under a closed-world assumption. For DFA learning, queries are abstracted into a finite token-class alphabet and bounded sequences.

E. A6: Forward-Chaining Logic Engine

1) Parsing:

  • Natural-language statements are converted into structured facts and rules, such as encoding “All cats are animals” as a rule from cat to animal.Source: 1) Parsing · p. 4

2) Forward Chaining:

  • Rules are applied until no new facts can be produced or a 50-iteration safety bound is reached; newly derived facts are available immediately within the same iteration.Source: 2) Forward Chaining · p. 4

3) Query Evaluation:

  • Under the closed-world assumption, a query is answered “Yes” if its fact is in the derived set and “No” otherwise.Source: 3) Query Evaluation · p. 4

IV. LEARNED ROUTING VIA GRAMMATICAL INFERENCE

  • The paper motivates learned routing as a response to brittle regex patterns that may misroute logic queries phrased unexpectedly.Source: §IV · p. 4

A. Token-Class Abstraction

  • The DFA input uses 12 abstract token classes; consecutive narrative tokens are collapsed and sequences truncated to 15 tokens, preserving category structure in a finite alphabet.The classes include commands, numbers, variables, operators, parentheses, entities, properties, rule keywords, question markers, narrative words, units, and sentence-ending punctuation.Source: A. Token-Class Abstraction · p. 4

B. L* Algorithm for Route Learning

L* learns routing DFAs by refining an observation table with membership and equivalence queries. A closed, consistent table yields an automaton whose states represent E-equivalence classes and whose accepting states match the target language.

B. L* Algorithm for Route Learning

  • L* learns a regular language through membership and equivalence queries, refining its observation table when a counterexample is found.Membership queries label words; equivalence queries test a hypothesis DFA and can return a counterexample.Source: B. L* Algorithm for Route Learning · pp. 4–5
  • For a closed, consistent observation table, each E-equivalence class of state words becomes a DFA state, with transitions determined by closedness and accepting states set by the teacher’s language.Consistency makes the successor state unique.Source: B. L* Algorithm for Route Learning · p. 5
  • In the arithmetic example, L* accepts {CMD}{NUM}{OP}{NUM}; the equivalence oracle finds no counterexample, and the learned DFA processes a query in under 0.05 ms without an SLM call.The DFA starts at q0, accepts the arithmetic pattern at q2, and rejects other sequences at q⊥.Source: B. L* Algorithm for Route Learning · p. 5, Figure 2 · p. 5
  • The learning setup uses the SLM as a membership oracle and labeled training data as the equivalence oracle for one-vs-rest category DFAs.For synthetic sequences without natural-language counterparts, a feature-based classifier supplies membership labels.Source: B. L* Algorithm for Route Learning · p. 5

C. RPNI: Passive DFA Learning as a Component Variant

The section describes RPNI as a replaceable passive DFA-learning component, then specifies how category DFAs are combined and how the evaluation data and edge-device setup are organized.

C. RPNI: Passive DFA Learning as a Component Variant

  • RPNI is a passive grammatical-inference algorithm that learns DFAs from positive and negative examples without an oracle, and can replace L* without changing the routing architecture or solvers.This variant is intended to isolate the contribution of the SLM membership oracle.Source: C. RPNI: Passive DFA Learning as a… · p. 5

D. Multi-Class Classification

  • The four binary category DFAs form a multiclass classifier using priority LOG > ALG > AR > WP, with WP as the default when none accepts.A query is assigned to the highest-priority accepting DFA.Source: D. Multi-Class Classification · pp. 5–6

A. Hardware

  • Experiments run on a Raspberry Pi 4 Model B with 8 GB RAM and a quad-core 1.8 GHz CPU, without a GPU or neural accelerator.Models run in CPU-only mode with four threads.Source: A. Hardware · p. 6

B. Models

  • The evaluation uses quantized Phi-4-mini and Qwen2.5-Math-1.5B models, with greedy decoding at temperature 0.0 and seed 42.Phi-4-mini has 3.8B parameters and Q6 K quantization; Qwen2.5-Math-1.5B has 1.5B parameters and Q6 K quantization.Source: B. Models · p. 6

C. Dataset

  • The evaluation uses 100 held-out test prompts (25 per category) sampled from three established datasets, with exact-match scoring and three runs per system configuration (300 trials per system).Source: C. Dataset · p. 6

D. Tool-Calling Agent Baseline

The baseline gives the same SLM access to the same symbolic solvers through tool calls, while defining the metrics and error categories used to evaluate it.

D. Tool-Calling Agent Baseline

  • The tool-calling baseline gives Phi-4-mini access to arithmetic, algebra, logic, and direct-answer tools, with the model generating a single tool call for each query.It requires an SLM inference step even for simple arithmetic that a solver could handle in 1 ms.Source: D. Tool-Calling Agent Baseline · p. 6

E. Metrics •

  • Evaluation metrics are exact-match accuracy, wall-clock latency per inference, and energy per prompt measured with a USB power meter.Latency runs from prompt submission to answer extraction; energy is total run energy divided by prompts.Source: E. Metrics • · p. 6

F. Error Taxonomy

  • The error taxonomy distinguishes correct answers, arithmetic, logic, algebra, and word-problem errors, timeouts, and parse failures.The labels are E0, E1, E2, E3, E5, E7, and E8, respectively.Source: F. Error Taxonomy · p. 6

VI. SYSTEM VERSIONS AND ABLATION

The system progresses from an unreliable SLM-only baseline through solver and post-processing variants, then compares learned routing with a tool-calling agent. The full-budget learned router reaches 98.3% accuracy, while its efficiency depends on the operating point.

A. Baseline: SLM-Only

  • The SLM-only baseline’s best configuration reaches 37.3% overall accuracy, and 17% of trials fail because its output cannot be parsed.This best baseline uses 30 tokens, grammar constraints, and Phi-4-mini.Source: A. Baseline: SLM-Only · p. 7

B. V1: Arithmetic Solver (+A5)

  • Routing arithmetic to a safe evaluator raises arithmetic accuracy from 48% to 100%, reduces latency from 6.2 s to 1 ms, and raises overall accuracy to 53.0%.Source: B. V1: Arithmetic Solver (+A5) · p. 7

C. V2: Algebra Solver (+A4)

  • Adding SymPy raises algebra accuracy from 40% to 96–100%, drops its latency from 5.8 s to 11 ms, and lifts overall accuracy to 67.0%.Source: C. V2: Algebra Solver (+A4) · p. 7

D. V3: Post-Processing Repair Layer (+A3)

  • The answer-repair module raises word-problem accuracy from 8% to 18.7%, but its numeric extraction corrupts yes/no logic answers, reducing logic accuracy from 64% to 36.7%.Restricting repair to numeric categories restores logic accuracy to 64% and brings overall accuracy to 70.7%.Source: D. V3: Post-Processing Repair Layer… · p. 7

E. V4: Confidence Calibration

F. V5: Logic Engine and a Larger Reasoning Budget (+A6, +CoT)

  • The 512-token word-problem budget lifts V5 to 99.0% overall accuracy, with perfect arithmetic, algebra, and logic results and 96% on word problems.A forward-chaining logic engine reaches 100% accuracy in under 1 ms; one word problem fails consistently across three repeats.Source: F. V5: Logic Engine and a Larger… · p. 7

A. Learned Routing vs. Tool-Calling Agent

  • At a 512-token budget, the L*-learned router achieves 98.3% overall accuracy versus 58.7% for the tool-calling agent, with 100% accuracy on arithmetic, algebra, and logic and 93.3% on word problems.The comparison uses the same SLM and symbolic solvers; the agent often fails to invoke the logic engine or emits malformed algebra tool calls.Source: A. Learned Routing vs. Tool-Calling… · p. 7
  • At the 30-token operating point, the router is 2.4× faster than the agent (6,907 ms vs. 16,439 ms mean latency) and uses 2.3× less energy (33.1 vs. 75.0 mWh per prompt).Raising the word-problem budget to 512 tokens increases overall energy to 141.3 mWh per prompt.Source: A. Learned Routing vs. Tool-Calling… · p. 7

B. Comparison with Agent Reasoning Frameworks

L*-learned routing outperforms the agent baselines while routing structured queries to symbolic solvers; its classifier reaches 100% accuracy on held-out prompts. The reported comparisons also show sharp gains when deterministic solvers are added to the development system.

B. Comparison with Agent Reasoning Frameworks

  • 6 percentage points separate L*-learned routing from the strongest agent, Program-of-Thought at 72.0%; ReAct scores 63.0% and Plan-and-Solve 43.0%.Program-of-Thought is strongest on word problems and algebra (88% each) but scores 16% on logic.Source: B. Comparison with Agent Reasoning… · pp. 7–8
  • 100% accuracy on AR, ALG, and LOG is achieved by L*-learned routing via symbolic solvers, while word problems remain challenging for all systems.The tool-calling agent scores 59% on LOG and 76% on ALG.Source: Figure 3 · p. 8
  • 2.4× faster and 2.3× more energy-efficient is learned routing (L* and RPNI) than the tool-calling agent, as structured queries bypass the SLM.Source: Figure 4 · p. 8

C. Classification Accuracy

  • 100% held-out routing accuracy is achieved by L* with both the SLM and feature-based oracles, versus 86% for RPNI, whose WP routing accuracy is 64%.Source: C. Classification Accuracy · p. 8

D. V1–V5 Development Ablation

  • 99.0% accuracy is reached by hand-coded V5 at 512 tokens, compared with 79.7% in its 30-token configuration.The V1–V5 progression adds one component at a time, serving as an ablation.Source: D. V1–V5 Development Ablation · p. 8

E. Per-Category Accuracy

  • Symbolic solvers achieve perfect accuracy on their respective domains, as shown in the per-category comparison with learned routing and the development ablation.Source: E. Per-Category Accuracy · p. 8

F. Latency Analysis

Symbolic routes are fast, but word-problem latency and energy rise with the higher reasoning-token budget. The reported V5 errors are confined to one repeatedly failed word problem with an ambiguous referent.

G. Energy–Accuracy Tradeoff

H. Error Distribution

  • V5 at 512 tokens eliminates all error types except E5, with three word-problem errors across 300 trials arising from one prompt repeated three times.Source: H. Error Distribution · p. 9

A. Why Symbolic Routing Works

  • Solver introductions produce abrupt category-specific gains: arithmetic rises from 48% to 100% with A5, algebra from 40% to 96–100% with A4, and logic from 64% to 100% with A6.The paper attributes these jumps to replacing probabilistic approximation with exact computation when problem structure is known.Source: A. Why Symbolic Routing Works · p. 9

B. Error Analysis: The Single V5 Failure

  • The sole V5 failure has an expected answer of 200, but both models repeatedly produce 240 by treating an ambiguous reference as the updated cannoli count.The paper describes the shared interpretation as a systematic parsing bias rather than a stochastic error.Source: B. Error Analysis: The Single V5 Failure · p. 9

F. Latency Analysis

  • 531–6,288× speedups are reported for symbolic solvers on structured categories; the system-wide median is 6 ms, while WP takes approximately 137 s per prompt.The system-wide median reflects symbolic routes handling 75% of queries; WP latency increased from 25 s with the higher token budget.Source: F. Latency Analysis · p. 8, Figure 5 · p. 9

C. Model Comparison

At 300 tokens, Phi-4-mini is more accurate on word problems than Qwen, while both models match on symbolic categories because those queries never reach the model. The learned router’s benchmark generalization is bounded by category separation and remains vulnerable to adversarial phrasing.

C. Model Comparison

  • 100% symbolic-category accuracy is identical across models because those queries never reach the model.Source: C. Model Comparison · p. 9
  • 92.0% WP accuracy for Phi-4-mini versus 64.0% for Qwen at 300 tokens; both reach 99.0% overall and 96.0% WP accuracy at 512 tokens.The word-problem accuracy-by-token-budget comparison is shown in Table VIII.Source: C. Model Comparison · p. 9, Table VIII · p. 10

A. Generalizability

  • The four-category benchmark does not cover areas such as commonsense or spatial reasoning, but extending the router requires additional examples and a new DFA rather than manual regex engineering.Source: A. Generalizability · p. 10

B. Classifier Robustness

  • 100% held-out routing accuracy reflects well-separated benchmark categories, not adversarial robustness; crafted queries could still cause misclassification.Token-class abstraction offers some paraphrase robustness, and a solver-failure fallback is identified as a possible improvement.Source: B. Classifier Robustness · p. 10

C. Active vs. Passive Learning

  • L* achieves 100% classification and 78.0% task accuracy, versus RPNI’s 86% classification and 74.3% task accuracy.The difference is attributed to L*’s SLM membership oracle, which can query novel token sequences; RPNI’s word-problem routing is difficult to learn from 10 positive examples alone.Source: C. Active vs. Passive Learning · p. 10

D. Dataset Size

The paper reports strong end-to-end results, but its small benchmark and the cost of word-problem inference constrain the practical picture. Symbolic solvers deliver category-specific gains, while word-problem latency and energy remain important limits.

D. Dataset Size

  • 100 prompts, 25 per category, make the benchmark small; 99.0% accuracy has a 95% Wilson interval of [97.1%, 99.8%], while 96% WP accuracy has [80.5%, 99.3%].Figure 6 reports both models at 96% WP accuracy with 512 tokens and says Phi-4-mini is more token-efficient at 300 tokens.Source: D. Dataset Size · p. 10, Figure 6 · p. 10

E. Energy–Accuracy Tradeoff

  • 2.8× more energy than the baseline is required by the best-accuracy system, V5 at 512 tokens; its WP generation uses 211.1 mWh versus 30.6 mWh at 30 tokens.Source: E. Energy–Accuracy Tradeoff · p. 10

F. Scalability of Symbolic Solvers

  • The current solvers cover single-variable linear equations, basic arithmetic, and propositional logic; broader equation systems and first-order logic require more powerful solvers.The routing architecture would remain unchanged.Source: F. Scalability of Symbolic Solvers · p. 10

G. Practical WP Latency

  • 137 s per prompt at 512 tokens makes word-problem inference acceptable for batch or non-interactive use but prohibitive for real-time use on the Pi 4B CPU.Source: G. Practical WP Latency · p. 10

X. CONCLUSION

  • Each symbolic solver adds a discontinuous gain in its target category, where accuracy reaches 100% upon its introduction.Figure 7 shows accuracy by category across system versions and configurations.Source: Figure 7 · p. 11, §X · p. 11
  • 98.3% end-to-end accuracy at 512 tokens and 78.0% at 30 tokens, versus 58.7% for a tool-calling agent with the same solvers.On the Pi 4B, the router is 2.4× faster and 2.3× more energy-efficient at its efficient operating point, with structured queries dispatched in 1–11 ms without invoking the SLM.Source: §X · p. 11
  • 93–96% word-problem accuracy requires 512 tokens, roughly seven times the energy of the 30-token setting and more than two minutes of CPU time per prompt.Adaptive token budgets, faster accelerators, and larger evaluations are identified as directions for future work.Source: §X · p. 11

Related papers

Loading 2609.35833v1…