Neurosymbolic Routing for Reliable Reasoning on Resource-Constrained Edge Devices

Avyay Sadhu; Alvaro Velasquez; Lekai Chen

cs.AISep 24, 2026

Neurosymbolic Routing for Reliable Reasoning on Resource-Constrained Edge Devices

Authors: Avyay Sadhu, Alvaro Velasquez, Lekai Chen

Organizations: independent researcher · Department of Computer Science, University of Colorado Boulder, Boulder, CO 80309 USA

Abstract

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.

Figures & tables

Fig. 1: Overview of the proposed learned neurosymbolic routing architecture for reliable reasoning on resource-constrained edge devices. A local SLM running on a Raspberry Pi struggles with structured reasoning tasks, while an $L^{\ast}$ -learned DFA router classifies incoming queries into arithmetic (AR), algebra (ALG), logic (LOG), or word-problem (WP) categories. Structured queries are dispatched to deterministic symbolic solvers, whereas open-ended word problems are routed to the local SLM, reducing unnecessary neural inference while preserving flexibility.

$S\setminus E$	$\varepsilon$	CMD	CMD · NUM
$\varepsilon$	$\times$	$\times$	$\times$
CMD	$\times$	$\times$	$\times$
CMD · NUM	$\times$	$\checkmark$	$\checkmark$
CMD · NUM · OP	$\times$	$\times$	$\checkmark$
CMD · NUM · OP · NUM	$\times$	$\checkmark$	$\checkmark$

TABLE I: Example observation table

(S,E,T)

built by

L^{\star}

for

\mathcal{L}_{AR}

\checkmark

= word belongs to the language,

\times

= rejected. Rows above the dashed line are state words

S

; rows below are frontier words

S\cdot\Sigma

Fig. 2: DFA $\mathcal{A}_{AR}$ learned by $L^{\star}$ from the observation table above. States correspond to $E$ -equivalence classes of $S$ ; $q_{2}$ (double circle) is the accepting state. Red transitions lead to the dead/reject state $q_{\perp}$ .

Fig. 3: End-to-end task accuracy by category. L*-learned routing achieves 100% on AR, ALG, and LOG via symbolic solvers, while the tool-calling agent struggles on all categories, particularly LOG (59%) and ALG (76%). Word problems remain challenging for all systems.

Fig. 4: Efficiency comparison. Learned routing (L* and RPNI) is 2.4 $\times$ faster and 2.3 $\times$ more energy-efficient than the tool-calling agent, because AR, ALG, and LOG queries bypass the SLM entirely.

System	AR	ALG	WP	LOG	All
L* routing $\to$ V5 (512tok)	100	100	93	100	98.3
L* routing $\to$ V5 (30tok)	100	100	12	100	78.0
RPNI routing $\to$ V5	96	96	13	92	74.3
Agent framework baselines
Program-of-Thought [ 7 ]	96	88	88	16	72.0
ReAct [ 6 ]	92	52	68	40	63.0

TABLE II: End-to-End Task Accuracy on T2 (300 trials, 3 repeats). The 512-token result uses chain-of-thought prompting for WP; agent baselines use 1 repeat.

System	Lat. (ms)	mWh/p	Route (%)
L* $\to$ V5	6,907	33.1	100.0
RPNI $\to$ V5	6,567	30.2	86.0
Program-of-Thought	60,870	94.7	n/a
ReAct	97,193	150.3	n/a
Tool-calling agent	16,439	75.0	n/a
Plan-and-Solve	82,521	123.9	n/a

TABLE III: Efficiency Comparison on T2 (Same Hardware, Same Model)

Classifier	AR	ALG	WP	LOG	All
L* (SLM oracle)	100	100	100	100	100.0
L* (feature oracle)	100	100	100	100	100.0
RPNI (passive)	96	92	64	92	86.0
Feature classifier	100	100	100	100	100.0

TABLE IV: Routing Classification Accuracy on T2 (100 Prompts)

System	Acc. (%)	Med. Lat. (ms)	E (mWh/p)
SLM-only baseline	37.3	8,612	75.0
V1 (+A5 arith.)	53.0	4,147	75.9
V2 (+A4 algebra)	67.0	2,598	37.2
V3.1 (+A3 repair)	70.7	1,413	34.0
V5 (30 tokens)	79.7	6	30.6
V5 (512 tokens)	99.0	6	211.1

TABLE V: V1–V5 Development Ablation (300 Trials Each, Hand-Coded Routing)

System	AR	ALG	WP	LOG	All
Learned routing (this work)
L* routing $\to$ V5 (512tok)	100	100	93	100	98.3
L* routing $\to$ V5 (30tok)	100	100	12	100	78.0
RPNI routing $\to$ V5	96	96	13	92	74.3
Tool-calling agent	95	76	5	59	58.7
V1–V5 ablation (hand-coded routing)

TABLE VI: Per-Category Accuracy (%): Learned Routing vs. Development Ablation

Fig. 5: Per-category median latency on a log scale: baseline vs. V5. Symbolic solvers achieve 531–6,288 $\times$ speedups on structured categories. WP latency increases due to the higher token budget.

System	AR (ms)	ALG (ms)	LOG (ms)	WP (s)
Baseline (best)	6,288	5,838	2,672	25.6
V5 (512tok)	1	11	2	137.2

TABLE VII: Median Latency by Category

Model	Tok.	CoT	WP (%)	Lat. (s)	E (mWh/p)
Phi-4-mini	30	No	18.7	26.0	30.6
Phi-4-mini	300	Yes	92.0	128.6	147.2
Phi-4-mini	512	Yes	96.0	135.2	211.1
Qwen-1.5B	30	No	18.7	26.0	30.6
Qwen-1.5B	300	Yes	64.0	100.1	113.1
Qwen-1.5B	512	Yes	96.0	128.2	147.6

TABLE VIII: Word-Problem Accuracy vs. Token Budget

Fig. 6: Word-problem token budget ablation for two SLMs: accuracy (left) and energy cost (right) as a function of token budget. Both models converge to 96% at 512 tokens, but Phi-4-mini is more token-efficient at 300 tokens.

System	E0	E1	E2	E3	E5	E7	E8
Baseline	112	36	26	45	21	9	51
V1 (+A5)	159	0	27	45	24	0	45
V2 (+A4)	201	0	27	3	24	0	45
V3.1 (+A3)	212	0	27	0	18	30	13
V5 (512)	297	0	0	0	3	0	0

TABLE IX: Error Distribution (300 Trials Each). E0 = Correct

Fig. 7: Accuracy by category across all system versions and configurations. Each column is a category; each row is a system version. Symbolic solvers (A5, A4, A6) produce immediate 100% accuracy in their target categories upon introduction.

Automata Learning

See all 15 papers

Efficient Reasoning on the Edge
Mar 17, 2026Yelysei Bondarenko, Thomas Hehn, Rob Hesselink +15Efficient Language Model Reasoning On-Device Language Model Inference
Qualcomm AI Research is an initiative of Qualcomm Technologies, Inc.
Policy-Guided Stepwise Model Routing for Cost-Effective Reasoning
May 7, 2026Wenwen Si, Insup Lee, Osbert BastaniCost-Aware Inference Efficient Language Model Reasoning
Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104, USA
RouteGoT: Node-Adaptive Routing for Cost-Efficient Graph of Thoughts Reasoning
Mar 6, 2026Yuhang Liu, Ruijie Wang, Yunlong Chu +4LLM Reasoning with Graphs Efficient Language Model Reasoning
School of New Media and Communication, Tianjin University, Tianjin, China · School of Computer Science and Engineering, Beihang University, Beijing, China · Shanghai Jiao Tong University, Shanghai, China

Mar 17, 2026J/K move · Enter open · S save

Efficient Reasoning on the Edge

Yelysei Bondarenko, Thomas Hehn, Rob Hesselink, Romain Lepert+14

Qualcomm AI Research is an initiative of Qualcomm Technologies, Inc.

Efficient Language Model Reasoning On-Device Language Model Inference Memory-Efficient Inference

Open paper AskPDF arXiv

Large language models (LLMs) with chain-of-thought reasoning achieve state-of-the-art performance across complex problem-solving tasks, but their verbose reasoning traces and large context requirements make them impractical for edge deployment. These challenges include high token generation costs, large KV-cache footprints, and inefficiencies when distilling reasoning capabilities into smaller models for mobile devices. Existing approaches often rely on distilling reasoning traces from larger models into smaller models, which are verbose and stylistically redundant, undesirable for on-device inference. In this work, we propose a lightweight approach to enable reasoning in small LLMs using LoRA adapters combined with supervised fine-tuning. We further introduce budget forcing via reinforcement learning on these adapters, significantly reducing response length with minimal accuracy loss. To address memory-bound decoding, we exploit parallel test-time scaling, improving accuracy at minor latency increase. Finally, we present a dynamic adapter-switching mechanism that activates reasoning only when needed and a KV-cache sharing strategy during prompt encoding, reducing time-to-first-token for on-device inference. Experiments on Qwen2.5-7B demonstrate that our method achieves efficient, accurate reasoning under strict resource constraints, making LLM reasoning practical for mobile scenarios. Videos demonstrating our solution running on mobile devices are available on our project page.

Abstract

Automata Learning

Explore similar work

Efficient Reasoning on the Edge

Policy-Guided Stepwise Model Routing for Cost-Effective Reasoning

RouteGoT: Node-Adaptive Routing for Cost-Efficient Graph of Thoughts Reasoning